Nov, 2023

迁移式在线学习的三分论

HTML
PDF
TL;DR我们对Ben-David、Kushilevitz和Mansour (1997)的可逆在线学习设置中学习者错误的数量提出新的上界和下界。定性地，我们证明了一个三分法，即随着n的增长，学习者所犯错误的最小数量只能取三个明确定义的值之一：n，Θ(log(n))或Θ(1)。此外，这种行为是由VC维度和Littlestone维度的组合确定的。定量地，我们展示了各种将错误数量与众所周知的组合维度相关联的界限。特别地，我们将Θ(1)情况下的常数的已知下界从Ω(√log(d))改进为Ω(log(d))，其中d是Littlestone维度。最后，我们将我们的结果扩展到多类分类和不可知设置。
发现论文，激发创造
  • 带集合值反馈的在线学习

    本文研究一种在线多类分类变体，在这种模型中，学习器预测一个单一标签，但接收一个标签的集合作为反馈，我们证明在这种情况下，确定性和随机化的在线可学习性不等价，并且给出两个新的组合维度，称为集合维度和度量破灭维度，分别紧密描述了实现情况下的确定性和随机化的在线可学习性，此外，我们还展示了度量破碎维度紧密描述了模糊情况下的在线可学习性，最后，我们展示了在线多标签排名和在线多标签分类是我们提出的在线学习框架的具体实例。

    Jun, 2023

  • 有界损失在线学习游戏的组合特征化

    我们研究了关于任意但有界损失函数的假设类的在线可学习性。我们给出了一种新的与规模敏感的组合维数相关的步进最小二维，并证明它对在线可学习性提供了紧密的定量刻画。作为应用，我们首次对两种自然学习设置进行了在线可学习性的定量刻画：向量值回归和多标签分类。

    Jul, 2023

  • 多分类问题下的在线可学习性研究

    我们研究基于强化学习反馈的在线多类别分类。我们扩展了(daniely2013price)的结果，通过展示在标签空间无限的情况下，强化学习小石维度的有限性是在线多类别可学习性的必要和充分条件。我们的结果补充了(hanneke2023multiclass)的最近工作，他们证明了在标签空间无限的情况下小石维度描述了全信息设置中的在线多类别可学习性。

    Aug, 2023

  • 具有一致性预言机的简单在线学习

    在在线学习中，我们考虑了一种只能通过一致性预测器来访问类的学习算法的模型。我们提出了一种新的算法，最多会犯O(256^d)个错误。同时观察到在这个模型中不存在一种算法能在最多犯2^(d+1)-2个错误。

    Aug, 2023

  • 非均匀在线学习：走向理解归纳

    物理学家和归纳推理的非均匀在线学习的作用和限制，以及与在线学习理论和Littlestone类的关系。

    Nov, 2023

  • 在线多类别分类的强化学习反馈算法：变体和权衡

    多类分类中，我们研究了在对抗性在线环境中依赖强化学习反馈与完全信息之间的差异对最佳错误界限的影响，提供了几乎严格的答案。我们还研究了随机化学习者与确定性学习者之间以及适应性对手与无意识对手之间在强化学习反馈环境下的差距，并与完全信息场景进行了对比。此外，我们的结果表明，在某些情况下，最佳随机化错误界限接近于其确定性对应界限的平方根。

    Feb, 2024

  • 自主学习的维度

    自主学习复杂性主题是在线学习理论社区自上世纪90年代初以来一直关注的重要问题。本文研究了二进制和多类别设置中的自主学习复杂性，并开发了一个维度，即$SDdim$，精确地对任何概念类别的自主学习错误界进行了表征。

    Feb, 2024

  • 关于差分隐私在线学习中错误增长的下界透视

    对差分隐私在线学习算法提供了下界，表明广泛类别的（ε, δ）-差分隐私在线算法—当满足log T≤O(1/δ)时，算法产生的错误数量的期望呈Ω(log(T/δ))增长，与非隐私在线学习不同，其中错误数量与T无关。据我们所知，这是首次为差分隐私在线学习确定下界的结果，并在一定程度上解决了Sanyal和Ramponi（2022）中的疑问。

    Feb, 2024

  • 树的拉姆齐定理及一般的“私人学习等于在线学习”的定理

    对于一般的分类任务，差分隐私可学习性意味着在线学习性。本研究通过建立树的数个拉姆齐型定理，直接对Littlestone树进行推理，而不依赖于阈值，给出了对这些问题肯定的回答。

    Jul, 2024

  • 战略Littlestone维度: 改进的在线战略分类界限

    在线二分类问题中，我们研究了策略性代理可以修改可观测特征以实现积极分类的问题。我们通过特征空间上的有向图模拟可行的操纵集，并假设学习者仅观察到修改的特征而非原始特征。我们引入了战略Littlestone维度，一种新的组合测量方法，捕捉了假设类和操纵图的联合复杂性。我们证明它刻画了可实现设置中确定性学习算法的实例最优错误界限。通过一种精细的从不观察代理的原始特征带来的额外挑战的可知设置到可实现设置的减少，我们在可知设置中实现了改进的遗憾。最后，我们放宽了学习者知道操纵图的假设，而是假设他们的知识由图族来表示。我们得出了在所有代理按照图族中的同一图进行操纵的可实现设置和选择性地建模为图系的对抗选择性设置中的遗憾界限。

    Jul, 2024