Sep, 2024

联邦环境中低秩矩阵分解的深入分析

HTML
PDF
TL;DR本研究针对低秩矩阵分解在联邦学习设置中的分布式算法进行了分析，解决了在多客户端环境中数据集局部性对模型训练的影响。通过将光滑非凸问题转化为光滑强凸问题，我们提出了基于并行Nesterov梯度下降的解决方案，并证实了其收敛速度优于现有文献的结果。实验表明，该方法在重构误差上表现出显著改善，能够有效提升模型训练的效率。
发现论文，激发创造
  • 稀疏矩阵分解的紧凸松弛

    提出了一种基于新原子范数的凸形式，用于稀疏矩阵分解问题，其中假设因子的非零元素个数是固定和已知的，可应用于稀疏PCA，子空间聚类和低秩稀疏双线性回归等。使用主动集算法解决了该凸问题。

    Jul, 2014

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

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

    Sep, 2015

  • 通过非凸矩阵分解高效可靠地找到低秩解

    本研究提出了一种基于矩阵分解的优化方法——双因式梯度下降算法（BFGD），在一定条件下可以实现局部次线性收敛以及全局线性收敛，为实现矩阵分解优化问题提供了一种有效的解决思路。

    Jun, 2016

  • 重新审视低秩矩阵分解的迹范数正则化

    本文中提出了一种迭代元算法，通过动态扩展参数空间，避免优化陷入局部最优解，从而更好地解决低秩矩阵因式分解问题及其应用。

    Jun, 2017

  • 结构化低秩矩阵分解：全局最优、算法和应用

    本文研究了一种适用于大规模数据集且通过使用特定形式的正则化来捕获因素中的额外结构的矩阵分解技术，该技术将已知的正则化器（如总变化和核范数）作为特定情况。 尽管所得到的优化问题是非凸的，但我们证明如果因素的大小足够大，在某些条件下，任何因素的局部最小值都可以得到全局最小值。我们还提供了一些实用的算法来解决矩阵分解问题，并导出了给定近似解的距离与全局最优解之间的距离范围。在大数据集上，神经钙成像视频分割和高光谱压缩恢复的示例显示了我们的方法的优势。

    Aug, 2017

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

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

    Dec, 2020

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

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

    Jun, 2021

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

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

    May, 2023

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

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

    Feb, 2024

  • 高效联邦低秩矩阵补全

    我们开发并分析了一种基于梯度下降（GD）的解决方案，称为交替GD和最小化（AltGDmin），以在联邦环境中高效解决低秩矩阵完成（LRMC）问题。我们的理论保证（迭代和样本复杂度界限）表明AltGDmin是联邦环境中最高效的解决方案之一，速度最快，并且在所有迭代解LRMC的方法中具有第二最佳的样本复杂度。此外，我们还证明了两个重要的推论：（a）我们为AltGDmin解决有噪声的LRMC问题提供了保证。（b）我们展示了如何利用引理改进AltMin的样本复杂度保证，AltMin是最快的集中式解决方案。

    May, 2024