Accelerated Factored Gradient Descent for Low-Rank Matrix Factorization
Accelerated Factored Gradient Descent for Low-Rank Matrix Factorization
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Dongruo Zhou;Yuan Cao;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Dongruo Zhou;Yuan Cao;Quanquan Gu
研究了低秩矩阵估计问题，其中目标函数L（M）定义在秩小于或等于r的半正定矩阵空间上.解决这个问题的一种快速方法是矩阵分解，它将M重新参数化为两个较小矩阵的乘积，使得M = UU（cid：62），然后直接对U执行梯度下降，即，因子梯度下降由于所产生的问题是非凸的，Nesterov的加速方案是否可以适应它仍然是一个长期存在的问题。在本文中，我们回答了这个问题，提出了一个新的和实用的加速因子梯度下降方法的启发Nesterov的加速梯度下降。该方法具有更好的迭代复杂度和计算复杂度比国家的最先进的算法在广泛的制度。我们算法的核心思想是将所有的迭代限制在一个特殊的凸集上，这使得加速。实验结果表明，该算法具有更快的收敛速度，并证实了我们的理论。
We study the low-rank matrix estimation problem, where the objective function L ( M ) is defined over the space of positive semidefi-nite matrices with rank less than or equal to r . A fast approach to solve this problem is matrix factorization, which reparameterizes M as the product of two smaller matrix such that M = UU (cid:62) and then performs gradient descent on U directly, a.k.a., factored gradient descent. Since the resulting problem is nonconvex, whether Nesterov’s acceleration scheme can be adapted to it remains a long-standing question. In this paper, we answer this question affirmatively by proposing a novel and practical accelerated factored gradient descent method motivated by Nesterov’s accelerated gradient descent. The proposed method enjoys better iteration complexity and computational complexity than the state-of-the-art algorithms in a wide regime. The key idea of our algorithm is to restrict all its iterates onto a special convex set, which enables the acceleration. Experimental results demonstrate the faster convergence of our algorithm and corroborate our theory.