mlsanityData to 7 Oct 2026

Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing

arXiv 2403.10547 ↗First posted 12 Mar 2024math.OC cs.AI cs.DScited by 2

Not on the map. Why?

Abstract (arXiv)

Finding an approximate second-order stationary point (SOSP) is a well-studied and fundamental problem in stochastic nonconvex optimization with many applications in machine learning. However, this problem is poorly understood in the presence of outliers, limiting the use of existing nonconvex algorithms in adversarial settings. In this paper, we study the problem of finding SOSPs in the strong contamination model, where a constant fraction of datapoints are arbitrarily corrupted. We introduce a general framework for efficiently finding an approximate SOSP with dimension-independent accuracy guarantees, using widetildeO(D2/ε) samples where D is the ambient dimension and ε is the fraction of corrupted datapoints. As a concrete application of our framework, we apply it to the problem of low rank matrix sensing, developing efficient and provably robust algorithms that can tolerate corruptions in both the sensing matrices and the measurements. In addition, we establish a Statistical Query lower bound providing evidence that the quadratic dependence on D in the sample complexity is necessary for computationally efficient algorithms.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 31 of its 48 references that are in the map. First posted on arXiv 12 Mar 2024.

Builds on

31 of 48 references.

References · 31

  1. 2017Certified Defenses for Data Poisoning Attackscited by 288
  2. 2017How to Escape Saddle Points Efficientlycited by 284
  3. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  4. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  5. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  6. 2016Agnostic Estimation of Mean and Covariancecited by 131
  7. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  8. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  9. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  10. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  11. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  12. 2016A Geometric Analysis of Phase Retrievalcited by 92
19 more
  1. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  2. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  3. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  4. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  5. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  6. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  7. 2015Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picturecited by 49
  8. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  9. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  10. 2018Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learningcited by 32
  11. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  12. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  13. 2017Robust Regression via Mutivariate Regression Depthcited by 20
  14. 2016On the low-rank approach for semidefinite programs arising in synchronization and community detectioncited by 17
  15. 2017Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descentcited by 10
  16. 2018Non-Convex Matrix Completion Against a Semi-Random Adversarycited by 9
  17. 2018A Subsampling Line-Search Method with Second-Order Resultscited by 8
  18. 2023Robust empirical risk minimization via Newton's methodcited by 1
  19. 2023A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guaranteescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 1.

2 papers.

  1. 2026Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexitycited by 1
  2. 2024Optimal Rates for Robust Stochastic Convex Optimizationcited by 0