Optimal regret bounds achieved for decentralized online learning
Optimal Regret for Communication-Efficient Decentralized Online Learning
Machine Learning
Summary
This paper deals with teaching many computers working together how to learn from data that changes over time, using limited communication between them. Previous methods had inefficiencies in how fast the computers could agree and learn, measured by something called regret. The authors improved these methods by developing a new communication technique called Ascent-gossip that speeds up consensus while using compressed messages. Their final algorithm reaches the best possible performance in how quickly it learns, matching theoretical limits except for some small technical factors.
What this means in practice
- •For distributed system engineers: Improve the efficiency of collaborative machine learning across networked devices with limited bandwidth by using faster consensus methods with compressed communication.
- •For network algorithm designers: Develop network protocols that optimize information exchange for online learning tasks by exploiting spectral properties and compression.
Authors
Sifan Yang, Wenhao Yang, Wei Jiang, Yuanyu Wan, Lijun Zhang
Abstract
In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $ρ\in(0,1)$ is the spectral gap of the communication matrix and $ω\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $ρ^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ for convex and strongly convex loss functions, respectively. Up to logarithmic factors in $n$ and $ρ^{-1}$, these results match the lower bounds in terms of $T$, $n$, $ρ$, and $ω$.