Research map / Learning theory and algorithms / Sample complexity
On the Optimality of the Median-of-Means Estimator under Adversarial Contamination
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 Median-of-Means estimator is minimax optimal under adversarial contamination for finite-variance, infinite-variance (finite (1+r)-th moment) and symmetric distributions, and sub-optimal for sub-exponential and light-tailed classes, via upper and lower bounds.
Problem
Determining whether the Median-of-Means estimator is minimax optimal for mean estimation under adversarial contamination beyond the Gaussian case, and characterizing its limitations (asymptotic bias) for different distribution classes.
Approach
Derives MoM error bounds via the quantile function of block averages (Theorem: error governed by quantiles of the i.i.d. average around its median), then tunes the number of blocks k per distribution class; matching lower bounds show optimality for heavy-tailed and symmetric classes and sub-optimality for light tails.
Key results
- MoM is minimax optimal under adversarial contamination for finite-variance distributions with asymptotic bias order sqrt(alpha), and for infinite-variance classes with bias alpha^{r/(1+r)}.
- For symmetric distributions with linearly increasing quantile near the median, MoM achieves the optimal asymptotic bias of order alpha.
- For sub-exponential distributions, MoM's asymptotic bias is lower bounded by alpha^{2/3} for any number of blocks, which is sub-optimal versus the alpha log(1/alpha) achievable by the trimmed mean.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MoM with k = max{ceil{log(2/delta)/(1/2-1/gamma)^2}, ceil{gamma alpha n}} | MoM on finite-variance distributions · Finite variance (P2), adversarial contamination | estimation error: \sqrt{\frac{\log(2/\delta)}{n}} + \sqrt{\alpha} | Helped |
| Use MoM with k = max{ceil{log(2/delta)/(1/2-1/gamma)^2}, ceil{gamma alpha n}} | MoM on distributions with finite absolute (1+r)-th moment · Infinite variance (P_{1+r}), adversarial contamination | estimation error: \left({\frac{\log(2/\delta)}{n}}\right)^{\frac{r}{1+r}} + {\alpha}^{\frac{r}{1+r}} | Helped |
| Choose k = ceil{xi alpha^{2/3} n} | MoM on sub-exponential distributions · Sub-exponential (P_SE), adversarial contamination | asymptotic bias: \alpha^{2/3} | Helped |
| Use any number of blocks k | MoM on sub-exponential distributions · Sub-exponential (P_SE), adversarial contamination | asymptotic bias: \alpha^{2/3} | Hurt |
| Use k = ceil{xi alpha^{2/(s+1)} n} on distributions matching Gaussian central moments through order s | MoM on P_SG^s · Sub-Gaussian moment-matched distributions, adversarial contamination | asymptotic bias: \alpha^{\frac{s}{s+1}} | Helped |
| Use k = ceil{beta n} on symmetric distributions with a locally linear quantile function | MoM on P_sym^{epsilon_0,c} · Symmetric distributions (P_sym^{epsilon_0,c}), adversarial contamination | estimation error: \sqrt{\frac{\log(2/\delta)}{n}} + \alpha | Helped |
| Choose the block count for finite-variance worst-case optimality rather than specifically for light-tailed distributions | MoM on well-behaved distributions such as Gaussian · Finite variance, adversarial contamination | asymptotic bias: \sqrt{\alpha} | Hurt |
| Use MoM rather than the optimal trimmed mean | Mean estimation on sub-Gaussian distributions · Sub-Gaussian (P_SG), adversarial contamination | asymptotic bias: \alpha^{2/3} vs. \alpha\sqrt{\log(1/\alpha)} | Hurt |
| Use MoM rather than the optimal trimmed mean | Mean estimation on sub-exponential distributions · Sub-exponential (P_SE), adversarial contamination | asymptotic bias: \alpha^{2/3} vs. \alpha\log(1/\alpha) | Hurt |
| Use MoM rather than the optimal Gaussian estimator | Mean estimation on Gaussian distributions · Gaussian (P_G), adversarial contamination | asymptotic bias: \alpha | No clear effect |
Surprising findings
- For a fixed block count chosen to be optimal over the finite-variance class, MoM does not improve on Gaussian distributions: error stays at order sqrt(alpha) even for finite-variance distributions like Gaussians.
- MoM's contamination tolerance for infinite-variance distributions does not decrease with r, unlike Catoni's M-estimator.
Limitations
- Constants in error bounds are not optimized and are much larger than best known i.i.d. constants.
- Optimal number of blocks depends on the distribution class, requiring prior knowledge.
- Sub-exponential and sub-Gaussian results hold only for restricted confidence ranges of delta.
Experimental setup
Metrics: estimation error bound order asymptotic bias order
Baselines: trimmed mean Catoni's M-estimator Lee-Valiant estimator
Builds on: Median-of-Means Catoni's M-estimator trimmed mean Minsker's MoM analysis
Closest papers by meaning
- All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance (ICML 2025 · similarity 0.85)
- Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness (NeurIPS 2024 · similarity 0.85)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.84)
- Consistent Adversarially Robust Linear Classification: Non-Parametric Setting (ICML 2024 · similarity 0.84)
- Adversarial Robustness of Nonparametric Regression (NeurIPS 2025 · similarity 0.84)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.84)
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.