Distributed Online Randomized Gradient-Free Optimization With Compressed Communication

Area of Science:

• Distributed Systems
• Optimization Theory
• Machine Learning

Background:

• Distributed online convex optimization (DOCO) faces challenges in communication efficiency and limited feedback.
• Existing methods often assume perfect communication and full gradient access, limiting practical application.

Purpose of the Study:

• To propose a unified framework, online compressed gradient tracking (OCGT), addressing communication efficiency and limited feedback in DOCO.
• To develop algorithms that reduce communication overhead while maintaining convergence guarantees.

Main Methods:

• Introduced OCGT with two variants: OCGT-BF (two-point bandit feedback) and OCSGT (stochastic gradient feedback).
• Employed data compression with error compensation and gradient-free or stochastic gradient optimization techniques.
• Combined gradient-like tracking with feedback estimation under practical communication constraints.

Main Results:

• Theoretical analysis provided dynamic regret bounds for both OCGT variants.
• Experimental validation demonstrated OCGT's ability to achieve low dynamic regret.
• Significant reduction in communication requirements was observed compared to traditional methods.

Conclusions:

• OCGT offers an effective solution for communication-efficient DOCO under limited feedback.
• The framework balances communication reduction with optimization performance.
• OCGT algorithms are practical for real-world distributed network scenarios.