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 \mu$ has bounded empirical sensitivity if, with high probability over a dataset $X = (X_1, \dots, X_n) \sim \mathcal{D}^{\otimes n}$, for any dataset $Y$ obtained by modifying at most $\eta n$ points in $X$, we have that $\hat \mu(Y)$ is close to $\hat \mu(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 \mu$ which achieves an optimal $\ell_2$-error bound of $O(\sqrt{d/n})$, the empirical sensitivity is at least $\Omega(\eta + \sqrt{\eta d/n})$. 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.