Decentralized Online Exp-Concave Optimization

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 $\mathcal{O}\left(Nd(1-{\sigma }_2{)}^{-1/2}{\log }^2(T)\right)$ where $N$ is the number of agents, $d$ is the dimension, $T$ is the horizon, and $1-{\sigma }_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 $\Omega \left(Nd(1-{\sigma }_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 achieve logarithmic regret.