# Heavy-tailed Streaming Statistical Estimation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 61 references that are in the map.
- First posted on arXiv 25 Aug 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks](https://mlsanity.com/paper/1903.11680/) (2019)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [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)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [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)
- [On Proximal Policy Optimization's Heavy-tailed Gradients](https://mlsanity.com/paper/2102.10264/) (2021)
- [Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent](https://mlsanity.com/paper/1909.00843/) (2019)
- [Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression](https://mlsanity.com/paper/1903.08192/) (2019)
- [Fast Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1902.01998/) (2019)
- [High-Dimensional Robust Mean Estimation via Gradient Descent](https://mlsanity.com/paper/2005.01378/) (2020)
- [A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1908.04468/) (2019)

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

- [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)
- [Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation](https://mlsanity.com/paper/2110.11271/) (2021)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise](https://mlsanity.com/paper/2310.18784/) (2023)
- [Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry](https://mlsanity.com/paper/2410.15637/) (2024)
- [Robust Stochastic Optimization via Gradient Quantile Clipping](https://mlsanity.com/paper/2309.17316/) (2023)
- [Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees](https://mlsanity.com/paper/2410.13954/) (2024)
- [Online Heavy-tailed Change-point detection](https://mlsanity.com/paper/2306.09548/) (2023)
- [Online Distributional Prediction via Latent Cluster Geometry Under Drift and Corruption](https://mlsanity.com/paper/2606.18778/) (2026)

## Abstract (arXiv)

We consider the task of heavy-tailed statistical estimation given streaming p-dimensional samples. This could also be viewed as stochastic optimization under heavy-tailed distributions, with an additional O(p) space complexity constraint. We design a clipped stochastic gradient descent algorithm and provide an improved analysis, under a more nuanced condition on the noise of the stochastic gradients, which we show is critical when analyzing stochastic optimization problems arising from general statistical estimation problems. Our results guarantee convergence not just in expectation but with exponential concentration, and moreover does so using O(1) batch size. We provide consequences of our results for mean estimation and linear regression. Finally, we provide empirical corroboration of our results and algorithms via synthetic experiments for mean estimation and linear regression.