研究Expectation Maximization问题的可学习性和采样复杂度，特别是在布尔函数情形下的研究以及其与集合论关系的探讨，结论表明该问题的可学习性与集合论ZFC公理无关。

Nov, 2017

提出了一个将差分隐私统计估计转化为无差分隐私的框架，并给出了用于学习高斯分布和鲁棒学习高斯分布的多项式时间差分隐私算法，该方法中学习高斯分布的样本复杂度和已知的信息论样本复杂度的上限相匹配，并且还证明了相似的结果，其中鲁棒学习高斯分布的样本复杂度更低。

Nov, 2021

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

Apr, 2023

本文提出了一种参数化 PAC 学习理论，通过该理论可对 CNF、DNF 和图形学习等问题的可行性边界进行更精细的界定，并发展了机器学习领域的参数化固定参数学习的概念。

Apr, 2023

论文研究了稀疏度- d 多项式阈值函数的属性稀疏特性和机器学习的 PAC 学习方法，提出了一种新算法，使用仅限 Frobenius 范数来验证好的近似或识别受污染样本的杂音过滤器。

Jun, 2023

我们研究了学习从标准的d维高斯度量中绘制的带有标签的示例的k个ReLU激活的线性组合的问题。我们发现了一个简化的一阶段版本的算法，其运行时间只有(d/ε)^O(k^2)。

Jul, 2023

该研究调查了深度学习在计算统计差距存在的情况下的算法设计选择。通过考虑离线稀疏奇偶学习，一种多层感知器的梯度训练的统计查询下界，我们展示了稀疏初始化和增加网络宽度在样本效率方面的显著改进，以及合成稀疏奇偶任务对于需要轴对齐特征学习的真实问题的代理用途。

Sep, 2023

对于每个常数q，我们证明了在样本流上进行q次遍历的任何奇偶性学习算法都需要Ω(n2)的内存大小或至少需要2Ω(n)个样本数量，并且这是对于任何q≥3的第一个非平凡的下界。与先前的工作类似，我们的结果适用于具有许多近似正交概念的任何学习问题。我们还通过上界来补充下界，表明带有q次遍历的奇偶性学习可以使用O(n2/ log q)的内存高效地完成。

Oct, 2023

从有限的点值样本学习多变量平滑目标函数的近似是科学计算和计算科学工程中的一个重要任务。本文调查了近年来在此方面取得的重大进展，描述了来自参数模型和计算不确定性量化的当代动机，无穷维巴拿赫空值全纯函数类，这些类的有限数据可学习性的基本限制，以及从有限数据高效学习此类函数的稀疏多项式和深度神经网络方法。针对深度学习的实际性能与深度神经网络的近似理论之间的差距，我们发展了实际存在理论的主题，宣称存在维度无关的 DNN 结构和训练策略，以证明在训练数据量方面具有可证明近似最优的泛化误差。

Apr, 2024

研究梯度算法在学习稀疏函数（juntas）时的复杂性。引入了一种称为可微学习查询（DLQ）的统计查询类型，用于建模指定损失相对于任意模型的梯度查询。提供了对于在通用产品分布上学习稀疏函数的DLQ查询复杂性的紧密刻画。DLQ查询复杂性关键取决于损失函数。对于平方损失，DLQ与相关统计查询（CSQ）的复杂性相匹配——可能比SQ复杂得多。但对于其他简单损失函数，包括l1损失，DLQ总是实现与SQ相同的复杂性。还提供了DLQ确实可以捕捉（随机）梯度下降学习的证据，通过展示其正确描述均场区域和线性放缩中两层神经网络学习的复杂性。

Jul, 2024