Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913267070271488 |
|---|---|
| author | Li, Shuyao Cheng, Yu Diakonikolas, Ilias Diakonikolas, Jelena Ge, Rong Wright, Stephen J. |
| author_facet | Li, Shuyao Cheng, Yu Diakonikolas, Ilias Diakonikolas, Jelena Ge, Rong Wright, Stephen J. |
| contents | 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}/ε)$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_10547 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing Li, Shuyao Cheng, Yu Diakonikolas, Ilias Diakonikolas, Jelena Ge, Rong Wright, Stephen J. Optimization and Control Artificial Intelligence Data Structures and Algorithms Machine Learning 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}/ε)$ 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. |
| title | Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing |
| topic | Optimization and Control Artificial Intelligence Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2403.10547 |