非凸低秩问题中不存在虚假局部极小点:统一的几何分析
该研究表明,使用非凸因式分解的参数化方法可以从不一致的线性测量中恢复低秩矩阵,且不存在虚假的局部最小值。并且在有噪声的测量中,所有局部最小值都非常靠近全局最优解。结合鞍点的曲率界限,保证了随机梯度下降从随机初始化出发以多项式时间全局收敛。
May, 2016
本文从统计模型的角度出发,系统地讨论低秩矩阵分解非凸优化的可靠解法,总结出了两种方法:1. 根据问题特征设计初始值,进行迭代求解;2. 利用全局凸性分析,无需初始值,直接求解。文章阐述了这些方法在各种场景下的应用并剖析了其理论基础。
Sep, 2018
提出了一种用于研究具有对称结构的非凸优化景观的通用理论,基于不变群对目标函数的 Hessian 矩阵进行分析并应用于低秩矩阵分解问题,其中研究了所有驻点和全局最小值,将整个参数空间划分为三个区域,为常见迭代算法提供了强有力的全局收敛保证。
Dec, 2016
通过推导理论,证明矩阵感知问题中存在有利于优化的严格鞍点,从而解释了非凸优化中的复杂性,并介绍了高阶损失函数对远离真实矩阵的鞍点的影响,加速了逃离和解决非凸优化问题,为解决机器学习中的更广泛目标提供了一个综合框架。
Mar, 2024
提出了一种基于梯度下降算法的非凸优化的低秩矩阵估计的统一框架,其通用性很强,可应用于噪声和无噪声观测,算法能够线性收敛到未知低秩矩阵的最小最优统计误差,同时也能够以线性速率收敛到未知低秩矩阵,并以最优样本复杂度实现精确恢复。
Oct, 2016
采用 Burer-Monteiro 方法,论文提出一种较少变量的非凸非光滑优化问题形式的低维对称和非对称正秩 - 1 RPCA,其具有良好的景观和不会有虚假的本地解决方案,保证了精确恢复真实主分量的强大确定性和概率保证。
Dec, 2018
本文针对两个广泛使用的最小化问题:凸函数最小化问题和加上核范数的凸函数最小化问题,提出使用低秩分解和替代核范数的方法来加速求解问题,并证明其可以在全局范围内找到最优解。
Nov, 2016
通过矩阵分解和投影梯度下降算法解决约束最优化问题,提供了一种通用理论框架,当给定适当的初始化时,可以几何级数地收敛到具有统计意义的解,适用于许多具体模型。
Sep, 2015
本文研究了在非凸约束下最小化问题的几何特性与梯度下降的收敛性之间的相互作用,并探讨了这些几何特性在低秩估计问题中优化的作用及其计算方法,从而提出了一种更高效的解决方法。
Mar, 2017