Certification-Enhanced Generalization Bounds

Leo Elmecker-Plakolm; Matthew Wicker

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

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\rightarrow\infty

where

N

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

Hyperparameter	train_size sweep	all- $k$ run
	(panels 2–3)	(panel 1)
Noise $\sigma$	0.3	0.3
Train size $m$	10, 25, 50, 100, 200, 400, 750, 1000,	2500
	1250, 1500, 2000, 3200, 5000, 10000
Validation size	1000	1000
Training steps	200	200

Appendix

Table 1: Hyperparameter configurations for

\beta

ablations in Figure 5 . Swept values in bold .

Setting	Mean [s]	Std [s]
Halfmoons – Uniform	3.4878	0.1041
Halfmoons – DD	2.5993	0.0904
MNIST – DD	2.5743	0.1908
ImageNet – DD	2.5233	0.1217
LLM – DD	1.9881	0.0298

Appendix

Table 2: Wall clock times in seconds for computing bounds based on 100 values of

k

, for a model trained on 500 sample points over 100 steps, standard deviation reported over 10 runs.

Hyperparameter	train_size sweep	train_steps sweep
Noise $\sigma$	0.3	0.3
Train size $m$	25, 50, 100, 200, 400, 800, 1600, 3200	1600
Validation size	1000	1000
Training steps (full batch)	1000	10, 50, 100, 200, 500, 1000, 2500
Learning rate	0.1	0.05
Clipping bound $\gamma$	0.1	0.1

Appendix

Table 3: Half-moons sweeps over train size and train steps. Swept values are in bold .

Hyperparameter	train_steps sweep	width sweep
Train size $m$	500	500
Validation size	1000	1000
Training steps	10, 50, 100, 200, 500, 1000	200
Learning rate	0.05	0.05
Clipping bound $\gamma$	0.1	0.1
Hidden width	16	4, 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 .

Hyperparameter	depth sweep	train_steps sweep
Train size $m$	500	500
Validation size	1000	1000
Training steps	200	10, 50, 100, 200, 500, 1000
Learning rate	0.05	0.05
Clipping bound $\gamma$	0.1	0.1
Hidden width	16	16

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 .

Hyperparameter	clip sweep	train_steps sweep
Train size $m$	500	500
Validation size	500	500
Test size	500	500
Training steps	100	5, 10, 25, 50, 100, 200, 400
Learning rate	0.05	0.05
Clipping bound $\gamma$	0.01, 0.05, 0.1, 0.5, 1.0, 2.0	0.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 .

Hyperparameter	Value
Train / val / test size	500 / 500 / 500
Training steps	100
Learning rate	0.05
Clipping bound $\gamma$	0.1
Hidden width	16
Hidden layers	1

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\pm 0.65

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\pm 0.82

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\pm 1.01

Figure 9: Evaluating generalisation bounds over different learning rates. The vertical line shows there point where HRS bounds violate their requirement of

\alpha<\frac{2}{\beta}

for a

\beta

-smooth loss function.

Explore similar work

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
Jun 5, 2026Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1Generalization Bounds Lipschitz Continuity
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.
Upper Bounds on the Generalization Error of Deep Learning Models via Local Robustness and Stability
Jun 15, 2026Abdul-Rauf Nuhu, Parham M. Kebria, Vahid Hemmati +3Generalization Bounds Upper Bounds
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
Bound to Disagree: Generalization Bounds via Certifiable Surrogates
Feb 26, 2026Mathieu Bazinet, Valentina Zantedeschi, Pascal GermainGeneralization Bounds Surrogate Models
1Département d’informatique et génie logiciel, Université Laval, Québec, Qc, Canada · 2ServiceNow Research, Montreal, Qc, Canada

Jun 5, 2026, stat.MLJ/K move · Enter open · S save

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments

Qianqian Lei, Soham Bonnerjee, Yuefeng Han, Wei Biao Wu

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 Bounds Lipschitz Continuity

Open paper AskPDF arXiv

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

L_p

moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under

L_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

L_p

stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.

Abstract

Explore similar work

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite LpL_pLp​ Moments

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

Bound to Disagree: Generalization Bounds via Certifiable Surrogates

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments