Revisiting Decentralized Online Convex Optimization with Compressed Communication

2026-07-02 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

Two novel Follow-the-Regularized-Leader (FTRL)-type algorithms are introduced for Decentralized Online Convex Optimization (D-OCO) with compressed communication, a framework crucial for distributed applications handling streaming data. While previous D-OCO studies with compressed communication relied on Online Gradient Descent (OGD)-type algorithms, and FTRL variants were only optimal for exact communication, this work bridges that gap. The proposed FTRL-type algorithms are presented as more elegant in design and theoretical analysis, leveraging FTRL's dual update mechanism to simplify average consensus with communication compression. The first algorithm addresses the full-information setting, matching existing regret bounds. The second algorithm targets the bandit setting, achieving significant improvements in both regret bounds and communication costs compared to current algorithms.

Key takeaway

For AI Scientists designing decentralized online convex optimization (D-OCO) systems with streaming data, you should re-evaluate algorithm choices. This research demonstrates that FTRL-type algorithms, previously limited to exact communication, now offer more elegant designs and significantly improved performance for compressed communication, particularly in bandit settings. Consider adopting these FTRL variants over traditional OGD-type approaches to enhance regret bounds and reduce communication costs in your distributed applications.

Key insights

FTRL-type algorithms can significantly improve decentralized online convex optimization with compressed communication.

Principles

• FTRL's dual update mechanism simplifies communication compression.
• Compressed communication can be integrated into D-OCO via FTRL.

Method

Apply FTRL's dual update mechanism to integrate average consensus with communication compression for D-OCO.

In practice

• Improve D-OCO performance in bandit settings.
• Reduce communication costs in distributed streaming applications.

Topics

• Decentralized Online Convex Optimization
• Compressed Communication
• Follow-the-Regularized-Leader
• Online Gradient Descent
• Bandit Algorithms
• Distributed Machine Learning

Best for: Research Scientist, AI Scientist

Related on AIssential

• Adaptive Decentralized Composite Optimization via Three-Operator Splitting — Adaptive decentralized optimization methods use local backtracking and min-consensus for robust convergence in network settings.
• Efficient Gradient Methods for Distributed Saddle Problems — A novel decoupled method achieves optimal communication and improved oracle costs for distributed saddle problems.
• Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation — The paper provides information-theoretic lower bounds for bit-constrained stochastic optimization, linking it to compressed Gaussian mean estimation.
• Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry — q-PDGD offers efficient distributed optimization with quantized communication, matching centralized stochastic rates under relaxed geometric conditions.
• Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback — A new uncoupled learning algorithm achieves $\tilde{O}(T^{-1/4})$ last-iterate convergence in bilinear saddle-point problems with bandit feedback.
• Semiglobal Input-Delay Tolerance Algorithm for Distributed Nonconvex Optimization of Networked Nonlinear Systems — The SIDT algorithm enables distributed optimization in networked nonlinear systems despite input delays and nonconvexity.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.