无光滑,无投影的带函数约束优化
我们介绍了 MOPES 方法和 MOLES 方法,用于在具有昂贵的投影和线性最小化查询的情况下,高效地寻找在强凸约束集上的次优解。 MOPES 方法通过 Moreau-Yosida 平滑和加速的一阶方案结合,并通过仅需 O (ε ^ -1) 投影查询和最少的 O (ε ^ -2) 函数值查询即可找到次优解。 MOLES 方法仅具有线性最小化查询,但需要更多的函数值查询。
Oct, 2020
该论文提出了一种新颖的元 Frank-Wolfe 算法及其简化版 One-Shot-Frank-Wolfe,用于对在线优化进行全局和子模最优解的快速求解。其方法基于梯度下降实现,通过随机梯度估算和孪生逼近算法来降低收敛难度。
Feb, 2018
本文介绍了一种零阶 Frank-Wolfe 算法,用于解决约束随机优化问题,该算法与基本 Frank-Wolfe 算法同样无需投影,且不需要计算梯度,可收敛于凸平滑约束下的优化目标函数。同时,本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数,本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4}),并在黑盒优化设置上进行实验,证明了其效果。
Oct, 2018
本文中我们考虑在闭凸子集上最小化一个非光滑非凸的目标函数 $f (x)$,同时满足附加的非光滑非凸约束 $c (x) = 0$。我们开发了一个统一的框架来发展基于 Lagrangian 的方法,在每次迭代中通过某些子梯度方法对原始变量进行单步更新。这些子梯度方法被 “嵌入” 到我们的框架中,以黑盒更新原始变量的方式加以合并。我们证明了在温和条件下,我们提出的框架继承了这些嵌入子梯度方法的全局收敛性保证。此外,我们证明了我们的框架可以扩展到解决具有期望约束的约束优化问题。基于我们提出的框架,我们展示了一系列现有的随机子梯度方法,包括 proximal SGD、proximal momentum SGD 和 proximal ADAM,可以嵌入到基于 Lagrangian 的方法中。对深度学习任务的初步数值实验表明,我们提出的框架可以为非凸非光滑约束优化问题提供高效的 Lagrangian-based 方法变体,并具有收敛性保证。
Apr, 2024
该论文研究了随机受限多层优化的无投影算法。介绍了新的无投影方差缩减算法并分析了它们在不同条件下的复杂性,包括梯度映射和 Frank-Wolfe 间隙准则,并通过分阶段适应进一步获得了凸函数和强凸函数的复杂性,数值实验证明了该方法的有效性。
Jun, 2024
本文介绍了一种基于随机投影次梯度方法的弱凸(即均匀逼近正则)非光滑非凸函数的算法,并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度;这似乎是第一个针对弱凸函数类的随机次(或确定性)梯度法的收敛速度分析。
Jul, 2017
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
本文提出了一种用于解决非凸、非光滑优化问题的近端次梯度方法(Prox-SubGrad),并通过建立一些子梯度上界及其关系,简化和统一了收敛速度的证明方案,同时还提出了一些新的随机子梯度上界条件,并为随机子梯度方法(Sto-SubGrad)建立了收敛和迭代复杂度。
Aug, 2023
本研究将众所周知的 BFGS 拟牛顿方法及其内存限制变种 LBFGS 扩展到非平滑凸目标的优化,提出了 subBFGS 算法,其全局收敛,并使用其记忆限制变体(subLBFGS)来最小化 L2 正则化风险并开发了新的多类和多标签设置下的准确搜索算法。
Apr, 2008