mlsanityData to 14 Oct 2026

Heavy-tailed Streaming Statistical Estimation

arXiv 2108.11483 ↗First posted 25 Aug 2021cs.LG math.OC stat.MLcited by 10

Not on the map. Why?

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.

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

33 of 61 references.

References · 33

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Deep Learning with Differential Privacycited by 2,728
  3. 2017Improved Training of Wasserstein GANscited by 2,235
  4. 2014Convex Optimization: Algorithms and Complexitycited by 575
  5. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
  6. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  7. 2019SGD: General Analysis and Improved Ratescited by 207
  8. 2019Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networkscited by 159
  9. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  10. 2020Understanding Gradient Clipping in Private SGD: A Geometric Perspectivecited by 142
  11. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  12. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
21 more
  1. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  2. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  3. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  4. 2017Adaptive Huber Regressioncited by 60
  5. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  6. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  7. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
  8. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  9. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  10. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  11. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  12. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  13. 2021On Proximal Policy Optimization's Heavy-tailed Gradientscited by 31
  14. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 27
  15. 2019Adaptive Hard Thresholding for Near-optimal Consistent Robust Regressioncited by 23
  16. 2019Fast Mean Estimation with Sub-Gaussian Ratescited by 18
  17. 2020High-Dimensional Robust Mean Estimation via Gradient Descentcited by 16
  18. 2019A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Ratescited by 12
  19. 2019A Unified Approach to Robust Mean Estimationcited by 11
  20. 2018An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimizationcited by 8
  21. 2019Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimizationcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 4; 2024: 2; 2025: 0; 2026: 1.

10 papers.

  1. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 24
  2. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  3. 2021Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimationcited by 15
  4. 2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 11
  5. 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
  6. 2024Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetrycited by 7
  7. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  8. 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guaranteescited by 1
  9. 2023Online Heavy-tailed Change-point detectioncited by 0
  10. 2026Online Distributional Prediction via Latent Cluster Geometry Under Drift and Corruptioncited by 0