# Robust estimation via generalized quasi-gradients

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2020.

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

- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Outlier-Robust Sparse Estimation via Non-Convex Optimization](https://mlsanity.com/paper/2109.11515/) (2021)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Towards Trustworthy Federated Learning with Untrusted Participants](https://mlsanity.com/paper/2505.01874/) (2025)
- [High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackers](https://mlsanity.com/paper/2307.13352/) (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)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise](https://mlsanity.com/paper/2209.02856/) (2022)
- [A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation](https://mlsanity.com/paper/2403.04726/) (2024)
- [Robust Moment-Based Estimation via Spectral Gradient Reweighting](https://mlsanity.com/paper/2605.27718/) (2026)
- [Robustifying Markowitz](https://mlsanity.com/paper/2212.13996/) (2022)
- [A Novel Framework for Improving the Breakdown Point of Robust Regression Algorithms](https://mlsanity.com/paper/2305.12220/) (2023)

## Abstract (arXiv)

We explore why many recently proposed robust estimation problems are efficiently solvable, even though the underlying optimization problems are non-convex. We study the loss landscape of these robust estimation problems, and identify the existence of "generalized quasi-gradients". Whenever these quasi-gradients exist, a large family of low-regret algorithms are guaranteed to approximate the global minimum; this includes the commonly-used filtering algorithm. For robust mean estimation of distributions under bounded covariance, we show that any first-order stationary point of the associated optimization problem is an approximate global minimum if and only if the corruption level ε < 1/3. Consequently, any optimization algorithm that aproaches a stationary point yields an efficient robust estimator with breakdown point 1/3. With careful initialization and step size, we improve this to 1/2, which is optimal. For other tasks, including linear regression and joint mean and covariance estimation, the loss landscape is more rugged: there are stationary points arbitrarily far from the global minimum. Nevertheless, we show that generalized quasi-gradients exist and construct efficient algorithms. These algorithms are simpler than previous ones in the literature, and for linear regression we improve the estimation error from O(√ε) to the optimal rate of O(ε) for small ε assuming certified hypercontractivity. For mean estimation with near-identity covariance, we show that a simple gradient descent algorithm achieves breakdown point 1/3 and iteration complexity tildeO(d/ε2).