Skip to main content

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

Publication ,  Conference
Li, S; Diakonikolas, I; Ge, R; Cheng, Y; Diakonikolas, J; Wright, S
Published in: Advances in Neural Information Processing Systems
January 1, 2023

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 Oe(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.

Duke Scholars

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2023

Volume

36

Start / End Page

54386 / 54398

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Li, S., Diakonikolas, I., Ge, R., Cheng, Y., Diakonikolas, J., & Wright, S. (2023). Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing. In Advances in Neural Information Processing Systems (Vol. 36, pp. 54386–54398).
Li, S., I. Diakonikolas, R. Ge, Y. Cheng, J. Diakonikolas, and S. Wright. “Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing.” In Advances in Neural Information Processing Systems, 36:54386–98, 2023.
Li S, Diakonikolas I, Ge R, Cheng Y, Diakonikolas J, Wright S. Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing. In: Advances in Neural Information Processing Systems. 2023. p. 54386–98.
Li, S., et al. “Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing.” Advances in Neural Information Processing Systems, vol. 36, 2023, pp. 54386–98.
Li S, Diakonikolas I, Ge R, Cheng Y, Diakonikolas J, Wright S. Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing. Advances in Neural Information Processing Systems. 2023. p. 54386–54398.

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2023

Volume

36

Start / End Page

54386 / 54398

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology