【博士论文】基于信息论的泛化理论方法，274页pdf

在本论文中，我们研究了机器学习算法的分布内泛化，重点是建立严格的泛化误差上界。我们引入并分析了量化学习算法与训练数据之间依赖关系的信息论界，脱离了传统的复杂性基础方法。我们考虑了两类泛化保证：

-** 期望保证**。这些界衡量平均情况下的性能。这里，算法与数据之间的依赖关系通常由互信息或基于f-散度的其他信息度量来捕捉。虽然这些度量提供了直观的解释，但可能忽视算法假设类的几何结构。为了解决这一限制，我们引入了使用Wasserstein距离的界，Wasserstein距离结合了几何考虑，但数学上更复杂。此外，我们提出了一种结构化、系统的方法，以推导出捕捉算法与单个数据之间以及算法与数据子集之间依赖关系的界，这些界是基于已知其他数据条件下的。这类界提供了更深入的见解，我们通过应用它们推导随机梯度Langevin动力学算法的泛化误差界来证明这一点。

• PAC-Bayesian保证。这些界以高概率衡量性能水平。这里，算法与数据之间的依赖关系通常通过相对熵来衡量。我们建立了Seeger–Langford界和Catoni界之间的联系，揭示了前者由Gibbs后验优化。此外，我们为各种损失函数（包括有界范围、累积生成函数、矩或方差）的损失函数引入了新的、更紧的界。为此，我们引入了一种新的技术来优化概率陈述中的参数。

我们还研究了这些方法的局限性。我们提出了一个反例，其中大多数现有的（基于相对熵的）信息论界失效，而传统方法则不会。最后，我们探索了隐私与泛化之间的关系。我们展示了具有有限最大泄漏的算法可以泛化。此外，对于离散数据，我们推导出差分隐私算法的新界，这些界随着样本数量的增加而消失，从而保证即使在隐私参数不变的情况下也能泛化。这与文献中的先前界形成对比，后者需要隐私参数随着样本数量的增加而减小才能确保泛化。