ICMLJan, 2021

针对鞍点问题的单侧 Frank-Wolfe 算法

PDF
TL;DR通过使用近端原始对偶算法和 Frank-Wolfe 算法，结合线性最小化 oracle 和低效率近端图来求解包括离散优化问题松弛之后的凸凹鞍点问题 —— 一个优化复杂且具有挑战性的问题，本文展示了该算法在诸如机器学习和计算机视觉等方面的标签问题上的应用。
convex-concave saddle-point problemsproximal primal-dual algorithmslinear minimization oraclelagrangian relaxationlabeling problems
发现论文，激发创造
  • Frank-Wolfe 算法求解鞍点问题

    本研究将 Frank-Wolfe 算法拓展至解决约束光滑凸 - 凹鞍点问题，只需要访问线性最小化神谕。通过利用 FW 优化的最近进展，我们首次证明了 FW 类型的鞍点求解器在多面体上的收敛性，并探讨了其他收敛结果和 FW 算法理论基础的缺口。同时，通过应用结构化预测与组合惩罚以及涉及指数数量的匹配多面体游戏等问题的研究，探讨了没有已知有效替代方案的潜在应用。

    Oct, 2016

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

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

    Feb, 2020

  • 一种带有线搜索的原对偶算法求解一般凸 - 凹鞍点问题

    提出了一种基于新动量项的原始 - 对偶算法，使用偏导数来求解不要求耦合项线性的凸 - 凹函数产生的鞍点问题，并给出了具体的收敛速度。

    Mar, 2018

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

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

    Apr, 2018

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

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

    Nov, 2015

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

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

    Oct, 2018

  • 关于鞍点问题的更低迭代复杂度下界

    本文研究了纯一阶方法或者使用投影算子的方法找到强凸强凹鞍点问题的下降迭代复杂度下界，给出了特定参数范围下的最优算法和二次耦合问题的下降迭代复杂度下界和已有完美算法

    Dec, 2019

  • 无梯度方法求解鞍点问题

    文章介绍了一种面向凸 - 凹鞍点问题的方法，使用梯度有限差分进行随机逼近，在某些条件下可以将所需的 oracle 调用次数降低至原来的 1/（log n）倍

    May, 2020

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

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

    Jun, 2014

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

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

    May, 2020