Robust Statistical Estimators with Bounded Empirical Sensitivity

Abstract

We introduce a new measure of robustness for statistical estimators, which we call \emph{empirical sensitivity}. An estimator $\hat{\hat{I}}¸$ 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 $\hat{I}\cdot n$ points in $X$, we have that $\hat{\hat{I}}¸(Y)$ is close to $\hat{\hat{I}}¸(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{\hat{I}}¼$ which achieves an optimal ${\ell }_2$-error bound of $O\left(\sqrt{d/n}\right)$, the empirical sensitivity is at least $\hat{I}\text{c◯}\left(\hat{I}\cdot +\sqrt{\hat{I}\cdot d/n}\right)$. 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.