Jan, 2021

关于过度参数化矩阵感知的计算和统计复杂度

PDF
TL;DR通过将分解矩阵 F 分解为单独的列空间来捕捉额外等级的影响，我们考虑使用分解梯度下降（FGD）方法来解决低秩矩阵感知问题，该问题将真实排名为空未知且超说明定。因此，我们提供了 FGD 在超参数矩阵感知问题的统计和计算复杂性的全面图景。
low rank matrix sensingfactorized gradient descendover-parameterized matrix sensingcolumn spacescomputational complexity
发现论文，激发创造
  • 矩阵感知中过参数化如何降低梯度下降速度：对称性和初始化的困扰

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

    Oct, 2023

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

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

    Dec, 2017

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

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

    Sep, 2023

  • 放弃凸性以加速半定规划

    本研究探讨了正定半矩阵上凸函数的最小化问题，提出了分解梯度下降算法 (FGD) 的规则，并在标准条件下分析了其收敛性和收敛速率，同时证明了该算法在可重构矩阵分解等实际问题上的有效性，是首篇在一般凸函数下提供收敛率保证的研究。

    Sep, 2015

  • 泛化因子分解机和秩一矩阵感知的非凸一次过程框架

    利用条件独立 RIP 特性构造 GMF 模型的估计序列，实现在线学习、线性收敛及对只消耗 O (kd) 内存，在遍历一遍数据集时，仅需要执行矩阵−向量乘积操作的推广版因子分解机 (gFM)。

    Aug, 2016

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

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

    May, 2023

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

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

    Jan, 2017

  • 通过缩放梯度下降可证明地加速病态低秩估计，即使过度参数化

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

    Oct, 2023

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

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

    Feb, 2024

  • 更多即更少：通过过度参数化诱导稀疏性

    研究了深度学习模型过度参数化和随机梯度下降的泛化能力现象，探讨了稀疏恢复的情况，提出了一种相应的超参数化均方误差损失函数，证明了该函数的梯度下降可以收敛到最小 L1 范数的好近似解。

    Dec, 2021