时变约束在线凸优化
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
提出了一种适应性在线梯度下降算法,用于解决具有长期约束的在线凸优化问题,可以处理任意凸约束,该算法在损失和约束违规方面分别具有 O (T^max {β,1−β}) 和 O (T^(1−β/2)) 的累积遗憾界,优于 Mahdavi 等(2012 年)最好的已知累积遗憾界,该算法的性能已在实践中得到验证。
Dec, 2015
该研究提出了一种在线凸优化算法,其可以处理特定类型的累计平方约束违规问题,以及为凸目标导出了另类的后悔边界,并针对强凸目标提出了改进的后悔边界,并在数值实验中说明了该算法的效果。
Feb, 2018
我们研究了一类带有长期约束的在线度量问题,该问题涉及在线玩家在度量空间中进行决策以同时最小化击中成本和度量确定的切换成本。我们设计了特定实例的最优竞争性和学习增强算法,并进一步在数值实验中证明了我们提出的算法的良好性能。
Feb, 2024
本文提出了一种使用对数障碍惩罚函数的内点法解决具有时变目标和约束函数的凸优化问题的方法,并提出了一种能够跟踪(时变)最优解的连续时间动力系统来确保其全局渐近收敛于指数速度的最优解。
Aug, 2016
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
在线凸优化(OCO)的未知约束设置是近年来备受关注的问题。本研究考虑了一种具有静态线性约束且玩家接收到噪声反馈并始终满足的问题版本。通过利用我们的乐观安全设计范例,我们提供了一种算法来解决该问题,其后悔值为 O (√T)。这比之前最佳后悔边界 O (T^2/3) 有所改进,并且只使用了更强烈一些的独立噪声和无意识对手的假设。然后,我们将该问题重新表述为随时间变化的随机线性约束下的 OCO 问题,并证明了我们的算法在这样的设置中具有相同的后悔保证,并且预期上不违反约束。这对于 OCO 在随时间变化的随机约束下的文献做出了贡献,其最先进的算法在约束为凸约束且玩家接收到完整反馈时具有 O (√T) 的后悔和 O (√T) 的违规。此外,我们提供了更加高效的算法版本,并通过与基准算法进行了数值实验比较。
Mar, 2024