cs.LGOct 5, 2026

Certification-Enhanced Generalization Bounds

Authors: Leo Elmecker-Plakolm, Matthew Wicker

Organizations: Department of Computing Imperial College London London, SW7 2AZ, UK

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We investigate the use of formal methods to provide tight and sound generalization bounds for learning algorithms. By casting the traditional notion of algorithmic stability as a specification to be verified, we demonstrate that recent advances in reachability analysis can yield provable bounds on the generalization of a given model and algorithm on a sample dataset. As sample-specific algorithmic stability is insufficient to bound the usual distributional notion of generalization, we develop a novel concentration inequality to connect the sample-specific results of formal certification algorithms to the required distributional analysis for bounding the expected generalization gap. The resulting framework enables the analysis of prior generalization bounds to extend far beyond their original restrictive assumptions. Our approach computes sound bounds on the expected generalization gap in a constant number of algorithm runs without making any analytical assumptions on the algorithm; to achieve non-vacuous bounds we only require that the certified reachable parameter set is bounded --- a condition that we do not assume but formally verify. In practice, we demonstrate that our framework provides formal generalization guarantees that are orders of magnitude tighter than alternative sound computational approaches at scales ranging from toy datasets to fine-tuning classification heads on top of modern large language models. While we implement certification-enhanced versions of several well-known stability results, future extensions of our approach will enable tighter bounds and enhanced practical adoption across the spectrum of modern generalization bounds.

Figures & tables

Figure 1: In various settings our bounds are always-sound, tighter alternatives to existing analytical bounds.
Figure 2: Bound gaps observed on halfmoons dataset. The leftmost and center plots explore our bounds against benchmarks across number of train steps and train size. The rightmost figure plots the cross entropy loss gap alongside a halfmoons sample and a star for the uniform bound. Shaded region displays correction factor impact.
Figure 3: From left to right the plots show (i) the behaviour of our data dependent bounds compared to train steps on MNIST, (ii) bounds across different hidden layer widths, (iii) the same train step plot but on ImageNet, (iv) bound tightness for varying numbers of hidden layers.
Figure 4: The bound behaviour compared to baselines in LLM classification head fine-tuning. The left and center subfigures use Gemma-4-E2B, whereas the rightmost subfigure compares different foundation models.
Figure 5: Small ablations on different properties of interest. Left to right: (i) investigation of bound tightness for increasing numbers of k evaluations in our practical algorithm, (ii) asymptotic bound behaviour as N→∞N\rightarrow\infty where NN is the sample size (excl. correction factor), and (iii) optimal beta values for increasing sample sizes.
Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Hyperparametertrain_size sweepall- kk run
 (panels 2–3)(panel 1)
Noise σ\sigma0.30.3
Train size mm10, 25, 50, 100, 200, 400, 750, 1000,2500
 1250, 1500, 2000, 3200, 5000, 10000 
