Dec, 2015

Frank-Wolfe 算法的多面体调节和线性收敛

PDF
TL;DR研究表明，当在具有 Lipschitz 梯度的强凸函数上应用梯度下降算法时，其收敛速度由函数的条件数决定且算法收敛速度类似于一个带有离开步骤的 Frank-Wolfe 算法。在对无约束情况的良好扩展中，算法的收敛速度由函数的条件数及多面体的某个特定条件数的乘积决定。本研究为这种类型多面体调整提出了新的方法，并且认为之前的相关方法是等价的，并可通过多面体的参数进行统一，从而实现算法的线性收敛。此外，对于凸二次目标，研究表明收敛速度取决于相应缩放多面体的条件数。
gradient descent algorithmstrongly convex functionlipschitz gradientfrank-wolfe algorithmpolytope
发现论文，激发创造
  • 结构多面体的线性内存和分解不变线性收敛条件梯度算法

    提出了一种改进的条件梯度方法来解决约束凸优化问题，针对多面体进行了相应的分析及优化，降低了每次迭代时的计算及内存开销，并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。

    May, 2016

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

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

    Nov, 2015

  • Frank-Wolfe 方法在强凸集合上的更快收敛速率

    在本篇论文中，我们考虑了在强凸集上进行的优化的特殊情况。我们证明，与一般情况的收敛速度为 1/t 相比，vanila FW 方法以 1/t² 的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导 FW 方法的多个快速收敛结果。

    Jun, 2014

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

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

    May, 2020

  • 混合条件梯度法：解除条件梯度法的约束

    提出了一种混合条件梯度方法，可用于在多面体 P 上最小化平滑凸函数，该方法结合了 Frank-Wolfe 算法和基于梯度的步骤，并通过保持迭代点为 P 的极端点的有限数量的稀疏凸组合，避免了向 P 投影的优点，实现了强凸函数的线性收敛。

    May, 2018

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

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

    Dec, 2013

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

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

    Jul, 2015

  • 一种线性收敛的条件梯度算法及其在在线和随机优化中的应用

    本研究介绍了一种基于条件梯度算法的优化模型，可用于求解线性优化问题和非线性凸优化问题，并给出了一种基于此算法的在线凸优化算法，具有线性收敛速度和最优的遗憾保证。

    Jan, 2013

  • 面向无梯度和无投影的随机优化

    本文介绍了一种零阶 Frank-Wolfe 算法，用于解决约束随机优化问题，该算法与基本 Frank-Wolfe 算法同样无需投影，且不需要计算梯度，可收敛于凸平滑约束下的优化目标函数。同时，本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数，本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4})，并在黑盒优化设置上进行实验，证明了其效果。

    Oct, 2018

  • 非强凸函数的线性收敛离点条件梯度法

    本研究利用简单的对偶算法和相应的误差边界提供了一种新的算法和分析，可以在紧凑型多面体集上最小化一个包含线性和强凸函数和线性转换组合的函数，同时具有线性收敛速度和附加线性项，允许通过条件梯度方法求解。

    Apr, 2015