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
复制标题
DOI：
10.48550/arxiv.2403.10547
复制
发表时间：
2024-03
期刊：
影响因子：
--
通讯作者：
Shuyao Li;Yu Cheng;Ilias Diakonikolas;Jelena Diakonikolas;Rong Ge;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Shuyao Li;Yu Cheng;Ilias Diakonikolas;Jelena Diakonikolas;Rong Ge;Stephen J. Wright
在机器学习中许多应用程序中，找到大概的二阶固定点（SOSP）是随机非凸优化的一个充分且基本的问题。但是，在存在异常值的情况下，该问题对该问题的理解很少，从而限制了在对抗环境中使用现有的非凸算法的使用。在本文中，我们研究了在强污染模型中找到SOSP的问题，在强污染模型中，数据标记的持续部分被任意损坏。我们介绍了一个通用框架，用于使用\ emph {dimension-nistepents}的精度保证，使用$ \ widetilde {o}（{d^2}/{\ epsilon}）$ d $是环境，尺寸和$ \ epsilon $是损坏数据点的一部分。作为我们框架的具体应用，我们将其应用于低等级矩阵传感的问题，发展有效且可证明的稳健算法，这些算法可以忍受传感矩阵和测量结果中的损坏。此外，我们建立了一个统计查询下限，提供了证据，表明二次依赖对$ d $在样本复杂性中对于计算有效算法是必需的。
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.