Validation size10001000
Training steps200200
Appendix
Table 1: Hyperparameter configurations for β\beta ablations in Figure 5 . Swept values in bold .
SettingMean [s]Std [s]
Halfmoons – Uniform3.48780.1041
Halfmoons – DD2.59930.0904
MNIST – DD2.57430.1908
ImageNet – DD2.52330.1217
LLM – DD1.98810.0298
Appendix
Table 2: Wall clock times in seconds for computing bounds based on 100 values of kk , for a model trained on 500 sample points over 100 steps, standard deviation reported over 10 runs.
Hyperparametertrain_size sweeptrain_steps sweep
Noise σ\sigma0.30.3
Train size mm25, 50, 100, 200, 400, 800, 1600, 32001600
Validation size10001000
Training steps (full batch)100010, 50, 100, 200, 500, 1000, 2500
Learning rate0.10.05
Clipping bound γ\gamma0.10.1
Appendix
Table 3: Half-moons sweeps over train size and train steps. Swept values are in bold .
Hyperparametertrain_steps sweepwidth sweep
Train size mm500500
Validation size10001000
Training steps10, 50, 100, 200, 500, 1000200
Learning rate0.050.05
Clipping bound γ\gamma0.10.1
Hidden width164, 8, 16, 32
Appendix
Table 4: MNIST sweeps over train steps and hidden layer dimension. The certified model is an MLP head over MNIST pixels projected onto their leading 50 principal components. Swept values are in bold .
Hyperparameterdepth sweeptrain_steps sweep
Train size mm500500
Validation size10001000
Training steps20010, 50, 100, 200, 500, 1000
Learning rate0.050.05
Clipping bound γ\gamma0.10.1
Hidden width1616
Appendix
Table 5: ImageNet sweeps over model depth and train steps. The certified model is an MLP head over frozen ResNet-18 features. Swept values are in bold .
Hyperparameterclip sweeptrain_steps sweep
Train size mm500500
Validation size500500
Test size500500
Training steps1005, 10, 25, 50, 100, 200, 400
Learning rate0.050.05
Clipping bound γ\gamma0.01, 0.05, 0.1, 0.5, 1.0, 2.00.1
Appendix
Table 6: Hyperparameters for gamma value and train step sweeps. The certified model is a small MLP head over frozen LLM embeddings. Swept values are in bold .
HyperparameterValue
Train / val / test size500 / 500 / 500
Training steps100
Learning rate0.05
Clipping bound γ\gamma0.1
Hidden width16
Hidden layers1
Appendix
Table 7: Hyperparameter configuration for embedding-model comparison.
Figure 6: LLM model type experiment across 5 different seeds. Lines show the average with error bars representing one standard deviation. Run time across 15 runs [mean ±\pm std]: 14.20±0.6514.20\pm 0.65 s.
Figure 7: LLM clip value experiment across 5 different seeds. Lines show the average with error bars representing one standard deviation. Run time across 5 runs [mean ±\pm std]: 29.02±0.8229.02\pm 0.82 s.
Figure 8: ImageNet model depth experiment across 5 different seeds. Lines show the average with error bars representing one standard deviation. Run time across 5 runs [mean ±\pm std]: 48.85±1.0148.85\pm 1.01 s.
Figure 9: Evaluating generalisation bounds over different learning rates. The vertical line shows there point where HRS bounds violate their requirement of α<2β\alpha<\frac{2}{\beta} for a β\beta -smooth loss function.

Explore similar work

CardsList
Jun 5, 2026stat.ML

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite LpL_p Moments

While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptions, which can be overly restrictive for modern settings with heavy-tailed or unbounded losses. We develop a stability-based framework that requires only a finite LpL_p moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under LpL_p constraints, extending McDiarmid's bounded-differences techniques beyond the classical regime. Leveraging these results, we derive sharp high-probability generalization bounds across a range of learning paradigms, including empirical risk minimization, transductive regression, and meta-learning. These guarantees show that LpL_p stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.

Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1

Department of Statistics, The University of Chicago, Chicago, IL 60637, USA. · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, USA.

Generalization BoundsLipschitz Continuity
AskPDF
Jun 15, 2026cs.LG

Upper Bounds on the Generalization Error of Deep Learning Models via Local Robustness and Stability

Generalization is a critical property of data-driven models, particularly deep learning models deployed in safety-critical applications. Robustness-based generalization bounds have gained attention as a principled way to link robustness properties to generalization performance, often in a data-dependent manner. However, most existing bounds suffer from vacuousness in practical settings, yielding loose upper bounds that greatly exceed the actual error rates and limiting their usefulness for real-world evaluation. While this issue is often attributed to the uncertainty term, a substantial part of the problem originates from the robustness term itself, particularly for the 0-1 loss. Existing approaches typically treat the robustness term as a global measure, ignoring its variation across different sub-regions of the input space. In this work, we propose a generalization bound that addresses this limitation by scaling the robustness term according to the number of stable and unstable samples within each sub-region. Our bounds incorporate both data- and model-dependent factors while maintaining practical relevance (yielding tighter upper bounds on true error). Experiments on models trained on the ImageNet dataset show that our bounds remain consistently non-vacuous and achieve the tightest estimates among existing methods, closely aligning with empirical performance across a range of robust deep neural networks.

Abdul-Rauf Nuhu, Parham M. Kebria, Vahid Hemmati +3

aNorth Carolina Agricultural and Technical State University, Dept. Electrical and Computer Engineering 1601 E Market St., Greensboro, 27411, NC, USA · bUniversity of Alabama, Dept. Computer Science, Tuscaloosa, 35487, AL, USA · cSouthwest Research Institute, San Antonio, 78238, TX, USA

Generalization BoundsUpper BoundsDeep LearningImagenet
AskPDF
Feb 26, 2026cs.LG

Bound to Disagree: Generalization Bounds via Certifiable Surrogates

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.

Mathieu Bazinet, Valentina Zantedeschi, Pascal Germain

1Département d’informatique et génie logiciel, Université Laval, Québec, Qc, Canada · 2ServiceNow Research, Montreal, Qc, Canada

Generalization BoundsSurrogate ModelsPac-Bayesian TheoryDeep LearningSurrogatesDisagreement
AskPDF