Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models
Khoat Than, Dat Phan · 2025
Read Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models by Khoat Than, Dat Phan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-07325.txt.
Introduction
Khoat Than and Dat Phan give a way to bound how much a trained deep net will err on fresh data, with no change to the net. Past bounds of this kind read as blank at real scale: they promise more than the whole range of loss. Their bound can be summed to the digit and stays tight at all scales tried. Nets as big as six hundred million parts are in the set.
The bound splits the gap into two parts a reader can grasp. One weighs how the data mass is spread through the space of inputs. The next weighs how the net acts in each small zone of that space. Some parts of the bound track the true test error close. The bound also grows tight when the zones are cut to fit the data's own shape. Wide nets can thus carry real promises, the pair say.
Catalog record
| CREATOR | Khoat Than, Dat Phan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-07325
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models Khoat Than, Dat Phan Abstract Understanding and certifying the behavior of modern deep neural networks remains a fundamental challenge in reliable machine learning. We introduce a new class of data-dependent generalization bounds that apply directly to trained models, without any modification. In particular, we present an exactly computable bound that is non-vacuous across all evaluated networks, including ImageNet-scale models with 600M parameters. This this is the first work showing that meaningful generalization guarantees are achievable even for large, unaltered deep networks. Our approach reveals that generalization is governed by the interaction between the trained model and the geometry of the data distribution. We decompose the generalization error into two interpretable components: a distributional complexity term, capturing how the data mass is distributed across the input space, and local model-behavior terms, capturing the network’s behavior within individual regions. This joint dependence identifies where and why generalization gaps arise. Empirically, some components of our bound are highly predictive of the true test error, and the bound tightens when the partition aligns with the intrinsic data geometry, highlighting data-dependent local regularity as a key driver of generalization. 1 Introduction Deep neural networks (NNs) have enabled remarkable advances across domains ranging from game playing to structural biology and large-scale language modeling ( Silver et al., 2016 ; Jumper et al., 2021 ; Achiam et al., 2023 ) . A striking aspect of these systems is their ability to generalize: models trained on finite datasets often achieve strong performance on previously unseen data. Understanding the origin of this generalization capability remains a central challenge in modern learning theory. Despite decades of progress, classical frameworks struggle to explain this phenomenon in the regime of overparameterized, high-capacity networks. Approaches based on Rademacher complexity ( Bartlett et al., 2017 ) , algorithmic stability ( Bousquet and Elisseeff, 2002 ; Brutzkus and Globerson, 2021 ) , robustness ( Xu and Mannor, 2012 ; Sokolić et al., 2017 ) , and PAC-Bayes analysis ( McAllester, 2003 ; Biggs and Guedj, 2022 ) offer valuable perspectives, but typically yield vacuous guarantees when applied to modern NN architectures. Recent work has begun to close this gap by demonstrating that non-vacuous bounds are attainable under carefully controlled settings. For instance, Dziugaite and Roy (2017) obtained non-vacuous PAC-Bayes bounds via optimized posterior distributions, while Zhou et al. (2019) leveraged compression to control the generalization error of stochastic networks. Stability-based approaches have also shown promise ( Nadjahi et al., 2024 ) . However, these advances largely remain confined to small-scale models or rely on stochasticity and model modifications. A notable breakthrough toward large-scale analysis was achieved by Lotfi et al. (2024a) ; Lotfi et al. (2024b) , who derived non-vacuous bounds for large language models such as GPT-2 and LLaMA2 using a combination of quantization, fine-tuning, and compression techniques. While these results significantly expand the scope of theoretical guarantees, they apply to modified versions of the original networks rather than to the trained models themselves. Consequently, it remains unclear whether such guarantees faithfully capture the generalization behavior of the unaltered model. This limitation highlights a fundamental open problem: Can we obtain a non-vacuous bound on the true error of a trained NN, without altering it? Addressing this question is intrinsically challenging. The true error is the primary quantity governing generalization ( Mohri et al., 2018 ) , yet most existing techniques ( Dziugaite and Roy, 2017 ; Zhou et al., 2019 ) either introduce stochasticity or rely on significant model transformations. Even recent PAC-Bayes approaches ( Lotfi et al., 2024a ; Lotfi et al., 2024b ) that reduce explicit randomness still depend on aggressive compression and fine-tuning, yielding guarantees for surrogate models . Since the relationship between the original model {\bm{h}} and its modified counterpart {\bm{h}}^{\prime} is generally uncontrolled, tight bounds for {\bm{h}}^{\prime} need not translate into meaningful guarantees for {\bm{h}} . Figure 1 : The behaviors of two ImageNet-scale trained models. The x -axis shows the data density at each local region of the input space, while the y -axis reports local errors. At a deeper level, these difficulties stem from the reliance of existing theories on global measures of complexity, whether of the hypothesis class, parameter space, or model itself. In contrast, modern NNs exhibit highly heterogeneous behavior across the input space: prediction errors tend to concentrate in specific regions as illustrated in Figure 1 , and both the data distribution and the model’s local behavior critically influence generalization. Capturing this interaction requires moving beyond global worst-case analyses toward a more refined, spatially localized perspective. In this work, we develop a geometry-aware framework that decomposes the true error of a trained model into contributions from different regions of the input space. This perspective makes explicit how distributional mass and local model behavior jointly determine generalization. Crucially, our approach yields bounds that are both non-vacuous and structurally informative : they not only certify the true error, but also identify where errors arise and how they relate to the geometry of the data. Our main contributions are as follows: • First , we derive a novel bound on the true error of a trained model {\bm{h}} under mild assumptions, based on a partition of the input space. The bound simultaneously captures distributional complexity and local properties of {\bm{h}} , revealing how alignment between local errors and data geometry governs overall performance. Empirically, such an alignment highly correlates with true error, and hence can be reliably used for model selection and understanding generalization. A key technical challenge is the control of an intractable aggregation term over local regions; we resolve this via a fine-grained analysis of small and binomial random variables. • Second , we introduce a tractable variant that can be computed exactly from the training data (optionally, with few more held-out samples), without modifying {\bm{h}} . This yields a practical certification procedure that retains the structural insights of the general theory. A detailed comparison with prior approaches is provided in Table 1 . • Third , we empirically validate our framework on 30 modern neural networks trained on ImageNet (1.2M samples), spanning CNNs and Transformers with up to 600M parameters. Across all models, we obtain non-vacuous upper bounds on the true error, even under conservative parameter choices. With suitable partitions, the resulting certificates are remarkably tight. For example, for a large Vision Transformer with validation error 0.2 , our bound yields a certificate of 0.3 . To the best of our knowledge, this is the first work to provide non-vacuous guarantees at this large scale without altering the trained models. The tightness of our certificates suggests that meaningful, data-dependent generalization guarantees for modern NNs are practically realizable without requiring large held-out test sets. Organization: We present our novel bounds in Section 2 , accompanied with more detailed comparisons. Section 3 contains our empirical evaluation for some pretrained NNs. Section 4 concludes the paper. A comprehensive survey about related work is presented in Appendix F . Table 1 : Recent approaches for analyzing generalization error. \checkmark means “Required” or “Yes”. The upper part shows the required assumptions about differrent aspects, e.g., hypothesis space, loss function, training or finetuning. The lower part