Escaping Parameter Space: Tight Generalization Bounds via Representation Quality

Niclas Göring; Shuofeng Zhang; Branton DeMoss; Ard A. Louis

cs.LGOct 16, 2026

Escaping Parameter Space: Tight Generalization Bounds via Representation Quality

Authors: Niclas Göring, Shuofeng Zhang, Branton DeMoss, Ard A. Louis

Organizations: Rudolf Peierls Centre for Theoretical Physics, University of Oxford, Oxford, UK · Mathematical Institute, University of Oxford, Oxford, UK

Abstract

We derive a tight generalization bound for deterministic neural We derive a tight generalization bound for deterministic neural networks based on their last hidden layer representations. By evaluating representation quality with a parameter-free $k$ -nearest-neighbor ( $k$ -NN) classifier, our certificate avoids traditional parameter-space complexity measures, KL divergences to a posterior, weight norms, and compression. The bound is tight: trained from scratch, it reaches an 8.0 percentage point gap to test error on CIFAR-10 (ResNet-18) and yields the first non-vacuous certificates we are aware of on CIFAR-100; with frozen DINOv2 representations, it certifies at 1.4% on CIFAR-10 and 23.1% on 1,000-class ImageNet. It decomposes additively into three empirical, independently measurable quantities: local class geometry ( $k$ -NN decoder error), decoder-network agreement, and training stability. This allows the bound to act as a diagnostic tool: we demonstrate that actively destroying local class geometry eliminates generalization while leaving dataset memorization intact, identifying class geometry as a causally relevant mechanism for generalization. Finally, we show that learned representations are significantly less sensitive to weight noise than linear readouts, suggesting why parameter-space certificates often struggle to remain tight.

Figures & tables

Figure 1: Any learned feature map

\varphi\colon\bm{X}\to\mathcal{Z}

raises three questions: Q1 Can a simple classifier in

\mathcal{Z}

predict labels? Q2 Does it agree with the network? Q3 Is training stable under fold removal? a) A

k

-NN classifier on the last-hidden-layer representation

h^{(L)}(\bm{x})

yields

\hat{y}_{\mathrm{kNN}}

( Q1 ), compared against

\hat{y}_{\mathrm{NN}}

( Q2 ); a fold-trained model tests stability ( Q3 ). b) ResNet-18 on CIFAR-10: the bound converges to within

8.0

pp of test error at

n{=}50{,}000

, the tightest known certificate from a deterministic network without modified training. Stacked bars show Q1 dominates: representation quality is the binding constraint.

		CIFAR-10			CIFAR-100			ImageNet			ImageNet-V2
Model	Params	Err	Bnd	Gap	Err	Bnd	Gap	Err	Bnd	Gap	Err	Bnd	Gap
DINOv2-L/14	304M	0.9	1.4	0.5	10.4	12.1	1.7	20.9	23.1	2.2	37.5	43.0	5.5
DINOv2-g/14	1.1B	—	—	—	—	—	—	21.2	23.5	2.3	37.7	43.2	5.5
DINOv2-B/14	86M	2.3	3.2	0.9	14.9	16.9	2.0	23.4	25.7	2.3	41.3	46.8	5.5
ViT-B/16	86.6M	6.8	8.3	1.5	28.1	30.5	2.4	21.6	23.8	2.2	39.2	44.7	5.5
ViT-L/16	304M	7.7	9.2	1.5	29.5	32.0	2.5	21.8	24.0	2.2	40.3	45.8	5.5

Table 1: Transfer decoder certification (

\ell_{2}

\delta{=}0.05

). The certified object is the

k

-NN decoder, not the pretrained classifier head ( Q2 , Q3 vanish by construction). Err:

k

-NN error (%). Bnd: certified bound (%). Gap:

<

5 5–15 15–30 30–50

>

50 pp .

Method	Architecture	$n$	Test	Bound	Gap	Certified object
MNIST
Dziugaite and Roy (2017)	FCN-600	60k	${\sim}$ 2.5%	${\sim}$ 17%	14.5	Stochastic net
Zhou et al. (2019)	LeNet-5	60k	${\sim}$ 1%	${\sim}$ 46%	45	Compressed net
Lotfi et al. (2022)	LeNet-5	60k	${\sim}$ 1%	11.6%	10.6	Quant. subspace
Pérez-Ortiz et al. (2021)	FCN	60k	${\sim}$ 1.4%	${\sim}$ 2.3%	0.9	Stochastic net
Ours (FFNN)	FFNN	60k	1.5%	4.9%	3.4	Det. net via repr.

Table 2: Cross-fit certification vs. prior bounds. Per-dataset blocks list prior work (above the rule) and our cross-fit bounds across architecture families (below, shaded). Best row per dataset in darker shade and bold. ReLU activation; SiLU results are in Table 3 .

\ell_{2}

metric,

\delta{=}\delta^{\prime}{=}0.025

, best over

k\in\{1,3,5,7,11,15,21\}

and

j\in[5]

; union-bound cost included. Prior-work numbers from original publications.

Figure 2: ResNet-18 width sweep on CIFAR-10 (0%, 10%, 20% label noise, 3 seeds). a) Test error and total bound. b)

\Delta Q_{1}(w)

and

\Delta Q_{2}(w)

, each measured as excess over the widest-network baseline. c)

\Delta Q_{1}

(local class geometry) decreases monotonically in width. d)

\Delta Q_{2}

(decoder–network agreement) is the only non-monotone term, peaking at the interpolation threshold and then collapsing. The test-error hump is localized to

Q_{2}

. The

Q_{3}

term is not analyzed in this sweep.

Figure 3: Six-layer FFNNs (width

{=}1024

) trained on SVHN with

\mathcal{L}_{\mathrm{CE}}+\lambda\,\mathcal{L}_{\mathrm{rep}}

across four activation functions. Training accuracy ( blue ) saturates near

100\%

; test accuracy ( red ) degrades toward chance (

\sim 10\%

Q_{1}

( black ) decays together with test error in every case. The qualitative

Q_{1}

-to-test-error coupling is invariant across activation functions, although trajectories differ quantitatively.

Figure 4: a) ReLU ResNet-18 on CIFAR-10. Under Gaussian weight noise at level

\sigma

k

-NN accuracy in

\ell_{2}

representation space ( solid blue ) degrades more slowly than the network’s own predictions ( dashed red ). At

\sigma{=}0.01

the

k

-NN decoder retains

84\%

accuracy while the network has fallen to

67\%

. b) The representation advantage holds across activation functions and label-corruption levels at

\sigma{=}0.01

, with the gap ranging from

+2

pp (40% corruption) to

+46

pp (tanh).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Feedforward networks
		MNIST ( $n{=}60$ k)			CIFAR-10 ( $n{=}50$ k)			CIFAR-100 ( $n{=}50$ k)
Model	Act.	Test	Bound	Gap	Test	Bound	Gap	Test	Bound	Gap
FFNN	ReLU	1.5	4.9 $\pm$ 0.4	3.4	44.6	95.5 $\pm$ 1.1	50.9	75.2	100.0	24.8
FFNN	SiLU	1.4	4.8 $\pm$ 0.1	3.4	44.3	96.2 $\pm$ 1.0	51.9	75.4	100.0	24.6
Convolutional networks
ResNet-18	ReLU	0.6	2.6 $\pm$ 0.0	2.0	4.7	13.0 $\pm$ 0.3	8.3	21.2	51.1 $\pm$ 0.1	29.9

Appendix

Table 3: Cross-fit certification of trained networks (

\ell_{2}

J{=}5

\delta{=}\delta^{\prime}{=}0.025

). Best bound over

k\in\{1,3,5,7,11,15,21\}

and

j\in[5]

. Each entry: mean

\pm

std over 3 seeds.

Method	Det. net	No mod. training	No surrogate	No compress.	No stoch. weights	Pretrained / transfer	Arch.- agnostic	Diagnoses repr.
Dziugaite and Roy [2017]	✗	✗	✓	✓	✗	✗	✓	✗
Pérez-Ortiz et al. [2021]	✗	✗	✓	✓	✗	✗	✓	✗
Zhou et al. [2019]	✗	✗	✓	✗	✗	✗	✓	✗
Lotfi et al. [2022]	✗	✗	✓	✗	✗	✓	✓	$\sim$
Bazinet et al. [2026]	✓	✗	✗	$\sim$	✓	✗	✓	✗
Than and Phan [2025]	✓	✓	✓	✓	✓	✓	✗	✗

Appendix

Table 4: Desiderata for generalization certificates. Our approach satisfies all desiderata; the stability term is certified empirically from unlabeled data rather than bounded analytically.

Family	Repr. dim	Notes
FFNN	$D{=}1024$	6 hidden layers, width 1024, no dropout. Activation (ReLU or SiLU) applied before readout. No data augmentation.
ResNet-18	$D{=}512$	CIFAR-style stem (3 $\times$ 3 conv, no maxpool) for 32 $\times$ 32 inputs. Standard torchvision stem for 224 $\times$ 224.
ResNet-50	$D{=}2048$	Same stem conventions as ResNet-18.
ViT (from scratch)	varies	MNIST: patch 4, embed 192, depth 4, 3 heads, MLP ratio 4, dropout 0. CIFAR-10/100: patch 4, embed 256, depth 6, 8 heads, MLP ratio 4, dropout 0.

Appendix

Table 5: Architecture details for trained-model experiments.

Family	Dataset	Optimizer	LR	Momentum	WD	LS	Batch	Epochs
FFNN	MNIST	AdamW	$10^{-3}$	–	$10^{-5}$	0	512	150
	CIFAR-10	AdamW	$5{\cdot}10^{-4}$	–	$2{\cdot}10^{-5}$	0	512	300
	CIFAR-100	AdamW	$3{\cdot}10^{-4}$	–	$2{\cdot}10^{-5}$	0	512	400
ResNet-18	MNIST	SGD	0.05	0.9	$10^{-4}$	0	256	120
	CIFAR-10	SGD	0.1	0.9	$5{\cdot}10^{-4}$	0	128	200
	CIFAR-100	SGD	0.1	0.9	$5{\cdot}10^{-4}$	0.1	128	240

Appendix

Table 6: Optimization hyperparameters for the cross-fit experiments (Table 2). All schedules are cosine decay to zero unless stated otherwise. “LS” denotes label smoothing.

Experiment	Training seeds	Fold / split seed
Table 1 (transfer)	–	42
Table 2 (MNIST, CIFAR-10)	$\{0,1,2\}$	42
Table 2 (CIFAR-100)	$\{0,1\}$	42
Table 3 (“Ours”)	same as Table 2	42
Figure 1b (sample-size sweep)	$\{0,1,2\}$	42
Figure 2 (width sweep)	$\{42,43,44\}$	42

Appendix

Table 7: Random seeds used in each experiment.

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 163 papers

Jun 9, 2022

Learning Non-Vacuous Generalization Bounds from Optimization

One of the fundamental challenges in the deep learning community is to theoretically understand how well a deep neural network generalizes to unseen data. However, current approaches often yield generalization bounds that are either too loose to be informative of the true generalization error or only valid to the compressed nets. In this study, we present a simple yet non-vacuous generalization bound from the optimization perspective. We achieve this goal by leveraging that the hypothesis set accessed by stochastic gradient algorithms is essentially fractal-like and thus can derive a tighter bound over the algorithm-dependent Rademacher complexity. The main argument rests on modeling the discrete-time recursion process via a continuous-time stochastic differential equation driven by fractional Brownian motion. Numerical studies demonstrate that our approach is able to yield plausible generalization guarantees for modern neural networks such as ResNet and Vision Transformer, even when they are trained on a large-scale dataset (e.g. ImageNet-1K).

Chengli Tan, Jiangshe Zhang, Junmin Liu +1

Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China

Neural Network Generalization Statistical Learning Theory Generalization Bounds

Ask PDF

Oct 5, 2026

Certification-Enhanced Generalization Bounds

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.

Leo Elmecker-Plakolm, Matthew Wicker

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

Algorithmic Stability Generalization Bounds Algorithmic Generalization

Ask PDF

Jun 15, 2026

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

Neural Network Generalization Neural Network Robustness Generalization Bounds

Ask PDF

Abstract

Generalization Bounds

Explore similar work

Learning Non-Vacuous Generalization Bounds from Optimization

Certification-Enhanced Generalization Bounds

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