Statistical Limits of Affine Equivariant Estimation

We investigate the quantitative performance of affine-equivariant estimators for robust mean estimation. As a natural stability requirement, the construction of such affine-equivariant estimators has been extensively studied in the statistics literature. We quantitatively evaluate these estimators under two outlier models which have been the subject of much recent work: the heavy-tailed and adversarial corruption settings. We establish lower bounds which show that affine-equivariance induces a \emph{strict} degradation in recovery error with quantitative rates degrading by a factor of $\sqrt{d}$ in both settings. We find that classical estimators such as the Tukey median {(Tukey '75)} and Stahel-Donoho estimator {(Stahel '81 and Donoho '82)} are either quantitatively sub-optimal \emph{even within} the class of affine-equivariant estimators or lack any quantitative guarantees. On the other hand, recent estimators with strong quantitative guarantees are not affine-equivariant or require additional distributional assumptions to achieve it. We remedy this by constructing a new affine-equivariant estimator which nearly matches our lower bound. Our estimator is based on a novel notion of a high-dimensional median which may be of independent interest. Notably, our results are applicable more broadly to \emph{any} estimator whose performance is evaluated in the \emph{Mahalanobis} norm which, for affine-equivariant estimators, corresponds to an evaluation in \emph{Euclidean} norm on isotropic distributions.