一种高效的在线凸优化内点方法
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
提出了一种适应性在线梯度下降算法,用于解决具有长期约束的在线凸优化问题,可以处理任意凸约束,该算法在损失和约束违规方面分别具有 O (T^max {β,1−β}) 和 O (T^(1−β/2)) 的累积遗憾界,优于 Mahdavi 等(2012 年)最好的已知累积遗憾界,该算法的性能已在实践中得到验证。
Dec, 2015
本文针对带有随机反馈的在线凸优化问题(称为 bandit convex optimization),通过将椭球法应用于在线学习,给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法,并引入了离散凸几何中的新工具。
Mar, 2016
探讨在线变体的 Frank-Wolfe 算法,包括简单迭代更新和非自适应步长规则,研究凸和非凸损失的多个新结果,并基于对随机 Frank-Wolfe 算法的改进分析得出在强凸随机成本时的遗憾界和任何时刻的最优性为 O (log^3T/T) 和 O (log^2T/T) ; 此外,该在线算法即使在损失非凸的情况下也能收敛,以速率 O (1/T 的平方根) 找到时变 / 随机损失的稳态点。
Oct, 2015
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024
本文讨论在线线性优化问题,考虑可行操作集通过近似线性优化预言机具有 α 乘性逼近保证的情况,给出了新算法并提出了显著改进甚至多项式对数的预言机复杂度,同时得到了常数 c>0 的 alpha 遗憾界。
Sep, 2017
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018