在谱多面体上更快的无投影凸优化
在本篇论文中,我们考虑了在强凸集上进行的优化的特殊情况。我们证明,与一般情况的收敛速度为1/t相比,vanila FW方法以1/t²的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导FW方法的多个快速收敛结果。
Jun, 2014
探讨在线变体的Frank-Wolfe算法,包括简单迭代更新和非自适应步长规则,研究凸和非凸损失的多个新结果,并基于对随机Frank-Wolfe算法的改进分析得出在强凸随机成本时的遗憾界和任何时刻的最优性为O(log^3T/T)和O(log^2T/T) ; 此外,该在线算法即使在损失非凸的情况下也能收敛,以速率O(1/T的平方根)找到时变/随机损失的稳态点。
Oct, 2015
提出了一种改进的条件梯度方法来解决约束凸优化问题,针对多面体进行了相应的分析及优化,降低了每次迭代时的计算及内存开销,并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。
May, 2016
本研究通过使用秩-$k$变体的Frank-Wolfe算法对迹范数球上的凸优化问题进行求解,其将Frank-Wolfe中的$1$-SVD替换为$top-k$ SVD算法。实验表明,当目标函数是平滑的并且强凸的,且最优解的秩最多为$k$时,该算法具有线性收敛率,从而提高了Frank-Wolfe算法及其变体的收敛速度和总时间复杂度。
Aug, 2017
提出了一种混合条件梯度方法,可用于在多面体P上最小化平滑凸函数,该方法结合了Frank-Wolfe算法和基于梯度的步骤,并通过保持迭代点为P的极端点的有限数量的稀疏凸组合,避免了向P投影的优点,实现了强凸函数的线性收敛。
May, 2018
本文介绍了一种零阶Frank-Wolfe算法,用于解决约束随机优化问题,该算法与基本Frank-Wolfe算法同样无需投影,且不需要计算梯度,可收敛于凸平滑约束下的优化目标函数。同时,本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数,本算法的Frank-Wolfe gap为O(d^{1/3}T^{-1/4}),并在黑盒优化设置上进行实验,证明了其效果。
Oct, 2018
本文探讨了强凸约束条件下的Frank-Wolfe(FW)优化,展示了一个比标准FW更快的变体的更快收敛速度,证明了即使对于非凸而是半凸和局部Lipschitz的平滑函数,FW也可以通过线搜索收敛到全局最优解,并且展示了在强凸约束集下,对于一般情况(平滑)的非凸函数,FW带有线搜索以高概率收敛到一个$O(1/t)$的速率上。
Nov, 2018
本文介绍了一种使用低秩SVD计算的简单启发式算法,使得标准一阶方法可以实现局部收敛,并可用于平滑凸规划的计算,以及带缩放梯度正则化和约束半正定矩阵上的计算。这些计算为机器学习,信号处理和统计学等领域中底秩矩阵恢复问题提供了实质性帮助。
Feb, 2019
本文提出了一种称为1-SFW的新的随机Frank-Wolfe算法,通过设计一种新颖的无偏动量估计器,实现了使用每次迭代的单个样品来优化,而无需仔细调整批量大小、步长、学习速率和其他复杂的超参数,并在随机凸优化、随机DR亚模拟最大化问题和一般的非凸设置中达到了最优收敛率。
Oct, 2019
本研究旨在提高解决基于最大后验马尔可夫随机场的LP松弛的问题的效率,并提出了一种基于面内Frank-Wolfe方向的高效实现方法,实验结果表明,该方法是当前某些问题类的最先进LP解决器。
Oct, 2020