# Distributed Online Optimization in Dynamic Environments Using Mirror Descent

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2016.

## Built on by (most cited first, 30 of 32)

- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Drift](https://mlsanity.com/paper/2211.12578/) (2022)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Distributed Online Private Learning of Convex Nondecomposable Objectives](https://mlsanity.com/paper/2206.07944/) (2022)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2406.01484/) (2024)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds](https://mlsanity.com/paper/2509.07779/) (2025)
- [QC-ODKLA: Quantized and Communication-Censored Online Decentralized Kernel Learning via Linearized ADMM](https://mlsanity.com/paper/2208.02777/) (2022)
- [Delay-Tolerant Constrained OCO with Application to Network Resource Allocation](https://mlsanity.com/paper/2105.04005/) (2021)
- [Optimization in Open Networks via Dual Averaging](https://mlsanity.com/paper/2105.13348/) (2021)
- [On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints](https://mlsanity.com/paper/2105.14385/) (2021)
- [Distributed Online Optimization with Byzantine Adversarial Agents](https://mlsanity.com/paper/2109.12340/) (2021)
- [Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions](https://mlsanity.com/paper/2202.12843/) (2022)
- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [Decentralized Online Convex Optimization with Unknown Feedback Delays](https://mlsanity.com/paper/2601.07901/) (2026)
- [Gradient and Projection Free Distributed Online Min-Max Resource Optimization](https://mlsanity.com/paper/2112.03896/) (2021)
- [Personalized incentives as feedback design in generalized Nash equilibrium problems](https://mlsanity.com/paper/2203.12948/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Optimized Gradient Tracking for Decentralized Online Learning](https://mlsanity.com/paper/2306.06375/) (2023)
- [Locally Differentially Private Distributed Online Learning with Guaranteed Optimality](https://mlsanity.com/paper/2306.14094/) (2023)
- [Distributed optimization: designed for federated learning](https://mlsanity.com/paper/2508.08606/) (2025)
- [Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions](https://mlsanity.com/paper/2607.20316/) (2026)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)
- [A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks](https://mlsanity.com/paper/2508.20645/) (2025)
- [A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis](https://mlsanity.com/paper/2603.12838/) (2026)
- [Distributed Optimization with Streaming Data: A Temporal Weighting Perspective](https://mlsanity.com/paper/2608.09565/) (2026)

## Abstract (arXiv)

This work addresses decentralized online optimization in non-stationary environments. A network of agents aim to track the minimizer of a global time-varying convex function. The minimizer evolves according to a known dynamics corrupted by an unknown, unstructured noise. At each time, the global function can be cast as a sum of a finite number of local functions, each of which is assigned to one agent in the network. Moreover, the local functions become available to agents sequentially, and agents do not have a prior knowledge of the future cost functions. Therefore, agents must communicate with each other to build an online approximation of the global function. We propose a decentralized variation of the celebrated Mirror Descent, developed by Nemirovksi and Yudin. Using the notion of Bregman divergence in lieu of Euclidean distance for projection, Mirror Descent has been shown to be a powerful tool in large-scale optimization. Our algorithm builds on Mirror Descent, while ensuring that agents perform a consensus step to follow the global function and take into account the dynamics of the global minimizer. To measure the performance of the proposed online algorithm, we compare it to its offline counterpart, where the global functions are available a priori. The gap between the two is called dynamic regret. We establish a regret bound that scales inversely in the spectral gap of the network, and more notably it represents the deviation of minimizer sequence with respect to the given dynamics. We then show that our results subsume a number of results in distributed optimization. We demonstrate the application of our method to decentralized tracking of dynamic parameters and verify the results via numerical experiments.