Research map / Bandits and online learning / Online convex optimization and games
Revisiting Decentralized Online Convex Optimization with Compressed Communication
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes two follow-the-regularized-leader (FTRL)-type algorithms (CD-FTGL for full information, CD-FTBL for bandit) for decentralized online convex optimization with compressed communication, using Choco-Gossip on dual variables.
Problem
Decentralized online convex optimization (D-OCO) with compressed communication: existing compressed algorithms are OGD-based, complex, and have large dependence on spectral gap, compression ratio and network size; bandit variants also need many communication rounds.
Approach
Apply Choco-Gossip to the dual variables of FTRL (cumulative gradients) rather than to primal decisions, so consensus error is unaffected by the projection; combined with blocking, warm-started gossip across blocks, and one-point gradient estimation for bandit feedback with sublinear communication rounds.
Key results
- CD-FTGL matches the existing best full-information regret bounds Õ(ω^{-1/2}ρ^{-1} n√T) and Õ(ω^{-1}ρ^{-2} n log T) for convex and strongly convex losses.
- CD-FTBL improves bandit regret to O(nT^{3/4}) (convex) and O(nT^{2/3}(log T)^{1/3}) (strongly convex) versus prior Õ(ω^{-1/4}ρ^{-1/2}nT^{3/4}) and Õ(ω^{-1/3}ρ^{-2/3}nT^{2/3}(log T)^{1/3}).
- CD-FTBL needs only about 2,000 communication rounds in experiments versus at least 10,000 for bandit baselines, and yields lower loss per transmitted bit on ijcnn1 and a9a with 9 nodes.
Surprising findings
- Bandit algorithm's communication rounds are sublinear in T (Õ(ω^{-1}ρ^{-2}√T)), a reduction not achieved by prior compressed bandit D-OCO methods.
Limitations
- Full-information regret still has a gap in rho versus AD-FTGL which uses accelerated gossip.
- Assumes oblivious adversary and bounded/Lipschitz losses; bandit setting needs shrunk decision set and smoothing.
- Experiments limited to logistic regression on two LIBSVM datasets with 9 nodes and Top-k compressor.
Experimental setup
Datasets: ijcnn1 a9a
Benchmarks: ijcnn1 a9a
Metrics: average cumulative loss vs communication rounds average cumulative loss vs transmitted bits regret bound order
Baselines: Top-DOGD DC-DOGD Top-DOBD-1 DC-DOBD AD-FTGL
Builds on: AD-FTGL Choco-Gossip one-point gradient estimator D-OGD Top-DOGD
Closest papers by meaning
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.95)
- Distributed Online Convex Optimization with Compressed Communication (NeurIPS 2022 · similarity 0.93)
- Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.89)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.88)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.87)
- Revisiting Differentially Private Algorithms for Decentralized Online Learning (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.