mlsanityData to 7 Oct 2026

Outlier-Robust Sparse Estimation via Non-Convex Optimization

arXiv 2109.11515 ↗First posted 23 Sep 2021cs.LG cs.DS math.OCcited by 14

Not on the map. Why?

Abstract (arXiv)

We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks. The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 15 of its 36 references that are in the map. First posted on arXiv 23 Sep 2021.

Builds on

15 of 36 references.

References · 15

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2017Certified Defenses for Data Poisoning Attackscited by 288
  3. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  4. 2016Agnostic Estimation of Mean and Covariancecited by 131
  5. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  6. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  7. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  8. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  9. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  10. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  11. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  12. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
3 more
  1. 2020Robust estimation via generalized quasi-gradientscited by 19
  2. 2020High-Dimensional Robust Mean Estimation via Gradient Descentcited by 16
  3. 2019High Dimensional Robust M-Estimation: Arbitrary Corruption and Heavy Tailscited by 3

Built on by

Cited by year

Citing papers per year: 2022: 7; 2023: 5; 2024: 2.

14 papers.

Sort:

By area:

  1. 2023Large Language Modelscited by 774
  2. 2022Is Out-of-Distribution Detection Learnable?cited by 109
  3. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallelcited by 29
  4. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  5. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  6. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  7. 2022List-Decodable Sparse Mean Estimationcited by 11
  8. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  9. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  10. 2022Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Modelscited by 6
  11. 2024Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contaminationcited by 2
  12. 2022Nearly minimax robust estimator of the mean vector by iterative spectral dimension reductioncited by 1
2 more
  1. 2023Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimizationcited by 0
  2. 2023Sparse Mean Estimation in Adversarial Settings via Incremental Learningcited by 0