在线凸优化下的在线次模最大化
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
我们研究了经典的在线凸优化(OCO)框架的一种推广,通过考虑额外的长期对抗性约束。我们提出了一种元策略,能够同时达到亚线性的累积约束违规和亚线性的遗憾,通过将约束问题转化为递归构建的一系列代理代价函数的标准 OCO 问题的黑盒减缩。我们展示了通过使用任何享有标准数据相关遗憾上界的自适应 OCO 策略求解代理问题,可以达到最优性能界限。通过一种新的基于李雅普诺夫的证明技术,我们揭示了遗憾和某些顺序不等式之间的联系,通过一种新颖的分解结果。最后,我们强调了在在线多任务学习和网络控制问题中的应用。
Oct, 2023
有关在线凸优化和约束在线凸优化的一篇研究论文,证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规,通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合,达到了这一结果。
May, 2024
在线决策问题存在非线性组合目标函数,现有框架局限于子模函数定义域为单位超立方体子集,为克服这一限制,本文引入在线 L 自然凸最小化概念,并提出有效算法以在完全信息和强盗设置下最小化在线 L 自然凸函数,分析算法的遗憾以及演示在线 L 自然凸最小化的实际应用示例。
Apr, 2024
本文研究了 DR - 次模连续函数在最大化过程中的基本问题,并在凸集合的不同类型下提出了一系列在线算法,用于最小化在线非单调 DR - 次模函数。在实验中表现良好并为机器学习领域中有关问题提供了新的解决方案。
Sep, 2019
本文提出了一个新的在线凸优化框架,能够利用过去的决策历史对当前损失进行建模,并引入了 “p 有效内存容量” 来量化过去决策对当前损失的最大影响。在此框架下,证明了一些政策遗憾的较好上界,并展示了该框架对于各种在线学习任务的适用性。
Oct, 2022
本研究考虑了在线连续 DR-submodular 最大化问题,采用了随机线性长期约束,并提出了在线 Lagrangian Frank-Wolfe(OLFW)算法来解决这类问题,得到了期望和高概率下的次线性后悔上限和次线性约束违规上限。
May, 2020
本研究以连续贪心算法为基础,研究了具有一般性骨架约束的随机子模最大化问题,主要应用于在线学习,团队形成,设施位置,影响最大化,主动学习和感知目标函数。实验表明,使用多项式梯度估计代替样本估计,可有效减少随机性并缩短执行时间。
Mar, 2023