Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Tian Tong;Cong Ma;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Tian Tong;Cong Ma;Yuejie Chi
低秩矩阵估计是一个典型问题，在信号处理、机器学习和成像科学中有着广泛的应用。实践中流行的方法是将矩阵分解为两个紧凑的低秩因子，然后通过简单的迭代方法（例如梯度下降和交替最小化）直接优化这些因子。尽管具有非凸性，但最近的文献表明，当针对越来越多的感兴趣的问题进行正确初始化时，这些简单的启发式实际上可以实现线性收敛。然而，经过仔细检查，现有方法的计算成本仍然很高，尤其是对于病态矩阵：梯度下降的收敛速度线性取决于低秩矩阵的条件数，而交替最小化的每次迭代成本对于大型矩阵来说通常是令人望而却步的。本文的目标是提出一种称为缩放梯度下降（ScaledGD）的竞争性算法方法，它可以被视为预处理或对角缩放梯度下降，其中预处理器是自适应的并且迭代变化，计算开销最小。通过针对低秩矩阵感知、鲁棒主成分分析和矩阵补全的定制变体，我们从理论上表明 ScaledGD 实现了两全其美：它以独立于低秩矩阵条件数的速率线性收敛，类似于交替最小化，同时保持梯度下降的低每次迭代成本。我们的分析也适用于在低秩矩阵上受到强凸和平滑限制的一般损失函数。据我们所知，ScaledGD 是第一个在广泛的低秩矩阵估计任务中证明具有此类属性的算法。
Low-rank matrix estimation is a canonical problem that finds numerous applications in signal processing, machine learning and imaging science. A popular approach in practice is to factorize the matrix into two compact low-rank factors, and then optimize these factors directly via simple iterative methods such as gradient descent and alternating minimization. Despite nonconvexity, recent literatures have shown that these simple heuristics in fact achieve linear convergence when initialized properly for a growing number of problems of interest. However, upon closer examination, existing approaches can still be computationally expensive especially for ill-conditioned matrices: the convergence rate of gradient descent depends linearly on the condition number of the low-rank matrix, while the per-iteration cost of alternating minimization is often prohibitive for large matrices. The goal of this paper is to set forth a competitive algorithmic approach dubbed Scaled Gradient Descent (ScaledGD) which can be viewed as pre-conditioned or diagonally-scaled gradient descent, where the pre-conditioners are adaptive and iteration-varying with a minimal computational overhead. With tailored variants for low-rank matrix sensing, robust principal component analysis and matrix completion, we theoretically show that ScaledGD achieves the best of both worlds: it converges linearly at a rate independent of the condition number of the low-rank matrix similar as alternating minimization, while maintaining the low per-iteration cost of gradient descent. Our analysis is also applicable to general loss functions that are restricted strongly convex and smooth over low-rank matrices. To the best of our knowledge, ScaledGD is the first algorithm that provably has such properties over a wide range of low-rank matrix estimation tasks.