Certifying Deep Network Risks and Individual Predictions with PAC-Bayes Loss via Localized Priors
Authors: Wen Dong
Venue: NeurIPS 2025 poster ()
Keywords: PAC-Bayes generalization
Data-dependent bounds
Bayesian neural networks
Adversarial robustness
Model calibration
Trustworthy AI
Primary area: probabilistic_methods
TL;DR: We propose a computationally efficient localized PAC-Bayes prior directly integrated into training, yielding tight generalization certificates, individual prediction guarantees, robustness, and calibration for deep networks.

Abstract: As machine learning increasingly relies on large, opaque foundation models powering generative and agentic AI, deploying these systems in safety-critical settings demands rigorous guarantees on their generalization beyond training data. PAC-Bayes theory offers principled certificates linking training performance to generalization risk, yet existing approaches are rarely practical: simple theoretical priors yield vacuous bounds, while data-dependent priors trained separately are computationally costly or introduce bias. To bridge this fundamental gap, we propose a localized PAC-Bayes prior—a structured, computationally efficient prior softly concentrated near parameters favored during standard training, enabling effective exploration without costly data splits. By integrating this localized prior directly into standard training loss, we produce practically tight generalization certificates without workflow disruption. Theoretically, under standard neural tangent kernel assumptions, our bound shrinks as networks widen and datasets grow, becoming negligible in practical regimes. Empirically, we certify generalization across image classification, NLP fine-tuning, and semantic segmentation, typically within three percentage points of test errors at ImageNet scale, while providing rigorous guarantees for individual predictions, selective rejection, and robustness.

Certifying Deep Network Risks and Individual Predictions with PAC-Bayes Loss via Localized Priors
Wen Dong"
Air Force Research Laboratory. Patterson AFB, OH 45433 wendong@gmail. com
Abstract
As machine learning increasingly relies on large, opaque foundation models power- ing generative and agentic AI, deploying these systems in safety-critical contexts demands rigorous generalization guarantees beyond training data. MMC-Bayes the- ory provides principled certificates linking training performance generalization risk, yet existing approaches remain impractical: simple theoretical priors yield vacuous bounds, while data-dependent priors require costly second-stage training or introduce bias. To bridge this critical gap, we propose a localized PAC-Bayes prior-a structured, computationally efficient prior softly concentrated around parameters favored during standard training. By integrating this localized prior di- rectly into the standard training objective, we deliver practically tight generalization certificates with minimal workflow disruption. Under standard neural tangent ker- nel assumptions, our bound shrinks as networks widen and datasets grow, becoming negligible in realistic regimes. Empirically, we demonstrate tight generalization certificates on tasks ranging from image classification (MNIST, CIFAR, ImageNet) and NLP fine-tuning (GLUE) to semantic segmentation (Cityscapes), typically within three percentage points of test error at ImageNet scale. Additionally, our ap- proach provides rigorous guarantees for individual predictions, selective rejection of uncertain predictions, adversarial robustness, and accurate calibration direetll addressing key requirements for trustworthy AI deployment.
Introduction
Large-scale neural networks now read chest X-rays, flag fraudulent transactions, steer driver- assistance systems, and complete sentences for hundreds of millions of users. single held-out accuracy number no longer suffices for regulators and practitioners deploying these models in safety- critical contexts. Aviation (EU's A/ Roadmap 2.0), medical (U.S. FDA's 2025 draft guidance), and automotive (ISO PAS 8800:2024) standards all explicitly require rigorous learning-assurane argu- ments that bound the model's 's post-deployment error rate. Industry responses- such as robustness checks provided by major tool builders and responsible Al practices promoted by leading compa- address only local or point-wise guarantees, leaving open the distribution-level risk question central to real-world safety and trastworthiness.
Probably Approximately Correct (PAC) learning theory quantifies generalization rigorously, yet classical PAC complexity measures (VC dimension, Rademacher complexity) yield overly con- servative bounds for modern, heavily over over- peee-aaraettrieeed networks. PAC-Bayes, introduced by McAllester I| [ and further developed by Langford B 4 and Catoni 55 6. sharpens this anal- ysis by comparing the learned parameter distribution p with reference distribution и. The gap between training and test loss reduces to an information term [L r)) However, naive PAC-Bayes
Affiliation provided for identification only; work performed in personal capacity on personal time.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

priors produce vacuous bounds on large-scale architectures: the resulting KL divergence can reach thousands of nats, rendering the method practically unusable.
We address this fundamental limitation by employing a localized prior, an approach inspired by localized prior is defined as Toe (0) & π T(0) exp(=<Ars(0)), with 0 < { <<>> 1. Here, x0)) is the original data- independent prior, (0) is the empirical loss, and the parameters X, É control the strength of the shift toward promising parameters. This prior closely mirrors the ideal Gibbs posterior distribution p(0) x (0)) exp[- s
Catoni's original work [6] and subsequent extensions 7 8) Specifically,
which emerges naturally as the limit case when Ç 1. Thus, the factor E < 1 introduces controlled softening, preventing overfitting by keeping the prior more dispersed than the fully empirical Gibbs posterior. Optimizing and À as part of standard SGD seamlessly integrates PAC-Bayes regularization into training, yielding tight and practically meaningful generalization bounds for modern neural networks.
Empirically, our localized PAC-Bayes bound integrates seamlessly into standard training by directly replacing traditional loss objectives with PAC-Bayes-based counterparts. On benchmarks ranging from classical image classification (MNIST, CIFAR-10/100, ImageNet) to modern tasks such as Cityscapes semantic segmentation and GLUE NLP fine-tuning, our method consistently provides rigorous, tight, and meaningful certificates. The certification overhead is minimal, comparable to adding just one training epoch, while offering reliable individual-level guarantees. selective prediction strategies, and robust adversarial input detection.
Theoretically, confirm that bound converges favorably with increasing data and network size, establishing clear relationships between localization parameters, network width, and sample size. Informally stated, under standard scaling conditions, the KL. term shrinks linearly in network width and inversely with the sample size, vanishing entirely in infinite-width limits (Theorem) 3.2p.
In summary, we (i) introduce localized, trajectory-aware PAC-Bayes bound, transforming PAC- Bayes from theoretical curiosity to practical diagnostic, (ii) demonstrate straightforward, effective integration into real-world deep-learning pipelines, and (iii) validate our approach across diverse vision, language, and control tasks, aligning closely with emerging regulatory requirements.
PAC-Bayes Preliminaries and Notation
Machine-learning papers typically report empirical training loss, yet practical deployment demands guarantees on unseen data. The difference between these defines a deviation event. Formally, given a dataset S { y: ) drawn from unknown distribution D, a predictor parameterized by 0, and per-example loss {(;; Ii yi) E j0, 1]. we denote the empirical loss by r0) = N E; e(O; x,, Mi) and the population (true) loss by R(()) = (x [e(0; x. v)]. Our central question: how improbable
the event R(0)- Ts > 0?
The simplest way to bound such deviations uses Markov's 's inequality, controlling the tail of nonnegative random variable X via its expectation: P[X > k EX] & 1/k. To sharpen control, we transform deviations through a monotone mapping speessiccciill........... exponentiation tto amplify large deviations. Explicitly, we rewrite the deviation probability using exponentiation and then apply Markov:
P(rs(B) R(0) > ((0) > ANE < -ANE E (lc))((()))R))))
Union bounds and classical complexity measures (c.g., VC-dimension, Rademacher complexity extend these guarantees from single predictors to finite hypothesis sets. However, classical PAC bounds falter when faced with large, complex hypothesis spaces-such as deep neural networks, explicitly parameterized by many-layered compositions of affine transformations and nonlinear activations. Classical PAC bounds require clipping or softening losses to lie within [o. 1]. yet even after we clipped/softened and sealed the cross entropy loss to be within [0, 1] to satisfy these artificial constraints, traditional combinational or covering- numberr arguments rapidly explode due to the massive complexity inherent in deep architectures.
PAC-Bayes circumvents these issues by considering distributions over predictors rather than finite sets. The central technical tool is the Donsker- Varadhan variational identity, which provides a sharp

---

variational bound on exponential moments under a reference distribution n.:
log Ex (()) = sup (Ep]S(0) - -LL(]|=))
Choosing f(0) (0))(0) R(0)), and applying Jensen's 's inequality to push expectation inside, the exponential tail bound above becomes:
Ps EEp (r)(0) - R(O)] > s) - Ps (Bpplre0) RRi)] > x20) S S Se-ANEE ( (e) R(0))
(Jensen) e Xe Es. (()
(DV) S e exp (sup, {Ep[)(rs(0) - - -K()))))
Setting this probability equal to 6, we finally obtain the simplified PAC-Bayes inequality IT0 6). explicitly linking good generalization to small divergence of the posterior from a fixed prior x: with high probability 1-5, 5,
[)( < Ep] + KL(p|(>) + log(1/0)
X
Original PAC-Bayes results 1
3 instead chose f(0) = (0) R(0)) to directly bound KI.-
divergences between empirical and population risks, but evaluating such KI. divergences is challeng- ing. Thus, the linearized Hoeffding- based form above is preferred in practice.
Still, PAC-Bayes bounds remain challenging for deep networks, since naïve priors (like isotropic
Gaussians) differ substantially from actual SGD-trained parameters, inflating the KL term dramatically and producing trivial guarantees. Recent efforts include complex data-dependent priors-weighh compression [T], variational priors learned through auxiliary optimization [8, and differential-
privacy priors 12 each effective but computationally expensive.
simple way view Catoni's ss localization 66) is the PAC-Bayes analogue of classical capacity- near-the-data ideas: SVM margin/SRM reasoning (9. local Rademacher complexities that shrink around empirical minimizers [13 [4, and variance-aware (empirical -errsseein concentration (15) In PAC-Bayes, we implement this by exponential tilting (0) x T (0) exp [-EArs this is the same mechanism as Gibbs/exponential weights in aggregation [6] and is handled analytically via the Nonsker-Varadhar log т [exp {-] added to the usual (L(p]| lT. The temperature & E (0, 1) softly interpolates between the base prior (5 + 0) and the empirical Gibbs posterior (5 + 1). and the bound tracks this interpolation with only mild (1 - 5 factor. This perspective both connects localization to standard non-PAC-Baye tools and reassures that the "extra strength" from data dependence is explicitly accounted for by log-partition term rather than hidden in heuristies
change of measure, which turns the tilt into transparent compensation term
Insights from Neural Tangent Kernel theory [19 suggest the KL divergence of the SGD trajectory from initialization accumulates gradually, with small incremental increases per step-ttepppp implying that total KL cost shrinks as network width grows.
A more detailed and extended review of PAC-Bayes theory and related derivations be found in Appendix In the next section, we rigorously formalize these localized PAC- BByya ideas, developing practical generalization certificate validated experimentally at ImageNet scale.
3 Empirical PAC-Bayes Bound for Neural Networks
The following theorem guarantees with high probability a bound on a neural network's 's true (population) error based solely on the training data, sampled network parameters, and explicit statistical penalties. Specifically, our bound decomposes into four intuitive components: (1) empirical risk estimated via sampling from learned posterior distribution, (2) penalties due to Monte Carlo sampling uncertainty, (3) complexity measured as the divergence hetween the learned posterior and a tilted data-dependent prior (similar variational inference objectives), and (4) normalization terms ensuring uniform statistical validity.
Let p(8) denote posterior distribution over neural network parameters, which we optimize directly with respect to the empirical loss rf()) and, in practice, its mini-batch proxy fm (Component
1). To measure complexity, we a tilted prior distribution (Component 3): Texpl (o) (0) x (0) expp-=Xrs((P)))) constructed by softly aligning fixed, data-independent reference distribution
3

---

(0) toward low-loss regions of parameter space, moderated by scaling parameters 0 < a <<I and tempeeetee parameter X.
We estimate the empirical loss and the log-moment under the prior via independent samples 0; ~ and 03- T:
plfm) R > 1=1 (0:). π [e-
Σ >,m -
(2)
These sample estimates introduce explicit uncertainty penalties into the bound (Component 2). The parameter e (0, 1) represents our total confidence budget, split among different rare events. The parameters a and Ç specify the granularity of our discretization, enabling optimization of parameters & and À to minimize the PAC-Bayes bound.
Theorem 3.1 (Empirical PAC-Bayes Bound), For any confidence budget e E (0, 1), localization parameters < < a < 1, scaling parameter X E [1, 2N,, and discretization parameter Ç E (5. 1), let 9 ()/(NN)) With probability at least 1 6.
[A[R(O) (1 (1- 1
att
{ p [ + A/2 (KL(OlT) + log x (e- (-(AAm])
(3)
CN
log(6) All (l/e)
log( AlE
+ log 1+ (1-e Ex)
(o 2M
1+5/a log
2AA
where 6=
+(++5)
2K
2m
Here g(x)
= E'-8-1 and |= are the sizes of the X and E-grids. The denominator satisfies
0 1 att (
S 1.
Proof sketch. The proof starts from Catoni's localized learning lemma: for any posterior p. tilting a base prior π by exp (-EArs) yields a high-probabiliiy inequality that upper-bounds p p| by combination of p [rs]] a divergence term, and small curvature penalty coming from a Bernstein mgf control; algebraically expanding KL (ppp (-{)r))) = (L((p] =)) + Exp [rs) + log E,, [e <Ams] exposes exactly the three quantities we estimate in practice (empirical risk, structural complexity, and the localization normalizer). To make (x.E) ) tunable by SGD without data-splitting,
first uniformize over discrete grids for À and & (union bound) and then relax back to continuous values using the nearest grid points, which introduces the transparent contraction factors in the denominator and the small grid-size logs in the numerator (this is the source of the (1-E/a (/a)//) and the g(X/(<N) ) term). Finally, each expectation is replaced by Monte-Carlo proxy with one-sided concentration
correction that preserves the direction of the bound: we use Hoeffding for p [fm] and prior-sampling upper confidence bound for log E, (e- (monotonicity of log keeps it one-sided), while mini-
batching replaces Ts by fm with an added ( (1+E) { ) radius. the resulting bound is tight because automatically adapts to concentrate around models with low training loss (localization) and adjusts to the variance of the loss (curvature), avoiding overly conservative estimates. Moreover, it provides a practical drop-in objective, resembling standard training j a well-calibrated regularization term, making it easy to optimize via standard wraseent-based methods. The formal statement and complete proof of Theorem 3.1 can be found in Appendix A.1
Our PAC-Bayes bound explicitly avoids the vacuousness problem common in prior PAC-Bayes analyses of deep networks and reduces generalization analysis to standard variational inference (VI) - or, in the special case of a point posterior, maximum a posteriori (MAP) learning leveraging familiar optimization methods with interpretable guarantees. Specifically, the empir-
XE AB,(rs(0))+KLL T=xp(-CArg(0))
ical risk and KL complexity terms jointly form VI objective:
X(1-E)
Its optimal posterior is exactly the Gibbs distribution given explicitly by the Vonsker-Varadhan formula: p(0) x (0) exp( (O)s At optimality, the objective equals ZeA 2, where X(1-E)
ΣμΛ f (0) exp( (33rss()(()) d0. For risks bounded in [0, 1]. this quantity naturally lies in [0, 1] (since (1 Za/Zex < 1), ensuring the bound is inherently non-vacuous. In fact, even the data- independent variational principle remains non-vacuous at optimality, though it is less optimal than the data-dependent version: inf, (f)r + {L(p)))} = - log E [e (x=)r=(0] E [0, 1). since Eg-r Ar)) [ 1]. Its optimal distribution coincides exactly with the Gibbs posterior of the data-dependent case (with the same inverse temperature À ). Additional penalty terms explicitly account for confidence and finite-sample estimation effects.

---

The variance-sensitive denominator 0 < 1 att
structured as "linear term minus variance-driven penalty," " arises naturally from the Bernstein-type inequality in our PAC-Bayes bound. smaller denominator indicates greater uncertainty in the empirical risk estimate, thereby enforcing stronger regularization to avoid overly confident posterior solutions. Hyperparameters and Ç discretize the optimization space for À and ç, allowing optimization while preventing overfitting. Because g(x) is almost linear when its argument small, the combined term g( A c'v collapses to roughly& 1/2 CN whenever the denominator is kept near 1. Allowing that denominator to fall by at most 2c(a-()
a-E
CN
CN
from one then leads to the easy rule of thumb À
a+ę
The previous theorem provides rigorous yet computationally challenging generalization guarantee. To operationalize this result practically, we propose a computationally efficient stochastic gradient descent (SGD) algorithm with partitioned posterior sampling, detailed in Algorithm [ At each iteration, the algorithm partitions the current mini-batch into K sub-batches and independently samples network parameters for each partition. This parallelized approach yields stable Monte
Carlo estimates ofempirical posterior risk plfm)), the structural term (T.(p)T). and the localization normalizer log Ex (e [ (via the one-sided prior-sampling bound used in Eq. 3. without needing to buffer historical parameter snapshots across iterations. Consequently, this approach significantly enhances computational stability, reduces memory overhead, and improves scalability.
The computational overhead per iteration remains modest (typically 1.1x-1.3x a standard SGD step). scaling sub-linearly with the partition count K when shards are fused/batched across the sample axis. Empirically, choosing moderate partition size (e.g., K [4, 8)) provides an effective balance between statistical accuracy and computational cost. The optimization jointly updates the posterior parameters and key bound parameters (A, E), with hyperparameters (a, () controlling the discretization granularity used the uniformization step (cf. 3). facilitating efficient optimization. Overall, the proposed algorithm integrates seamlessly into standard neural network training workflows, effectively balancing theoretical rigor with practical usability and providing computationally efficient and theoretically sound generalization guarantees.
Algorithm 1: Empirical PAC-Bayes SGD with Partitioned Posterior Sampling
Input: Data mini-batches B, (X,, Yt) for i 1:T, initial parameters (ø, X, {), prior x,
partition/posterio--ssapp count K, prior MC size M, learning rate 7), discretization hyperparameters a, and confidence level
Output: Final parameters (Ø, A, {) and PAC-Bayes bound (Eq. 3
Initialize: Posterior distribution Pa-
for t t= 1....... T do
Split mini-batch B, into K shards of size **m KB (reuse the same B, for all estimators this step).
/* Posterior MC on shards (vectorizable/fused across a sample axis) */
Draw 0....., 0g Ps and evaluate shard risks obtain pmmm] (Setup):
From the same } and layer log-densities, compute (p](TT (Setup);
/* Prior MC for the localization log-moment (no grads to Φ)
Draw Ú,,..., 0M ~ н on B. and compute π [(--(Aim] (Setup); use this value (and its concentration radius from Eq. 3 only in the prior term and 6, with stop-gradient w.r.t.
(grads to X, E allowed).
Form the per-step objective L, the RHS of Eq. with plug-in -lug-in estimators plFm.) (L(p))
log Tle Tfe-EAmm), and 5 (using K, M, m. (.
/* Update (project to feasible set to keep denominator positive)
(d), X) <- (,)
(o..x.)) Lri project (), onto
{1-5 S 0, 1 a- o(
ÇN CN 0).
Notes: (i) Fuse the K posterior samples across a leading "sample" axis to keep GEMMs efficient; (ii) use small M (e.g.. 8-16) since prior MC is forward-only: (iii) typical overhead is
1.1x-1.3x x a standard step when K E [4, 8); (iv) clamp log arguments as usual for numerical
safety and clip le [(Am)]] away from using the same floor as Appendix A.1
5

---

Given a PAC-Bayes bound on population risk Ep < B, we can turn it into a per-prediction guarantee using Markov's inequality and union bound. For any input DD the loss of posterior-sampled or averaged model satisfies:
P Pa-D (((()),)) > B/c se.
This allows the user to flag or reject high-risk predictions during deployment, while guaranteeing that such rejections are rare- assuming deployment data matches training distribution. It's particularly useful for adversarial filtering, data drift detection, and model monitoring, where spikes in rejection rates indicate mismatch or failure. No retraining is required; the certificate is derived directly from the posterior and the bound.
Machine learning practitioners often follow standard training protocols-sude regularized stochas- tic gradient descent (SGD)-anm and observe consistent generalization performance across replications. This empirical stability raises a fundamental question: how does regularization contribute to generalization, and can we provide a formal guarantee grounded in PAC-Bayes theory? To address this, we model neural network training as a stochastic differential equation (SDE) defined by its initialization and SGD update schema. Since marginalizing this SDE to compute the posterior ordinary differential equation
density (f) is intractable, we approximate it by constructing (ODE) whose marginal distribution matches that of the SDE in expectation. This approximation is derived by applying the -eakcc--lanck equation and assuming diagonal structure for the posterior variance, with Hutchinson's 's estimator used to approximate the trace of the Hessian. The resulting log-posterior can be updated via simple recurrence:
log 1t+1 (0) log (e) "e +10,01)))++))))
where T/r the learning rate at step f, is the L2 regularization coefficient, and He is the generalized local curvature matrix given by: H, V [(0.) + L.
In practice, we estimate Tr(H,) using Hutchinson's method with Rademacher noise: sample random vector & {=1}d, compute the Hessian- vector product He via nested autodiff, and estimate the trace v Hzv. This fast, biased update rule tracks the contraction of log-density along the training trajectory, and when inserted into the PAC-Bayes bound (Theorem (.11) yields nonvacuous generalization guarantees-ever without explicitly minimizing the bound.
While we showed deep networks trained with SGD can yield nonvacuous empirical PAC-Bayes generalization guarantees, our deeper question is: can neural networks generalize in the highly overparameterized regimes where classical complexity theory would suggest overfitting, and if so, why and in what sense? The answer lies in the structure imposed by modern training: stochastic optimization from random initialization induces posterior that is not arbitrary, but aligned with low-risk, low-complexity regions. The next result formalizes this idea. It shows that, in wide networks trained under standard conditions, the PAC-Bayes generalization gap converges exponentially at rate OLL/N + 1/n),, where n. is network width and N is training data size, and the learned distribution remains close to a Gibbs posterior over a tractable linear approximation.
Specifically, consider a neural network of width n, trained via stochastic gradient descent (SGD) with step size 17 Tu/n from a Neural Tangent Kernel-style initialization (scaled such that activations remain stable as network width grows). To ensure controlled convergence, assume input norms are bounded or bounded with high probability, activation functions have bounded first- and second-order derivatives, and the initial empirical kernel is positive definite with eigenvalues uniformly bounded away from zero and infinity. Under these mild assumptions typically met by standard deep networks, we state informally the following PAC-Bayes generalization guarantee. A formal statement and proof appear in the appendix.
Theorem 3.2 (PAC-Bayes Bound for Wide Networks, Informal). Under these assumptions. with probability at least 1 - E, the expected population risk under the posterior distribution induced by SGD satisfies:
(A (^+ 8) p p.((( + CKL. + +log
[R(] <
A- K N
Here CKT./n is the oracle penalty from replacing the nonlinear network by its linearization; it scales as O(1 because the per-step Gaussian KL between the two SGD increment laws is quadratic in their lazy-training drift.

---

Proof sketch. To establish tight generalization guarantee for wide neural networks, we first ap- proximate the complicated nonlinear training dynamics by simpler linearized network at ini- tialization. Under standard NTK (neural tangent kernel) cnnditionsbbuuddee activations and derivatives, stable NTK, and appropriate learning rate scaling-Ssandard the network becomes wider (larger width n),, the original nonlinear training and its linearized ap- proximation remain very close, differing only by small O(n-1/2) amounts in their predictions and kemels. We then model each stochastic gradient descent (SGD) update as a step drawn from Gaussian distribution, using known results from the neural network literature. Since the KL divergence between two Gaussian distributions grows quadratically with the difference in their parameters, these small O(n ((2)) differences translate into even smaller ((1/n) KL terms per step. More precisely, if one-step SGD updates are modeled as Gaussians with mean/covariance perturbations Apt, AΣ, between the nonlinear and linearized dynamics, a second-order expansion _
-ttandadd theory ensures that as
around equality gives KL, - Ar E Ap: +
1/2 AE,,, F
+ (14mall ||E,,))))
with || : || O (n 1/3), this yields per-step KT, = (1//n). Because the prediction shrinks quickly during training, summing these small KI. terms over the entire trajectory remains just ((1/n) (n) Finally, by plugging this linearized approximation into our localized PAC-Bayes bound (Theorem 3.1), we obtain a generalization guarantee that shrinks significantly as the network width increases, providing a rigorous yet practical certificate that the trained network's 's true error remains close to its empirical training error. For full details, see Appendix A.2
4 Experiments
In this section, we present experiments to assess the behavior of the proposed localized PAC- MAC-Bayes method. We first examine performance standard benchmark datasets and models commonly studied in PAC-Bayes literature. Subsequently, we extend the evaluation to more recent tasks in deep learning, illustrating practical integration of the PAC-Bayes approach into modern workflows. Detailed experimental configurations and hyperparameters are provided in Appendix B
4.1 Classic Benchmarks and Localization Behavior
We begin our empirical evaluation by demonstrating the effectiveness, interpretability, and practical tightness our localized PAC-Bayes bound on classic benchmarks. We explicitly compare our localized method against both traditional data-independent and recent data-dependent PAC-Bayes approaches, clearly diffcrentiating between one-pass and two-pass frameworks.
Our evaluation spans widely-used datasets such as MNIST 20 CIFAR-10/100 21 and ImageNet
22
utilizing common network architectures including fully connected networks (FCN), LeNet-5
23
ResNet-50 [24]. Wide ResNet (WRN-28-18) 225. DenseNet- 121 [26), and EfficientNet-BO
27
We contrast several PAC-Bayes bounds: classical data-independent bounds [77, two-pass
data-dependent bounds using weight compression 28), sesgherinformaaion--aasss methods [29], and
our proposed localized PAC-Bayes method, which efficiently constructs a data-informed tilted prior.
Results summarized in Table
Table 1: Empirical evaluation of PAC-Bayes bounds across datasets and architectures. Columns show dataset, model architecture, empirical error (Train/Test), and PAC-Bayes bounds categorized by method type: (1) Classical (data- indeeeinde,,,,nt,, one-pass). (2) Compression (data- deeenddep,n,nnt, two-pass voopass), (3) Fisher Information (data-dependent, two-pass), and (4) Localized (ours, data-dependent, one- pass). Empirical errors based on best predictor (posterior mean or sampled).
Dataset
Architecture
Error (Tn/Tst)
Classical
Compression
Fisher Info
Localized (ours)
MNIST
FCN
0.1% / 1.2%
5.5%
2.5%
2.1%
1.9% (0.3%)
MNIST
LeNet-5
0.9% 1.1%
4.2%
2.0%
1.7%
1.5% (0.2%)
CIFAR-10
ResNet-50
8.0% /9.5%
45.0%
20.0%
18.5%
11.5% (1.5%)
CIFAR-10 10
WRN-28-1P 10
7.0% / 8.0%
39.0%
18.0%
17.0%
9.5% (1.0%)
CIFAR- 100
DenseNet-121
25.5% / 27.0%
Vacuous
44.0%
44.5%
29.5% (2.0%)
CIFAR- 100
EffiiientNet-Bf BO
25.5% 26.5%
Vacuous
45.0%
44.0%
27.0% (2.0%)
ImageNet
ResNet-50
25.0%
27.0%
Vacuous
47.0%
46.0%
31.0% (2.5%)
ImageNet
EfficientNet
31.0% 32.5%
Vacuous
50.0%
48.0%
35.5% (2.5%)

---

Figure I visualizes training dynamics for CIFAR-10 using WRN-28-10 10, highlighting how empirical metrics (aceuracy, loss) and PAC-Bayes bounds evolve over training epochs. The localization param- eters (A, 5) exhibit intuitive convergence behavior, indicating seamless integration into conventional SGD workflows. Specifically, À stabilizes at an effective regularization strength, while & decreases gradually to minimal yet meaningful level.
Selecting moderate localization parameters (c.g., 2500, 0.01) effectively uses information from approximately 25 data points. This minimal yet strategic localization substantially tightens the PAC-Bayes bound without risking overfitting, illustrating balanced and practically beneficial approach.
4.2 Extending PAC-Bayes to Modern Deep Learning Tasks
Having demonstrated the effectiveness of our localized PAC-Bayes bound classical benchmarks, we now illustrate its practical application modern deep learning scenarios. We highlight how our method seamlessly integrates PAC-Bayes certification into standard workflows by directly substituting traditional training objectives (such as cross-entropy) with PAC-Bayes-based loss objectives.
We begin with the Cityscapes semantic segmentation task [30], which is vital for applications like autonomous driving. Semantic segmentation naturally fits PAC-Bayes certification because of its bounded per-pixel classification loss. We use lightweight U-Net with ResNet backbone, trained on standard TensorFlow Datasets, and evaluate performance via Intersection-over Union (loU). Our PAC- Bayes certification is seamlessly incorporated into the training process by probabilistically modeling convolutional and fully connected layers, leaving task-specific segmentation heads deterministic. Table 2 confirms confirs that our method achieves tight, practical certification bounds, making it valuable for deployment in safety-critical applications.
Concurrently, we showcase our PAC-Bayes certification on NLP fine-tuning tasks from the GLUE benchmark [31]: MRPC (paraphrase classification), SST-2 (sentiment classification), and RTE (textual entailment). These tasks highlight the growing reliance on fine-tuning foundation models with limited labeled data, where conventional validation metrics fall short in providing formal safety guarantees. We employ LoRA [32] fine-tuning GPT-2-small, explicitly modeling low-rank adapter parameters as Gibbs distributions via reparameterization. By directly replacing standard fine-tuning losses with our PAC-Bayes bounds, achieve rigorous generalization guarantees suitable for reliable NLP deployments.
We summarize experimental results in Table
Table Empirical results demonstrating that our localized PAC-Bayes bounds yield tighter, practi- cally meaningful generalization guarantees compared to two-pass PAC-Bayes methods across diverse tasks. Columns show task/dataset, architecture/model, empirical loss (Train/Val), and PAC-Bayes loss bounds: Two-pass and Localized (ours, one-pass).
Task/Dataset
Model
Loss (Train/Val)
Two-pass
Localized (ours)
Cityscapes
U-Net (ResNet)
0.22 / 0.25
0.30
0.27
MRPC
GPT-2 + LoRA
0.15 / 0.14
0.16
0.15
SST-2
GPT-2 + LoRA
0.08 / 0.11
0.14
0.14
RTE
GPT-2 + LoRA
0.22 / 0.25
0.28
0.26
We compare our localized PAC-Bayes bound against a two-pass PAC-Bayes approach that first trains model conventionally and then separately computes data-dependent prior. The experimental results summarized Table 2 highlight our method's advantages clearly. Our localized PAC- MAy-Bayes bounds consistently provide tighter and practically meaningful generalization guarantees compared to the two-pass PAC-Bayes approaches. These findings underscore our method's ' ability to bridge theoretical rigor and real-world practicality effectively.
4.3 Certifying Individual Predictions and Adversarial Robustness
Our PAC-Bayes bound allows us to set precise risk-based threshold for individual predictions derived directly from our certified model, utilizing Markov's inequality and union-bount argument

---

Callrratin Individual Predictions
L045
Poor
Figure 1: Training dynamics
Figure 2: PAC-Bayes 0-1 risk Figure 3: Calibration of indi- distributions for normal. OOD, vidual predictions across various and adversarial data (PGD tasks. tack).
and PAC-Bayes bound evolution (CIFAR-10, WRN-28-10).
(Eq. 4. Predictions exceeding this threshold can be reliably flagged or discarded, ensuring we retain only trustworthy predictions while tightly controlling the rejection rate.
We empirically demonstrate this selective prediction approach by examining risk distributions for correctly classified versus misclassified test samples. Figure[Zshows PAC-Bayes 0-1 risk distributions
for normal, outto--dissribution (OOD; primarily using ImageNet-32x32 33 $4 ), and adversarial
(PGD attack (35) examples. Clearly, adversarially perturbed samples exhibit substantially higher risk values compared to normal and OOD samples, highlighting our method's practical capability to robustly detect and reject adversarial inputs.
Additionally, we evaluate the calibration (36] of our PAC-Bayes-certfffee predictions (Figure 3 Across diverse practical tasks (Cityscapes, MRPC, RTE, SST-2), our models exhibit excellent calibra- tion, meaning that predicted uncertainties closely match observed error frequencies. This accurate calibration underscores the reliability and interpretability of PAC-Bayes-cerre the selective rejection mechanism is both trustworthy and effective in real-world deployments.
predictions, ensuring
Together, these results demonstrate the practical strength of our PAC-Bayes framework-proveee providing rigorous individual-level guarantees, robust detection of adversarial attacks, and well-calibrated predictive uncertainties essential for dependable model deployment.
Related Work
PAC-Bayes theory provides a rigorous probabilistic framework for deriving generalization guarantees. overcoming many limitations of classical VC-dimension and Rademacher complexity- -based analyses
17 37.. Classical PAC-Bayes bounds often use data-independent priors, resulting in empirically
vacuous or excessively loose guarantees when applied to modern deep neural networks [37 38
Conversely, theoretical advancements, such as localization techniques developed by Catoni 6 provide mathematically elegant and tighter bounds, but often remain disconnected from practical machine learning workflows.
Recent works aim bridge this gap by introducing data-dependent priors surrogate optimization methods. For instance, weight-compressionn approaches improve tightness significantly by exploiting sparsity or compressibility of neural networks 29 28). Nevertheless, these methods typically require
multiple optimization stages or additional computational overhead, limiting their practical adoption
40 38
Similarly, Fisher information-base and Neural Tangent Kernel (NTK) -baeed PAC-Bayes methods further tighten generalization guarantees through approximations of the local geometry of loss landscapes [1 19.. These methods generally rely on strong assumptions (e.g.. wide-networt limits linear approximations), thus restricting their applicability in diverse realistic training scenarios.
Other contemporary efforts operationalize PAC-Bayes bounds within specialized contexts such reinforeement learning, conformal prediction, and meta-learning 42 43 44 However, these

---

methods often remain computationally intensive, niche-specific, or challenging to integrate directly into conventional deep learning training loops.
Our work explicitly bridges this gap by introducing a localized PAC-Bayes bound that naturally integrates theoretical rigor (inspired by techniques such as Catoni's localization) into standard deep learning workflows. This approach avoids multiple optimization passes and excessive computa- tional costs, offering practically meaningful and empirically tight generalization guarantees directly applicable to modern neural networks.
Limitations and Broader Impacts
Limitations. Our localized PAC-Bayes certification relies on Monte Carlo estimation (with repa- rameterization) of the prior log- mo-mmmtet log Ez [c-(Ar=(9) in Theorem 3.1 and, when evaluating the Gibbs-minimized form, to approximate structured losses as differences between log-partition functions, i.e., I (log ET (rree((-(Ars(0)) tent, using finite samples may introduce a negative bias due to Jensen's inequality, potentially risking overfitting. Accordingly, our bound uses one-sided, high-probabilltyy upper surrogates for log E e [+] (see Eq. 3 via 6) to avoid optimistic bias, at the cost of extra conservativeness. more accurate but computationally intensive alternative integrates posterior expectations continuously
- log ET (e(eex((Arss()))
While statistically consis-
over inverse temperatures, i.e., Je En-stexpt pArg(e)) [0) d,3, by sampling from intermediate Gibbs
posteriors Texp(-8Xree This multi-temperature estimator reduces logarithmic bias but increases sampling cost. Thus, our chosen two-endpoint method represents a pragmatic balance between accuracy and computational efficiency. Additionally, efficient GPU parallelization is critical; careless implementation- -usiiiioonsuuhhhheee such as sequential rather than batched forward passes can significantly degrade computational performance.
Broader Impacts. Our work improves transparency and trustworthiness of neural network pre- dictions, particularly valuable for large foundation models and generative agentic Al deployed in safety-critcaal and regulated domains, such as healthcare and autonomous driving. Rigorous PAC-Bayee certification enables responsible deployment, facilitating regulatory compliance and safer adoption of advanced AI systems. However, as PAC-Bayes certificates inherently depend on assumptions- such representative training data and accuracy of practical approximations used in peseementaiionmmiiitteepprp
these assumptions can lead to misuse and false confidence. Clear communication about these assumptions, limitations, and proper interpretation guidelines is critical to responsibly leverage the benefits of our approach while mitigating potential negative consequences.
Conclusions
We have developed practical PAC-Bayes certification method that addresses key computational and conceptual obstacles previously limiting PAC-Bayes applicability to modern neural networks. Our localized prior approach enables tight certification of generalization risks at both network and srtividual-predicctin levels without significantly altering standard training workflows. Empirical results demonstrate strong certification performance across image classification, NLP fine-tuning, and semantic segmentation, closely aligning theoretical guarantees with real-world applications and regulatory needs. This advancement transforms PAC-Bayes theory into a practical tool for reliably certifying deep learning models, substantially improving trustworthiness and transparency in safety-critical Al deployments.
Disclaimer
The views expressed are those of the authors and do not reflect the official guidance or position of the United States Govermment, the Department of Defense or of the United States Air Force. The content or appearance of hyperlinks does not reflect an official DoD, Air Force, Air Force Research Laboratory position endorsement of the external websites, or the information, products, or services contained therein. This work was conducted in the authors' personal capacity, on personal time, and without the use of employer U.S. Government resources.
10

---

References
[1] David A. McAllester. PAC-Bayesian model averaging. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pages 164-170. ACM, 1999.
[2] David A. McAllester. PAC-Bayesian stochastic model selection. Machine Learning, 51(1):
5-21, 2003.
[3] John Langford and Matthias Seeger. Bounds for averaging classifiers. Technical Report CMU-CS-01-102. Carnegie Mellon University, 2001.
[4] Matthias Seeger. PAC-Bayesian generalisation error bounds for Gaussian process classification. Journal of machine learning research, 3(Oct):233- 2002.
[5] Olivier Catoni. A PAC- MAC-saaesi approach to adaptive classification. preprint LPMA 840, 2003,
[6] Olivier Catoni. PAC-Bayesiad supervised classification: the thermodynamics of statistical learning, volume 56 of Institute of Mathematical Statisties Lecture Notes Monograph Series. Institute of Mathematical Statistics, Beachwood, OH, 2007.
[7] Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approxi- mations of Gibbs posteriors. Journal of Machine Learning Research, 17(239):1-41 2016.
[8] Gintare Karolina Dziugaite and Daniel M. Roy. Data-dependent PAC-Bayes priors via dif- ferential privacy. In Advances in Neural Information Processing Systems, pages 8430-8441, 2018.
[9] Vladimir Vapnik. Statistical learning theory. Wiley-Blackwell, 1998.
[10] Andreas Maurer. note on the PAC Bayesian theorem. httts://arxiv.cr www.ariii....ooaaaooooooo abs/ es/ 0411099 2004.
[11] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non- vacuous generalization bounds at the imagenet scale: A pac-bayesian compression approach. In International Conference Learning Representations (ICLR), 2019. URL https://
openrevies
[12] Yujia Wang, Vitaly Feldman, and Chicheng Wang. Differentially private PAC-Bayes generaliza- tion bounds. Advances in Neural Information Processing Systems (NeurIPS), 35:40469 40483,
2022. fttpss/ss:///ppp / net//fouummiii _____-m---- 73aD
[13] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
[14] Peter I. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities.
Annals of Statisties, 199-)33497 2005.
[15] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. In Proceedings of the 22nd Annual Conference on Learning Theory (COL.7), 2009.
[16] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[17] David A McAllester. Some pac-bayesian theorems. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pages 230-234, 1999.
[18] Benjamin Guedj. A primer on PAC- Bay-Bay learning. In Proceedings of the second congress of the French Mathematical Society, 2019.
[19] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[20] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online], 2010. Available: http:: //yann lecun. com/ exdb/mniss
[21] Alex Krizhevsky. Learning multiple layers of features from tiny images. In Master's thesis, Department of Computer Science, University of Toronto, 2009.
[22] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEFE Conference on Computer Vision and Pattern Recognition, pages 248-255. IEEE, 2009.

---

[23]
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (1:2278-22224 1998.
[24] Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[25] Sergey Zagoruyko and Nikos Komodakis. 16Xiv:1605.07144 2016.
Wide residual networks.
arXiv preprint
[26] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 4700 2017.
[27] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. International conference on machine learning, pages 6105-6114. PMLR, 2019.
[28] Sanjeev Arora et al. Stronger generalization bounds for deep nets via a compression approach. In ICML, 2018.
[29] Yuchen Zhou, Yuxin Wu, Behnam Neyshabur, and Nathan Srebro. Non-vacuous generaliza- tion bounds at the imagenet scale: A pac- pac-bayesian compression approach. In International Conference on Learning Representations, 2018.
[30] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 3213-3223, 2016.
[31] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNIPP: Analyzing and Interpreting Neural Networks for NLP, pages 353-355, 2018.
[32] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models, 2021. arXiv preprint arXiv:2106.09685.
[33] Patryk Chrabaszez, Ily Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprini arXiv: 100.:0/777.08819 2017.
[34] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and distribuuti examples neural networks. International Conference on Learning Representations, 2017.
[35] Aleksander Madry, Alcksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference on Learning Representations, 2018
[36] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. International conference on machine learning, pages 1321-1330. PMLR, 2017.
[37] Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2017.
[38] Maria Pérez-Ortiz, Osvaldo Rivasplata. John Shawe- Taylor, and Csaba Szepesvári. Tighter risk certificates for neural networks. pettps://arxivv. orgg abs abs/ 2007 12911 2020.
[39] Andrew Y.K. Foong, Wessel P. Bruinsma, David R. Burt, and Richard E. Turner. How tight can pac-bayes be in the small data regime? In Advances in Neural Information Processing Systems, volume 35, 2021. httL:htt:///arstt http::::///xxivoor//abbb/ee attp///s/220006 01011100660022222
[40] Antoine Picard, Roman Moscoviz, and Benjamin Guedj. Learning via surrogate pac-bayes, In Advances in Neural Information Processing Systems, volume 37, pages 53390-53417, 2025. URL htttps://neurrpp::p
[41] Zifeng Wang. Shao Lun Huang, Fircan F. Kuruoglu, Jimeng Sun, Xi Chen, and Yefeng Zheng Pac-bayes information bottleneck. International Conference on Learning Representations,
2022. URL htLphttps:: /// //wrxxiv.vvvv///////// org org/pdf///ii/ /2199 14509.
12

---

[42] Anirudha Majumdar and Maxwell Goldstein. Pac-bayes control: Synthesizing controllers that provably generalize to novel environments. In Conference on Robot Learning, pages 293-305. PMLR, 2018. URL.pttt://prrceeddng mlr press//88mmajjmdaaa htt:/mmjjummaa 1acieaarrraa//a 1aaamajumdar jmddar 18a
v87
pdf
[43] Apoorva Sharma, Sushant Veer, Asher Hancock, Heng Yang, Marco Pavone, and Anirudha Majumdar. Pac-bayes generalization certificates for inductive conformal prediction. In Advances in Neural Information Processing Systems, volume 36, 2023. URL https://arxiv org/
p23/2 046218
[44] Jonas Rothfuss, Vincent Fortuin, Martin Josifoski, and Andreas Krause. Pacoh: Bayes-optimal meta-learning with pac-guarantees. In International Conference Machine Learning, pages mlr htt.://caaa..........eee//s///ss
9116-9126. PMLR, 2021.
rothfuss21a.ppe pdf
13

---

with a focus on A Proofs and Formal Statements
This section gives formal statements and complete proofs of Theorems 3.1 and 3.2 the theory and all notation and assumptions made explicit.
A.1 Formal Statement and Proof of Theorem 3.1
Before formally stating Theorem 3.1, we briefly review the essential notation to ensure clarity and readability. We denote by θ measurable parameter space. The true data-generating distribution over the input-output pairs (I, y) is denoted by P. from which we have a training dataset {(2s, yi) vx)) H drawn independently and identically from P.
Given parameters 0 O, consider bounded loss function E(O; v),, satisfying 0 ((0; x. y) S 1 for all 0, x, y- We define the population risk R(0) ((z,))~p(((0; x, y)], and the empirical risk (0) = + Σ -i=1 200; 91).
We consider distributions over the parameter space θ, with the prior distribution denoted by (0). and the posterior distribution denoted by p(0). The mullback-Leibbee (KL) divergence between these two distributions is given by KL(p, x) = So p(0) log न( dO.
To refine generalization guarantees practically, we introduce the concept a lucalized prior, defined as data-dependent prior distribution: "exp (0))
(0)) (0) x I(0) (xx(-()rs(00)] Here, the parame- ters À > 0 and < 5 < 1 control the concentration of this prior around empirically promising param- eter regions. We utilize Bernstein-type concentration inequality, which controls the bound using second-order and bounded higher-order moments via the auxiliary function g(z) = (e" - x 1)/2²
We introduce two discretization parameters, a E (ç. 1) and ÇE E (E. 1), to define auxiliary grids that evenly distribute the allowed error probability (uniformization): =\t = (a* 1 < k < (N)) = { 0 < k S Logg-, [2N) We then slightly relax this discretization, allowing direct continuous optimization of X and & via gradient-basee methods.
We define the empirical posterior risk estimate p [rs)] as the Monte Carlo estimate of the empirical risk under the posterior p. using K i.i.d. parameter samples 0, p
K
plrsi
(0,))).
K
We estimate the pog-partition term log E [e (0)] with M i.i.d. samples 0 ~
x [te-s
1 M j=l E/e e -Arrs(0,)
M
In practice, approximate the full-dataset risk (0) by the mini-batch risk A, (0), the average loss on a mini-batch of size m (drawn without replacement or as an i.i.d. approximation), and we use the corresponding substitutions p [fm]] and æ [e-SAAm] in the estimators above.
The following theorem bounds the neural network's 's true risk explicitly in terms of empirical risk and complexity estimates defined above.
Theorem 3.1 (Empirical PAC-Bayes Bound). Let k = g(A/(CN)), under the previously defined conditions on localization parameters &, a, the confidence parameter (0, 1). and regularization
parameter À E [1, with the denominator satisfying 0 < 1 até bound on the expected population risk under the posterior distribution p(0) holds with probability at least 1 E:
g (5xx) ÇN S 1, the following
(
E, [R(O)
(phm) + (KL(pl(T) + log (( (e-EXPm) +
CN
where 8=
log(G)A|EE/e)) +(1+E)V 2K
log(G A|EE/e)
+ log 1+ 256
(1-)- /og(G/A||E)/)) 1+E/a log
2M
2|A||
This theorem links training performance, sampling estimates, and statistical penalties to give practical generalization guarantee. The proof follows four steps: (i) restating and proving Catoni's
14

---

learning lemma, (ii) introducing a localized prior, (ii) uniformizing X, E for optimization, and (iv) deriving practical estimators via importance sampling.
We begin by restating Catoni's learning lemma (Lemma A.Ip. foundational to constructing the localized PAC-Bayes bound (Theorem 3.1). This lemma introduces a confidence function m)(0) that quantifies our certainty regarding the parameter 0 in minimizing the true risk, effectively localizing the small-event probability budget towards more promising parameters. states that, with high probability over the training sample, no posterior distribution can significantly deviate from its empirical risk [r)] beyond a confidence interval determined by the complexity term (I(pl(=) and the expected confidence Ep]n(
Lemma A.1 (Catoni, 2007(51) For any positive real parameter À > 0, any measurable function 7: θ + R, and any prior probability distribution т on θ we have:
P sup XE, XEpp/s(0)) - Ep(n(0)] - (T(p)==) 2 0f
(5)
exp ( (5) R(0)(1 R(O) n(0))
E
Similarly,
sup XE, [R()] -Ep[n(0)] - (L(pITT) 2 0
P
(6)
S Eg
exp
[ ( R(0) -(0))
Proof of Lemma A.1
We begin with the following identity based on the Donsker-Varadhan varia- tional representation of the KL divergence:
s (E,( r0) Ep[n(0)] (L(p||T) log (Eg [exp (A[R(() rs rs( (-)]-~n(0]]] (0)))
Taking probability explicitly with respect to the random draw of the training set S, we have:
Ps sup
ss{
AE (R(0) - r0) - [,)) - [T((p] 20}
Ps
s
E
lexp (A(R(0) - r0) (0)) 2 1}
Es EST
exp (A(R(0) rrs( (0))]]
ES-
Es jexp (A(R(O) - r0s( (0)]]]
Egna
exp
9 (7) (L)) - -R(O)) -(0)
The first inequality follows from Markov's inequality applied to the random variable Eg [exp (X[R(0)-r)) r0] 104--11 r7())) The subsequent equality follows by Fubini's theorem applied to the positive function (6. S) + exp (A[R(0) r0) - n)d)). The final inequality results from Bernstein's 's inequality applied to the random variables é (0; .r., ... where g(z) = (c" x 1) /a² is standard auxiliary function arising from Bernstein's 's inequality. This function explicitly pro- vides refined control over the tail behavior through second-order moments and higher-order moment bounds.
For the reverse inequality, we similarly start from the Vonsker-Varadhan variational representation of the KL divergence:
sup (r)( R(0)] - [n)) KT(p)T=> log (Eaーn (exp (Alrs(0) R(O) - (0))))
Taking probability explicitly with respect the dataset S, we have:
Ps- sup (xprrs(()) R(0)] - Ex(r(0)) (L(p) (L(()))))) 20
Ps Egwn (exp (O) - R(0)] (0))) 11
Es Eg exp (0(rs(0)- R(O)] - (0))]]
Emgr Es jexp (0( - R(O)] - (0)0]
Ba-n eepp | (+) (1 - -R(O)- - ]
15

---

We proceed to construct PAC-Bayes bound with localized prior from Catoni's 's learning lemma A.1 following Catoni's idea of localization.
Proof of Theorem 3.1
Localizing the Prior Using Population Risk Information. We begin by explicitly choosing confidence function v)(0) as if we already had knowledge of the true risk R(0):
X² (0) RR(O) - log ) log(c")), where x. = g (x)
The first term encodes our confidence from Bernstein's 's inequality that empirical risk closely approxi- mates the population risk, simplifying the variance term R(0)[1 R(0)] R(0) for convenience. The second term, log -exp(-8R(0)) (R(()) (0) R + log m(cxp(-8R(e))) differentially penalizes parameter regions based on their proximity to empirical optima: parameters far from the optimum incur looser penalty, while those near the optimum experience tighter localization. The final term for notational simplicity.
provides uniform confidence control. We define x = g x+)
Substitute (0) into Eq. 5 in Lemma A.1 then relax the Bernstein bound X ( R(O) - R(O) 2
in the exponent by N N R(O) the right-hand side. This relaxation effectively simplifies the expression involving ())) leaving only the term explicitly on the right-hand side, thus yielding
Ps
Ps{sup/ sup (A- (A-B-x E
R(O))) 2 log(( {t)) S c,
i.., with probability at least 1 e, the following bound holds for all posterior distributions p: [p[R(()) S (A - B- - x
[r()] KI.(pll=) + log (exp((((((((()))))) + log({)) (7)
Bounding the Log-Partition Function via Empirical Risk. The log-partition term log(r(exp(-3 R(0)]}} in the above BAC-Bayes incquality cannot be optimized directly since involves the unknown population risk R(0). To resolve this, aim to replace with bound in- volving the known empirical risk (0) To achieve this, we start by applying the Donsker- Varadhan Donsker-Varadhan expectation under the Gibbs
variational formula to explicitly express the term in question
posterior Texp(=AR((1))
[og(T(expp R(O)))) = - E ( [R(0)] KL (TTTeoo(-
The unknown expectation term E. asce)
[[O)] can be bounded in terms of the empirical risk using the inequality from Eq. of Lemma With probability least -c, we have: [R()) s
Vp. Applying this inequality specifically to the Gibbs posterior
*+ * we obtain the following bound with probability at least 1 - E:
A
x log - X n
E [R(O)] E E
rs(0)
N
Substituting this result back into the expression for the log-partition function yields, with probability at least 1 -
log log( (exp(-8 R(O))))
- E. Essoppe OR(O))
[R(O]] KL (Texp(-
(8)
1
< E
Tuxen (R((0)))(0))
rs(
log
KL KL (T(Np))(--R
A + k
x N
A
x2 N
B
Epprss(0)] + log(1/e)
5 sup
A
(L((llT)
1 11 K N
3
}]}
B
1
log
π exp
(1 K N
(0)
log
À +
k
N
16

---

Here, the second inequality follows directly from the definition of supremum by allowing the posterior distribution to vary freely. The final equality is obtained by re-applying the Nonsker-Varadlae formula, now transforming the supremum back into a simpler log oog-pariitoon function explicitly involving the empirical risk (0))
Applying a union bound to the earlier localized PAC-Bayes bound (Eq. 7 specifically, using the deviation bound (Eq. S control the log-partition term involving the unknown population risk
and introducing the substitution ç
9
we obtain:
x(++*))*
Ps sup ((1- - 5)* - (1 E) X E - (Eplrs(0)) (LL()) - log E [exp( (oon--((((0)]]] 2
N
P
(1 + (2)l)((2e-))) 16-1 Se.
Equivalently, with probability at least - e, the following PAC-Bayes bound holds for all posterior distributions p:
[p[R(0]] A [Ep(rs(0) + (L(pl log E eexp (-(rs((0)) + (1 log(()
(1 - E) (1 + x
Simplitying with a Localized Prior. Next, we use the following identity involving KL divergences: (T((pl log (xxx(((((x(s(0)) KL. (pl((ex)(-EArss) EA (p))())))),
where the distribution (exp((CAr=((0)) (0) x (0) exp( ((rs()))( is a localized, data-dependent prior.
With this simplification, obtain the following explicit PAC-Bayes bound: with probability least 1 e, for all posterior distributions
[[()] S -1- E) (rssE + KL (pl Teeeppp-rrra + (1 log
(1- (1 x
The identity relating the KL divergences be explicitly verified through the following derivation:
log p())
log p(0)/ Tonn (E)
(L(p E,
= Ep
T0))
T0)) Tepp(- (0)
Ep log p())
log exp(p(Xxss (O) [expp((AAx
Texp(-EArs) (Ars) Ep
T(0)
Ep log exp( exp(-EXrs(O))
KT. (pli
E, (exp(((Ars(O))
KL. (pl( (r,,(rs(0)) - log E (cxp(-EArs
Uniformizing the Bound for Continuous Optimization. To practically optimize the parameters and using stochastic gradient descent (SGD), we first apply union bound across discrete parameter grids. Specifically, we discretize the parameters onto finite sets, defining grids: A = {2Nç* 0 < S |log (2N)J} for with 0 < Ç < 1, and =\t (a** S < [log,-1(N)) (N)J} for & with 0 < < 1. We then evenly distribute the allowable failure probability across all grid points, ensuring with probability at least e that the PAC-Bayes bound simultaneously holds for every
discrete combination X' E and g E E satisfying the condition
(1 - g¹) - -1 E' > 0:
XEp[rs] + KL (pl(=) + log E e e'Xrs
+ (1 + 5¹) log 2 A
[p[R(0)] <
(1 -1- (1-5') X (1 (1+ {7) x
The factor | explicitly accounts for the union bound over the discrete grids of X' and g¹. We used the identity KT. (pl( KL (p, .) EXE, [rs] log E,, [A-s)
Next, we relax these discrete conditions to continuous parameters À E [1, 2N and & E [0. 1) by
selecting their nearest grid points X' A and g e E such that X < X' < a and E < g < 5
17

---

Thus, we obtain continuous optimization-friendiy PAC-Bayes bound: With probability at least
1 6, for all continuous parameters [1, and & (0,1) satisfying the relaxed condition
(1 -1- -) - (1+ )) )²)² > O, we have:
Eplrs [0)]
[KL (pl(T) + log E, (-e' + 1+5/a log 2|
Ep(R(O)
(10)
(1-5/a a- (N)
This relaxation is crucial since permits direct optimization of À and via gradient-based methods like SGD, making the bound highly practical for numerical implementations.
Estimation of expectations with respect to p and rT, and empirical risk by mini-batch. The p-/n-dependent parts of the numerator is (1+ E,Ess + (KL (p, T) + log Es |e- (e-()s)). We
approximate each expectation using Monte Carlo sampling and concentration inequalities.
For the posterior expectation term Ep [rs], we draw K independent samples 0g from the posterior p. and estimate the empirical risk the simple average p|rs] * Σ rss (0,). Using Hoeffding's inequality (since each loss is bounded in [0.1]] D). we have, with probability at least cpp
Ep (rss S p(rs)
log(1/eo) 2K
Similarly, estimate the localization term log E, [e-SArs]
draw M independent samples 0, from the prior æ,, and compute the empirical average [e- " Ei=ıe (0,) Using Hoeffding's s inequality again (since the function e (A) is always between e EA and ), we have
with probability at least 1- cr. we have E [e EArs] = EATT]+ (1+((1111 -(A) v 2M
(1/e)/))) Taking
logs (monotone), we obtain the one-sided upper bound:
log E [e -rrr] & log
Tee TTe-sAis) [Ais] + (1 -1-c e
log log(1/em)
2M
log [e-eArs] + log 1+
(1-e- x 2ar-
log(1/em)
2M
Next we replace the full-dataset risk (0) by mini- batch confidence bounds that preserve the required one-sidedness. Let (0) be the average loss f E [0, 1] on a mini-batch of size m drawn without replacement. to upper-bound p-expectation, we use Hoeffding to get, w.p. at least 1 -
(0( S (0) +
log(1/er) 2m
To upper-bound Ex, [e- (Ar())((0)] note that EArr is decreasing in and lower bound rs (0) gives upper bound exp (-EArs(0) E [0, 1] with probability at least
E,::
(1/el/e.) 2m
+ exp (-EArs(0) S exp (-EA (fm(() (1g(e/).)
(0) 2 (m)
2m
Split the failure probabilities so that the final event has probability 2 e, we allocate
Ep = Ex = E
to the three estimation events (posterior MC, prior MC, mini-batch x2).
and 'gri = to all earlier failure probabilities in Eq. 10 Let the X-grid have size A| and the E-grid
have size | To make each estimation event hold simultaneously for all grid pairs (X, E). apply union bound over the grid and replace every tail probability 6, inside the one-sided Hoeffding bounds by e./ El) This is equivalent replacing each log (1/ea) appearing in the MC/ mini-batch radii by log (( ((AJ))) /e.). With our allocation Ep En common factor log All/ee)
e/6, all three radii pick up the
Concretely, using the same mini-batch of size m for all samples in a step and writing [fmm
1 D/= i' (0.) and n CArs] NV ΣØ - (0,), the three estimation penalties combine to
K
(o((6)A|[3/+)) 2K
log [+)
1 log [+ (1-c EA)
log |og
EV
27
2m
X
x(e eAPmm
2M
18

---

We also need the uniformization penalty that does not come from MC. This is the standard term that ensures the localized Catoni inequality holds simultaneously over the (A, E)-rid itself (independently of the MC estimation). Allocating 'grid e/3 and union-bounding over the grid yields an additive
contribution of 1+5/2 log 6|A]
E
Apply a union bound across the p p- MC, the π - MC, the mini-batch confidence intervals, and the localized Catoni inequality across grids (A, E), we achieve a fully implementable empirical PAC-Bayes generalization bound, w.p. 2 21- -
E [[[]](]] - (1 1 (1
a+t
{flmml + a (KL(a, TT + log (e (--AAim))
+8)
where d=v
[og +(++5)
[og(G|A]] (c)
1 2m X
log 1+ (1-e Ea)
(3//))//E//) 1+5/0
log 2|
2K
x/e EXFm
2M
A
We have presented a PAC-Bayes generalization bound suitable for practical optimization. Beginning with Catoni's general PAC-Bayes lemma, we incorporated a localized, data-dependent prior to sharpen the bound, replaced unknown population risks with empirical approximations, and applied uniform discretization over hyperparameters to enable direct optimization via stochastic gradient descent. Finally, we introduced Monte Carlo and importance sampling methods for numerical estimation, providing explicit, implementable approach for evaluating and enhancing neural network generalization performance within the PAC-Bayes framework.
Discussion: Optimality of the Gibbs Posterior
The empirical PAC-Bayes bound (Eq. 9 at its minimal can be expressed neatly as a difference of log-partition functions. Specifically, with probability least 1 e, have
Ep[R(O)] - log π (exp(( Ars (0)) + log ffeep(--xxpMMee (0) (1 ( E) (1 + x)x
(1 (xxp((()
log 2
To see this optimality, recall the Donsker-Varadhan variational formula, which states that the infimum of the objective [Eplrs(O)] + KL(pl=) over all posterior distributions p is precisely -log π (e)x This infimum is uniquely attained by the Gibbs posterior distribution, xx0) exp((Ar=(() parameterized by the inverse temperature x. Substitut- given explicitly by (0) = F., [oxpo (())
ing this optimal posterior p² (0) into the PAC-Bayes bound directly yields the minimal achievable
bound, characterized by the difference-of-log wwr----oo-prattio----eee functions form: log ল
log π
Discussion: Bias of the Log-Sum-Exp Estimator and Integral Form Alternative
The log-partition function log r(cxp(-EArs(O)) in our bound is practically esti- mated using importance sampling with posterior samples: log n (exp(((Ars(O))IIS
log ii= 1 (xp((ee))-))))
This estimator, however, is biased due Jensen's
p(O.)
inequality applied to the concave logarithm function. Specifically, since E[log(X)] < log(E E[X]), taking the log after averaging inherently introduces negative bias. Thus, while consistent as K + oc, this estimator systematically underestimates the true bog-partition function for finite sample sizes.
To obtain an unbiased alternative, we utilize the fundamental theorem of calculus. Observe that:
log ffeex((-xxxxrp -rrs (0)) log (erxpp(((xs(()))) = / d3
d
log (oxp(((xx(8'rs( d3'.
Evaluating the derivative inside explicitly, we have:
d
log ((oep(((33rs(()) E B [rs(0)].
d3
8'r8)
Thus, the integral form becomes:
llog क (eeexp((Ars(0))) + log (eexp((=Exrs(0))
E Ex -grg) (rs( d3'.
Jex
19

---

Applying the substitution 8 = BA, we simplify to:
Excap parg) (rs d3.
To numerically estimate this integral form unbiasedly, discretize the integral using numerical quadrature rule with points 8 evenly spaced in [g. 1]. For each By, we draw samples f independently from the corresponding Gibbs posterior distribution Texp(-8)Ars) and then form the Monte Carlo estimator:
K
K
Emexpt (arg) (0) A(1 5
(5())))
This estimator is unbiased by construction, as it directly estimates the expectation within the integral without applying nonlinear transformations.
The Nog-sum-exp estimator requires only K samples from single posterior, thus is computationally efficient but biased. The integral-based estimator requires sampling from // different Gibbs posteriors, yielding a total of x K samples, thus it unbiased but computationally more demanding. Choosing between the two methods involves balancing the trade-off between estimator bias and computational resources.
Compared to the log- -ug-sumexp estimator, the integral form estimator directly estimates expected risks at multiple intermediate Gibbs posteriors, avoiding logarithmic bias entirely. However, it requires drawing samples from multiple Gibbs posteriors (J K total samples), thus increasing computational cost significantly compared the log-sum-exp method, which uses only samples from a single posterior. Choosing between the two involves trade-off: the integral estimator is unbiased but computationally heavier, whereas the log-sum-exp estimator is computationally efficient but biased.
20

---

A.2 Formal Statement and Proof of Theorem 3.2
We begin by briefly summarizing notation and key assumptions required for formally stating Theorem 3.2. Consider an (L + 1l-layer feedforward neural network f(:,0) with parameter vector & θ S
R 19, The parameter 9 explicitly includes all layer-wise weights and biases, given by:
= [Wi, by 1
where each layer is computed as
(x fi (Wix bi), 1 I=.....,4 with fL+1 being identity.
We have training dataset S {( yr) y drawn independently and identically from the data- generating distribution D. Inputs are collected as X' {z, } and outputs as y y= {y
Assume a bounded loss function x, y) [0. 1]. We define the population risk R(0) and empirical risk r() explicitly as: R())= ( p [ x, y) and r(0) = Σi E(O; x4, ys).
Next, consider linearized approximation of the original neural network around initialization Op: (, f(. (=)(() 0o)-
Define an approximate loss i(0; v, y) based on this linearized model, with its corresponding approxi- mate population risk R((0) and approximate empirical risk F(0) given explicitly by:
R()) (( F(0) 1
(0: v.).
We explicitly define the model approximation error emodel (0) as the worst-case difference between the original loss and the approximate loss, satisfying uniformly:
1e(0;,,)) x, ē(0; w)1 (0).
This quantity measures the approximation gap induced by linearizing the neural network.
We introduce prior and posterior distributions (0) and p(0), respectively. Gibbs-type posterior distributions are defined explicitly as:
Txpp( (exp(-Arstie (6) (0() exp(- exp(- "h "exp((98(0)) (0) क (0) exp(-3R(0)),
for parameters x,3 > 0. The Kullhack-Leehllrr divergence is denoted explicitly by:
p(0)
KL(pl()) = p(0) log
d0.
x(0)
We explicitly assume the following standard conditions:
I.....,L L 13 has weights (A1) (Gaussian Initialization and Bounded Inputs). Each layer / E {1...., and biases initialized independent Gaussian distributions:
W Win N (0, o2 1)
T--1
with input dimension ne, hidden layer widths nı, and inputs xa bounded sub-Gaussian. There exist finite constants Cur Co. Cap > 0, such that with high probability:
[ Vng
||xo||
WW < Cw
Th 7I-1
<
Cbob,
S
Czg-
Vno
(A2) (Bounded Width Ratios), Layer widths ny maintain uniformly bounded ratios; explicitly, there 0 such that:
exist constants Cmin Cmax
Cmin < < Cmaxx:
V,
thus O(n) (Vl).
np
21

---

(A3) (Pasitive Definiteness of Infinite- NTK). Define explicitly the empirical Neural Tangent Kernel (NTK) iteration as:
V Vol 0,), (2V
Assume the -ifinite-width NTK limit O lim @ is strictly positive definite, with eigenvalues bounded away from and oc. Explicitly, there exist constants Amin I Amax < oo such that:
A
O lim
O AmaxIN-
(A4) (Bounded Activations and Derivatives), Each layer activation function fi. [ I,..., L. has explicitly bounded magnitude and bounded first and second derivatives:
lf((O) < co; | < co,
Il < cc.
(A5) (Controlled Learning Rate), Stochastic gradient descent parameter updates are given explicitly
by: 02 = 01-1 17Vor(( with learning rate 17 no/n, where the step-size factor i/o satisfies:
7o S Amin + Amax
strictly below the NTK stability threshold.
(A6) (Smooth, non-degenerate minibatch noise). Stochastic gradient updates can be written as
Oct1 O2 - 17 ((.) ((.,) + (O.), (l,)(0.) =
with conditional covariance (0.) (0.( 0,). Assume: (i) Non-degenerucy: there exist constants < mmin I mmax < x independent of width n such that, for all 1, the linearized covariance satisfies mind < >mm mmxx (ii) Lipschitz smoothness: there is Lx oc with
[0) (0'' & Ls|10 0' 2 for all 0,0'.
(If needed in practice, adding an infinitesimal isotropic jitter to updates enforces (i) without affecting training.)
With this notation and under these assumptions, we formally state Theorem 3.2:
Theorem 3.2 (PAC-Bayes Bound for Wide Networks, Formal), Under assumptions (A1)-(66, for any choice of regularization parameter X >> O, localization parameter & E [0, 1), confidence level
E (0, 1), and sufficiently large training size N satisfying < <1 - ( N S the following
bound on the expected population risk under the Gibbs posterior distribution Texp(->r(0)) induced
by stochastic gradient descent holds with probability at least 1 1
E E Ar) [R(O)] < ((1 +-)((}))) E, [R(()) + [T-EJA (SKL (Stt+ +log +log())))
(1-
where g(x) = (exp(x)- 1 and CKI. is constant independent of network width n and
training size N.
We start by stating and proving the following localized oracle PAC-Bayes bounds using proxy models. While our usage of this lemma is to show that as network width grows unbounded, a neural network trained from random initialization with stochastic gradient descent generalizes well as its simpler linear approximation at initialization, these bounds extend to various deep learning scenarios where proxy or approximate models address challenges like con-differentiable metrics, complex loss landscapes, unlabeled data, knowledge distillation, unstable reinforcement signals, and differentiable relaxations of hard constraints. Our theorems build on Catoni's 's localization idea but incorporate approximate losses, assuming the true loss is controlled by these approximations.
Lemma A.2 (PAC-Bayes oracle bound with approximate population risk). With previously defined notation. for any posterior distribution p(0), prior (()), and inverse temperature X > 0. the expected population risk under the Gibbs posterior TI Tespl- (exp(->r(()) satisfies the following bound with probability at least - & over the draw of the training sample S
E ETTepp(AAr(o) [R(0)] <
(11)
A x Ep [i(0) + emodal (0) -KL(p)(T) + log Ex (exp(-B(i(()) emodal (0)))
log
2
K
22

---

Proof of Lemma A.2 We begin by picking the same confidence function ny0) in the proof of Theorem 3.1 as if we already knew the true risk R(0):
X²
00) R(()) log ( log(c log(<")), where = (x²)
N
In this function, the first term encodes certainty that the empirical risk r(0) is close to R(O), effectively absorbing the Bernstein-type bound & 9 (x) R[0)[1 - R(0) on the right-hand side of the rare event in Eq. 5n Lemma A. The second term allots a portion of the confidence budget proportionally to R()). controlled by positive parameter that dictates the "localization" strength. 0 is far from minimizer-we can afford looser confidence interval because we care less about ensuring r(0) 2 R(O). Conversely, R()) is small, we impose a tighter bound near the minimizer. The final term log(e provides uniform confidence shift in the tail event once we have accounted for the uncertainty in r(f) and in choosing 8.
If R(() is large-meantne
Although this choice of n)) presupposes knowing R(O), we eventually eliminate that assumption by relaxing R(0) with r0) using the reverse bound from the same learning lemma.
Substitute (0) into Eq. 5 in Lemma A.1 yields the following bound, which holds for all posterior
distributions P with probability least
Ep (R()) S (A B > XEE [0)] (Il() + (og(fr(xp(-33((0) + log(!))
The right hand side of Eq.
7 is minimized at the Gibbs distribution Texp(- Texp(-Ar(0))- in which case sup, Epl- (r])] [I(p = log E E (r(o)) (exp(-Ar(0))
inf, E, (+) (pl (
X2 N
Åx (R()] -
3 k
+
(<)
x2
inf
X B
{mrl((0) + KT(p 1og([[ log (e })}
N
2 N
B K
[Av[r(0)] + k(pp
log (e
To form theoretical bound using the approximate risk R(0), we need to upper-bound both Ep[r(0) and log (E, (exp(-BR(O))). By approximation, we have
log (E,, (exp(-3R(0))) S log Ex Texp (-3(R(()- <model (0)))
Moreover, from Eq. in Lemma with probability at least
- E:
12
EE((((0] S A
E, [R(] + log (1)
X x
E, (i(( + Emodel (0) + log (t)
By union bound, we get Eq. Further using the identity
<L(pp| + log E exp (R(()) (m)od
KL (pll (=) ((m))))))))))))) - BE [ū(0) Emodel (0)},
we obtain the localize oracle bound with approximate population risk: with probability at least 1
X²
X2
A 3
E E [R(O)] <
A
+
k
Ep [T(0)()) + fmodel())
N
N
+ KL (pll exxpTexp( (m)))(()))) ET)(((0) - (0)] + log (2)
special case is when (model()) is constant. In that case:
(x- X -
X²
-1
EsTexst An) [R(0)] <
N
A2 { 1 [p[R(0)]+ + (L(P](T) + log Ex (exp(=>R(0))) + +(*+
2² N
N +B Emodel + log (3)
23

---

With Lemma A.2. we prove Theorem 3.2 in the following steps. Throughout, we apply triangle inequalities, Mauchy-Schward assumptions (A6).
cedduct-diffeeen identities, and random matrix bounds under
(i) Bounding activation and its sensitivity. A forward recursion for each layer / inductively shows that (0) Olyni) and [0x (x)l S ( |00 ØI) A similar backward recursion yields ()) = xL+1 = O(1) and []6x(0) - (()) = O(1@ @]])-
(i Bounding Jacobian and NTK. By applying the chain rule each activation-ssessiivity product, one obtains - and Vo](X, 0) VoJ(2 - -) (v ØI). Expressing the empirical NTK é,, the parameter iterate Oc, and the risk r(0) in terms of the same activation- sensitivity- expansions, and then iterating over SGD steps, shows ||ê, - Ooll = 0 (a)).
110e doll = 0 (..) and [,, 8,) y Jo ) Ro.
(iii) Comparing network vs. linearized updates. By expanding f(0,) - flin ) in terms of b, - Oo and (00:-1)- ((n()00-1) and then telescoping, we obtain (0. ( (0:)1l = O / (1 no Auiin ) 3
parallel argument in parameter space shows |10, اساا -
(iv) Bounding KL divergence between original and linearized learning. Although Og is not strictly Gaussian, each small Gaussian increment can be compared to that of 0 via the chain rule for KL divergence. This requires bounding log-det ratios of covariance updates (through log-matrix expansions) and bounding trace terms involving the precision matrices and the second-moment difference. Both steps rely on the empirical NTK converging to a strictly positive-definite limit, yielding (L p! S (
(v) Bounding complexity in theoretical PAC-Bayes. Since the model approximation penalty -
and the KI. divergence D exxp(= R)) are both ( combining these N sample-size term completes the proof of rates on the order of 1 (width) and 1 N (data).
with the 1
We now formalize the five-step argument outlined above. Let 0n denote the random initialization of the network parameters, and let 0g be the parameter iterate after steps of stochastic gradient descent (SGD). Define the linearized network around fg by
Iin (x, 0) (X, 00) + Vol (X, (0- (0)
and let 8ttH be the corresponding parameter iterate from gradient descent on flin, with the same initialization and step size. We will show:
110, 10,-0 11--0-11--0 o ( (1.) (0.)
and KL (plTTep((
(
m
and then apply the PAC-Bayes bound conclude.
Proof. Before proving Step (i), establish high-probability bounds weights, biases, and inputs implied by assumption \ textbf { (A1)). Each weight matrix W, and bias vector by is drawn from a scaled Gaussian distribution, and inputs Xo either bounded sub-Gaussian. Consequently, with high probability 1 Et, we have:
[Wil S Cwo
|b:l| S Chory
n1-1
for constants Cw, C. > O. provided n; 2 - log E and mi-1
is bounded. Likewise, the input norm
satisfies ||xo|| < Cro with probability 1 8n in the sub-Gaussian case.
In practice, such input conditions are met through preprocessing (e.g., centering, rescaling, or clipping). Applying union bound across all layers, conclude that probability at least 1 Σ El and for sufficiently large the following initialization bounds hold simultancously:
Will S Cwo
nI T4-1
1
by S Clas.
|
ll S
Cap
Tno
24

---

(i) Bounding activations and their sensitivities.
Starting from no - I Czgz can recursively bound n441 -1/2 x 1ll C21+1
Cayaa with
|1 Cr aw + Cbos) + [f(0)):
||-=I|| = Ilf+1 (W++1x/ + b1+1) |I - |l (|| + b(+1ll) + /n(+if((0)
<I (1 | + (b:++1])) ((0)
<1Iff (Cwow V Ca, v Chony + (
=vn (ol (Cw O2 C + [f())))
Starting from no -1/2 (x)(0) 1x - xo(0)]l
s Cesso |10 0||. we can recur-
sively bound M1+1 -1/2 1=11211x110 ||x|+1 8) Xx+1 0)11
S Cd ||0 01 with Cdn
(Cazn Cw + Cr. / mn/nni11 + 1/ /
[|x(+1(X0 (Xo. - Xx,1 1)1 |lf( 8) + b(+1) -f [(W(+1x((xx) 0) + b(+1)ll (Wi+) x + b (W++1 (xo: 0) + b(+1))
< <||
< Ill (IW [xx 0) (x0, 0) + W1111 W [xx, 0)1 + || Bi41ll)
$
I11f'll (Cuow V 1441/m/ Caz, you + Cz / + 1) 110 1 Ø1
-vm4i 110 - 0|| ||00 (Cian (Cann Tw + Czyy v m1/n441 + 1/ ///T+T))
Let ((() = X (0), Starting from |11+11|| I Co we can recursively bound || s Cs, with
Co. = Cb443 Cwo m1t2/nn
[|0: 0)1 = 18141 (x0, W) S [| 0)1 |[ = Co Cwo / Ar11
= =(Chu11 Cw ow V ni+1
Starting from [| (Xo, 0) - 81t1 (x0, 0)1 = 0 S Cabz 110 - Ö1[. we can recursively bound
||ó (xo, 0) 6x(x0, 0)]l s Cas, 10 Ö11, where Cas, = Cabr Cu Ter Be+1 + +o
[xo, 0) - 6x 0)هl = ||01+1 W - 8141(20. 0) W4ill
(dL+1 0) - 5i+1 (xo, 0)) W (0+1(200 0) (W4+1 - WHi)
< <Cb644 ||0 Ø|| Cwowy m141 + Co 110 011
=I1e Ø|| (Cab.. Cw Tw
mit1 Cāut).
m
Thus, under the same union bound of events for Wr[], n 1/2 [b:l] no -/ we have:
1/2 |x|||| < Ca., ni
-1/2 | (xo, 0) xi 0)1l S Can, |10 Ø11
|| S Ca,, [|o 0) & (xo, 8i1l < Cas, 110 - -11-
(ii Bounding the network Jacobian and empirical NTK.
25

---

The Jacobian of network output with respect to the parameters can be bounded by
(max) m²) an)-1/2
1/2 110xx+1lle S CC,, where C2 = |1 / E
C% C2
C
max;
maxi Ty
180x1+1118
Σ [1xxx dfag(f") (Öw. Wix + biill + 110xxx diag(f") (Öb, W + biill
$ Σ | || 1 + 1 11
Σ Cg.
|1 nh- 22 +0 11
C2
max 1
T4-1
C C2
x
max
maxi TM
The difference of the Jacobians can be bounded by (max: mi) 1/2 |00x 00xrt1ll S
Carll0 - Ø1| where Cas = =V E
maxi (Cas, Czy-1 + Co, Cra)
11-1
Cab.:
100x++1 - 0281+1112
Σ (0xx (f hi) - (0x,51+1) diag(( 10)ll
hi) (0,, x1+1) diag (hi (fi) hu))
(xo 0) (hx)) (x..0)) (x ding( (h: xx (xx..) (h))) diag((
S (Cc,,11100001111111 11o- C +C 11 11 110-01 01 vo +C II Cot -o
+(Cas,
1I 110--1))
< maxn: 10 - 01
Σ
n--1 Car + Co 2x,)²++ max 71
Ca6.
max 171
Consequently, with high probability, the Frobenius norm of the network's Jacobian (scaled by 1/ // /maxi ni ) is bounded by constant Cj,, and the difference of these scaled Jacobians is Lipschitz in 0 with Lipschitz constant Caj- Equivalently, unscaled, both the Jacobian and the Lipschitz constant scale on the order of /maxx ni, where max; ny denotes the network's width. Formally,
(max 1
112
1/2 |100x1+11 S CJ, (max -1/2 1/2 00xx (xo, 0) 0g 00x
(x0, (xo, 0
S Carllo - Ō1
Under the mean-squared error (MSE) objective, one iteration of gradient descent updates 0 0, 17 Vof(X, (
Since , Vof(X 0,) V (X 0.), we have
1(X 0.+1 - f(X 0.) = (x, (F(X -)) -- (S(X, -V).
If θ, stays close to a positive-definite limit O this induces a contraction factor ||. - m s
1 2o Amin Hence the residue decreases exponentially in training step
[{ >'1 < (1 no Amni
[l 6.) - Vl1-
It also follows that |10; 0oll < C, +// Aunin
3 [| - 31ll by summer over parameter steps t:
10++1 Bell < 7/0
(1 no Amiia
) '11((2(,6) - 3/1-
Vof(XX || 0.) - 211 S noCs vn.
3
26

---

Throughout the training, the distance of the empirical NTK from its initialization is controlled by 1 Amin
@ - 6,
Ca2 1f(22, Bb) - 3'1l v where
F
@00 6.11 = n
Vot (2, (o. -
1 (IVof (X, 0b)1 Vol (x, (X, 00) (x 7 + Vof (x) Vos (X, 66)1 V (X, (1))
$ n
603Cas 1f((2,)) - - nn
- Cas 116 - 0
Amin
(iii) Comparing the network linearized updates.
In what follows, we characterize the gap between the network's prediction error g(0++1) = f(X' 0e+1)= - y and the prediction error of its linear approximation at initialization (0=+1)))) = flim 0++1)= - y by examining how the gap at each previous training step accumulates throughout training. Our goal is to bound this gap in terms of the network width and the training step.
g (m 1) 1(0++1)
[ (0.) dog lin (0:) g((,)) n00)
(0,) - g(O,)) Qn (0.) g(0,)) +oo (0o 6.) g(0,)
[ 00 ) (4 bm (0.) - g(0,)) + no (0o -- 6.) g(0,)
(1 no 1m (6o - 6.) g(Oa).
710
It follows that the gap between the network's prediction error (i.e., the network's 's output minus the target) and the error of its linear approximation at initialization decreases exponentially with each training step. Moreover, this gap scales on the order of 1/ Vn. where is the network's 's width.
l1g lin (fc+1) g(f++1)ll
I no n0 1-
-|600 -.11 [l)(
Sm10
Σ
modmiu
f-8 3 Ro 11/2
1/2 (1- Modauin )
Ro
3
Amin
3
Amin
6K 12
<
1
1/2
3
Auain
The gap between the network's parameters and those its linear approximation stems from dif- ferences in both the prediction error and the Jacobian of the network output with respect to the parameters. At each training step, these discrepancies accumulate across all previous iterations, as shown by the summation of the terms involving (im().)) g(0.) and Vof 0.) Vef(X, 0o).
27

---

@ 12+1 = [0.th V (2 (0.)] 10, Vof(( (,
= (0) 0z) - ls aV fiim (x, 0.)9 "M (0.)
7 Vel (x (0.) (o)(x,00)g(03)
V lin (x) (0)) (Vof(X) - 9(0.)
==0
Vef(2, (0 g(0.)) (Vo5(x.0.) Vef(22,00) g(a))
==0
It follows that 10lin 01+1/l
Sn
Vof(X,,0)) (| (0.) - -((0)) Cas 10, Boll [l9().)]
770
Csvns
(1- (1-7dmmin
6C3Car11300
Vn + Carvn
3
(1 (1- 70
Ro
3
Amin
Amiin vn
3
9
+ Cas R 3
1
Ro
Amin
TiA22.
Amin
AoAmin
(iv) Bounding the KL divergence between original and linearized learning.
We compare the one-step update laws of the original and linearized trainings. Model single SGD update at time t by Gaussians pf = / ( + Apt, Σg + AE,) for the nonlinear dynamics and d: / (He, E,) for the linearized dynamics. Under (A1)- the NTK/lazy tariazyy--riingggggt tube gives || (8,) J (8o)ll.p
(n 1/2), , g!t O (n (n-1/2). 1/2). ). and ||9.1| decays geometrically. With
7 = no/ /o/ n. this implies the mean-update gap Aμt: = - [J (0.)* 9. J (0o) g.th is O(1/n) (each bracketed term is O(1), multiplied by 1 no/n ). Assumption (A6). 2 and the O (n-1/2) parameter drift yield || || = O (n (1/)), and (A6). lets us pre-whiten by 1/1/2 to get O (n 1/2)) A second-order expansion of the Gaussian KL around equality
Σ 1E-//2A,, A 1/2
(zero gap) then gives
KL
/ Au Σ Ap.
1/2 + (1AAmll + I1AE))P))
With ||T'|las bounded (A6.1), the first term O(1/n) because Ap ((/n)) and the second is O(1/n) because the pre-whitened Frobenius norm is O 1/2). Summing over steps preserves the ((1/n) order thanks to the geometric decay of [|g:]|- The key reason we obtain O(1/n) (rather than P(1/vn) is that the KL's leading terms are quadratic in the small O (n/1 normalized perturbations, so squaring them yields O(1/n). This O(1/n) trajectory-level discrepancy then passed, by data processing, to the posteriors inside the localized PAC-Bayes bound, which adds only an explicit C/(An) oracle penalty top of the linearized risk.
(v) Applying the PAC-Bayes argument.
Let R(0) be the (linearized) proxy risk. Since - mismatch in the loss is O(1/n). Likewise, we have DKL. (pll eexpp= Ro) = (11m)) Substituting these terms into the standard PAC- BAC-Bayes bound gives:
- flim = 0(1/V)), the actual model
Er [()) (11
CKL log (2)) / (1 (1=1))()))
+ (1-E)X
which completes the proof of the claimed order- n. (width) and order- Y/4 (sample size) complexity terms under assumptions (A1)
28

---

B Experimental Details
We describe the standard experimental configurations used for the benchmarks and tasks presented in Section 4 All models are trained using widely adopted protocols from their respective foundational papers or community baselines. Training is performed on a single NVIDIA A100 GPU, with batch sizes and runtimes selected to ensure convergence within approximately 24 hours. No data augmenta- tion or enhancement is applied beyond basic preprocessing to ensure consistency in accounting for dataset size when evaluating PAC-Bayes generalization bounds.
B.1 Vision Benchmarks
MNIST. We evaluate two classic architectures for MNIST digit classification: fully connected network (FCN) with three hidden layers of 600 ReLU units each, and LeNet-5(23). which consists of two convolutional layers (6 and 16 filters of size 5x5), followed by two fully connected layers with 120 and 84 units, and 10-way softmax output. Input images are normalized to the range [0, 1], with no data augmentation. We train each model using the Adam optimizer with initial learning rate 1 x 10-3, batch size 128, and cross-entropp loss for 100 epochs. Learning rate is decayed by factor of 0.1 at epochs 60 and 90. No dropout, batch normalization, or regularization is applied.
CIFAR-10/100. We consider three standard architectures: ResNet-50 24), WideResNet-288 10 25 and DenseNet-BC--eee (2.00-1[[2].... Input images are normalized channel-wise using CIFAR- 10 statistics (mean = [0.491, 0.482, 0.447], std = [0.247, 0.243, 0.262J). No data augmentation (e.g.. crop- ping. flipping, MixUp, CutMix) is used to maintain countable sample size for PAC-Bayes analysis. Reference implementations for all listed CIFAR models, including ResNet, VGG, GoogLeNet, Mo- bileNet, NretctResNet, ShuffleNet, and DenseNet, are available in the kuanglauupyoordh-ciffa repository.
The ResNet-50 used here is the CIFAR variant, where the initial 7 X 7 conv and max pooling are replaced with a single 3 3 conv, and the downsampling stages follow the 6n + 2 bottleneck pattern with increasing channel widths (16, 32, 64). We use SGD with Nesterov momentum (0.9), weight decay 5 x 10-4, and batch size 128. The initial learning rate is 0.1, decayed by a factor of 0.2 at epochs 60, 120, and 160. Total training lasts 200 epochs.
WRN-28-10 10 widens all convolutional blocks by factor of 10 and follows the pre-activation design (BN-ReLUU-Con)) A dropout of 0.3 is applied between convolutional layers within residual blocks. The network is trained using the same optimizer and schedule as above.
For DenseNet-BC, we follow the L = 100, k = 12 configuration. The model consists of three dense blocks interleaved with transition layers that apply 1 x 1 convolution and 2 x 2 average pooling. Bottleneck layers and compression (growth rate reduction) are applied as in the original paper. Dropout of 0.2 is used throughout. Training uses SGD with momentum 0.9, batch size 128, initial learning rate 0.1, and learning rate drops at epochs 150 and 225, for a total of 300 epochs.
ImageNet. We evaluate ResNet-500 (4], DenseNet- 121 26), and EfficientNer-BOl 27 on ImageNet- 1k. Images resized to 256x256 via bicubic interpolation. At training time, random crops of size 224x224 and horizontal flips are applied once per image. At test time, center crops of 224x224 are used. Pixel values are normalized using ImageNet mean and standard deviation (mean [0.485, 0.456, 0.406), std = [0.229, 0.224, 0.225J).
ResNer-50 follows the standard configuration with a 7 x 7 initial convolution (stride 2), max pooling, four stages of bottleneck residual blocks with channel sizes [256, 512, 1024, 2048], and global average pooling before the classifier. DenseNet- 121 consists of four dense blocks with growth rate 32, compression at transition layers, and bottleneck layers with 1 x 1 convolutions. EfficientNet-B0 and compound scaling.
uses inverted bottleneck MBConv blocks with squezze-and-xxiieee
Models are trained for 120 epochs using SGD with momentum 0.9, initial learning rate 0.1, and batch size 256. The learning rate decays by a factor of 10 at epochs 30, 60, and 90. No label smoothing, RandAugment, MixUp, or repeated augmentation is used, Each model completes training in approximately two days. Reference implementations for ResNet, DenseNet, and EfficientNet are available in torchvision. models, keras . applicationnni and timm, with ImageNet training pipelines provided in repositories such as pytorch/ www./eeeaeeeaaaeeeeeeeeeeeeeeeee immggeeet..
29

---

B.2 Semantic Segmentation
We evaluate semantic segmentation on the Cityscapes dataset using a standard U-Net architecture with ImageNeet-reetrinee ResNet-34 encoder. Images are resized to 256x512, center-cropped if necessary, and normalized using Cityscapes mean and standard deviation. The model follows the encoder-decoder pattern with skip connections between symmetric encoder and decoder blocks, each containing two convolutional layers followed by batch normalization and ReLU activations. The decoder upsamples spatial resolution using transposed convolutions.
Training is performed using the Adam optimizer (learning rate x 10-4, batch size 8) for 100 epochs. We use pixel-wise cross-entropy loss over 19 semantic classes. No label smoothing augmentation applied. All layers are probabilistic except the final segmentation head, which remains deterministic. We evaluate performance on the validation set using mean Intersection-over-Unre using pixel-wise cross-entropy loss and evaluate using mloU, following standard Cityscapes protocol. Our PAC-Bayes bound formally applies to the expected cros--enrropy loss, which correlates well with mloU in practice. Our configuration is consistent with widely used U-Net implementations such pytorch.
(mloU), We train
keras-unet-collectioo and aegmentation_modieee
B.3 GLUE Fine-tuning with GPT-2 + LoRA
We fine-tune GPT-2-small (124M parameters) on three classification tasks from the GLUE benchmark MRPC. SST-2, and RTE-using parameter-efficient fine-tuning setup with LoRA 32]. Our protocol builds standard GPT-2 token classification with causal language modeling: each input is serialized as prompt (e.g., "sentencel <sep> sentence2") followed by label token ("Yes", "No", "Positive", etc.). and the model is trained using next-token coss-entropy loss over the label position. This formulation enables us to reuse standard language model heads without modifying the decoder architecture.
We adopt the GPT-2 tokenizer with maximum sequence length of 128 tokens and batch size 32. We A with learning rate 2 x 10-5, 81 0.9, /2 = 0.98, and 10-8 Weight decay is set to zero, and training runs for 10 epochs unless early stopping is triggered. Our setup follows the Keras example Parameter-efficient fine-tuning of GPT-2 with LoRA httpt:tt///// /wwass.e.s..//e///ee 1o/ http/xxmplee/////e // parameter_ .ff effficient....... inneuningg_ot ltapinnggg__________2___ 1i122_wtth__. wwwhtwhttlrrrtreel lora/ and Hugging Face's s adapter-based fine-tuning pipelines, with GPT-2 checkpoints loaded from the Hugging Face model hub.
We inject LoRA adapters into the GPT-2 self- attention blocks, targeting the query and value projection matrices in each transformer layer. Each LoRA module is rank-4 adapter with scaling factor 32 and dropout 0.05. The base GPT-2 weights remain frozen throughout training. For classification, we project the final token's hidden state onto softmax over verbalized class tokens (e.g., "Yes", "No"), computing loss on the generated token. This verbalizer-based approach avoids architectural changes while preserving interpretability.
To apply our localized PAC-Bayes bound, we replace the standard loss with a variational objective defined over the LoRA parameters. These adapters are reparameterized Gaussian posteriors, and the mini-batch/i is partitioned into K = 8 shards. For each shard, we sample LoRA weights and compute predictions, aggregating empirical risk via importance-weighted weighted averaging. KL divergence estimated from the same samples. Bound parameters À and are jointly optimized with the adapter weights using reparameterized sigmoid transformation. The training loop and data pipeline otherwise unchanged, demonstrating that our PAC-Bayes loss integrates seamlessly into standard fine-tuning workflows.
We report training and validation losses as well as PAC-Bayes generalization bounds (Eq. 3)
B.4 PAC-Bayes Training Details
We implement our localized PAC-Bayes training procedure as a drop-in replacement for standard training workflows. Our method defines single-pass objective that integrates importance-weightee weighttd empirical risk estimation with reparameterized posterior sampling and KL regularization, enabling seamless compatibility with Keras, TensorFlow, and analogous PyTorch abstractions.
For each model, we replace standard deterministic layers with variational layers (e.g., reparameterized dense or convolutional layers with learned Gaussian posteriors), where posterior samples are drawn
30

---

using the reparameterization trick. At each training step, the mini-batchi is split into K = 4 shards, and forward passes are used approximate expectations with importance weighting. Our loss replaces the standard cross-entropy loss with PAC-Bayes bound involving data-dependent estimates of empirical risk, KI. divergence, and importance-weighted oog-partition estimate.
To control the bound's tightness and ensure numerical stability, we jointly optimize two scalar parameters (A, E) using reparameterized sigmoid transformations. These parameters are clipped to remain in numerically stable range. The parameter È, in particular, governs the balance between empirical fit and regularization. The bound uses a Bernstein- -ttpe inequality combined with the Donsker- Varadhan variational form to achieve tight guarantees under approximate posterior sampling.
Posterior and prior distributions are modularized the layer level and managed through lightweight wrappers. The full PAC-Bayes loss including posterior sampling and KL. terms, is evaluated during each forward pass and is fully differentiable. In frameworks like Keras, this integrates naturally via model compilation and fitting. In Py PyTorc or JAX, the same logic can be incorporated directly within the standard mini-batch training loop, without requiring two-pass estimation, KL annealing, or external scheduling. This makes our method easily portable across stossttems with minimal changes model or training code.
Our implementation avoids reliance on specialized inference libraries and instead uses lightweight wrappers that expose posterior sampling and KL evaluation in modular form. In PyTorch, these components can be integrated as attributes of standard extttnn.Module classes, enabling straightfor- ward porting of posterior logic into existing model definitions. Our approach parallels existing PEFT (parameter-efffciee) fine-tuning) strategies such as LoRA or Adapter modules, in the sense that "injects" stochastic behavior inside existing model layers without rewriting the full training logic. Crucially, our PAC-Bayes loss is computed inline with the model's forward and backward passes, without requiring separate optimization stages KL annealing. This design allows it to be integrated into standard training loops across architectures and frameworks.
All posterior layers initialized with random priors and appropriate variance scaling. The PAC- Bayes loss is fully compatible with standard Keras callbacks, model checkpointing, and TensorBoard logging.
B.5 Certifiable Prediction
Post-training, we use the same posterior distribution to derive per-example prediction certificates. For each test input, we compute the expected 0-1 loss under posterior sampling via importance-weighted risk estimation. We then apply a single-sample Markov bound and union bound across the test set to produce a certified upper bound on the misclassification risk of each individual prediction, as formalized in Eq.
This certifiable risk enables a rejection mechanism: predictions whose estimated risk exceeds a chosen threshold can be flagged or abstained from, ensuring reliable deployment in safety-critical applications. Our experiments visualize the full risk distribution and demonstrate that adversarial or misclassified samples tend to exhibit significantly higher certified risk than correctly predicted ones. We also evaluate calibration curves and find that PAC-Bayes risk estimates align closely with empirical misclassification rates, supporting their use for uncertainty-awant selective prediction.
B.6 Software and Reproducibility
All models are implemented in TensorFlow 2.12 with Keras 2 and HuggingFace Transformers 4.28 (for GPT-2 LoRA fine-tuning). Training is conducted in Google Colab using a single NVIDIA A100 GPU with 40 GB of memory. To ensure feasibility under Colab constraints, all experiments are designed to complete within single 24-hour session. Our codebase is written R and uses the reti reticulate package to interface with Python modules. Due to compatibility requirements of TensorFlow Probability, we restrict the software environment to Python 3.10 and TensorFlow <=2. Code and configuration scripts for all experiments will be made available upon publication.
31

---

C
Concentration Inequalities and PAC-Bayes Bounds
This section presents self-contained statement and derivation of the key inequalities underlying PAC-Bayes bound. Our goal is to help readers unfamiliar with PAC-Bayes theory or concentration inequalities appreciate the theoretical structure and understand how our bound emerges naturally from classical tools.
We begin with the simplest and most foundational of these: Markov's inequality. It formalizes the intuitive idea that if random variable tends to be small on average, then large values must be rare. This simple insight is the of broad family of results known concentration inequalities, which describe how tightly a random variable tends to concentrate around its average.
Markoy's Inequality. If X 2 0 is nonnegative random variable and >> 0, then:
E[X]
P(X 2 a)
a
Proof. Let A = (X 2 a). Then:
E X(w)dP(w) 2 / x(w)dP(w) 2 adP(w) a P( 2 20)
Dividing both sides by gives the result.
Markov's inequality gives weak but general tail bounds. Its real power emerges when we apply to transformed variables. If large deviations of X are rare, then so are large values of eAx This exponential magnification enables sharper control.
Hoeffding's Inequality. Suppose X1, XI,..., X,, are independent and bounded in [0, 1]. and let = Σ X,. Then for any ε 0:
P(X E 2 E) S exp((22n=).
Proof. Consider X = - X,. E, We apply Markov's inequality to the exponential of the deviation:
P(X - e) P(e2n(X-EII)) E[R] ednr S Ane
D
An -E([))]
By independence, can factor the expectation: EledA(X ([enn(X-1181))) B[X
E Ele
Apply Hoeffding's lemma: for any X₃ E [0, 1]. we have -(X <
A/8 so
EleAn(X [ e²\"/8 Hoeffding's ' lemma follows by applying a second-order Taylor expansion
the moment- coment--enerating function of a bounded random variable and optimizing over the bound on
its range.
Combining this with the previous bound: P(X - E 2 E) e Anc+nA?/S
Minimizing the right-hand side wrt À gives À 4c, yielding: P(X E[X] 2 2) expp-2ne" (ime?).r
Hoeffding's 's inequality provides uniform control over deviations based solely on the bounded range of each variable-it does not consider the variance or how probability mass is distributed within range. In contrast, Bernstein's s inequality makes use of both the variance and a bound on the centered deviations. This allows it to produce tighter bounds when the variance is small, particularly in settings with heterogeneous or skewed noise.
Bernstein's Inequality. Let oI..... NN be independent real-valued random variables, each bounded above by b in deviation from its mean: a; Elo,] & b. Let S x Σ o; the normalized sum, m E[S] its mean, and = E( - E[ax])*] its renormalized variance. Then, for any and any 77 > 0:
V N )2),
P(S - m 2 n) I exp
An +
where g(x)
N
x²
This exponential moment bound captures both the variance and the tail size of the distribution. We use directly in our PAC-Bayes analysis to account for heteroskedasticity and sharp transitions in empirical risk estimates.
32

---

Proof. Let 01...., ON be independent real-valued random variables with E(o;] 14 and di - H4 S
almost surely. Define the empirical average S N Σ di with define the renormalized variance
E [
N Σ Más and
(o p
We begin by applying Markov's inequality to the exponential: for any À > 0,
P(S 2 7) (e((s-m) 2 e>n) Se El [e)((())))]]
By independence, we factor the moment generating function as E(e N Ele
Since each 0j [4i S b, we apply the bound log Eleex] & g(bl) E for X bounded by b and
g(x) -1- to get
N
1
by V
log Ele MS m)
El(o,
mi) g
A.
N
N2
N
Putting everything together:
bd N
V N 12
P(S 2 1) exp
-An +
This bound holds for all À > 0: optimizing it over À yields the standard Bernstein tail bound.
The following Donsker- Donsker-Varadhan Varadhan variational formula connects the moment genneatggnnerating function (i.e., the log of the expected exponentiated f to variational optimization over distributions It is especially powerful when f represents a deviation, such as f0) À (rs(0) R(0)), which is common in PACBayes theory.
The inequality shows that rather than analyzing E, [e'] directly, we upper bound it using any distribution at the cost of a KI. divergence penalty. In PAC-Bayes, serves as the prior and p as the learned posterior, making this identity the key bridge between exponential moment bounds and generalization guarantees.
Vansken-Varadhan Variational Formula. Let be probability distribution over space θ, and let f + R be measurable and integrable under æ. Then:
log [e = sup [E,]f(0) - [L(p]]=}}
where the supremum is taken over all probability measures p absolutely continuous with respect to
Proof. Let < æ (i.e., p is absolutely continuous with respect to æ. meaning p does not assign mass where ı assigns zero), and define the Radon-Nikodym derivative dp/dx h. In continuous spaces, x has a density p(0) and p has density q(0), then h(0) 2(0) is the pointwise ratio densities. p(0)
We write:
/ (())(()) - /
E <T(())=)= -T(e(l))
h(0) log 1())()))z(()))
Define functional J(h)
J(h) = [h / h dr,
subject the constraint f h 1, since P must be probability measure.
Using calculus of variations or Lagrange multipliers to maximize J(h), the optimal (0) satisfies
(())
/ (10) c10)) dz)
f(0) log h ('(()))))) (0) - - 1 0
h0 = Z
Z
Plugging this optimal h- back into the original expression gives
sup (Ep[f) KL(p](m) = log / ( = log E, (ef(0)
claimed.
33

---

The following PAC-Bayes bound, due to Catoni [6]. provides a generalization guarantee for random- ized predictors drawn from a posterior distribution p. terms of their empirical risk and divergence from a prior x. Unlike classical uniform convergence bounds, which struggle with infinite or continu- ous hypothesis spaces, this approach avoids union bounds altogether by reasoning about the expected behavior under p. using the Ponsker-Varadhar variational identity.
Catoni's PAC-Bayes bound Let be a prior distribution over parameters posterior distribution. Assume that for all 0, the loss function {(0; x y) E [0, CJ is bounded. Then for any and E (0, 1), with probability at least 1 8 over the draw of dataset {(r,, y:)
O and let p be any
we have:
AC KL(p]TT) + log(1/6)
Ea-pl [R(O) < Ba-p(r((0]] 8N
Proof. Fix any 0 E O. By Hoeffding's inequality applied (:(0) E [0, C), we have for any >> Es (=))) < Axo2 Setting A/N: Es [c>(((0)-5((0) x20²
Integrate this bound over 0 w. ES [=>(((0))-<(01]] S x2
By Fubini's theorem, we
exchange the order of integration: Es (E [c>(R(0)-r<(0)]] S 3R
Apply the Donsker- Donsker-Varadhan variational formula to the inner expectation:
sup (AE, - [0]] (L(e||T)) }}
22c² S
Es exp
Apply a Chernoff bound: for any Ps (sup, AE rs] kL(p)TT)
X²62
+ S se
SN
Setting = -log(1/)) and rearranging gives: Ps (3p: [R(O)) > Ep]rs(0)] +
XC
(L(pll=) + log(1/0)
8.
8N
Taking the complement concludes the proof.
The following KL-risk formulation, commonly seen in the PAC-Bayes literature, is due to McAllester I and Langford-Seeger [. It directly bounds the KL divergence between the ex- pected empirical risk and the expected true risk. However, directly optimizing this bound with respect to p is challenging in practice. We do not use this bound in our work but include it here for completeness.
Theorem (PAC-Bayes Bound via KI. of Risks). be a prior distribution over predictors 0 O and p be any posterior, For any 5 (0, 1) and integer N 2, with probability at least over the draw of dataset 5 ~ DN, the following inequality holds:
(T(pp]T)) + log N
KL (E,(r((0) E,(R(0))) =
N
Proof. Let f(0) = (N 1) (T((s((0) R(0)), and apply the Donsker-Varadhan inequality: Ep(((0) < (L(pl(=) + log E. [.]] Taking expectation over the sample S and applying Fubini gives: Es E,](()] < (L(p]| + log Es,a [e)
To control the exponential moment, define
R(0). 4 = ro),), and note that é(h, is Binomial(N, p) proportion. Using an explicit bound on the moment-generating function of (N- 1) KL(glpp) under the binomial sampling process, we can show:
Es ( (L(((())))))) < N, uniformly in
Applying Markov's inequality, with probability at least 1 1- 8, log E, (11 (L(rs(0) (((()) < log 3-
Plugging this into the earlier bound, and dividing both sides by N 1, we conclude:
KL (Eplrs(0)) Eg(R(())) KL(pI| T) + log N
T
N
34

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction clearly and accurately reflect the theoretical and empirical contributions demonstrated in Sections and 4.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Limitations, including biases from finite-sample importance sampling and GPU implementation efficiency, are explicitly discussed in the "Limitations and Broader Impacts" section.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
35

---

Answer: [Yes]
Justification: All theoretical assumptions are explicitly stated in the main paper, and formal proofs appear fully in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Experimental details including datasets, model architectures, training proce- dures, and hyperparameters explicitly stated in Section 4 and detailed in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
36

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: An anonymized version of the code, along with detailed instructions for reproducing the main experiments. included in the supplementary material. The full, non-anonymized code will be publicly released upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
mublic/guider PoodeSubmissioooolieee
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips wttp:ccpccwccpcdeeeeeeeeeeepeeee
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Training and evaluation details including data splits, model architectures, opti- mizers, and hyperparameters are explicitly provided in Section 4 and detailed in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We explicitly report error bars (standard deviations across multiple runs) in tables and figures. The sources variability (e.g.. random initialization and data splits) and calculation methods (bootstrap multiple independent runs) are clearly described in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
37

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We explicitly document the GPU types, memory usage, and approximate runtimes for key experiments in the supplementary material to facilitate reproducibility. Complete details will be provided openly upon acceptance.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::///paappp.cccppooocc/cccit
Answer: [Yes]
Justification:
Our research fully conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Positive impacts (increased transparency, trustworthiness) and potential neg- ative impacts (misuse due to misinterpretation of theoretical assumptions) are explicitly discussed in the "Limitations and Broader Impacts" section.
38

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release high-risk models datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual- use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We clearly cite all datasets used (MNIST, CIFAR-10/100, ImageNet, GLUE, Cityscapes), explicitly provide their URLs, dataset versions, and fully document their licenses in supplemental material.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
39

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets.paperssw package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new datasets, benchmarks, assets were introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The research does not involve human subjects, thus no IRB approval is required.
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
40

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were used solely for editorial assistance (clarifying concepts, editing text), and thus formal declaration is required.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurip) httt:p////eerippssc/ooffeeeeeeee for what should or should not be described.
41


Reviews:
[{"review_id": "hCyHJFtYBu", "reviewer": "Reviewer_8Egq", "summary": "This paper seeks to provide a PAC-Bayes bound on the generalization error (i.e the true risk) of a classifier. Pure PAC approaches yield vacuous bounds due to the expressiveness of neural networks. The approach of a traditional PAC-Bayes bounds compares a learned distribution of parameters to a prior parameter. This too can yield vacuous bounds due to the large movement in parameters needed to learn useful models. One could circumvent this issue with a data-splitting approach but this adds complications. Of course if we’re willing to split the data, we’ll seldom do better than just estimating the risk on the holdout data. There’s a reason why this is what we all do and will continue to do. \n\nThe authors propose a method that uses localized priors based on an idea from Catoni. The central problem here is how to use a data-dependent prior without sample splitting. The authors use an idea from Catoni that softens the data-dependent distribution with a parameter that is then accounted for in the bound. Assuming the results are correct (and sufficiently novel) the result is a new method for computing non-vacuous PAC-Bayes bounds. \n\nThe idea here involves an interpretation of training trajectories where checkpoints are taken as samples from a posterior distribution over the weights. A PAC-Bayes bound is calculated that accounts for the divergence between a  The finite set of checkpointed weights are taken as an approximation of the posterior and this approximation is taken into account in the bound. Assuming the analysis is correct, the authors offer a PAC-Bayes bound on the risk that accounts for some but not all approximations. Importantly the finiteness of the checkpoints but lack of independence of the checkpoints isn’t accounted for. \n\nThe authors present empirical results that show that the PAC-Bayes bounds that they produce on several academic datasets of interest are indeed nonvacuous and tighter than previous attempts although these results involve early stopping / the impacts from the modified objective are such that the results are far from state of the art. The test set is going no where fast :).  The experiments also include some results on usefulness for flagging adversarial / OOD examples but these are cases where the formal guarantees do not hold so the interest is purely empirical. \n\n\nI would like to see more empirical confirmation of the coherence of the results. Crucially, I would like to see what happens not just up to the point of early stopping but what happens when one continues training down to near-0 training error. If the method is valid, the PAC-Bayes bound should dip but then rise again and explode as the learned model overfits the data. The results in Figure 1 show only the descent but not the rise and given the complexity of the setup and presence of some violated assumptions doesn’t inspire confidence in me that the bounds. I’d like to see more empirical evidence that the bounds behave as expected when one trains into the interpolation regime.", "questions": "See above.", "limitations": "See above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am not fully in position to verify the correctness of the paper but it offers an interesting take on an interesting problem, introducing a refined technique for calculating and optimizing PAC-Bayes bounds that can be applied on neural networks.\n\nWeaknesses: \n\nThe authors are a bit too coy in the introduction in suggesting that test set estimation of the generalization is somehow insufficient for providing assurance that the test error is indeed low. It’s far the best way to do this and in fact the only viable method. A test-set-free guarantee on the generalization error is primarily useful for the fundamental insights it sheds on generalization. No practitioner would take the massive hit in accuracy (here incurred due to the aggressive early stopping?) to get the elegance of a one-pass estimate of the risk using training data only. \n\nThe paper is harder to follow than it needs to be. The authors should more clearly lay out the shape of the strategy. What is the key insight from Catoni that doesn’t involve data splitting? How is validity ensured? What are the key pieces of the argument? The reader is left to go fishing and this makes the paper unapproachable for an otherwise competent reader somewhat unfamiliar with the terrain.  Moreover, it’s not sufficiently clear in the paper what is the key contribution over what’s already present in Catoni’s work. Is it the use of the samples to approximate the posterior and the ensuing analysis? The body of the paper lacks a proper prior work section but would benefit from one.", "was_revised": false, "final_justification": "", "rebuttal": "**Summary of Review**\n\nReviewer 8Egq appreciated the novelty and practical intent of our PAC-Bayes method, highlighting the localized prior and empirical improvements over traditional bounds. The reviewer expressed concerns regarding potential practical issues (accuracy trade-offs, early stopping), requested clarifications on the theoretical basis for the localized prior, and sought clearer explanations of our contributions beyond Catoni's original theory. Additionally, they suggested improving clarity and accessibility.\n\n**Summary of Response**\n\nWe clarify that our method integrates directly into standard deep-learning workflows (no early stopping or extra tuning). The observed accuracy gap arises solely from deliberately omitting data augmentation to ensure rigorous mathematical certification. With standard offline augmentation, our approach achieves near-SOTA accuracy, confirming practical effectiveness. The localized prior is theoretically justified using standard Bernstein-type inequalities and the Donsker–Varadhan identity, guaranteeing correctness and stability. We significantly extend Catoni's theoretical foundation by generalizing to cross-entropy loss, developing stable estimators, providing a plug-and-play training implementation, introducing per-prediction certificates, and theoretically analyzing wide-network generalization. We appreciate Reviewer 8Egq’s valuable suggestions for improving clarity and accessibility, which we will incorporate into our manuscript.\n\n---\n\n**Clarifying Practical Utility and Accuracy**\n\nOur method uses a PAC-Bayes loss as a direct replacement for cross-entropy—trained with standard optimizers, learning rates, and a 200-epoch schedule. We do **not** use early stopping or any special tuning: the bound tightens smoothly and plateaus (see Table i), and training completes as usual.\n\nTable i: PAC-Bayes bound evolution (WRN-28-10 on CIFAR-10)\n\n| Epoch | Train 0–1 Error | Test 0–1 Error | PAC-Bayes Bound (Risk) |\n| ----- | --------------- | -------------- | ---------------------- |\n| 100   | 9.1 %           | 8.7 %          | 10.3 %                 |\n| 150   | 7.4 %           | 8.3 %          | 9.6 %                  |\n| 200   | 7.0 %           | 8.0 %          | **9.5 %**              |\n| 300   | 6.9 %           | 8.0 %          | 9.4 %                  |\n| 500   | 6.9 %           | 7.9 %          | 9.4 %                  |\n| 1000  | 6.9 %           | 7.9 %          | 9.3 %                  |\n\n**Note:** This training uses no data augmentation. The PAC-Bayes loss is optimized over the full 1000 epochs. The bound tightens monotonically and stabilizes, with no early stopping or overfitting.\n\nWe emphasize that the observed test accuracy gap is **not** due to the PAC-Bayes loss itself, nor caused by early stopping or instability.. To ensure the **mathematical validity** of the bound, we disable standard data augmentation—such as random crops or flips—since these inject infinite on-the-fly stochasticity. While this is a common strategy to improve generalization, it breaks the i.i.d. sample-count assumption underlying the PAC-Bayes bound (by sampling repeatedly from the same base datapoint), making it unclear what “effective $N$” to plug into the denominator. To avoid this ambiguity, we certify the model using only the original dataset with no replayed views.\n\nIn Table ii, we show that adding standard augmentations (via *offline-augmented datasets* of 4× and 8× size) closes the accuracy gap with SOTA. While this overestimates the effective $N$ and the bound is not certifiable in these settings, the results nevertheless show that the PAC-Bayes loss itself is not the bottleneck: the method regularizes effectively, achieves near-SOTA performance, and smoothly integrates into existing training workflows (compared to similarly trained classical CNN models).\n\nTable ii: Performance improvement with offline augmentation\n\n| Augmentation Setup          | Approximate Dataset Size | Train 0–1 Error | Test 0–1 Error | PAC-Bayes Bound (Risk) |\n| --------------------------- | ------------------------ | --------------- | -------------- | ---------------------- |\n| No augmentation (certified) | 50,000                   | 7.0 %           | 8.0 %          | **9.5 %**              |\n| Offline aug ×4              | 200,000 (4× original)    | 3.4 %           | 4.3 %          | **5.4 %** (heuristic)  |\n| Offline aug ×8              | 400,000 (8× original)    | 2.7 %           | **3.9 %**      | **4.9 %** (heuristic)  |\n\n**Note:** The first row is fully certifiable. In rows 2–3, the bound is **not formally valid**—the PAC-Bayes denominator $N$ is overestimated—but these rows demonstrate that PAC-Bayes loss can achieve near-SOTA accuracy under standard training setups when more data is available, confirming the method's practical usability and demonstrating that the previously noted accuracy trade-off is solely due to rigorous certification constraints rather than method limitations.\n\n**Thus, the PAC-Bayes loss slots into the ordinary training loop: same optimizer, same epoch budget, no additional hyperparameters. Practitioners can still hold out a test set if they wish—but the *same* training run also yields a high-confidence generalization certificate, and even allows safely folding in test data to tighten the bound without risk of overfitting.**\n\n**Practical Importance of One-Pass PAC-Bayes**\n\nCurrent practice relies heavily on evaluating models via held-out test sets. While common, this approach struggles in real-world scenarios:\n\n* **Medical imaging/autonomous driving:** labeled data is scarce, making dedicated validation splits expensive.\n* **Safety-critical applications (healthcare/finance):** fixed hold-out data offers no protection against subtle deployment shifts or hidden overfitting.\n* **Resource-constrained environments:** repeated training or multi-pass validation (typical of previous PAC-Bayes methods) is prohibitively costly.\n\nOur one-pass PAC-Bayes method addresses these pain points by seamlessly embedding generalization certification within standard workflows. Practitioners gain rigorous generalization guarantees directly from a single training pass, efficiently protecting against hidden overfitting and shifts in deployment—ideal for safety-critical and resource-constrained applications.\n\n**Theoretical Justification of Localized Prior**\n\nCatoni's localisation starts from the ideal—but unusable—reference prior: if we somehow knew the true risk $R(\\theta)$ of each parameter $\\theta$, we would create a prior $\\pi_{\\text{ideal}}(\\theta)\\propto\\pi(\\theta)\\,e^{-\\lambda R(\\theta)}$ to assign larger probability to parameters with smaller true risk. Of course, the true risk $R(\\theta)$ is unknown, so Catoni's localisation uses the empirical loss $r_S(\\theta)$—which we do know from data—to approximate it, defining instead a *softly tilted* prior:\n$$\n\\pi_{\\text{loc}}(\\theta)\\propto\\pi(\\theta)\\,e^{-\\xi\\lambda r_S(\\theta)},\\quad 0<\\xi< 1.\n$$\n\nBecause this new prior only partly relies on the empirical data (controlled by the factor $\\xi< 1$), it remains broader and more conservative than the posterior, preventing overfitting. Mathematically, the correctness of this substitution (replacing unknown true risk with known empirical risk) is guaranteed by a standard two-step argument: (i) a Bernstein-type concentration inequality controlling how far empirical averages deviate from their true expectations, and (ii) the Donsker–Varadhan identity converting log-moment terms into KL-divergences. After this substitution, every term involving the unknown ideal prior $\\pi_{\\text{ideal}}$ can be safely replaced by the corresponding term evaluated at the computable prior $\\pi_{\\text{loc}}$, plus a small explicit penalty term $\\frac{\\xi}{1-\\xi}g(\\lambda/N)\\lambda/N$. That penalty (appearing as the denominator in our Theorem 1) explicitly compensates for the data-dependence of the prior, thus preserving correctness and high-probability validity while significantly tightening the resulting bound.\n\n**Contributions Beyond Catoni’s Original Work**\n\nCatoni introduced the theoretical concept of \"localization,\" showing in principle how PAC-Bayes bounds could be tightened via a softly-tilted reference prior dependent on empirical data. However, Catoni’s result remained purely theoretical—limited to abstract settings and binary 0–1 loss—without practical algorithms for modern deep networks.\n\nOur contributions fill these critical practical and theoretical gaps by extending Catoni's localization idea to deep learning:\n\n* **Cross-entropy extension:** generalized the bound rigorously to scaled cross-entropy loss, enabling direct gradient-based optimization.\n* **Stable estimation:** developed finite-sample corrected importance-sampling estimators for computationally stable log-partition approximations.\n* **One-pass practical implementation:** provided a lightweight, plug-and-play TensorFlow/Keras decorator integrating directly into standard training loops (no early stopping or extra phases).\n* **Per-prediction certification:** rigorously extended PAC-Bayes bounds to per-example certificates, enabling principled OOD detection.\n* **Wide-network analysis:** rigorously characterized generalization properties for wide neural networks trained with SGD (Theorem 3.2).\n\nThese nontrivial advances transform Catoni’s theoretical insight into a practical and scalable generalization certification tool for modern deep learning workflows.\n\n---\n\nWe sincerely appreciate Reviewer 8Egq’s feedback highlighting opportunities to improve the paper’s clarity and accessibility. We will incorporate all clarifications into our manuscript. We share the reviewer's goal of making PAC-Bayes theory understandable and practically useful for a broad audience. We welcome any additional feedback or suggestions from Reviewer 8Egq."}, {"review_id": "Pj5YheZcpA", "reviewer": "Reviewer_K8zw", "summary": "This paper introduces a method for computing tight PAC-Bayes generalization bounds for deep neural networks, aiming at addressing the issue of vacuous results  for over-parameterized models (e.g., deep neural networks) when we were trying to compute traditional PAC-Bayesian generalization bound built upon measuring the KL divergence between a learned posterior and a fixed prior.\n\nThe authors’ contribution is a data-dependent reference distribution called “localized prior”, which is constructed by softly tilting a base prior towards low-loss regions of the parameter space. This localization is controlled by a parameter $\\xi$. By integrating the optimization of the model's posterior and the localization hyper-parameters into a single training pass, the method avoids the second training stage required by many other data-dependent PAC-Bayes approaches, which is typically costly. The authors also provide a theoretical bound formalizing this approach and show empirically that it can yield non-vacuous generalization certificates on a range of tasks, including ImageNet classification, Cityscapes segmentation, and NLP fine-tuning.", "questions": "q1. Is it possible to provide an ablation study on high-dimensional tasks showing the final bound changes for different values of K, and further justifications where possible?\n\nq2. Regarding the optimization of algorithm 1. Is it valid to apply the union bound by optimizing $\\lambda$ and $\\xi$ continuously? Also, is it valid to optimize them “data-dependently” while claiming PAC-Bayes guarantees?", "limitations": "The authors have noted the potential for underestimation from finite-sample importance sampling due to Jensen's inequality. However, I think this discussion should be extended - it frames the issue as a trade-off, which I believe is essential to analyze the severity of this bias.  The authors should have stated that their reported certificates are conditioned on the (potentially) questionable assumption that this biased, low-sample estimator is accurate.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. The paper targets a critical problem in learning theory: how to provide rigorous generalization guarantees for large-scale neural networks, which is also a key requirement for their practical deployment in safety-critical domains beyond theoretical interests.\n2. The \"one-pass\" approach to learning a localized prior is a practical contribution that sidesteps the computational burdens of existing two-pass methods, making PAC-Bayes certification potentially much more accessible.\n3. The method is evaluated on a set of modern benchmarks with state-of-the-art reported tightness of the bounds.\n\n---\n\n### Weaknesses\n\nI am not working on ML theory, so the issues/questions identified below are primarily based on educational knowledge and experiences - please use them sparingly.\n\n1. The training objectives rely on a Monte Carlo estimator for log-partition functions with a very small sample size. As far as I know, in the high-dimensional setting of deep learning, such kind of estimator can be systematically biased, leading to an underestimation of the model’s complexity. I am concerned with whether this would lead to artifacts if estimation errors occur.\n2. The theoretical justification of the bound relies on a union bound over a discrete grid of hyperparameters. But the proposed algorithm appears to optimize these parameters via SGD continuously. I think there might be some concerns - are we allowed to optimize them during training while claiming PAC-Bayes guarantees? I think standard PAC-Bayes requires priors fixed before observing data, but these parameters are optimized on the training data?\n3. I think it would also be important to evaluate whether the number of Monte Carlo samples impacts the theoretical and empirical results, which were omitted currently.", "was_revised": true, "final_justification": "The authors' response has addressed my concerns in the initial round.", "rebuttal": "**Summary of Review**\n\nReviewer K8zw recognized the importance and novelty of our PAC-Bayes method, particularly the one-pass localized prior that avoids costly two-pass training. They appreciated our empirical validation across several benchmark tasks. However, the reviewer expressed concerns regarding the theoretical justification for continuous optimization of hyperparameters (\\$\\lambda\\$, \\$\\xi\\$), potential bias from small-sample Monte Carlo estimation of log-partition functions, and requested additional analysis or ablations showing robustness to finite sampling effects.\n\n**Summary of Response**\n\nWe clarify that continuous optimization of hyperparameters (\\$\\lambda\\$, \\$\\xi\\$) is fully justified through a rigorous uniformization and relaxation procedure explicitly detailed in our proof, maintaining theoretical correctness. Regarding estimator bias, our approach uses standard importance sampling combined with explicit finite-sample deviation corrections, ensuring conservative and practically stable bounds. Empirical results demonstrate minimal sensitivity to the Monte Carlo sample size (\\$K\\$), confirming the method’s robustness even at small values of \\$K\\$. We thank Reviewer K8zw for valuable questions highlighting these important clarifications.\n\n---\n  \n**Clarifying SGD-optimizability of $\\lambda$ and $\\xi$ with uniformization and relaxation:**\n\nIn the supplementary proof of Theorem 3.1 (\"Uniformizing the Bound for Continuous Optimization,\" p.15, line 518), we explicitly made parameters $\\lambda$ and $\\xi$ optimizable with SGD using the following discrete-to-continuous uniformization and relaxation procedure:\n\n> \"We discretize the parameters onto finite sets, defining grids: $\\Lambda = \\\\{2N\\zeta^k : 0 \\le k \\le \\lfloor\\log_{\\zeta^{-1}}(2N)\\rfloor\\\\}$ for $\\lambda$ with $0<\\zeta < 1$, and $\\Xi = \\\\{\\alpha^k : 1 \\le k \\le \\lfloor\\log_{\\alpha^{-1}}(N)\\rfloor\\\\}$ for $\\xi$ with $0<\\alpha < 1$. We then evenly distribute the allowable failure probability $\\epsilon$ across all grid points, ensuring with probability at least $1-\\epsilon$ that the PAC-Bayes bound simultaneously holds for every discrete combination of $\\lambda'\\in\\Lambda$ and $\\xi'\\in\\Xi$.\"\n\nAfter establishing this discrete guarantee, the authors carefully relax the discrete grid to continuous variables $\\lambda$ and $\\xi$:\n\n> \"Next, we relax these discrete conditions to continuous parameters $\\lambda \\in [1, 2N]$ and $\\xi \\in [0,1)$ by selecting their nearest grid points $\\lambda' \\in \\Lambda$ and $\\xi' \\in \\Xi$ such that $\\lambda \\leq \\lambda' \\leq \\frac{\\lambda}{\\zeta}$ and $\\xi \\leq \\xi' \\leq \\frac{\\xi}{\\alpha}$.\"\n\nThis uniformization and relaxation procedure explicitly appears in the final bound of Theorem 3.1 as additional conservative penalty terms. For example, the numerator includes:\n$\\left(1+\\frac{\\xi}{\\alpha}\\right) \\log \\left[\\frac{6\\left(\\frac{\\log(2N)}{\\log(\\zeta^{-1})}+1\\right)\\left(\\frac{\\log(N)}{\\log(\\alpha^{-1})}+1\\right)}{\\epsilon}\\right]$, reflecting both the union-bound penalty over discrete grids $\\Lambda, \\Xi$ (where $|\\Lambda| = \\frac{\\log(2N)}{\\log(\\zeta^{-1})}+1$ and $|\\Xi|=\\frac{\\log(N)}{\\log(\\alpha^{-1})}+1$), and the conservative relaxation from discrete $\\xi'$ to continuous $\\xi$. Likewise, the denominator includes:\n$1 - \\frac{\\alpha + \\xi}{\\alpha - \\xi} g\\left(\\frac{\\lambda}{\\zeta N}\\right)\\frac{\\lambda}{\\zeta N}$, reflecting the conservative relaxation from discrete $\\lambda'$ to continuous $\\lambda$.\n\nTogether, these terms ensure that even though $\\lambda$ and $\\xi$ are optimized continuously on the training data, the resulting PAC-Bayes bound remains mathematically rigorous and maintains a valid high-probability guarantee. This is a standard and principled procedure known in PAC-Bayes literature as uniformization, and it fully addresses concerns regarding data-dependent tuning.\n\n**On estimator bias and the use of small $K$:**\n\nThe log-partition function $\\log \\pi[\\exp(-\\xi \\lambda r_S)]$ is a fundamental quantity across statistical physics, Bayesian inference, and machine learning. It arises in settings including variational inference (e.g., ELBO), Laplace approximation, annealed importance sampling (AIS), and Perturb-and-MAP. Many such methods accept bias, rely on lower bounds (e.g., via Jensen’s inequality), or trade variance for computational feasibility—particularly in high-dimensional deep learning.\n\nOur estimator uses importance sampling with posterior reparameterization and finite $K$, chosen for compatibility with standard training pipelines. As discussed in the supplement, more accurate but computationally intensive methods (e.g., thermodynamic integration) exist but are typically not practical for large-scale modern neural networks due to significant runtime and memory requirements. Our choice reflects a practical trade-off between bias, runtime, and VRAM requirements.\n\nWhile the log-partition estimate is biased (due to Jensen’s inequality: $\\log \\mathbb{E}[Z] \\neq \\mathbb{E}[\\log Z]$), our bound follows standard PAC-Bayes practice by conservatively including an explicit finite-sample deviation correction $\\sqrt{\\log (1 / \\delta) /(2 K)}$. This standard practice implicitly guards against bias-induced underestimation, as commonly accepted in machine learning literature. Empirically, we observe stable and tight bounds even at small $K$, and we plan to include a full bias-deviation decomposition in the camera-ready version.\n\nTo demonstrate this empirically, we evaluated the localized PAC-Bayes bound for CIFAR-10 (WRN-28-10) under varying $K$. As shown below, the bound tightens rapidly and saturates by $K = 4$, with minimal gain from larger $K$. This validates both the stability of the estimator and our conservative correction strategy.\n\n\nTable iii: PAC-Bayes Bound vs. Monte Carlo Sample Count $K$\n\n(CIFAR-10, WRN-28-10; test error = 8.0%)\n\n| $K$ | Localized Bound | Deviation Correction | Bound Gap over Test Error |\n| --: | --------------: | -------------------: | ------------------------: |\n|   1 |           11.5% |                +2.0% |                     +3.5% |\n|   2 |           10.9% |                +1.4% |                     +2.9% |\n|   4 |        **9.5%** |            **+1.0%** |                 **+1.5%** |\n|   8 |            9.2% |                +0.7% |                     +1.2% |\n|  16 |            9.0% |                +0.5% |                     +1.0% |\n\n\n---\n\nWe sincerely thank Reviewer K8zw for highlighting these essential clarifications. We fully agree that clarifying the rigor of continuous optimization and addressing finite-sample bias are critical for practical adoption. All clarifications provided here will be included in our manuscript revision to ensure broader accessibility and clarity. We welcome any additional feedback or suggestions from Reviewer K8zw."}, {"review_id": "Sfjo9jpUyV", "reviewer": "Reviewer_41fQ", "summary": "This paper tightens the PAC-Bayesian bound by introducing a localized prior into the computation. The proposed bound, along with three baseline PAC-Bayesian bounds, is evaluated on several benchmark datasets. The results show that the improved bound achieves better tightness compared to the baselines.", "questions": "1. Since the proposed bound is data-dependent, would it be possible to provide an error bar or confidence interval on the computed generalization error bound? This could offer additional insight into its reliability and variability across different datasets.\n2. The improvement in bound tightness appears to be more pronounced in image classification tasks compared to semantic segmentation and NLP fine-tuning. Could the authors elaborate on the reasons behind this discrepancy and the potential takeaways for practitioners?\n3. The application of per-prediction bounds for adversarial or out-of-distribution (OOD) input detection is intriguing. However, in Figure 2, there is considerable overlap between the adversarial and benign risk distributions in the range [0.625, 0.875]. How should the $\\epsilon$ threshold be selected to effectively distinguish between adversarial and benign inputs, while minimizing the false negative rate for a given false positive rate?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n+ The tightness of the bound is evaluated across diverse benchmarks, including image classification, semantic segmentation, and NLP fine-tuning tasks.\n+ The paper is clearly written and easy to follow.\n+ The extension of the population risk bound to per-prediction guarantees offers intriguing potential applications in adversarial and out-of-distribution (OOD) input detection.\n\n**Weaknesses:**\n- Although the computational overhead is moderate, computing the localized bound still requires an additional forward pass during neural network training.\n- The tightness of the bound is data-dependent, which may limit its effectiveness when training data are not carefully curated.\n- The paper lacks a discussion on how to appropriately choose the $\\epsilon$ value to obtain meaningful per-prediction guarantees for adversarial or OOD detection use cases.", "was_revised": true, "final_justification": "The rebuttal addressed most of my concerns. I would like to keep my positive rating.", "rebuttal": "**Summary of Review**\n\nReviewer 41fQ acknowledged the novelty and empirical rigor of our PAC-Bayes framework, especially its application across vision, NLP, and segmentation tasks. The reviewer raised several important clarifications: (1) the manuscript claims a one-pass procedure but seems to require an additional forward pass; (2) the bound’s tightness is data-dependent, raising questions about robustness and generalizability; (3) it is unclear how the bound can distinguish adversarial/OOD data; (4) the reviewer requested error bars to better understand variability in the generalization bound; and (5) the reviewer asked why tighter bounds are observed for image classification compared to NLP or segmentation. These concerns are valuable and provide guidance for strengthening the clarity and practical impact of our work.\n\n**Summary of Response**\n\nWe clarify that our method does **not** require an additional forward pass: the statement was an editing oversight, and our final implementation remains strictly one-pass using partitioned posterior sampling. The data-dependent localized prior tightens bounds when data is clean but gracefully degrades in noisy settings—never worse than standard PAC-Bayes. For adversarial/OOD detection, a principled threshold can be calibrated on a clean validation set; Figure 2 shows strong separation even under a fixed threshold. To address variability, we now include deviation terms in Table 2, providing empirical insight into bound stability. Finally, the tighter image classification bounds stem from structured high-dimensional inputs and more stable loss distributions. We thank Reviewer 41fQ for prompting these clarifications and improvements.\n\n---\n\n**Clarification on the \"One Additional Forward Pass\" (p. 4, lines 159–160)**\n\nThe statement that our method requires “one additional forward pass” is an editing oversight. Initially, we considered buffering an extra snapshot per iteration. However, our final approach (Algorithm 1) employs **partitioned posterior sampling**, simultaneously evaluating subsets of the minibatch using one of the \\$K\\$ posterior draws in parallel within the same minibatch forward pass. Thus, our method remains strictly a single-pass, drop-in replacement for standard cross-entropy SGD. The computational overhead (10–20%) reported in the paper stems solely from evaluating multiple Bayesian samples per minibatch, not from additional passes over the data. We apologize for this confusion and will remove the inaccurate sentence in the camera-ready version.\n\n**On Data-Dependent Tightness**\n\nOur localized prior is data-dependent, but the **probability guarantee** is distribution-free: for the observed sample \\$S\\$, the bound always holds. When the sample is noisy, empirical risks \\$r\\_S(\\theta)\\$ rise, the tilt factor \\$\\exp(-\\xi\\lambda r\\_S)\\$ flattens, and the KL term approaches that of the classical data-independent prior. Thus the certificate gracefully degrades and is **never looser than the standard PAC-Bayes bound** (see Eqs. (3) and (9) with \\$\\xi \\to 0\\$). If a practitioner worries about outliers, they can plug any robust surrogate into \\$r\\_S\\$ (e.g., MAE); the derivation is unchanged. Hence \"data-dependence\" is not a liability: it tightens the bound on well-curated data while remaining safe on messier samples.\n\n**On Choosing \\$\\epsilon\\$ for Adversarial/OOD Detection**\n\nFigure 2 demonstrates that certified risks for adversarial inputs consistently concentrate well above benign and OOD samples. A practitioner can therefore select \\$\\epsilon\\$ by calibrating on a small, clean validation set—for example, choosing the 99th percentile of benign certified risks—to fix the false-positive rate (e.g., at 1%) in advance. Any test sample with certified risk \\$\\hat r(x) > \\epsilon\\$ is then rejected. In Figure 2, this single threshold eliminates approximately 90% of PGD-perturbed images while retaining 99% of clean and OOD data, confirming that the certificate is directly actionable without additional training passes or hyperparameter tuning. Crafting inputs that fool **all** posterior draws simultaneously would require an adaptive, ensemble-aware attack — a challenging attack scenario we identify as important future work.\n\n**Clarifying Variability of Data-Dependent Bounds**\n\nOur PAC-Bayes bound already provides a high-probability generalization certificate: with probability \\$\\ge 1-\\epsilon\\$ (over the training sample), the bound holds uniformly for all posteriors \\$\\rho\\$. This subsumes traditional confidence intervals. That said, we agree it is useful to visualize the empirical variability. In Table 1, we already report deviation terms (in parentheses) that reflect Monte Carlo variability due to posterior sampling. We have now extended this reporting to Table 2 in the same format. These values are derived using standard PAC-Bayes concentration inequalities and offer dataset-specific insight into bound reliability, complementing the universal theoretical guarantee.\n\n**Updated Table 2 (with variability reported):**\n\n| **Task/Dataset** | **Model**      | **Loss (Train/Val)** | **Two-pass** | **Localized (ours)**    |\n| ---------------- | -------------- | -------------------- | ------------ | ----------------------- |\n| Cityscapes       | U-Net (ResNet) | 0.22 / 0.25          | 0.30         | **0.27 (\\$\\pm\\$ 0.02)** |\n| MRPC             | GPT-2 + LoRA   | 0.15 / 0.14          | 0.16         | **0.15 (\\$\\pm\\$ 0.01)** |\n| SST-2            | GPT-2 + LoRA   | 0.08 / 0.11          | 0.14         | **0.14 (\\$\\pm\\$ 0.01)** |\n| RTE              | GPT-2 + LoRA   | 0.22 / 0.25          | 0.28         | **0.26 (\\$\\pm\\$ 0.02)** |\n\n**On Tighter Bounds in Image Classification Tasks**\n\nWe appreciate the observation. We believe the tighter PAC-Bayes bounds observed in vision tasks (e.g., CIFAR, ImageNet) are due to two compounding effects: (1) the posterior distribution \\$\\rho\\$ concentrates faster during training when applied to structured, high-dimensional image inputs with large sample sizes; and (2) our bound is expressed in terms of cross-entropy losses, which are naturally lower and less sparse on image classification compared to structured prediction or binary NLP tasks like MRPC or RTE. These factors combine to yield tighter estimated generalization error in image domains. That said, even in NLP and segmentation, our one-pass localized bound remains non-vacuous and tighter than prior baselines (Table 2), suggesting broad applicability with room for further tuning of loss scaling or posterior design across domains.\n\n---\n\nWe sincerely thank Reviewer 41fQ for highlighting these important issues and offering constructive feedback. We will incorporate all clarifications into the camera-ready version to enhance clarity, precision, and practical relevance. We especially appreciate the opportunity to clarify the practical applicability and empirical variability of the method, and we welcome any further questions or suggestions."}, {"review_id": "BX6apj86Uf", "reviewer": "Reviewer_5sDD", "summary": "The paper discusses the problem of certifying the links training performance to generalization risk. To solve this problem, the authors propose a localized PAC-Bayes prior, derive a non-vacuous bound for it, and show that integrating this prior into the training process yields practically tight generalization certificates. They validate their approach across diverse tasks.", "questions": "1. Could the authors elaborate on the technical challenges they faced while proving the theoretical results?\n\n2. Could the authors explain in more detail how their theoretical bounds compare with previous results?", "limitations": "Yes.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper is well written. Its motivation and results are presented clearly. I enjoyed reading it, even though it lies outside my area of expertise.\n\n2. The localized PAC-Bayes bound provided by the authors improves upon earlier work. Their claims are empirically verified across multiple datasets and architectures.\n\n3. The proposed approach is interesting and improves existing solutions to the problem.\n\nWeaknesses\n\nThe paper would benefit from including a proof sketch in the main text that outlines the key steps of the proofs of Theorems 3.1 and 3.2.", "was_revised": true, "final_justification": "The paper lies somewhat outside my area of expertise, but I found it well written, with clearly presented motivation and results. To the best of my understanding, the proposed approach is interesting and offers improvements over existing solutions. I also appreciate the authors’ plan to include a proof sketch that highlights the main analytical challenges and clarifies how the results build on prior work.", "rebuttal": "**Summary of Review**\n\nReviewer 5sDD appreciated the direction of applying PAC-Bayes bounds to deep networks and recognized the value of developing more practical and scalable generalization guarantees. The reviewer specifically requested: (1) proof sketches for Theorems 3.1 and 3.2 in the main text to improve accessibility, (2) elaboration on the technical challenges encountered when proving these results, and (3) a clearer comparison to previous PAC-Bayes approaches to understand what is new and impactful. These questions reflect thoughtful engagement with the paper and a desire to clarify the contributions for a broad audience.\n\n**Summary of Response**\n\nWe provide below proof sketches for Theorems 3.1 and 3.2 that outline the structure and innovations of our analysis. We also clarify the key technical challenges we addressed—such as combining data-dependent localization, uniformization, and finite-sample concentration into a usable bound—and explain how these make PAC-Bayes reasoning compatible with routine deep learning training. Compared to classical and two-pass PAC-Bayes methods, our bound is tighter, easier to optimize, and integrates directly into standard pipelines. Importantly, our approach also yields per-prediction guarantees that extend the practical value of PAC-Bayes theory beyond prior work.\n\n---\n\n**Proof Sketch of Theorem 3.1**\n\nWe start by adapting Catoni’s idea of tightening PAC-Bayes bounds by reweighting the prior to emphasize models with lower loss—this “localization” sharpens the bound by shifting prior mass toward high-performing regions. Since the true (test) loss is unknown, we upper-bound all such terms using the empirical loss instead, yielding a data-dependent prior while still preserving the bound’s validity via Catoni’s concentration inequality. To allow gradient-based tuning of \\$(\\lambda, \\xi)\\$, we discretize these hyperparameters, apply a union bound over the grid, and then relax back to continuous values with mild correction terms. Finally, we estimate expectations via posterior samples and control finite-sample noise using Hoeffding-type bounds. This produces a high-probability PAC-Bayes bound that is tight, fully empirical, and directly usable as a one-pass training loss in deep learning.\n\n**Proof Sketch of Theorem 3.2**\n\nTo explain why SGD-trained neural networks can generalize despite overparameterization, we bound the generalization gap by comparing the original model to a linearized proxy at initialization. The proof begins by establishing a localized oracle PAC-Bayes bound that upper-bounds the population risk of the nonlinear network using the population risk of its linearized counterpart. Under standard assumptions—bounded activations, stable NTK limit, and NTK-style learning rate—we control the deviation between the nonlinear and linearized networks across five successive steps: activation norms, Jacobian stability, empirical NTK drift, trajectory mismatch, and KL divergence. These terms are all shown to scale as \\$O(1/n)\\$, where \\$n\\$ is the network width. Plugging into the oracle PAC-Bayes bound yields a generalization guarantee with complexity \\$O(1/n + 1/N)\\$, formalizing how stochastic training dynamics implicitly concentrate the learned distribution near low-risk, low-complexity regions—even without explicit regularization.\n\n**Technical Challenges in Proving Theoretical Results**\n\nTo operationalize PAC-Bayes bounds within standard deep learning pipelines, Theorem 3.1 required combining several techniques:\n* (i) **Catoni-style localization**, enabling data-dependent priors that substantially tighten generalization certificates;\n* (ii) **uniformization** to rigorously justify continuous SGD optimization of bound parameters \\$(\\lambda, \\xi)\\$; and\n* (iii) **finite-sample concentration bounds** that robustly control the log-partition function estimates despite Monte Carlo approximation.\n\nThese components jointly deliver a fully empirical, one-pass bound seamlessly integrated as a drop-in training objective.\n\nFor Theorem 3.2, demonstrating why these PAC-Bayes guarantees remain tight for highly overparameterized networks required extending PAC-Bayes theory to linearized (NTK) models and rigorously controlling KL divergence via Gaussian approximations  of the posterior distribution around SGD trajectories. By directly connecting these theoretical innovations with standard training practices, we aimed to bridge the gap between rigorous generalization theory and practical, real-world applicability.\n\n**Comparison with Previous PAC-Bayes Bounds**\n\nUnlike classical PAC-Bayes bounds—which rely on a fixed, data-independent prior and typically produce vacuous guarantees for large neural networks—our approach introduces a **localized prior**, inspired by Catoni’s method, that significantly tightens the bound by centering it around empirically low-risk regions.\n\nCompared to **two-pass PAC-Bayes techniques** (which require data splitting or a second optimization phase), our single-pass, localized prior integrates seamlessly into standard training as a drop-in replacement for cross-entropy, avoiding extra tuning and accuracy trade-offs.\n\nEmpirically (Tables 1 and 2), we achieve substantially tighter and practically meaningful generalization certificates across diverse architectures (CNNs, Transformers) and tasks (CIFAR, ImageNet, NLP), clearly surpassing previous PAC-Bayes methods. Additionally, our method uniquely provides rigorous **individual-level certificates** for predictions, enabling robust detection of adversarial inputs and further strengthening practical utility. Thus, our localized PAC-Bayes bound bridges rigorous generalization theory with routine deep learning workflows.\n\n---\n\nWe thank Reviewer 5sDD for highlighting important questions regarding accessibility and context. We will include proof sketches for Theorems 3.1 and 3.2 in the main text and ensure clearer comparisons to prior work throughout. We share the reviewer's goal of broadening the reach of PAC-Bayes theory and making its insights both actionable and interpretable for modern deep learning practice. We welcome any additional questions or suggestions."}]

Author rebuttal:

Meta-review: This paper explores tighter generation bounds of deep neural networks by leveraging PAC-Bayes bounds along with a novel localized PAC-Bayes prior. The tightness is theoretically supported and empirically validated over diverse datasets and practical models. 

**Strengths**:
* exploring a critical problem in learning theory: a non-vacuous generalization bound for deep networks
* proposing computationally efficient "one-pass" approach
* broad empirical evaluation


**Weaknesses**:
* presentation issues – the paper would be more readable by explaining layman's terms. 

The paper is borderline but reviewers agree that this paper has sufficient contributions and advances the frontier of PAC-Bayes bounds. So, I vote for acceptance. For the final manuscript, it would be better to refine the paper presentation to make it more accessible for general readers and include valuable discussions from reviewers.
Decision: Accept (poster)