多点反馈的安全在线凸优化
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸-凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
提出了一种适应性在线梯度下降算法,用于解决具有长期约束的在线凸优化问题,可以处理任意凸约束,该算法在损失和约束违规方面分别具有O(T^max{β,1−β})和O(T^(1−β/2))的累积遗憾界,优于Mahdavi等(2012年)最好的已知累积遗憾界,该算法的性能已在实践中得到验证。
Dec, 2015
我们提出了一种在线凸优化算法(RescaledExp),该算法在无约束设置下实现了最优的后悔,并没有先验知识任何损失函数的界限。我们证明了一个下界,说明现有算法在损失函数需要已知界限的情况下与不需要这种知识的任何算法之间存在指数分离。RescaledExp在迭代次数方面与这个下界是一致的。RescaledExp自然无超参数,并且我们通过实验证明它可以匹配需要超参数优化的之前的优化算法。
Mar, 2017
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为T的序列上,通过总共T次对LOO的调用,相对于损失函数产生的后悔为$ ilde{O}(T^{3/4})$,对于约束的违反是$O(T^{7/8})$(忽略除了$T$以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为$T$的函数)。
Feb, 2024
在线凸优化(OCO)的未知约束设置是近年来备受关注的问题。本研究考虑了一种具有静态线性约束且玩家接收到噪声反馈并始终满足的问题版本。通过利用我们的乐观安全设计范例,我们提供了一种算法来解决该问题,其后悔值为O(√T)。这比之前最佳后悔边界O(T^2/3)有所改进,并且只使用了更强烈一些的独立噪声和无意识对手的假设。然后,我们将该问题重新表述为随时间变化的随机线性约束下的OCO问题,并证明了我们的算法在这样的设置中具有相同的后悔保证,并且预期上不违反约束。这对于OCO在随时间变化的随机约束下的文献做出了贡献,其最先进的算法在约束为凸约束且玩家接收到完整反馈时具有O(√T)的后悔和O(√T)的违规。此外,我们提供了更加高效的算法版本,并通过与基准算法进行了数值实验比较。
Mar, 2024
有关在线凸优化和约束在线凸优化的一篇研究论文,证明了一个在线策略可以同时实现 O(√T) 的遗憾和 θ̃(√T) 的累积约束违规,通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合,达到了这一结果。
May, 2024