Robust Second-Order Nonconvex Optimization and Its Application to Low
  Rank Matrix Sensing
Shuyao Li Yu Cheng Ilias Diakonikolas Jelena Diakonikolas Rong Ge Stephen J. Wright
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 \emph{dimension-independent} accuracy guarantees, using
$\widetilde{O}({D^2}/{\epsilon})$ samples where $D$ is the ambient dimension
and $\epsilon$ 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.