Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
复制标题
DOI：
--
复制
发表时间：
2021
影响因子：
4
通讯作者：
Jialun Zhang;S. Fattahi;Richard Y. Zhang
中科院分区：
文献类型：
--
作者：
Jialun Zhang;S. Fattahi;Richard Y. Zhang
在非凸矩阵分解的实际例子中，真实解r的秩通常是未知的，因此模型的秩r可以被过度指定为r > r。矩阵分解的这种过度参数化的机制显著地减慢了局部搜索算法的收敛，从r = r = r的线性速率到r > r时的次线性速率。我们提出了一个廉价的预条件的非凸矩阵分解，恢复梯度下降的收敛速度回到线性，即使在过参数化的情况下，矩阵传感变体，同时也使其不可知的可能病态的地面真理。经典的梯度下降在解决方案的一个邻域减慢，由于需要模型矩阵因子变得奇异。我们的关键结果是，这种奇异性可以通过具有特定阻尼参数值范围的正则化来校正。事实上，一个好的阻尼参数可以便宜地估计从当前的阻尼。由此产生的算法，我们称之为预处理梯度下降或PrecGD，是稳定的噪声下，线性收敛到信息理论上的最优误差界。我们的数值实验发现，PrecGD的作品同样很好地恢复过参数化制度的非凸矩阵分解的其他变量的线性收敛。
In practical instances of nonconvex matrix factorization, the rank of the true solution r ⋆ is often unknown, so the rank r of the model can be overspecified as r > r ⋆ . This over-parameterized regime of matrix factorization significantly slows down the convergence of local search algorithms, from a linear rate with r = r ⋆ to a sublinear rate when r > r ⋆ . We propose an inexpensive preconditioner for the matrix sensing variant of nonconvex matrix factorization that restores the convergence rate of gradient descent back to linear, even in the over-parameterized case, while also making it agnostic to possible ill-conditioning in the ground truth. Classical gradient descent in a neighborhood of the solution slows down due to the need for the model matrix factor to become singular. Our key result is that this singularity can be corrected by ℓ 2 regularization with a specific range of values for the damping parameter. In fact, a good damping parameter can be inexpensively estimated from the current iterate. The resulting algorithm, which we call preconditioned gradient descent or PrecGD, is stable under noise, and converges linearly to an information theoretically optimal error bound. Our numerical experiments find that PrecGD works equally well in restoring the linear convergence of other variants of nonconvex matrix factorization in the over-parameterized regime.