# Bound to Disagree: Generalization Bounds via Certifiable Surrogates

arXiv: https://arxiv.org/abs/2602.23128 · HTML: https://mlsanity.com/paper/2602.23128/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 106 references that are in the map.
- First posted on arXiv 26 Feb 2026.

## Builds on (most cited first, 30 of 54)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [An Empirical Study of Example Forgetting during Deep Neural Network Learning](https://mlsanity.com/paper/1812.05159/) (2018)
- [Up or Down? Adaptive Rounding for Post-Training Quantization](https://mlsanity.com/paper/2004.10568/) (2020)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Measuring the Intrinsic Dimension of Objective Landscapes](https://mlsanity.com/paper/1804.08838/) (2018)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [Adversarial Active Learning for Deep Networks: a Margin Based Approach](https://mlsanity.com/paper/1802.09841/) (2018)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [Generalization bounds for deep convolutional neural networks](https://mlsanity.com/paper/1905.12600/) (2019)
- [Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin](https://mlsanity.com/paper/1910.04284/) (2019)
- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network](https://mlsanity.com/paper/1909.11274/) (2019)

## Built on by (most cited first, 2 of 2)

- [Pay Only for Disagreement: Certified No-Regression Verdicts for Model Updates with Matching Label-Complexity Bounds](https://mlsanity.com/paper/2609.17560/) (2026)
- [Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancing](https://mlsanity.com/paper/2609.32271/) (2026)

## Abstract (arXiv)

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.