本文通过对有限最大概念类的压缩的几何系统性研究，证明了Piecewise-Linear超平面排列能够通过等高线法压缩任意有限最大类，从而证明了Kuzmin和Warmuth的猜想，并说明了一些d-最大化类无法嵌入到VC维度为d+k的任何最大类中。

Nov, 2009

本研究针对极端分类，基于Sandwich定理构建了一个样本压缩方案，其尺寸等于其VC维度，并提出了一些有关极端分类的组合结构和无标签压缩方案存在性的问题。

May, 2015

本文研究了样本压缩方案与统计学习之间的关系，探究了学习能力与可压缩性之间的等价性，并在多类别分类问题中研究了统计学习理论。作者证明了在零/一损失分类的情况下，可学习性等价于对数样本大小的压缩，并且一致收敛意味着恒定大小的压缩。作者还探究了在Vapnik的一般学习设置下压缩能力与学习能力的等价性，并给出了一些在多类别分类问题中的应用。

Oct, 2016

该论文研究了机器学习中的组合概念和立体几何领域的拓扑概念之间的联系，并引入了VC维和样本压缩方案等概念，提出了一些新的构造和结论。

Dec, 2018

本文基于两种算法（一个可直接恢复出真实标签，另一个则可以在标注标签子集的情况下可靠地推断出大型实例集的真实标签）从而开发利用配对比较查询可在指数级减少标签复杂性的方法，用于众包PAC学习阈值函数的设定，并在保留整体查询复杂性和运行时间的同时，可以成功地处理来自可能反对者的注释。

Nov, 2020

提出了一种新的学习算法，利用基于Vapnik维度的泛化界限定了算法的误差上界，并根据学习任务的特性使用一种依赖于尺度的维度定义，获得了新的打包数边界和样本复杂度上界，进而得到了一系列关于学习性质和可学性的充分条件和必要条件。

Apr, 2023

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

Aug, 2023

使用并改编拓扑学中的Borsuk-Ulam定理来推导对列表可复制和全局稳定学习算法的限制，在组合学和拓扑学中进一步展示了我们方法的适用性，并发现在无初始假设能力类设置下，列表可复制和全局稳定学习均不可能。

Nov, 2023

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

Nov, 2023

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

Jul, 2024