Nov, 2015

一种带有 “面内” 方向的扩展 Frank-Wolfe 方法及其在低秩矩阵补全中的应用

PDF
TL;DR本文基于低秩矩阵补全问题，提供了 Frank-Wolfe 方法的一种扩展，该方法旨在在可行区域的低维面上产生近最优解。我们采用一种新方法，在每次迭代中生成 “面内” 方向，并通过在面内和 “定常” Frank-Wolfe 步骤之间选择的新选择规则来实现。我们引入的生成面内方向的框架将 Wolfe 引入的离开步骤的概念推广了出来。特别地，面内方向始终保持下一个迭代在包含当前迭代的最小面内。我们为新方法提供了计算保证，以在计算近最优解的效率和迭代产生的最小面的维度上进行权衡。我们将新方法应用于矩阵补全问题，其中低维面对应于低秩矩阵。我们提供了计算结果，证明了我们的方法论方法在产生非常低秩的近最优解方面的有效性。在人工数据集和真实数据集上，与 Frank-Wolfe 方法或其传统的远离步骤变体相比，我们展示了计算非常低秩近最优解的显著加速。
low-rank matrix completionfrank-wolfe methodin-face directionsminimal facecomputational guarantees
发现论文，激发创造
  • 解决 MAP-MRF 问题的松弛问题：组合内向 Frank-Wolfe 方向

    本研究旨在提高解决基于最大后验马尔可夫随机场的 LP 松弛的问题的效率，并提出了一种基于面内 Frank-Wolfe 方向的高效实现方法，实验结果表明，该方法是当前某些问题类的最先进 LP 解决器。

    Oct, 2020

  • 关于 Frank-Wolfe 优化变量的全局线性收敛性

    本文研究了 Frank-Wolfe 算法，提出了几个变体并分别给出了全局线性收敛性证明，证明了不同算法的收敛速度取决于几何量与条件数的乘积，这些算法在机器学习，子模优化等领域取得了实际应用。

    Nov, 2015

  • 多面体问题下的 Frank-Wolfe 算法：严格互补性和稀疏性的再探讨

    本文介绍了一种带有机械销为严格互补条件的 Frank-Wolfe 算法，证明了在该条件下该算法的收敛速度具有线性，并且仅取决于最优面的维度。

    May, 2020

  • 一种新的 Frank-Wolfe 算法。分析及其在大规模 SVM 训练的应用

    本研究提出并分析了一种基于新的 away steps 方法的 Frank-Wolfe 方法变种，重点研究了在 Simplex 上的一般凸优化问题。 研究表明，该方法与传统的 away steps 可以达到相同的收敛速率和迭代次数，实验结果显示该方法比经典的 away steps 方法更快，而且精度不降。

    Apr, 2013

  • 降低 Frank-Wolfe 方法的离散化误差

    通过改进多步骤的 Frank-Wolfe 方法和 LMO - 平均方案使用一阶和高阶离散方案，从而减少离散化误差，其局部收敛速率通过一般凸集可以加速从 O (1/k) 到 O (1/k^​{3/2})，改善 Frank-Wolfe 算法的收敛速度。

    Apr, 2023

  • 带有最佳效率和实用特性的约束优化方法

    本文介绍了两种新的 Frank-Wolfe 算法变体，用于随机有限和最小化。这些方法在凸和非凸目标函数方面，都具有最佳的收敛保证。同时，本文提出的两种方法都不需要永久收集大批量数据和完整确定性梯度，可用于优化机器学习等领域中的结构约束问题。

    Apr, 2023

  • 关于带远离步长的 von Neumann 和 Frank-Wolfe 算法

    该研究展示了 von Neumann 算法在 origin 在 polype 上且仅依赖于特定几何参数时的线性收敛性和几何洞见，同时将结果扩展到了强凸函数的 Frank-Wolfe 算法的变体。

    Jul, 2015

  • Frank-Wolfe 算法的仿射不变线性收敛分析

    研究间断型 Frank-Wolfe 算法及其变种的线性收敛性，利用仅与仿射不变量相关的常数或仅与区域几何性质相关的常数来证明该算法的线性收敛性，无需了解任何问题特定参数。

    Dec, 2013

  • 约束自共轭最小化的牛顿 Frank-Wolfe 方法

    使用线性 oracle 解决自协调约束优化问题，并提供数值结果表明 Newton Frank-Wolfe 在组合优化比例、D - 最优实验设计和 logistic 回归等方面表现优异。

    Feb, 2020

  • 增广拉格朗日法的 Frank-Wolfe 分裂算法

    本文提出了一种名为 Frank-Wolfe Augmented Lagrangian (FW-AL) 算法的优化方法，该算法利用线性一致性约束来优化在相交凸集中的光滑函数，仅需要对单个约束的线性最小化预言机进行访问，并证明了该算法在一般凸紧集和多面体上的收敛率。

    Apr, 2018