Research map / Learning theory and algorithms / Sample complexity

Robust Statistical Estimators with Bounded Empirical Sensitivity

NeurIPS 2026 · 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.

Introduces empirical sensitivity, the average-case change in an estimator's output under bounded Hamming-distance contamination of a clean sample, and proves matching-up-to-logs lower and upper bounds for Gaussian mean estimation.

Problem

How sensitive can accurate statistical estimators be when a fraction eta of the clean i.i.d. sample is replaced, measured as the shift of the estimate from its clean-data value (not from the true parameter)?

Approach

Defines empirical sensitivity as a distributional, average-case, Hamming-ball sensitivity of the output. Shows any MSE-optimal Gaussian mean estimator must have empirical sensitivity Omega(eta + sqrt(eta d/n)) via mean obstructions (scalar reduction, indistinguishability/coupling) and variance obstructions (Efron-Stein with block resampling), and that a robust empirical-mean estimator of Chen et a

Key results

• Any estimator with O(d/n) MSE has sup_mu ES_{eta,2} >= Omega(eta + sqrt(eta d/n)) for sufficiently large n.
• A robust empirical-mean estimator (Chen et al.) achieves sensitivity O~(eta + sqrt(eta (d+log(1/beta))/n)) with probability 1-beta while retaining O((d+log(1/beta))/n) MSE.
• Under the resampling adversary the empirical mean has sensitivity of order sqrt(eta d/n), with no linear-in-eta term.

Surprising findings

• The eta term appears even though the triangle inequality only suggests a lower bound of order eta in some regimes; it requires separate technical work.
• The median has empirical sensitivity O(eta + log(1/beta)/n), quadratically better than the worst-case robustness guarantee suggests.

Limitations

• The upper bound estimator is computationally inefficient; efficient estimators achieve only a weaker rate sqrt(eta sqrt(d/n)).
• Lower bounds for the high-corruption regime require eta < 1/10 and eta n at least C log n; the proofs are sketched for large n only.
• Results are established for Gaussian mean estimation with known identity covariance.

Experimental setup

Metrics: empirical sensitivity mean squared error

Baselines: median empirical mean

Builds on: Efron-Stein inequality Hammersley-Chapman-Robbins inequality local sensitivity strong contamination model

Closest papers by meaning

• Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation (ICML 2024 · similarity 0.85)
• Optimal kernel regression bounds under energy-bounded noise (NeurIPS 2025 · similarity 0.85)
• Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.84)
• The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli (ICML 2025 · similarity 0.84)
• Variance estimation in compound decision theory under boundedness (NeurIPS 2024 · similarity 0.84)
• Generalization and Robustness of the Tilted Empirical Risk (ICML 2025 · similarity 0.83)