# Loss minimization and parameter estimation with heavy tails

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

## Key facts

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

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

- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Why does Throwing Away Data Improve Worst-Group Error?](https://mlsanity.com/paper/2205.11672/) (2022)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems](https://mlsanity.com/paper/2105.11558/) (2021)
- [High-dimensional robust regression under heavy-tailed data: Asymptotics and Universality](https://mlsanity.com/paper/2309.16476/) (2023)
- [Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference](https://mlsanity.com/paper/2103.02860/) (2021)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [Robust Imitation Learning from Corrupted Demonstrations](https://mlsanity.com/paper/2201.12594/) (2022)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [On Goodhart's law, with an application to value alignment](https://mlsanity.com/paper/2410.09638/) (2024)
- [On the benefits of maximum likelihood estimation for Regression and Forecasting](https://mlsanity.com/paper/2106.10370/) (2021)
- [Byzantine-Robust Federated Linear Bandits](https://mlsanity.com/paper/2204.01155/) (2022)
- [Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Products](https://mlsanity.com/paper/2312.15469/) (2023)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Geometry-Aware Adaptation for Pretrained Models](https://mlsanity.com/paper/2307.12226/) (2023)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [On Medians of (Randomized) Pairwise Means](https://mlsanity.com/paper/2211.00603/) (2022)
- [Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning](https://mlsanity.com/paper/2309.04626/) (2023)
- [Robust Stochastic Optimization via Gradient Quantile Clipping](https://mlsanity.com/paper/2309.17316/) (2023)
- [Minimax Linear Regression under the Quantile Risk](https://mlsanity.com/paper/2406.12145/) (2024)
- [Locally minimax optimal confidence sets for the best model](https://mlsanity.com/paper/2503.21639/) (2025)
- [Regularized least squares learning with heavy-tailed noise is minimax optimal](https://mlsanity.com/paper/2505.14214/) (2025)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2106.02888/) (2021)

## 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.