# On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2018.

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

- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses](https://mlsanity.com/paper/2104.14562/) (2021)
- [Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees](https://mlsanity.com/paper/2305.15249/) (2023)
- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms](https://mlsanity.com/paper/2404.08073/) (2024)
- [Natural Gradient VI: Guarantees for Non-Conjugate Models](https://mlsanity.com/paper/2510.19163/) (2025)
- [Sparse Training of Neural Networks based on Multilevel Mirror Descent](https://mlsanity.com/paper/2602.03535/) (2026)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Riemannian Stochastic Gradient Method for Nested Composition Optimization](https://mlsanity.com/paper/2207.09350/) (2022)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [Non-KKT Accumulation in Entropic Mirror Descent](https://mlsanity.com/paper/2608.01658/) (2026)
- [SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm](https://mlsanity.com/paper/2202.02797/) (2022)
- [Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization](https://mlsanity.com/paper/2406.19475/) (2024)
- [Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization](https://mlsanity.com/paper/2608.07248/) (2026)

## Abstract (arXiv)

In this paper, we investigate the non-asymptotic stationary convergence behavior of Stochastic Mirror Descent (SMD) for nonconvex optimization. We focus on a general class of nonconvex nonsmooth stochastic optimization problems, in which the objective can be decomposed into a relatively weakly convex function (possibly non-Lipschitz) and a simple non-smooth convex regularizer. We prove that SMD, without the use of mini-batch, is guaranteed to converge to a stationary point in a convergence rate of  O(1/√t) . The efficiency estimate matches with existing results for stochastic subgradient method, but is evaluated under a stronger stationarity measure. Our convergence analysis applies to both the original SMD and its proximal version, as well as the deterministic variants, for solving relatively weakly convex problems.