Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes
Authors: Itamar Harel
Yonathan Wolanowsky
Gal Vardi
Nathan Srebro
Daniel Soudry
Venue: NeurIPS 2025 spotlight ()
Keywords: Generalization
Langevin dynamics
deep learning
Primary area: theory
TL;DR: We derive simple generalization bounds for Markov training processes at any time during training, and then apply them to training with Langevin dynamics to improve existing bounds.

Abstract: We analyze the generalization gap (gap between the training and test errors) when training a potentially over-parametrized model using a Markovian stochastic training algorithm, initialized from some distribution $\theta_0 \sim p_0$. We focus on Langevin dynamics with a positive temperature $\beta^{-1}$, i.e. gradient descent on a training loss $L$ with infinitesimal step size, perturbed with $\beta^{-1}$-variances Gaussian noise, and lightly regularized or bounded.
There, we bound the generalization gap, *at any time during training*, by $\sqrt{(\beta\mathbb{E} L (\theta_0) + \log(1/\delta))/N}$ with probability $1-\delta$ over the dataset, where $N$ is the sample size, and $\mathbb{E} L(\theta_0)=O(1)$ with standard initialization scaling. In contrast to previous guarantees, we have no dependence on either training time or reliance on mixing, nor a dependence on dimensionality, gradient norms, or any other properties of the loss or model. This guarantee follows from a general analysis of any Markov process-based training that has a Gibbs-style stationary distribution. The proof is surprisingly simple, once we observe that the marginal distribution divergence from initialization remains bounded, as implied by a generalized second law of thermodynamics.

Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes
Itamar Harel"
Yonathan Wolanowsky Technion
Gal Vardi Weizmann Institute of Science
Technion
Nathan Srebro
Daniel Soudry Technion
Toyota Technological Institute at Chicago
Abstract
We analyze the generalization gap (gap between the training and test errors) when training potentially over-parametrized model using a Markovian stochastic train- ing algorithm, initialized from distribution 0 Po- We focus Langevin dynamics with positive temperature f=1,, i.e. gradient descent on training loss L with infinitesimal step size, perturbed with -vr-iinisee Gaussian noise, and lightly regularized or bounded. There, we bound the generalization gap, at any time during training, by / (O, + In(1/8)) with probability - ô over the dataset, where N is the sample size, and (L,) O(1) with standard initializa- tion scaling. In contrast to previous guarantees, we have no dependence on either training time reliance on mixing, nor dependence on dimensionality, gradient norms, or any other properties of the loss model. This guarantee follows from general analysis of any Markov process-based training that has a Gibbs-style stationary distribution. The proof is surprisingly simple, once we observe that the marginal distribution divergence from initialization remains bounded, as implied by generalized second law of thermodynamics.
Introduction
One main goal of contemporary machine learning theory is to predict model's 's behavior before training occurs. commonly desired metric the generalization of overparameterized models, such as neural networks (NN), For these models, such a predictive theory of generalization is still lacking, despite great empirical success [71, 23]. In particular, significant line of work aimed explain the role of optimization in generalization (e.g. [23, 64, 40, 66)), and specifically the effect of stochasticity (e.g. [59, 49, 10, 8)).
Data-dependent Markov processes are a common optimization approach. These include stochastic gradient descent (SGD), as well other stochastic gradient methods either studied theoretically [30, 59], or used in practice such as SGD with momentum [52], ADAM [34], and many more. Of particular interest are continuous Langevin dynamics (CLD) and discrete analogues of it, which have been studied extensively as models for SGD (see Section 4.1).
In Section 2 we develop, for the first time, generalization bound applicable to any dependennnd Markov process with a Gibbs-type stationary distribution (i.e. whose finite density exists and is nonzero w.r.t. some data-independent base measure). An important feature of our analysis is that is entirely independent of the training time t, both in that we do not rely on training for only a
Cooresponding author: stamarharel01@maal..com
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

