# A Distributed Online Convex Optimization Algorithm with Improved Dynamic Regret

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2019.

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

- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [Locally Differentially Private Gradient Tracking for Distributed Online Learning over Directed Graphs](https://mlsanity.com/paper/2310.16105/) (2023)
- [Gradient and Projection Free Distributed Online Min-Max Resource Optimization](https://mlsanity.com/paper/2112.03896/) (2021)
- [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)
- [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)

## Abstract (arXiv)

In this paper, we consider the problem of distributed online convex optimization, where a network of local agents aim to jointly optimize a convex function over a period of multiple time steps. The agents do not have any information about the future. Existing algorithms have established dynamic regret bounds that have explicit dependence on the number of time steps. In this work, we show that we can remove this dependence assuming that the local objective functions are strongly convex. More precisely, we propose a gradient tracking algorithm where agents jointly communicate and descend based on corrected gradient steps. We verify our theoretical results through numerical experiments.