mlsanityData to 7 Oct 2026

Statistical Barriers to Affine-equivariant Estimation

arXiv 2310.10758 ↗First posted 16 Oct 2023math.ST cs.DS cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 strict degradation in recovery error with quantitative rates degrading by a factor of √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 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 any estimator whose performance is evaluated in the Mahalanobis norm which, for affine-equivariant estimators, corresponds to an evaluation in Euclidean norm on isotropic distributions.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 20 of its 73 references that are in the map. First posted on arXiv 16 Oct 2023.

Builds on

20 of 73 references.

References · 20

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  3. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  4. 2021Robust and Differentially Private Mean Estimationcited by 66
  5. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  6. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  7. 2017Sub-Gaussian estimators of the mean of a random vectorcited by 47
  8. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  9. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  10. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  11. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  12. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
8 more
  1. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  2. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  3. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  4. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  5. 2019Fast Mean Estimation with Sub-Gaussian Ratescited by 18
  6. 2019A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Ratescited by 12
  7. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  8. 2020Multivariate mean estimation with direction-dependent accuracycited by 2

Built on by

Not cited yet.