# Empirical risk minimization for heavy-tailed losses

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2014.

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

- [Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape](https://mlsanity.com/paper/2305.11584/) (2023)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Robust Imitation Learning from Corrupted Demonstrations](https://mlsanity.com/paper/2201.12594/) (2022)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [On the benefits of maximum likelihood estimation for Regression and Forecasting](https://mlsanity.com/paper/2106.10370/) (2021)
- [Non-Asymptotic Guarantees for Robust Statistical Learning under Infinite Variance Assumption](https://mlsanity.com/paper/2201.03182/) (2022)
- [On Regression in Extreme Regions](https://mlsanity.com/paper/2303.03084/) (2023)
- [A Survey of Learning Criteria Going Beyond the Usual Risk](https://mlsanity.com/paper/2110.04996/) (2021)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)
- [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)
- [Regularized least squares learning with heavy-tailed noise is minimax optimal](https://mlsanity.com/paper/2505.14214/) (2025)
- [Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2106.02888/) (2021)
- [Posterior concentration and fast convergence rates for generalized Bayesian learning](https://mlsanity.com/paper/2111.10243/) (2021)
- [Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems](https://mlsanity.com/paper/2205.13827/) (2022)
- [Tailoring to the Tails: Risk Measures for Fine-Grained Tail Sensitivity](https://mlsanity.com/paper/2208.03066/) (2022)
- [Distributional Robustness Bounds Generalization Errors](https://mlsanity.com/paper/2212.09962/) (2022)
- [On the Robustness of Kernel Ridge Regression Using the Cauchy Loss Function](https://mlsanity.com/paper/2503.20120/) (2025)
- [Robust Generalized Method of Moments: A Finite Sample Viewpoint](https://mlsanity.com/paper/2110.03070/) (2021)
- [Robust Mixture Learning when Outliers Overwhelm Small Groups](https://mlsanity.com/paper/2407.15792/) (2024)
- [Differentially Private Sparse Linear Regression with Heavy-tailed Responses](https://mlsanity.com/paper/2506.06861/) (2025)
- [Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound](https://mlsanity.com/paper/2603.06851/) (2026)
- [Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments](https://mlsanity.com/paper/2606.06855/) (2026)
- [Robust learning with anytime-guaranteed feedback](https://mlsanity.com/paper/2105.11135/) (2021)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)

## Abstract (arXiv)

The purpose of this paper is to discuss empirical risk minimization when the losses are not necessarily bounded and may have a distribution with heavy tails. In such situations, usual empirical averages may fail to provide reliable estimates and empirical risk minimization may provide large excess risk. However, some robust mean estimators proposed in the literature may be used to replace empirical means. In this paper, we investigate empirical risk minimization based on a robust estimate proposed by Catoni. We develop performance bounds based on chaining arguments tailored to Catoni's mean estimator.