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$.

我们在分散的在线凸优化中（D-OCO），通过仅使用本地计算和通信来最小化一系列全局损失函数的一组本地学习器。我们首先开发了一种新颖的 D-OCO 算法，将凸函数和强凸函数的遗憾边界分别降低到 O (nρ^{−1/4}√T) 和 O (nρ^{−1/2} log T)。通过设计一种在线加速的谣言策略并巧妙利用特定网络拓扑的谱特性，我们进一步提高了凸函数和强凸函数的下界为 Ω(nρ^{−1/4}√T) 和 Ω(nρ^{−1/2})。