CS Paper Radar

Decentralized Online Exp-Concave Optimization

Hao Qiu, Mengxiao Zhang, Yuanyu Wan

cs.LG ·submitted 2026-10-18 04:56 UTC · v1
theory

Abstract

Decentralized Online Convex Optimization (D-OCO) is a fundamental framework in which a set of local agents aims to minimize a sequence of global loss functions using only local computations and communications. While recent work has established near-optimal regret guarantees for convex and strongly convex losses, the case of exp-concave losses remains an open challenge: specifically, whether logarithmic regret is achievable. In this paper, we answer this question affirmatively by proposing Decentralized Online Newton Step (D-ONS), which adapts the idea of blocking and accelerated gossip to the Online Newton Step algorithm in a non-trivial manner. Concretely, our algorithm achieves a regret bound of $O\left(Nd(1-σ_2)^{-1/2}\,\log^2(T) \right)$ where $N$ is the number of agents, $d$ is the dimension, $T$ is the horizon, and $1-σ_2$ represents the spectral gap of the network. To our knowledge, this is the first logarithmic regret bound for decentralized online exp-concave optimization. We further establish a nearly matching lower bound of $Ω\left(Nd (1-σ_2)^{-1/2}\,\log(T/N) \right)$ showing the near optimality of our upper bound. Finally, we extend our algorithm to decentralized online linear regression in which the feasible domain is unbounded and features and labels are locally observed. By gossiping covariance and label-feature statistics, we also achieve logarithmic regret.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Regret for Communication-Efficient Decentralized Online Learning

cs.LG ·2026-10-28 ·Sifan Yang, Wenhao Yang, Wei Jiang, Yuanyu Wan, Lijun Zhang
similarity 0.74
Abstract

In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $ρ\in(0,1)$ is the spectral gap of the communication matrix and $ω\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $ρ^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ for convex and strongly convex loss functions, respectively. Up to logarithmic factors in $n$ and $ρ^{-1}$, these results match the lower bounds in terms of $T$, $n$, $ρ$, and $ω$.

0.10

Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds

cs.LG math.OCstat.ML ·2026-09-12 ·Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour
theoryhot direction similarity 0.70
Abstract · 6 pages, 2 figures

This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish $O(\sqrt{T})$ and $O(\log T)$ static regret, respectively, matching the corresponding Euclidean rates with respect to $T$, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.

0.35

Strongly Adaptive Online Learning Achieves Uniform Discounted Regret

cs.LG ·2026-10-29 ·Sifan Yang, Wenhao Yang, Lijun Zhang
similarity 0.69
Abstract

Discounted regret measures the performance of an online learner by assigning exponentially decaying weights to past losses, reflecting the greater importance of recent losses in non-stationary online learning. While previous work obtains uniform discounted regret bounds over a continuous range of discount factors using a specialized meta-algorithm, its results are limited to convex functions. In this paper, we demonstrate that strongly adaptive regret bounds can directly imply uniform discounted regret guarantees for convex, strongly convex, and exp-concave loss functions. Our key observation is that discounted regret against a fixed comparator admits an exact decomposition into a convex combination of interval regrets. For convex functions, this reduction yields an $O(\sqrt{\log T/(1-λ)})$ discounted regret bound for all discount factors $λ\in(0,1)$, matching the previous rate over a broader range of discount factors. For strongly convex and exp-concave functions, we provide regret bounds of $O\left(\log T\left(1+\log\frac{1}{1-λ}\right)\right)$.

0.16

Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes

cs.LG cs.DSmath.OC ·2026-09-09 ·Akira Kitaoka
theory similarity 0.68
Abstract · 56 pages

In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of $\log T$ between the regret upper bound $O(d \log T)$ and the lower bound $Ω(d)$ is unresolved (here $T$ is the total number of rounds and $d$ is the dimension). When the action set is M-convex, the regret is known to be bounded by $O(d \log d)$, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake, and applies it to online gradient descent, the online Newton step, and MetaGrad. When the forward problem is an integer linear program with a unique optimal solution, the number of mistakes is bounded, for all three, by a quantity independent of $T$; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes $O(d^2)$, that is, the factor $\log T$ is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.

0.49

Tracking a Small Set of Experts in Online Convex Optimization

