论文标题
通过信息密度和条件信息密度的概括界定
Generalization Bounds via Information Density and Conditional Information Density
论文作者
论文摘要
我们提出了一种基于指数不平等的一般方法，以在随机学习算法的概括误差上得出界限。使用这种方法，我们为PAC-Bayesian和单绘图场景提供了平均概括误差以及其尾部概率的界限。具体而言，对于高出高斯损失功能的情况，我们获得了依赖训练数据和输出假设之间信息密度的新颖界限。当适当地削弱时，这些界限恢复了文献中可用的许多信息理论界限。我们还将提出的指数质量方法扩展到Steinke和Zakynthinou（2020）最近引入的设置，其中学习算法取决于可用培训数据的随机选择子集。对于此设置，我们在输出假设与随机变量之间的条件信息密度方面提出了有限损耗函数的界限，鉴于所有训练数据，确定子集选择的随机变量。通过我们的方法，我们恢复了Steinke和Zakynthinou（2020）提出的平均概括，并将其扩展到Pac-bayesian和单绘图场景。对于单绘图场景，我们还可以从条件$α$ - 流浪性信息和条件最大泄漏方面获得新的边界。
We present a general approach, based on exponential inequalities, to derive bounds on the generalization error of randomized learning algorithms. Using this approach, we provide bounds on the average generalization error as well as bounds on its tail probability, for both the PAC-Bayesian and single-draw scenarios. Specifically, for the case of sub-Gaussian loss functions, we obtain novel bounds that depend on the information density between the training data and the output hypothesis. When suitably weakened, these bounds recover many of the information-theoretic bounds available in the literature. We also extend the proposed exponential-inequality approach to the setting recently introduced by Steinke and Zakynthinou (2020), where the learning algorithm depends on a randomly selected subset of the available training data. For this setup, we present bounds for bounded loss functions in terms of the conditional information density between the output hypothesis and the random variable determining the subset choice, given all training data. Through our approach, we recover the average generalization bound presented by Steinke and Zakynthinou (2020) and extend it to the PAC-Bayesian and single-draw scenarios. For the single-draw scenario, we also obtain novel bounds in terms of the conditional $α$-mutual information and the conditional maximal leakage.
