# Outlier-Robust Sparse Estimation via Non-Convex Optimization

arXiv: https://arxiv.org/abs/2109.11515 · HTML: https://mlsanity.com/paper/2109.11515/

## Key facts

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

## Builds on (most cited first, 15 of 15)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions](https://mlsanity.com/paper/1802.02988/) (2018)
- [Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering](https://mlsanity.com/paper/1911.08085/) (2019)
- [Robust estimation via generalized quasi-gradients](https://mlsanity.com/paper/2005.14073/) (2020)
- [High-Dimensional Robust Mean Estimation via Gradient Descent](https://mlsanity.com/paper/2005.01378/) (2020)
- [High Dimensional Robust M-Estimation: Arbitrary Corruption and Heavy Tails](https://mlsanity.com/paper/1901.08237/) (2019)

## Built on by (most cited first, 14 of 14)

- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel](https://mlsanity.com/paper/2406.00924/) (2024)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (2022)
- [Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination](https://mlsanity.com/paper/2403.10416/) (2024)
- [Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction](https://mlsanity.com/paper/2204.02323/) (2022)
- [Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization](https://mlsanity.com/paper/2302.05865/) (2023)
- [Sparse Mean Estimation in Adversarial Settings via Incremental Learning](https://mlsanity.com/paper/2305.15276/) (2023)

## 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.