结合在线学习保证
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
本研究考虑在线学习算法在对抗环境中可以保证最坏情况下的后悔率,而在有利的随机环境下能够自适应地表现良好,并通过 Bernstein 条件量化随机环境的友好程度,证明了两种最近的算法自适应于随机环境的 Bernstein 参数,并证明这些算法在其各自的环境中都具有快速的期望和高概率率。
May, 2016
本文分析并评估了一种采用逐坐标调整学习率的在线梯度下降算法,该算法可被视为带有对角先决条件的批量梯度下降的在线版本。实验结果表明,该算法在大规模机器学习问题中与最先进的算法相竞争,并带来更强的遗憾边界。
Feb, 2010
介绍了一种基于 Lagrangian hedging 的在线算法(包括 regret-matching 和 hedge),通过引入 optimism 和 adaptive step size 对非对抗性问题进行了优化,并给出了相应的性能界限。
Jan, 2021
本文研究在线学习算法的稳定性及其对可学性(有限后悔)的影响,提出了一种称为 “前向后悔” 的新指标,用于测量在线学习算法的预测性能,证明了对于在线优化问题,稳定性等价于后悔有界,且有界前向后悔等价于有界后悔,在分析现有算法的可学性方面提供了一个简单的方法。
Nov, 2012
本研究探讨了一类广泛问题的在线可学性,并将其扩展到远超过外部遗憾的性能评估简单规范。我们的框架同时捕捉了其他著名规范,例如内部和一般 Phi 规范、学习使用非加性全局成本函数、Blackwell 的可挑战性、预测者的校准、自适应遗憾等。我们展示了在所有这些情况下的可学习性归因于控制相同的三个量:马田哥小定理收敛项、如果已知未来则能够表现良好的能力描述项、以及顺序 Rademacher 复杂性的概括,该复杂性在 (Rakhlin, Sridharan, Tewari, 2010) 中得到研究。由于我们直接研究问题的复杂性,而不是专注于高效算法的开发,因此我们能够改进和扩展许多已知结果,这些结果之前是通过算法构造推导出来的。
Nov, 2010
在线学习中最小化后悔,满足安全约束的广义元算法,估计未知的安全约束,并将在线学习预测转化为满足未知安全约束的预测,同时使用预测误差、各类模型的复杂度和新的复杂度度量来界定算法的后悔上限,同时提供了线性约束情况下的具体算法,使用比例变换平衡乐观探索和悲观约束满足,最小化根号 T 的后悔。
Mar, 2024
本研究开发了一种乐观的在线学习算法,不需要参数调整,在延迟反馈下具有最佳的后悔保证,支持实时气象预测,同时通过引入乐观提示来减少延迟造成的代价,并应用于气候子季节预测任务中,相对于现有模型具有低后悔。
Jun, 2021