May, 2020

通过缩放梯度下降加速恶态低秩矩阵估计

PDF
TL;DR本文提出一种新算法 ScaledGD，它是梯度下降方法的预处理或对角线缩放版本，其预处理器是自适应且具有最小的计算开销，在低秩矩阵感知，鲁棒主成分分析和矩阵完成等任务中实现了线性收敛，具有优秀的性能表现。
low-rank matrix estimationgradient descentalternating minimizationscaled gradient descentrobust principal component analysis
发现论文，激发创造
  • 通过缩放梯度下降可证明地加速病态低秩估计，即使过度参数化

    本研究论文介绍了一种名为 ScaledGD 的新算法，通过合适的预处理能够快速收敛于低秩对象，并在多种任务中保持梯度下降的低迭代成本，同时无论条件数如何，都能以恒定速率线性收敛，突出了在加速非凸统计估计中适当预处理的能力。

    Oct, 2023

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

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

    Sep, 2015

  • 通过非凸梯度下降快速且极小化误差地估计低秩矩阵

    本文研究了从噪声测量中估计低秩矩阵的问题，并提出一种修改的非凸梯度下降方法，既能解决慢收敛的问题，又能保持极小值最优性，通过医学成像应用的实验，我们观察到，与先前的方法相比，重建误差显着减小。

    May, 2023

  • 某些非凸矩阵问题的随机梯度下降全局收敛

    本研究展示了低秩最小二乘问题上的随机梯度下降算法的步长设定方案，并证明了在广泛的采样条件下，该算法能够从一个随机起始点全局收敛。

    Nov, 2014

  • 低秩矩阵线性恢复的随机方差减少梯度下降

    本研究探讨通过非凸优化从线性测量（即矩阵感知）中估计低秩矩阵的问题，并建议了一种有效的随机方差减少梯度下降算法来解决此问题。我们的算法适用于有噪声和无噪声的情况。在有噪声的情况下，我们证明了该算法在最小化统计误差方面以线性速率收敛于未知低秩矩阵。在无噪声的情况下，我们的算法保证线性收敛于未知低秩矩阵，并在最优采样复杂度下实现了精确恢复。值得注意的是，我们提出的算法的总计算复杂度（定义为迭代复杂度乘以每次迭代时间复杂度）低于基于梯度下降的最新算法。用合成数据的实验证明了该算法优于现有算法。

    Jan, 2017

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

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

    Jun, 2021

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

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

    May, 2023

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

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

    Dec, 2020

  • 具有复合优化的低秩矩阵恢复：良好的条件和快速收敛

    该研究提出了一种新的低秩矩阵恢复方法，采用非平滑惩罚形式，在某些具体情况下能够克服传统平滑方法的病态问题，同时具有自适应性和鲁棒性。数值实验说明了该方法在解决相位恢复、盲卷积、矩阵补全和稳健 PCA 等计算任务中的优势。

    Apr, 2019

  • 预处理随机梯度下降

    本文提出了一种新的方法，通过估计一个预条件器来加速随机梯度下降算法的收敛速度，适用于凸性和非凸性优化，具有稳定梯度降噪的效果，并且经过了大规模问题的有效预条件估计验证，可以在无需调整的情况下，高效解决深度神经网络等复杂问题

    Dec, 2015