ICMLSep, 2020

用可扩展的二阶方法逃避病态矩阵补全中的鞍点

PDF
TL;DR提出了一个迭代算法，用于低秩矩阵完成，可以解释为迭代重新加权最小二乘（IRLS）算法和应用于非凸秩代理目标的鞍点逃逸平滑牛顿方法，它结合了先前 IRLS 方法的有利数据效率与几个数量级的可伸缩性的改进。我们的方法在样本数量接近信息理论极限时就达到了局部二次收敛速度，并在数值实验中表明，与许多现有方法不同，我们的方法能够在样本很少的情况下完成条件数高达 $10^{10}$ 的非常病态的矩阵。
low-rank matrix completioniterative algorithmirls algorithmrank surrogate objectivescalability
发现论文，激发创造
  • Rank 2r 迭代最小二乘法：从少量条目高效恢复病态低秩矩阵

    提出了一种新的、简单的、计算效率高的迭代方法，用于矩阵完成的低秩分解。该方法能快速稳定地从非常少的观测数据中重建病态矩阵，并对加性噪声具有稳定性。

    Feb, 2020

  • 如何高效地逃离鞍点

    本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点，收敛速率与梯度下降到一阶稳定点的收敛速率匹配，当所有鞍点都是非退化的时，所有的二阶稳定点都是局部最小值，该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点，并可直接应用于许多机器学习应用中，包括深度学习。

    Mar, 2017

  • 通过非凸迭代重新加权最小二乘法恢复同时结构化数据

    提出一种新的算法来恢复数据，该数据符合多个异构低维结构，并专注于同时为行稀疏和低秩的数据矩阵，该算法能够利用两种结构。

    Jun, 2023

  • 迭代加权最小二乘法平滑低秩和稀疏矩阵恢复

    本文提出了一个解决低秩和 / 或稀疏矩阵最小化问题的一般框架，使用迭代重新加权最小二乘（IRLS）方法来解决混合低秩和稀疏最小化问题，例如用于解决 Schatten-p 规范和 ell_2,q-norm 规范的低秩表示问题，理论证明了所获得的解为静止点，并在合成和实际数据集上进行了广泛的实验以证明其有效性。

    Jan, 2014

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

    本文提出一种新算法 ScaledGD，它是梯度下降方法的预处理或对角线缩放版本，其预处理器是自适应且具有最小的计算开销，在低秩矩阵感知，鲁棒主成分分析和矩阵完成等任务中实现了线性收敛，具有优秀的性能表现。

    May, 2020

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

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

    Apr, 2019

  • 逃离鞍点的通用方法

    本文介绍了一种通用框架，该框架在最小化 Hessian 基础计算的同时，能够收敛到二阶临界点，侧重于解决非凸优化中的关键问题：鞍点。经实证，该策略具有较好的实际性能。

    Sep, 2017

  • 基于牛顿法的非凸优化算法：快速躲避鞍点

    本文介绍一种修改了牛顿法更新方式的二阶方法，通过替换海森矩阵的负特征值为绝对值，并使用其截断版本来考虑目标的曲率，以获得比随机梯度下降更快的局部最小值收敛速度。

    Jul, 2017

  • 非凸优化中逃离高阶鞍点的高效方法

    本文提出了一种使用高阶导数的算法，能够逃离高维复杂的鞍点结构，并保证能够收敛到三阶局部最优解，是现有技术的两倍，同时也证明了进一步寻找四阶局部最优解是 NP-hard 的。

    Feb, 2016

  • 迭代重新加权偏最小二乘调和平均用于低秩矩阵恢复

    本文提出了谐波均值迭代加权最小二乘（HM-IRLS）算法，应用于从不完整的线性观测中恢复秩为 r 的矩阵 X，通过一系列低复杂度的线性问题求解，以优化非凸的 Schatten-p 准范罚项，以提高低秩性。HM-IRLS 算法具有三个主要优势，尤其是在矩阵完成设置中：第一，算法自变量对于相关感兴趣的情况下以低秩矩阵呈现出显着的全局收敛性；第二，即使线性观察值的数量非常接近理论下界 r（d1+d2-r），HM-IRLS 表现出接近 1 的经验恢复概率；第三，如果线性观察满足适合的零空间属性，则 HM-IRLS 表现出局部超线性收敛速度（2-p）的优势。

    Mar, 2017