论文标题
非平滑矩阵和低级矩阵优化问题的低排放外部方法
Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems
论文作者
论文摘要
低级和非平滑矩阵优化问题捕获了统计和机器学习中的许多基本任务。尽管近年来在开发\ textit {平滑}低排名优化问题的有效方法方面取得了重大进展，这些问题避免了保持高级矩阵和计算昂贵的高级SVD，但对非平滑问题的进步的步伐缓慢。 在本文中，我们考虑了针对此类问题的标准凸放松。 Mainly, we prove that under a natural \textit{generalized strict complementarity} condition and under the relatively mild assumption that the nonsmooth objective can be written as a maximum of smooth functions, the \textit{extragradient method}, when initialized with a ``warm-start'' point, converges to an optimal solution with rate $O(1/t)$ while requiring only two \textit{low-rank} SVD通过迭代。我们在所需的SVD等级与我们需要初始化该方法的球的半径之间进行精确的权衡。我们通过几个非平滑级别矩阵恢复任务进行经验实验来支持我们的理论结果，这表明当使用简单的初始化时，当完整级别的SVD替换为与（低级别）接地矩阵的等级相匹配的级别级别的SVD时，该方法会产生完全相同的迭代，以恢复。
Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in recent years in developing efficient methods for \textit{smooth} low-rank optimization problems that avoid maintaining high-rank matrices and computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced. In this paper we consider standard convex relaxations for such problems. Mainly, we prove that under a natural \textit{generalized strict complementarity} condition and under the relatively mild assumption that the nonsmooth objective can be written as a maximum of smooth functions, the \textit{extragradient method}, when initialized with a ``warm-start'' point, converges to an optimal solution with rate $O(1/t)$ while requiring only two \textit{low-rank} SVDs per iteration. We give a precise trade-off between the rank of the SVDs required and the radius of the ball in which we need to initialize the method. We support our theoretical results with empirical experiments on several nonsmooth low-rank matrix recovery tasks, demonstrating that using simple initializations, the extragradient method produces exactly the same iterates when full-rank SVDs are replaced with SVDs of rank that matches the rank of the (low-rank) ground-truth matrix to be recovered.
