Nov, 2010

在线学习：超越遗憾

PDF
TL;DR本研究探讨了一类广泛问题的在线可学性，并将其扩展到远超过外部遗憾的性能评估简单规范。我们的框架同时捕捉了其他著名规范，例如内部和一般 Phi 规范、学习使用非加性全局成本函数、Blackwell 的可挑战性、预测者的校准、自适应遗憾等。我们展示了在所有这些情况下的可学习性归因于控制相同的三个量：马田哥小定理收敛项、如果已知未来则能够表现良好的能力描述项、以及顺序 Rademacher 复杂性的概括，该复杂性在 (Rakhlin, Sridharan, Tewari, 2010) 中得到研究。由于我们直接研究问题的复杂性，而不是专注于高效算法的开发，因此我们能够改进和扩展许多已知结果，这些结果之前是通过算法构造推导出来的。
online learnabilityperformance measureregretmartingale convergencerademacher complexity
发现论文，激发创造
  • 在线学习中稳定性与后悔之间的相互作用

    本文研究在线学习算法的稳定性及其对可学性（有限后悔）的影响，提出了一种称为 “前向后悔” 的新指标，用于测量在线学习算法的预测性能，证明了对于在线优化问题，稳定性等价于后悔有界，且有界前向后悔等价于有界后悔，在分析现有算法的可学性方面提供了一个简单的方法。

    Nov, 2012

  • 非凸在线学习中的本地遗憾

    本文讨论了基于梯度的在线学习算法来预测非凸模型序列的结果，提出了一种比标准 regret 更可解释的新定义来评估预测问题的性能并给出了该定义的边界分析。

    Nov, 2018

  • 在线到 PAC 转换：通过遗憾分析获得泛化界

    本文提出了从在线学习的角度推导统计学习算法的泛化界限的新框架，建立在线学习算法与统计学习算法之间的联系，通过构造一种在线学习游戏来实现该框架并得到多种泛化保证。

    May, 2023

  • 在线学习众多量子对象

    通过应用正则化跟随领导算法，在学习正半定矩阵的通用子集和其他量子物体时，证明了一个次线性的遗憾界，并建立了在量子信息理论中有用的各种矩阵分析结果。

    Jun, 2024

  • 重复博弈中的政策后悔

    本文重新审视了在线学习中的策略后悔问题，表明在某些情况下，外部后悔和策略后悔是不兼容的，而在自利智能体领域，如果使用某些算法，则可以保证外部后悔和策略后悔都是有利的。本文还介绍了一个新的均衡概念 —— 策略均衡，并表明粗略相关均衡是策略均衡的一个真子集。

    Nov, 2018

  • 终身学习的遗憾界限

    本文提出了一种在线的迁移学习方法，通过对任务内算法中底层的数据表示进行改进，实现跨任务信息转移，同时证明了该方法拥有良好的成本控制性质，并讨论了其在字典学习和有限预测器中的应用。

    Oct, 2016

  • 未知约束的在线学习

    在线学习中最小化后悔，满足安全约束的广义元算法，估计未知的安全约束，并将在线学习预测转化为满足未知安全约束的预测，同时使用预测误差、各类模型的复杂度和新的复杂度度量来界定算法的后悔上限，同时提供了线性约束情况下的具体算法，使用比例变换平衡乐观探索和悲观约束满足，最小化根号 T 的后悔。

    Mar, 2024

  • 一种连续时间的在线优化方法

    研究一种基于连续时间的在线优化策略族，证明其能够达到无遗憾学习。从传统的离散时间角度来看，这种方法可导出大量离散时间算法（包括一些经典遗憾分析算法）的无遗憾性质，并统一了许多经典的遗憾上界，得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。

    Jan, 2014

  • 结合在线学习保证

    本文提出了一种简单的方法，可以将两个具有不同遗憾保证的无参数在线学习算法结合起来得到一个新的算法，其遗憾值是两个算法中的最小值。此外，作者还提出了一种基于该方法的黑盒子算法，可以生成乐观的在线学习算法，并提供无拘束设定下的第一个乐观遗憾保证。

    Feb, 2019

  • 未知马尔可夫博弈中的在线学习

    本文研究未知马尔可夫博弈的在线学习问题以及提出了一种算法，实现了与后记中的最佳响应之间亚线性的最小化值的竞争。

    Oct, 2020