可证明高效的在线矩阵完成算法:非凸随机梯度下降
本文提出在非凸优化算法的研究中,矩阵补全问题是一个重要的问题,但现有的理论分析都基于每个条目都有相同的概率被观察到的假设,不符合实际。因此,当每个条目被观察到的概率稍有不同的情况下,我们提出一种预处理方法,以便可以恢复基础地真实矩阵。
Mar, 2018
本研究探讨通过非凸优化从线性测量(即矩阵感知)中估计低秩矩阵的问题,并建议了一种有效的随机方差减少梯度下降算法来解决此问题。我们的算法适用于有噪声和无噪声的情况。在有噪声的情况下,我们证明了该算法在最小化统计误差方面以线性速率收敛于未知低秩矩阵。在无噪声的情况下,我们的算法保证线性收敛于未知低秩矩阵,并在最优采样复杂度下实现了精确恢复。值得注意的是,我们提出的算法的总计算复杂度(定义为迭代复杂度乘以每次迭代时间复杂度)低于基于梯度下降的最新算法。用合成数据的实验证明了该算法优于现有算法。
Jan, 2017
本文探讨了解决基本的机器学习问题 —— 矩阵补全的方法,并证明了普遍使用的非凸优化问题在正半定矩阵补全中没有局部极小值,可用于任意初始化的优化算法,并可在多项式时间内证明其正确性。
May, 2016
本文研究了从噪声测量中估计低秩矩阵的问题,并提出一种修改的非凸梯度下降方法,既能解决慢收敛的问题,又能保持极小值最优性,通过医学成像应用的实验,我们观察到,与先前的方法相比,重建误差显着减小。
May, 2023
本文介绍了如何通过改进梯度下降的技术和方法,将矩阵填充的采样率由 O (poly (条件数)*mu^3*r^3*log^3n/n) 降低至 O (mu^2*r^2 * 条件数 ^14*log (n)/n),并且这些技术和方法在改善其他相关问题的分析方面也具有潜在的用处。
Jan, 2019
我们提出了一个两阶段的非凸算法,用于从高度不完整和随机损坏的观测值中重建低秩张量,并在几乎线性时间内恢复所有单个张量因子,同时享受接近最优的统计保证,我们还讨论了如何扩展我们的方法以适应非对称张量。
Nov, 2019
研究嵌入低秩矩阵流形的黎曼优化方法在矩阵补全问题上的应用和收敛性,其中采样复杂度能进一步通过重新采样的黎曼梯度下降初始化方法减小,这取决于采样算子的像的非对称限制性同构性质和低秩矩阵流形的曲率。
Mar, 2016
本文研究了针对大规模低秩矩阵的部分和带噪声数据中的矩阵补全问题,采用凸松弛和 Burer-Monteiro 方法,成功地将凸松弛的实践与非凸方法的统计保证相结合,取得了近乎最优的估计误差。
Feb, 2019