mlsanityData to 7 Oct 2026

Loss minimization and parameter estimation with heavy tails

arXiv 1307.1827 ↗First posted 7 Jul 2013cs.LG stat.MLcited by 50

Not on the map. Why?

Abstract (arXiv)

This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded low-order moments. We show that the technique can be used for approximate minimization of smooth and strongly convex losses, and specifically for least squares linear regression. For instance, our d-dimensional estimator requires just tildeO(dlog(1/δ)) random samples to obtain a constant factor approximation to the optimal least squares loss with probability 1-δ, without requiring the covariates or noise to be bounded or subgaussian. We provide further applications to sparse linear regression and low-rank covariance matrix estimation with similar allowances on the noise and covariate distributions. The core technique is a generalization of the median-of-means estimator to arbitrary metric spaces.

Key facts. Cited by 50 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Jul 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 15; 2023: 10; 2024: 5; 2025: 6; 2026: 6.

50 papers.

Sort:

By area:

  1. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  2. 2022Rank-based Decomposable Losses in Machine Learning: A Surveycited by 26
  3. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 22
  4. 2022Why does Throwing Away Data Improve Worst-Group Error?cited by 22
  5. 2021Distribution-Free Robust Linear Regressioncited by 19
  6. 2021Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systemscited by 17
  7. 2023High-dimensional robust regression under heavy-tailed data: Asymptotics and Universalitycited by 15
  8. 2021Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inferencecited by 11
  9. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  10. 2022Robust Imitation Learning from Corrupted Demonstrationscited by 10
  11. 2022Minimax risk classifiers with 0-1 losscited by 9
  12. 2024On Goodhart's law, with an application to value alignmentcited by 9
38 more
  1. 2021On the benefits of maximum likelihood estimation for Regression and Forecastingcited by 8
  2. 2022Byzantine-Robust Federated Linear Banditscited by 7
  3. 2022Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recoverycited by 7
  4. 2023Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Productscited by 7
  5. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  6. 2022Robust Methods for High-Dimensional Linear Learningcited by 5
  7. 2023Geometry-Aware Adaptation for Pretrained Modelscited by 5
  8. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  9. 2023Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basiscited by 4
  10. 2022Robust supervised learning with coordinate gradient descentcited by 3
  11. 2022On Medians of (Randomized) Pairwise Meanscited by 3
  12. 2023Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learningcited by 3
  13. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  14. 2024Minimax Linear Regression under the Quantile Riskcited by 3
  15. 2025Regularized least squares learning with heavy-tailed noise is minimax optimalcited by 3
  16. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  17. 2021Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimizationcited by 2
  18. 2021Posterior concentration and fast convergence rates for generalized Bayesian learningcited by 2
  19. 2022Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problemscited by 2
  20. 2022Tailoring to the Tails: Risk Measures for Fine-Grained Tail Sensitivitycited by 2
  21. 2025Locally minimax optimal confidence sets for the best modelcited by 2
  22. 2023Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Normcited by 1
  23. 2024Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Methodcited by 1
  24. 2025Robust and Scalable Variational Bayescited by 1
  25. 2025Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Boundscited by 1
  26. 2025High-Probability Bounds For Heterogeneous Local Differential Privacycited by 1
  27. 2026Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Momentscited by 1
  28. 2022A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noisecited by 0
  29. 2022Robust High-dimensional Tuning Free Multiple Testingcited by 0
  30. 2023Robust variance-regularized risk minimization with concomitant scalingcited by 0
  31. 2023Empirical Risk Minimization for Losses without Variancecited by 0
  32. 2023A Consistent and Scalable Algorithm for Best Subset Selection in Single Index Modelscited by 0
  33. 2024Subsampled Ensemble Can Improve Generalization Tail Exponentiallycited by 0
  34. 2025On the Optimality of the Median-of-Means Estimator under Adversarial Contaminationcited by 0
  35. 2026Metric space valued Fr'echet regressioncited by 0
  36. 2026HOMER: Huber-of-Means for Efficient and Robust Estimation in Hilbert Spacescited by 0
  37. 2026Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oraclecited by 0
  38. 2026Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Mapscited by 0