Nearly Optimal Regret for Decentralized Online Convex Optimization
Yuanyu Wan Tong Wei Mingli Song Lijun Zhang
We investigate decentralized online convex optimization (D-OCO), in which a
set of local learners are required to minimize a sequence of global loss
functions using only local computations and communications. Previous studies
have established $O(n^{5/4}\rho^{-1/2}\sqrt{T})$ and ${O}(n^{3/2}\rho^{-1}\log
T)$ regret bounds for convex and strongly convex functions respectively, where
$n$ is the number of local learners, $\rho<1$ is the spectral gap of the
communication matrix, and $T$ is the time horizon. However, there exist large
gaps from the existing lower bounds, i.e., $\Omega(n\sqrt{T})$ for convex
functions and $\Omega(n)$ for strongly convex functions. To fill these gaps, in
this paper, we first develop novel D-OCO algorithms that can respectively
reduce the regret bounds for convex and strongly convex functions to
$\tilde{O}(n\rho^{-1/4}\sqrt{T})$ and $\tilde{O}(n\rho^{-1/2}\log T)$. The
primary technique is to design an online accelerated gossip strategy that
enjoys a faster average consensus among local learners. Furthermore, by
carefully exploiting the spectral properties of a specific network topology, we
enhance the lower bounds for convex and strongly convex functions to
$\Omega(n\rho^{-1/4}\sqrt{T})$ and $\Omega(n\rho^{-1/2})$, respectively. These
lower bounds suggest that our algorithms are nearly optimal in terms of $T$,
$n$, and $\rho$.