Oct, 2015

关于凸优化和非凸优化的在线 Frank-Wolfe 算法

PDF
TL;DR探讨在线变体的 Frank-Wolfe 算法，包括简单迭代更新和非自适应步长规则，研究凸和非凸损失的多个新结果，并基于对随机 Frank-Wolfe 算法的改进分析得出在强凸随机成本时的遗憾界和任何时刻的最优性为 O (log^3T/T) 和 O (log^2T/T) ; 此外，该在线算法即使在损失非凸的情况下也能收敛，以速率 O (1/T 的平方根) 找到时变 / 随机损失的稳态点。
发现论文，激发创造
  • 面向无梯度和无投影的随机优化

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

    Oct, 2018

  • 在线连续子模最大化

    本文研究一种在线优化过程，其中目标函数不是凸函数（也不是凹函数），而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体，它可以访问目标函数的全梯度，并证明它对未来最佳可行解的（1-1/e）- 近似具有 O（T 的平方根）的遗憾界。对于只能获得梯度的无偏估计的情况，我们还提出了在线随机梯度上升算法，并证明它也具有 O（T 的平方根）的遗憾界，但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数，并证明相同的次线性遗憾界。最后，在几个问题实例上演示了算法的效率，包括非凸 / 非凹二次规划，子模集函数的多线性扩展和 D - 最佳设计。

    Feb, 2018

  • 更快的无投影在线学习

    研究了在线学习问题中的限制，提出了基于 Follow-the-Perturbed-Leader 的投影法之外的高效项目方法，其保证了平滑成本函数和每个迭代中一个线性优化计算的一般在线凸优化中的 $T ^ {2/3}$ 后悔界。

    Jan, 2020

  • 随机 Frank-Wolfe 非凸优化方法

    本文研究非凸随机优化和有限和优化问题中的 Frank-Wolfe 方法，并提出基于方差约减技术的新型非凸 Frank-Wolfe 方法，证明了其具有比传统方法更快的收敛速度。

    Jul, 2016

  • 基于随机梯度的无需投影的在线优化：从凸性到次模性

    该论文提出了一种新颖的元 Frank-Wolfe 算法及其简化版 One-Shot-Frank-Wolfe，用于对在线优化进行全局和子模最优解的快速求解。其方法基于梯度下降实现，通过随机梯度估算和孪生逼近算法来降低收敛难度。

    Feb, 2018

  • 无投影方差减少的随机优化

    本研究利用一种新的方差降低技术，提出两种随机 Frank-Wolfe 算法变体，可在小于梯度下降算法的数据梯度评估次数下，获得更好的结果。

    Feb, 2016

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

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

    Nov, 2015

  • 无投影在线学习

    本论文提出采用 Frank-Wolfe 技术的高效在线学习算法，避免了投影步骤，同时在在线凸优化方面获得了一系列遗憾界，特别是在随机在线平滑凸优化方面。此外，我们的算法具有参数自由性和产生稀疏决策的优点，并将算法应用到协作过滤的计算密集型应用中，并在标准数据集上显示出理论上的改进。

    Jun, 2012

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

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

    Jun, 2014

  • 一种高效的在线凸优化内点方法

    在线凸优化中一种新的遗憾最小化算法被描述，该算法具有良好的遗憾界限和适应性，并与内点算法在运行时间上相匹配。

    Jul, 2023