Jul, 2020

加速的随机无梯度投影方法

HTML
PDF
TL;DR本文提出了一种加速的随机零阶Frank-Wolfe优化算法，通过使用SPIDER/SpiderBoost技术和一种新的动量加速技术，它可以在非凸优化中实现O(d√nε⁻²)的函数查询复杂度，并改进了现有最佳结果，同时在随机问题中实现了O(dε⁻³)的函数查询复杂度，同时提出了基于STORM的Acc-SZOFW *，它不需要大批量也可以达到与Acc-SZOFW相同的函数查询复杂度。
发现论文，激发创造
  • Frank-Wolfe方法在强凸集合上的更快收敛速率

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

    Jun, 2014

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

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

    Oct, 2015

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

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

    Feb, 2016

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

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

    Jul, 2016

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

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

    Feb, 2018

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

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

    Oct, 2018

  • 一种样本随机Frank-Wolfe算法

    本文提出了一种称为1-SFW的新的随机Frank-Wolfe算法，通过设计一种新颖的无偏动量估计器，实现了使用每次迭代的单个样品来优化，而无需仔细调整批量大小、步长、学习速率和其他复杂的超参数，并在随机凸优化、随机DR亚模拟最大化问题和一般的非凸设置中达到了最优收敛率。

    Oct, 2019

  • 非凸优化的改进零阶方差约减算法及分析

    本文介绍了两种零阶随机算法的优化和改进，其中一种通过新的ZO-SVRG-Coord-Rand算法和分析结果发现，比现有的同类算法以及ZO-GD和ZO-SGD更为优秀，另一种通过新的ZO-SPIDER-Coord算法有效降低了Gaussian随机变量的数量和步长的级别以实现相同的收敛速度和查询复杂度，并且自动实现了线性收敛率。

    Oct, 2019

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

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

    Apr, 2023

  • 无梯度方法用于重约束非凸优化

    本研究解决了传统无梯度方法在大量非凸约束下效率低下的问题。提出了一种带动量和自适应步长的双随机无梯度梯度方法（DSZOG），理论上证明其能够收敛到约束问题的$\epsilon$-稳态点。实验结果显示，该方法在训练时间和准确性方面优于其他无梯度方法。

    Aug, 2024