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})。

分散式在线凸优化的近优遗憾

Nearly Optimal Regret for Decentralized Online Convex Optimization

This paper studies decentralized online convex optimization in a networked
multi-agent system and proposes a novel algorithm, Learning-Augmented
Decentralized Online optimization (LADO), for individual agents to select
actions only based on local online information. LADO leverages a baseline
policy to safeguard online actions for worst-case robustness guarantees, while
staying close to the machine learning (ML) policy for average performance
improvement. In stark contrast with the existing learning-augmented online
algorithms that focus on centralized settings, LADO achieves strong robustness
guarantees in a decentralized setting. We also prove the average cost bound for
LADO, revealing the tradeoff between average performance and worst-case
robustness and demonstrating the advantage of training the ML policy by
explicitly considering the robustness requirement.

本文讨论了基于网络化多智能体系统的分散在线凸优化，并提出了一种新的算法 —— 学习增强的分散式在线优化（LADO），使个体代理人仅基于本地在线信息选择动作。与现有的集中式学习增强在线算法形成鲜明对比，LADO 实现了分散式设置下的强大的鲁棒性保证。我们还证明了 LADO 的平均成本限制，揭示了平均性能和最坏情况下鲁棒性之间的权衡，并表明通过明确考虑鲁棒性要求来训练 ML 策略的优势。