不对称低秩矩阵分解的梯度下降全局收敛性

Jun, 2021

不对称低秩矩阵分解的梯度下降全局收敛性

Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization

Tian Ye, Simon S. Du

TL;DR本研究论文首次证明了初始化的随机梯度下降算法可以在多项式时间内收敛到具有对称和非对称特点的低秩矩阵分解问题的全局最小值，该证明基于新的对称化技术和定量扰动分析方法，并可以拓展到其他相关的非凸问题。

Abstract

We study the asymmetric low-rank factorization problem: \[\min_{\mathbf{U} \in \mathbb{R}^{m \times d}, \mathbf{V} \in \mathbb{R}^{n \times d}} \frac{1}{2}\|\mathbf{U}\mathbf{V}^\top -\mathbf{\Sigma}\|_F^2\] where $\mathbf{\Sigma}$ is a given matrix of size $m \times n$ and rank $d$. T

发现论文，激发创造

非凸因式分解实现保证矩阵补全

矩阵分解是一种常用的大规模矩阵补全方法，本文提出了一种理论保证，即在正则化条件下，优化算法可以收敛于矩阵分解的全局最优解，并恢复真实的低秩矩阵，其中的非对称矩阵分解的扰动分析是一项技术贡献。

Nov, 2014

投影梯度下降法的快速低秩估计：广义统计和算法保证

通过矩阵分解和投影梯度下降算法解决约束最优化问题，提供了一种通用理论框架，当给定适当的初始化时，可以几何级数地收敛到具有统计意义的解，适用于许多具体模型。

Sep, 2015

通过非凸矩阵分解高效可靠地找到低秩解

本研究提出了一种基于矩阵分解的优化方法——双因式梯度下降算法（BFGD），在一定条件下可以实现局部次线性收敛以及全局线性收敛，为实现矩阵分解优化问题提供了一种有效的解决思路。

Jun, 2016

非凸低秩问题中不存在虚假局部极小点：统一的几何分析

发展了一种新框架，旨在捕捉一般非凸低秩矩阵问题的共同局面，包括矩阵感知，矩阵完成和鲁棒PCA，在优化风景线的现有分析的基础上进行了连接和简化，自然地导致了不对称矩阵完成和鲁棒PCA的新结果

Apr, 2017

解决梯度下降隐式偏差的矩阵分解方法：贪婪的低秩学习

通过深度为 2 的矩阵分解及理论和实证证据，我们证明了梯度流（用无穷小初始化）等价于一个简单的启发式秩量化算法，同时对深度大于等于 3 的情况进行了扩展，并证明了深度的优势在于对初始化幅度的弱依赖性，因此这种秩量化更可能在实践中起作用。

Dec, 2020

非凸矩阵分解的噪声梯度下降收敛于平坦极小值

本文研究了非凸矩形矩阵分解问题，通过引入噪声来解决全局极小值的不确定性，表明噪声向特定最优解施加了影响。

Feb, 2021

矩阵分解的交替梯度下降收敛

本文研究了交替梯度下降算法应用于非对称矩阵分解目标函数的收敛性分析，证明了在充分迭代步数内，随机初始化下可以收敛到较优解，此结果可以为更广泛的非凸低秩矩阵分解问题的收敛分析提供帮助，并在实验中得到了验证。

May, 2023

小随机梯度下降的非对称矩阵感知

矩阵感知是从少量线性测量中重建低秩矩阵的问题，我们引入了连续微分方程，称其为“扰动梯度流”，通过边界足够有界的累计误差，证明扰动梯度流迅速收敛到真实目标矩阵，从而提供了一种基于梯度下降的非对称矩阵感知的新证明方法。

Sep, 2023

小初始化的梯度下降收敛性用于非正则化矩阵补全

对称矩阵完成问题的研究表明，使用小初始化的梯度下降算法可以无需显式正则化地收敛到真实解，即使在过参数优化情况下也成立；同时，初始点越小，解的精确度越高。针对该问题的全局收敛性分析借助了一种新颖的弱耦合一致性评估方法，拓展了经典的留一法分析范畴。

Feb, 2024

联邦环境中低秩矩阵分解的深入分析

本研究针对低秩矩阵分解在联邦学习设置中的分布式算法进行了分析，解决了在多客户端环境中数据集局部性对模型训练的影响。通过将光滑非凸问题转化为光滑强凸问题，我们提出了基于并行Nesterov梯度下降的解决方案，并证实了其收敛速度优于现有文献的结果。实验表明，该方法在重构误差上表现出显著改善，能够有效提升模型训练的效率。

Sep, 2024