Research map / Bandits and online learning / Online convex optimization and games

Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Constrained and unconstrained OCO algorithms · 0 citations (OpenAlex)

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.

Studies distributed online convex optimization (D-OCO) with δ-contractive compressed communication between learners and a central server, proposing D-FTCL (error feedback in FTRL, regret O(δ^-1√T)) and D-FTFCL (online fast compressed communication with blocking, regret O(δ^-1/2√T) and O(δ^-1 log T)), matched by new lower bounds, plus an online-to-batch extension to distributed stochastic non-smoot

Problem

Distributed online convex optimization with a central server suffers high communication cost; existing error-feedback methods fail to control the coupled compression and projection errors under domain constraints, and no optimal regret bounds exist for compressed D-OCO.

Approach

Integrates error feedback into FTRL so projection error does not propagate into later compression steps, applies bidirectional EF, then uses online fast compressed communication over blocks of size L≈1/δ (with delayed updates) to reduce amplified compression error and attain matching lower bounds.

Key results

• D-FTCL achieves regret O(δ^-1√T) for convex and O(δ^-2 log T) for strongly convex losses under bidirectional compression.
• D-FTFCL with block size L=⌈1/δ⌉ achieves O(δ^-1/2√T) and O(δ^-1 log T) regret, matching the lower bounds Ω(δ^-1/2√T) and Ω(δ^-1 log T).
• The offline extension attains last-iterate rates O(δ^-1/2 T^-1/2) for convex and O((μD+G)^2/(μδT)) for strongly convex non-smooth distributed optimization with domain constraints.

Limitations

• Optimal guarantees require block size L=⌈1/δ⌉ from worst-case analysis; practical smaller L is unanalyzed.
• Asynchronous two-block delay complicates analysis; updates use stale information.
• Smooth-loss improvement via optimistic methods left open since compressed gradients alone are insufficient for optimistic terms.

Experimental setup

Metrics: regret convergence rate

Baselines: D-FTCL

Builds on: Follow-the-Regularized-Leader error feedback (EF) fast compressed communication (FCC) anytime online-to-batch conversion EF21

Closest papers by meaning

• Revisiting Decentralized Online Convex Optimization with Compressed Communication (NeurIPS 2026 · similarity 0.95)
• Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.90)
• Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.90)
• Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.90)
• Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.89)
• Universal Online Convex Optimization with $1$ Projection per Round (NeurIPS 2024 · similarity 0.89)