UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

An Exact Characterization of the Generalization Error for the Gibbs Algorithm

Aminian, G; Bu, Y; Toni, L; Rodrigues, M; Wornell, G; (2021) An Exact Characterization of the Generalization Error for the Gibbs Algorithm. In: Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Advances in Neural Information Processing Systems (NeurIPS 2021) Green open access

[thumbnail of GE_Bayesian_Draft_NIPS_Version-11.pdf]
Preview
Text
GE_Bayesian_Draft_NIPS_Version-11.pdf - Published Version

Download (499kB) | Preview

Abstract

Various approaches have been developed to upper bound the generalization error of a supervised learning algorithm. 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 (a.k.a. Gibbs posterior) using symmetrized KL information between the input training samples and the output hypothesis. Our result can be applied to tighten existing expected generalization error and PAC-Bayesian bounds. Our approach is versatile, as it also characterizes the generalization error of the Gibbs algorithm with data-dependent regularizer and that of the Gibbs algorithm in the asymptotic regime, where it converges to the 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.

Type: Proceedings paper
Title: An Exact Characterization of the Generalization Error for the Gibbs Algorithm
Event: Conference on Neural Information Processing Systems 2021
Location: Sydney, Australia
Dates: 6th-14th December 2021
Open access status: An open access version is available from UCL Discovery
Publisher version: https://proceedings.neurips.cc/paper/2021/hash/445...
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher's terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Electronic and Electrical Eng
URI: https://discovery.ucl.ac.uk/id/eprint/10138209
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item