Gradient-Variation and Small-Loss Regret for Decentralized Online Convex Optimization

We study decentralized online convex optimization over a fixed network of $N$ learners with spectral gap $\rho$, where learners communicate only with their neighbors. Existing algorithms achieve nearly optimal worst-case regret bounds, but do not adapt to benign loss sequences, such as those with small gradient variation or small comparator loss. To address this limitation, we propose Decentralized Optimistic Follow-the-Regularized-Leader with Gradient Tracking (DOFTRL-GT), which combines delay-compensated optimism with two-level gradient tracking via accelerated gossip. DOFTRL-GT achieves regret bounds of $\tilde{\mathcal{O}}(N\min \{{\rho }^{-3/4}\sqrt{V_T},{\rho }^{-1/4}\sqrt{F_T}\})$ for convex losses and $\tilde{\mathcal{O}}(N{\rho }^{-1/2}\log (2+\min \{V_T,F_T\}))$ for strongly convex losses, up to additive terms independent of $T$, $V_T$, and $F_T$. Here, $V_T$ denotes the gradient variation, $F_T$ the cumulative loss of the best fixed comparator, and $\tilde{\mathcal{O}}$ hides logarithmic factors in $N$ and $1/\rho$. We establish lower bounds that match the corresponding upper bounds up to logarithmic factors in their respective problem-dependent regimes, showing that convex gradient-variation and small-loss guarantees necessarily incur distinct ${\rho }^{-3/4}$ and ${\rho }^{-1/4}$, respectively. Finally, applications to offline optimization and stochastic-adversarial learning further demonstrate its ability to exploit benign loss sequences.