Feb, 2024

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

PDF
TL;DR对称矩阵完成问题的研究表明，使用小初始化的梯度下降算法可以无需显式正则化地收敛到真实解，即使在过参数优化情况下也成立；同时，初始点越小，解的精确度越高。针对该问题的全局收敛性分析借助了一种新颖的弱耦合一致性评估方法，拓展了经典的留一法分析范畴。
symmetric matrix completiongradient descentover-parameterized regimeconvergence ratetrue rank
发现论文，激发创造
  • 非凸矩形矩阵完整性的无 L2,∞ 正则化梯度下降

    本文介绍了如何通过改进梯度下降的技术和方法，将矩阵填充的采样率由 O (poly (条件数)*mu^3*r^3*log^3n/n) 降低至 O (mu^2*r^2 * 条件数 ^14*log (n)/n)，并且这些技术和方法在改善其他相关问题的分析方面也具有潜在的用处。

    Jan, 2019

  • 矩阵感知中过参数化如何降低梯度下降速度：对称性和初始化的困扰

    研究论文通过严格的证明展示了过参数化如何改变矩阵感知问题中梯度下降的收敛行为，论文涉及过参数化与称对称参数化以及非对称参数化，提出了线性收敛结果并给出了关键关键字。

    Oct, 2023

  • Riemannian 优化在低秩矩阵补全中的保证

    研究嵌入低秩矩阵流形的黎曼优化方法在矩阵补全问题上的应用和收敛性，其中采样复杂度能进一步通过重新采样的黎曼梯度下降初始化方法减小，这取决于采样算子的像的非对称限制性同构性质和低秩矩阵流形的曲率。

    Mar, 2016

  • 采用 Burer-Monteiro 分解和梯度下降的矩形矩阵完成的收敛分析

    利用正定矩阵在更高维度上的升阶和简单的梯度下降算法，我们能够以高概率线性收敛到全局最优解，从而有效地解决了矩阵 Completion 问题。

    May, 2016

  • 矩阵补全的留一法：原始和对偶分析

    本文介绍了一种基于 Leave-one-out 方法的技巧用于解决低秩矩阵完成问题，进而通过对 Projected Gradient Descent 和 nuclear norm minimization 等算法进行分析，得到了这些算法的收敛性保证以及较为精细的界限。

    Mar, 2018

  • 利用随机初始化的黎曼梯度下降快速全局收敛的低秩矩阵恢复

    本文提出了一种适用于 Riemann 流形上低秩矩阵恢复问题的新的全局分析框架，其中使用 Riemann 梯度下降算法最小化最小二乘损失函数，并研究了渐近行为以及精确收敛速率。

    Dec, 2020

  • 过参数化矩阵感知和二次激活神经网络中的算法正则化

    本文研究了正定矩阵和一层神经网络的学习问题，通过梯度下降算法和二次激活函数的方式来实现隐式正则化，提出利用 UU 转置参数化正定矩阵并最小化平方损失函数的方法来恢复正定矩阵，并且证明在初始值的基础上，梯度下降算法大约在 O (sqrt (r)) 步长内能复原正定矩阵。

    Dec, 2017

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

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

    Nov, 2014

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

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

    Jun, 2021

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

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

    May, 2023