Research map / Learning theory and algorithms / Sample complexity

Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means

ICML 2025 · Learning theory and algorithms › Sample complexity · approach: Distributed estimation under communication limits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes the median-of-means estimator for uniform mean estimation over function classes under heavy tails (p-th moments, p in (1,2]), proving a sample complexity bound via a novel two-ghost-sample symmetrization and a relaxed distribution-dependent discretization, with applications to k-means and linear regression.

Problem

Uniform (simultaneous) mean estimation over a function class under heavy-tailed distributions that only have finite p-th moments for p in (1,2], where the sample mean performs poorly.

Approach

A novel symmetrization using two ghost samples (one to symmetrize the mean, one to symmetrize the MoM) combined with a relaxed discretization that only needs most of the batch means to be approximated, yielding MoM sample complexity bounds for unbounded classes.

Key results

• Main theorem: MoM achieves uniform estimation over a D-discretizable class with sample complexity of order (v_p/eps^p)^{1/(p-1)}(log N_D + log(1/delta)) under only p-th moments, p in (1,2].
• For k-means with normalized losses, the bound has a dk log k log(1/eps) + log(1/delta) form, exponentially better in the 1/delta confidence term than the kurtosis-based sample mean bound.
• For linear regression with Lipschitz losses, the sample complexity is of order (1/eps^{p/(p-1)})(d log(WL/eps) + log(1/delta)), matching sub-exponential rates up to log factors.

Limitations

• Constants in the bound are large (e.g., 400*16^p, 10^6 ln2/99) and not optimized.
• Bound has an extra log factor in epsilon for k-means compared with prior work.
• Requires finding a D-discretization of the function class, which is nontrivial for unbounded classes.

Experimental setup

Metrics: sample complexity

Baselines: sample mean trimmed mean sample mean uniform bound for k-means (kurtosis-based)

Builds on: median-of-means symmetrization argument Catoni estimator

Closest papers by meaning

• Generalization Bounds in the Presence of Outliers: a Median-of-Means Study (ICML 2021 · similarity 0.88)
• Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions (NeurIPS 2022 · similarity 0.85)
• Robust Mean Estimation Without Moments for Symmetric Distributions (NeurIPS 2023 · similarity 0.84)
• On the Optimality of the Median-of-Means Estimator under Adversarial Contamination (NeurIPS 2025 · similarity 0.84)
• Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.83)
• Simple and Optimal Sublinear Algorithms for Mean Estimation (NeurIPS 2025 · similarity 0.82)