Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL information
This work addresses a fundamental issue in learning theory for researchers and practitioners by offering a more precise theoretical guarantee, though it is incremental as it builds on existing approaches.
The paper tackles the problem of bounding the generalization error of supervised learning algorithms by providing an exact characterization of the expected generalization error for the Gibbs algorithm using symmetrized KL information, which can be applied to tighten existing bounds.
Bounding the generalization error of a supervised learning algorithm is one of the most important problems in learning theory, and various approaches have been developed. However, existing bounds are often loose and lack of guarantees. As a result, they may fail to characterize the exact generalization ability of a learning algorithm. Our main contribution is an exact characterization of the expected generalization error of the well-known Gibbs algorithm in terms of symmetrized KL information between the input training samples and the output hypothesis. Such a result can be applied to tighten existing expected generalization error bound. Our analysis provides more insight on the fundamental role the symmetrized KL information plays in controlling the generalization error of the Gibbs algorithm.