mlsanityData to 14 Oct 2026

Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction

arXiv 2204.02323 ↗First posted 5 Apr 2022math.ST cs.LG stat.THcited by 1

Not on the map. Why?

Abstract (arXiv)

We study the problem of robust estimation of the mean vector of a sub-Gaussian distribution. We introduce an estimator based on spectral dimension reduction (SDR) and establish a finite sample upper bound on its error that is minimax-optimal up to a logarithmic factor. Furthermore, we prove that the breakdown point of the SDR estimator is equal to 1/2, the highest possible value of the breakdown point. In addition, the SDR estimator is equivariant by similarity transforms and has low computational complexity. More precisely, in the case of n vectors of dimension p -- at most varepsilon n out of which are adversarially corrupted -- the SDR estimator has a squared error of order big(fracr_Sigman + varepsilon2log(1/varepsilon)big)log p and a running time of order p3 + n p2. Here, r_Sigma≤ p is the effective rank of the covariance matrix of the reference distribution. Another advantage of the SDR estimator is that it does not require knowledge of the contamination rate and does not involve sample splitting. We also investigate extensions of the proposed algorithm and of the obtained results in the case of (partially) unknown covariance matrix.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 15 of its 38 references that are in the map. First posted on arXiv 5 Apr 2022.

Builds on

15 of 38 references.

References · 15

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  4. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
  5. 2015Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Modelcited by 47
  6. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  7. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  8. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  9. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  10. 2019Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimatorcited by 31
  11. 2018High Dimensional Robust Sparse Regressioncited by 29
  12. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
3 more
  1. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  2. 2019ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labelscited by 5
  3. 2019Confidence regions and minimax rates in outlier-robust estimation on the probability simplexcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussianscited by 3