Jan, 2024

对齐研究中心矩阵完备问题的多项式精度依赖解决方案

PDF
TL;DR我们提出了一个多项式依赖于精度 epsilon 的矩阵补全问题的解决方案，该问题的动机是为了实现对深度神经网络中不同数量的启发式估计器进行正式评估和推理的高效计算，以实现人工智能对齐的目标。我们的解决方案是将矩阵补全问题重新构建为半定规划问题（SDP），并利用快速、高效且可扩展的 SDP 解算的最新进展中的光束谱方法。
matrix completion problemsalignment research centerheuristic estimatorsdeep neural networksai alignment
发现论文，激发创造
  • 矩阵填充无虚假局部极小值

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

    May, 2016

  • 最优低秩矩阵完成：半定松弛和特征向量分离

    通过将低秩矩阵补全问题重新表述为在投影矩阵的非凸集上的凸问题，并实施一个可证明最优的分离分支限界方案，推导出一类新的收敛松弛方法。数值实验表明，相比现有的收敛松弛方法，我们的新型收敛松弛方法将最优性差距降低了两个数量级。此外，我们展示了我们的分离分支限界方案的性能，并展示了它在解决矩阵完成问题方面的优异表现。

    May, 2023

  • 正半定规划的更快速、更简单的宽度独立并行算法

    本文研究了正半定规划的近似算法，提出了一种简单的 NC 并行算法，其迭代次数为 O (1/ϵ³ log³ n)，总工作量近似为因子分解中非零条目数的线性级别。

    Jan, 2012

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

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

    May, 2024

  • 半定规划多参考序列比对

    该研究提供了一种基于半定规划松弛的多参考点对齐问题的最大似然估计的近似算法，并在应用中表现良好，并提供了稳定性保证。

    Aug, 2013

  • 低秩矩阵完成的确定性理论

    使用图极限理论规定的某一必要且充分条件，对于一系列矩阵补全问题，只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解，该理论是完全确定性的，没有随机性假设，同时列出了一些未解决的问题。

    Oct, 2019

  • 缺失数据填补和传导学习的多项式矩阵补全

    本文提出一种新方法，在低维数据内部的情况下，通过对基于多项式的生成的矩阵的秩进行最小化，使用内核技巧结合松弛约束的目标函数的新公式，快速恢复高秩或完全秩的矩阵中的缺失条目，并且这一方法在维度较高时具有很好的性能。

    Dec, 2019

  • 图上矩阵补全

    本文提出了一种基于社区检测和流形学习的矩阵完成模型，通过约束矩阵在图上的平滑性来隐含地强制行和列之间的相似性，得到了比标准模型更好的矩阵恢复效果。

    Aug, 2014

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

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

    Nov, 2014

  • 半定规划方法求解稀疏图的二次分配问题

    本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题，采用正半定矩阵进行松弛，并通过聚类来加强松弛，使得计算复杂度和运行时间得到了缩减，可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。

    Mar, 2017