研究了在所有可计算标签函数中的学习，证明了这是可能的，但也表明了无法独立于分布地限制样本复杂度，这完全是由于学习算法可计算的要求，而不是统计问题的本性。

Jun, 2008

研究多类预测中的样本复杂度，并提出了设计ERM学习器的原则以及使用这些原则来证明对称的多类假说类的样本复杂度的紧束缚定理。此外，通过对Littlestone维度的新概括，提供了在线背景和强盗问题中多类学习的错误和遗憾界限的描述。

Aug, 2013

本文证明了多分类问题的效率最优解必须是不正确的，并提出了一种基于generalized linear classifiers 的效率最优解的算法。

May, 2014

本文提出采样压缩序列作为一种学习算法的抽象形式，并回答了问题：每个概念类别C具有VC维度d的序列都具有指数大小的采样压缩序列，这得益于对VC维下二进制矩阵的逼近极小现象。

Mar, 2015

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

Oct, 2016

本文研究了一个基于样本压缩界限的多类学习算法的贝叶斯一致性，并证明了在度量空间有限两倍维度的情况下，该算法是强贝叶斯一致的，甚至在某些无限维情况下也是连贯的，这是一项有趣的发现，当前存在几个值得研究的问题。

May, 2017

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

Jul, 2023

设计高效的统计监督学习算法的一大挑战是找到不仅在可用训练样本上表现良好，也在未知数据上表现良好的表示方法。本文建立了一个压缩性框架，通过标签或潜在变量（表示）的“最小描述长度”（MDL）来推导表示学习算法的泛化误差的上界。通过与固定先验的训练集和测试集的表示（或标签）分布之间的“多字母”相对熵，而不是通常认为反映算法泛化能力的编码器输入和表示之间的互信息，建立了新的界限。本文的压缩性方法是信息论的，基于Blum-Langford的PAC-MDL界限，并引入了两个关键因素：块编码和有损压缩。最后，本文通过引入新的数据依赖性先验，部分利用了理论结果。数值模拟展示了选择良好的先验与IB中使用的经典先验相比的优势。

Feb, 2024

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

Feb, 2024

探讨列表学习在PAC学习中的适用性，研究了与泛化相关的经典原理，特别侧重于一致收敛和样本压缩对于学习可行性的影响，并证明了一致收敛在列表PAC学习中与可学习性等价，同时发现了样本压缩的一些令人吃惊的结果。

Mar, 2024