Research map / Learning theory and algorithms / Sample complexity
Robust Estimation Under Heterogeneous Corruption Rates
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.
Defines a heterogeneous-corruption (lambda-contamination) model where each sample has its own known corruption probability, and gives minimax rates for bounded, univariate/multivariate Gaussian mean estimation and Gaussian linear regression via thresholding and weighted Tukey-depth estimators.
Problem
Robust estimation when each sample is corrupted with a known but different probability; existing robust estimators assume uniform or worst-case corruption rates.
Approach
Generalize Huber contamination to per-sample corruption rates lambda_i; show the minimax error is governed by an effective rate min_t (t^2 + k/N(t)), where N(t) counts samples with corruption at most t, so samples above a threshold can be discarded; upper bounds via thresholding or weighted Tukey median/regression depth, lower bounds via Le Cam and Assouad-style constructions.
Key results
- For bounded distributions in R^d, minimax rate is r^2 f(lambda,1) with f(lambda,k)=min_t(k/|{i:lambda_i<=t}|+t^2), achieved by a near-linear-time reweighting estimator.
- For univariate Gaussian mean estimation the minimax PAC rate matches min_t(1/N(t)+t^2) up to constants.
- For multivariate Gaussian mean estimation and linear regression the rate is established up to a sqrt(d) factor, with upper bound min_t(d/N(t)+t^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use heterogeneous-corruption thresholding or per-sample reweighting instead of the sample mean | Bounded mean estimation · Synthetic bounded distributions | mean squared error | Helped |
| use heterogeneous-corruption thresholding or per-sample reweighting instead of the sample median | Univariate Gaussian mean estimation · Synthetic univariate Gaussian distributions | squared error | Helped |
| use per-sample reweighting instead of thresholding | Heterogeneous robust mean estimators · Synthetic bounded distributions | mean squared error | Helped |
| use per-sample reweighting instead of thresholding | Heterogeneous robust mean estimators · Synthetic univariate Gaussian distributions | squared error | No clear effect |
Surprising findings
- Samples above a certain corruption threshold can be discarded by optimal estimators without loss up to constants.
- Coordinate-wise methods lose a Theta(d) factor in squared error versus the proposed approach in the Gaussian setting.
Limitations
- Multivariate Gaussian mean estimation and linear regression are tight only up to a sqrt(d) factor.
- Assumes corruption rates lambda_i are known exactly (or up to constant factor).
- Experiments are preliminary and only in synthetic settings.
Experimental setup
Datasets: synthetic data
Metrics: mean squared error quantile of squared error
Baselines: sample mean sample median
Builds on: Huber contamination model Tukey median semi-verified learning
Closest papers by meaning
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.87)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.85)
- Locally Private and Robust Multi-Armed Bandits (NeurIPS 2024 · similarity 0.85)
- Multigroup Robustness (ICML 2024 · similarity 0.85)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.85)
- Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal (ICML 2025 · 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.