# Distributed Mirror Descent for Online Composite Optimization

arXiv: https://arxiv.org/abs/2004.00837 · HTML: https://mlsanity.com/paper/2004.00837/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2020.

## Built on by (most cited first, 10 of 10)

- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints](https://mlsanity.com/paper/2105.14385/) (2021)
- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading](https://mlsanity.com/paper/2509.06466/) (2025)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Achieving Efficient Distributed Machine Learning Using a Novel Non-Linear Class of Aggregation Functions](https://mlsanity.com/paper/2201.12488/) (2022)
- [Aggregation in the Mirror Space (AIMS): Fast, Accurate Distributed Machine Learning in Military Settings](https://mlsanity.com/paper/2210.16181/) (2022)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)

## Abstract (arXiv)

In this paper, we consider an online distributed composite optimization problem over a time-varying multi-agent network that consists of multiple interacting nodes, where the objective function of each node consists of two parts: a loss function that changes over time and a regularization function. This problem naturally arises in many real-world applications ranging from wireless sensor networks to signal processing. We propose a class of online distributed optimization algorithms that are based on approximate mirror descent, which utilize the Bregman divergence as distance-measuring function that includes the Euclidean distances as a special case. We consider two standard information feedback models when designing the algorithms, that is, full-information feedback and bandit feedback. For the full-information feedback model, the first algorithm attains an average regularized regret of order O(1/√T) with the total number of rounds T. The second algorithm, which only requires the information of the values of the loss function at two predicted points instead of the gradient information, achieves the same average regularized regret as that of the first algorithm. Simulation results of a distributed online regularized linear regression problem are provided to illustrate the performance of the proposed algorithms.