Research map / Learning theory and algorithms / Sample complexity
All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance
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.
Shows that the Lee and Valiant 1-d mean estimator is simultaneously optimal in constants for sub-Gaussian i.i.d. error, robust to strong contamination, optimal under low (1<z<2) moments, neighborhood optimal, and asymptotically efficient.
Problem
Whether a 1-d mean estimator can be robust to adversarial corruption and heavy tails (low moments) while keeping the optimal-constant sub-Gaussian error of Lee and Valiant's estimator in the i.i.d. finite-variance setting.
Approach
Proves that the existing Lee and Valiant estimator, without modification, achieves O(sigma sqrt(eta)) robustness under strong contamination, optimal low-moment error via a zth-moment generalization of its Chernoff analysis, neighborhood optimality via a reduction from robust sub-Gaussian estimators, and asymptotic efficiency.
Key results
- Lee and Valiant's estimator has error O(sigma sqrt(eta)) under eta-fraction strong contamination when eta <= 1/(24 n log(1/delta)), with sub-Gaussian constant sqrt(2) preserved.
- For distributions with finite z-th moment, z in (1,2), error is (M_z)^{1/z}(1+o(1))(c_z log(1/delta)/n)^{1-1/z} with c_z = 2(5.6)^{1/(z-1)} - 1, improving median-of-means constant 8sqrt(3)(12)^{1/(z-1)} - 1.
- Under finite variance, sqrt(n)(mu_hat - mu) converges to N(0, sigma^2), whereas median-of-means has asymptotic variance (pi/2) sigma^2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Lee–Valiant estimator under strong contamination | Lee–Valiant estimator · Finite-variance distributions, strong contamination | estimation error: σ · ((√2 + o(1))√(log 1/δ / n) + 222√η) | Helped |
| Use the alternative failure-probability parameterization for corruption | Lee–Valiant estimator · Finite-variance distributions, strong contamination | estimation error: σ · ((√2 + o(1))√(log 1/δ′ / n) + (135 + o(1))√η) | Helped |
| Apply the Lee–Valiant estimator when only a finite zth moment is assumed | Lee–Valiant estimator · Finite zth-moment distributions (z ∈ (1, 2)) | estimation error: (Mz)^(1/z) · (1 + o(1)) (cz log 1/δ / n)^(1−1/z) | Helped |
| Use a robust and sub-Gaussian estimator | Lee–Valiant estimator · Finite-mean distributions | distribution-dependent estimation error: O(ϵn,δ(D)) | Helped |
| Use the Lee–Valiant estimator instead of median-of-means | Mean estimation under finite variance and i.i.d. sampling · Finite-variance i.i.d. distributions, n → ∞ | asymptotic variance: (π/2)σ² versus σ² | Helped |
Limitations
- Robustness constants (222 and 135) are likely loose and not optimized
- Robustness requires an upper bound on corruption level eta <= O(log(1/delta)/n)
- Analysis of the estimator under robustness is much more intricate than for median-of-means
Experimental setup
Metrics: estimation error sub-Gaussian error constant asymptotic variance
Baselines: median-of-means trimmed mean Catoni estimator Devroye et al. 2016 multiple-delta estimators
Builds on: Lee and Valiant 2022 mean estimator median-of-means Dang et al. 2023 neighborhood optimality
Closest papers by meaning
- Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+\alpha$ Moments (NeurIPS 2023 · similarity 0.91)
- Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.86)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.86)
- On the Optimality of the Median-of-Means Estimator under Adversarial Contamination (NeurIPS 2025 · similarity 0.85)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.84)
- Robust Statistical Estimators with Bounded Empirical Sensitivity (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.