Outlier Robust Mean Estimation with Subgaussian Rates via Stability

  • 2020-07-30 17:33:03
  • Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
  • 5

Abstract

We study the problem of outlier robust high-dimensional mean estimation undera finite covariance assumption, and more broadly under finite low-degree momentassumptions. We consider a standard stability condition from the recent robuststatistics literature and prove that, except with exponentially small failureprobability, there exists a large fraction of the inliers satisfying thiscondition. As a corollary, it follows that a number of recently developedalgorithms for robust mean estimation, including iterative filtering andnon-convex gradient descent, give optimal error estimators with(near-)subgaussian rates. Previous analyses of these algorithms gavesignificantly suboptimal rates. As a corollary of our approach, we obtain thefirst computationally efficient algorithm with subgaussian rate foroutlier-robust mean estimation in the strong contamination model under a finitecovariance assumption.

 

Quick Read (beta)

loading the full paper ...