# Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2019.

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

- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise](https://mlsanity.com/paper/2204.02593/) (2022)
- [Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2206.01095/) (2022)
- [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (2025)
- [Clip21: Error Feedback for Gradient Clipping](https://mlsanity.com/paper/2305.18929/) (2023)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise](https://mlsanity.com/paper/2208.08567/) (2022)
- [Large deviations rates for stochastic gradient descent with strongly convex functions](https://mlsanity.com/paper/2211.00969/) (2022)
- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [General Tail Bounds for Non-Smooth Stochastic Mirror Descent](https://mlsanity.com/paper/2312.07142/) (2023)
- [Efficient Distributed Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2502.04164/) (2025)
- [Robust Online Convex Optimization in the Presence of Outliers](https://mlsanity.com/paper/2107.01881/) (2021)
- [Stochastic Bilevel Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2509.14952/) (2025)
- [Flexible risk design using bi-directional dispersion](https://mlsanity.com/paper/2203.14434/) (2022)
- [Robust Stochastic Optimization via Gradient Quantile Clipping](https://mlsanity.com/paper/2309.17316/) (2023)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2602.13413/) (2026)
- [Parameter-free Gradient Temporal Difference Learning](https://mlsanity.com/paper/2105.04129/) (2021)
- [Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method](https://mlsanity.com/paper/2402.08992/) (2024)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [Robust learning with anytime-guaranteed feedback](https://mlsanity.com/paper/2105.11135/) (2021)
- [Making Robust Generalizers Less Rigid with Loss Concentration](https://mlsanity.com/paper/2408.03619/) (2024)
- [Stress-Aware Learning under KL Drift via Trust-Decayed Mirror Descent](https://mlsanity.com/paper/2510.15222/) (2025)
- [Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity](https://mlsanity.com/paper/2601.19730/) (2026)

## Abstract (arXiv)

We propose an approach to construction of robust non-Euclidean iterative algorithms for convex composite stochastic optimization based on truncation of stochastic gradients. For such algorithms, we establish sub-Gaussian confidence bounds under weak assumptions about the tails of the noise distribution in convex and strongly convex settings. Robust estimates of the accuracy of general stochastic algorithms are also proposed.