Source-linked AI summary
Mean estimation and regression under heavy-tailed distributions--a survey
Gabor Lugosi, Shahar Mendelson
TL;DR
Heavy-tailed data make reliable mean and regression estimation difficult, especially when high accuracy and high confidence are required. The paper surveys recent univariate, multivariate, and learning-theoretic advances, emphasizing median-of-means methods alongside Catoni-type approaches. It also identifies impossibility and estimator-specific limitations, including dependence on prior information and lack of translation invariance.
Problem
Heavy-tailed distributions and outliers challenge empirical mean estimation, while reliable high-accuracy, high-confidence mean and regression estimates remain important for machine learning and data science.
Method
The paper surveys sub-Gaussian mean estimators in univariate and multivariate settings, emphasizing median-of-means techniques and also discussing Catoni's estimator, uniform estimation, and regression applications.
Results
The survey shows that mean-estimation technology yields regression algorithms with essentially optimal performance under mild assumptions and discusses limits on simultaneous sub-Gaussian estimation across confidence levels.
Takeaways & Limitations
Median-of-means methodology provides a central framework for robust mean estimation and can be carried into regression under heavy-tailed data.
Takeaways & Limitations
Some multivariate estimators require prior knowledge and can have weaker bounds because they depend on the mean norm and lack translation invariance.
Abstract
from arXiv · showhide
We survey some of the recent advances in mean estimation and regression function estimation. In particular, we describe sub-Gaussian mean estimators for possibly heavy-tailed data both in the univariate and multivariate settings. We focus on estimators based on median-of-means techniques but other methods such as the trimmed mean and Catoni's estimator are also reviewed. We give detailed proofs for the cornerstone results. We dedicate a section on statistical learning problems--in particular, regression function estimation--in the presence of possibly heavy-tailed data.
1 Introduction
The introduction frames robust mean estimation as necessary when data may be heavy-tailed or contain outliers, and surveys recent efforts to achieve high accuracy with high confidence. It emphasizes median-of-means methods across univariate and multivariate mean estimation, extending the technology to regression under mild assumptions.
- Heavy-tailed distributions and outliers can undermine the quality of the empirical mean, motivating robust statistics for mean estimation.
- The survey examines the accuracy-confidence tradeoff for mean and regression function estimators motivated by machine learning and data science.
- It focuses on univariate and multivariate mean estimation, describing expected performance, estimator varieties, and their analyses.
- Median-of-means techniques receive special attention as a simple but powerful methodology.
- Mean-estimation technology is used to construct regression learning algorithms with essentially optimal performance under mild assumptions.
2 Estimating the mean of a real random variable
The section develops non-asymptotic mean estimation under finite-variance and heavier-tailed assumptions, showing that robust estimators can attain sub-Gaussian performance while confidence-independent estimation has fundamental limits.
- The empirical mean cannot generally provide sub-Gaussian confidence dependence when only a finite variance is assumed.Chebyshev-type bounds have the optimal O(n^-1/2) sample-size rate but substantially worse dependence on δ.
- Median-of-means estimator: Median-of-means estimation achieves sub-Gaussian performance for finite-variance distributions by partitioning observations into blocks and taking the median of block means.With k chosen proportional to log(1/δ), Theorem 2 gives L = 8.
- Median-of-means estimator: Under a finite (1 + α)-th central moment, median-of-means estimation achieves the corresponding optimal heavy-tail accuracy bound, and a matching lower bound applies to every estimator.The result covers α ∈ (0,1], including infinite-variance settings when α < 1.
- Median-of-means estimator: A finite third moment permits median-of-means estimators to remain sub-Gaussian over a wider range of block counts and confidence levels without depending on δ.The tradeoff is the additional third-moment assumption.
- Catoni’s estimator: Catoni’s estimator uses a slowly growing influence function to reduce the effect of heavy-tailed outliers and can achieve sub-Gaussian performance with an appropriate parameter.Its theorem gives the best possible constant 2, but the standard parameter choice depends on the variance.
- Trimmed mean: Trimmed means provide a conceptually simple alternative that is sub-Gaussian under finite variance and robust to adversarial contamination.The estimator removes fractions of the largest and smallest observations before averaging.
- Multiple-δ estimators: No single estimator can be simultaneously L-sub-Gaussian at two specified confidence levels for all finite-second-moment distributions.The impossibility holds for every L ≥ 50 and every sample size n.
3 Estimating the mean of a random vector
The multivariate mean-estimation problem concerns estimating a mean vector under heavy tails, where the sample mean can have sub-optimal performance. The survey presents median-of-means, Catoni-Giulini, and tournament-based estimators, emphasizing sub-Gaussian accuracy, confidence, computational feasibility, and scope limitations.
- Problem: Estimating a random vector’s mean requires handling heavy tails, for which the sample mean may perform sub-optimally.The setup assumes i.i.d. samples with existing mean vector and covariance matrix.
- Sub-Gaussian performance: Multivariate sub-Gaussian performance controls error using λmax(Σ) rather than Tr(Σ), avoiding explicit dimension dependence.The trace-based empirical-mean bound can be substantially worse in high dimensions, especially at small failure probabilities.
- Median-of-means estimators: The geometric median-of-means estimator is efficiently approximable through convex optimization and achieves a performance bound comparable to Proposition 1.It provides a computationally practical multivariate median-of-means construction.
- Catoni-Giulini estimator: The Catoni-Giulini estimator shrinks observations with large norm toward zero, but its lack of translation invariance can introduce dependence on ∥μ∥2.A two-stage centering modification removes this dependence, yet the resulting bound remains non-sub-Gaussian in the stated sense.
- Catoni-Giulini estimator: A small additional moment assumption, E∥X∥β < ∞ for some β > 2, makes Catoni-Giulini performance close to sub-Gaussian.The estimator is computationally simple, whereas tournament estimators offer stronger guarantees but may be computationally intractable; semidefinite relaxation provides a route toward efficient computation.
- Median-of-means tournaments: Median-of-means tournaments compare empirical risks between candidate vectors to identify points that defeat all sufficiently distant alternatives.The method exploits that the true mean minimizes f(x) = E∥X − x∥2 and yields a sub-Gaussian estimator for distributions with finite covariance.
4 Uniform median-of-means estimators
Uniform median-of-means estimators extend individual mean guarantees to entire function classes and arbitrary norms. Their error combines an individual estimation term with a complexity-dependent uniform-control term, supporting multivariate mean estimation and L2 distance oracles.
- Problem: The uniform estimation problem seeks high-probability simultaneous control of |bφn(f) − Ef(X)| for every f in a function class.The estimator must control all class members on one event, rather than estimate a single fixed function.
- Estimator structure: Uniform median-of-means error contains a worst individual estimate and a global term reflecting the complexity of the function class.The global term accounts for uniform control beyond the accuracy required for one fixed function.
- Proof strategy: The proof splits n = mk observations into k blocks, controls a finite net by a union bound, and bounds oscillations so at most 0.4k blocks are corrupted.The median tolerates corrupted blocks, while the complexity term controls deviations between net points and the full class.
- Multivariate mean estimation: The framework yields a mean estimator for any norm on R^d, with a bound combining one-dimensional variance control and global parameters involving E∥G∥ and E∥ζn∥.For the Euclidean norm, the theorem recovers the corresponding two-term error bound, and the authors state that the general bound is plausibly optimal.
- L2 distance oracles: The same framework constructs an isomorphic L2 distance oracle that estimates ∥f − h∥L2 up to multiplicative constants.The oracle can certify that a function is far from zero or bound its norm within constants under the theorem’s conditions.
5 Median-of-means tournaments in regression problems
Regression function estimation is framed as conditional-mean estimation under potentially unreliable empirical risks. Median-of-means tournaments compare predictors across blocks and use a distance oracle to obtain strong accuracy-confidence guarantees in convex classes, including heavy-tailed settings.
- Problem setup: Regression estimation seeks a function in F predicting Y from X, measured by mean-squared error, with excess risk controlled with probability at least 1 − δ.The standard formulation assumes a closed, convex class with an attained unique risk minimizer.
- Limits of empirical risk minimization: Empirical risk minimization becomes unreliable when candidate functions or the target have heavy tails, whereas sub-Gaussian-tail assumptions support its standard guarantees.The paper motivates robust alternatives because performance depends strongly on tail behavior.
- Supported guarantees: The tournament framework attains the optimal accuracy-confidence tradeoff for prediction in convex classes, including when some functions or outcomes may be heavy tailed.The cited work introduces median-of-means tournaments for convex classes and extends related ideas to regularization.
- Tournament procedure: Median-of-means tournaments split the sample into blocks and compare each pair of functions by which has the smaller blockwise empirical squared loss on a majority of blocks.The procedure uses robust blockwise comparisons rather than relying on one aggregate empirical risk.
- Distance oracle: A distance oracle identifies when two functions are too close for a reliable match, allowing the tournament to disregard ambiguous comparisons.This additional component addresses the instability of matches between nearby candidates.
- Analysis: Qualifiers remain close to the risk minimizer, and functions winning all home matches have small excess risk.The analysis links tournament qualification and match outcomes to proximity to f* and low risk.