small number of steps, nor that we rely on mixing - the guarantees are valid at any time, with no dependence at all on Furthermore, it is also completely trajectory independent.
In Section we apply these general results to the particular case where training is done with CLD with loss I. and inverse temperature 3, deriving a particularly simple generalization bound for CLD, which we compare to previous generalization bounds for CLD in Section 4, as well as discussing other related work. Finally, we address limitations and future work in Section 5.
To prove these results, we first show in Section 2 how, for the marginal distribution at time t, Pe its divergence (either KL or the Rényi infinity divergence) from initialization is bounded due to its monotonicity, i... a generalized second law of thermodynamics [11, 46]. This surprisingly simple derivation leads to key technical result (Corollary 2.5). Standard PAC-Ban -AC-Bayes generalization bounds [43] then yield our generalization bounds (Theorem 2.7 and Corollary 3.1).
2 Generalization Bounds for General Markov Process
In this Section, we consider general data-dependent Markov processes over predictors and obtain a bound on their generalization gap. Importantly, although the bound only depends on the initialization distribution and a stationary distribution, it will apply to predictors at any time t > 0 along the Markov process. Our main goal is apply these bounds stochastic training methods, such as Langevin dynamics, where the iterates form a data-dependent Markov process. But to emphasize the broad generality of the results, in this section we consider a generic stochastic optimization framework and general data-dependent Markov processes.
We obtain generalization guarantees by bounding the KI.-divergence (or, for high probability bounds, the Rényi infinity divergence, see Definition 2.1) between the data-dependent marginal distribution Pe of the predictors time f,, and some data-independent base measure (the PAC- "prior"). The crux of the analysis is therefore bounding the divergence between and v, based only on assumptions on the initial distribution po (specifically, the divergence between Po and v) and stationary distribution Pso (specifically, requiring that Prx can be expressed as a Gibbs distribution with bounded potential or expected potential, see Definition 2.2) we do this in Section 2.1. Then, in Section 2.2 we plug these bounds on the divergence between pt and V into standard PAC-Bayes bounds to obtain the desired generalization guarantees.
Detailed proofs of all the results in this section can be found in Appendix B.
2.1 Bounding the Divergence of a Markoy Process
In this subsection, we consider a general time-invariant Markov process h2 E H. over a state space H. The Markov process can be either in discrete or continuous time, i.e. we can think of ( as either an integer or a real index. We denote by Pt the marginal distribution at time I,, i.e. hy ~ Pt. We do not assume that the Markov process is ergodic, and all our results will rely on the existence of some stationary distribution Pao. The main goal of this subsection is to bound the divergence D (pe ()) between the marginal distribution at time and some reference distribution v. We can think of bound on the divergence as ensuring high entropy relative to v, or in other words that Pt does not concentrate too much relative v, i.e. does not have too much probability mass in small v-region. We present all bounds for both the KL-divergence KL (p q) and the Rényi infinity divergence D (p || q). defined below.
Divergences and Gibbs distributions. We recall the definitions of our two divergences, and also relate them to the Gibbs distribution. It will also be convenient for us to introduce "relative" versions of divergences.
Pe.g. to bound the KL divergence of Markov process having stationary distribution with potential E [0, (o), ie. /poo/ dpo & e (e.g.. v = BL for CLD), the second law implies the first inequality below
kI(ppllpo) = -fn In Pt =f= Pa
In Pro
+ +
Peo 1 f In Poo Do
+ +
Poo
Eop v Ey, po
Egp v.
$ Formally stated: we require that for any 0 < 41 < 12 < ts we have that hig is independent of he conditioned on hig (Markov property) and that for any 0 S t1 b2, A we have that hy A she has the same conditional distribution heetalll l/t, ttime-invariance..
2

---

Definition 2.1 (Divergences *). For probability distributions q and
The y-weighted Kullback-Leibler (KL) divergence (a.k.a. relative cross-entropy) is* KL, (p = d ag and the KL-divergence then KL (pl1g) KLp (p g).
2. The Rényi infinity divergence is D (p = ess sup, In dg' with Dxc (p || D (p
Definition 2.2 (Gibbs distribution). A distribution p is Gibbs w.r.t a base distribution with potential W:H- - = e-" dg < 0o and
e- dq.
Claim 2.3. Pf U. are probability measures, and is Gibbs w.r.. q with potential V < oc, then
KL 9) + kL (q p) = E, E V.
2. D (pl q) D (q p) = ess sup, v/ - ess p W.
So. KL (p ()) KL (g p) E E. v and Do (pll))+ + (q (lp) ess sup, - ess inf, p W.
That is, the potential a Gibbs distribution p allows us to bound the divergence in both directions between p and the base measure q. A generalized converse of Claim 2.3 also holds, and we have that bounding on the symmetrized divergences (but not just on one direction!) is also sufficient for being Gibbs with bounded potential."
Second Law of Thermodynamies Central to our analysis is the following monotonicity property on the divergence between the marginal distribution of a Markov process and any stationary distribution.
Claim 2.4 (Cover's s Second Law of Thermodynamics). Let pt be the marginal distribution of a time-invariant Markov process, and Pse a stationary distribution for the transitions of the Markov process (the process need not be ergodic, and pt need not converge to poo). Then for any t 2 0
KL (px P=0) < KL (po P>0) and
Doa (pe Poo) S Doo (po |1 Poc)
When the stationary distribution is uniform (thus having maximal entropy), the KL-form of Claim 2.4 recovers the familiar second law of thermodynamies i.c. that the entropy is monotonically non- decreasing. The more general form, as Claim 2.4, is a direct consequence of the data processing inequality, pointed out by Theorem 4 of Cover [11] (see also [12, 46] and the generalization to Rényi divergences in [65, Theorem 9 and Example 2] for completeness we provide a proof in Appendix A.2).
In our case, the stationary distribution pso will not be uniform, but rather will very data-dependent (we are interested mostly in processes that aim to optimize some data-dependent quantity, such as Langevin dynamics). Nevertheless, we want to use Claim 2.4 to control the entropy of pt relative to some benign inta-independent base distribution (which we can informally think of as "uniform")). To do so, we can use the chain rule and plug in Claim 2.4 to obtain that for any distribution v and at any time & we have (see Lemma B.1 in Appendix B for the full derivation):
KL (p: [] KL (pr Poo) + KLpp (p 1] S KL (po |l poo) + KLp, (poo ||
KL (po v) + KLpo (v Poo) + KLpp (poo [[
(I)
and similarly,
Doc (pellv) S Doo (po 11 + D (v Px)) D (poc 1|
(2)
"The term "divergence" is slight abuse of notation, as the following definitions are strictly non-negative, without specifying p.
For two measures p and dp/ dg is the Radon-Nikodym derivative (i.e. the density of w.r.t. q) when it exists (i.e. when p & q. i.c. p absolutely continuous w.r.t. q). or otherwise.
'The essential supremum of function f w.r.t. a measure is ess sup,, f inf (b E R (f > b) = 0).
i.e. the smallest (infimum) number that bounds f from above almost everywhere. The essential infimum detined similarly.
(l) < B iff there exists potential V such that is Gibbs w.r.t "More formally: KL (p g) + KL
with potential v and E,, - E,, < 3, and similarly Dx (p () + Dz. (q p) < 3 iff there exists a potential
0 < v < 3 such that is Gibbs w.r.t. with potential w. See Claim B.8 for proof.

---

Bounding the last two terms in (1) and (2) using Claim 2.3 we obtain the main result of this subsection:
Corollary 2.5. For any distribution v and any time-invariant Markov process, and any stationary distribution Poo that is Gibbs w.rt. v with potential y 2 0 (the Markov chain need not be ergodic, and need not converge Pool, at any time 2 0:
KL (pr || 1)) < KL (po p) Bpp v/ Ep.
v - KL (Po 1) + Ep. V
(3)
Do (pt v) S Do (pu || v) + ess suppo
(4)
The important feature of Corollary 2.5 that bounds the divergence at any time I, in terms of right-hand side that depends only on the initial distribution pa and stationary distribution Poc. Interpreting the divergence D (p: || in) as measure of concentration, the Corollary ensures that at no point during its run, and regardless of mixing, does the Markov process concentrate too much, and it always maintains high entropy (relative to the base measure v2).
Remark 2.6. In order to bound the divergence D (px v) at finite time I, it is not enough to rely only on the divergences D (po v) and D (Peo v) from the initial and stationary distributions, and necessary to rely also the reverse divergence D (v Poo) - see Appendix C.
2.2 From Divergences to Generalization
Corollary 2.5 can be directly used to obtain PAC-Bayes type generalization guarantees. Specifically, we consider a generic stochastic optimization setting specified by a bounded instantaneous objective f: x Z + [0, 1] over class H. which we will refer to as the "predictor" class, and instance domain Z. For example, in supervised learning Z = X' x y. H. C yd and f(,, (x. y)) ) = 1 (h(x) * y} measures the error of predicting h(z) when the correct label is y. For a source distribution D over Z and data S ~ DN of size N we would like to relate the population and empirical objectives
1 Es(h, Es (h)= N
ED (h) = E. EZ-DDI(
(5)
In our case, we are interested in predictors generated by a data-dependent Markov process ht- That is, conditioned on the data S. {he is time-invariant Markov process, specified by some (possibly data-dependent) initial distribution (hg: S), and a transition distribution that would also depend the data S, and specifies (randomized) rule for generating the next iterate h4+1 (if in discrete time) from the current iterate ht and the data (as in, e.g., stochastic gradient descent or stochastic gradient Langevin dynamics; SGLD).
We present two types of generalization guarantees: guarantees that hold in expectation over draw from the Markov process ((6) below) and guarantees that hold with high probability over a single draw from the Markov process (as in (7), e.g. a single run of CLD). In both cases, the guarantees hold with high probability over the training set.
Theorem 2.7. Consider any distribution D over Z. function f H x 2 - [0. 1]. sample size N 8, and any distribution over H. Let (he E H)rzo be discrete or continuous time process (i.e. & E Z,4 or t ) that is tieeinnariian Markov conditioned on S, that starts from an initial distribution Po(::S) (that may depend on S), and admits stationary distribution conditioned on S. Pool:; S). Let sh) 2 0 be non-negative potential function and assume that Poo (:;S) S) is Gibbs w.E.. V with (:
potential V Then:
1. with probability 1- - over S ~ DN.
KL (po(::))l + E V (ho))[] + In N/8
E (ht) (s(h))
(6)
2N
2. with probability 8 over S DNN and over he:
Doo (po(::)) v)) + ess sup sup Vs(h) + In N/o
(bt) - Es(hh)) 1
(7)
2NV

---

Proof. The Theorem follows immediately by plugging the divergence bounds of Corollary 2.5 into standard PAC-Bayes guarantees, which we do Appendix B.
Remark 2.8. A simplified variant of Theorem 2.7 can be stated when the initial distribution po is data-independent and always equal v. In this case the divergence between po and vanishes, and (6) and (7) become
Po V s
S] + In N/ 2N
ess usssuppi
V + In 2/6
E [ED (b+) - (is(h))SS) S
(b(h Es(ha)
2N
(8)
But allowing Po * v/ is more general, as it both allows using data-dependen initialization (recall that v must be data independent) and it allows initializing to a distribution where D (Pec || Po) is infinite e.g., we can allow initializing to degenerate initial distribution Po whose support is strict subset of the support of Pao (in which case Pao will definitely not be Gibbs w.rt. po), as long as the u-mass of the support of po
too small.
Remark 2.9. In Theorem 2.7, the Markov process need not be ergodic, and need not converge to Poo. or converge at all. If there are multiple stationary distributions, the theorem holds for all of them, and so we can take Pso to be any stationary distribution we want. And in any case, there is no mixing requirement, and the theorem holds at any time t.
Remark 2.10. Our data-dependent Markov process of interest, and in particular CLD and SGD, might aim to minimize (hy), and the potential V might also be related to it (as in, e.g., CLD). This is allowed, but is in way required in Theorem 2.7. Even for CLD, these might be related but not the same, as we might be minimizing a surrogate loss, such as logistic loss, but are interested in bounding the generalization gap for a zero-one error. In stating Theorem 2.7 we intentionally refer to an arbitrary stochastic optimization problem and an arbitrary data-dependent Markov process, that are allowed be related or dependent arbitrary ways.
Remark 2.11. In Appendix we show that in order to ensure generalization at every intermediate t, is not sufficient to only bound KL (Poo (/) or Doc (p || []) and we do need the stronger symmetric bound ensured by the Gibbs potential and Claim 2.3; and that it is also necessary to relate both Po and Pao to the same data independent distribution v, relating them to different iata-indeeendent distributions ensures generalization at the beginning and at the end, but not the middle training.
Remark 2.. In Theorem 2.7 we plugged Corollary 2.5 into a simplified PAC-Bayes bound that allows for easy interpretation and comparison with other results. But once we have the divergence bounds of Corollary 2.5, we can just as easily plug them into tighter PAC-Bayes bounds see Appendix B. For example, when Es (h+) O, these yield a rate of O (1/N).
3 Special Case: Continuous Langevin Dynamics
Clearly, given Theorem 2.7 all we need to do in order to derive explicit generalization bounds for any Markovian training procedure, is to find stationary distribution, and bound its potential (or its expectation at Po). this section, we will exemplify our results in a few special cases of continuous-time Langevin dynamics (CLD), commonly studied approximation for NN training with "infinitesimal learning rate" (e.g. [41], see Section 4.1 for additional references), which have a normalized stationary distribution that we can write analytically.
Additional notation. In the following, it will be convenient to consider a parametric model. Specif- ically, we assume that there exists some parameter space θ C IR that parameterizes a hypothesis class H C y via mapping + - 0 + he E H. and assume Markovian dynamics in parameter space, instead of in the hypothesis space (note that Markov processes in parameter space may not be Markovian in hypothesis space, but the same generalization results apply ). We shall also use, with some abuse of notation, (0) & (ha) for any data-dependent or data-independent function yp over hypotheses, e.g. a training loss/objective I.g w.r.t a training set Finally, we use C² to denote the space of twice continuously differentiable functions on θ.
CLD in bounded domain. Let θ be box in Rdd, and suppose that training is modeled with CLD in bounded domain, i.e. that the parameters evolve according to the stochastic differential equation with reflection at the boundary (SDER)
d0,- = - LL (0,) dt + /28- dw, + dr.,
(9)
5

---

where Lg 2 O is twice continuously differentiable, w; is standard Brownian motion, and is reflection process that constrains 0, within O Such weight clipping is quite common in practical scenarios such as NN training. For simplicity, we assume that ry has normal reflection, meaning that the reflection is perpendicular to the boundary. An established result in the analysis of SDERs states that under these assumptions (9) has a stationary distribution Poo (0) x e - {0) (see Appendix H.2). Thus, when Pu Uniform (0), we have Pu V.
Regularized CLD in IRS Suppose that the parameters evolve according to the stochastic differential equation (SDE) with weight decay (i.e. l regularization)
d0, VLs (0.) dl 0, + /23-Iddr.
(10)
where Lg O is twice continuously differentiable, w, is standard Brownian motion. Such weight decay also quite common in practical scenarios such as NN training. Similar to the previous case, with the regularization and twice continuous differentiability of Lg this process has unique stationary distribution Pao (0) x e (0) Φb (0), where Φx is the density of the multivariate Gaussian N' (o, 10, Thus, when po = N (0, X Ia),, we also have Po V.
We now formulate generalization bound for both cases.
Corollary 3.1. Assume that the parameters evolve according to either (9) with po Uniform (0), or (10) with pa = N (0, la). Then for any time t 2 O, and 8 E (0, 1).
1. w.p. 1 - 8 over S DN,
GEApp (s((0) 8] + In (N/6)
Eg.-p. EED (0.) - Es(O,) (5)
(11)
2N
2. w.p. 1 - 8 over S ~ D and 0: ~ Pt
esss supp (ss(0) + In (N/8)
En(O,) - Es(O,) S
(12)
2N
The proof is simple - assumption, in both cases po = v so Doo (Pu || v) = The rest is a direct substitution into Theorem 2.7, and in particular, using 3 potential V.
3.1 Interpreting Corollary 3.1
Corollary 3.1 raises questions on the relevance of this setting, which we address below: (1) How large is Po Ls (0) in practically relevant cases? (2) Can we attribute the generalization to the regularization (either with the le regularization term, or the bounded ?omain)? (3) Can models successfully train in the presence of noise with variance large enough make the bounds non- vacuous?
Magnitude of the initial loss. Commonly, the dependence on Ep, Ls (0) with realistic po and Ls is relatively mild. For example, using standard initialization schemes, Gaussian process approximations [50, 42, 35, 25] imply that the output of an infinitely wide fully connected neural network converges to Gaussian with mean 0 and ((1) variance at initialization. So in many cases Ep, Ls (0) O(1), such as for the scalar square and logistic losses. the multi-output case, Ep, Ls (0) may also depend on the number of outputs (e.g., logarithmically so in (rottex-rooss-entroppy) A more difficult question concerned with the case that ess sup,, Ls = oo, which is common when po has infinite support. This can be mitigated by clipping the loss, which is standard in practice (e.g. in reinforcement learning [48, 62]) and in the theory of optimization [37, 33). Moreover, this clipping can be done in a differentiable way (c.g. using either softmin, tanh (e.g. tanh( tanh(L/c)) L/c)), etc) and at values only slightly higher than the typical loss at the initialization (since the loss is roughly monotonically decreasing in CLD with small noise, the optimization process would typically operate below the clipping and will not be affected by it).
Magnitude of regularization. In the above result we must use regularization (or a bounded domain) that matches the initialization yo (this can be somewhat relaxed, see Section 3.2). The same assump- tion, that the regularization matches the initialization, was also made in other theoretical works on CLD [49, 38, 19). Note that, NN models regularized this way remain highly expressive, both empiri- cally (Appendix F) and theoretically (Appendix G), and therefore we cannot use this regularization

---

alone, together with classical uniform convergence approaches to show generalization. Intuitively. this is because the regularization term can be tiny, for example, in (10) the regularization term is divided by 3. Therefore, when 3 = O (N) (which is sufficient for non-vacuous result), Po = and we use a standard deep nets initialization distribution po (e.g., [21, 28), where x layer width),
the regularization coefficient is O Iayer width that is rather small in realistic cases. Therefore, we found (empirically) that it does not seem to have a large effect at practical timescales. In addition, one can always increase the regularization by modifying the loss Ls < Ls + c e|01| in (10). Under standard initializations, this changes the loss in the bound by an (cd)) factor, where d is the depth of the neural network and so cd is small, for common values of and d. Therefore, combining these observations, we do not see the magnitude of the regularization as a significant practical issue.
Magnitude of noise: theoretical perspective. In the above result we must use 3 = O (N) to obtain bound. This requirement is standard in many theoretical works. For example, as we will discuss below in Section 4.1, all previous generalization bounds for CLD and SGLD also required, to generalize well, 3 = O (N) and potentially much worse (lower 3). In addition, other theoretical works on noisy training also typically had 8 = O (N) or worse. For example, when considering the ability of noisy gradient descent to escape saddle points, Jin et al. [30] uses noise sampled uniformly from ball with radius that depends on the dimensionality and smoothness of the problem, and thus cannot decay with N. Moreover, it is known that the Gibbs posterior generalizes
a
well with 3 O (VN) (e.g. see Theorem 2.8 in 1), which is significantly smaller than B O (N). Lastly, in Appendix E we examine the impact of B in the simple model of linear regression with i.i.d. standard Gaussian input, labels produced by a constant-magnituee
teacher label noise, trained using regularized CLD as in (10), with À x d to match standard initialization. We find there that whenever < 3 < N, the added noise does not significantly affect the training or population losses, and our bound is useful, i.e., it implies vanishing generalization gap (since / < N and E = O())). Note that d < N is not a major constraint, since d < N is required to obtain low population loss in this setting, even if we did not add noise to the training process (i.e. / oo).
Magnitude of noise: empirical perspective, An inverse temperature of 3 = O (N) also relevant in many practical settings. For example, in Bayesian settings, when we wish to (approximately) sample from the posterior, it quite common to use variants of SGLD; then inverse temperatures of order 3 = 0 (N) are commonly used to achieve good generalization [69], which matches our results. In the standard practical training settings, the inverse temperature is a hyperparameter tuned to best fit given problem. Empirically, in Appendix F we find that B O (NV) can be tuned to obtain non- vacuous generalization bounds for overparameterized NNs in a few small binary classification datasets (binary MNIST, Fashion MNIST, SVHN, and a parity problem), i.e. the sum of the generalization gap bound and the training error is smaller than 0.5. Importantly, these non-vacuous bounds do not use any jejeecorr-dependdeee
quantities as other non- vaccuuu bounds (e.g. [15, 391), which make them arguably more useful as they can be calculated before training. The bounds are still not very tight (at noise levels that allow for vacuous bounds), but we believe there is still much room for improvement in future work.
3.2 Extensions and Modifications
State dependent diffusion coefficient. Consider a state-dependent diffusion coefficient
d0:- = L. (0,) di + / 2/3-122 (0.) + dr,,
where o² E C²2 For example, in Appendix D.I we derive the explicit form of stationary distributions
when x² (0) (I.s (0) + a)* or o² (0) (0)) for some h E N and > 0. In both cases, the analytic form of the stationary potential V can be used directly with Theorem 2.7 to derive generalization bounds.
Restricted initialization. In Appendix D.2 we present generalizations of Corollary 3.1 to cases where and / are different. Specifically, for the bounded case we consider Po that is uniform in a subset O, O of the domain, and for the regularized case we consider general diagonal Gaussian initialization and regularization. In particular, this means that some of the parameters can be more
Generalization bounds for the Gibbs posterior typically assume that it is "trained" and "tested" on the same function, while here the distribution is defined by the loss and "tested" on the error.
7

---

Table 1: Comparison of generalization bounds for CLD. We compare the main bounds in settings similar to the CLD setting considered here. All the bounds here consider different functions for training and evaluation, as was done in this paper with Ls and Es, ED. respectively. For simplicity, we assume that Es, E are bounded in [0. 1], and are therefore 1 1/2-subGaussian via Hoeffding's s inequality. We use gr. to denote Irejectory-dependent statistics of the gradients, K for the Lipschitz constant, and C' for a bound on the loss, or the expected loss at initialization, when they are required. For compactness, low-order terms are omitted, time-dependent quantities are simplified to an approximate asymptotic value, and trajectory dependent integrals are solved by considering the statistics Ir constant w.r.t. the variable of integration. Finally, all bounds assume Gaussian initialization N Ia) and regularization term A
00 Il. both with the same X.
23
Paper
Trajectory dependent
dimension dependence
Bound (hig O)
Mou al. [49]
through gradients through K
x
Li ct al. [38]
X
2K
Futami and Fujisawa [19]
/
through gradients X
V Gesac V V&. VVV .V
Ours (11)
x
loosely regularized/houndedd cost proportional their number. For example, in deep NN, if only single layer is loosely regularized/bounddd, the KL-divergence cost will be proportional only to the number of parameters in that layer, not the entire d.
4 Related Work
Information theoretic guarantees and PAC-Bayes theory. A common type of generalization bounds consists of measure of the dependence between the learned model and the dataset used to train it, such as the mutual information between the data and algorithm [58, 70, 61] or the KL- divergence between the predictor's distribution and any data-independent distribution [44, 9, 1]. In particular, recent works were able to estimate such dependence measures from trained models to derive non-vacuous generalization bounds, even for deep overparameterized models. For example, Dziugaite et al. [17] used held-out data to bound the KL-divergence in a PAC- Bayes bound with a data- dependent prior. Other works used some property of the trained model estimate the information content, adding valuable insight to the mechanisms facilitating the successful generalization. such as the size of the compressed model after training, due to noise stability [3], and data structure [39].
Generalization of the Gibbs posterior. One classic result in the PAC-Bayesiag theory of generaliza- tion is that the Gibbs posterior with properly tuned temperature minimizes the PAC-Bayes bound of McAllester [44], i.e. the KL-regularized expected loss. Raginsky et al. [59] used uniform stability [7] to derive different generalization bound for sampling from the Gibbs distribution. Due these known generalization capabilities, some works relied on it to derive bounds for related algorithms.
4.1 Explicit Comparison for CLD
Many previous works [59, 49, 38. 18, 19, 14] derived generalization bounds specifically for CLD, under different assumptions. Our bound offers some improvements over previous ones:
It is trajectory independent, and does not require gradient statistics [49, 19].
does not require very large time scales to make sure we have already converged near Gibbs [59], nor does it deteriorate with time, is common for stability- baseed bounds [49, 14].
It does not depend on the dimension of the parameters, neither explicitly through constants [18]. nor implicitly, e.g. through the Lipschitz constant or the norms of the gradients (49,38, 19]. In particular, as previously discussed, using standard initialization, our in-expectation bound in (11) dimension independent. However, our high- high-probability bound (12) relies on the effective supremum at = 0, and may also depend on the dimension if the loss is not bounded.
The dependence on the inverse temperature / and loss' (or expected loss) bound C' is polynomial (VBC) instead of exponential [38, 18, 19].
8

---

The bounded expectation assumption in (11) is weaker than uniform bound on the loss [38, 19]. Theorem 2.7 and Corollary 3.1 demonstrate that our results hold for general initialization- regularization pairs, beyond Gaussian initialization with matching & regularization.
In Table we compare in more detail Corollary 3.1 to other bounds that remain bounded as L + oo.
Finally, Dupuis et al. [14] recently derived bounds on the generalization gap for all intermediate times 0 < & I simultaneously. Naturally, as avoiding parameters with large generalization gap is increasingly less likely the process mixes, their bounds grow with time. Therefore, Dupuis et al. [14]'s bounds are qualitatively different, and higher than most other bounds, including ours.
4.2 Technical Novelty
As representative example, we first focus on Raginsky et al. [59], which provided bound for CLD (as an intermediate step for deriving generalization bound for SGLD, a discretized version of CLD). Using spectral methods [e.g. 5]. they bound the distance between the process' distribution to the Gibbs posterior, which, when combined with the generalization bound for the Gibbs distribution, results in generalization bounds for intermediate times. Our Corollary 2.5 and the preceding arguments are similar to the proof of Lemma 3.4 of Raginsky et al. [59] that bounds the divergence between the initialization and the Gibbs distribution, where their dissipativity coefficient m corresponds to our explicit e regularization coefficient A. We use some significant observations that make the bound simpler, and time/dimension// time/immnsioo/Lipcchi/smsoenn Lipschiz//mmottnness independent.
Instead of a bound on the convergence of intermediate time distributions to Gibbs, which restricts the result to very large times and introduces exponential dependence on dimensionality through the spectral gap, we only require the monotonic convergence to it. As a result, we do not use a spectral gap, but a complexity term for the initial distribution. This also enables to generalize the result to any Markov process, relying on Ep V as a complexity term for the Gibbs posterior, which is also included in Lemma 3.4 of Raginsky et al. [59] along other quantities.
By using& symmetric version of the divergence (e.g. by summing KL (p ll q) and KL (q ll p)) were able to completely remove the partition function from the analysis, avoiding the complica- tions arising from it.
By separating the regularization from the loss we were able to disentangle their effects.
This approach also sidesteps the main difficulties encountered by other works, e.g., using stability- based bounds [49, 38, 19] which either diverge with training time or have dimension dependence.
4.3 Generalization Guarantees Applicable for Neural Networks
Many additional lines of work established generalization guarantees applicable for NNs, but are less directly related to our work. These results have some limitations that do not exist in ours. For example, NTK analysis [29] can imply generalization guarantees certain settings, but they do not allow for feature learning: Mcan-field results [45] require non standaadd initialization and specific architectures; Algorithmic stability analysis Bousquet and Elisseeff [7], Hardt et al. [26), Richards and Rabbat [60], Lei et al. [36], Wang et al. [67] only apply when the number of iterations is sufficiently small;
Norm-based generalization bounds [6, 22] ignore optimization aspects and depend exponentially on the network's is depth; And bounds for random interpolators [8] involve impractical training procedures.
closely related setting the one studied here is SGLD, i.e. a discretized version of CLD. There an extensive line of work bounding the generalization gap of such models (see [59, 49, 55, 51, 18, 19, 13] for partial list). These results typically have a significant dependence on hyperparameter stemming from the discretization such as the learning rate and batch size, or suffer from constraints similar to the ones discussed in Section 4.1, such as dependence on trajectory or dimensionality (c.g. via smoothness, parameter norms, log-Sobolev or spectral gap constants).
5 Discussion, Limitations, and Future Work
Summary. We derived simple generalization bound for general parametric models trained using a Markov-process-bent algorithm, where the dynamics have stationary distribution with bounded

---

potential or expected potential. For CLD with reuulaizationboundddnes constraint matching the initial distribution, we proved that the model generalizes well when the inverse temperature of order / = O (N). There are several interesting directions to extend this result.
Non-isotropic noise. We can consider more general model for training, such
d0,- Vis (0.) dt + Σ (0.) dw, + dr,,
where E is matrix-valued dispersion coefficient, and r. is some regularization process, such as e regularization or reflection process in bounded domain. In contrast, in this paper, to derive concrete generalization bounds, we focused on CLD with isotropic noise, i.e. such that Σ is scalar multiple of the identity matrix. The reason for this was that our bound (Corollary 3.1) relies on explicit analytical expressions or bounds on stationary distributions, which are difficult to find in the general case. In addition, in typical overparameterized settings, the noise induced by the randomness of SGD may not only be non-isotropic, but also singular with low-rank. The analysis of such processes poses various challenges beyond the ubility to derive an analytic form for their stationary distribution. For example, they may concentrate on low-dimensional manifolds, possibly making the KI.-divergence term infinite, or making some of the assumptions unrealistic (e.g. the choice of initial distribution).
No regularization. In this work, we only considered processes that have stationary probability measures, For this reason, in the examples in Section 3 we used either a bounded domain or regularization. This seems essential for generalization f - oc, unless there are other architectural constraints. For example, consider training a model for the classification of randomly labeled data. Without regularization, a sufficiently expressive model is likely to arrive (at some point) at high training accuracy, yet it cannot generalize in this setting. Nonetheless, it might be possible to ensure generalization as a function of time, but here we focus on indeenddeen bounds.
Discrete time steps. The behavior of SGD with a large step size may be qualitatively different than that of the continuous process considered here. Specifically, Azizian al. [4] showed that while the asymptotic distribution of SGD resembles the Gibbs posterior, it is influenced by the step size and geometry of the loss surface. While an extension of our analysis to this setting is straightforward given a stationary distribution, such stationary distributions are typically hard to find explicitly (except in simple cases, such as quadratic potentials), and the error terms coming from their approximations are typically detrimental to finding non-vacuous generalization bounds, as they may depend on the dimension of the parameters through the model's Lipschitz or smoothness coefficients. etc. (49, 38, 19. 14). Hence, direct application of our approach to such algorithms requires additional considerations. An alternative approach is to incorporate a Satropolis-Hastinge type rejection [47, 27], ensuring that the stationary distribution is indeed the Gibbs posterior.
Can noise be useful for generalization? There is long line of work in the literature (e.g. see [20] and references therein), debating the effect of noise on generalization. Our work does not imply that higher noise improves the test error, only that decreases the gap between training and testing. Since higher noise could hurl the training error, the overall effect depends on the specific situation. Even if introducing noise does not improve test performance, there could still be an advantage to introducing noise, based on our results, in that it reduces the gap and thus could increase the training error to match the test error in cases we cannot hope to learn (i.e. to get small test error). This a good thing since it prevents being mislead by overfitting, hopefully without hurting the test error when we can generalize well (i.e. in learnable regimes, both training and test errors are low, perhaps also without noise, but in non-learnable regimes, where the test error is necessarily high, noise forces the training error to be high as well, so that the gap is small). Indeed, in our small-scal scale experiments in Appendix F, we noticed that a small amount of noise can decrease the generalization gap, without significantly harming the test error (e.g. see the bottom half of Tables 2 to 4). Further analysis is necessary in order to establish general conditions under which test performance is not significantly hurt by noise, while ensuring a small gap. This, in particular, requires studying the effect of noise on the training loss, and what noise level still ensures obtaining a small training loss in learnable regimes.
Acknowledgments and Disclosure of Funding
The research of DS was Funded by the European Union (ERC, A-B-C-Deep. 101039436). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the
10

---

European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of the Schmidt Career Advancement Chair in AI. GV is supported by the Israel Science Foundation (grant No. 2574/25), by research grant from Mortimer Zuckerman (the Zuckerman STEM Leadership Program), and by research grants from the Center for New Scientists at the Weizmann Institute of Science, and the Shimon and Golde Picker Weizmann Annual Grant. Part of this work was done as part the NSF-Simons funded Collaboration on the Mathematics of Deep Learning. NS was partially supported by the NSF TRIPOD Institute on Data Economics Algorithms and Learning (IDEAL) and an NSF-IIS award.
References
[1] Pierre Alquier et al. User-friendly introduction to pac-bayes bounds. Foundations and Trends@ in Machine Learning, 17(2): 1743337,,3 2024.
[2] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 2009.
[3] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International conference machine learning. pages 263. PMLR, 2018.
[4] Waiss Azizian, Franck Iutzeler, Jerome Malick, and Panayotis Mertikopoulos. What is the long-run distribution stochastic gradient descent? a large deviations analysis. In Forty-first International Conference Machine Learning, 2024. URL /tttps://openreviow net/ forum? Darun?id=vsOF7qDlt.
[5] D. Bakry and M. Émery. Diffusions hypercontractives. Jacques Azéma and Marc Yor, editors, Séminaire de Probabilités XIX 1983/84, pages 177-206, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. ISBN 978-3-540-39397-9,
[6] Peter I. Bartletr, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[7] Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2: 499-526, March 2002. ISSN 1532-4435. doi: 10. 10.1162//5324333770000007 URL https: / //doi. 11111111/3/413277751000
[8] Gon Buzaglo, Itamar Harel, Mor Shpigel Nacson, Alon Brutzkus, Nathan Srebro, and Daniel Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. In Ruslan Salakhutdinov, Zico Kolter, Kather- ine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Pro- ceedings of Machine Learning Research, pages 5035-5081. PMLR, 21-27 Jul 2024. URL https: //tppss:///ccceingg.. mlr press/v2355/ 2r/235/buuag12228 html.
[9] Olivier Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning, arXiv preprint arXiv:0712.02248. 2007.
[10] Ping-yeh Chiang, Renkun Ni, David Yu Miller, Arpit Bansal, Jonas Geiping, Micah Goldblum, and Tom Goldstein. Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. In The Eleventh International Conference on Learning Representations, 2022.
[11] Thomas M. Cover. Which processes satisfy the second law? J. Halliwell, J. Perez-Mercaderr, and W. H. Zurek, editors, Physical Origins of Time Asymmetry, pages 98-107. Cambridge University Press, New York, 1994.
[12] Thomas M. Cover and Joy A. Thomas. Entropy, Relative Entropy and Mutual Information, chapter 2, pages 12-49. John Wiley & Sons, Ltd, 2001. ISBN 9780471200611 doi: https:
hidbi..rg/10.1100//44111200 1.h2. URL https: tettps:://oniaae inel cooniinelbbrarn ibbrrr. bobbbrrr.wwlley.........l.be.eee wiley.com/doi /abs/ 10. 10.1002//471200611 ch2.

---

[13] Lecllo Tadesse Dadi and Volkan Cevher. Generalization of noisy SGD in unbounded non- convex settings. In sorood International Conference on Machine Learning. 2025. URL nttps://openreviev.. wtt.:e.tteeettooommdddattrr1111
[14] Benjamin Dupuis, Paul Viallard, George Deligiannidis, and Umut Simsekli. Uniform gener- alization bounds on data-dependent hypothesis sets via pac-bayesiaa theory on random sets. Journal of Machine Learning Research, 25(409):1-55 2024.
[15] 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.
[16] Gintare Karolina Dziugaite and Daniel M. Roy. The size of teachers
measure of data complexity: Pac-bayes excess risk bounds and scaling laws. In Yingzhen Li. Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 3979-300 3987. PMLR, 03 05 May 2025. URL https: htttps:/pproceednngg mmr. press/v258/ /2155////igaaaee25e html.
[17] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbich, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics, pages 604 612. PMLR, 2021.
[18] Tyler Farghly and Patrick Rebeschini. Time-independent generalization bounds for sgld in non-convex settings. Advances in Neural Information Processing Systems, 34: 34:19836-19846, 2021.
[19] Futoshi Futami and Masahiro Fujisawa, Time-independent information- generalization bounds for sgld. Advances in Neural Information Processing Systems, 36:8173-8185, 2023.
[20] Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein. Stochastic training is not necessary for generalization. In International Conference on Learning Represen- tations, 2022. URL https:
[21] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Reseurch, pages 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May mlr wwtpaaaw.........eeeeeeeeeeeeere hltp///llot////// 10a html.
2010. PMLR. URL.
[22] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018.
[23] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization matrix factorization. In I. Guyon, U. Von Luxburg, S. Ben- gio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[24] Arjun K. Gupta and Daya K. Nagar. Matrix Variate Distributions. Monographs and Surveys in Pure and Applied Mathematics. Chapman & Hal//CRC Boca Raton, FL, 1999. ISBN 978 9781584880462.
[25] Boris Hanin. Random neural networks the infinite width limit as gaussian processes. The Annals of Applied Probability, 33(6A):4798 4819, 2023.
[26] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[27] W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, (7(1)9771 1970. ISSN 00063444, 14643510. URL http: btstp://www //www.jstorrrrr org/ stable/23349..
12

---

[28] Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leve performance on imagenet classification, In Proceedings of the IEEE international conference computer vision, pages 1026-1034, 2015.
[29] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernll: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[30] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International conference on machine learning, pages 1732-1732. PMLR, 2017.
[31] Weining Kang and Kavita Ramanan. Characterization of stationary distributions of reflected diffusions. The Annals of Applied Probability, 24(4):1329 1374, 2014. doi: 10.1214/
13-AAP947. URL https://dos oooooogg//// 1214111-1991/1
[32] Weining Kang and Kavita Ramanan. On the submartingale problem for reflected diffusions in domains with piecewise smooth boundaries. The Anmals of Probability, 45(1):404 - 468, 2017. doi: N0.221/16-A0P11533 URL https: //tp:///oiioooo org/ 10. 1214/1211111/ 1114/16-A0P1153.
[33] Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher. High probability bounds for class of nonconvex algorithms with adagrad stepsize. arXiv preprint arXiv:2204.02833, 2022.
[34] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL attp://arxe http:///aaxivv..oaaaaooo 1412..1..9999
[35] Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein Deep neural networks as gaussian processes. In International Conference on Learning Representations (ICLR), 2018. URL https:://aaiii/// http:::////vvvieeee http:////aaxxi..oo////////11...1
[36] Yunwen Lei, Rong Jin, and Yiming Ying. Stability and generalization analysis of gradient methods for shallow neural networks. Advances in Neural Information Processing Systems, 35: 38557-38570, 2022.
[37] Kfir Yehuda Levy, Ali Kavis, and Volkan Cevher. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL httpss:/ net httee//ormmmnddtteeeeeope/s
[38] Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020. URL https: //t///opppnn/ /ttp://veeeeeeieee///////e wwtp:/.ee/oorruueeeeeeeeeee peet/foruum?tddSkxxgggtt
[39] Sanae Lotfi, Marc Finzi, Sanyam Kapoor, Andres Potapczynski, Micah Goldblum, and An- drew G Wilson. Pac-bayes compression bounds tight that they can explain generalization. Advances in Neural Information Processing Systems, 35:31459-31473, 2022.
[40] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference Learning Representations, 2020. URL https: / //openreview
[41] Stephan Mandt, Matthew D Hoffman, and David M Blei. Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1-35, 2017.
[42] Alexander G de Matthews, Jiri Hron, Mark Rowland, Richard E Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018.
[43] Andreas Maurer. note on the pac bayesian theorem. arXiv preprint cs/0411099, 2004.
[44] David McAllester. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pages 230-234, 1998.
13

---

[45] Song Mei, Andrea Montanari, and Phan-Ming Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33): B7665-EE777, 2018.
[46] Neri Merhav. Data processing theorems and the second law of thermodynamics. IEEE Transactions on Information Theory, 47($):4926-4939, 2011. doi: 10.1109/T11:2001122555
[47] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. Technical report, Los Alamos Scientific Lab., Los Alamos, NM (United States); Univ. of Chicago, IL (United States), 03 1953. URL https://www..... osti gor/bbbb1oo/43055778 http:://ww...ottt.oo//bbba//////
[48] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland. Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015,
[49] Wenlong Mou, Liwei Wang. Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pages 605-638, PMLR, 2018.
[50] Radford M. Neal. Priors for Infinite Networks, pages 29-53. Springer New York, New York, NY, 1996. ISBN 978-1-4612-0745-0,, doi: https://doi. http:::///o..or/1//0/ 1007 10007/978---411--074--00000
URL
[51] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-theorrtiic generalization bounds for sgid via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.
[52] Yurii Nesterov. A method for solving the convex programming problem with convergence rate o(1/k²). Proceedings of the USSR Academy of Sciences, 269:543-547, 1983. URL sew.aapismmmmnnccccolllt.t
hes//CrrpuSDDD: 145918791.
[53] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 201 URL http://ufld) stanford. hath/hooseenumerrr/nipp220212111
hhoussuumeree.s..... harreaamrrrrrttpaoooooooooaeerer .dff.
[54] Bernt Øksendal. Stochastic Differrntiaal Equations, pages 65-84, Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. ISBN 978-3-642-143944 6. doi: 10. -49-7/99988-3-64--4449---- URL
https:///oi. /ttp:::///oo..r//1/... 1007 97-97778---33- 14394-6_5.
[55] Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
[56] K. B. Petersen and M. S. Pedersen. The matrix cookbook, nov 2012. URL http://www2. compute dtu. dk/ wwtppbddd/ppuaeee /ttbddb/pubs/3224444 3274 full. full.html. html. Version 20121115.
[57] Andrey Pilipenko. An introduction to stochastic differential equations with reflection, 09 2014.
[58] Maxim Raginsky, Alexander Rakhlin, Matthew Tsao, Yihong Wu, and Aolin Xu. Information- theoretic analysis of stability and bias of learning algorithms. In 2016 IEEE Information Theory Workshop (ITW), pages 26-30, 2016. doi: 10. 0ttp////T.0011776777735
[59] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
[60] Dominic Richards and Mike Rabbat. Learning with gradient descent and weakly convex losses. In International Conference on Artificial Intelligence and Statistics, pages 1990-1998, PMLR, 2021.
[61] Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-323, 2020. doi: 10. 10.1109/TT22019924457777
14

---

[62] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 2XXv:1707.06347, 2017.
[63] Zeev Schuss. Euler's Scheme and Wiener's Measure, pages 35-88. Springer New York, New York, NY, 2013. ISBN 978-1-4614-76687 doi: 10.1007/978-144614--677---- URL
https://doi. http:://do...rg/1..... /ttt:///0010007711---11111-1---0
[64] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. Journal of Machine Learning Research, 19 (70):1-57, 2018.
[65] Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 60(7):3797-3820 2014.
[66] Gal Vardi. On the implicit bias deep-learning algorithms. Communications of the ACM, 66 (6):86-93, 93, 2023.
[67] Puyu Wang, Yunwen Lei, Di Wang. Yiming Ying, and Ding-Xuan Zhou. Generalization guarantees gradient descent for shallow neural networks. Neural Computation, 37(2))344 402, 2025.
[68] Jonathan Wenger, Beau Coker, Juraj Marusic, and John P Cunningham. Variational deep learning via implicit regularization. arXiv preprint arXiv:2505.2025: 2025.
[69] Florian Wenzel, Kevin Roth, Bastiaan Veeling, Jakub Swiatkowski, Linh Tran, Stephan Mandt, Jasper Snoek, Tim Salimans, Rodolphe Jenatton, and Sebastian Nowozin. How good is the bayes posterior in deep neural networks really? In International Conference on Machine Learning, pages 10248-10259 PMLR, 2020.
[70] Aolin Xu and Maxim Raginsky. Information- analysis of generalization capability of learning algorithms. Advances in neural information processing systems, 30, 2017.
[71] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
15

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See Sections and 3.
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 in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on 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 images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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 proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
See Sections 2 and 3 and appendices.
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 referenced in 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 to provide short proof sketch 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Appendix F.
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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 can also be provided via detailed 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, or other means that are appropriate to the research performed.
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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, 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 to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [No]
Justification: The experiments conducted use standard models and datasets, and are described in a manner that allows for simple reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
iiyy for more details.
While encourage the release of code and data, 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. cc/ ccc/publicgguiii /eliddeseCooeubbnn wwwsssslicccyyii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, 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 to understand the results?
Answer: [Yes]
Justification:
The required details appear in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
18

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо 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
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiments are not computationally demanding and can be reproduced with basic resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:
Answer: [Yes]
Justification:
This work does not deviate from the 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 sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The research conducted in this work theoretical, and foundational in nature. Thus, there are no broader impacts we feel must be specifically highlighted.
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 considerations.
19

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe 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 research conducted in this work is theoretical, and foundational in nature. Thus, there are no risks we feel must be specifically safeguarded.
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 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
Question: 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?
Answer: [Yes]
Justification: We properly reference previous theoretical work throughout the paper, and the datasets used for experimentation in Appendix F.
Guidelines:
The answer NA means that the paper does not use 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 URI
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 use in package should be provided. For popular datasets, paperswi twwode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
20

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if 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:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include 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 nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 or equivalent for research with human subjects
Question: 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
21

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it 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: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https //tpr///nnuu../eeeeee tweeurip..cc/oofeeeeeee /LLM) for what should or should be described.
22

---

denote the volume Appendix structure:
Appendix A we recap and establish notation and conventions, and present some well- known lemmas.
In Appendix B we prove Theorem 2.7 and its related claims in Section 2.
In Appendix C we discuss the tightness and necessity of the divergence conditions found in Appendix B.
In Appendix D we prove generalized version of Corollary 3.1.
The bounds found in this paper only bound the generalization gap, and not the absolute error of a model. In Appendix E and Appendix F we study the applicability of our bound in realistic settings. Specifically, whether the regime in which the bound on the generalization gap is non-vacuous allows for meaningful learning, i.e. coincides with a regime in which the absolute training error is also small. In Appendix E we study linear regression trained with CLD, for which we can analytically characterize the training loss, and in Appendix F we experiment with NNs trained with SGLD (discretized version of CLD) on standard training sets.
As Section 3 deals only with models trained with some form of regularization, it is natural ask whether the regularization alone sufficient for the use of uniform convergence to arrive the desired generalization bounds. In Appendix G we show that the regularization used in Section is not sufficient for such bounds, and that the models can remain highly expressive.
Finally, for completeness, in Appendix H we recall some definitions and properties related to SDEs used throughout the paper.
A Preliminary and Auxiliary Results
A.1 Preliminaries
We start by restating and introducing notation.
Notation. We use bold lowercase letters (e.g. E Rd) denote vectors, bold capital letters to denote matrices (e.g. A E Iddx)), and regular capital letters to denote random elements (e.g. S, X, Y). We may deviate from these conventions when it does not create confusion. Unless stated otherwise, all vectors are assumed to be column vectors. Specifically, we use e; E IRd, i I,...,de d, to denote the standard basis vector with 1 in the ith entry, and elsewhere. For a subset ft S Rd we denote by 12, 0R, and !2º, the closure, boundary, and interior of Ω respectively. In addition, of C. Q2 when it defined, by [B) With some abuse of notation, when
finite we denote its cardinality by [B]. We use ||-II for the standard Euclidean norm on RR Then, the open Euclidean ball centered
Fdd with radius > is B, (x) {y Rd | Ily x| < r). In addition, we use } for the indicator function, and specifically for A C IRd and x E Rd IA {x) = 1 {x E A). We denote the set of all probability measures over Ω by A (Ω). For some
A (S) with density p. with some abuse of notation we denote p E A (2). and p (B) = μ (B) for measurable B C Ω. In addition, use Ex~p or Ep to denote the expectation w.r.t p, and omit the subscript when it can be inferred. For two distributions μ., with densities p, we denote by KL (μ their KL-divergence (relative entropy). Furthermore,
() = (L (] 6n 8).
H (8) - In (6) 5 E [0, 1). for the binary entropy function (in nats). We denote the divergence of a vector field by V. and the gradient and Laplacian of scalar function by V and A V V. respectively. Given domain C R and k E Z4 U {oo}, we denote by C* (F)) the set of real valued functions that are continuous over E. and k-times continuously differentiable with continuous partial derivatives in E. In particular, C CD) is the set of continuous functions.
Conventions. Unless stated otherwise, we use Ω C Rd to denote a non non-empty, connected, and open domain. In addition, we follow the following naming conventions for probability distributions.
For a discrete/comtimuous-tiie Markov process, we use Pu. or Pt for its marginal distribution at time N or t I4..
23

---

We denote stationary distributions of Markov processes by Poo-
the context of PAC-Bayesian theory, we denote prior distributions by p. and data dependent posteriors by Ås-
In case some stationary distribution also data-dependent, we use Pao.
We also use p, q for generic distributions, or modify the pervious notation.
A.2
General Lemmas: Data processing inequality and generalized second laws of thermodynamics
For completeness, we start by proving some well known results in probability and the theory of Markov processes.
Lemma A.1 (Data processing inequality). Let (x, y) and a (x, v) be the densities of two joint distributions over a product measure space X x Denote by px (x) qx (2) the marginal densities, e.g.
/ 1 (x. dy
px (x)
and by p (y x) , ()) the conditional densities, so p (a, v) p x)) px (z), and similarly for Then
KL (px ll (x) KL (p))g)
Proof. By definition of the KL divergence
KL (pll))) = /
p (2x, y)
p p(r,y) In
drdy
q q v)
xxy
/
(v 1) px (z)
(xx 8) In
drdy
1 (v x) 9x (x)
Xxy
/ ((r,)))
px (x) ax (x))
/ p(r,y))l
(pyy x)) q x.)
dody +
dady
=
X'xY
X'x3'
=f p (0012) (x) PX (z) In
Px (Ir) qx (x)
(p(v x)
drdy
px (z) (y)
x)) In
drdy
(v x))
XXy
Xxy
- px (x) In
Px (x) qx (z)
p X)
[Fubini]
dr + E Exapx
p(y X)In
dy
9 x)
= KL (px || (xx) + Ex-px KL (p
X) (- (x)x)
The KI. divergence non-negative and therefore the expectation in the last line is non-negative as well, and we conclude that
KL (pllg) 2 KL (px 4x
Let Xx, J be discrete-time Markov chain on Ω C Rdd with transition kernel P such that for all n E No.
PA+1 (v) f P(y x)) (x) dz.
52
In addition, assume that the there exists an invariant distribution Poe such that
/ P Poo (x) dr.
Poo (v)
We proceed to present generalized form of the second law of thermodynanics, regarding the monotonicity of the (relative) entropy of Markov processes with possibly non-uniform stationary distributions [11, 12].
24

---

Lemma A.2 (Generalized second law of thermodynamics), For all n 2 0,
KL (pu+1 |l Poo) I KT. (Pr. Poo)
Proof. First, note that assume that KL (pn P oo, since otherwise the claim holds trivially. Let (z, y) Pa (x) P (y x) be the joint densities of (Xn, Xa+1) where X, Pas and let () Poe (x) yy 1)) be the joint distribution under Xx Poc. By definition of pa+l.
qy (v) Pn+1 (3)
and by definition of the stationary distribution,
(1) Poc (v)
Therefore according to Lemma A.I,
KL (pu+1 Poo) S KI (g]lr)
In addition,
KL (g(r)) = / (x, In
(z. y) (xx
drdy
axΩ
/ QxΩ
(x:) P (y x))
q (x, v) In
drdy
Poo (x) P (y x))
/
Pn (x)
q (z, y)) In
drdy
=
(z)
9xΩ
/ Pn (x) (y x)
Pr (x)
drdy
Poo (x)
QxΩ
Pr (x)
[Fubini]
Pn (z) In
dr
Poo (x)
=KL (pn Poo)
and overall
KL (pu+1 Po S KL (pr Poo)
A similar result can be obtained form Doc (-I Lemma A.3 (The Pointwise Second Law). For all n >> 0:
Doo (Pa+1 (/)) S Dzo (pm poc)
Proof. Let p. q be some probability measures such that de exists. By definition, dy
Doo (p ess sup, In dp inf fOERI 1 (((( In dp > =0]=
dq
dq
Let C E and suppose that for all measurable c X, (A)) s e (A). Assume by way of
contradiction that D:o (p > C, that is, that there exists > C such that
(1
In dp dq
o 0.
Denote
dp
4 =
In
c
dq
25

---

then
[ dp du E ( e
(
dg
in contradiction the assumption. Therefore, for all C' such that p (A) S e (A) for all measurable A, C' 2 Doe (p q). We can now show the claim.
Let P(dy | x)) be the processes' transition kernel (in measure form). We can assume Do (pr. || Poo) oo, since otherwise the claim holds trivially. Let be measurable, then by definition,
Pa+1 (A) / P(A x)) dpn (x) = f P(A x)) dpn (a:) dp (x)
dp
pew) poo) f P P(A dpo (x) = Dalon ll P Poo Poo (A),
- Doc (Pm DD
so Do (pn+1 Poo) S Doc (pn Pro)
We state the relevant results for continuous-time processes.
Corollary A.4. Let Xx be Markov process with marginals p; and stationary distribution Poo. Then, for all t 0:
KL (p: Poo) < KL (po Poc) or Doo (Pr Poo) Doo (po Poo)
Proof. Let 0 < and let At > 0 such that t E At N. Define Y, = Xndis then Y, is discrete time Markov chain with marginals Pn-Ar and stationary distribution Peo, so Lemma A.2 and Lemma A.3 imply the results.
26

---

B Proof of Theorem 2.7 and its Related Claims in Section 2
In this section, present the proof of Theorem 2.7, the claims leading to it, and some of its generalizations.
B.1 Derivation of Corollary 2.5
Recall Claim 2.3. If p,9,14 then
9,94, (4, are probability measures, and is Gibbs w.r.t & with potential V < oc,
1. KL (p + KLy (q |1 p) E, v - 1E v
2. D (p q) D (q [I) = css sup, vp - ess inf, W.
In particular, KL (p || 4) + KL (q p) = B,y vt - Ep v, and Do (pll4) D (g = ess ess sup, v
ess inf,
Proof. By definition
de
= 2 - where Z < oo is the appropriate partition function. Then we du
have
KI, (g) KL, (gllp) / dulnn dq
dp + / dv dg dp = / (-v In dd + / (V+ +
dv E E V.
Also,
dp
dg dp/
D (pllg) + Dx (4 [1) = In e88 cus # dg
+ In ess sup,
= ess sup, (-V In 2) + ess sup, (V + In 7) = ess sup, ess inf p. V
where in the last equality we used the fact that ess (-v) css inf v and that Z is a constant.
Using the Chain Rule and Claim 2.4, derive the bounds of (1) and (2), re-stated and established in the following lemma.
Lemma B.1. If Pt is the marginal distribution of a Markov process with initial distribution po at time t, Poo is stationary distribution, and v is probability measure, then
KL. (p+ll) S KT. v) + KT (v Pox) KT (Poo [1v)
and similarly,
Doe (pt 1) - Doo (po v) + Do (w)) D% (poc 11
Proof. This is a simple application of the chain rule,
(T. = / dp, In dp: = f dp, In dp dp KT. (pr (o + KT., (poo v) dp dy
dv
< KL (po ( + KLp, (Pee || ||)) = KL (po || + KL (v (po)) + KLp, (poo (|
where in the first inequality we used Claim 2.4. Similarly,
Doc (pe u) = css sus In dp: css sup In dp: dy dv I Doo (po p + D (poo || = Doo (po v) + D (v p1 + DP: (poo l|
dpcc du - Doc (pe (ac)) + DPr (poc v))
Corollary 2.5 now follows from plugging in Claim 2.3 into Lemma B. Given these bounds on the divergences, All that remains in order to prove Theorem 2.7 is plugging Corollary 2.5 into a PAC-Bayes bound.
27

---

B.2 In-Expectation PAC-Bayes Bounds
Theorem B.2 (Theorem from Maurer [43]). For any 8 E (0, 1) and any N 8, for any data-
independent prior distribution
KL (pll + In
N
P PSWDN Vy kl EE (h) || E (h)) -
2 21-8,
N
where kl (a [) aln & + a) In 1 for 0 S a, is the Kl. divergence for Bernoulli
random variable, and P denotes a posterior distribution.
B.3 Single-Sample PAC-Bayes Bounds
Theorem B.2 can be viewed as a bound in expectation over the draw from the posterior, which corresponds to the traditional PAC-Bayes view of considering the expected error of randomized predictor. But it is actually possible to get guarantees for a single draw from this predictor, which is more appropriate when view the randomness part of the training algorithm, that then outputs single deterministic predictor (chosen at random). High probability guarantees for single draw from the posterior were shown by Alquier et al. [1] based on Catoni [9] and also discussed by Dziugaite and Roy [16]. Here we present a tight version based on a simple modification to Maurer's proof [43].
Theorem B.3. For any 8 10 and N 2 8, for any data independent prior p. and any learning rule specified by a conditional probability h S ~ ps such that p < ps S-a.s,
In
dĀs de
(h) + N
P PNDDN ho-ps
kl (Eg (h) 1I ED (h))
2 1 6
and so, by the definition of Doo (ps p).
Doo (0s (l)) + In 2v'N
PS-DN Joups (I(S (h) || ED (h)) S
21-8.
Proof. Following and modifying the proof of Theorem 5 of Maurer [43], we start with the inequality Es [e (i((Fs(h) [D(A)]] < 2 [43, Theorem 1], which holds for any h, and so also in expectation over h w.r.t. pt
2v N Es [exp (N kl (Es (h) ED (h))) EglEs~ (exp (N kl (Es (h) Ep (h)))
with a change of measure from p to ps.
dp
EsLEnups
exp (N kl (Es (h) ED (h)))
(h))
(13)
dps
exp N kl (h) Ep (h)) - In dps
-Es
(h1
(14)
dp
Now applying Markov's inequality, we get:
Ps exp N (Es (h) ED (h)) - In dōs (h)
2/N
> 1 - 8.
(15)
dp
8
Rearranging terms, get the desired bound.
B.4 Arriving at Theorem 2.7
Theorem B.4. Consider any distribution D over Z, function f H x 2 - [0, 1), and sample size N > 8, any distribution over H, and any discrete or continuous time process {he E H2 (i.e. L E Z. or I E IR,) that is time-invariant Markov conditioned on S. Denote po(: S) the initial distribution of the Markov process (that may depend on S). Let (oo S) be any stationary distribution of the process conditioned on and (h) 2 0 a non-negative potential function that can depend arbitrarily on S, such that p (:; S) is Gibbs w.r.t. v with potential V s. Then:
28

---

1. With probability 1 - 5 over S ~ D
KL (po(:))) + ( +13 2/28 (16)
N
and so
KL (po 5) v) + E2 [ In2vN/6
I - Es & V 2E [Es (ht) S]
KL (po(:; 5) 11 + L ( + 1n2v//6
(17)
N
2. With probability 1 - 5 over S ~ DN and over hy:
Doc (po(:; [) + ess pu Vis(ho) + In 122v
(ls(s (E())) S
(18)
N
and when (h() < ED(h))
Doo (po(::)) + ess supp, ws(ho) + 1n2vN/6
Ep(hi) - Esshh) V 2Es (ha)
N
Doo (Po(::)) + esssupp,
+ +s(ho)) 1n2vN/66
(19)
N
Lemma B.5. Let a, E [0, 1]. Then
b a 22kl (a ()) + 2kl (a (]
(20)
Proof. The KL divergence is non-negative, so suffices to consider the case that b 2 a. Defining ; [0, 1 a| + R as
(u) 2 (a u) it can be readily checked by differentiation that for all E 10, - a).
(a u) 2 (u).
In particular, for b a e [0.1
(b (b-a)²
kl (a 2
(21)
2b
Next, we consider the following inequality
2u² V2au + - b > 0, 2 0.
(22)
Solving for u, it turns out that the inequality holds when
88b 6a 2a
(23)
In addition, under the assumption that b 2 a
v8b- 6a v 2a
(b ab=
(24)
4
2h
Combining (21), (23), and (24), a / kl (a b) solves (22) implying (20).
Proof. The inequalities (16) and (18) follow by plugging Corollary 2.5 into Theorems B.2 and B.3. For mequalities (17) and (19), we use (20). For (17), we use a (h, and b Es(h,), which yields:
Ep(h+) s Es(h.) + /2 kkl (Es
ED ED())) + 2kl (Es(he) (bhh)))
S Es(h + V (hss) KL (po(:: 5) v)) + Epo (ho) + In 2/N/8
N
KL (po 11)) + Epo v sho)) + 22
+
N
and similarly for (19).
29

---

Remark B.6. Notice that when h2 has small training error E [Es (h,) [] = 0, the effective generalization gap decays as O (1/N) instead of as O (1/vN)
Remark B.7. In order to get the version in Theorem 2.7 we use the upper bound of Pinsker's 's inequality, i.e. that for all a, E (0,
la bl = /1laa))))
and simplify N 5
I In as 288.
Finally, we prove the equivalence statement made Footnote 7:
Claim B.8. KL (pl1g) + KL (q (1 S 3 iff there exists a potential such that p Gibbs w.r.f. with potential Vo and Eg V V S B, and similarly Doc (p || q) + Dos (q ll S 3 iff there exists potential V S such that p is Gibbs w.r.t q with potential V.
Proof. The first direction follows directly from Claim 2.3,
only need to prove the converse.
Assume that either KL (p || q) + KL (q [] S 3, or Do (p || q) + Doo (q
both dp/ dg and dq/ dp exist, and for any measurable event B, (B) = p) S 3. In these cases,
q (B) 0, or equivalently, p ( > 0 > q (B) > 0. Therefore, supp (p) supp (g). and dp/ dq > 0 on supp (p). Denote V in the proof of Claim 2.3 results in the bounds E, v - E, v S and ess sup, ess inf, < 8
In dp/ dg. then p is Gibbs w.r.t q with potential w The same derivation as
In particular, if the latter holds then V can be shifted such that essentially 0 V S B.
30

---

C Tightness and Necessity of the Divergence Conditions
If we are only interested in ensuring generalization at time t + oc, and when we converge the stationary distribution Pac, then it is enough to bound the divergence D (Poo || v). If we are interested in bounding D (pt || v) (and consequently, the generalization gap) at times then we need also to limit Po s dependence on S, since pu (as well as pt for small t) can be completely different from stationary Pse. and just bounding D (Peo (n) does not say anything about it. Bounding D (po 14), for some data-independent distribution μr, ensures generalization at po- This leaves the following questions regarding the proof of Theorem 2.7:
Why do we need to bound the divergences D (p |] and D (po || 1) from the same distribution v? That is, we do we need to require μز = !/? Bounding the divergences of po and Peo to two different divergences μ # y is sufficient get generalization at the beginning (i.e. initialization) and end (i.e. after mixing)-is it sufficient for generalization in the middle (i.e. at any t)?
Why do we need to also bound the reverse divergence (v pp I.e., why do we need to require Poe is Gibbs w.r.t. y with a bounded potential, instead of just controlling the divergence D (peo [| v)) which is a weaker requirement and sufficient for generalization after mixing?
As now show, both necesairy, and without requiring both, i.c. if we drop either one of these, we cannot ensure generalization at intermediate times f 2 0.
Construction.
Consider supervised learning problem with Z X' ", (0, 1}, H. = all measurable functions from to y, and the zero-one loss f(, (z,y) = (h(a)) y). with D being the uniform distribution over X, and y being Bernoulli( independent of x. For all h, (h) 0.5. Let po be the constant zero function with probability 1 and the constant one function with probability 3. Consider the following deterministic S-dependent transition function over h: he is the constant zero function, then h++1 hy which memorizes S, i.e. hs(x)) = y for (x, E S, and hg (x)
otherwise. If h2 is not the constant zero function, then h441 is the constant ones function. We have that Poo is deterministic at the constant one function, and KL (pxx ll In 2, and in fact Pt. = Poo for & > 1. But with probability half, h = hg, for which for any sample size while (hs)
N > O, Es(hs)
How does this show it is not enough to bound D (po 1v and D (Poc |] but that we also need the reverse D (v/ Pxo) Since Po is data independent, we can take
Po. in which case KL (Po || v) = Do (Po v/) = 0 and KL (Poo |l v)) = Do (pxc || v) = In 2, but even as N + oo, the gap for h does not diminish. Indeed, D (v Poo) co, and so pou is not Gibbs w.r.t. y and Theorem 2.7 does not apply.
How does this show it is not enough to bound D (Pec || D (v/ P and D (po |l (1) for μ # 1/? Since in this example P is also data independent, we can take v = Pso and μl = Po, in which case D (Po (4) O and D (poo || () + D (v/ Poo) = O. We are indeed ensured small gap for ho and hoo, but not for h1.
31

---

D Generalized Version of Corollary 3.1
We start by characterizing the stationary distributions of SDERs in box with different noise scales o². The stationary distributions for Gaussian initialization can be found similarly. Then, we extend Corollary 3.1 scenarios where Po o v, as an immediate consequence of Theorem 2.7.
D.1 Stationary distributions of CLD
We first derive the stationary distribution of SDERs of the form
(25) with normal reflection in box domain (for full definition (45) in Appendix H.2), where T. 2 0 is some C2 loss function, 33 > 0 is an inverse temperature parameter, and 6² is a diffusion coefficient. First, we present well known characterization of the stationary distribution of (25).
dx: L (xx) dt + /28-10² (xe)dw, + dr:;
Lemma D.I. If, C2, a² (+) > 0 is uniformly bounded away from 0 in 12
V L
(x) σ
2
exp
-8
dx
< 00,,
(
the integrals exist, and the field V//0² 02 is conservative (curl-free), then
7 o2 (x) exp (-8
V VL (x)
Poo (x)
dx
(26)
x² (x)
is a stationary distribution of (25).
For completeness, the proof is presented in Appendix 1.2.1, following additional results and defini- tions in Appendix H. We can now calculate explicit stationary distributions for some choices of o². Specifically, focus cases where 2² (x) g [T. (x)) for some scalar function g. it guarantees the curl-free condition, and is convenient to integrate.
Example D.2 (Uniform noise scale). Assuming that o² (x) 1, the stationary distribution becomes the well-known Gibbs distribution
1 -L((x)
Poo (x) z
(27)
so
M uniiform (x) = 3L (x)
(28)
Example D.3 (Linear noise scale). Let a > 0, and suppose that o² (L(x) + a). Then
VL V (x)
(In(((())+a)
a² (x)
so the stationary distribution is
Poo (x)
+(x)+a a exp (-3ln (x + a)) = T.(x) +a (L(x)+a) = =10)))===0000000000000000=000001 a)
1
(29)
which is integrable in a bounded domain. Recall that we want represent Poe using a potential W with inf v O. In this case, we can start from (x) (B + 1) In (L (x) + a). Since L
clearly holds that V 2 (3 1) In (ax), so we can use the shifted version
L(x)
Vinear (x) (3 1) (In (x) + aa) In (n)) (8 In
+1)
(30)
Example D.4 (Polynomial noise scale). Let a > 0, and A 1. Suppose that o² (x) = (L (x) + a)* Then
VL (x) 0² (x)
1 v (L) +a)
7L (x)
32

---

50
Pos (x)
(x) + a) exp (
--1 (T. (Ix(x + a)) xx)=*})
B
As before, the potential is monotonically increasing with (x), so we can make a shift
L (x) +1 1-1 (a'* -a-= (a)=))
V poly = k In
a
Example D.5 (Exponential noise scale). Let a > 0 and suppose that o² (x) = eab(x) Then
VL (x)
v e (e-a((x)
x² (x)
a
B ( exp
3 -a al (x)
Poe (x) xe all(x) exp
a
Denote 1 (r) = or o ee- then v/l (7) = a + Be 2 0. Therefore, min-20 (T) =10 ())
9 and can take
3 exp (x) = al (aaa(x) + B = al al) B (1-10
=
(31)
D.2 Generalization bounds
Bounded domain with uniform initialization. Assume that training follows a CLD in a bounded domain described in (25) with uniform initialization pa Uniform (On), where Og C O. For simplicity we take 6² = In that case Theorem 2.7 implies the following.
Lemma D.6. Assume that the parameters evolve according to (25) with o² 1 and uniform initialization Po = Uniform (0o), where On C O. Then for any time 2 O, and ō E (0,
w.p. 1 8 over S DN
BE (s(
S + In 01/
In (N/8)
Eaa~pa (En(O.) - Es(O,) |S <
(32)
2N
2. w.p. 1 1 8 over S ~ N and 0, ~
Resssu esssuupp (.((0) + In [ / In (N/8)
(0, (0, S
(33)
2N
Proof. This a direct corollary of Theorem 2.7 with KL (po || v) In [l/|
(2 regularization with Gaussian initialization. Let A Rd be regularization terms, and consider the unconstrained SDE
d0, VL (0:) dt 3-
33-1 diag (A) 0.dt 128-1 (0.)dwe.
(34)
additive regularization of the form 23 O diag (A) 0r, so each parameter can have different regularization coefficient. We shall denote by Φx multivariate Gaussian distribution with mean O and covariance matrix diag (X (X-)), where A- (AT ".T....,A,7 x....,,T)), " For simplicity, we present the results with o² 1.
Notice that - diag (A) 0,dt corresponds
Lemma D.7. Let Ao, Ai > O, and let O, evolve according to (34) with o² = and À = A and start from Gaussian initialization Pu & Then for any time & 0, and E (0,
1. w.p. 1 - 8 over S ~ D
Eg,-m ~m (ED(O.) Es(O.) < BBp (s) S) + KL (O ((x)) + In (N/8)
(35)
2N
33

---

2. wip. 1 - 8 over S ~ D and 0, ~ Pt
Bess po Ls(
(2,) + In (N/0) KL (dxo
ED(O,) Fs((0)) $ v
(36)
2N
where KL (d>o xx.) 1/2 Σ
[In
Aidt Ao,
+
An.1 X1.
Proof. This a direct corollary of Theorem 2.7 with the explicit expression for the KL divergence
between two Gaussians.
Remark D.8 (Dependence on the parameters' dimension). While the bound in Lemma D.7 depends on the dimension of the parameters this can be mitigated in practice. For example, by matching the regularization coefficient and initialization variance, the Kl.-divergence term vanishes and we lose the dependence on dimension. Furthermore, we can control each parameter separately by using parameter specific initialization variances and regularization coefficients. Then, the KL-divergence can have different dependencies, any, on the dimension d.
For = AoT,
A1 = A, Ao, A > 0, this simplifies to KI. (áx,
(xx)
(In Aa
1 + 1/4
34

---

E Linear Regression with CLD
Theorem 2.7 and Corollary 3.1 only bound the gap between the population and training errors, yet this does not necessarily bound the population error itself. One way to do this is by separately bounding the training error and showing that in the regime which the generalization gap small, the training error can be small as well. In Appendix F we show empirically that deep NNs can reach low training error when trained with SGLD the regime in which Corollary 3.1 not vacuous. Here, we look at the particular case of the asymptotic behavior of ridge regression with CLD training with Gaussian i.i.d, data, for which we can analytically study the training and population losses.
Setup. Let 0' E IR x + with ||0'|| = 1 and .V (0, o2) independent of x. We assume that has ii.d. entries with Ex 0 and covariance E xx be the data (design) matrix, y RN the training targets, & E RR the pointwise perturbations, and 0 E Rd the parameters in a linear regression problem. In what follows, we focus on the overdetermined case N > d, where X has full column rank with probability I, the empirical covariance A & x x > 0 a.s. In addition, we denote 0LS A y. and 0 OLS. The training objective is then the minimization of the regularized empirical loss
I. Let X R
Lg (0) - 2B
0 2
|X0 - y1
10
0 T
AŌ + Cs +
1012,
2N
2/3
2B
where Cg Ls (01s) 1 empirical irreducible emror.
lyl1 LLS
2
|lyl
2N
x
(x
X_y, is the
2N
CLD training. Assume that training is performed by CLD with inverse temperature 3 > 0, which, because Lş is quadratic, takes the form
d0,- A (0: -is) dt A-- 0, dt + 2 dw..
(37)
Since A > 0 and A > 0, the Gibbs distribution
(1- 0r.)) T BA (0 0r.s) + +>000)
Poo
0 x exp
the unique stationary distribution, and furthermore, is the asymptotic distribution of (37). We can simplify this to Gaussian. Denote a = A/B and
= (A all) and 0 =EEALL
1 N (A (A+
1
then
(0 (0-0) 0) Σ (0 (0- 0) =30 (A + al) 0 20 Σ 00 ----0
Σ-1(6
=30 (A + al) 0 2,30 T - EEAIs + +330 AΣE EA0
30 (A + al) 0 - 2,30 AOLS + |
Since the last term is constant w.r.t. 0, we deduce that
Poo (0) x exp (0 0) Σ (0 (0-0)
ie. the stationary distribution a Gaussian N (0,E). Σ). We can now calculate the expected training and population losses.
Goal. In the rest of this section, our final aim is to calculate the expected training and population losses in the setup described above, in the case when the data is sampled i.i.d. from standard Gaussian distribution, a is a fixed constant, À oc d (to match standard initialization). 10 N, 8 and are large, but
Since this is linear model d layer width, and as we assume the regularization matches the standard initialization. This initialization is considered in many works as Bayesian prior in various settings [35, 68).
35

---

8 < N, so our generalization bound is small (since Ep, L is a fixed constant in this case). We will find (in Remark E.2 and Remark E.4) that if also d < then the training and expected population loss are not significantly degraded. This is not major constraint, since we need d < N to get good population loss anyway, even without noise (i.e. 8 oo). This shows that in this regime d < B < N, the randomness required by our generalization bound (the KL bounds in Corollary 3.1) does not significantly harm the training loss or the expected population loss.
Claim E.1. With some abuse of notation, denote Ls (0xz) = Ea-y. Ls (0). Then
1 Tr (A + at) +aI) " + rT
2 (A+ + aI)
E LLS (0xc)
X
A0*
2/
2
a²a²
0²
d
Tr aA)) 2)
+
1
2N
2
N
Proof.
From Petersen and Pedersen [56] (equation 318)
Ls (0xc))
E lLS) A (0- 0ss) + Cs
(0- -iis) T A (0- Ois) + Css
Ir (Az) + 2
For the second term, notice that
LLs = (BEA - -1S
(BEA AE -YΣ I)0s.
E3 + al - AΣ -
OLS
=I-1
-1E01s -a (A+
+ al)
01ss
A and E are simultaneously diagonalizable. To see this, let A = QAQ be a spectral decomposition
of A, then A + al = QA + al) QT, so Σ = 8 (A + aI) -1 QTQT. This means that A, E, and their inverses all multiplicatively commute. Therefore,
1
a²
Ls (0x)
Ir (AE) +
O (A al)
A al) OLS + Cs
a²
Tr (AE) + 2N XA al) A(A + al) A y + +Cs
23 Tr (A + al) )
2 y (A aA+ A - + Cs
Conditioned on X, standard results about the residuals in linear regression imply that,
d [ X = x² 1 (1-N) N
In addition, for any symmetric matrix M we have
Eg [y My]
(x)++ M M(X0' + +e] = =(XO") MXX" +E [ [M]]
E. (X0* +E)
=(X0") MX0' + o (M).
In particular,
E
X X + ([A++I)+2 - A X
x A x XO +02Ir (x (A + al) -2 al) ''--'x)
-AATNA(A+oI) A - NAO" + +o (x X(A + al) -2 aI) 'A-I)
=T (A+ A0 - NO²Ti (a)+
36

---

where we used the definition of A, the joint diagonalizability of A and Σ, and the cyclicality of the trace. In total, the expected training loss, conditioned on the data
a² 0"
EeLs (0x)
Tr (A + aa)
+
(A
aa)
23 a²a² 2N II -) + 1
2
2 N
Remark E.2. We intuitively derive the asymptotic behavior of Claim E.1. Let be constant, and let B grow (so shrinks). We can decompose (A + al) al) as
(A + +al
aA 2 + A (A + +
This can be readily verified
A- 1
A 2 + A
A (A + al)
(A a al) a (A aAl +a'l)
= A (A + al)
-1 (A² +a aA - -
A (A + al) A
= (A + aI) -1
where we used the multiplicative commutativity, as before. Notice that since A > 0, A. so (A + aI) x A for any & E N. Denote
R₂ (a) = a²A (A aI)
then |R2 (a)ll2 Am) where Amin (A) is the minimal eigenvalue of A. As the elements of X are i..d. with mean O and variance 1, the limiting distribution of the spectrum of A as
N. + with d/N + y E (0,1) the Marchenko Pastur distribution, which is supported on
(1- - vワ) (1 v In particular, as N, d + 00, Amin (A) 2 (1 (1- VdVV//N) so for > 0,
a²
RR (ai)l2 S (1- Vd/N -
6
with high probability. Therefore, in the following shall treat the remainder as R₂ (a) 0 (a?). even when taking the expectation over X.
Since = 2/3 and A x d, then for d d B, we have a/B = =0 (a²). and we conclude that
3 + 2² (2- + (a²)
[Ls (0xx) X]
Therefore, the added noise does not significantly hurt the training loss when E 0² (1 }) or equivalently, B 2 [N-2joz- In particular, this holds when d < B & N, which is a regime where our generalization bound Corollary 3.1 also becomes small (since 3 & N). This shows that the randomness required by Corollary 3.1 can allow for successful optimization of the training loss.
Moving on the population loss, we define Lp in the usual way
1 Bx.e (xTO, -)) E (x 0, - 100-xop x =s)
Lp (0.)
Due to the independence between and e,
+ 0²
0²
Ln (0) E (0 07))²
0 0"
1
2
2
37

---

Claim E.3. With some abuse of notation, denote LD (0))) = Eampz Lo (0). Then
E (0xz) x
1
Tr (A+ (I)+ +
- 0z A (A + al) 0
1
23
2
o²
o²
+ 2N
Tr A (A (A+) 3) T al) 0 +
10 +
2
Proof. Taking the expectation w.r.t 0 ~ N/ (0, Σ) we get from Petersen and Pedersen [56]
LD (00)) = Ir [ + ト 2
o² 2
0 0"
Tr (IA +1) +
000 0 0 10 o²
23
We can simplify some of the terms when taking the expectation conditioned on X.
Eg
X (A- al) (A
+al) y
N2
1
(XA*
+ E) + x (XI' +e)
N
0"
X X (A aI)
x X0
Be e X (A -
N
N2
d²
A (A (A
+
Tt
x (A
N2
T
A3 0"
Tr
a1
N
In addition,
E2
0
0
0+
E
[X0' + E) X + aal 0+)
N
1
0
X x al) 0" E x (A)+ 0+
= A + -10
Combining these we get the desired result.
Remark E.4. As we have done for the training loss in Remark E.2, we can estimate the expected population loss in some asymptotic regimes. Let be constant, and let 8 grow (so shrinks). As in Remark F.2,
the approximation (A + al) -1 A a O (a²T), which also implies (A + al) -2 A A -3 + + (a²1). and treat the remainders as O (a?) even when taking the expectation w.r.t X. Then,
1
1 8* A2
E [LD (0 X
Tr (A
aA -2 +0(a²I)) +
2aA -3 (a'()))) 0
2
0²
Tr (A A AA- -
2nA +0(()))))
2N
0T
(A -1 -A ²+0(22))) 2 0r - 101
1
o²
1 (1
d²
Ti (A o²
+
2
3
N
Tr (A +0o ~ (A-1+0(al)) 0"
23
aaa
Tr (A (al))
T (A-1 + ( 0*
N
Simplifying, we arrive at
11
d2
a²
02
E [L (0xx x
=
+
Tr A
11
+
Tr (A (0
2
8
N
2
23
N
38

---

Assuming that x are i..d. .N (0, N. A ~ (N,,,, i.e. has Wishart distribution. According Theorem 3.3.16 [24], N d+3 then
N
EA 1
N d 1 I
Tr II]
EA N
(N - d) (N - 1) d 2
(N (N d 33)
N -N-d-1)
I.
-N (N 1) (N 3)
Then, the expectation X and if o here),
N
v (which is true for X x d and < N like assume
1 1/1
N
-N---1)
Nd
ELD (0x))
+
+o²
- + (a²)
2 8
N
Nd
1
N
N-1)
Nd
2 B +
o
N -- +0
Nd
This result is similar the one in Remark E.2 for the expected population loss be significantly Nd
hurt by the added noise, it must hold that 3 2 (N-1)o²- In particular, this holds when d < B < N, which is regime where our generalization bound Corollary 3.1 also becomes small (since 3 < N). This shows that the randomness required by Corollary 3.1 does not harm the expected population loss.
39

---

Numerical Experiments
E.1 Experimental results
The following are results of training with SGLD (a discretized version of the CLD in (10)) few benchmark datasets. Notice we use the regularized version where regularization coefficient is A B-1 and the À hyperparameter is dictated by the initialization from the normal distribution Po . (0, We used a common initialization of N (0, din i... X = dm
We several different values of 3 relative N (the number of training samples). For simplicity, we focused on binary classification cases. In all datasets with more than classes, we constructed a binary classification task by partitioning the original label into disjoint sets of the same size.
The results demonstrate that learning with SGLD possible with various values of [3, In fact, in several instances, the injected noise appears improve the generalization gap, e.g. in SVHN [53], in all the tested 3 values between 0.4 N and 2 N the average test error remained almost the same while the training error decreased increased (i.e. the generalization gap increased). Notably, also observe that for sufficiently large levels of noise, the generalization bounds are non-vacuous.
Table 2: MNIST (binary classification)
Es
ED
ED Es
Bound (11) w.p 0.99
0.01 N
0.1972(+0.0213) 0.2279(+0.0001)
-0,0307
0.06124
0.03
0.1161(+0.0028)
0.1074(+0.0035)
-0.0087
0.10498
0.1 N
0.0618(+00.01)
0.062(+0.0041)
0,0002
0.19096
0.15 N
0.0497(100.0014
0.0494(+10.001)
-0.0003
0,23376
0.4 N
0.0281
0.0358(100.009)
0,0077
0.38147
0.7
0.0202( 10.0000)
0.0284(1000004)
0.0082
0.50456
N
0.0162( L0.0006)
0.0278(10.0023
0.01166
0.60302
2- N
0.0092 (.0092(+000004)
0.0262(+0.0016)
0.017
0,85273
0.0001(=0)
0.0229(+0.0004)
0.0228
> 1
Table 3: fashionMNIST (binary classification)
Es
ED
Ep Fig
Bound (11) 0.99
0.01 N
0.1215(10.002) (0027777
0. 0.1251(10.0085 0087)
0.0036
0,06833
0.03 N
0.0999(10.001)
0.106)
0,0088
0.11738
0.1 N 0.0.21(+0.0012)
0.000(+00001)
0.0039
0.21368
0.15
0.0765(+000009)
0.0803(++0.015)
0.0038
0.26159
0.4 N 0.0635(+00.005)
0.0722(+0.002)
0.0087
0,42695
0.7 N
0.0.67(10.0006)
0.0691(10.0019)
0.0124
0,56473
N
0.0525(10.00055 0.0672(10.002)
0.0675(40.0013)
0.015
0.67495
0.013(+0.0007)
0.0242
0.95446
DO
0.0248(40.001)
0.0675(+0.0033
0.0427
> 1
Table 4: SVHN (binary classification)
Es
Ep
Ep
Es
Bound (11) w.p 0.99
0.01
0.0746(+0.0012)
0.1033(++0.032)
0.0287
0.05898
0.03
0.0.41(10.0004)
(.067(10.0026)
0.0229
0.10203
0.1
1.0282(10.0008
0.0176(10.007)
0.0194
0.1862
-
N
0.0251(40.0005
0.0145(10.002)
0.0194
0.22803
0.4-A
0.0182(+0.000)
0.0074(+0.0001)
0.0192
0.37235
0.7
0.0146(+0.000)) 0004)
0.0363(+0.002)
0.0217
0,49256
N
0.0124(+0.0002
0.0342((000004)
0.0218
0,58872
2- N
0.0085(+0)
(.0371(+0.001)
0.0286
0.83256
40

---

Error, beta=0.2N
Error, beta=0.4N
bound for beta=0.4N
Error. beta-0.7N
bound for beta-0.7N
Error, beta=1.5N
bound beta=1.5N
Error, beta=12N
Error, beta=N"2
Error, beta=N"3
Error, b
Error, beta-N"5
0.6
0.5
0.5
03-
0.4
Train Error
Test
0.1
0.9
0.0
-0.1
-0.
10000
20000
30000
40000
50000
20000
40000
50000
Figure 1: Parity Results. Left: Training error. Right: test error and generalization bound.
F.2
Training details
MNIST and fashionMNIST. We trained fully connected network with 4 hidden layers of sizes [256, 256, 256, 128] and ReLU activation, Ir 0.01, for 60 epochs.
SVHN. The network was trained with convolutional neural network with 5 convolutional layers, 0.01, for 80 epochs. The complete architecture:
Two convolutional layers (3x3 kernel, padding 1) with 32 channels, followed by ReLU activations and 2x2 max pooling.
Two convolutional layers (3x3 kernel, padding 1) with 64 channels, followed by ReLU activations and a 2x2 max pooling.
A 3x3 convolution with 128 channels, ReLU, and 2x2 max pooling.
2 A linear layer 2048 - 512, followed by ReLU and another 512 - 1 linear layer
Parity. In this experiment, we consider a synthetic binary classification task where each input is binary vector of length 70 and the target label is defined the parity of randomly selected input dimensions. We train neural network using SGLD with varying values of the inverse temperature parameter 3 and different sample sizes.
The network was trained with fully connected network with 4 hidden layers of sizes [512, 1028, 2064, 512] and ReLU activation, Ir 0.05, for 100 epochs.
The results show that injecting noise can improve the generalization gap: specifically, the case of B > 2 leads to overfitting, while smaller values of 3 (e.g., 1.5 N to 12 N) yield better generalization. Moreover, as well as the benchmark datasets, this setting, our generalization bound is non-vacuous in several cases.
41

---

F.3 Comparison with the bound of Mou et al. [49]
The bound proposed by Mou al. [49] has demonstrated non-vacuous results. To further assess the effectiveness of our bound and evaluate its relative tightness, we conducted series of numerical experiments on the MNIST binary classification task (see Tables 5-8).
worth emphasizing that our bound offers a distinct advantage: can be evaluated directly at initialization, whereas the bound of Mou al. [49] depends gradients and therefore cannot be computed before training. When testing their bound we used the continuous version, i.e.
{" 2n 0
e C [[) dt log(1/5) + log log M
Ep, (p) Es( S
For simplicity, we omitted the term involving M (which makes the bound more favorable). In addition, we set 8 0.5 since the zero-one loss (denoted here by f(w), unlike [49]) is bounded within the interval [0, 1]. observed that the relative tightness of the two bounds varies across different values of 3 and at different points in time. Consequently, in some instances, the bound of Mou et al. [49] tighter, while others our bound performs better, and we could not draw any further conclusions.
Table 5: 20 training epochs
3
Train Error
Test Error Generalization Gap
Mou et al. [49]
Our bound
0.03NN 1800
0.1224
0.137
0.0146
0.0539
0.1144
0.15N 9000
0.0515
0.0747
0.0232
0.1279
0.2548
0.4N
24000
0.0335
0.058
0.0245
0.2845
0.4157
0.7N
42000
0.0278
0.0498
0.0220
0.4930
0.5499
60000
0.0249
0.0428
0.0179
0.7032
0.6572
120000 2N
0.0209
0.0356
0.0147
1.4044
0.9294
Table 6: 50 training epochs
3
Train Error
Test Error Generalization Gap
Mou et al. [49]
Our bound
0.03N = 1800
0.1156
0.1697
0.05-11
0.0637
0.1144
0.15N 9000
0.0491
0.0615
0.0124
0.1324
0.25-18
0.4N 24000
0.0295
0.0348
0.0053
0.2992
0.4157
0.7.V
42000
0,0217
0.0283
0.0066
0,4903
0.5499
60000
0.0173
0.0277
0.0104
0.6827
0.6572
2N
120000
0.0108
0.0265
0.0157
1.3153
0.9294
Table 7: 250 training epochs
3
Train Error
Test Error Generalization Gap
Mou et al. [49]
Our bound
0.03N = 1800
0.122
0.1049
-0.011
0.1273
0.1144
0.15N 9000
0.0502
0.0476
-0.0026
0.1503
0.25-18
0.4N 24000
0.0284
0.0296
0.0011
0.2853
0.4157
0.7.V 42000
0,0178
0.0247
0.0069
0,4595
0.5499
.V 60000
0.0127
0.0240
0.0113
0.6478
0.6572
2N = 120000
0.0050
0.0234
0.0184
1.2158
0.9294
42

---

Table 8: 400 training epochs
3
Train Error
Test Error
Generalization Cap
Mou et al. [49]
Our bound
0.03N = 1800
0.1224
0.1105
-0.0119
0.1900
0.1144
0.15N = 9000
0.0499
0.0556
0.0057
0.1774
0.2548
0,4N 24000
0.0261
0.0357
0,0096
0,3005
0,4157
0.7.N 42000
0.0161
0.0271
0.0110
0.4548
0,5499
60000
0.0112
0.0255
0.0143
0.6247
0,6572
2N = 120000
0.0038
0.0249
0.0211
1.1455
0.9294
G Mild Overparametrization Prevents Uniform Convergence
In this section, we consider fully-connected ReLU networks, where the weights are bounded, such that for each layer j the absolute values of all weights are bounded by Vd; where dy-1 is the width of layer -1. Moreover, we assume that the input x is such that each coordinate x; is bounded in [-1, We show that m training examples do not suffice for learning constant depth networks with (m) parameters. Thus, even mild overparameterization prevents uniform convergence in our setting.
Our result follows by bounding the fat-shattering dimension, defined as follows:
Definition G.1. Let be class of real-valued functions from an input domain X. We say that FF shatters points { S X with margin 0 if there ? R such that for all y1...., Vm E {0, there exists f E F such that
E [m], f(x,) S rg if = 0 and f(x)) te if yi 11
The fat-shattering dimension of F with margin is the maximum cardinality mn of a set of points in X' for which the above holds.
The fat-shattering dimension of F with margin lower bounds the number of samples needed to learn F within accuracy in the distribution-fres setting (see, e.g., [2, Part III)). Hence, to lower bound the sample complexity by some m it suffices to show that we can shatter a set of m points with a constant margin.
Theorem G.2. We can shatter points m where ||x:||ac 1, with margin using ReLU
networks of constant depth and (m)) parameters, such that for each layer j the absolute values of all weights are bounded by
where dj-1 is the width of layer j -1.
Vd;-1'
Proof. Consider input dimension do = For 1 m, consider the points I; - and
m
let {v: 1m C {0, 1). Consider the following one-hidden-layer ReLU network N, which satisfies N(x,) = Mt for all First, the network N includes a neuron with weight 0 and bias 21 i.e. [0 mi Now, for each i such that y, = 0 and //+1 = 1 we add two neurons: [I: y/l+ - -Ix b--1++. and for such that = and y = O we add - [r: yi]+ + [x 1i+1]+- It is easy to verify that this construction has width at most 2m
and allows to shatter points with margin 2m However, the output weights of the neurons are 1,, and thus it does not satisfy the theorem's requirement. Consider the network N'(x) = N(x) fーーーT obtained from N by modifying the output weights. The network N' satisfies the theorem's 's requirement on the weight magnitudes, and allows for shattering with margin 2m We will now show how to increase this margin to 1 using constant number of additional layers.
1.
Let Ñ be network obtained from N' as follows. First, we add a ReLU activation to the output neuron of N'. Since for every z; we have (2x) 2 0, does not affect these outputs. Next, we add L = 8 additional layers (layers 3.... + L - 1) of width /m and without bias terms, where the incoming weights to layer are all and the weights in layers ,,...,3 + 11/4- Finally, we add an output neuron (layer 3 + L.) with incoming weights m,74 The network N satisfies the theorem's 's requirements on the weight magnitudes, and it has depth + 11 and (mm) parameters. Now, suppose that all neurons in layer < < + L I have values (i.e., activations) 2 0, then the values of all neurons in layer j + are mi/4 Vm 1/4
are
43

---

Hence, if the value of the neuron in layer 2 is 1 then the output of the network is
2mz/2m-1'
2m 2m (m11/)4 2m 2mn 200 22m-T for large enough m. If the value of the neuron
L/4
in layer then the output of N is also Hence, this construction allow for shattering m points with margin at least 1, using (m) parameters and weights that satisfy the theorem's 's conditions. L
44

---

H Background on Stochastic Differential Equations with Reflection
We supply an introduction to the theory of stochastic differential equations with reflection (SDERs), then proceed to characterize the stationary distribution of a family of SDERs in a box. The background of standard (non-reflective) SDEs is similar and more common, and is therefore included here. See for example [54] for more.
H.1 SDEs with reflection
One of the main analytical tools of this work is the characterization of stationary distributions of SDER in bounded domains (see 57, 63, for an introduction).
The purpose of this section is to present more rigorously the setting of the paper, and supply the relevant definitions and results required to arrive at Lemma D.1. As Lemma D.1 is considered a well-known result, this section is mainly intended for completeness. Specifically, in the following we present some relevant definitions and results by Kang and Ramanan [31, 321, and specifically, ones that relate solutions to SDERs (Definition 2.4 in [32]), to solutions to sub-martingale problems (Definition 2.9 in [32]), and that characterize the stationary distributions of such solutions. For simplicity, we sometimes do not state the results in full generality.
Setting. Let d be a domain (non-empty, connected, and open). Let the drift term b R Rd and dispersion coefficient Σ Rdd - Rdxd be measurable and locally bounded. We also denote the diffusion coefficient by A (+) E (.) E E (ay ()) and denote its columns by a, (-). We say that the diffusion coefficient is uniformly elliptic if there exists o > 0 such that
Vv e e v ('A(x)v> |v]l
(38)
Let ry be set valued mapping of allowed reflection directions defined on 92 such that r (x) {0} for S2, and (x) is non-empty, closed and convex cone in Rd such that {0} S (x) for x E 8n and furthermore assume that the set { {(x, v) E an let ñ (x) be the set of inwards normals to Q2 at
02 v E n (x)) is closed in Rdd In addition, for
ñ (x)
ú, (x)
Pr (x) = I
IRd
|||||| = 1, B, (x - rn) no = 0}
Then, denote the set boundary points with inward pointing cones
u e fx an En â (x) Vn E E (x) (n, n) > 0}
and let V A 0Q \, U. For example, if Ω is convex polyhedron and 17 (x) is the cone defined by the positive span of (x) we get that = 0.
Throughout this section and the rest of the paper, the stochastic differential equation with reflection (SDER) in (7)
dx; = b bx,) dt + Σ (x;) + dr,,
(39)
where w, a Wiener process, and r, is a reflection process with respect to some filtration, is understood as in Definition 2.4 of [32], and the submartingale problem associated with (2, 1)) V. b and Σ, refers to Definition 2.9 of [32]. In addition, we use the following definition.
Definition H.1 (Piecewise C with continuous reflection; Definition 2.11 in [32]). The pair (22, is said to be piecewise C² with continuous reflection it satisfies the following properties:
1. Ω is a non-empty domain in Rd with representation
Ω
0 Ω iez
where I is a finite set and for each i E I, Ω is a non-empty domain with C² boundary in the sense that for each x E a2, there exist neighborhood A (x) of x, and functions
p E C² (R.), i I (x) {i eieT I x E an }, such that
N (x) = (x (x) > 0} A (x) = EREN(x (x) = 0}
45

---

and Vip + 0 on (x). For each x E aΩ' and i E I (x), let
V
n' (x)
denote the unit inward normal vector to 02' at x.
2. The (set-valued) direction "vector field" 77 12 - IR is given by
[0]
x E S2
7 (x) = {{ EiE amn (x) a; 20, i
(40)
x E an,
where for each i I, 77' (-) is continuous unit vector field defined on 00 that satisfies for all x E 02"
(n' (x), .7 (x)) > 0.
If rf (-) is constant for every i E I, the the pair (2t, n) is said to be piecewise C² with constant reflection. If, in addition, n' (-) is constant for every E I, then the pair (9, 77) is said to be polyhedral with piecewise constant reflection.
In addition, let S denote the smooth parts of @n.
Remark H.2. It is clear from the definition that if Ω is polyhedral, i.e. if all Ωt's are half- and " consists of inward normal reflections, then (S2, 1j) is polyhedral with piecewise constant reflection.
Theorem H.3 (Theorem in [31], simplified). Suppose that the pair (S2,1) n)) is piecewise C² with continuous reflection, for all and x E an', (n' (x) , (x))
V = 0, b-) C² (S) and A E C2 (1) (elementwise), and the submartingale problem associated with (S2, 17) and is well posed. Furthermore, suppose there exists nonnegative function & C² (52) with Zp = Ja (x) dx < co that solves the PDE defined by the following three relations:
1. For x E Q2:
0²
d
0
(ai (x)
Σ
(b, (x))
(41)
dx,dx,
Oz.
T,j=1
2. For each E I and x E anns
0 2p (x) (n' (x), (x)) n' (x) A A (x()) V (x(x) p (xx) K; (x),
(42)
where
qp (x) nx) T (x)) - A (x) n' (x)
and
d
Jaki (x) Ox,
K4 (x) & (x), V A(x)) Σ Σ
n² (xx)
k=1
j=1
3. For each i,j E I, i j. and E 09' n 1 n nan,
(x) ((q (x) n' (x)) + (q¹ (x) n' (x))) = 0.
(43)
Then the probability measure Ω defined by
Z, [ dxx) A A
1
Poo (A)
(44)
A
is stationary distribution for the well- well-posed submartingale problem.
46

---

We are now ready to state characterization of stationary distributions of (39). Note that for simplicity. we do not maintain full generality.
Corollary H.4 (Stationary distribution of weak solutions SDERs). Suppose that, P is convex and bounded, b C' (I) and A C² (9), (2,, is piecewise C² with continuous reflection, A is uniformly elliptic (see (38)), and V = V.. Then p C² satisfying the conditions in Theorem H.3 defines a stationary distribution for (39).
Proof. Assumptions compactness of the domain, and continuous differentiabiliiy of the drift and dispersion coefficient imply that they are Lipschitz, hence Exercise 2.5.1 and Theorem 2.5.4 of [57] imply that there exists unique strong solution to the SDER (39). Then, piecewise C2 with continuous reflection, the uniform ellipticity assumption, Theorems and of [32], and Theorem H.3 imply that if there exists p E C2 satisfying (41)-(43), then (44) a stationary distributions of (39).
In the next subsection we use this to derive explicit expressions for the stationary distribution in the setting of this paper.
H.2 SDER with isotropic diffusion in box
We proceed to assume that the diffusion term is a scalar matrix of the form A (x) = -2o² (x) Ia. and that f is a bounded box in Rd. i.e. there exist {m; < M,) such that
Ω II im M,)
(2 (
(45)
where
D - [x Rdd
xy > m Srr & {x E Rd
x; < <M..
(46)
and that the reflecting field is normal to the boundary, i.e. given by (40) with
n n'n e and n'as = n'y = -c
(47)
for i = 1..... d. In this setting, we can considerably simplify the conditions in Theorem H.3, as done in the following corollary.
Lemma H.5 (Stationarity condition for SDER in a box with normal reflection). Ler b (-) E C², and let o (-) E C be uniformly bounded away from O, i.e. there exists 0² > O such that for all x e Z
o² xx) > o². If there exists p E C² such that
-= v (V (o2 (x)) - (x)) (0 0= (v (a² (x)) - (x)) (x))
x E Ω
(48)
x E 0n,
and (x) dx 1, then p is a stationary distribution of
dx, = b (xx) dt + 200 (xx)dw; + dr:
(49)
in Z.
Remark H.6. (48) is exactly the stationarity condition derived from the Fokker-Plance equation with Neumann boundary conditions ensuring conservation of mass.
Proof. Under the assumptions we see that the conditions of Corollary H.4 are satisfied, and we can use (41)-(43) to find stationary distributions of (49). First, notice that (41) simplifies to
Σ à
0 -
(aij (x))
(b. (x))
2 1.j
dz,0x,
dr,
i=l
d
a
120" (x)
Σ
(b, (x) (x))
2 1=1
Oz?
dz,
1=1
V
(V (x) - bx)))((x))
47

---

Next, we can considerably simplify the boundary conditions. First, notice that S consists of the interior of the domain's 's faces so for atns. the set of active boundary regions I (x) is singleton I (x) {(i, s)}, J. for some i 1...., d and 8 E {m, M). We focus on the lower boundaries (m), as the conditions for the upper boundaries are symmetric.
For i = L..... d and x E ann S, Tm (x) = n'm (x) = e, so
Im (x) n'n (x) A (x) n'n (x) n' (x) A (x) m'n (x)
= 0² (x) (e: L,e;) e; 0² (x) Lae;
0,
so (43) is satisfied. In addition,
k (x) = V a (x) i 0² (x)
Or.
so (42) becomes, for all i = ,,...,d, d,
0 = -xp(x) (n (x), b (x)) + nm (x)
(x) Vp (x) - v (x (x)) + + (x) (x)
0 0² (x)
0 = -2 b, (x) + a Vp (x) + (x))
dz:
0 0² (x)
0 = (x) (x) +
(x)
(x) + p (x)
dz.
dz.
which is
1 a
0 -x(x) (x)
(x
2 8x.
(V (x)) - bxx))())))
H.2.1 Reflected Langevin dynamics in a box
In this section, we derive some useful properties of the SDER
dx, - (xx) + o2 (xt Jo),,, + dre,
(50)
in a box domain as defined in (45)-(47), where I, 2 0 is some (loss/potential) function, and , > 0 is an inverse temperature parameter. First, we characterize the stationary distribution of this process.
Recall Lemma D.1. If E C2, 2 (+) O uniformly bounded away from 0 in P2
V L a²
2 =
exp
-9
dx
< <0,,
the integrals exist, and the field TL/o² is conservative (curl-free), then
Poo (x) = 0² (x) exp (-8
V (x) dx
(51)
a² (x)
is stationary distribution of (50).
Proof. The drift term in this setting is b = L. Therefore, from Lemma H.5, we get that any distribution that satisfies
0
(x) Poo (x)) + 8p (x) (x)
on Ωt is stationary distribution. We can solve this PDE
0 = (x)
Vo (x)
(x) Voc (x)
Poo (x)
(xV Vo (x)) (x) Vecc (x)
48

---

0² (x) Vpc (x) = Poo (x) (BVL L (x) + Vo2
Vpcc
3VI. + Vo²
Pro
BVL
V Vlnpoo
Vlno
0²
LVL
Vln (Poo 0²)
Then,
In (Poo .0)= f
VL
o² +C
where we used the assumption that the integral on the RHS exists, and is well defined. Hence
(-3
V (x) (x)
Poo (x)
r² (x exp
dx
When the integral in (51) is solvable, we can find an explicit expression for the stationary distribution, as was done in Appendix D.I.
49


Reviews:
[{"review_id": "flyEMPa934", "reviewer": "Reviewer_6xrj", "summary": "This paper derives the generalization gap results for two common cases, which both have important practical implications.\n1.This paper first derives the generalization bound for Markov process with a Gibbs stationary distribution, regardless of the trajectory of the process.\n2.This paper further focus on the special case of the continuous-time Langevin Dynamics (CLD). The generalization bound is agnostic of dimension, number of iterations, or the trained weights, making the bounds more practical compared to previous ones.", "questions": "1. Bayesian Interpretation of Regularization: Regarding the loss in line 632, can the dimension-dependent regularization term ( $\\lambda \\propto d$ ) be interpreted from a Bayesian perspective? Does it correspond to a specific prior distribution, which might justify this unconventional choice?\n2. Negative Generalization Gap: In Table 2, the generalization gap, $E_D-E_S$, is reported to be negative in some instances. Could the authors provide an explanation for this observation? Is it due to stochasticity in the evaluation on a finite test set, or does it point to another phenomenon?\n3. Impact of $N$ and $\\beta$ Scaling: How do changes in the sample size $N$ affect the results presented in Tables 2-4? Furthermore, how do $N$ and $\\beta$ jointly influence the generalization gap $E_D-E_S$ ? To better investigate the impact of $\\beta$ scaling, we suggest that the authors consider evaluating a more systematic range of values, for example, $\\beta \\in$ $\\{0.01 N, 0.1 N, N, 10 N, 100 N, 1000 N, \\infty\\}$.\n\nIf the authors can explain this paper clearly in plain math without introducing advanced math jargons, anonymous link to pdf can be provided (if this is acceptable by the conference regulations). This modifications could also help this paper to have larger impacts if accepted.", "limitations": "See weakness.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThis paper provides a novel perspective on the generalization bound. The optimization process of DNNs can be modeled as a Markov process. Previous PAC-Bayes bound usually does not involve the stochastic modeling of the Markov process. Besides, the bounds is neat and the overall proof logic is clear.\n\nWeakness:\nThis paper uses a lot of mathematical jargons which may not necessary and hinders the readers to quickly comprehend it. Additionally, some mathematical notations have not been explained clearly before using it. If the theorem can be explained in more plain math no more than the undergrad level, this paper will be more suitable for publications.\n1.The unexplained usage of esssup and essinf. Though the introduction of these concepts make the paper more rigorous, it can pose challenges for readers who do not have the background on the measure theory.\n2.Is the concept of Gibbs with regard to x is necessary in the paper. Indeed, Gibbs distribution can be defined clearly by the PDF. This creates extra burdens for understanding Theorem 2.7\n3.From corollary 3.1, the bound is still relied on the weights theta, which is different from the claim.\n\nApart from these, with regard to the contents of the paper:\n1. Stationary Distribution Assumption: The theory's core relies on the existence of a stationary distribution of the Gibbs form, $p_{\\infty} \\propto e^{-\\beta L_S}$. While this holds for CLD on a bounded domain or with specific regularizers, the existence and form of an asymptotic distribution for practical optimizers like SGD remain unresolved open problems.\n2. Inverse Temperature Scaling: To be non-vacuous, most theoretical work requires the inverse temperature to scale as $\\beta=O(N)$. This implies that for a large sample size $N$, the injected noise variance $\\beta^{-1}$ (from Eq. 10) becomes vanishingly small, potentially rendering it inconsequential to the training dynamics. Conversely, for small $N$, the strong noise required to maintain a non-vacuous bound may severely impair model training and performance.\n3. Unconventional Regularization: In the linear regression case study (Appendix E), the authors employ a regularization coefficient $\\lambda \\propto d$ that scales with the parameter dimension $d$. This deviates from standard machine learning practice, where $\\lambda$ is typically a hyperparameter determined via cross-validation. Consequently, the conclusion that \"random noise is harmless\" derived under this assumption has questionable universality and practical relevance.\n4. Loss Function Smoothness: The theoretical derivations, particularly concerning the stationary distribution in Appendices D and H , explicitly require the loss function $L$ to be twice continuously differentiable ( $C^2$ ). However, all experiments were conducted using ReLU activation functions, which result in a loss landscape that is not everywhere differentiable, let alone $C^2$.\n5. Bounded Parameter Space: Lemma D. 6 assumes that model parameters are confined to a bounded domain $\\Theta$. While this is a standard requirement in many PAC-Bayes and SDE convergence analyses, the experimental description in Appendix F. 2 provides no details on weight initialization or mechanisms (e.g., parameter clipping or projection) that ensure the weights remain within such a bounded set. For non-convex loss functions, unconstrained SGLD offers no guarantee against parameter divergence.\n6. Gap Between Theory and Experiments: The provided experiments are overly simplistic and do not adequately bridge the significant gap between the theoretical framework and its practical application.", "was_revised": true, "final_justification": "The authors have addressed my comments. Therefore, I decided to increase the score.", "rebuttal": "**We thank the reviewer for acknowledging the novelty and neatness of our results, and for the constructive feedback.** We understand the main suggestion of the reviewer is to reduce mathematical jargon, especially related to measure theory (which some undergrads do not study), to make the paper more widely accessible. We agree, and will incorporate the reviewer suggestions into the paper (e.g., add definitions of essup and essinf and exemplify Gibbs in the case it has a PDF). Below we address the additional comments (we will clarify all these in the revised version).\n\n**Weaknesses:**\n\n1. **Stationary Distribution Assumption: The theory's core relies on the existence of a stationary distribution of the Gibbs form, $p_{\\infty} \\propto e^{-\\beta L_S}$. While this holds for CLD on a bounded domain or with specific regularizers, the existence and form of an asymptotic distribution for practical optimizers like SGD remain unresolved open problems.**\n\n    The exact forms of the stationary distributions do tend to be either very complicated or without an elementary expression (see e.g. [A]). That being said, 1) as shown in [B] the distribution of realistic algorithms can in some cases be approximated by known ones, such as the Gibbs posterior studied in Section 3, and 2) we do not need to derive the full stationary distribution, but only need to evaluate the expected potential at initialization. This may be significantly simpler in some cases. .\n\n    [A] Azizian, Waïss, et al. \"What is the long-run distribution of stochastic gradient descent? A large deviations analysis.\" arXiv preprint arXiv:2406.09241 (2024).\n\n    [B] Raginsky, Maxim, Alexander Rakhlin, and Matus Telgarsky. \"Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.\" Conference on Learning Theory. PMLR, 2017.\n\n2. **Inverse Temperature Scaling: To be non-vacuous, most theoretical work requires the inverse temperature to scale as $\\beta = O(N)$. This implies that for a large sample size $N$, the injected noise variance $\\beta^{-1}$ (from Eq. 10) becomes vanishingly small, potentially rendering it inconsequential to the training dynamics. Conversely, for small $N$, the strong noise required to maintain a non-vacuous bound may severely impair model training and performance.**\n\n    Note that $\\beta = O(N)$ means that $\\beta$ must be at most of order $N$, thus making the use of small $\\beta$ possible, even for large $N$. Also, we think it is a strength (not a weakness) of our generalization guarantee that it also applies when the noise is too small to affect the training dynamics (i.e., so it effectively applies to gradient flow).  Otherwise, this claim is correct — when the training set is small we require more noise to achieve the same generalization guarantee.\n\n3. **Unconventional Regularization: In the linear regression case study (Appendix E), the authors employ a regularization coefficient $\\lambda \\propto d$ that scales with the parameter dimension $d$. This deviates from standard machine learning practice, where $\\lambda$ is typically a hyperparameter determined via cross-validation. Consequently, the conclusion that \"random noise is harmless\" derived under this assumption has questionable universality and practical relevance.**\n\n    First, just to make sure we are on the same page, please note the actual regularization (i.e. the weight decay factor in eq. 10) is not $\\lambda$, but $\\lambda/\\beta$ (i.e. approximately $\\lambda/N$), and in a neural network, $\\lambda \\propto \\text{layer width}$, not $d$. Second, as we wrote in the paper, we found empirically this regularization was rather small, and did not have a significant impact on performance. Third, one can always increase the regularisation by modifying the loss $L_S \\leftarrow L_S + c ||w||^2$ in equation 10. Under standard initializations, this changes the loss in the bound by $O(c \\cdot D)$ factor, where D is the depth of the neural network and so $cD$ is small, for common values of $c$ and $D$. Therefore, combining these observations, we do not see this as a significant practical issue. \n\n4. **Loss Function Smoothness: The theoretical derivations, particularly concerning the stationary distribution in Appendices D and H, explicitly require the loss function to be twice continuously differentiable ($C^2$). However, all experiments were conducted using ReLU activation functions, which result in a loss landscape that is not everywhere differentiable, let alone $C^2$.**\n\n    Notice there is no issue here: we do not have any continuity/smoothness terms in the results, implying that we can use any $C^2$ approximation to non-$C^2$ functions, e.g. a $C^2$ approximation of ReLU that is identical to ReLU after being quantized to be represented in a computer.\n\n5. **Bounded Parameter Space: Lemma D. 6 assumes that model parameters are confined to a bounded domain $\\Theta$. While this is a standard requirement in many PAC-Bayes and SDE convergence analyses, the experimental description in Appendix F. 2 provides no details on weight initialization or mechanisms (e.g., parameter clipping or projection) that ensure the weights remain within such a bounded set. For non-convex loss functions, unconstrained SGLD offers no guarantee against parameter divergence.**\n\n    See Lemma D.7 that derives the analogous result for unbounded parameters with $\\ell^2$ regularization. The experiments in Appendix F were conducted with this form of regularization, instead of the bounded domain assumption.\n\n6. **Gap Between Theory and Experiments: The provided experiments are overly simplistic and do not adequately bridge the significant gap between the theoretical framework and its practical application.**\n\n    Indeed, our focus in this work was theoretical, to significantly improve previous bounds. We found it remarkable that we were already able to get non-vacous bound without any trajectory-dependent information (as did previous non-vacous bounds), but, as we wrote (in lines 236-237), our bounds still require tightening before they can be practically useful, and we plan to do so in future work. \n\n\n**Questions:**\n\n\n1. **Bayesian Interpretation of Regularization: Regarding the loss in line 632, can the dimension-dependent regularization term ($\\lambda \\propto d$) be interpreted from a Bayesian perspective? Does it correspond to a specific prior distribution, which might justify this unconventional choice?**\n\n    The form of regularization is chosen to match the standard initialization (Gaussian, with a variance of 1/(layer width)). The initialization is considered in many works as a Bayesian prior in various settings (e.g., [C,D]).\n\n    [C]  Lee, Jaehoon et al., Deep Neural Networks as Gaussian Processes, 2025.\n\n    [D] Wenger, Jonathan et al., Variational Deep Learning via Implicit Regularization, 2025.\n\n2. **Negative Generalization Gap: In Table 2, the generalization gap, $E_{D} - E_{S}$, is reported to be negative in some instances. Could the authors provide an explanation for this observation? Is it due to stochasticity in the evaluation on a finite test set, or does it point to another phenomenon?**\n\n    These negative values are not statistically significant, as the standard deviation of the difference of means of $E_S$ and $E_D$, is too large (see the corresponding columns, in parentheses). \n\n3. **Impact of $N$ and $\\beta$ Scaling: How do changes in the sample size $N$ affect the results presented in Tables 2-4? Furthermore, how do $N$ and $\\beta$ jointly influence the generalization gap $E_D - E_S$? To better investigate the impact of $\\beta$ scaling, we suggest that the authors consider evaluating a more systematic range of values, for example, $\\beta \\in 0.01N, 0.1N, N, 10N, 100N, 1000N, \\infty$.**\n\n    We used the entire training set here. Using smaller $N$ globally improves $E_S$ and degrades $E_D$, $E_{D} - E_{S}$ and the bound. Regarding the $\\beta$ values in Tables 2-4, as suggested we added $0.01 N$ and $0.1 N$ to the Tables and they follow the same trends of the other values; note that $N$ and $\\infty$ are already included in the tables, while the other values are not significantly different from infinity. \n\n4. **If the authors can explain this paper clearly in plain math without introducing advanced math jargons, an anonymous link to pdf can be provided (if this is acceptable by the conference regulations). This modifications could also help this paper to have larger impacts if accepted.**\n\n    Unfortunately, no links are allowed. However, the bound on KL (which is used in in-expectation PAC bayes) is easy to derive, e.g. in the case that $p_0=\\nu$, which we assume for CLD:\n\n    $$ \n    \\mathrm{KL}\\left(p_{t}||p_{0}\\right) =\\int p_{t}\\log\\frac{p_{t}}{p_{0}} =\\int p_{t}\\log\\frac{p_{t}}{p_{\\infty}}+\\int p_{t}\\log\\frac{p_{\\infty}}{p_{0}} \\leq\\int p_{0}\\log\\frac{p_{0}}{p_{\\infty}}+\\int p_{t}\\log\\frac{p_{\\infty}}{p_{0}} =\\int p_{0}\\log e^{\\Psi}+\\int p_{t}\\log e^{-\\Psi} =E_{p_{0}}\\Psi-E_{p_{t}}\\Psi \\leq E_{p_{0}}\\Psi\n    $$\n\n    where in the first inequality we used the second law, and in the next we used our assumption that $p_{\\infty}=p_0 e^{-\\Psi}/Z$ (there is the main trick, that the troublesome normalization constant $Z$ cancels). We hope this helps to clarify the result. Note that we assume the relevant PDFs exist, and omitted some of the integrals’ notation for brevity."}, {"review_id": "6mt2eOeaMA", "reviewer": "Reviewer_8GSk", "summary": "The paper gives a bound on the generalization gap when training with a Markovian stochastic algorithm that holds at any time during training, with no dependence on mixing time, dimensionality, or gradient norms. The authors start by giving a bound for any data-dependent Markov-process whose statinoary distribution is Gibbs and then specializes to continuous-time Langevin dynamics. The temperature $1/\\beta$ and the initial expected loss turn out to be \"all you need\" to get a high-probability bound on the generalization gap. The authors also carefully discuss implications of the bound in the context of common neural net training practices.", "questions": "- In Thm 2.7, can the $\\textrm{ess sup}_{h \\sim p_0} \\Psi_S(h)$ term hide dependence on dimensionality when the loss scales with width?\n- The paper doesn't seem to discuss gradient-norm clipping, a common training practice. Could the authors discuss possible extensions to state-dependent drift?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths\n- Thm 2.7 is significant and general; the PAC-Bayes recipe works for any data-dependent Markov process as long as the stationary distribution is Gibbs type.\n- The results are original. In particular, it's nice that it does not require gradient norms, unlike the trajectory-dependent results of Mou et al. and Futami and Fujisawa et al.\n- The paper is very well written and the proof idea is easy to follow. The authors motivate upfront that the everything follows from the generalized second law of thermodynamics monotonicity, so Corollary 2.5 and Thm 2.7 are easier to follow. \n- The \"Interpreting Corollary 3.1\" subsection is helpful for anchoring the theoretical results within typical NN training practices. It is very clarifying that the required $\\beta = O(N)$ is desirable in Bayesian settings as well as SGD. \n\n### Weaknesses\n- If I understand Appendix D.2 correctly, it seems that the initialization $p_0$ needs to match the shape of the loss (the regularizer or the box constraint), otherwise a KL cost depending on dimensionality will be incurred.\n- The bound loses meaning if a task has unbounded or heavy-tailed losses that don't take finite expected or ess sup loss at initialization.\n- Please see \"Questions\" below.", "was_revised": true, "final_justification": "I maintain my acceptance score.", "rebuttal": "**We thank the reviewer for acknowledging the significance, originality, and clarity of our work, and for the useful feedback. Below we address the reviewer’s comments; all typos will be corrected.**\n\n**Weaknesses:**\n\n1. **If I understand Appendix D.2 correctly, it seems that the initialization $p_0$ needs to match the shape of the loss (the regularizer or the box constraint), otherwise a KL cost depending on dimensionality will be incurred.**\n\n    Correct — the bound in Theorem 2.7 depends on $KL(p_0 || \\nu)$, where $\\nu$ is related to the constraints/regularization. In particular, when the initialization does not match the “base measure” induced by the constraints/regularization, a KL cost depending on dimensionality is incurred. See Remark D.8 for more details, and discussion starting in line 203 (“Magnitude of regularization”) on this assumption.\n\n2. **The bound loses meaning if a task has unbounded or heavy-tailed losses that don't take finite expected or ess sup loss at initialization.**\n\n    Correct, though this can be mitigated by clipping the loss. This clipping is standard in practice (e.g., in reinforcement learning [A, B]) and in the theory of optimization [C, D]. Moreover, this clipping can be done in a differentiable way (e.g., using either softmin, tanh with $c \\cdot \\tanh (L / c)$, etc.). Practically, the clipping can be done at values only slightly higher than the typical loss at the initialization: since the loss is roughly monotonically decreasing in CLD with small noise, the optimization process would then typically operate below the clipping threshold and will not be affected by it. We will clarify this in the paper.\n\n    [A] Mnih, V., Kavukcuoglu, K., Silver, D. et al. Human-level control through deep reinforcement learning. Nature 518, 529–533 (2015).\n\n    [B] Schulman, John, et al. \"Proximal policy optimization algorithms.\" arXiv preprint arXiv:1707.06347 (2017).\n\n    [C] Levy, Kfir Y., Ali Kavis, and Volkan Cevher. \"STORM+: Fully adaptive SGD with momentum for nonconvex optimization.\" arXiv preprint arXiv:2111.01040 (2021).\n\n    [D] Kavis, Ali, Kfir Yehuda Levy, and Volkan Cevher. \"High probability bounds for a class of nonconvex algorithms with adagrad stepsize.\" arXiv preprint arXiv:2204.02833 (2022).\n\n\n**Questions:**\n\n1. **In Thm 2.7, can the $\\text{ess} \\sup_{h \\sim p_0} \\Psi_S (h)$ term hide dependence on dimensionality when the loss scales with width?**\n\n    Yes, in fact, the supremum can hide an infinite value, e.g. when $p_0$ is Gaussian, the essential supremum is over the entire space, meaning that when the loss is unbounded the value is $\\infty$. This can be mitigated by clipping the loss as was previously discussed.\n\n2. **The paper doesn't seem to discuss gradient-norm clipping, a common training practice. Could the authors discuss possible extensions to state-dependent drift?**\n\n    Correct. The paper does not currently discuss gradient clipping. That being said, it lays the groundwork to do so, as by Theorem 2.7 it only remains to characterize a stationary distribution of the new process. Unfortunately, this may be highly non-trivial, as the stationary distributions of such processes rarely have a closed-form expression.  However, we do not need to derive the full stationary distribution, but only need to evaluate either the expected value or an upper bound for the potential at initialization. This may be significantly simpler in some cases."}, {"review_id": "Sa5gItCwTm", "reviewer": "Reviewer_iEYq", "summary": "The manuscript derives bounds for the difference of the loss function for the data distribution and an empirical approximation. These bounds are stated in terms of the KL divergence and the Renyi infinite divergence. These bounds are based on a data independent reference measure $\\nu$ such that the stationary distribution of the process, which describes the learning process, is a Gibbs distribution with respect to $\\nu$. The authors then use some KL properties and PAC Bayes results to derive their bounds. These bounds are first derived for quite general time homogeneous Markov processes. Then they are applied to Markov processes that are solutions of SDEs, which resemble stochastic gradient Langevin dynamics for training neural networks. For  certain choices of learning procedures (e.g. parameters in a box or weight decay) the base distribution and the Gibbs potential of the stationary distribution are explicitely given, which makes for concrete bounds.These SGLD have a \"temperature\" hyperparameter. The role of this temperature is discussed, which also explains the name of the paper.", "questions": "If the following could be clarified I would happily increase my rating:\n\n* The loss function has to be positive? Why do you restrict to the case with values in [0,1]? Is this only for simplicity or is there serious issues if you don't? Popular loss functions do not have that property.\n* Theorem B.1. Please be more precise, what is a random variable, what a realization? Also its easier to understand when you make $\\hat{\\rho}$ more explicit e.g. by writing $\\hat{\\rho}\\in\\mathcal{P}(\\mathcal{H})$.\n* Then notation in Theorem B.2 is not entirely clear to me. $\\hat{\\rho}_S$ is a Markov kernel in $S$? and $h|S\\sim \\hat{\\rho}_S$ just means $h\\sim \\hat{\\rho}(S,dx)$?\n* Is the setting in Theorem B.1,B.2 not a bit different from the setting in Theorem 2.7? In 2.7 the conditional expectation is used, so both sides are random variables, while this is not the case in B.1/2 if I'm not mistaken.\n* how do you optimize over $\\lambda$ in line 457?\n\nMinor points:\n* what does it  mean that the same generalization results apply in line 165? It just changes the $f$ then?\n* please give references for the interpretation of network training by equations (9) and (10)\n* I guess you use in Corollary 3.1 that in this case $\\Psi_S=\\beta L_S$. This could be briefly mentioned in line 190\n* at the beginning the terminology for $p_t$ is \"marginal distribution\", but in line 84 it is called \"state distribution\". This could be unified.\n* please give the exact statement number in the references for claim 2.4.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is generally well written and the results are interesting. Bounds are presented in various levels of generalities which makes their use on related problems as well as in concrete applications easier. The authors openly discuss current limitations and directions of future work in section 5.\n\nWeaknesses: At certain places the notation could be a bit more precise, see Questions. Although the bounds on the difference of the errors are interesting, a discussion on the generalization on the task of the neural network would be interesting.", "was_revised": true, "final_justification": "The paper presents interesting theory, is clearly written and the authors were very precise in answering my questions", "rebuttal": "**We thank the reviewer for acknowledging that our results are interesting, and that the paper is well written, and for feedback that improved our paper. Below we address the reviewer’s comments.**\n\n\n**Weaknesses:**\n\n1. At certain places the notation could be a bit more precise, **see Questions.**\n2. **Although the bounds on the difference of the errors are interesting, a discussion on the generalization on the task of the neural network would be interesting.**\n\n    We agree that the performance on the task of the model would be interesting. In general, it can be bounded by the empirical error + a bound on the generalization gap. Thus, the current work can be applied to bound the generalization error when either 1) there are empirical observations of the training error, or 2) when there is an analytical prediction for the training error, e.g. as was derived in Appendix E.\n    We leave the theoretical analysis of the empirical error for future work.\n\n\n**Questions:**\n\n1. **The loss function has to be positive? Why do you restrict to the case with values in $[0,1]$? Is this only for simplicity or is there serious issues if you don't? Popular loss functions do not have that property.**\n\n    There are 2 functions in play —\n    1. The “error function” $f$ used to defined $E_S$ and $E_D$ which is the “test objective”, e.g. classification error (0-1 loss), and is required to be bounded in $[0, 1]$, but has no additional constraints, e.g. it need not be continuous. The boundedness condition comes from the PAC-Bayes bounds that form the basis of our analysis, namely Theorems B.1 and B.2. In the general case, we can consider $f$ which is bounded in $[0, c]$ for some $c > 0$ at the cost of a multiplicative $c$ factor to the generalization bounds, or alternatively assume that $f$ is sub-Gaussian. For simplicity we only used $[0, 1]$.\n    2. The “optimization objective” $L_S$, e.g. cross-entropy-loss, which is assumed to be non-negative and $C^2$ for the existence of a stationary distribution and the simplicity of the analysis. While for the results that depend on the KL divergence $L_S$ need not be bounded, the results that depend on $D_\\infty$ do require an essentially bounded potential, and thus a bounded $L_S$ in Corollary 3.1.2.\n\n2. **Theorem B.1. Please be more precise, what is a random variable, what a realization? Also its easier to understand when you make $\\hat{\\rho}$ more explicit e.g. by writing $\\hat{\\rho} \\in \\mathcal{P} (\\mathcal{H})$.**\n\n    The probability is taken over the training set $S$, and the event in question is that the expectation over $h$ of the generalization gap is bounded. We will clarify this in the paper.\n\n3. **Then notation in Theorem B.2 is not entirely clear to me. $\\hat{\\rho}_S$ is a Markov kernel in $S$? And $h \\mid S \\sim \\hat{\\rho}_S$ just means $h \\sim \\hat{\\rho} (S, dx)$?**\n\n    Not quite, Theorems B.1 and B.2 apply to general distributions, not necessarily ones that correspond to a Markov process. That is, $S$ denotes the training data, and $\\hat{\\rho}_S$ is any data-dependent distribution. We later use this result with a Markov process with kernel $p(dx, y; S)$, i.e. given a training set $S$, $p$ is a transition kernel defining the transition probability from a state $y$.\n    We will clarify this in the paper.\n\n4. **Is the setting in Theorem B.1,B.2 not a bit different from the setting in Theorem 2.7? In 2.7 the conditional expectation is used, so both sides are random variables, while this is not the case in B.1/2 if I'm not mistaken.**\n\n    While you are correct to question the notation, both cases are actually the same:\n    1. Theorems B.1 and 2.7.1 consider the case where the outer probability is taken over the training set $S$, while the event under consideration is that the expectation, taken over $h$ alone, of the generalization gap is bounded, given $S$. I.e. no randomization over $S$ in the expectation, and therefore the notation $\\mathbb{E} [\\cdot | S]$ can be used in Theorem B.1 as well. We will unify the notation in the next version of the paper.\n    2. Theorems B.2 and 2.7.2 consider the case where the outer probability is over both $S$ and $h$. \n\n5. **How do you optimize over $\\lambda$ in line 457?**\n\n    The derivation is quite simple and we shall include it in the paper. Starting from the expression in Theorem 2.7 of [1], we uniformly bound the log-density term with $D_\\infty$, making the bound of the generalization gap $R(\\tilde{\\theta}) - r(\\tilde{\\theta})$ $\\theta$-independent. Thus, we can optimize over $\\lambda$ to get a $D_\\infty$-dependent bound over the generalization gap.\n\n    [1] Alquier, Pierre. \"User-friendly introduction to PAC-Bayes bounds.\" arXiv preprint arXiv:2110.11216 (2021).\n\n\n**Minor points:**\n\n1. **What does it mean that the same generalization results apply in line 165? It just changes the $f$ then?**\n\n    Correct. It means that the entire analysis in Section 2 could have been made in parameter space, instead of hypothesis space, by changing $f$ and $\\Psi_S$ to be in terms of $\\theta$ instead of $h$. \n\n2. **Please give references for the interpretation of network training by equations (9) and (10).**\n\n    If the point is with regards to the claims “such … is quite common in practical scenarios such as NN training”:\n    1. Parameter clipping is related to standard norm based regularization (see e.g. [A] Section 7.2).  In addition, some Quantization-Aware Training (QAT) algorithms include parameter clipping after each update to allow for meaningful quantization [B,C,D,E].\n   2. Norm-based regularization is ubiquitous in deep learning, e.g. see [A] for a starting point.\n\t\n    If the point is with regards to the use of SDEs to model NN training, see the previous work discussed in Section 4.1.\n\n    [A] Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. MIT Press, 2016.\n\n    [B] Courbariaux, M., Bengio, Y., and David, J.-P. Binaryconnect: Training deep neural networks with binary weights during propagations. Advances in neural information processing systems, 28, 2015.\n\n    [C] Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., and Bengio, Y. Binarized neural networks. Advances in Neural Information Processing Systems, 29, 2016.\n\n    [D] Baskin, C., Zheltonozhkii, E., Rozen, T., Liss, N., Chai, Y., Schwartz, E., Giryes, R., Bronstein, A. M., and Mendelson, A. Nice: Noise injection and clamping estimation for neural network quantization. Mathematics, 9(17), 2021. ISSN 2227-7390. doi: 10.3390/math9172144.\n\n    [E] Gholami, A., Kim, S., Dong, Z., Yao, Z., Mahoney, M. W., and Keutzer, K. A survey of quantization methods for efficient neural network inference. In Low-Power Computer Vision, pp. 291–326. Chapman and Hall/CRC, 2022.\n\n3. **I guess you use in Corollary 3.1 that in this case $\\Psi_S = \\beta L_S$. This could be briefly mentioned in line 190.**\n\n    Correct. We will emphasize this in the paper.\n\n4. **At the beginning the terminology for $p_t$ is \"marginal distribution\", but in line 84 it is called \"state distribution\". This could be unified.**\n\n    Correct. We will fix this in the next version of the paper.\n\n5. **Please give the exact statement number in the references for claim 2.4.**\n\n    Cover [10] gives the monotonicity of the KL divergence for discrete time processes in Theorem 4, which can be simply used to derive the KL part of our Claim 2.4 (see Corollary A.4 and the lemmas leading to it). For the $D_\\infty$ part we give the exact reference in line 91.\n    We will clarify this in the next version."}, {"review_id": "WNS97vzPKE", "reviewer": "Reviewer_hJur", "summary": "This paper presents new generalization bounds for learning algorithms that can be written as time-homogeneous Markov processes. The proposed methods work for both discrete and continuous time processes, as soon as there exists a stationary distribution that is a Gibbs density with respect to some prior (data-independent) measure, with a potentially data-dependent potential. \n\nThe main technical novelty is to note that the normalizing constant of the Gibbs potential is cancelled out when computing some kind of weighted symmeterized KL divergence. The authors then used that the KL divergence $KL(p_t|P_infty)$ between the marginal $p_t$ at time $t$ and a stationary distribution $p_\\infty$ is non-increasing to derive a bound of the form $KL(p_t|\\nu) \\leq KL(p_0 | \\nu) + E_{p_0}[\\Psi]$, where $\\nu$ is a prior distribution and $\\Psi$ is the Gibbs potential (a disintegrated version is also proposed). This result can be used in standard PAC-Bayesian bounds to obtain generalization bounds in several settings.\n\nThe main application is the case of (regularized) continuous Langevin dynamics, where the Gibbs potential can be computed exactly. This leads to a trajectory-independent bound, involving only the expected surrogate loss at initialization, which is in contrast with most of the literature. The authors then discuss the implications of their bound and compare it to existing work. In addition to being time-uniform, a main advantage of the bound (according to the authors) is to not depend on the trajectory of the algorithm, hence, being computable before-hand.", "questions": "- It is mentioned in Section 4.1 that one of the main advantages of the new bounds is to be trajectory-independent. Why is that necessarily a good thing? One could argue that a trajectory-independent bound does not give any insight as to why generalization happens and it is common in the literature that generalization should be affected by the properties of the local minimum the algorithm converged to (ie, flat minima,...).\n- Can you empirically study the correlation between the expected loss at initialization and the generalization error. Also, how was the expectation appearing in the bound evaluated in your experiments?\n- Can you obtain closed-form bounds beyond CLD? In particular can you apply it to the discrete-time case (ie, SGLD, only SGD is discussed line 342), to the best of my knowledge, it is hard to fully characterize the Gibbs potential in that case. \n- Can you obtain a meaningful bound for CLD without regularization but in the settings of [Li et al., Futami et al.]?\n- line 210: why is $\\beta = O(N)$ sufficient for non-vacuous bounds? When $\\beta = N$, the bound does not go to $0$ as $N\\to\\infty$.", "limitations": "Most of the limitations are discussed in Section 5.\n\nAs discussed above, some implications of the bounds and comparisons with existing works could be made more precise.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The proposed generalization bounds apply to a quite general class of Markov process\n\n- For CLD, the new generalization bounds are time-independent, which, under mild conditions, ensures that the bound is non-vacuous as $t \\to \\infty$.\n\n- The proposed proof technique is ingenious and novel, despite its simplicity.\n\n\n**Weaknesses:**\n\n- The treatment of absolute continuity conditions is not always clear. It seems to me that the arguments of Section 2 if all the involved probability measures are absolutely continuous wrt the Lebesgue measure (or another reference measure). In particular, the condition $KL(p_0 | p_\\infty) < \\infty$ might be required for the derivations of Equation (1), which prevents to initialize from Dirac distributions. \n- The proposed bounds for require either regularization or bounded domain, which is a stronger requirement compared to [Li et al.] and [Futami et al.].\n- It is not clear whether the new technique can be used to obtain bounds beyond the case of CLD.\n- It is great that the bound is time-uniform, but if we take $t\\to\\infty$ in the first inequality of Equation (1), we obtain $0 \\leq KL(p_0 | p_\\infty)$, which seems loose. This makes one wonder how tight the bound is in practice. In particular, it is not clear that the proposed bounds are better than the existing gradient-based bounds.\n- The comparison with gradient-based bounds is very informal (only an implicit dimension-dependence is mentioned), it should be made more precise. Indeed, the technique of [Mou et al.] consists in a direct bound of $KL(p_t | \\nu) - KL(p_0 | \\nu)$, like in your method, and it is not clear which approach is tighter. I believe this should be formally studied.\n- The bound for CLD is quite surprising as it only depends on the initialization, while it is common wisdom that CLD should forget the initialization when $t\\to\\infty$. This might suggest that the bound is sub-optimal as $t\\to\\infty$. An important question is whether the loss at initialization indeed as an empirical impact on the generalization at time $t$, such an experiment (ie, analysis of the correlation between loss at initialization and generalization error) could validate the approach but is lacking. \n- In section 4.1, you mention that stability-based bounds grow with time, but it is not the case of [Li et al., Futami et al.]. Also [Dupuis et al.] is mentioned but is not stability-based. The literature review in Section 4 could be made more precise.\n\n**Other remarks and typos**\n\n- You use a bounded loss $f$, why not assume subgaussian loss? Such subgaussian PAC-Bayes bounds have been derived used in similar setting, for instance in [Generalization bounds for heavy-tailed SDEs through the fractional Fokker-Planck equation, Dupuis et al., 2024], it could be an easy improvement of the theory.\n- Typos: line 122 (grantees), \n- the writing feels a bit informal in places, eg, line 63 (our two divergences), line 92 (very data-dependent), line 93 (some quantity)\n- last line of claim 2.3, why is it an inequality?", "was_revised": true, "final_justification": "After the rebuttal, I still have a positive opinion on the paper and I believe it brings a very interesting perspective comparer to the existing bounds.\n\nMost of my questions were addressed,  in particular by new experiments for the comparison with existing works.\n\nI am happy to keep my acceptance score.", "rebuttal": "**We thank the reviewer for acknowledging the generality and novelty of our results, and for the detailed and helpful feedback. Below we address the reviewer’s comments (which we will clarify in the revised version of the paper), all typos and formulations will be corrected.**\n\n**Weaknesses:**\n\n1. **The treatment of absolute continuity conditions is not always clear...**\n\n    You are correct to address absolute continuity conditions. We incorporate them implicitly through the divergence terms, which are defined to be infinite when absolute continuity does not hold. In particular, note that:\n    1. Even when one of the divergence terms is $\\infty$ the inequalities hold (trivially).\n    2. Absolute continuity does not imply finite KL divergence, and is therefore a weaker condition compared to finite KL divergence (assuming that $D_{KL}$ is defined to be infinite when the measures are not absolutely continuous).\n    Finally, you are correct to note that this prevents us from initializing from the Dirac distribution, but we can take any absolutely continuous approximation of this distribution, at the cost of large divergence terms.\n\n2. **The proposed bounds require either regularization or a bounded domain...**\n\n    All of the results in Table 1 use regularization similar to the one used in Section 3 (as stated in the last two lines in the Table’s caption). The cited papers present additional results that do not require this kind of regularization. For example, Mou et al. (Proposition 1) and Li et al. (Theorem 9) used stability based reasoning to derive bounds that do not require this sort of regularization, but instead grow with time — making an implicit use of early stopping as a regularization mechanism. Futami & Fujisawa (Theorem 5) present a non-regularized version of the result for convex losses, but require regularization in order to extend it to non-convex losses. Similarly, as noted in Section 4.2, Raginsky et al. use a dissipativity assumption instead of our explicit regularization term.\n\n3. **It is not clear whether the new technique can be used to obtain bounds beyond the case of CLD.**\n\n    You are correct to observe that one bottleneck of the results in this paper is the ability to derive explicit forms for stationary distributions of typical training procedures, which we discuss in Section 5. In general, finding exact forms for stationary distributions in “natural” scenarios may be difficult, yet there are still ways to find meaningful results in these cases:\n    1. Approximation by known distributions — e.g. Raginsky et al. used CLD to approximate the discrete SGLD training scheme.\n    2. Recent work implicitly characterized the distribution of more realistic training processes, e.g. [A].\n    3. By modifying common training procedures, e.g. via a Metropolis-Hasting type update rule, the exact stationary distribution can be found, even when each training step deviates from CLD significantly.\n\n    [A] Azizian, Waïss, et al. \"What is the long-run distribution of stochastic gradient descent? A large deviations analysis.\" arXiv preprint arXiv:2406.09241 (2024).\n\n4. **It is great that the bound is time-uniform, but if we take $t \\to \\infty$ ...**\n\n    These are two good points:\n    1. This bound may indeed be loose (e.g. see Tables 2-4, where the bound is larger than the observed gap). In fact, taking $t \\to \\infty$ allows us to take into account additional properties of the system, such as the generalization of the asymptotic distribution (which can be much better,  e.g. see [8, B] characterizing the generalization capabilities of posterior sampling in NNs). Deriving exact bounds for intermediate times involves considering the particular training dynamics, which we were able to avoid by simply using the monotonicity implied by the second law.\n    2. We find that this paper complements gradient-based bounds, as they shed light on different aspects of generalization. \n\n    [B] Dziugaite, Gintare Karolina, and Daniel M. Roy. \"The Size of Teachers as a Measure of Data Complexity: PAC-Bayes Excess Risk Bounds and Scaling Laws.\" The 28th International Conference on Artificial Intelligence and Statistics. 2025.\n\n5. **The comparison with gradient-based bounds is very informal...**\n\n    1. The dependence on dimensionality is indeed only referenced implicitly, as it is hard to be characterized specifically without further assumptions. \n\n        For example, in linear regression with data $(x_i, y_i)_{i=1}^N$, $x_i \\sim \\mathcal{N} (0, \\sigma^2 I_d)$ i.i.d, labels $y_i = x_i^\\top \\theta^\\star$ and parameters $\\theta \\in \\mathbb{R}^d$ we have the following:\n\n        $$\n        \\nabla L_S (\\theta) = \\frac{1}{N} \\sum_{i=1}^N x_i x_i^\\top (\\theta - \\theta^\\star)\n        $$\n \n        so $|| \\nabla L_S (\\theta) ||_2$ typically scales as $\\sigma^2 ||\\theta - \\theta^\\star ||_2 \\sqrt{1 + d/N}$. That is, the dependence on dimensionality depends not only on the model but also on the data, stage of the optimization, etc.\n\n    2. The dependence of [Mou et al.]’s bounds on trajectory statistics has the potential of achieving tighter bounds than our trajectory agnostic ones. That being said, due to this fact they are more complicated, and deteriorate significantly when simplified, e.g. by a factor of a Lipschitz constant (see (29) in [Mou et al.]).\n\n6. **The bound for CLD is quite surprising...**\n\n    Correct! Markov processes typically forget their initialization, but due to the second law of thermodynamics (see Claim 2.4) they can only get closer to a stationary distribution. Thus the bound connects both ends — it involves **the expected/supremum value at $t=0$ of the potential at $t \\to \\infty$**. That being said, we agree that as $t \\to \\infty$ more information can be incorporated, thus improving the bound (see our previous response to (W4)).\n    Finally, from a practical point of view, the potential’s value at initialization may already be small, e.g. when finetuning a pretrained model with zero-shot capabilities.\n\n7. **In section 4.1, you mention that stability-based bounds grow with time...**\n\n    Regarding [Dupuis et al.], we do not claim that their bounds are stability based, rather we note that due to the different quantity being bounded, their results are qualitatively different than the ones in this paper. Specifically, they derive bounds for all times simultaneously, while we derive bounds for all times $t \\ge 0$ individually.\n    We will make this reference clearer.\n\n    In their paper, [Li et al.] derive multiple bounds — some are stability based and do grow with time (e.g. their Theorem 9), while others are not and are bounded as a function of $T$ (e.g. their Theorem 15, the one used in this paper’s Table 1).\n\n    As for [Futami & Fujisawa], we indeed do not claim that their bound deteriorates with time, but rather that it depends on gradient statistics, implicitly dependent on the dimension through the norms of the gradients, and has an exponential dependence on an upper bound of the loss.\n\n**Other remarks and typos:**\n\n1. **You use a bounded loss $f$, why not assume subgaussian loss...**\n\n    We opted to use a bounded $f$ for simplicity, but we can indeed use a sub-Gaussian $f$ instead, similar to many previous results.\n\n4. **Last line of claim 2.3, why is it an inequality?**\n\n    Correct, this is in fact an equality. We will change it in the next version.\n\n\n**Questions:**\n\n1. **It is mentioned in Section 4.1 that one of the main advantages of the new bounds is to be trajectory-independent. Why is that necessarily a good thing...**\n\n    Practically, with a trajectory-independent (sufficiently tight) bound we can quickly evaluate different neural network architectures, initializations, and pre-training regimes before doing optimization. Specifically, it was already observed in practice in pre-trained foundation models, where low zero-shot loss on a task typically correlates well with the generalization performance on the task after fine-tuning.\n    Theoretically, the trajectory independence of the bounds in this work complements trajectory based bounds as it shows that:\n    1. Trajectory statistics are not necessary to derive meaningful (non-vacous) generalization bounds.\n    2. It is not necessary to rely on local properties (such as Lipschitz continuity/smoothness), and coarse statistics of the global geometry can imply non-trivial generalization.\n\n2. **Can you empirically study the correlation between the expected loss at initialization and the generalization error. Also, how was the expectation appearing in the bound evaluated in your experiments?**\n\n    This is an interesting point which we intend to study further, e.g. to see what the implications of pretraining are for the bounds.\n    Regarding the evaluation of the expectations appearing in the bound, we approximated them with the appropriate empirical means, based on 3 samples for SVHN, and 5 for the rest.\n\n3. **Can you obtain closed-form bounds beyond CLD? In particular, can you apply it to the discrete-time case (ie, SGLD, only SGD is discussed line 342), to the best of my knowledge, it is hard to fully characterize the Gibbs potential in that case.**\n\n    See response (W1) by reviewer 6xrj.\n\n4. **Can you obtain a meaningful bound for CLD without regularization but in the settings of [Li et al., Futami et al.]?**\n\n    See response to (W2).\n\n5. **Line 210: why is $\\beta = O(N)$ sufficient for non-vacuous bounds? When $\\beta = N$, the bound does not go to $0$ as $N \\to \\infty$.**\n\n    By non-vacuous we mean that it can be smaller than some threshold of trivial generalization, e.g. 1/2 in balanced binary classification. In order for the bound to vanish as $N \\to \\infty$ we need $\\beta = o(N)$."}]

Author rebuttal:

Meta-review: This paper presents a rigorous and insightful theoretical analysis of how temperature influences generalization in Langevin dynamics and other Markovian learning algorithms. The authors show that, under minimal assumptions, higher temperatures can provably reduce generalization error. Remarkably, the resulting bound is independent of training time, mixing assumptions, dimensionality, and gradient norms.

Reviewers found the paper to be technically strong, clearly written, and of high relevance to the NeurIPS community. The theoretical contributions are nontrivial and broadly applicable, and the experimental results, while simple, appropriately validate the core claims.
Decision: Accept (spotlight)