All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance

All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance

Speakers: Jasper Lee, PhD Student, UC Davis; Walter McKelvie; Maoyuan Song; Paul Valiant, Professor

Conference: ICML 2025

YouTube: https://slideslive.com/39044081

Overview

This talk, presented by Jasper Lee from UC Davis, delves into the foundational problem of mean estimation over the real numbers, a seemingly simple task that is, in fact, remarkably complex in practice. Co-authored with Walt McKelvie, Raymond Song, and Paul Valiant, the presentation challenges conventional wisdom surrounding the ubiquitous sample mean and highlights the shortcomings of traditional robust estimators like median-of-means. The core message is that while many believe mean estimation is a solved problem, achieving robust, statistically optimal guarantees in finite-sample settings, especially in the presence of outliers or heavy-tailed data, remains a significant challenge.

The talk introduces and elaborates on a novel estimator, referred to as the LV21 estimator (from previous work by Lee and Valiant in 2021), which initially provided optimal sub-Gaussian error with sharp constants for data with finite variance. The central contribution of this paper is to demonstrate that this same LV21 estimator, without modification, inherently possesses a suite of additional desirable properties. These include robustness to adversarial data corruption, optimal performance for heavy-tailed distributions where only lower moments are finite, instance-by-instance optimality, and asymptotic efficiency.

This work is crucial for anyone dealing with real-world data in machine learning, statistics, or computational sciences, where distributions are often unknown, noisy, or prone to extreme values. By presenting an "all-purpose Swiss Army knife" estimator, the researchers offer a solution that simplifies the choice of estimator, eliminates the need for prior knowledge about the data's statistical properties, and provides strong, theoretically-backed performance guarantees across a wide spectrum of challenging scenarios.

Background

▶ Watch: Introduction: Mean estimation, a non-trivial fundamental problem (0:00)

The problem of mean estimation is a cornerstone of statistics and a fundamental component of countless randomized algorithms and scientific applications. Given n samples from an unknown distribution D over the real numbers, the goal is to estimate the true mean μ accurately with high probability, typically 1-δ.

The most common and intuitively appealing estimator is the sample mean, which simply averages the observed samples. Its widespread use is often justified by the Central Limit Theorem (CLT), which states that as the number of samples grows, the distribution of the sample mean converges to a Gaussian distribution around the true mean. Furthermore, the Gaussian error rate is considered optimal in the asymptotic limit. However, Lee emphasizes a critical caveat: the CLT is an infinite-sample guarantee. It doesn't specify how quickly this Gaussian behavior is approached for any given distribution. For some distributions, it might take very few samples, while for others, it could require millions or even billions of samples, rendering the CLT insufficient for practical finite-sample guarantees.

A major practical failing of the sample mean is its extreme sensitivity to outliers or "extreme values." A single corrupted or unusually large (or small) sample can drastically skew the estimate, leading to provably poor finite-sample guarantees. In practice, this often leads to ad-hoc outlier removal methods, which are unprincipled and can further degrade estimation accuracy.

To address the brittleness of the sample mean, various robust mean estimators have been developed. A classic example is the median-of-means estimator. This estimator was specifically designed to be robust against extreme data points and offers finite-sample error guarantees that are big-O optimal, meaning optimal up to constant factors. While theoretically appealing, empirical evidence presented in the talk demonstrates that median-of-means can still perform poorly compared to the sample mean on simple Gaussian data, exhibiting an error bump that is approximately 25% wider, indicating larger estimation errors. This loss of a constant factor in the error guarantee significantly impacts its practical utility.

