# A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 52 references that are in the map.
- First posted on arXiv 13 Mar 2026.

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

- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [The Information Geometry of Mirror Descent](https://mlsanity.com/paper/1310.7780/) (2013)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems](https://mlsanity.com/paper/1706.06461/) (2017)
- [Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning](https://mlsanity.com/paper/1709.06293/) (2017)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Greedy Quasi-Newton Methods with Explicit Superlinear Convergence](https://mlsanity.com/paper/2002.00657/) (2020)
- [Zeroth Order Nonconvex Multi-Agent Optimization over Networks](https://mlsanity.com/paper/1710.09997/) (2017)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity](https://mlsanity.com/paper/2102.10312/) (2021)
- [Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization](https://mlsanity.com/paper/1610.04702/) (2016)
- [Stochastic Bregman Proximal Gradient Method Revisited: Kernel Conditioning and Painless Variance Reduction](https://mlsanity.com/paper/2401.03155/) (2024)
- [Rate analysis of dual averaging for nonconvex distributed optimization](https://mlsanity.com/paper/2211.06914/) (2022)
- [Randomized Block Proximal Methods for Distributed Stochastic Big-Data Optimization](https://mlsanity.com/paper/1905.04214/) (2019)
- [Bregman Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/2208.05102/) (2022)
- [Privacy-Preserving Distributed Online Mirror Descent for Nonconvex Optimization](https://mlsanity.com/paper/2501.04222/) (2025)

## Abstract (arXiv)

Existing convergence analyses of distributed optimization methods in non-Euclidean geometries typically rely on kernel assumptions: (i) global Lipschitz smoothness and (ii) bi-convexity of the associated Bregman divergence function. Unfortunately, these conditions are violated by nearly all kernels used in practice, leaving a huge theory-practice gap. This work closes this gap by developing a unified analytical tool that guarantees convergence under mild conditions. Specifically, we introduce Hessian relative uniform continuity (HRUC), a regularity satisfied by nearly all standard kernels. Importantly, HRUC is closed under concatenation, positive scaling, composition, and various kernel combinations. Leveraging the geometric structure induced by HRUC, we derive convergence guarantees for mirror-descent-based gradient tracking without imposing any restrictive assumptions. More broadly, our analysis techniques extend seamlessly to other decentralized optimization methods in genuinely non-Euclidean and non-Lipschitz settings.