本文提供了一个统一的框架来表征纯和近似差分隐私(DP)可学习性。我们使用图论语言来定义$mathcal{H}$的矛盾图$G$，并发现$G$的组合结构与在DP下学习$mathcal{H}$有着深刻的联系。

Apr, 2023

研究了多类别分类的通用速率问题，证明了所有假设类的最优速率（最多对数因子），基于有限和无限 Littlestone树和Danieley-Shalev-Shwartz-Littleston tree定义了DSL 树，并提供了更精确限制学习曲线的证明，具有PAC学习性。

Jul, 2023

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

Jul, 2023

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

Aug, 2023

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

Aug, 2023

在在线二元分类中，以苹果品尝反馈为基础，研究了部分反馈设置的经典问题，并从组合的角度研究了在线可学习性。通过证明Littlestone维度在此问题中紧密定量描述了苹果品尝的不确定性，解决了之前提出的开放问题。此外，引入了一个新的组合参数——有效宽度，严格量化了可实现设置中最小化最大期望错误的情况，进而建立了最小化最大期望错误的三分情况，即仅可能出现$\Theta(1)$、$\Theta(\sqrt{T})$或$\Theta(T)$的错误数。

Oct, 2023

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

Nov, 2023

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

Nov, 2023

近期的学习研究显示，学习问题的可学习性可能是不可判定的，或者与标准集合论的ZFC公理无关。此外，这些问题的可学习性可能不是有限特性：简单来说，通过检查问题的有限投影无法检测出可学习性。然而，学习理论在定义学习的维度时充斥着只考虑问题的有限限制的概念，即具有有限特性的性质。如何调和这些结果呢？具体而言，哪些学习问题容易受到逻辑不可判定性的影响，哪些问题可以用有限特性来解决？我们证明了具有测度损失的监督学习的困难可以通过有限特性来精确描述。尤其是我们证明了学习一个假设类的样本复杂度可以通过检查其有限投影来判断。对于广泛类别的适当损失函数的可实现和了解学习，我们证明了一个确切的紧致性结果：一个类别在具有给定样本复杂度时可以学习，仅当其所有有限投影也是如此。对于具有不适当损失函数的可实现学习，我们证明了样本复杂度的确切紧致性可能会失败，并提供了样本复杂度相差2倍的相匹配上下界。我们猜想对于了解学习的情况可能存在更大的差距。我们技术工作的核心是一个关于变量分配的紧致性结果，它在保持函数类别在目标值以下方面具有广泛的兴趣，该结果推广了霍尔（Hall）经典匹配定理，可能具有独立的兴趣。

Feb, 2024

根据合理的密码学假设，我们展示了一个概念类别，该类别允许在多项式时间内以多项式错误边界运行的在线学习器，但不存在计算效率高的差异隐私PAC学习器。

Feb, 2024