在线学习中稳定性与后悔之间的相互作用
本研究探讨了一类广泛问题的在线可学性,并将其扩展到远超过外部遗憾的性能评估简单规范。我们的框架同时捕捉了其他著名规范,例如内部和一般Phi规范、学习使用非加性全局成本函数、Blackwell的可挑战性、预测者的校准、自适应遗憾等。我们展示了在所有这些情况下的可学习性归因于控制相同的三个量:马田哥小定理收敛项、如果已知未来则能够表现良好的能力描述项、以及顺序Rademacher复杂性的概括,该复杂性在(Rakhlin, Sridharan, Tewari, 2010)中得到研究。由于我们直接研究问题的复杂性,而不是专注于高效算法的开发,因此我们能够改进和扩展许多已知结果,这些结果之前是通过算法构造推导出来的。
Nov, 2010
研究表明,稳定性是一种可以用来量化学习算法的稳定程度的一般概念,是推动在线学习和减少后悔的关键。本文引入了在线稳定性,这是与均匀留一稳定性相关的一种稳定性条件,足以实现在线可学习性,并且说明了流行类的在线学习算法的一些理论。在特定的二分类设置中,稳定性条件是充分必要的。
Aug, 2011
研究使用镜像下降和熵正则化的方法在维度上实现对于一系列的一般化后的后悔情况的误差上界,其中包括了位移、自适应、折扣等等,并且得到了和权值分享方法的等价结果。研究同时提出了对于小的误差和参数的自适应调整等的改进。
Feb, 2012
该论文提出了当对手可以适应在线算法的动作时,标准遗憾定义变得不再有效, 定义了替代的政策遗憾概念,用于测量在线算法在适应性对手下的性能,并研究了在线赌徒问题的情况,表明任何赌徒算法都无法针对带有无界内存的适应性对手保证次线性的政策遗憾,但同时提出了将标准遗憾限制在次线性边界以下的任何赌徒算法转换为政策遗憾限制在次线性边界以下的算法的一般技术, 并将这一结果扩展到其他遗憾变体。
Jun, 2012
通过建立连续在线学习(COL)这种新的设置,连续轮次中在线损失函数的梯度会随着学习者的决策而连续变化,我们可以更完整地描述许多有趣的应用,特别地,证明了满足单调EPs(经济平衡问题)能够在COL中实现子线性的静态遗憾。 由此得出的启示是,我们提供了实现子线性动态遗憾的有效算法的条件,即使选择的损失在先验变化预算中没有适应性。 此外,我们还展示了一个从动态遗憾到静态遗憾和相关EP(经济平衡问题)收敛的COL之间的简化,从而允许我们分析许多现有算法的动态遗憾。
Feb, 2019
本文提出了一种简单的方法,可以将两个具有不同遗憾保证的无参数在线学习算法结合起来得到一个新的算法,其遗憾值是两个算法中的最小值。此外,作者还提出了一种基于该方法的黑盒子算法,可以生成乐观的在线学习算法,并提供无拘束设定下的第一个乐观遗憾保证。
Feb, 2019
本文研究了非稳态下的无投影在线学习,使用动态遗憾和自适应遗憾来衡量性能,提出了基于多个不同步长的BOGD_IP算法并行运行的算法,以及维护一组BOGD_IP算法并动态地组合它们的元算法,实验结果验证了理论分析。
May, 2023
本文针对具有强可观测无向反馈图的在线学习问题,在回报上下界方面进行了改进,并使用 FTRL 与 q-Tsallis 熵对结果进行了证明;同时扩展了该技术应用于时间变化图的情形,并提供了适用于所有 alpha>1 的改良下界。
May, 2023