Information-Theoretic Characterizations of Generalization Error for the Gibbs Algorithm
Information-Theoretic Characterizations of Generalization Error for the Gibbs Algorithm
复制标题
DOI：
10.1109/tit.2023.3329617
复制
发表时间：
2022-10
影响因子：
2.5
通讯作者：
Gholamali Aminian;Yuheng Bu;L. Toni;M. Rodrigues;G. Wornell
中科院分区：
文献类型：
--
作者：
Gholamali Aminian;Yuheng Bu;L. Toni;M. Rodrigues;G. Wornell
已经开发了各种方法来上界监督学习算法的泛化误差。然而，现有的界限往往是松散的，甚至是空洞的，在实践中评估。因此，它们可能无法表征学习算法的精确泛化能力。我们的主要贡献是精确刻画了著名的吉布斯算法（a.k.a. Gibbs后验）使用不同的信息度量，特别是输入训练样本和输出假设之间的对称化KL信息。我们的结果可以应用于收紧现有的预期泛化误差和PAC-Bayesian边界。我们的信息理论的方法是通用的，因为它也具有数据相关的正则化和吉布斯算法的渐近制度，在那里它收敛到标准的经验风险最小化算法的吉布斯算法的泛化误差的特点。特别相关的，我们的研究结果突出了对称化KL信息在控制吉布斯算法的泛化误差中所起的作用。
Various approaches have been developed to upper bound the generalization error of a supervised learning algorithm. However, existing bounds are often loose and even vacuous when evaluated in practice. As a result, they may fail to characterize the exact generalization ability of a learning algorithm. Our main contributions are exact characterizations of the expected generalization error of the well-known Gibbs algorithm (a.k.a. Gibbs posterior) using different information measures, in particular, the symmetrized KL information between the input training samples and the output hypothesis. Our result can be applied to tighten existing expected generalization errors and PAC-Bayesian bounds. Our information-theoretic approach is versatile, as it also characterizes the generalization error of the Gibbs algorithm with a data-dependent regularizer and that of the Gibbs algorithm in the asymptotic regime, where it converges to the standard empirical risk minimization algorithm. Of particular relevance, our results highlight the role the symmetrized KL information plays in controlling the generalization error of the Gibbs algorithm.