# On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 29 May 2021.

## Builds on (most cited first, 22 of 22)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Dissipativity Theory for Nesterov's Accelerated Method](https://mlsanity.com/paper/1706.04381/) (2017)
- [Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems](https://mlsanity.com/paper/1705.03615/) (2017)
- [Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions](https://mlsanity.com/paper/1805.10579/) (2018)
- [Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication](https://mlsanity.com/paper/1401.4432/) (2014)
- [The proximal augmented Lagrangian method for nonsmooth composite optimization](https://mlsanity.com/paper/1610.04514/) (2016)
- [Distributed Mirror Descent for Online Composite Optimization](https://mlsanity.com/paper/2004.00837/) (2020)
- [A Proximal Approach for a Class of Matrix Optimization Problems](https://mlsanity.com/paper/1801.07452/) (2018)
- [Convergence of the Iterates in Mirror Descent Methods](https://mlsanity.com/paper/1805.01526/) (2018)
- [Analysis and Design of First-Order Distributed Optimization Algorithms over Time-Varying Graphs](https://mlsanity.com/paper/1907.05448/) (2019)
- [Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization](https://mlsanity.com/paper/1610.04702/) (2016)
- [Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation](https://mlsanity.com/paper/1905.02637/) (2019)
- [Convex Synthesis of Accelerated Gradient Algorithms](https://mlsanity.com/paper/2102.06520/) (2021)
- [RLC Circuits based Distributed Mirror Descent Method](https://mlsanity.com/paper/1911.06273/) (2019)
- [Distributed Continuous-Time Algorithm for Constrained Convex Optimizations via Nonsmooth Analysis Approach](https://mlsanity.com/paper/1510.07386/) (2015)
- [Distributed Mirror Descent with Integral Feedback: Asymptotic Convergence Analysis of Continuous-time Dynamics](https://mlsanity.com/paper/2009.06747/) (2020)
- [Linear Convergence of Distributed Mirror Descent with Integral Feedback for Strongly Convex Problems](https://mlsanity.com/paper/2011.12233/) (2020)

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

- [Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking](https://mlsanity.com/paper/2506.07351/) (2025)
- [Estimating Mixture Distributions via Stochastic Mirror Descent](https://mlsanity.com/paper/2605.24929/) (2026)

## Abstract (arXiv)

Mirror descent (MD) is a powerful first-order optimization technique that subsumes several optimization algorithms including gradient descent (GD). In this work, we develop a semi-definite programming (SDP) framework to analyze the convergence rate of MD in centralized and distributed settings under both strongly convex and non-strongly convex assumptions. We view MD with a dynamical system lens and leverage quadratic constraints (QCs) to provide explicit convergence rates based on Lyapunov stability. For centralized MD under strongly convex assumption, we develop a SDP that certifies exponential convergence rates. We prove that the SDP always has a feasible solution that recovers the optimal GD rate as a special case. We complement our analysis by providing the O(1/k) convergence rate for convex problems. Next, we analyze the convergence of distributed MD and characterize the rate using SDP. To the best of our knowledge, the numerical rate of distributed MD has not been previously reported in the literature. We further prove an O(1/k) convergence rate for distributed MD in the convex setting. Our numerical experiments on strongly convex problems indicate that our framework certifies superior convergence rates compared to the existing rates for distributed GD.