cs.LG math.OCstat.ML ·2026-10-14 ·Angelos Assos, Anand Brahmbhatt, Elad Hazan
similarity 0.68
Abstract

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches $k$ times among only $m$ experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of $\widetilde{O}(md+k)$, while the best known efficient algorithm for this problem has regret $\widetilde{O}(dk)$. We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least $(k\sqrt d)^{1-o(1)}$ regret.

0.19

$\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO

cs.LG ·2026-10-02 ·Dhruv Sarkar, Abhishek Sinha
similarity 0.68
Abstract

We study constrained online convex optimization with adversarial convex costs and constraints ($\mathsf{COCO}$). At each round $t\in[T]$, a learner selects $x_t$ from a $d$-dimensional convex decision set $X$, after which an adaptive adversary reveals a convex cost function $f_t$ and constraint function $g_t$. Consequently, the learner incurs a cost of $f_t(x_t)$ and a constraint violation of $\max\{0,g_t(x_t)\}$, and aims to simultaneously minimize regret and cumulative constraint violation ($\mathsf{CCV}$) over the entire horizon. Existing algorithms achieve $O(\sqrt{T})$ regret and $\widetilde O(\sqrt{T})$ $\mathsf{CCV}$. We show that an online policy can achieve $O(\sqrt{T\log T})$ regret and $O(\log^2 T)$ $\mathsf{CCV}$, reducing the $\mathsf{CCV}$ from polynomial to polylogarithmic while retaining near-optimal regret. When all cost functions are either $α$-exp-concave or $β$-strongly convex, the algorithm achieves $O(\log T)$ regret with the same $\mathsf{CCV}$ bound as above. Our approach combines continuous Hedge with elimination on shrinking feasible sets. The key observation is that whenever the mean of the Hedge distribution violates a constraint, Grünbaum's inequality guarantees that a constant fraction of the Hedge probability mass is eliminated. We use an adaptive learning-rate schedule and a potential function coupling the surviving volume with the learning rate to convert this probability-mass reduction into a bound of $O(\log^2 T)$ on the $\mathsf{CCV}$.

0.10

Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback

cs.LG cs.DSstat.ML ·2026-10-12 ·Tao Hu, Rohan Ghuge
similarity 0.67
Abstract · 68 pages, 20 figures, 1 table

Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, \citet{agarwal2026semibandit} give an online-to-offline reduction for monotone stochastic optimization under semi-bandit feedback, where only probed variables are observed. Its expected regret relative to the offline guarantee is $\widetilde O(n\sqrt T)$, where $n$ is the number of variables and $T$ the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve $\widetilde O(\sqrt{nT})$ using problem-specific algorithms. \emph{Can a general online-to-offline reduction achieve this improved rate?} We give such a reduction for strongly monotone stochastic optimization, answering the corresponding open question. Strong monotonicity is defined relative to the chosen offline algorithm. Our oracle-efficient reduction achieves $\widetilde O(\sqrt{nT})$ expected regret while preserving approximation guarantees for oracles satisfying the same condition. It combines Bernstein-type optimistic distribution estimates with a Hellinger stability bound for adaptive policy transcripts, aggregating squared marginal errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for $T\ge n$, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves $\widetilde O(n^{3/4}\sqrt T)$ expected approximation regret, improving the previous linear dependence on $n$. The exponent $3/4$ is sharp for its ordinary regret over instances and exact oracle choices. Our framework applies to prophet inequality, Pandora's box, best-of-$K$ selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.

0.39

Hardness of Online Directed Steiner Network

cs.DS ·2026-09-18 ·Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.67
Abstract

In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network design, heavily studied in both the offline and the online setting. Offline, it has a superpolylogarithmic hardness of approximation. However, offline hardness says nothing about online algorithms, which are computationally unrestricted. It has been an open question whether uncertainty itself (needing to commit to a solution without knowing future demands) rules out polylogarithmic-competitive online algorithms. In this work, we show the first such unconditional, information-theoretic hardness. Namely, we give an $\exp\!\bigl(Ω(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs. Our proof uses a novel connection between online network design and algebraic coding theory. We encode requests using a hidden low-degree polynomial, whose past evaluations reveal nothing about future ones. We then use list-recovery bounds to show that an algorithm cannot make cheaply reusable decisions without knowing those future evaluations.

0.18