A more recent development, the LV21 estimator proposed by Lee and Valiant, aimed to overcome these limitations. This estimator, informally described as involving an initial centering estimate (e.g., using median-of-means), followed by a "fractional trimming" of samples based on a carefully computed quadratic function, achieved finite-sample sub-Gaussian error with sharp, optimal constants. For instance, on Gaussian data, the LV21 estimator recovers the optimal Gaussian behavior that the sample mean enjoys, but without its fragility. Crucially, for heavier-tailed distributions (like the Student's t-distribution), the LV21 estimator demonstrably outperforms both the sample mean and median-of-means, yielding the narrowest error distribution and thus the smallest error.

Formally, for distributions with finite but unknown mean μ and variance σ², the LV21 estimator guarantees an estimation error that scales as σ ⋅ sqrt(2 log(1/δ) / n) (1 + o(1)). Here, sqrt(2) is a provably sharp constant, and the (1 + o(1)) factor represents a distribution-independent convergence behavior, ensuring that the nice sub-Gaussian guarantees are achieved quickly across all distributions, unlike the sample mean. This contrasts with median-of-means, which achieves a similar rate but with a suboptimal constant (greater than sqrt(2)), and Catoni's estimator, which achieves the optimal rate but critically assumes a priori knowledge of the distribution's variance, a much harder problem to solve than mean estimation itself.

The motivation for the current paper stems from a desire to consolidate the best properties of mean estimators. While the LV21 estimator excels in the standard IID finite-variance setting, other estimators (like median-of-means) are known for their robustness to adversarial corruption, effectiveness with infinite-variance heavy-tailed distributions, instance-by-instance optimality, and asymptotic efficiency. The central question addressed by this research is: Can an estimator possess all these desirable properties—including the sharp constant guarantees of LV21—without sacrificing performance in any specific scenario? The answer, as the talk reveals, is a resounding yes, and surprisingly, the LV21 estimator already does the trick.

Key Findings

▶ Watch: Median-of-Means: Robust but suboptimal constants and empirical performance (2:50)

The central and most significant finding of this work is the comprehensive expansion of the proven capabilities of the previously introduced LV21 estimator. While the LV21 estimator was initially recognized for achieving optimal sub-Gaussian error with sharp constants in the standard independent and identically distributed (IID) finite-variance setting, this paper rigorously demonstrates that it inherently possesses a much broader set of desirable properties, positioning it as an "all-purpose Swiss Army knife" for mean estimation.

Specifically, the key findings are:

1. Robustness to Adversarial Data Corruption: The LV21 estimator is provably robust against adversarial corruption, where an η fraction of the n samples may be arbitrarily corrupted. The estimator achieves an error bound that is the sum of its original optimal sub-Gaussian error and a term proportional to η, which is known to be the optimal corruption rate in robust statistics literature. Crucially, the algorithm adapts to the corruption rate η without requiring explicit knowledge of it, making it highly practical. This holds as long as η is not "too large."

1. Optimal Performance for Heavy-Tailed Distributions: For distributions with potentially infinite variance but finite z-th moments (where 1 < z < 2), the LV21 estimator achieves an estimation error that is optimal up to constants. The error expression directly incorporates the z-th moment (M_z) and scales as M_z^(1/z) (log(1/δ) / n)^(1-1/z). This generalizes the 1/sqrt(n) rate for z*=2 (finite variance) and provides appropriate, theoretically optimal rates for heavier tails. Similar to the corruption case, the estimator does not need to know the specific value of z, demonstrating its remarkable adaptivity.

1. Instance-by-Instance Optimality: The LV21 estimator is shown to be optimal in a stronger sense, adapting to the specific characteristics of a given distribution to achieve instance-by-instance optimal error behavior, at least up to constants. This ensures that its performance is not merely a worst-case guarantee but adapts to the data at hand.

1. Asymptotic Normality and Efficiency: Unlike some robust estimators (e.g., median-of-means, which is known to be asymptotically inefficient), the LV21 estimator also possesses optimal infinite-sample guarantees, exhibiting asymptotic normality and efficiency. This means it performs optimally in both finite-sample and asymptotic regimes.

In essence, the paper argues that the LV21 estimator unifies the strengths of various mean estimation approaches, offering a single, robust, and theoretically optimal solution that works across a wide range of challenging statistical scenarios without requiring prior knowledge about the underlying data distribution or corruption levels.

Technical Deep Dive

▶ Watch: Speaker's prior estimator: Fractional trimming, optimal sub-Gaussian error (3:20)

The LV21 estimator is a sophisticated approach to mean estimation that builds upon, and significantly improves over, prior methods like the sample mean and median-of-means estimator. While the talk provides an informal description, the underlying mechanism involves a multi-stage process designed to achieve finite-sample sub-Gaussian error with sharp constants while being robust to outliers.

Informally, the estimator operates as follows:

1. Initial Centering: It first computes an initial, rough estimate of the mean to center the data. The speaker suggests that an estimator like median-of-means could be used for this step, though the specific method is likely more nuanced in the actual implementation. This centering step is crucial for making the subsequent trimming process effective.
2. Fractional Trimming via Quadratic Function: Instead of hard thresholding or removing outliers entirely, the LV21 estimator employs a "careful computation" involving a quadratic function to fractionally trim the samples. This means that instead of discarding extreme samples, their influence on the final mean is reduced proportionally to their extremity. This fractional approach is key to maintaining statistical efficiency while gaining robustness. The final estimate is then the sample mean of these fractionally weighted (or "untrimmed parts") samples. This stands in contrast to methods that simply remove observations outside a certain range, which can introduce bias or discard valuable information.

The core theoretical strength of the LV21 estimator, established in the prior work, lies in its sub-Gaussian error guarantee. Assuming the distribution has a finite but unknown mean and variance (σ²), for n samples and a desired failure probability δ, the estimation error is bounded by:

Error ≤ σ sqrt(2 log(1/δ) / n) * (1 + o(1))

Here, σ is the standard deviation, n is the number of samples, and δ is the failure probability. The sqrt(2) term is a provably sharp constant, meaning no estimator can achieve a smaller constant in this specific sub-Gaussian error bound. The (1 + o(1)) factor is a distribution-independent term that decays as n increases, ensuring rapid convergence to the optimal Gaussian-like behavior regardless of the underlying distribution's specific shape. This is a significant improvement over the sample mean, whose convergence to Gaussian behavior can be arbitrarily slow for certain distributions. It also surpasses median-of-means, which achieves a similar rate but with a suboptimal constant (greater than sqrt(2)).

The current paper extends these guarantees by demonstrating the estimator's intrinsic robustness and adaptability across more challenging scenarios:

1. Robustness to Adversarial Data Corruption:

In this setting, up to an η fraction of the n samples can be arbitrarily corrupted by an adversary. The LV21 estimator's error bound is then given by:

Error ≤ σ sqrt(2 log(1/δ) / n) (1 + o(1)) + C η * σ

where C is a universal constant. The first term is the original optimal sub-Gaussian error, and the second term, C η σ, represents the additional error introduced by corruption, which is known to be optimal in the robust statistics literature. A critical feature highlighted is that the algorithm does not need to know the corruption rate η. It adaptively achieves this bound, making it highly practical. The speaker noted that this robustness holds as long as η is not "too large," and that the precise interaction with n and δ is subtle, often implying that δ must be set sufficiently small if η is large.

2. Performance with Heavy-Tailed Distributions (Infinite Variance):

For distributions where the variance might be infinite, but a **finite z-th moment** (M_z) exists for some z between 1 and 2 (i.e., 1 < z ≤ 2), the LV21 estimator also achieves optimal error rates. The z-th moment M_z serves as an analog to the variance for these heavier-tailed distributions. The error expression, optimal up to constants, is:

Error ≤ C' M_z^(1/z) (log(1/δ) / n)^(1-1/z)

where C' is a universal constant.

To interpret this, consider:

• If z = 2 (finite variance case), 1 - 1/z = 1 - 1/2 = 1/2. The expression becomes C' M_2^(1/2) (log(1/δ) / n)^(1/2), which is C' σ sqrt(log(1/δ) / n). This recovers the 1/sqrt(n) dependence characteristic of the sub-Gaussian rate, with M_2^(1/2) being the standard deviation σ.
• If z is closer to 1 (e.g., z = 1.5), 1 - 1/z = 1 - 1/1.5 = 1 - 2/3 = 1/3. The error would then scale as (log(1/δ) / n)^(1/3), which is 1 / n^(1/3). This indicates a slower rate of convergence than 1/sqrt(n) but is the optimal rate for distributions with only a finite 1.5-th moment.

Again, a key practical advantage is that the algorithm does not need to know the specific value of z. It adapts to the underlying moment structure of the distribution. In contrast, median-of-means achieves this rate but with significantly larger constants for all values of z.

The speaker also highlights that the analysis for these extended properties is "somewhat complicated," suggesting deep theoretical proofs are involved. The algorithm's runtime is stated to be linear time, which is crucial for scalability, although it's described as a "slightly complicated algorithm." This efficiency, combined with its robust theoretical guarantees, positions the LV21 estimator as a powerful and practical tool.

Experimental Setup & Results

▶ Watch: Formal guarantees of prior work, comparison to Catoni's estimator (4:40)

The talk primarily focuses on the theoretical advancements and expanded properties of the LV21 estimator. While the new findings about robustness to corruption and performance on heavy-tailed distributions are presented as theoretical proofs, the speaker does refer to prior empirical results that established the initial superiority of the LV21 estimator.

The empirical comparisons mentioned are:

1. Gaussian Data:

• Setup (implied): A small experiment was run comparing the sample mean and median-of-means estimator against the LV21 estimator on simple Gaussian data. The x-axis of the presented plot represented the signed estimation error, and the y-axis could be interpreted as probability density.
• Results: The LV21 estimator was shown to recover the optimal Gaussian-like behavior, matching the error characteristics that the sample mean ideally enjoys. In contrast, the median-of-means estimator exhibited a "wider bump" in its error distribution, indicating a larger error, specifically "something like 25% bigger" than the optimal. This demonstrated that while median-of-means is theoretically robust, its practical performance can be suboptimal due to larger constant factors in its error bounds.

1. Heavier-Tailed Distributions (Student's t-distribution):

• Setup (implied): Similar to the Gaussian experiment, the estimators were compared on data sampled from a Student's t-distribution, a common example of a heavy-tailed distribution.
• Results: For the Student's t-distribution, the LV21 estimator clearly outperformed all other estimators, displaying the "narrowest bump" and thus the smallest estimation error. This highlights its effectiveness in scenarios where extreme values are more common, further validating its robustness beyond simple Gaussian assumptions.

It is important to note that the presentation did not detail specific experimental setups for the new theoretical results (e.g., how the estimator performs empirically under various corruption rates or on different heavy-tailed distributions with varying z-th moments). The empirical evidence cited serves to underscore the foundational strength of the LV21 estimator that the paper's new theoretical results build upon. The focus of this specific conference talk was on the theoretical proofs extending the estimator's "all-purpose" nature rather than new empirical benchmarks. Therefore, details regarding specific datasets, hardware, or comprehensive ablation studies for the newly proven properties were not provided.

Practical Implications

▶ Watch: New work motivation: Adversarial robustness, heavy-tailed distributions (5:50)

The findings presented in this talk have profound practical implications for a wide range of practitioners, infrastructure teams, model builders, and anyone involved in deploying machine learning systems or performing statistical analysis. The central message is the availability of an "all-purpose" mean estimator that simplifies choices and enhances reliability.

For Practitioners and Data Scientists:

• Reduced Decision Fatigue: The primary benefit is the elimination of the need to choose between different mean estimators based on assumptions about the data. Instead of debating whether to use a sample mean (for efficiency), median-of-means (for robustness), or a specialized estimator (for heavy tails), the LV21 estimator offers a single, robust solution. The speaker aptly calls it a "Swiss Army knife" – "Just give it data, run it, it just works."
• No Prior Knowledge Required: Crucially, the estimator does not require prior knowledge of the distribution's variance, the order of its finite moments (z), or the rate of adversarial corruption (η). This adaptability is invaluable in real-world scenarios where such information is rarely known a priori.
• Improved Reliability in Noisy Data: In environments prone to outliers, measurement errors, or malicious data injection, the inherent robustness of the LV21 estimator to adversarial data corruption means more trustworthy mean estimates without manual outlier removal, which is often unprincipled and error-prone.
• Effective for Heavy-Tailed Data: Many real-world phenomena (e.g., financial data, network traffic, social media engagement) exhibit heavy-tailed distributions where variance is large or even infinite. The LV21 estimator provides statistically optimal mean estimates in these challenging scenarios, where traditional methods like the sample mean would completely fail.

For Infrastructure Teams and Deployers:

• Linear Time Complexity: The mention of linear time complexity is a significant advantage for large-scale data processing and real-time applications. While the algorithm is "slightly complicated," its linear scaling ensures that it remains feasible even with massive datasets, making it suitable for integration into high-throughput data pipelines.
• Simplified System Design: By providing a universally applicable mean estimator, infrastructure teams can standardize their statistical components, reducing the complexity of system design and maintenance. There's no need for conditional logic to switch estimators based on data characteristics.

For Model Builders and Algorithm Developers:

• Better Foundation for Downstream Tasks: Accurate and robust mean estimation is a fundamental building block for many machine learning algorithms (e.g., normalization, feature scaling, gradient estimation, clustering centroids). Using the LV21 estimator can lead to more stable and performant downstream models, especially when training data is noisy or comes from diverse, unknown distributions.
• Stronger Theoretical Guarantees: The sub-Gaussian error with sharp constants, coupled with robustness and heavy-tailed performance, provides strong theoretical backing for the reliability of estimates, which is critical for safety-critical applications or systems requiring auditable performance.

Tradeoffs and Limitations:

• Algorithm Complexity: While the runtime is linear, the "slightly complicated algorithm" might imply a higher constant factor overhead compared to the trivially simple sample mean. However, given the significant accuracy and robustness benefits, this is typically a worthwhile tradeoff.
• Limits to Robustness: The robustness to corruption is not infinite; the corruption rate η must not be "too large." The precise upper bound on η is subtle and depends on other parameters like the failure probability δ.
• Higher Dimensions: Acknowledged as an open problem, extending this work to arbitrary higher dimensions (multi-variate mean estimation) is still a challenge, though the speaker mentioned that the "constant dimensional case" is "coming soon." This means its immediate applicability is primarily for one-dimensional data or scalar statistics.
• Uniform Convergence: The speaker noted that applying these concentration results to problems like uniform convergence over function spaces (e.g., for empirical risk minimization) is a "much more challenging problem." The non-linearity of the LV21 estimator might complicate theoretical proofs in that context, even if it is conjectured to work well in practice. This suggests that while excellent for point estimates of means, its direct applicability to more complex statistical learning theory problems is still an area of research.

In summary, the LV21 estimator offers a compelling solution to a fundamental statistical problem, providing a robust, efficient, and theoretically optimal tool that simplifies the estimation process and enhances reliability across a broad spectrum of real-world data challenges.

Key Takeaways

• Mean estimation is surprisingly complex: Despite appearing trivial, achieving accurate, finite-sample, and robust mean estimates is challenging due to the limitations of the Central Limit Theorem and the sample mean's sensitivity to outliers.
• The LV21 estimator offers optimal sub-Gaussian performance: Developed by Lee and Valiant, this estimator achieves finite-sample sub-Gaussian error with sharp, optimal constants for IID finite-variance data, empirically outperforming traditional methods like median-of-means.
• LV21 is robust to adversarial corruption: The estimator adaptively handles up to an η fraction of corrupted samples, achieving near-optimal error bounds without requiring explicit knowledge of the corruption rate η.
• LV21 excels with heavy-tailed data: It provides optimal error rates (up to constants) even for distributions with infinite variance, requiring only a finite z-th moment (for 1 < z ≤ 2). Crucially, it adapts to the unknown z-th moment order.
• An "all-purpose Swiss Army knife" for mean estimation: The LV21 estimator combines robustness, optimal theoretical guarantees (including instance-by-instance optimality and asymptotic efficiency), and linear time complexity, making it a highly practical and versatile tool.
• Future work focuses on higher dimensions: While highly effective for one-dimensional data, extending the LV21 estimator to arbitrary higher dimensions for multi-variate mean estimation remains an active area of research.

About the Speaker(s)

The primary presenter of this talk was Jasper Lee, a PhD Student from UC Davis. He presented this work as a joint effort with his collaborators Walt McKelvie, who was also present at the conference, Maoyuan Song, and Paul Valiant. Paul Valiant is mentioned as a professor, implying a supervisory or senior research role in the project. The talk highlights their collective expertise in fundamental statistical problems and the development of robust and theoretically sound estimators.