Robust Statistical Estimators with Bounded Empirical Sensitivity

We introduce a new measure of robustness for statistical estimators, which we call empirical sensitivity. An estimator hat θ has bounded empirical sensitivity if, with high probability over a dataset X = (X1, dots, Xn) ~ Dotimes n, for any dataset Y obtained by modifying at most η n points in X, we have that hat θ(Y) is close to hat θ(X). We study bounds on this quantity for the prototypical problem of Gaussian mean estimation. We prove new lower bounds, showing that for any estimator hat μ which achieves an optimal ℓ2-error bound of Oleft(√d/nright), the empirical sensitivity is at least Omegaleft(η + √η d/nright). The two terms arise due to obstructions on the mean and variance (via an Efron-Stein argument) of such an estimator. We show that this bound is tight up to logarithmic factors, by employing recent results for robust empirical mean estimation.