Jan, 2019

非凸矩形矩阵完整性的无 L2,∞ 正则化梯度下降

PDF
TL;DR本文介绍了如何通过改进梯度下降的技术和方法，将矩阵填充的采样率由 O (poly (条件数)*mu^3*r^3*log^3n/n) 降低至 O (mu^2*r^2 * 条件数 ^14*log (n)/n)，并且这些技术和方法在改善其他相关问题的分析方面也具有潜在的用处。
nonconvex matrix completionpositive semidefinite matrix completiongradient descentrectangular casesampling rate
发现论文，激发创造
  • 采用 Burer-Monteiro 分解和梯度下降的矩形矩阵完成的收敛分析

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

    May, 2016

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

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

    Feb, 2024

  • 矩阵填充无虚假局部极小值

    本文探讨了解决基本的机器学习问题 —— 矩阵补全的方法，并证明了普遍使用的非凸优化问题在正半定矩阵补全中没有局部极小值，可用于任意初始化的优化算法，并可在多项式时间内证明其正确性。

    May, 2016

  • 非凸统计估计中的隐式正则化：梯度下降在相位恢复、矩阵补全和盲源分离问题中线性收敛

    研究非凸优化问题中梯度下降算法的隐式正则化特性，证明在多种统计模型中，梯度下降算法在没有显式正则化的情况下也能够实现正则化，并在相位恢复、低秩矩阵补全和盲反卷积等三个基本统计估计问题中实现近乎最优的统计和计算保证。

    Nov, 2017

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

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

    Mar, 2018

  • 可证明高效的在线矩阵完成算法：非凸随机梯度下降

    该研究提出了一种可证明，高效的在线算法，用于矩阵完成问题。该算法使用随机梯度下降，具有快速的更新时间，并可自然地用于离线设置。

    May, 2016

  • 有限样本下精确快速矩阵补全

    该论文提出了一种矩阵完成问题的快速迭代算法，该算法观测到 O (nr^5log^3 n) 的条目，具有确定的样本复杂度，可以解决低秩矩阵恢复的问题。

    Nov, 2014

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

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

    Mar, 2016

  • 基于凸化的离散感知矩阵补全的 l₀- 范数逼近

    在结构化环境下，本文提出了一种改进的低秩矩阵补全方法，通过引入离散字母表集合，使用基于连续可微函数的分数规划方法规范离散性，从而比现有方法和基于 L1 范数的离散感知矩阵补全方法具有更好的性能。

    May, 2024

  • 从含噪数据中恢复低秩张量的非凸方法

    我们提出了一个两阶段的非凸算法，用于从高度不完整和随机损坏的观测值中重建低秩张量，并在几乎线性时间内恢复所有单个张量因子，同时享受接近最优的统计保证，我们还讨论了如何扩展我们的方法以适应非对称张量。

    Nov, 2019