论文标题
梯度下降和小的随机初始化，等级-1矩阵完成
Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization
论文作者
论文摘要
与凸配方相比，由于其负担得起的复杂性，矩阵完成问题的非凸公式近年来受到了极大的关注。梯度下降（GD）是一种简单而有效的基线算法，用于解决非凸优化问题。当GD与随机初始化结合使用时，GD的成功在许多不同的问题中都被看到。但是，先前关于矩阵完成的工作需要仔细的初始化或正规化器来证明GD的收敛性。在本文中，我们研究了等级-1对称矩阵的完成，并证明当使用小的随机初始化时，GD会收敛到地面真相。我们表明，在对数数量的迭代中，轨迹进入了发生局部收敛的区域。我们在初始化大小上提供了一个足以保证收敛性的上限，并表明可以将较大的初始化用作更多样品可用。我们观察到，GD的隐式正规化效应在分析中起着至关重要的作用，并且对于整个轨迹，它可以防止每个条目变得比其他轨迹大得多。
The nonconvex formulation of the matrix completion problem has received significant attention in recent years due to its affordable complexity compared to the convex formulation. Gradient Descent (GD) is a simple yet efficient baseline algorithm for solving nonconvex optimization problems. The success of GD has been witnessed in many different problems in both theory and practice when it is combined with random initialization. However, previous works on matrix completion require either careful initialization or regularizers to prove the convergence of GD. In this paper, we study the rank-1 symmetric matrix completion and prove that GD converges to the ground truth when small random initialization is used. We show that in a logarithmic number of iterations, the trajectory enters the region where local convergence occurs. We provide an upper bound on the initialization size that is sufficient to guarantee the convergence, and show that a larger initialization can be used as more samples are available. We observe that the implicit regularization effect of GD plays a critical role in the analysis, and for the entire trajectory, it prevents each entry from becoming much larger than the others.
