未知约束的在线学习
我们研究了经典的在线凸优化(OCO)框架的一种推广,通过考虑额外的长期对抗性约束。我们提出了一种元策略,能够同时达到亚线性的累积约束违规和亚线性的遗憾,通过将约束问题转化为递归构建的一系列代理代价函数的标准 OCO 问题的黑盒减缩。我们展示了通过使用任何享有标准数据相关遗憾上界的自适应 OCO 策略求解代理问题,可以达到最优性能界限。通过一种新的基于李雅普诺夫的证明技术,我们揭示了遗憾和某些顺序不等式之间的联系,通过一种新颖的分解结果。最后,我们强调了在在线多任务学习和网络控制问题中的应用。
Oct, 2023
在线凸优化(OCO)的未知约束设置是近年来备受关注的问题。本研究考虑了一种具有静态线性约束且玩家接收到噪声反馈并始终满足的问题版本。通过利用我们的乐观安全设计范例,我们提供了一种算法来解决该问题,其后悔值为 O (√T)。这比之前最佳后悔边界 O (T^2/3) 有所改进,并且只使用了更强烈一些的独立噪声和无意识对手的假设。然后,我们将该问题重新表述为随时间变化的随机线性约束下的 OCO 问题,并证明了我们的算法在这样的设置中具有相同的后悔保证,并且预期上不违反约束。这对于 OCO 在随时间变化的随机约束下的文献做出了贡献,其最先进的算法在约束为凸约束且玩家接收到完整反馈时具有 O (√T) 的后悔和 O (√T) 的违规。此外,我们提供了更加高效的算法版本,并通过与基准算法进行了数值实验比较。
Mar, 2024
我们提出了一种适用于未知特征生成过程的混合在线学习的、高效的预测方法,证明了该方法可在有限的 VC 类中实现具有次线性的遗憾上限,并在具有 α fat-shattering 维度的类中实现具有次线性的遗憾上限。此外,我们拓展了我们的结果到具有 K 个变化的分布转移场景,并为具有有限策略集合 H 和未知分布的 i.i.d. 生成的上下文以及敌对生成的成本的情境 K 臂赌博机建立了遗憾上限。
Jan, 2024
研究了如何适应信息获取成本昂贵的在线学习问题中平稳变化环境的影响;提出了一种算法用于处理标签有效预测的问题,并扩展到标签有效的赌博反馈和揭示行动部分监测游戏等领域,显著提高了现有算法的性能。
Oct, 2019
本文研究在线学习算法的稳定性及其对可学性(有限后悔)的影响,提出了一种称为 “前向后悔” 的新指标,用于测量在线学习算法的预测性能,证明了对于在线优化问题,稳定性等价于后悔有界,且有界前向后悔等价于有界后悔,在分析现有算法的可学性方面提供了一个简单的方法。
Nov, 2012
本文讨论在线线性优化问题,考虑可行操作集通过近似线性优化预言机具有 α 乘性逼近保证的情况,给出了新算法并提出了显著改进甚至多项式对数的预言机复杂度,同时得到了常数 c>0 的 alpha 遗憾界。
Sep, 2017
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024