High-Dimensional Robust Mean Estimation via Gradient Descent

Abstract

We study the problem of high-dimensional robust mean estimation in the presence of a constant fraction of adversarial outliers. A recent line of work has provided sophisticated polynomial-time algorithms for this problem with dimension-independent error guarantees for a range of natural distribution families. In this work, we show that a natural non-convex formulation of the problem can be solved directly by gradient descent. Our approach leverages a novel structural lemma, roughly showing that any approximate stationary point of our non-convex objective gives a near-optimal solution to the underlying robust estimation task. Our work establishes an intriguing connection between algorithmic high-dimensional robust statistics and non-convex optimization, which may have broader applications to other robust estimation tasks.

Under submission to ICML'20

References in corpus (11)

• Poisoning Attacks against Support Vector Machines
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Non-convex Optimization for Machine Learning
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
• The proximal point method revisited
• Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Cited by in corpus (10)

• Outlier Robust Mean Estimation with Subgaussian Rates via Stability
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
• Outlier-Robust Sparse Estimation via Non-Convex Optimization
• Learning Deep Neural Networks under Agnostic Corrupted Supervision
• Heavy-tailed Streaming Statistical Estimation
• Robust Estimation for Random Graphs
• Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
• Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time
• Robust Mean Estimation in High Dimensions via ${\ell }_0$ Minimization
• Adversarial robust weighted Huber regression