Bound to Disagree: Generalization Bounds via Certifiable Surrogates
This work provides a method for researchers and practitioners to obtain tighter and more computable generalization bounds for deep learning models without altering the models or training procedures, which is an incremental improvement in the field of theoretical machine learning.
This paper introduces new disagreement-based certificates to bound the true risk of deep learning models, addressing the limitations of existing vacuous, incomputable, or class-specific bounds. By using a surrogate model with tight generalization guarantees and evaluating on unlabeled data, the authors demonstrate empirically tight certificates across sample compression, model compression, and PAC-Bayes frameworks.
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 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.