# Robust Stochastic Optimization via Gradient Quantile Clipping

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 104 references that are in the map.
- First posted on arXiv 29 Sep 2023.

## Builds on (most cited first, 30 of 31)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Robust subgaussian estimation of a mean vector in nearly linear time](https://mlsanity.com/paper/1906.03058/) (2019)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method](https://mlsanity.com/paper/1907.02707/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise](https://mlsanity.com/paper/2302.05437/) (2023)
- [Fast Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1902.01998/) (2019)
- [A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1908.04468/) (2019)
- [AutoClip: Adaptive Gradient Clipping for Source Separation Networks](https://mlsanity.com/paper/2007.14469/) (2020)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)

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

- [Smoothed Normalization for Efficient Distributed Private Optimization](https://mlsanity.com/paper/2502.13482/) (2025)
- [Flat-Consensus Diffusion for Robust Data Reshaping under Noisy Evaluator](https://mlsanity.com/paper/2609.32696/) (2026)
- [NouveauVoice: Generating Novel Pseudo Speakers for Voice Anonymization](https://mlsanity.com/paper/2607.03985/) (2026)

## Abstract (arXiv)

We introduce a clipping strategy for Stochastic Gradient Descent (SGD) which uses quantiles of the gradient norm as clipping thresholds. We prove that this new strategy provides a robust and efficient optimization algorithm for smooth objectives (convex or non-convex), that tolerates heavy-tailed samples (including infinite variance) and a fraction of outliers in the data stream akin to Huber contamination. Our mathematical analysis leverages the connection between constant step size SGD and Markov chains and handles the bias introduced by clipping in an original way. For strongly convex objectives, we prove that the iteration converges to a concentrated distribution and derive high probability bounds on the final estimation error. In the non-convex case, we prove that the limit distribution is localized on a neighborhood with low gradient. We propose an implementation of this algorithm using rolling quantiles which leads to a highly efficient optimization procedure with strong robustness properties, as confirmed by our numerical experiments.