Chained generalisation bounds

Eugenio Clerico, Amitis Shidani, George Deligiannidis, Arnaud Doucet
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:4212-4257, 2022.

Abstract

This work discusses how to derive upper bounds for the expected generalisation error of supervised learning algorithms by means of the chaining technique. By developing a general theoretical framework, we establish a duality between generalisation bounds based on the regularity of the loss function, and their chained counterparts, which can be obtained by lifting the regularity assumption from the loss onto its gradient. This allows us to re-derive the chaining mutual information bound from the literature, and to obtain novel chained information-theoretic generalisation bounds, based on the Wasserstein distance and other probability metrics. We show on some toy examples that the chained generalisation bound can be significantly tighter than its standard counterpart, particularly when the distribution of the hypotheses selected by the algorithm is very concentrated.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-clerico22a, title = {Chained generalisation bounds}, author = {Clerico, Eugenio and Shidani, Amitis and Deligiannidis, George and Doucet, Arnaud}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {4212--4257}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/clerico22a/clerico22a.pdf}, url = {https://proceedings.mlr.press/v178/clerico22a.html}, abstract = {This work discusses how to derive upper bounds for the expected generalisation error of supervised learning algorithms by means of the chaining technique. By developing a general theoretical framework, we establish a duality between generalisation bounds based on the regularity of the loss function, and their chained counterparts, which can be obtained by lifting the regularity assumption from the loss onto its gradient. This allows us to re-derive the chaining mutual information bound from the literature, and to obtain novel chained information-theoretic generalisation bounds, based on the Wasserstein distance and other probability metrics. We show on some toy examples that the chained generalisation bound can be significantly tighter than its standard counterpart, particularly when the distribution of the hypotheses selected by the algorithm is very concentrated.} }
Endnote
%0 Conference Paper %T Chained generalisation bounds %A Eugenio Clerico %A Amitis Shidani %A George Deligiannidis %A Arnaud Doucet %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-clerico22a %I PMLR %P 4212--4257 %U https://proceedings.mlr.press/v178/clerico22a.html %V 178 %X This work discusses how to derive upper bounds for the expected generalisation error of supervised learning algorithms by means of the chaining technique. By developing a general theoretical framework, we establish a duality between generalisation bounds based on the regularity of the loss function, and their chained counterparts, which can be obtained by lifting the regularity assumption from the loss onto its gradient. This allows us to re-derive the chaining mutual information bound from the literature, and to obtain novel chained information-theoretic generalisation bounds, based on the Wasserstein distance and other probability metrics. We show on some toy examples that the chained generalisation bound can be significantly tighter than its standard counterpart, particularly when the distribution of the hypotheses selected by the algorithm is very concentrated.
APA
Clerico, E., Shidani, A., Deligiannidis, G. & Doucet, A.. (2022). Chained generalisation bounds. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:4212-4257 Available from https://proceedings.mlr.press/v178/clerico22a.html.

Related Material