Bound to Disagree: Generalization Bounds via Certifiable Surrogates

Mathieu Bazinet, Valentina Zantedeschi, Pascal Germain
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:491-520, 2026.

Abstract

Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes. In this paper, we tackle these issues by providing new disagreement-based certificates for the gap between the true risk of any two predictors. We then bound the true risk of the predictor of interest via a surrogate model that enjoys tight generalization guarantees, and by evaluating our disagreement bound on an unlabeled dataset. We empirically demonstrate the tightness of the obtained certificates and showcase the versatility of the approach by training surrogate models leveraging three different frameworks: sample compression, model compression and {PAC-Bayes} theory. Importantly, such guarantees are achieved without modifying the target model, nor adapting the training procedure to the generalization framework.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-bazinet26a, title = {Bound to Disagree: Generalization Bounds via Certifiable Surrogates}, author = {Bazinet, Mathieu and Zantedeschi, Valentina and Germain, Pascal}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {491--520}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/bazinet26a/bazinet26a.pdf}, url = {https://proceedings.mlr.press/v337/bazinet26a.html}, abstract = {Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes. In this paper, we tackle these issues by providing new disagreement-based certificates for the gap between the true risk of any two predictors. We then bound the true risk of the predictor of interest via a surrogate model that enjoys tight generalization guarantees, and by evaluating our disagreement bound on an unlabeled dataset. We empirically demonstrate the tightness of the obtained certificates and showcase the versatility of the approach by training surrogate models leveraging three different frameworks: sample compression, model compression and {PAC-Bayes} theory. Importantly, such guarantees are achieved without modifying the target model, nor adapting the training procedure to the generalization framework.} }
Endnote
%0 Conference Paper %T Bound to Disagree: Generalization Bounds via Certifiable Surrogates %A Mathieu Bazinet %A Valentina Zantedeschi %A Pascal Germain %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-bazinet26a %I PMLR %P 491--520 %U https://proceedings.mlr.press/v337/bazinet26a.html %V 337 %X Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes. In this paper, we tackle these issues by providing new disagreement-based certificates for the gap between the true risk of any two predictors. We then bound the true risk of the predictor of interest via a surrogate model that enjoys tight generalization guarantees, and by evaluating our disagreement bound on an unlabeled dataset. We empirically demonstrate the tightness of the obtained certificates and showcase the versatility of the approach by training surrogate models leveraging three different frameworks: sample compression, model compression and {PAC-Bayes} theory. Importantly, such guarantees are achieved without modifying the target model, nor adapting the training procedure to the generalization framework.
APA
Bazinet, M., Zantedeschi, V. & Germain, P.. (2026). Bound to Disagree: Generalization Bounds via Certifiable Surrogates. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:491-520 Available from https://proceedings.mlr.press/v337/bazinet26a.html.

Related Material