تقرير
Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing
| العنوان: | 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. |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control, Computer Science - Artificial Intelligence, Computer Science - Data Structures and Algorithms, Computer Science - 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}/{\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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.10547 |
| رقم الأكسشن: | edsarx.2403.10547 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |