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

Learning Non-Vacuous Generalization Bounds from Optimization
Jun 9, 2022Chengli Tan, Jiangshe Zhang, Junmin Liu +1Neural Network Generalization Statistical Learning Theory
Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China
Certification-Enhanced Generalization Bounds
Oct 5, 2026Leo Elmecker-Plakolm, Matthew WickerAlgorithmic Stability Generalization Bounds
Department of Computing Imperial College London London, SW7 2AZ, UK
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 +3Neural Network Generalization Neural Network Robustness
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

Jun 9, 2022J/K move · Enter open · S save

Learning Non-Vacuous Generalization Bounds from Optimization

Chengli Tan, Jiangshe Zhang, Junmin Liu, Yihong Gong

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

Open paper AskPDF arXiv

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).

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