Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes Itamar Harel, Yonathan Wolanowsky, Gal Vardi, Nathan Srebro, Daniel Soudry 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 𝜽 0 ∼ p 0 {\boldsymbol{\theta}}_{0}\sim p_{0} . We focus on Langevin dynamics with a positive temperature β − 1 \beta^{-1} , i.e. gradient descent on a training loss L L with infinitesimal step size, perturbed with β − 1 \beta^{-1} -variances Gaussian noise, and lightly regularized or bounded. There, we bound the generalization gap, at any time during training , by ( β ​ 𝔼 ​ L ​ ( 𝜽 0 ) + ln ⁡ ( 1 / δ ) ) / N \sqrt{(\beta\mathbb{E}L({\boldsymbol{\theta}}_{0})+\ln(1/\delta))/N} with probability 1 − δ 1-\delta over the dataset, where N N is the sample size, and 𝔼 ​ L ​ ( 𝜽 0 ) = O ⁡ ( 1 ) \mathbb{E}L({\boldsymbol{\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. 1 Introduction One main goal of contemporary machine learning theory is to predict a model’s behavior before training occurs. A commonly desired metric is 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, a significant line of work aimed to 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 as 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, a generalization bound applicable to any data-dependent 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 it is entirely independent of the training time t , both in that we do not rely on training for only a small number of steps, nor that we rely on mixing — the guarantees are valid at any time, with no dependence at all on t . Furthermore, it is also completely trajectory independent. In Section 3 we apply these general results to the particular case where training is done with CLD with loss L and inverse temperature \beta , 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 , p_{t} , its divergence (either KL or the Rényi infinity divergence) from initialization is bounded due to its monotonicity, i.e. a generalized second law of thermodynamics [ 11 , 46 ] . This surprisingly simple derivation 1 1 1 e.g. to bound the KL divergence of a Markov process having a stationary distribution with potential \Psi\in\left[0,\infty\right) , i.e. \mathop{}\!\mathrm{d}p_{\infty}/\mathop{}\!\mathrm{d}p_{0}\propto e^{-\Psi} (e.g., \Psi=\beta L for CLD), the second law implies the first inequality below \displaystyle\mathrm{KL}\!\left(p_{t}||p_{0}\right) \displaystyle=\!\int\!p_{t}\ln\frac{p_{t}}{p_{0}}\!=\!\int\!p_{t}\ln\frac{p_{t}}{p_{\infty}}\!+\!\int\!p_{t}\ln\frac{p_{\infty}}{p_{0}}\!\leq\!\int\!p_{0}\ln\frac{p_{0}}{p_{\infty}}\!+\!\int\!p_{t}\ln\frac{p_{\infty}}{p_{0}}\!=E_{p_{0}}\Psi-E_{p_{t}}\Psi\leq E_{p_{0}}\Psi. leads to our key technical result ( Corollary 2.5 ). Standard PAC-Bayes generalization bounds [ 43 ] then yield our generalization bounds ( Theorems 2.7 and 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\geq 0 along the Markov process. Our main goal is to apply these bounds to 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 KL-divergence (or, for high probability bounds, the Rényi infinity divergence, see Definition 2.1 ) between the data-dependent marginal distribution p_{t} of the predictors at time t , and some data-independent base measure \nu (the PAC-Bayes “prior”). The crux of the analysis is therefore bounding the divergence between p_{t} and \nu , based only on assumptions on the initial distribution p_{0} (specifically, the divergence between p_{0} and \nu ) and a stationary distribution p_{\infty} (specifically, requiring that p_{\infty} 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 p_{t} and \nu 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 Markov Process In this subsection, we consider a general time-invariant Markov process 2 2 2 Formally stated: we require that for any 0\leq t_{1}b\right)=0\right\} , i.e. the smallest (infimum) number that bounds f from above almost everywhere. The essential infimum is defined similarly. D_{\infty}^{\mu}\left(p\,\|\,q\right)=\esssup_{\mu}\ln\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q} , with D_{\infty}\left(p\,\|\,q\right)=D_{\infty}^{p}\left(p\,\|\,q\right) . Definition 2.2 (Gibbs distribution) . A distribution p is Gibbs w.r.t. a base distribution q with potential \Psi\!:\!\mathcal{H}\rightarrow\mathbb{R} if Z=\int e^{-\Psi}\mathop{}\!\mathrm{d}q<\infty and \mathop{}\!\mathrm{d}p=Z^{-1}e^{-\Psi}\mathop{}\!\mathrm{d}q\,. Claim 2.3 . If p,q,\mu,\nu are probability measures, and p is Gibbs w.r.t. q with potential \Psi<\infty , then 1. \mathrm{KL}_{\mu}\left(p\,\middle\|\,q\right)+\mathrm{KL}_{\nu}\left(q\,\middle\|\,p\right)=\mathbb{E}_{\nu}\Psi-\mathbb{E}_{\mu}\Psi , 2. D_{\infty}^{\mu}\left(p\,\|\,q\right)+D_{\infty}^{\nu}\left(q\,\|\,p\right)=\esssup_{\nu}\Psi-\essinf_{\mu}\Psi . So, \mathrm{KL}\left(p\,\middle\|\,q\right)+\mathrm{KL}\left(q\,\middle\|\,p\right)=\mathbb{E}_{q}\Psi-\mathbb{E}_{p}\Psi , and D_{\infty}\left(p\,\|\,q\right)+D_{\infty}\left(q\,\|\,p\right)=\esssup_{q}\Psi-\essinf_{p}\Psi . That is, the potential of 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 p being Gibbs with a bounded potential. 6 6 6 More formally: \mathrm{KL}\left(p\,\middle\|\,q\right)+\mathrm{KL}\left(q\,\middle\|\,p\right)\leq\beta iff there exists a potential \Psi such that p is Gibbs w.r.t. q with potential \Psi and \mathbb{E}_{q}\Psi-\mathbb{E}_{p}\Psi\leq\beta , and similarly D_{\infty}\left(p\,\|\,q\right)+D_{\infty}\left(q\,\|\,p\right)\leq\beta iff there exists a potential 0\leq\Psi\leq\beta such that p is Gibbs w.r.t. q with potential \Psi . See Claim B.8 for a proof. Second Law of Thermodynamics. 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 Second Law of Thermodynamics) . Let p_{t} be the marginal distribution of a time-invariant Markov process, and p_{\infty} a stationary distribution for the transitions of the Markov process (the process need not be ergodic, and p_{t} need not converge to p_{\infty} ). Then for any t\geq 0 \displaystyle\mathrm{KL}\left(p_{t}\,\middle\|\,p_{\infty}\right)\leq\mathrm{KL}\left(p_{0}\,\middle\|\,p_{\infty}\right)\quad\quad\textrm{and}\quad\quad D_{\infty}\left(p_{t}\,\|\,p_{\infty}\right)\leq D_{\infty}\left(p_{0}\,\|\,p_{\infty}\right)\,. When the stationary distribution is uniform (thus having maximal entropy), the KL-form of Claim 2.4 recovers the familiar second law of thermodynamics, i.e. that the entropy is monotonically non-decreasing. The more general form, as in Claim 2.4 , is a direct consequence of the data processing inequality, as 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 Section A.2 ). In our case, the stationary distribution p_{\infty} will not be uniform, but rather will be very data-dependent (we are interested mostly in processes that aim to optimize some data-dependent quantity, such as Langevin dynamics). Nevertheless, we do want to use Claim 2.4 to control the entropy of p_{t} relative to some benign data-independent base distribution \nu (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 \nu and at any time t we have (see Lemma B.1 in Appendix B for the full derivation): \mathrm{KL}\left(p_{t}\,\middle\|\,\nu\right)=\mathrm{KL}\left(p_{t}\,\middle\|\,p_{\infty}\right)+\mathrm{KL}_{p_{t}}\left(p_{\infty}\,\middle\|\,\nu\right)\leq\mathrm{KL}\left(p_{0}\,\middle\|\,p_{\infty}\right)+\mathrm{KL}_{p_{t}}\left(p_{\infty}\,\middle\|\,\nu\right)\\ =\mathrm{KL}\left(p_{0}\,\middle\|\,\nu\right)+\mathrm{KL}_{p_{0}}\left(\nu\,\middle\|\,p_{\infty}\right)+\mathrm{KL}_{p_{t}}\left(p_{\infty}\,\middle\|\,\nu\right)\,, (1) and similarly, D_{\infty}\left(p_{t}\,\|\,\nu\right)\leq D_{\infty}\left(p_{0}\,\|\,\nu\right)+D_{\infty}^{p_{0}}\left(\nu\,\|\,p_{\infty}\right)+D_{\infty}^{p_{t}}\left(p_{\infty}\,\|\,\nu\right)\,. (2) 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 \nu and any time-invariant Markov process, and any stationary distribution p_{\infty} that is Gibbs w.r.t. \nu with potential \Psi\geq 0 (the Markov chain need not be ergodic, and need not converge to p_{\infty} ), at any time t\geq 0 : \displaystyle\mathrm{KL}\left(p_{t}\,\middle\|\,\nu\right) \displaystyle\leq\mathrm{KL}\left(p_{0}\,\middle\|\,\nu\right)+\mathbb{E}_{p_{0}}\Psi-\mathbb{E}_{p_{t}}\Psi\leq\mathrm{KL}\left(p_{0}\,\middle\|\,\nu\right)+\mathbb{E}_{p_{0}}\Psi (3) \displaystyle D_{\infty}\left(p_{t}\,\|\,\nu\right) \displaystyle\leq D_{\infty}\left(p_{0}\,\|\,\nu\right)+\esssup_{p_{0}}\Psi (4) The important feature of Corollary 2.5 is that it bounds the divergence at any time t , in terms of a right-hand side that depends only on the initial distribution p_{0} and a stationary distribution p_{\infty} . Interpreting the divergence D\left(p_{t}\,\|\,\nu\right) as a 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 \nu ). Remark 2.6 . In order to bound the divergence D\left(p_{t}\,\|\,\nu\right) at finite time t , it is not enough to rely only on the divergences D\left(p_{0}\,\|\,\nu\right) and D\left(p_{\infty}\,\|\,\nu\right) from the initial and stationary distributions, and it is necessary to rely also on the reverse divergence D\left(\nu\,\|\,p_{\infty}\right) — 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:\mathcal{H}\times\mathcal{Z}\rightarrow[0,1] over a class \mathcal{H} , which we will refer to as the “predictor” class, and instance domain \mathcal{Z} . For example, in supervised learning \mathcal{Z}=\mathcal{X}\times\mathcal{Y} , \mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}} and f(h,(x,y))=\mathbb{I}\left\{h(x)\neq y\right\} measures the error of predicting h(x) when the correct label is y . For a source distribution D over \mathcal{Z} and data S\sim D^{N} of size N we would like to relate the population and empirical objectives E_{D}\left(h\right)=\mathbb{E}_{z\sim D}[f(h,z)]\quad\quad E_{S}\left(h\right)=\frac{1}{N}\sum_{z\in S}f(h,z). (5) In our case, we are interested in predictors generated by a data-dependent Markov process h_{t} . That is, conditioned on the data S , \{h_{t}\}_{t\geq 0} is a time-invariant Markov process, specified by some (possibly data-dependent) initial distribution p_{0}(h_{0};S) , and a transition distribution that would also depend on the data S , and specifies a (randomized) rule for generating the next iterate h_{t+1} (if in discrete time) from the current iterate h_{t} and the data S (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 a 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 \mathcal{Z} , function f:\mathcal{H}\times\mathcal{Z}\to[0,1] , sample size N\geq 8 , and any distribution \nu over \mathcal{H} . Let \{h_{t}\in\mathcal{H}\}_{t\geq 0} be a discrete or continuous time process (i.e. t\in\mathbb{Z}_{+} or t\in\mathbb{R}_{+} ) that is time-invariant Markov conditioned on S , that starts from an initial distribution p_{0}(\cdot;S) (that may depend on S ), and admits a stationary distribution conditioned on S , p_{\infty}(\cdot;S) . Let \Psi_{S}(h)\geq 0 be a non-negative potential function and assume that p_{\infty}(\cdot;S) is Gibbs w.r.t. \nu with potential \Psi_{S} . Then: 1. with probability 1-\delta over S\sim D^{N} , \displaystyle\mathbb{E}\left[E_{D}(h_{t})-E_{S}(h_{t})\middle|S\right] \displaystyle\leq\sqrt{\frac{\mathrm{KL}\left(p_{0}(\cdot;S)\,\middle\|\,\nu\right)+\mathbb{E}\left[\Psi_{S}(h_{0})\middle|S\right]+\ln\nicefrac{{N}}{{\delta}}}{2N}}\,, (6) 2. with probability 1-\delta over S\sim D^{N} and over h_{t} : \displaystyle E_{D}(h_{t})-E_{S}(h_{t}) \displaystyle\leq\sqrt{\frac{D_{\infty}\left(p_{0}(\cdot;S)\,\|\,\nu\right)+\esssup_{h\sim p_{0}(\cdot;S)}\Psi_{S}(h)+\ln\nicefrac{{N}}{{\delta}}}{2N}}\,. (7) Proof. The Theorem follows immediately by plugging the divergence bounds of Corollary 2.5 into standard PAC-Bayes guarantees, which we do in Appendix B . ∎ Remark 2.8 . A simplified variant of Theorem 2.7 can be stated when the initial distribution p_{0} is data-independent and always equal to \nu . In this case the divergence between p_{0} and \nu vanishes, and ( 6 ) and ( 7 ) become \mathbb{E}\left[E_{D}(h_{t})-E_{S}(h_{t})\middle|S\right]\leq\!\sqrt{\frac{\mathbb{E}_{p_{0}}\left[\Psi_{S}\mid S\right]+\ln\nicefrac{{N}}{{\delta}}}{2N}},\;E_{D}(h_{t})-E_{S}(h_{t})\leq\!\sqrt{\frac{\esssup_{p_{0}}\Psi_{S}+\ln\nicefrac{{N}}{{\delta}}}{2N}}\,. (8) But allowing p_{0}\neq\nu is more general, as it both allows using a data-dependent initialization (recall that \nu must be data independent) and it allows initializing to a distribution where D\left(p_{\infty}\,\|\,p_{0}\right) is infinite — e.g., we can allow initializing to a degenerate initial distribution p_{0} whose support is a strict subset of the support of p_{\infty} (in which case p_{\infty} will definitely not be Gibbs w.r.t. p_{0} ), as long as the \nu -mass of the support of p_{0} is not too small. Remark 2.9 . In Theorem 2.7 , the Markov process need not be ergodic, and need not converge to p_{\infty} , or converge at all. If there are multiple stationary distributions, the theorem holds for all of them, and so we can take p_{\infty} 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 E_{S}(h_{t}) , and the potential \Psi might also be related to it (as in, e.g., CLD). This is allowed, but is in no 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 a 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 to be related or dependent in arbitrary ways. Remark 2.11 . In Appendix C we show that in order to ensure generalization at every intermediate t , it is not sufficient to only bound \mathrm{KL}\left(p_{\infty}\,\middle\|\,\nu\right) or D_{\infty}\left(p_{\infty}\,\|\,\nu\right) , 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 p_{0} and p_{\infty} to the same data independent distribution \nu , as relating them to different data-independent distributions ensures generalization at the beginning and at the end, but not the middle of training. Remark 2.12 . 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 E_{S}\left(h_{t}\right)\approx 0 , these yield a rate of O\left(1/N\right) . 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 a stationary distribution, and bound its potential (or its expectation at p_{0} ). In this section, we will exemplify our results in a few special cases of continuous-time Langevin dynamics (CLD), a 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. Specifically, we assume that there exists some parameter space \Theta\subseteq\mathbb{R}^{d} that parameterizes a hypothesis class \mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}} via a mapping \Theta\ni{\boldsymbol{\theta}}\mapsto h_{\boldsymbol{\theta}}\in\mathcal{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, \varphi\left({\boldsymbol{\theta}}\right)=\varphi\left(h_{\boldsymbol{\theta}}\right) for any data-dependent or data-independent function \varphi over hypotheses, e.g. a training loss/objective L_{S} w.r.t a training set S . Finally, we use \mathcal{C}^{2} to denote the space of twice continuously differentiable functions on \Theta . CLD in a bounded domain. Let \Theta be a box in \mathbb{R}^{d} , and suppose that training is modeled with CLD in a bounded domain, i.e. that the parameters evolve according to the stochastic differential equation with reflection at the boundary (SDER) \displaystyle d{\boldsymbol{\theta}}_{t}=-\nabla L_{S}\left({\boldsymbol{\theta}}_{t}\right)dt+\sqrt{2\beta^{-1}}d\mathbf{w}_{t}+d\mathbf{r}_{t}\,, (9) where L_{S}\geq 0 is twice continuously differentiable, \mathbf{w}_{t} is a standard Brownian motion, and \mathbf{r}_{t} is a reflection process that constrains {\boldsymbol{\theta}}_{t} within \Theta . Such weight clipping is quite common in practical scenarios such as NN training. For simplicity, we assume that \mathbf{r}_{t} 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 p_{\infty}\left({\boldsymbol{\theta}}\right)\propto e^{-\beta L_{S}\left({\boldsymbol{\theta}}\right)}\mathbb{I}_{\Theta}\left\{{\boldsymbol{\theta}}\right\} (see Section H.2 ). Thus, when p_{0}=\mathrm{Uniform}\left(\Theta\right) , we have p_{0}=\nu . Regularized CLD in \mathbb{R}^{d} . Suppose that the parameters evolve according to the stochastic differential equation (SDE) with weight decay (i.e. \ell^{2} regularization) \displaystyle d{\boldsymbol{\theta}}_{t}=-\nabla L_{S}\left({\boldsymbol{\theta}}_{t}\right)dt-\lambda\beta^{-1}{\boldsymbol{\theta}}_{t}dt+\sqrt{2\beta^{-1}}d\mathbf{w}_{t}\,, (10) where L_{S}\geq 0 is twice continuously differentiable, \mathbf{w}_{t} is a standard Brownian motion. Such weight decay is also quite common in practical scenarios such as NN training. Similar to the previous case, with the regularization and twice continuous differentiability of L_{S} this process has a unique stationary distribution p_{\infty}\left({\boldsymbol{\theta}}\right)\propto e^{-\beta L_{S}\left({\boldsymbol{\theta}}\right)}\phi_{\lambda}\left({\boldsymbol{\theta}}\right) , where \phi_{\lambda} is the density of the multivariate Gaussian \mathcal{N}\left(\mathbf{0},\lambda^{-1}\mathbf{I}_{d}\right) . Thus, when p_{0}=\mathcal{N}\left(\mathbf{0},\lambda^{-1}\mathbf{I}_{d}\right) , we also have p_{0}=\nu . We can now formulate a generalization bound for both cases. Corollary 3.1 . Assume that the parameters evolve according to either ( 9 ) with p_{0}=\mathrm{Uniform}\left(\Theta\right) , or ( 10 ) with p_{0}=\mathcal{N}\left(\mathbf{0},\lambda^{-1}\mathbf{I}_{d}\right) . Then for any time t\geq 0 , and \delta\in\left(0,1\right) , 1. w.p. 1-\delta over S\sim D^{N} , \displaystyle\mathbb{E}_{{\boldsymbol{\theta}}_{t}\sim p_{t}}\left[E_{D}({\boldsymbol{\theta}}_{t})-E_{S}({\boldsymbol{\theta}}_{t})\mid S\right]\leq\sqrt{\frac{\beta\mathbb{E}_{{\boldsymbol{\theta}}\sim p_{0}}\left[L_{S}({\boldsymbol{\theta}})\mid S\right]+\ln\left(N/\delta\right)}{2N}}\,. (11) 2. w.p. 1-\delta over S\sim D^{N} and {\boldsymbol{\theta}}_{t}\sim p_{t} \displaystyle E_{D}({\boldsymbol{\theta}}_{t})-E_{S}({\boldsymbol{\theta}}_{t})\leq\sqrt{\frac{\beta\esssup_{p_{0}}L_{S}({\boldsymbol{\theta}})+\ln\left(N/\delta\right)}{2N}}\,. (12) The proof is simple — by assumption, in both cases p_{0}=\nu so D_{\infty}\left(p_{0}\,\|\,\nu\right)=0 . The rest is a direct substitution into Theorem 2.7 , and in particular, using \beta L_{S} as potential \Psi_{S} . 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 \mathbb{E}_{p_{0}}L_{S}\left({\boldsymbol{\theta}}\right) in practically relevant cases? (2) Can we attribute the generalization to the regularization (either with the \ell_{2} regularization term, or the bounded domain)? (3) Can models successfully train in the presence of noise with a variance large enough to make the bounds non-vacuous? Magnitude of the initial loss. Commonly, the dependence on \mathbb{E}_{p_{0}}L_{S}\left({\boldsymbol{\theta}}\right) with realistic p_{0} and L_{S} 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 a Gaussian with mean 0 and O(1) variance at initialization. So in many cases \mathbb{E}_{p_{0}}L_{S}\left({\boldsymbol{\theta}}\right)=O(1) , such as for the scalar square and logistic losses. In the multi-output case, \mathbb{E}_{p_{0}}L_{S}\left({\boldsymbol{\theta}}\right) may also depend on the number of outputs (e.g., logarithmically so in softmax-cross-entropy). A more difficult question is concerned with the case that \esssup_{p_{0}}L_{S}=\infty , which is common when p_{0} 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 (e.g. using either softmin, tanh (e.g. c\cdot\tanh(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 p_{0} (this can be somewhat relaxed, see Section 3.2 ). The same assumption, 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 empirically ( 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 \beta . Therefore, when \beta=O\left(N\right) (which is sufficient for a non-vacuous result), p_{0}=\nu , and we use a standard deep nets initialization distribution p_{0} (e.g., [ 21 , 28 ] , where \lambda\propto{\mathrm{layer\,width}} ), the regularization coefficient is O\left(\frac{\mathrm{layer\,width}}{N}\right) 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 L_{S}\leftarrow L_{S}+c\left\|{\boldsymbol{\theta}}\right\|^{2} in ( 10 ). Under standard initializations, this changes the loss in the bound by an O(c\tilde{d}) factor, where \tilde{d} is the depth of the neural network and so c\tilde{d} is small, for common values of c and \tilde{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 \beta=O\left(N\right) to obtain a non-vacuous 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, \beta=O\left(N\right) and potentially much worse (lower \beta ). In addition, other theoretical works on noisy training also typically had \beta=O\left(N\right) 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 a ball with a 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 7 7 7 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. generalizes well with \beta=O\left(\sqrt{N}\right) (e.g. see Theorem 2.8 in 1 ), which is significantly smaller than \beta=O\left(N\right) . Lastly, in Appendix E we examine the impact of \beta in the simple model of linear regression with i.i.d. standard Gaussian input, labels produced by a constant-magnitude teacher label noise, trained using regularized CLD as in ( 10 ), with \lambda\propto d to match standard initialization. We find there that whenever d\ll\beta\ll N , the added noise does not significantly affect the training or population losses, and our bound is useful, i.e., it implies a vanishing generalization gap (since \beta\ll N and \mathbb{E}_{p_{0}}L=O(1) ). Note that d\ll N is not a major constraint, since d\ll N is required to obtain low population loss in this setting, even if we did not add noise to the training process (i.e. \beta=\infty ). Magnitude of noise: empirical perspective. An inverse temperature of \beta=O\left(N\right) is also relevant in many practical settings. For example, in Bayesian settings, when we wish to (approximately) sample from the posterior, it is quite common to use variants of SGLD; then inverse temperatures of order \beta=O\left(N\right) 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 a given problem. Empirically, in Appendix F we find that \beta=O\left(N\right) 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 trajectory-dependent quantities as other non-vacuous bounds (e.g. [ 15 , 39 ] ), which can 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 non-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 \displaystyle d{\boldsymbol{\theta}}_{t}=-\nabla L_{S}\left({\boldsymbol{\theta}}_{t}\right)dt+\sqrt{2\beta^{-1}\sigma^{2}\left({\boldsymbol{\theta}}_{t}\right)}d\mathbf{w}_{t}+d\mathbf{r}_{t}\,, where \sigma^{2}\in\mathcal{C}^{2} . For example, in Section D.1 we derive the explicit form of stationary distributions when \sigma^{2}\left({\boldsymbol{\theta}}\right)=\left(L_{S}\left({\boldsymbol{\theta}}\right)+\alpha\right)^{k} or \sigma^{2}\left({\boldsymbol{\theta}}\right)=e^{\alpha L_{S}\left({\boldsymbol{\theta}}\right)} , for some k\in\mathbb{N} and \alpha>0 . In both cases, the analytic form of the stationary potential \Psi can be used directly with Theorem 2.7 to derive generalization bounds. Restricted initialization. In Section D.2 we present generalizations of Corollary 3.1 to cases where p_{0} and \nu are different. Specifically, for the bounded case we consider p_{0} that is uniform in a subset \Theta_{0}\subset\Theta 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 loosely regularized/bounded at a cost proportional to their number. For example, in a deep NN, if only a single layer is loosely regularized/bounded, 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 a 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 to 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-Bayesian theory of generalization 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 a different generalization bound for sampling from the Gibbs distribution. Due to these known generalization capabilities, some works relied on it to derive bounds for related algorithms. 4.1 Explicit Comparison for CLD 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 L_{S} and E_{S},E_{D} , respectively. For simplicity, we assume that E_{S},E_{D} are bounded in [0,1] , and are therefore 1/2 -subGaussian via Hoeffding’s inequality. We use g_{t} to denote trajectory-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 g_{t} constant w.r.t. the variable of integration. Finally, all bounds assume a Gaussian initialization \mathcal{N}\left(\mathbf{0},\lambda^{-1}\beta^{-1}\mathbf{I}_{d}\right) and regularization term \frac{\lambda}{2}\left\|{\boldsymbol{\theta}}_{t}\right\|^{2} , both with the same \lambda . Paper Trajectory dependent dimension dependence Bound (big O ) Mou et al. [49] ✓ through gradients \sqrt{\frac{\beta}{N}}\cdot\sqrt{\frac{1}{\lambda}g_{t}^{2}} Li et al. [38] ✗ through K \frac{e^{4\beta C}\sqrt{\beta}}{N}\cdot\frac{2K}{\sqrt{\lambda}} Futami and Fujisawa [19] ✓ through gradients \sqrt{\frac{\beta}{N}e^{8\beta C}}\cdot\sqrt{\frac{1}{\lambda}g_{t}^{2}} Ours ( 11 ) ✗ ✗ \sqrt{\frac{\beta}{N}}\cdot\sqrt{C} 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 ] . • It does not require very large time scales to make sure we have already converged near Gibbs [ 59 ] , nor does it deteriorate with time, as is common for stability-based 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 ) is dimension independent. However, our high-probability bound ( 12 ) relies on the effective supremum at t=0 , and may also depend on the dimension if the loss is not bounded. • The dependence on the inverse temperature \beta and loss’ (or expected loss) bound C is polynomial ( \sqrt{\beta C} ) instead of exponential [ 38 , 18 , 19 ] . • The bounded expectation assumption in ( 11 ) is weaker than a 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 \ell^{2} regularization. In Table 1 we compare in more detail Corollary 3.1 to other bounds that remain bounded as t\to\infty . Finally, Dupuis et al. [14] recently derived bounds on the generalization gap for all intermediate times 0\leq s\leq t simultaneously . Naturally, as avoiding parameters with large generalization gap is increasingly less likely as 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 a representative example, we first focus on Raginsky et al. [59] , which provided a bound for CLD (as an intermediate step for deriving a generalization bound for SGLD, a discretized version of CLD). Using spectral methods [ 5 , e.g.] , 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 \ell^{2} regularization coefficient \lambda . We use some significant observations that make the bound simpler, and time/dimension/Lipschitz/smoothness 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 us to generalize the result to any Markov process, relying on \mathbb{E}_{p_{0}}\Psi 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 a symmetric version of the divergence (e.g. by summing \mathrm{KL}\left(p\,\middle\|\,q\right) and \mathrm{KL}\left(q\,\middle\|\,p\right) ) we were able to completely remove the partition function from the analysis, avoiding the complications 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 in certain settings, but they do not allow for feature learning; Mean-field results [ 45 ] require non-standard 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 depth; And bounds for random interpolators [ 8 ] involve impractical training procedures. A closely related setting to the one studied here is SGLD, i.e. a discretized version of CLD. There is an extensive line of work bounding the generalization gap of such models (see [ 59 , 49 , 55 , 51 , 18 , 19 , 13 ] for a 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 (e.g. via smoothness, parameter norms, log-Sobolev or spectral gap constants). 5 Discussion, Limitations, and Future Work Summary. We derived a simple generalization bound for general parametric models trained using a Markov-process-based algorithm, where the dynamics have a stationary distribution with bounded potential or expected potential. For CLD with regularization/boundedness constraint matching the initial distribution, we proved that the model generalizes well when the inverse temperature is of order \beta=O\left(N\right) . There are several interesting directions to extend this result. Non-isotropic noise. We can consider a more general model for training, such as \displaystyle d{\boldsymbol{\theta}}_{t}=-\nabla L\left({\boldsymbol{\theta}}_{t}\right)dt+{\boldsymbol{\Sigma}}\left({\boldsymbol{\theta}}_{t}\right)d\mathbf{w}_{t}\,, where {\boldsymbol{\Sigma}} is a matrix-valued dispersion coefficient. In contrast, in this paper, to derive concrete generalization bounds, we focused on CLD with isotropic noise, i.e. such that {\boldsymbol{\Sigma}} is a 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 low-rank. The analysis of such processes poses various challenges beyond the ability to derive an analytic form for their stationary distribution. For example, they may concentrate on low-dimensional manifolds, possibly making the KL-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 at t\to\infty , unless there are other architectural constrains. For example, consider training a model for classification of randomly labeled data. Without regularization, sufficiently expressive models are 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 time-independent 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 et 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, a direct application of our approach to such algorithms requires additional considerations. An alternative approach is to incorporate a Metropolis-Hastings type rejection [ 47 , 27 ] , ensuring that the stationary distribution is indeed the Gibbs posterior. Can noise be useful for generalization? There is a 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 it decreases the gap between training and testing. Since higher noise could hurt 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 is 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-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 , 3 and 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 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 a 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 of 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. Appendix structure: • In 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 a 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 to ask whether the regularization alone is sufficient for the use of uniform convergence to arrive the desired generalization bounds. In Appendix G we show that the regularization used in Section 3 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. Appendix A Preliminary and Auxiliary Results A.1 Preliminaries We start by restating and introducing notation. Notation. We use bold lowercase letters (e.g. \mathbf{x}\in\mathbb{R}^{d} ) to denote vectors, bold capital letters to denote matrices (e.g. \mathbf{A}\in\mathbb{R}^{d\times d} ), 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 \mathbf{e}_{i}\in\mathbb{R}^{d} , i=1,\dots,d , to denote the standard basis vector with 1 in the i^{th} entry, and 0 elsewhere. For a subset \Omega\subseteq\mathbb{R}^{d} , we denote by \overline{\Omega} , \partial\Omega , and \Omega^{\circ} , the closure, boundary, and interior of \Omega , respectively. In addition, we denote the volume of B\subset\Omega , when it is defined, by {\left\lvert{B}\right\rvert} . With some abuse of notation, when B is finite we denote its cardinality by {\left\lvert{B}\right\rvert} . We use \left\|\cdot\right\| for the standard Euclidean norm on \mathbb{R}^{d} . Then, the open Euclidean ball centered at \mathbf{x}\in\mathbb{R}^{d} with radius r>0 is B_{r}\left(\mathbf{x}\right)=\left\{\mathbf{y}\in\mathbb{R}^{d}\,\mid\,\left\|\mathbf{y}-\mathbf{x}\right\|0: D_{\infty}\left(p_{n+1}\,\|\,p_{\infty}\right)\;\leq\;D_{\infty}\left(p_{n}\,\|\,p_{\infty}\right). Proof. Let p,q be some probability measures such that \frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q} exists. By definition, \displaystyle D_{\infty}\left(p\,\|\,q\right)=\esssup_{q}\ln\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}=\inf\left\{c\in\mathbb{R}\,\mid\,q\left(\left\{x\,\mid\,\ln\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}>c\right\}\right)=0\right\}\,. Let C\in\mathbb{R} and suppose that for all measurable A\subset\mathcal{X} , p\left(A\right)\leq e^{C}q\left(A\right) . Assume by way of contradiction that D_{\infty}\left(p\,\|\,q\right)>C , that is, that there exists c>C such that \displaystyle q\left(\left\{x\,\mid\,\ln\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}>c\right\}\right)>0\,. Denote \displaystyle A=\left\{x\,\mid\,\ln\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}>c\right\}\,, then \displaystyle p\left(A\right)=\intop_{A}\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}\mathop{}\!\mathrm{d}q>e^{c}q\left(A\right)>e^{C}q\left(A\right)\,, in contradiction to the assumption. Therefore, for all C such that p\left(A\right)\leq e^{C}q\left(A\right) for all measurable A , C\geq D_{\infty}\left(p\,\|\,q\right) . We can now show the claim. Let P(\mathop{}\!\mathrm{d}y\mid x) be the processes’ transition kernel (in measure form). We can assume D_{\infty}\left(p_{n}\,\|\,p_{\infty}\right)<\infty , since otherwise the claim holds trivially. Let A be measurable, then by definition, \displaystyle p_{n+1}\left(A\right) \displaystyle=\intop P\left(A\mid x\right)dp_{n}\left(x\right)=\intop P\left(A\mid x\right)\frac{\mathop{}\!\mathrm{d}p_{n}}{\mathop{}\!\mathrm{d}p_{\infty}}\left(x\right)\mathop{}\!\mathrm{d}p_{\infty}\left(x\right) \displaystyle\leq e^{D_{\infty}\left(p_{n}\,\|\,p_{\infty}\right)}\intop P\left(A\mid x\right)\mathop{}\!\mathrm{d}p_{\infty}\left(x\right)=e^{D_{\infty}\left(p_{n}\,\|\,p_{\infty}\right)}p_{\infty}\left(A\right)\,, so D_{\infty}\left(p_{n+1}\,\|\,p_{\infty}\right)\leq D_{\infty}\left(p_{n}\,\|\,p_{\infty}\right) . ∎ We can now state the relevant results for continuous-time processes. Corollary A.4 . Let X_{t} be a Markov process with marginals p_{t} and stationary distribution p_{\infty} . Then, for all t>0: \mathrm{KL}\left(p_{t}\,\middle\|\,p_{\infty}\right)\leq\mathrm{KL}\left(p_{0}\,\middle\|\,p_{\infty}\right)\;\mathrm{or}\;D_{\infty}\left(p_{t}\,\|\,p_{\infty}\right)\leq D_{\infty}\left(p_{0}\,\|\,p_{\infty}\right) Proof. Let 00 such that t\in\Delta t\cdot\mathbb{N} . Define Y_{n}=X_{n\Delta t} , then Y_{n} is a discrete time Markov chain with marginals p_{n\cdot\Delta t} and stationary distribution p_{\infty} , so Lemma A.2 and Lemma A.3 imply the results. ∎ Appendix B Proof of Theorem 2.7 and its Related Claims in Section 2 In this section, we 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,q,\mu,\nu are probability measures, and p is Gibbs w.r.t q with potential \Psi<\infty , then 1. \mathrm{KL}_{\mu}\left(p\,\middle\|\,q\right)+\mathrm{KL}_{\nu}\left(q\,\middle\|\,p\right)=\mathbb{E}_{\nu}\Psi-\mathbb{E}_{\mu}\Psi , 2. D_{\infty}^{\mu}\left(p\,\|\,q\right)+D_{\infty}^{\nu}\left(q\,\|\,p\right)=\esssup_{\nu}\Psi-\essinf_{\mu}\Psi . In particular, \mathrm{KL}\left(p\,\middle\|\,q\right)+\mathrm{KL}\left(q\,\middle\|\,p\right)=\mathbb{E}_{q}\Psi-\mathbb{E}_{p}\Psi , and D_{\infty}\left(p\,\|\,q\right)+D_{\infty}\left(q\,\|\,p\right)=\esssup_{q}\Psi-\essinf_{p}\Psi . Proof. By definition \frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}=Z^{-1}e^{-\Psi} where Z<\infty is the appropriate partition function. Then we have \displaystyle\mathrm{KL}_{\mu}\left(p\,\middle\|\,q\right)+\mathrm{KL}_{\nu}\left(q\,\middle\|\,p\right) \displaystyle=\int\mathop{}\!\mathrm{d}\mu\ln\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}+\int\mathop{}\!\mathrm{d}\nu\ln\frac{\mathop{}\!\mathrm{d}q}{\mathop{}\!\mathrm{d}p} \displaystyle=\int\left(-\Psi-\ln Z\right)\mathop{}\!\mathrm{d}\mu+\int\left(\Psi+\ln Z\right)\mathop{}\!\mathrm{d}\nu=\mathbb{E}_{\nu}\Psi-\mathbb{E}_{\mu}\Psi\,. Also, \displaystyle D_{\infty}^{\mu}\left(p\,\|\,q\right) \displaystyle+D_{\infty}^{\nu}\left(q\,\|\,p\right)=\ln\left(\esssup_{\mu}\frac{\mathop{}\!\mathrm{d}p}{\mathop{}\!\mathrm{d}q}\right)+\ln\left(\esssup_{\nu}\frac{\mathop{}\!\mathrm{d}q}{\mathop{}\!\mathrm{d}p}\right) \displaystyle=\esssup_{\mu}\left(-\Psi-\ln Z\right)+\esssup_{\nu}\left(\Psi+\ln Z\right)=\esssup_{\nu}\Psi-\essinf_{\mu}\Psi\,, where in the last equality we used the fact that \esssup\left(-\Psi\right)=-\essinf\Psi , and that Z is a constant. ∎ Using the Chain Rule and Claim 2.4 , we derive the bounds of ( 1 ) and ( 2 ), as re-stated and established in the following lemma. Lemma B.1 . If p_{t} is the marginal distribution of a Markov process with initial distribution p_{0} at time t , p_{\infty} is a stationary distribution, and \nu is a probability measure, then \displaystyle\mathrm{KL}\left(p_{t}\,\middle\|\,\nu\right)\leq\mathrm{KL}\left(p_{0}\,\middle\|\,\nu\right)+\mathrm{KL}_{p_{0}}\left(\nu\,\middle\|\,p_{\infty}\right)+\mathrm{KL}_{p_{t}}\left(p_{\infty}\,\middle\|\,\nu\right)\,, and similarly, \displaystyle D_{\infty}\left(p_{t}\,\|\,\nu\right)\leq D_{\infty}\left(p_{0}\,\|\,\nu\right)+D_{\infty}^{p_{0}}\left(\nu\,\|\,p_{\infty}\right)+D_{\infty}^{p_{t}}\left(p_{\infty}\,\|\,\nu\right)\,. Proof. This is a simple application of the chain rule, \displaystyle\mathrm{KL}\left(p_{t}\,\middle\|\,\nu\right) \displaystyle=\int\mathop{}\!\mathrm{d}p_{t}\ln\frac{\mathop{}\!\mathrm{d}p_{t}}{\mathop{}\!\mathrm{d}\nu}=\int\mathop{}\!\mathrm{d}p_{t}\ln\frac{\mathop{}\!\mathrm{d}p_{t}}{\mathop{}\!\mathrm{d}p_{\infty}}\frac{\mathop{}\!\mathrm{d}p_{\infty}}{\mathop{}\!\mathrm{d}\nu}=\mathrm{KL}\left(p_{t}\,\middle\|\,p_{\infty}\right)+\mathrm{KL}_{p_{t}}\left(p_{\infty}\,\middle\|\,\nu\right) \displaystyle\leq\mathrm{KL}\left(p_{0}\,\middle\|\,p_{\infty}\right)+\mathrm{KL}_{p_{t}}\left(p_{\infty}\,\middle\|\,\nu\right)=\mathrm{KL}\left(p_{0}\,\middle\|\,\nu\right)+\mathrm{KL}_{p_{0}}\left(\nu\,\middle\|\,p_{\infty}\right)+\mathrm{KL}_{p_{t}}\left(p_{\infty}\,\middle\|\,\nu\right)\,, where in the first inequality we used Claim 2.4 . Similarly, \displaystyle D_{\infty}\left(p_{t}\,\|\,\nu\right) \displaystyle=\esssup_{p_{t}}\ln\frac{\mathop{}\!\mathrm{d}p_{t}}{\mathop{}\!\mathrm{d}\nu}=\esssup_{p_{t}}\ln\frac{\mathop{}\!\mathrm{d}p_{t}}{\mathop{}\!\mathrm{d}p_{\infty}}\frac{\mathop{}\!\mathrm{d}p_{\infty}}{\mathop{}\!\mathrm{d}\nu}\leq D_{\infty}\left(p_{t}\,\|\,p_{\infty}\right)+D_{\infty}^{p_{t}}\left(p_{\infty}\,\|\,\nu\right) \displaystyle\leq D_{\infty}\left(p_{0}\,\|\,p_{\infty}\right)+D_{\infty}^{p_{t}}\left(p_{\infty}\,\|\,\nu\right)=D_{\infty}\left(p_{0}\,\|\,\nu\right)+D_{\infty}^{p_{0}}\left(\nu\,\|\,p_{\infty}\right)+D_{\infty}^{p_{t}}\left(p_{\infty}\,\|\,\nu\right)\,. ∎ Corollary 2.5 now follows from plugging in Claim 2.3 into Lemma B.1 . 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. B.2 In-Expectation PAC-Bayes Bounds Theorem B.2 (Theorem 5 from Maurer [43] ) . For any \delta\in(0,1) and any N\geq 8 , for any data-independent prior distribution \rho : \displaystyle\mathbb{P}_{S\sim D^{N}}\left(\forall_{\hat{\rho}\;}\mathrm{kl}\left(\mathbb{E}_{h\sim\hat{\rho}}E_{S}\left(h\right)\,\middle\|\,\mathbb{E}_{h\sim\hat{\rho}}E_{D}\left(h\right)\right)\leq\frac{\mathrm{KL}\left(\hat{\rho}\,\middle\|\,\rho\right)+\ln\frac{2\sqrt{N}}{\delta}}{N}\right)\geq 1-\delta\,, where \mathrm{kl}\left(a\,\middle\|\,b\right)=a\ln\tfrac{a}{b}+(1-a)\ln\tfrac{1-a}{1-b} for 0\leq a,b\leq 1 is the KL divergence for a Bernoulli random variable, and \hat{\rho} 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 a randomized predictor. But it is actually possible to get guarantees for a single draw from this predictor, which is more appropriate when we view the randomness as part of the training algorithm, that then outputs a single deterministic predictor (chosen at random). High probability guarantees for a 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 \delta\in(0,1) and N\geq 8 , for any data independent prior \rho , and any learning rule specified by a conditional probability h|S\sim\hat{\rho}_{S} such that \rho\ll\hat{\rho}_{S} S -a.s., \displaystyle\mathbb{P}_{S\sim D^{N},h\sim\hat{\rho}_{S}}\left(\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)\leq\frac{\ln\frac{\mathop{}\!\mathrm{d}\hat{\rho}_{S}}{\mathop{}\!\mathrm{d}\rho}(h)+\ln\frac{2\sqrt{N}}{\delta}}{N}\right)\geq 1-\delta\,, and so, by the definition of D_{\infty}\left(\hat{\rho}_{S}\,\|\,\rho\right) , \displaystyle\mathbb{P}_{S\sim D^{N},h\sim\hat{\rho}_{S}}\left(\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)\leq\frac{D_{\infty}\left(\hat{\rho}_{S}\,\|\,\rho\right)+\ln\frac{2\sqrt{N}}{\delta}}{N}\right)\geq 1-\delta\,. Proof. Following and modifying the proof of Theorem 5 of Maurer [43] , we start with the inequality \mathbb{E}_{S}\left[e^{N\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)}\right]\leq 2\sqrt{N} [ 43 , Theorem 1] , which holds for any h , and so also in expectation over h w.r.t. \rho : \displaystyle 2\sqrt{N} \displaystyle\geq\mathbb{E}_{h\sim\rho}\mathbb{E}_{S}\left[\exp\left(N\;\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)\right)\right]=\mathbb{E}_{S}\mathbb{E}_{h\sim\rho}\left[\exp\left(N\;\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)\right)\right] with a change of measure from \rho to \hat{\rho}_{S} , \displaystyle=\mathbb{E}_{S}\mathbb{E}_{h\sim\hat{\rho}_{S}}\left[\exp\left(N\;\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)\right)\frac{\mathop{}\!\mathrm{d}\rho}{\mathop{}\!\mathrm{d}\hat{\rho}_{S}}(h)\right] (13) \displaystyle=\mathbb{E}_{S,h\sim\hat{\rho}_{S}}\left[\exp\left(N\;\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)-\ln\frac{\mathop{}\!\mathrm{d}\hat{\rho}_{S}}{\mathop{}\!\mathrm{d}\rho}(h)\right)\right] (14) Now applying Markov’s inequality, we get: \displaystyle\mathbb{P}_{S,h\sim\hat{\rho}_{S}}\left(\exp\left(N\;\mathrm{kl}\left(E_{S}\left(h\right)\,\middle\|\,E_{D}\left(h\right)\right)-\ln\frac{\mathop{}\!\mathrm{d}\hat{\rho}_{S}}{\mathop{}\!\mathrm{d}\rho}(h)\right)\leq\frac{2\sqrt{N}}{\delta}\right)\geq 1-\delta\,. (15) Rearranging terms, we get the desired bound. ∎ B.4 Arriving at Theorem 2.7 Theorem B.4 . Consider any distribution D over \mathcal{Z} , function f:\mathcal{H}\times\mathcal{Z}\to[0,1] , and sample size N\geq 8 , any distribution \nu over \mathcal{H} , and any discrete or continuous time process \{h_{t}\in\mathcal{H}\}_{t\geq 0} (i.e. t\in\mathbb{Z}_{+} or t\in\mathbb{R}_{+} ) that is time-invariant Markov conditioned on S . Denote p_{0}(\cdot;S) the initial distribution of the Markov process (that may depend on S ). Let p_{\infty}(\cdot;S) be any stationary distribution of the process conditioned on S , and \Psi_{S}(h)\geq 0 a non-negative potential function that can depend arbitrarily on S , such that p_{\infty}(\cdot;S) is Gibbs w.r.t. \nu with potential \Psi_{S} . Then: 1. With probability 1-\delta over S\sim D^{N} , \displaystyle\mathrm{kl}\left(\mathbb{E}\left[E_{S}(h_{t})\middle|S\right]\,\middle\|\,\mathbb{E}\left[E_{D}(h_{t})\middle|S\right]\right) \displaystyle\leq\frac{\mathrm{KL}\left(p_{0}(\cdot;S)\,\middle\|\,\nu\right)+\mathbb{E}\left[\Psi_{S}(h_{0})\middle|S\right]+\ln\nicefrac{{2\sqrt{N}}}{{\delta}}}{N} (16) and so \displaystyle\mathbb{E}\left[E_{D}(h_{t})-E_{S}(h_{t})\middle|S\right] \displaystyle\leq\sqrt{2\mathbb{E}\left[E_{S}\left(h_{t}\right)\mid S\right]\frac{\mathrm{KL}\left(p_{0}(\cdot;S)\,\middle\|\,\nu\right)+\mathbb{E}\left[\Psi_{S}(h_{0})\middle|S\right]+\ln\nicefrac{{2\sqrt{N}}}{{\delta}}}{N}} \displaystyle\quad+2\frac{\mathrm{KL}\left(p_{0}(\cdot;S)\,\middle\|\,\nu\right)+\mathbb{E}\left[\Psi_{S}(h_{0})\middle|S\right]+\ln\nicefrac{{2\sqrt{N}}}{{\delta}}}{N} (17) 2. With probability 1-\delta over S\sim D^{N} and over h_{t} : \displaystyle\mathrm{kl}\left(E_{S}(h_{t})\,\middle\|\,E_{D}(h_{t})\right) \displaystyle\leq\frac{D_{\infty}\left(p_{0}(\cdot;S)\,\|\,\nu\right)+\esssup_{p_{0}}\Psi_{S}(h_{0})+\ln\nicefrac{{2\sqrt{N}}}{{\delta}}}{N} (18) and so, when E_{S}(h_{t})0\iff q\left(B\right)>0 . Therefore, \mathrm{supp}\left(p\right)=\mathrm{supp}\left(q\right) , and \mathop{}\!\mathrm{d}p/\mathop{}\!\mathrm{d}q>0 on \mathrm{supp}\left(p\right) . Denote \Psi=-\ln\mathop{}\!\mathrm{d}p/\mathop{}\!\mathrm{d}q , then p is Gibbs w.r.t. q with potential \Psi . The same derivation as in the proof of Claim 2.3 results in the bounds \mathbb{E}_{q}\Psi-\mathbb{E}_{p}\Psi\leq\beta and \esssup_{q}\Psi-\essinf_{p}\Psi\leq\beta . In particular, if the latter holds then \Psi can be shifted such that essentially 0\leq\Psi\leq\beta . ∎ Appendix C Tightness and Necessity of the Divergence Conditions If we are only interested in ensuring generalization at time t\rightarrow\infty , and when we converge to the stationary distribution p_{\infty} , then it is enough to bound the divergence D\left(p_{\infty}\,\|\,\nu\right) . If we are interested in bounding D\left(p_{t}\,\|\,\nu\right) (and consequently, the generalization gap) at all times t , then we need also to limit p_{0} ’s dependence on S , since p_{0} (as well as p_{t} for small t ) can be completely different from a stationary p_{\infty} , and just bounding D\left(p_{\infty}\,\|\,\nu\right) does not say anything about it. Bounding D\left(p_{0}\,\|\,\mu\right) , for some data-independent distribution \mu , ensures generalization at p_{0} . This leaves the following questions regarding the proof of Theorem 2.7 : • Why do we need to bound the divergences D\left(p_{\infty}\,\|\,\nu\right) and D\left(p_{0}\,\|\,\nu\right) from the same distribution \nu ? That is, we do we need to require \mu=\nu ? Bounding the divergences of p_{0} and p_{\infty} to two different divergences \mu\neq\nu is sufficient to 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 D\left(\nu\,\|\,p_{\infty}\right) ? I.e., why do we need to require p_{\infty} is Gibbs w.r.t. \nu with a bounded potential, instead of just controlling the divergence D\left(p_{\infty}\,\|\,\nu\right) , which is a weaker requirement and sufficient for generalization after mixing? As we now show, both are necesairy, and without requiring both, i.e. if we drop either one of these, we cannot ensure generalization at intermediate times t\geq 0 . Construction. Consider a supervised learning problem with \mathcal{Z}=\mathcal{X}\times\mathcal{Y} , \mathcal{X}=[0,1] , \mathcal{Y}=\{0,1\} , \mathcal{H}= all measurable functions from \mathcal{X} to \mathcal{Y} , and the zero-one loss f(h,(x,y))=\mathbb{I}\left\{h(x)\neq y\right\} , with D being the uniform distribution over \mathcal{X} , and y being \mathrm{Bernoulli}(\tfrac{1}{2}) independent of x . For all h , E_{D}(h)=0.5 . Let p_{0} be the constant zero function with probability \tfrac{1}{2} and the constant one function with probability \tfrac{1}{2} . Consider the following deterministic S -dependent transition function over h : if h_{t} is the constant zero function, then h_{t+1}=h_{S} which memorizes S , i.e. h_{S}(x)=y for (x,y)\in S , and h_{S}(x)=1 otherwise. If h_{t} is not the constant zero function, then h_{t+1} is the constant ones function. We have that p_{\infty} is deterministic at the constant one function, and \mathrm{KL}\left(p_{\infty}\,\middle\|\,p_{0}\right)=\ln{2} , and in fact p_{t}=p_{\infty} for t>1 . But with probability half, h_{1}=h_{S} , for which for any sample size N>0 , E_{S}(h_{S})=0 while E_{D}(h_{S})=\tfrac{1}{2} . How does this show it is not enough to bound D\left(p_{0}\,\|\,\nu\right) and D\left(p_{\infty}\,\|\,\nu\right) , but that we also need the reverse D\left(\nu\,\|\,p_{\infty}\right) ? Since p_{0} is data independent, we can take \nu=p_{0} , in which case \mathrm{KL}\left(p_{0}\,\middle\|\,\nu\right)=D_{\infty}\left(p_{0}\,\|\,\nu\right)=0 and \mathrm{KL}\left(p_{\infty}\,\middle\|\,\nu\right)=D_{\infty}\left(p_{\infty}\,\|\,\nu\right)=\ln{2} , but even as N\to\infty , the gap for h_{1} does not diminish. Indeed, D\left(\nu\,\|\,p_{\infty}\right)=\infty , and so p_{\infty} is not Gibbs w.r.t. \nu and Theorem 2.7 does not apply. How does this show it is not enough to bound D\left(p_{\infty}\,\|\,\nu\right)+D\left(\nu\,\|\,p_{\infty}\right) and D\left(p_{0}\,\|\,\mu\right) for \mu\neq\nu ? Since in this example p_{\infty} is also data independent, we can take \nu=p_{\infty} and \mu=p_{0} , in which case D\left(p_{0}\,\|\,\mu\right)=0 and D\left(p_{\infty}\,\|\,\nu\right)+D\left(\nu\,\|\,p_{\infty}\right)=0 . We are indeed ensured a small gap for h_{0} and h_{\infty} , but not for h_{1} . Appendix D Generalized Version of Corollary 3.1 We start by characterizing the stationary distributions of SDERs in a box with different noise scales \sigma^{2} . The stationary distributions for Gaussian initialization can be found similarly. Then, we extend Corollary 3.1 to scenarios where p_{0}\neq\nu , 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 \displaystyle d\mathbf{x}_{t}=-\nabla L\left(\mathbf{x}_{t}\right)dt+\sqrt{2\beta^{-1}\sigma^{2}\left(\mathbf{x}_{t}\right)}d\mathbf{w}_{t}+d\mathbf{r}_{t}\,, (25) with normal reflection in a box domain (for a full definition see ( 45 )-( 47 ) in Section H.2 ), where L\geq 0 is some \mathcal{C}^{2} loss function, \beta>0 is an inverse temperature parameter, and \sigma^{2} is a diffusion coefficient. First, we present a well known characterization of the stationary distribution of ( 25 ). Lemma D.1 . If L,\sigma^{2}\in\mathcal{C}^{2} , \sigma^{2}\left(\cdot\right)>0 is uniformly bounded away from 0 in \overline{\Omega} , \displaystyle Z=\intop_{\overline{\Omega}}\frac{1}{\sigma^{2}\left(\mathbf{x}\right)}\exp\left(-\beta\intop\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}d\mathbf{x}\right)<\infty\,, the integrals exist, and the field \nabla L/\sigma^{2} is conservative (curl-free), then \displaystyle p_{\infty}\left(\mathbf{x}\right)=\frac{1}{Z}\frac{1}{\sigma^{2}\left(\mathbf{x}\right)}\exp\left(-\beta\intop\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}d\mathbf{x}\right)\, (26) is a stationary distribution of ( 25 ). For completeness, the proof is presented in Section H.2.1 , following additional results and definitions in Appendix H . We can now calculate explicit stationary distributions for some choices of \sigma^{2} . Specifically, we focus on cases where \sigma^{2}\left(\mathbf{x}\right)=g\left(L\left(\mathbf{x}\right)\right) for some scalar function g , as it guarantees the curl-free condition, and is convenient to integrate. Example D.2 (Uniform noise scale) . Assuming that \sigma^{2}\left(\mathbf{x}\right)\equiv 1 , the stationary distribution becomes the well-known Gibbs distribution \displaystyle p_{\infty}\left(\mathbf{x}\right)=\frac{1}{Z}e^{-\beta L\left(\mathbf{x}\right)}\,, (27) so \displaystyle{\Psi_{\mathrm{uniform}}}\left(\mathbf{x}\right)=\beta L\left(\mathbf{x}\right)\,. (28) Example D.3 (Linear noise scale) . Let \alpha>0 , and suppose that \sigma^{2}\left(\mathbf{x}\right)=\left(L\left(\mathbf{x}\right)+\alpha\right) . Then \displaystyle\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}=\nabla\ln\left(L\left(\mathbf{x}\right)+\alpha\right) so the stationary distribution is \displaystyle p_{\infty}\left(\mathbf{x}\right)\propto\frac{1}{L\left(\mathbf{x}\right)+\alpha}\exp\left(-\beta\ln\left(L\left(\mathbf{x}\right)+\alpha\right)\right)=\frac{1}{L\left(\mathbf{x}\right)+\alpha}\left(L\left(\mathbf{x}\right)+\alpha\right)^{-\beta}=\left(L\left(\mathbf{x}\right)+\alpha\right)^{-\beta-1}\,, (29) which is integrable in a bounded domain. Recall that we want to represent p_{\infty} using a potential \Psi with \inf\Psi\geq 0 . In this case, we can start from \tilde{\Psi}\left(\mathbf{x}\right)=\left(\beta+1\right)\ln\left(L\left(\mathbf{x}\right)+\alpha\right) . Since L\geq 0 it clearly holds that \tilde{\Psi}\geq\left(\beta+1\right)\ln\left(\alpha\right) , so we can use the shifted version \displaystyle{\Psi_{\mathrm{linear}}}\left(\mathbf{x}\right)=\left(\beta+1\right)\left(\ln\left(L\left(\mathbf{x}\right)+\alpha\right)-\ln\left(\alpha\right)\right)=\left(\beta+1\right)\ln\left(\frac{L\left(\mathbf{x}\right)}{\alpha}+1\right)\,. (30) Example D.4 (Polynomial noise scale) . Let \alpha>0 , and k>1 . Suppose that \sigma^{2}\left(\mathbf{x}\right)=\left(L\left(\mathbf{x}\right)+\alpha\right)^{k} . Then \displaystyle\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}=\nabla L\left(\mathbf{x}\right)\left(L\left(\mathbf{x}\right)+\alpha\right)^{-k}=\frac{1}{1-k}\nabla\left(L\left(\mathbf{x}\right)+\alpha\right)^{1-k} so \displaystyle p_{\infty}\left(\mathbf{x}\right)\propto\left(L\left(\mathbf{x}\right)+\alpha\right)^{-k}\exp\left(\frac{\beta}{k-1}\left(L\left(\mathbf{x}\right)+\alpha\right)^{1-k}\right)\,. As before, the potential is monotonically increasing with L\left(\mathbf{x}\right) , so we can make a shift \displaystyle{\Psi_{\mathrm{poly}}}=k\ln\left(\frac{L\left(\mathbf{x}\right)}{\alpha}+1\right)+{\frac{\beta}{k-1}\left(\alpha^{1-k}-\left(L\left(\mathbf{x}\right)+\alpha\right)^{1-k}\right)}\,. Example D.5 (Exponential noise scale) . Let \alpha>0 and suppose that \sigma^{2}\left(\mathbf{x}\right)=e^{\alpha L\left(\mathbf{x}\right)} . Then \displaystyle\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}=-\frac{1}{\alpha}\nabla\left(e^{-\alpha L\left(\mathbf{x}\right)}\right) so \displaystyle p_{\infty}\left(\mathbf{x}\right)\propto e^{-\alpha L\left(\mathbf{x}\right)}\exp\left(\frac{\beta}{\alpha}e^{-\alpha L\left(\mathbf{x}\right)}\right)=\exp\left(\frac{\beta}{\alpha}e^{-\alpha L\left(\mathbf{x}\right)}-\alpha L\left(\mathbf{x}\right)\right)\,. Denote \psi\left(\tau\right)=\alpha\tau-\frac{\beta}{\alpha}e^{-\alpha\tau} , then \psi^{\prime}\left(\tau\right)=\alpha+\beta e^{-\alpha\tau}\geq 0 . Therefore, \min_{\tau\geq 0}\psi\left(\tau\right)=\psi\left(0\right)=-\frac{\beta}{\alpha} , and we can take \displaystyle{\Psi_{\mathrm{exp}}}\left(\mathbf{x}\right)=\alpha L\left(\mathbf{x}\right)-\frac{\beta}{\alpha}e^{-\alpha L\left(\mathbf{x}\right)}+\frac{\beta}{\alpha}=\alpha L\left(\mathbf{x}\right)+\frac{\beta}{\alpha}\left(1-e^{-\alpha L\left(\mathbf{x}\right)}\right) (31) D.2 Generalization bounds Bounded domain with uniform initialization. Assume that training follows a CLD in a bounded domain as described in ( 25 ) with uniform initialization p_{0}=\mathrm{Uniform}\left(\Theta_{0}\right) , where \Theta_{0}\subseteq\Theta . For simplicity we take \sigma^{2}\equiv 1 . In that case Theorem 2.7 implies the following. Lemma D.6 . Assume that the parameters evolve according to ( 25 ) with \sigma^{2}\equiv 1 and uniform initialization p_{0}=\mathrm{Uniform}\left(\Theta_{0}\right) , where \Theta_{0}\subseteq\Theta . Then for any time t\geq 0 , and \delta\in\left(0,1\right) , 1. w.p. 1-\delta over S\sim D^{N} , \displaystyle\mathbb{E}_{{\boldsymbol{\theta}}_{t}\sim p_{t}}\left[E_{D}({\boldsymbol{\theta}}_{t})-E_{S}({\boldsymbol{\theta}}_{t})\mid S\right]\leq\sqrt{\frac{\beta\mathbb{E}_{p_{0}}\left[L_{S}({\boldsymbol{\theta}})\mid S\right]+\ln{\left\lvert{\Theta}\right\rvert}/{\left\lvert{\Theta_{0}}\right\rvert}+\ln\left(N/\delta\right)}{2N}}\,. (32) 2. w.p. 1-\delta over S\sim D^{N} and {\boldsymbol{\theta}}_{t}\sim p_{t} \displaystyle E_{D}({\boldsymbol{\theta}}_{t})-E_{S}({\boldsymbol{\theta}}_{t})\leq\sqrt{\frac{\beta\esssup_{p_{0}}L_{S}({\boldsymbol{\theta}})+\ln{\left\lvert{\Theta}\right\rvert}/{\left\lvert{\Theta_{0}}\right\rvert}+\ln\left(N/\delta\right)}{2N}}\,. (33) Proof. This is a direct corollary of Theorem 2.7 with \mathrm{KL}\left(p_{0}\,\middle\|\,\nu\right)=\ln{\left\lvert{\Theta}\right\rvert}/{\left\lvert{\Theta_{0}}\right\rvert} . ∎ \ell^{2} regularization with Gaussian initialization. Let {\boldsymbol{\lambda}}\in\mathbb{R}^{d}_{>0} be regularization terms, and consider the unconstrained SDE \displaystyle d{\boldsymbol{\theta}}_{t}=-\nabla L\left({\boldsymbol{\theta}}_{t}\right)dt-\beta^{-1}\diag\left({\boldsymbol{\lambda}}\right){\boldsymbol{\theta}}_{t}dt+\sqrt{2\beta^{-1}\sigma^{2}\left({\boldsymbol{\theta}}_{t}\right)}d\mathbf{w}_{t}\,. (34) Notice that -\beta^{-1}\diag\left({\boldsymbol{\lambda}}\right){\boldsymbol{\theta}}_{t}dt corresponds to an additive regularization of the form \frac{1}{2\beta}{\boldsymbol{\theta}}_{t}^{\top}\diag\left({\boldsymbol{\lambda}}\right){\boldsymbol{\theta}}_{t} , so each parameter can have a different regularization coefficient. We shall denote by \phi_{{\boldsymbol{\lambda}}} a multivariate Gaussian distribution with mean \mathbf{0} and covariance matrix \diag\left({\boldsymbol{\lambda}}^{-1}\right) , where {\boldsymbol{\lambda}}^{-1}=\left(\lambda_{1}^{-1},\dots,\lambda_{d}^{-1}\right) . For simplicity, we present the results with \sigma^{2}\equiv 1 . Lemma D.7 . Let {\boldsymbol{\lambda}}_{0},{\boldsymbol{\lambda}}_{1}>0 , and let {\boldsymbol{\theta}}_{t} evolve according to ( 34 ) with \sigma^{2}\equiv 1 and {\boldsymbol{\lambda}}={\boldsymbol{\lambda}}_{1} , and start from a Gaussian initialization p_{0}=\phi_{{\boldsymbol{\lambda}}_{0}} . Then for any time t\geq 0 , and \delta\in\left(0,1\right) , 1. w.p. 1-\delta over S\sim D^{N} , \displaystyle\mathbb{E}_{{\boldsymbol{\theta}}_{t}\sim p_{t}}\left[E_{D}({\boldsymbol{\theta}}_{t})-E_{S}({\boldsymbol{\theta}}_{t})\mid S\right]\leq\sqrt{\frac{\beta\mathbb{E}_{p_{0}}\left[L_{S}({\boldsymbol{\theta}})\mid S\right]+\mathrm{KL}\left(\phi_{{\boldsymbol{\lambda}}_{0}}\,\middle\|\,\phi_{{\boldsymbol{\lambda}}_{1}}\right)+\ln\left(N/\delta\right)}{2N}}\,. (35) 2. w.p. 1-\delta over S\sim D^{N} and {\boldsymbol{\theta}}_{t}\sim p_{t} \displaystyle E_{D}({\boldsymbol{\theta}}_{t})-E_{S}({\boldsymbol{\theta}}_{t})\leq\sqrt{\frac{\beta\esssup_{p_{0}}L_{S}({\boldsymbol{\theta}})+\mathrm{KL}\left(\phi_{{\boldsymbol{\lambda}}_{0}}\,\middle\|\,\phi_{{\boldsymbol{\lambda}}_{1}}\right)+\ln\left(N/\delta\right)}{2N}}\,, (36) where \mathrm{KL}\left(\phi_{{\boldsymbol{\lambda}}_{0}}\,\middle\|\,\phi_{{\boldsymbol{\lambda}}_{1}}\right)=\frac{1}{2}\sum_{i=1}^{d}\left(\ln\left(\frac{\lambda_{1,i}}{\lambda_{0,i}}\right)-1+\frac{\lambda_{0,i}}{\lambda_{1,i}}\right) . 8 8 8 For {\boldsymbol{\lambda}}_{0}=\lambda_{0}\mathbf{I},{\boldsymbol{\lambda}}_{1}=\lambda_{1}\mathbf{I} , \lambda_{0},\lambda_{1}>0 , this simplifies to \mathrm{KL}\left(\phi_{\lambda_{0}}\,\middle\|\,\phi_{\lambda_{1}}\right)=\frac{d}{2}\left(\ln\frac{\lambda_{0}}{\lambda_{1}}-1+\frac{\lambda_{1}}{\lambda_{0}}\right) Proof. This is 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 d , 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, if any, on the dimension d . Appendix E Linear Regression with CLD Theorems 2.7 and 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 in which the generalization gap is 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 in the regime in which Corollary 3.1 is 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 {\boldsymbol{\theta}}^{\star}\in\mathbb{R}^{d} , y=\mathbf{x}^{\top}{\boldsymbol{\theta}}^{\star}+\varepsilon with \left\|{\boldsymbol{\theta}}^{\star}\right\|=1 and \varepsilon\sim\mathcal{N}\left(0,\sigma^{2}\right) independent of \mathbf{x} . We assume that \mathbf{x} has i.i.d. entries with \mathbb{E}\mathbf{x}=\mathbf{0} and covariance \mathbb{E}\left[\mathbf{x}\mathbf{x}^{\top}\right]=\mathbf{I} . Let \mathbf{X}\in\mathbb{R}^{N\times d} be the data (design) matrix, \mathbf{y}\in\mathbb{R}^{N} the training targets, {\boldsymbol{\varepsilon}}\in\mathbb{R}^{N} the pointwise perturbations, and {\boldsymbol{\theta}}\in\mathbb{R}^{d} the parameters in a linear regression problem. In what follows, we focus on the overdetermined case N>d , where \mathbf{X} has full column rank with probability 1, so the empirical covariance \mathbf{A}=\frac{1}{N}\mathbf{X}^{\top}\mathbf{X}\succ 0 a.s. In addition, we denote {\boldsymbol{\theta}}_{\mathrm{LS}}=\frac{1}{N}\mathbf{A}^{-1}\mathbf{X}^{\top}\mathbf{y} , and \tilde{{\boldsymbol{\theta}}}={\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{\mathrm{LS}} . The training objective is then the minimization of the regularized empirical loss \displaystyle L_{S}\left({\boldsymbol{\theta}}\right)+\frac{\lambda}{2\beta}\left\|{\boldsymbol{\theta}}\right\|^{2}=\frac{1}{2N}\left\|\mathbf{X}{\boldsymbol{\theta}}-\mathbf{y}\right\|^{2}+\frac{\lambda}{2\beta}\left\|{\boldsymbol{\theta}}\right\|^{2}=\frac{1}{2}\tilde{{\boldsymbol{\theta}}}^{\top}\mathbf{A}\tilde{{\boldsymbol{\theta}}}+C_{S}+\frac{\lambda}{2\beta}\left\|{\boldsymbol{\theta}}\right\|^{2}\,, where C_{S}=L_{S}\left({\boldsymbol{\theta}}_{\mathrm{LS}}\right)=\frac{1}{2N}\left\|\mathbf{y}\right\|^{2}-\frac{1}{2}{\boldsymbol{\theta}}_{\mathrm{LS}}\mathbf{A}{\boldsymbol{\theta}}_{\mathrm{LS}}=\frac{1}{2N}\left\|\mathbf{y}\right\|^{2}-\frac{1}{2N}\mathbf{y}^{\top}\mathbf{X}\left(\mathbf{X}^{\top}\mathbf{X}\right)^{-1}\mathbf{X}^{\top}\mathbf{y} , is the empirical irreducible error. CLD training. Assume that training is performed by CLD with inverse temperature \beta>0 , which, because L_{S} is quadratic, takes the form \displaystyle\mathop{}\!\mathrm{d}{\boldsymbol{\theta}}_{t}=-\mathbf{A}\left({\boldsymbol{\theta}}_{t}-{\boldsymbol{\theta}}_{\mathrm{LS}}\right)\mathop{}\!\mathrm{d}t-\lambda\beta^{-1}{\boldsymbol{\theta}}_{t}\mathop{}\!\mathrm{d}t+\sqrt{\frac{2}{\beta}}\mathop{}\!\mathrm{d}\mathbf{w}_{t}\,. (37) Since \mathbf{A}\succ 0 and \lambda>0 , the Gibbs distribution \displaystyle p_{\infty}\left({\boldsymbol{\theta}}\right) \displaystyle\propto\exp\left(-\frac{1}{2}\left(\left({\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{\mathrm{LS}}\right)^{\top}\beta\mathbf{A}\left({\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{\mathrm{LS}}\right)+\lambda{\boldsymbol{\theta}}^{\top}{\boldsymbol{\theta}}\right)\right) is the unique stationary distribution, and furthermore, it is the asymptotic distribution of ( 37 ). We can simplify this to a Gaussian. Denote \alpha=\lambda/\beta and \displaystyle{\boldsymbol{\Sigma}}=\frac{1}{\beta}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\;\mathrm{and}\;\bar{{\boldsymbol{\theta}}}=\beta{\boldsymbol{\Sigma}}\mathbf{A}{\boldsymbol{\theta}}_{\mathrm{LS}}=\frac{1}{N}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\mathbf{X}^{\top}\mathbf{y}\,, then \displaystyle\left({\boldsymbol{\theta}}-\bar{{\boldsymbol{\theta}}}\right)^{\top}{\boldsymbol{\Sigma}}^{-1}\left({\boldsymbol{\theta}}-\bar{{\boldsymbol{\theta}}}\right) \displaystyle=\beta{\boldsymbol{\theta}}^{\top}\left(\mathbf{A}+\alpha\mathbf{I}\right){\boldsymbol{\theta}}-2{\boldsymbol{\theta}}^{\top}{\boldsymbol{\Sigma}}^{-1}\bar{{\boldsymbol{\theta}}}+\bar{{\boldsymbol{\theta}}}^{\top}{\boldsymbol{\Sigma}}^{-1}\bar{{\boldsymbol{\theta}}} \displaystyle=\beta{\boldsymbol{\theta}}^{\top}\left(\mathbf{A}+\alpha\mathbf{I}\right){\boldsymbol{\theta}}-2\beta{\boldsymbol{\theta}}^{\top}{\boldsymbol{\Sigma}}^{-1}{\boldsymbol{\Sigma}}\mathbf{A}{\boldsymbol{\theta}}_{\mathrm{LS}}+\beta^{2}{\boldsymbol{\theta}}_{\mathrm{LS}}^{\top}\mathbf{A}{\boldsymbol{\Sigma}}{\boldsymbol{\Sigma}}^{-1}{\boldsymbol{\Sigma}}\mathbf{A}{\boldsymbol{\theta}}_{\mathrm{LS}} \displaystyle=\beta{\boldsymbol{\theta}}^{\top}\left(\mathbf{A}+\alpha\mathbf{I}\right){\boldsymbol{\theta}}-2\beta{\boldsymbol{\theta}}^{\top}\mathbf{A}{\boldsymbol{\theta}}_{\mathrm{LS}}+\beta^{2}{\boldsymbol{\theta}}_{\mathrm{LS}}^{\top}\mathbf{A}{\boldsymbol{\Sigma}}\mathbf{A}{\boldsymbol{\theta}}_{\mathrm{LS}}\,. Since the last term is constant w.r.t. {\boldsymbol{\theta}} , we deduce that \displaystyle p_{\infty}\left({\boldsymbol{\theta}}\right)\propto\exp\left(-\frac{1}{2}\left({\boldsymbol{\theta}}-\bar{{\boldsymbol{\theta}}}\right)^{\top}{\boldsymbol{\Sigma}}^{-1}\left({\boldsymbol{\theta}}-\bar{{\boldsymbol{\theta}}}\right)\right)\,, i.e. the stationary distribution is a Gaussian \mathcal{N}\left(\bar{{\boldsymbol{\theta}}},{\boldsymbol{\Sigma}}\right) . 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, \sigma is a fixed constant, \lambda\propto d (to match standard initialization), 9 9 9 Since this is a linear model d=\mathrm{layer\,width} , and as we assume the regularization matches the standard initialization. This initialization is considered in many works as a Bayesian prior in various settings [ 35 , 68 ] . N,\beta and d are large, but \beta\ll N , so our generalization bound is small (since \mathbb{E}_{p_{0}}L is a fixed constant in this case). We will find (in Remark E.2 and Remark E.4 ) that if also d\ll\beta then the training and expected population loss are not significantly degraded. This is not a major constraint, since we need d\ll N to get good population loss anyway, even without noise (i.e. \beta\rightarrow\infty ). This shows that in this regime d\ll\beta\ll 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 L_{S}\left({\boldsymbol{\theta}}_{\infty}\right)=\mathbb{E}_{{\boldsymbol{\theta}}\sim p_{\infty}}L_{S}\left({\boldsymbol{\theta}}\right) . Then \displaystyle\mathbb{E}\left[L_{S}\left({\boldsymbol{\theta}}_{\infty}\right)\mid\mathbf{X}\right] \displaystyle=\frac{1}{2\beta}\tr\left(\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\right)+\frac{\alpha^{2}}{2}{\boldsymbol{\theta}}^{\star\top}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}{\boldsymbol{\theta}}^{\star} \displaystyle\quad+\frac{\sigma^{2}\alpha^{2}}{2N}\mathrm{Tr}\left(\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\right)+\frac{\sigma^{2}}{2}\left(1-\frac{d}{N}\right)\,. Proof. From Petersen and Pedersen [56] (equation 318) \displaystyle L_{S}\left({\boldsymbol{\theta}}_{\infty}\right) \displaystyle=\frac{1}{2}\mathbb{E}\left({\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{\mathrm{LS}}\right)^{\top}\mathbf{A}\left({\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{\mathrm{LS}}\right)+C_{S} \displaystyle=\frac{1}{2}\mathrm{Tr}\left(\mathbf{A}{\boldsymbol{\Sigma}}\right)+\frac{1}{2}\left(\bar{{\boldsymbol{\theta}}}-{\boldsymbol{\theta}}_{\mathrm{LS}}\right)^{\top}\mathbf{A}\left(\bar{{\boldsymbol{\theta}}}-{\boldsymbol{\theta}}_{\mathrm{LS}}\right)+C_{S}\,. For the second term, notice that \displaystyle\bar{{\boldsymbol{\theta}}}-{\boldsymbol{\theta}}_{\mathrm{LS}} \displaystyle=\left(\beta{\boldsymbol{\Sigma}}\mathbf{A}-\mathbf{I}\right){\boldsymbol{\theta}}_{\mathrm{LS}} \displaystyle=\left(\beta{\boldsymbol{\Sigma}}\mathbf{A}+\lambda{\boldsymbol{\Sigma}}-\lambda{\boldsymbol{\Sigma}}-\mathbf{I}\right){\boldsymbol{\theta}}_{\mathrm{LS}} \displaystyle=\left({\boldsymbol{\Sigma}}\underset{={\boldsymbol{\Sigma}}^{-1}}{\underbrace{\beta\left(\mathbf{A}+\alpha\mathbf{I}\right)}}-\lambda{\boldsymbol{\Sigma}}-\mathbf{I}\right){\boldsymbol{\theta}}_{\mathrm{LS}} \displaystyle=-\lambda{\boldsymbol{\Sigma}}{\boldsymbol{\theta}}_{\mathrm{LS}}=-\alpha\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}{\boldsymbol{\theta}}_{\mathrm{LS}}\,. \mathbf{A} and {\boldsymbol{\Sigma}} are simultaneously diagonalizable. To see this, let \mathbf{A}=\mathbf{Q}{\boldsymbol{\Lambda}}\mathbf{Q}^{\top} be a spectral decomposition of \mathbf{A} , then \mathbf{A}+\alpha\mathbf{I}=\mathbf{Q}\left({\boldsymbol{\Lambda}}+\alpha\mathbf{I}\right)\mathbf{Q}^{\top} , so {\boldsymbol{\Sigma}}=\beta^{-1}\mathbf{Q}\left({\boldsymbol{\Lambda}}+\alpha\mathbf{I}\right)^{-1}\mathbf{Q}^{\top} . This means that \mathbf{A} , {\boldsymbol{\Sigma}} , and their inverses all multiplicatively commute. Therefore, \displaystyle L_{S}\left({\boldsymbol{\theta}}_{\infty}\right) \displaystyle=\frac{1}{2}\mathrm{Tr}\left(\mathbf{A}{\boldsymbol{\Sigma}}\right)+\frac{\alpha^{2}}{2}{\boldsymbol{\theta}}_{\mathrm{LS}}^{\top}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}{\boldsymbol{\theta}}_{\mathrm{LS}}+C_{S} \displaystyle=\frac{1}{2}\mathrm{Tr}\left(\mathbf{A}{\boldsymbol{\Sigma}}\right)+\frac{\alpha^{2}}{2N^{2}}\mathbf{y}^{\top}\mathbf{X}\mathbf{A}^{-1}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\mathbf{A}^{-1}\mathbf{X}^{\top}\mathbf{y}+C_{S} \displaystyle=\frac{1}{2\beta}\mathrm{Tr}\left(\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\right)+\frac{\alpha^{2}}{2N^{2}}\mathbf{y}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}^{-1}\mathbf{X}^{\top}\mathbf{y}+C_{S}\,, Conditioned on \mathbf{X} , standard results about the residuals in linear regression imply that, \displaystyle\mathbb{E}\left[C_{S}\mid\mathbf{X}\right]=\frac{\sigma^{2}}{2}\left(1-\frac{d}{N}\right)\,. In addition, for any symmetric matrix \mathbf{M} we have \displaystyle\mathbb{E}_{\boldsymbol{\varepsilon}}\left[\mathbf{y}^{\top}\mathbf{M}\mathbf{y}\right] \displaystyle=\mathbb{E}_{{\boldsymbol{\varepsilon}}}\left[\left(\mathbf{X}{\boldsymbol{\theta}}^{\star}+{\boldsymbol{\varepsilon}}\right)^{\top}\mathbf{M}\left(\mathbf{X}{\boldsymbol{\theta}}^{\star}+{\boldsymbol{\varepsilon}}\right)\right] \displaystyle=\left(\mathbf{X}{\boldsymbol{\theta}}^{\star}\right)^{\top}\mathbf{M}\mathbf{X}{\boldsymbol{\theta}}^{\star}+\mathbb{E}_{{\boldsymbol{\varepsilon}}}\left[{\boldsymbol{\varepsilon}}^{\top}\mathbf{M}{\boldsymbol{\varepsilon}}\right] \displaystyle=\left(\mathbf{X}{\boldsymbol{\theta}}^{\star}\right)^{\top}\mathbf{M}\mathbf{X}{\boldsymbol{\theta}}^{\star}+\sigma^{2}\mathrm{Tr}\left(\mathbf{M}\right)\,. In particular, \displaystyle\mathbb{E} \displaystyle\left[\mathbf{y}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}^{-1}\mathbf{X}^{\top}\mathbf{y}\mid\mathbf{X}\right] \displaystyle={\boldsymbol{\theta}}^{\star\top}\mathbf{X}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}^{-1}\mathbf{X}^{\top}\mathbf{X}{\boldsymbol{\theta}}^{\star}+\sigma^{2}\mathrm{Tr}\left(\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}^{-1}\mathbf{X}^{\top}\right) \displaystyle={\boldsymbol{\theta}}^{\star\top}N\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}^{-1}N\mathbf{A}{\boldsymbol{\theta}}^{\star}+\sigma^{2}\mathrm{Tr}\left(\mathbf{X}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}^{-1}\right) \displaystyle=N^{2}{\boldsymbol{\theta}}^{\star\top}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}{\boldsymbol{\theta}}^{\star}+N\sigma^{2}\mathrm{Tr}\left(\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\right)\,, where we used the definition of \mathbf{A} , the joint diagonalizability of \mathbf{A} and {\boldsymbol{\Sigma}} , and the cyclicality of the trace. In total, the expected training loss, conditioned on the data is \displaystyle\mathbb{E}_{{\boldsymbol{\varepsilon}}}L_{S}\left({\boldsymbol{\theta}}_{\infty}\right) \displaystyle=\frac{1}{2\beta}\tr\left(\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\right)+\frac{\alpha^{2}}{2}{\boldsymbol{\theta}}^{\star\top}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{A}{\boldsymbol{\theta}}^{\star} \displaystyle\quad+\frac{\sigma^{2}\alpha^{2}}{2N}\mathrm{Tr}\left(\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\right)+\frac{\sigma^{2}}{2}\left(1-\frac{d}{N}\right)\,. ∎ Remark E.2 . We intuitively derive the asymptotic behavior of Claim E.1 . Let \lambda be constant, and let \beta grow (so \alpha shrinks). We can decompose \left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1} as \displaystyle\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1} \displaystyle=\mathbf{A}^{-1}-\alpha\mathbf{A}^{-2}+\alpha^{2}\mathbf{A}^{-2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\,. This can be readily verified as \displaystyle\mathbf{A}^{-1} \displaystyle-\alpha\mathbf{A}^{-2}+\alpha^{2}\mathbf{A}^{-2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1} \displaystyle=\mathbf{A}^{-2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\left(\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)-\alpha\left(\mathbf{A}+\alpha\mathbf{I}\right)+\alpha^{2}\mathbf{I}\right) \displaystyle=\mathbf{A}^{-2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\left(\mathbf{A}^{2}+\alpha\mathbf{A}-\alpha\mathbf{A}-\alpha^{2}\mathbf{I}+\alpha^{2}\mathbf{I}\right) \displaystyle=\mathbf{A}^{-2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\mathbf{A}^{2} \displaystyle=\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\,, where we used the multiplicative commutativity, as before. Notice that since \mathbf{A}\succ 0 , \mathbf{A}+\alpha\mathbf{I}\succ\mathbf{A} , so \left(\mathbf{A}+\alpha\mathbf{I}\right)^{-k}\prec\mathbf{A}^{-k} for any k\in\mathbb{N} . Denote \displaystyle R_{2}\left(\alpha\right)=\alpha^{2}\mathbf{A}^{-2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\,, then \left\|R_{2}\left(\alpha\right)\right\|_{2}\leq\frac{\alpha^{2}}{\lambda_{\min}\left(\mathbf{A}\right)^{3}} , where \lambda_{\min}\left(\mathbf{A}\right) is the minimal eigenvalue of \mathbf{A} . As the elements of \mathbf{X} are i.i.d. with mean 0 and variance 1 , the limiting distribution of the spectrum of \mathbf{A} as N,d\to\infty with d/N\to\gamma\in\left(0,1\right) is the Marchenko–Pastur distribution, which is supported on \left[\left(1-\sqrt{\gamma}\right)^{2},\left(1+\sqrt{\gamma}\right)^{2}\right] . In particular, as N,d\to\infty , \lambda_{\min}\left(\mathbf{A}\right)\geq\left(1-\sqrt{d/N}\right)^{2} , so for \varepsilon>0 , \displaystyle\left\|R_{2}\left(\alpha\right)\right\|_{2}\leq\frac{\alpha^{2}}{\left(1-\sqrt{d/N}-\varepsilon\right)^{6}}\, with high probability. Therefore, in the following we shall treat the remainder as R_{2}\left(\alpha\right)=O\left(\alpha^{2}\right) , even when taking the expectation over \mathbf{X} . Since \alpha=\lambda/\beta and \lambda\propto d , then for d\leq\beta , we have \alpha/\beta=O\left(\alpha^{2}\right) , and we conclude that \displaystyle\mathbb{E}\left[L_{S}\left({\boldsymbol{\theta}}_{\infty}\right)\mid\mathbf{X}\right] \displaystyle=\frac{d}{2}\left(\frac{1}{\beta}+\sigma^{2}\left(\frac{1}{d}-\frac{1}{N}\right)\right)+O\left(\alpha^{2}\right)\,. Therefore, the added noise does not significantly hurt the training loss when \frac{1}{\beta}\lessapprox\sigma^{2}\left(\frac{1}{d}-\frac{1}{N}\right) , or equivalently, \beta\gtrapprox\frac{Nd}{(N-d)\sigma^{2}} . In particular, this holds when d\ll\beta\ll N , which is a regime where our generalization bound Corollary 3.1 also becomes small (since \beta\ll N ). This shows that the randomness required by Corollary 3.1 can allow for successful optimization of the training loss. Moving on to the population loss, we define L_{D} in the usual way \displaystyle L_{D}\left({\boldsymbol{\theta}}_{t}\right)=\frac{1}{2}\mathbb{E}_{\mathbf{x},\varepsilon}\left(\mathbf{x}^{\top}{\boldsymbol{\theta}}_{t}-y\right)^{2}=\frac{1}{2}\mathbb{E}\left(\mathbf{x}^{\top}{\boldsymbol{\theta}}_{t}-\mathbf{x}^{\top}{\boldsymbol{\theta}}^{\star}-\varepsilon\right)^{2}\,. Due to the independence between \mathbf{x} and \varepsilon , \displaystyle L_{D}\left({\boldsymbol{\theta}}\right)=\frac{1}{2}\mathbb{E}\left(\mathbf{x}^{\top}\left({\boldsymbol{\theta}}-{\boldsymbol{\theta}}^{\star}\right)\right)^{2}+\frac{\sigma^{2}}{2}=\frac{1}{2}\left\|{\boldsymbol{\theta}}-{\boldsymbol{\theta}}^{\star}\right\|^{2}+\frac{\sigma^{2}}{2}\,. Claim E.3 . With some abuse of notation, denote L_{D}\left({\boldsymbol{\theta}}_{\infty}\right)=\mathbb{E}_{{\boldsymbol{\theta}}\sim p_{\infty}}L_{D}\left({\boldsymbol{\theta}}\right) . Then \displaystyle\mathbb{E}\left[L_{D}\left({\boldsymbol{\theta}}_{\infty}\right)\mid\mathbf{X}\right] \displaystyle=\frac{1}{2\beta}\mathrm{Tr}\left(\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\right)+\frac{1}{2}{\boldsymbol{\theta}}^{\star\top}\mathbf{A}^{2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}{\boldsymbol{\theta}}^{\star} \displaystyle+\frac{\sigma^{2}}{2N}\tr\left(\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\right)-{\boldsymbol{\theta}}^{\star\top}\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}{\boldsymbol{\theta}}^{\star}+\frac{1}{2}\left\|{\boldsymbol{\theta}}^{\star}\right\|^{2}+\frac{\sigma^{2}}{2}\,. Proof. Taking the expectation w.r.t {\boldsymbol{\theta}}\sim\mathcal{N}\left(\bar{{\boldsymbol{\theta}}},{\boldsymbol{\Sigma}}\right) we get from Petersen and Pedersen [56] \displaystyle L_{D}\left({\boldsymbol{\theta}}_{\infty}\right) \displaystyle=\frac{1}{2}\mathrm{Tr}\left({\boldsymbol{\Sigma}}\right)+\frac{1}{2}\left\|\bar{{\boldsymbol{\theta}}}-{\boldsymbol{\theta}}^{\star}\right\|^{2}+\frac{\sigma^{2}}{2} \displaystyle=\frac{1}{2\beta}\mathrm{Tr}\left(\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\right)+\frac{1}{2}\bar{{\boldsymbol{\theta}}}^{\top}\bar{{\boldsymbol{\theta}}}-\bar{{\boldsymbol{\theta}}}^{\top}{\boldsymbol{\theta}}^{\star}+\frac{1}{2}\left\|{\boldsymbol{\theta}}^{\star}\right\|^{2}+\frac{\sigma^{2}}{2}\,. We can simplify some of the terms when taking the expectation conditioned on \mathbf{X} . \displaystyle\mathbb{E}_{{\boldsymbol{\varepsilon}}}\left[\bar{{\boldsymbol{\theta}}}^{\top}\bar{{\boldsymbol{\theta}}}\right] \displaystyle=\frac{1}{N^{2}}\mathbb{E}\left[\mathbf{y}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}\mathbf{X}^{\top}\mathbf{y}\right] \displaystyle=\frac{1}{N^{2}}\mathbb{E}\left[\left(\mathbf{X}{\boldsymbol{\theta}}^{\star}+{\boldsymbol{\varepsilon}}\right)^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{X}^{\top}\left(\mathbf{X}{\boldsymbol{\theta}}^{\star}+{\boldsymbol{\varepsilon}}\right)\right] \displaystyle=\frac{1}{N^{2}}{\boldsymbol{\theta}}^{\star\top}\mathbf{X}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{X}^{\top}\mathbf{X}{\boldsymbol{\theta}}^{\star}+\frac{1}{N^{2}}\mathbb{E}_{{\boldsymbol{\varepsilon}}}\left[{\boldsymbol{\varepsilon}}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{X}^{\top}{\boldsymbol{\varepsilon}}\right] \displaystyle={\boldsymbol{\theta}}^{\star\top}\mathbf{A}^{2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}{\boldsymbol{\theta}}^{\star}+\frac{\sigma^{2}}{N^{2}}\tr\left(\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\mathbf{X}^{\top}\right) \displaystyle={\boldsymbol{\theta}}^{\star\top}\mathbf{A}^{2}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}{\boldsymbol{\theta}}^{\star}+\frac{\sigma^{2}}{N}\tr\left(\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}\right)\,. In addition, \displaystyle\mathbb{E}_{{\boldsymbol{\varepsilon}}}\left[\bar{{\boldsymbol{\theta}}}^{\top}{\boldsymbol{\theta}}^{\star}\right] \displaystyle=\frac{1}{N}\mathbb{E}_{{\boldsymbol{\varepsilon}}}\left[\left(\mathbf{X}{\boldsymbol{\theta}}^{\star}+{\boldsymbol{\varepsilon}}\right)^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}{\boldsymbol{\theta}}^{\star}\right] \displaystyle=\frac{1}{N}{\boldsymbol{\theta}}^{\star\top}\mathbf{X}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}{\boldsymbol{\theta}}^{\star}+\frac{1}{N}\mathbb{E}_{{\boldsymbol{\varepsilon}}}\left[{\boldsymbol{\varepsilon}}^{\top}\mathbf{X}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}{\boldsymbol{\theta}}^{\star}\right] \displaystyle={\boldsymbol{\theta}}^{\star\top}\mathbf{A}\left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}{\boldsymbol{\theta}}^{\star}\,. 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 \lambda be constant, and let \beta grow (so \alpha shrinks). As in Remark E.2 , we use the approximation \left(\mathbf{A}+\alpha\mathbf{I}\right)^{-1}=\mathbf{A}^{-1}-\alpha\mathbf{A}^{-2}+O\left(\alpha^{2}\mathbf{I}\right) , which also implies \left(\mathbf{A}+\alpha\mathbf{I}\right)^{-2}=\mathbf{A}^{-2}-2\alpha\mathbf{A}^{-3}+O\left(\alpha^{2}\mathbf{I}\right) , and treat the remainders as O\left(\alpha^{2}\right) even when taking the expectation w.r.t. \mathbf{X} . Then, \displaystyle\mathbb{E}\left[L_{D}\left({\boldsymbol{\theta}}_{\infty}\right)\mid\mathbf{X}\right] \displaystyle=\frac{1}{2\beta}\tr\left(\mathbf{A}^{-1}-\alpha\mathbf{A}^{-2}+O\left(\alpha^{2}\mathbf{I}\right)\right)+\frac{1}{2}{\boldsymbol{\theta}}^{\star\top}\mathbf{A}^{2}\left(\mathbf{A}^{-2}-2\alpha\mathbf{A}^{-3}+O\left(\alpha^{2}\mathbf{I}\right)\right){\boldsymbol{\theta}}^{\star} \displaystyle\quad+\frac{\sigma^{2}}{2N}\tr\left(\mathbf{A}\left(\mathbf{A}^{-2}-2\alpha\mathbf{A}^{-3}+O\left(\alpha^{2}\mathbf{I}\right)\right)\right) \displaystyle\quad-{\boldsymbol{\theta}}^{\star\top}\mathbf{A}\left(\mathbf{A}^{-1}-\alpha\mathbf{A}^{-2}+O\left(\alpha^{2}\mathbf{I}\right)\right){\boldsymbol{\theta}}^{\star}+\frac{1}{2}\left\|{\boldsymbol{\theta}}^{\star}\right\|^{2}+\frac{\sigma^{2}}{2} \displaystyle=\frac{1}{2}\left(\frac{1}{\beta}+\frac{\sigma^{2}}{N}\right)\tr\left(\mathbf{A}^{-1}\right)+\frac{\sigma^{2}}{2} \displaystyle\quad-\frac{\alpha}{2\beta}\tr\left(\mathbf{A}^{-2}+O\left(\alpha\mathbf{I}\right)\right)-\alpha{\boldsymbol{\theta}}^{\star\top}\left(\mathbf{A}^{-1}+O\left(\alpha\mathbf{I}\right)\right){\boldsymbol{\theta}}^{\star} \displaystyle\quad-\frac{\sigma^{2}\alpha}{N}\tr\left(\mathbf{A}^{-2}+O\left(\alpha\mathbf{I}\right)\right)+\alpha{\boldsymbol{\theta}}^{\star\top}\left(\mathbf{A}^{-1}+O\left(\alpha\mathbf{I}\right)\right){\boldsymbol{\theta}}^{\star}\,. Simplifying, we arrive at \displaystyle\mathbb{E}\left[L_{D}\left({\boldsymbol{\theta}}_{\infty}\right)\mid\mathbf{X}\right] \displaystyle=\frac{1}{2}\left(\frac{1}{\beta}+\frac{\sigma^{2}}{N}\right)\tr\left(\mathbf{A}^{-1}\right)+\frac{\sigma^{2}}{2}-\alpha\left(\frac{1}{2\beta}+\frac{\sigma^{2}}{N}\right)\tr\left(\mathbf{A}^{-2}\right)+O\left(\alpha^{2}\right)\,. Assuming that \mathbf{x} are i.i.d. \mathcal{N}\left(\mathbf{0},\mathbf{I}\right) , N\cdot\mathbf{A}\sim\mathcal{W}_{d}\left(N,\mathbf{I}\right) , i.e. has a Wishart distribution. According to Theorem 3.3.16 of [ 24 ] , if N>d+3 then \displaystyle\mathbb{E}\mathbf{A}^{-1} \displaystyle=\frac{N}{N-d-1}\mathbf{I}\,, \displaystyle\mathbb{E}\mathbf{A}^{-2} \displaystyle=N^{2}\cdot\frac{\tr\left(\mathbf{I}\right)\mathbf{I}}{\left(N-d\right)\left(N-d-1\right)\left(N-d-3\right)}+N^{2}\cdot\frac{\mathbf{I}}{\left(N-d\right)\left(N-d-3\right)} \displaystyle=\frac{N^{2}d+N^{2}\left(N-d-1\right)}{\left(N-d\right)\left(N-d-1\right)\left(N-d-3\right)}\mathbf{I}\,. Then, the expectation over \mathbf{X} and if \frac{\sigma^{2}}{N}\lessapprox\alpha (which is true for \lambda\propto d and \beta\ll N like we assume here), \displaystyle\mathbb{E}L_{D}\left({\boldsymbol{\theta}}_{\infty}\right) \displaystyle=\frac{1}{2}\left(\frac{1}{\beta}+\sigma^{2}\left(\frac{1}{N}+\frac{N-d-1}{Nd}\right)\right)\cdot\frac{Nd}{N-d-1}+O\left(\alpha^{2}\right) \displaystyle=\frac{1}{2}\left(\frac{1}{\beta}+\sigma^{2}\cdot\frac{N-1}{Nd}\right)\cdot\frac{Nd}{N-d-1}+O\left(\alpha^{2}\right)\,. This result is similar to the one in Remark E.2 — for the expected population loss not to be significantly hurt by the added noise, it must hold that \beta\gtrapprox\frac{Nd}{\left(N-1\right)\sigma^{2}} . In particular, this holds when d\ll\beta\ll N , which is a regime where our generalization bound Corollary 3.1 also becomes small (since \beta\ll N ). This shows that the randomness required by Corollary 3.1 does not harm the expected population loss. Appendix F Numerical Experiments F.1 Experimental results The following are results of training with SGLD (a discretized version of the CLD in ( 10 )) on a few benchmark datasets. Notice we use the regularized version where regularization coefficient is \lambda\cdot\beta^{-1} and the \lambda hyperparameter is dictated by the initialization from the normal distribution p_{0}=\mathcal{N}\left(\mathbf{0},\lambda^{-1}\mathbf{I}_{d}\right) . We used a common initialization of \mathcal{N}\left(\mathbf{0},\frac{1}{d_{\mathrm{in}}}\right) , i.e. \lambda=d_{\mathrm{in}} . We use several different values of \beta relative to N (the number of training samples). For simplicity, we focused on binary classification cases. In all datasets with more than 2 classes, we constructed a binary classification task by partitioning the original label set into 2 disjoint sets of the same size. The results demonstrate that learning with SGLD is possible with various values of \beta . In fact, in several instances, the injected noise appears to improve the generalization gap , e.g, in SVHN [ 53 ] , in all the tested \beta values between 0.4\cdot N and 2\cdot N the average test error remained almost the same while the training error decreased as \beta increased (i.e. the generalization gap increased). Notably, we also observe that for sufficiently large levels of noise, the generalization bounds are non-vacuous. Table 2: MNIST (binary classification) \beta E_{S} E_{D} E_{D}-E_{S} Bound ( 11 ) w.p 0.99 0.01\cdot N 0.2279(\pm 0.0021) 0.1972(\pm 0.0243) -0.0307 0.06124 0.03\cdot N 0.1161(\pm 0.0028) 0.1074(\pm 0.0035) -0.0087 0.10498 0.1\cdot N 0.0618(\pm 0.001) 0.062(\pm 0.0041) 0.0002 0.19096 0.15\cdot N 0.0497(\pm 0.0014) 0.0494(\pm 0.0031) -0.0003 0.23376 0.4\cdot N 0.0281(\pm 0.0002) 0.0358(\pm 0.0029) 0.0077 0.38147 0.7\cdot N 0.0202(\pm 0.0006) 0.0284(\pm 0.0024) 0.0082 0.50456 N 0.0162(\pm 0.0006) 0.0278(\pm 0.0023) 0.0116 0.60302 2\cdot N 0.0092(\pm 0.0004) 0.0262(\pm 0.0016) 0.017 0.85273 \infty 0.0001(\pm 0) 0.0229(\pm 0.0004) 0.0228 >1 Table 3: fashionMNIST (binary classification) \beta E_{S} E_{D} E_{D}-E_{S} Bound ( 11 ) w.p 0.99 0.01\cdot N 0.1215(\pm 0.0027) 0.1251(\pm 0.0087) 0.0036 0.06833 0.03\cdot N 0.0999(\pm 0.001) 0.1087(\pm 0.0167) 0.0088 0.11738 0.1\cdot N 0.0821(\pm 0.0012) 0.086(\pm 0.001) 0.0039 0.21368 0.15\cdot N 0.0765(\pm 0.0009) 0.0803(\pm 0.0015) 0.0038 0.26159 0.4\cdot N 0.0635(\pm 0.0005) 0.0722(\pm 0.002) 0.0087 0.42695 0.7\cdot N 0.0567(\pm 0.0006) 0.0691(\pm 0.0019) 0.0124 0.56473 N 0.0525(\pm 0.0005) 0.0675(\pm 0.0013) 0.015 0.67495 2\cdot N 0.043(\pm 0.0007) 0.0672(\pm 0.0023) 0.0242 0.95446 \infty 0.0248(\pm 0.001) 0.0675(\pm 0.0033) 0.0427 >1 Table 4: SVHN (binary classification) \beta E_{S} E_{D} E_{D}-E_{S} Bound ( 11 ) w.p 0.99 0.01\cdot N 0.0746(\pm 0.0012) 0.1033(\pm 0.0032) 0.0287 0.05898 0.03\cdot N 0.0441(\pm 0.0004) 0.067(\pm 0.0026) 0.0229 0.10203 0.1\cdot N 0.0282(\pm 0.0008) 0.0476(\pm 0.007) 0.0194 0.1862 0.15\cdot N 0.0251(\pm 0.0005) 0.0445(\pm 0.002) 0.0194 0.22803 0.4\cdot N 0.0182(\pm 0.0005) 0.0374(\pm 0.0017) 0.0192 0.37235 0.7\cdot N 0.0146(\pm 0.0004) 0.0363(\pm 0.002) 0.0217 0.49256 N 0.0124(\pm 0.0002) 0.0342(\pm 0.0014) 0.0218 0.58872 2\cdot N 0.0085(\pm 0) 0.0371(\pm 0.001) 0.0286 0.83256 Figure 1: Parity Results. Left: Training error. Right: test error and generalization bound. F.2 Training details MNIST and fashionMNIST. We trained a fully connected network with 4 hidden layers of sizes [256,256,256,128] and ReLU activation, lr=0.01 , for 60 epochs. SVHN. The network was trained with a convolutional neural network with 5 convolutional layers, lr=0.01 , for 80 epochs. The complete architecture: • Two convolutional layers (3×3 kernel, padding 1) with 32 channels, followed by ReLU activations and a 2×2 max pooling. • Two convolutional layers (3×3 kernel, padding 1) with 64 channels, followed by ReLU activations and a 2×2 max pooling. • A 3×3 convolution with 128 channels, ReLU, and 2×2 max pooling. • 2 A linear layer 2048\rightarrow 512 , followed by ReLU and another 512\rightarrow 1 linear layer Parity. In this experiment, we consider a synthetic binary classification task where each input is a binary vector of length 70 and the target label is defined as the parity of 3 randomly selected input dimensions. We train a neural network using SGLD with varying values of the inverse temperature parameter \beta and different sample sizes. The network was trained with a fully connected network with 4 hidden layers of sizes [512,1028,2064,512] and ReLU activation, lr=0.05 , for 100 epochs. The results show that injecting noise can improve the generalization gap: specifically, the case of \beta\geq N^{2} leads to overfitting, while smaller values of \beta (e.g., 1.5\cdot N to 12\cdot N ) yield better generalization. Moreover, as well as in the benchmark datasets, in this setting, our generalization bound is non-vacuous in several cases. F.3 Comparison with the bound of Mou et al. [49] The bound proposed by Mou et al. [49] has demonstrated non-vacuous results. To further assess the effectiveness of our bound and evaluate its relative tightness, we conducted a series of numerical experiments on the MNIST binary classification task (see Tables 5 - 8 ). It is worth emphasizing that our bound offers a distinct advantage: it can be evaluated directly at initialization, whereas the bound of Mou et al. [49] depends on gradients and therefore cannot be computed before training. When testing their bound we used the continuous version, i.e. \mathbb{E}_{p_{T}}\!\left[E_{D}\!\left({\boldsymbol{\theta}}\right)\!-E_{S}\!\left({\boldsymbol{\theta}}\right)\right]\leq s\left(\frac{\beta}{2n}\int_{0}^{T}e^{\frac{\lambda}{2}(T-t)}\mathbb{E}_{p_{t}}\!\left[\|\nabla L_{S}({\boldsymbol{\theta}})\|^{2}\right]dt+\frac{\log(1/\delta)+\log\log M}{n}\right)^{0.5}\,. For simplicity, we omitted the term involving M (which makes the bound more favorable). In addition, we set s=0.5 since the zero–one loss (denoted here by f(w) , unlike [ 49 ] ) is bounded within the interval [0,1] . We observed that the relative tightness of the two bounds varies across different values of \beta and at different points in time. Consequently, in some instances, the bound of Mou et al. [49] is tighter, while in others our bound performs better, and we could not draw any further conclusions. Table 5: 20 training epochs \beta Train Error Test Error Generalization Gap Mou et al. [49] Our bound 0.03N=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 N=60000 0.0249 0.0428 0.0179 0.7032 0.6572 2N=120000 0.0209 0.0356 0.0147 1.4044 0.9294 Table 6: 50 training epochs \beta Train Error Test Error Generalization Gap Mou et al. [49] Our bound 0.03N=1800 0.1156 0.1697 0.0541 0.0637 0.1144 0.15N=9000 0.0491 0.0615 0.0124 0.1324 0.2548 0.4N=24000 0.0295 0.0348 0.0053 0.2992 0.4157 0.7N=42000 0.0217 0.0283 0.0066 0.4903 0.5499 N=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 \beta Train Error Test Error Generalization Gap Mou et al. [49] Our bound 0.03N=1800 0.122 0.1049 -0.0171 0.1273 0.1144 0.15N=9000 0.0502 0.0476 -0.0026 0.1503 0.2548 0.4N=24000 0.0284 0.0296 0.0011 0.2853 0.4157 0.7N=42000 0.0178 0.0247 0.0069 0.4595 0.5499 N=60000 0.0127 0.0240 0.0113 0.6478 0.6572 2N=120000 0.0050 0.0234 0.0184 1.2158 0.9294 Table 8: 400 training epochs \beta Train Error Test Error Generalization Gap 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.7N=42000 0.0161 0.0271 0.0110 0.4548 0.5499 N=60000 0.0112 0.0255 0.0143 0.6247 0.6572 2N=120000 0.0038 0.0249 0.0211 1.1455 0.9294 Appendix 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 \frac{1}{\sqrt{d_{j-1}}} , where d_{j-1} is the width of layer j-1 . Moreover, we assume that the input \mathbf{x} is such that each coordinate x_{i} is bounded in [-1,1] . We show that m training examples do not suffice for learning constant depth networks with O(m) parameters. Thus, even a mild overparameterization prevents uniform convergence in our setting. Our result follows by bounding the fat-shattering dimension, defined as follows: Definition G.1 . Let \mathcal{F} be a class of real-valued functions from an input domain \mathcal{X} . We say that \mathcal{F} shatters m points \{\mathbf{x}_{i}\}_{i=1}^{m}\subseteq\mathcal{X} with margin \epsilon>0 if there are r_{1},\ldots,r_{m}\in\mathbb{R} such that for all y_{1},\ldots,y_{m}\in\{0,1\} there exists f\in\mathcal{F} such that \forall i\in[m],\;\;f(\mathbf{x}_{i})\leq r_{i}-\epsilon\;\text{ if }\;y_{i}=0\;\text{ and }\;f(\mathbf{x}_{i})\geq r_{i}+\epsilon\;\text{ if }\;y_{i}=1~. The fat-shattering dimension of \mathcal{F} with margin \epsilon is the maximum cardinality m of a set of points in \mathcal{X} for which the above holds. The fat-shattering dimension of \mathcal{F} with margin \epsilon lower bounds the number of samples needed to learn \mathcal{F} within accuracy \epsilon in the distribution-free 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 m points \{\mathbf{x}_{i}\}_{i=1}^{m} where \left\|\mathbf{x}_{i}\right\|_{\infty}\leq 1 , with margin 1 , using ReLU networks of constant depth and O(m) parameters, such that for each layer j the absolute values of all weights are bounded by \frac{1}{\sqrt{d_{j-1}}} , where d_{j-1} is the width of layer j-1 . Proof. Consider input dimension d_{0}=1 . For 1\leq i\leq m , consider the points x_{i}=\frac{i}{m} , and let \{y_{i}\}_{i=1}^{m}\subseteq\{0,1\} . Consider the following one-hidden-layer ReLU network N , which satisfies N(x_{i})=\frac{y_{i}}{m} for all i . First, the network N includes a neuron with weight 0 and bias \frac{y_{1}}{m} , i.e., [0\cdot x+\frac{y_{1}}{m}]_{+} . Now, for each i such that y_{i}=0 and y_{i+1}=1 we add two neurons: [x-y_{i}]_{+}-[x-y_{i+1}]_{+} , and for i such that y_{i}=1 and y_{i+1}=0 we add -[x-y_{i}]_{+}+[x-y_{i+1}]_{+} . It is easy to verify that this construction has width at most 2m-1 and allows us to shatter m points with margin \frac{1}{2m} . However, the output weights of the neurons are \pm 1 , and thus it does not satisfy the theorem’s requirement. Consider the network N^{\prime}(x)=N(x)\cdot\frac{1}{\sqrt{2m-1}} obtained from N by modifying the output weights. The network N^{\prime} satisfies the theorem’s requirement on the weight magnitudes, and allows for shattering with margin \frac{1}{2m\sqrt{2m-1}} . We will now show how to increase this margin to 1 using a constant number of additional layers. Let \tilde{N} be a network obtained from N^{\prime} as follows. First, we add a ReLU activation to the output neuron of N^{\prime} . Since for every x_{i} we have N^{\prime}(x_{i})\geq 0 , it does not affect these outputs. Next, we add L=8 additional layers (layers 3,\ldots,3+L-1 ) of width \sqrt{m} and without bias terms, where the incoming weights to layer 3 are all 1 and the weights in layers 4,\ldots,3+L-1 are \frac{1}{m^{1/4}} . Finally, we add an output neuron (layer 3+L ) with incoming weights \frac{1}{m^{1/4}} . The network \tilde{N} satisfies the theorem’s requirements on the weight magnitudes, and it has depth 3+L=11 and O(m) parameters. Now, suppose that all neurons in a layer 3\leq j\leq 3+L-1 have values (i.e., activations) z\geq 0 , then the values of all neurons in layer j+1 are z\cdot\frac{1}{m^{1/4}}\cdot\sqrt{m}=z\cdot m^{1/4} . Hence, if the value of the neuron in layer 2 is \frac{1}{2m\sqrt{2m-1}} , then the output of the network \tilde{N} is \frac{1}{2m\sqrt{2m-1}}\cdot(m^{1/4})^{L}=\frac{m^{L/4}}{2m\sqrt{2m-1}}=\frac{m^{2}}{2m\sqrt{2m-1}}\geq 2 for large enough m . If the value of the neuron in layer 2 is 0 then the output of \tilde{N} is also 0 . Hence, this construction allow for shattering m points with margin at least 1 , using O(m) parameters and weights that satisfy the theorem’s conditions. ∎ Appendix 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 not 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] , Kang and Ramanan [32] , 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 \Omega\subset\mathbb{R}^{d} be a domain (non-empty, connected, and open). Let the drift term \mathbf{b}:\mathbb{R}^{d}\to\mathbb{R}^{d} and dispersion coefficient {\boldsymbol{\Sigma}}:\mathbb{R}^{d}\to\mathbb{R}^{d\times d} be measurable and locally bounded. We also denote the diffusion coefficient by \mathbf{A}\left(\cdot\right)={\boldsymbol{\Sigma}}\left(\cdot\right){\boldsymbol{\Sigma}}\left(\cdot\right)^{\top}=\left(a_{ij}\left(\cdot\right)\right)_{i,j=1}^{d} , and denote its columns by \mathbf{a}_{i}\left(\cdot\right) . We say that the diffusion coefficient is uniformly elliptic if there exists \sigma>0 such that \displaystyle\forall\mathbf{v}\in\mathbb{R}^{d}\,,\;\forall\mathbf{x}\in\overline{\Omega}\quad\mathbf{v}^{\top}\mathbf{A}\left(\mathbf{x}\right)\mathbf{v}>\sigma\left\|\mathbf{v}\right\|\,. (38) Let \eta be a set valued mapping of allowed reflection directions defined on \overline{\Omega} such that \eta\left(\mathbf{x}\right)=\left\{\mathbf{0}\right\} for \mathbf{x}\in\Omega , and \eta\left(\mathbf{x}\right) is a non-empty, closed and convex cone in \mathbb{R}^{d} such that \left\{\mathbf{0}\right\}\subseteq\eta\left(\mathbf{x}\right) for \mathbf{x}\in\partial\Omega , and furthermore assume that the set \left\{\left(\mathbf{x},\mathbf{v}\right)\,:\,\mathbf{x}\in\overline{\Omega},\mathbf{v}\in\eta\left(\mathbf{x}\right)\right\} is closed in \mathbb{R}^{2d} . In addition, for \mathbf{x}\in\partial\Omega let \hat{n}\left(\mathbf{x}\right) be the set of inwards normals to \Omega at \mathbf{x} , \displaystyle\hat{n}\left(\mathbf{x}\right)=\bigcup_{r>0}\,\hat{n}_{r}\left(\mathbf{x}\right)\,, \displaystyle\hat{n}_{r}\left(\mathbf{x}\right)=\left\{\mathbf{n}\in\mathbb{R}^{d}\,\mid\,\left\|\mathbf{n}\right\|=1,\,B_{r}\left(\mathbf{x}-r\mathbf{n}\right)\cap\Omega=\emptyset\right\}\,. Then, denote the set of boundary points with inward pointing cones \displaystyle\mathcal{U}\triangleq\left\{\mathbf{x}\in\partial\Omega\,\mid\,\exists\mathbf{n}\in\hat{n}\left(\mathbf{x}\right)\,:\,\forall{\boldsymbol{\eta}}\in\eta\left(\mathbf{x}\right)\;\left\langle\mathbf{n},{\boldsymbol{\eta}}\right\rangle>0\right\}\,, and let \mathcal{V}\triangleq\partial\Omega\setminus\mathcal{U} . For example, if \Omega is a convex polyhedron and \eta\left(\mathbf{x}\right) is the cone defined by the positive span of \hat{n}\left(\mathbf{x}\right) we get that \mathcal{V}=\emptyset . Throughout this section and the rest of the paper, the stochastic differential equation with reflection (SDER) in \left(\Omega,\eta\right) \displaystyle d\mathbf{x}_{t}=\mathbf{b}\left(\mathbf{x}_{t}\right)dt+{\boldsymbol{\Sigma}}\left(\mathbf{x}_{t}\right)d\mathbf{w}_{t}+d\mathbf{r}_{t}\,, (39) where \mathbf{w}_{t} is a Wiener process, and \mathbf{r}_{t} is a reflection process with respect to some filtration, is understood as in Definition 2.4 of [ 32 ] , and the submartingale problem associated with \left(\Omega,\eta\right) , \mathcal{V} , \mathbf{b} and {\boldsymbol{\Sigma}} , refers to Definition 2.9 of [ 32 ] . In addition, we use the following definition. Definition H.1 (Piecewise \mathcal{C}^{2} with continuous reflection; Definition 2.11 in [ 32 ] ) . The pair \left(\Omega,\eta\right) is said to be piecewise \mathcal{C}^{2} with continuous reflection if it satisfies the following properties: 1. \Omega is a non-empty domain in \mathbb{R}^{d} with representation \displaystyle\Omega=\bigcap_{i\in\mathcal{I}}\Omega^{i}\,, where \mathcal{I} is a finite set and for each i\in\mathcal{I} , \Omega^{i} is a non-empty domain with \mathcal{C}^{2} boundary in the sense that for each \mathbf{x}\in\partial\Omega , there exist a neighborhood \mathcal{N}\left(\mathbf{x}\right) of \mathbf{x} , and functions \varphi^{i}_{\mathbf{x}}\in\mathcal{C}^{2}\left(\mathbb{R}^{d}\right) , i\in\mathcal{I}\left(\mathbf{x}\right)=\left\{i\in\mathcal{I}\,\mid\,\mathbf{x}\in\partial\Omega^{i}\right\} , such that \displaystyle\mathcal{N}\left(\mathbf{x}\right)\cap\Omega^{i}=\left\{\mathbf{z}\in\mathcal{N}\left(\mathbf{x}\right)\,\mid\,\varphi^{i}_{\mathbf{x}}\left(\mathbf{z}\right)>0\right\}\,,\;\mathcal{N}\left(\mathbf{x}\right)\cap\partial\Omega^{i}=\left\{\mathbf{z}\in\mathcal{N}\left(\mathbf{x}\right)\,\mid\,\varphi^{i}_{\mathbf{x}}\left(\mathbf{z}\right)=0\right\}\,, and \nabla\varphi^{i}_{\mathbf{x}}\neq\mathbf{0} on \mathcal{N}\left(\mathbf{x}\right) . For each \mathbf{x}\in\partial\Omega^{i} and i\in\mathcal{I}\left(\mathbf{x}\right) , let \displaystyle\mathbf{n}^{i}\left(\mathbf{x}\right)=\frac{\nabla\varphi^{i}_{\mathbf{x}}}{\left\|\nabla\varphi^{i}_{\mathbf{x}}\right\|} denote the unit inward normal vector to \partial\Omega^{i} at \mathbf{x} . 2. The (set-valued) direction “vector field” \eta:\overline{\Omega}\to\mathbb{R}^{d} is given by \displaystyle\eta\left(\mathbf{x}\right)=\begin{cases}\left\{\mathbf{0}\right\}&\mathbf{x}\in\Omega\,,\\ \left\{\sum_{i\in\mathcal{I}\left(\mathbf{x}\right)}\alpha_{i}{\boldsymbol{\eta}}^{i}\left(\mathbf{x}\right)\,\mid\,\alpha_{i}\geq 0\,,\;i\in\mathcal{I}\left(\mathbf{x}\right)\right\}&\mathbf{x}\in\partial\Omega\,,\end{cases} (40) where for each i\in\mathcal{I} , {\boldsymbol{\eta}}^{i}\left(\cdot\right) is a continuous unit vector field defined on \partial\Omega^{i} that satisfies for all \mathbf{x}\in\partial\Omega^{i} \displaystyle\left\langle\mathbf{n}^{i}\left(\mathbf{x}\right),{\boldsymbol{\eta}}^{i}\left(\mathbf{x}\right)\right\rangle>0\,. If \eta^{i}\left(\cdot\right) is constant for every i\in\mathcal{I} , the the pair \left(\Omega,\eta\right) is said to be piecewise \mathcal{C}^{2} with constant reflection. If, in addition, \mathbf{n}^{i}\left(\cdot\right) is constant for every i\in\mathcal{I} , then the pair \left(\Omega,\eta\right) is said to be polyhedral with piecewise constant reflection. In addition, let \mathcal{S} denote the smooth parts of \partial\Omega . Remark H.2 . It is clear from the definition that if \Omega is polyhedral, i.e. if all \Omega^{i} ’s are half-spaces, and \eta consists of inward normal reflections, then \left(\Omega,\eta\right) is polyhedral with piecewise constant reflection. Theorem H.3 (Theorem 3 in [ 31 ] , simplified) . Suppose that the pair \left(\Omega,\eta\right) is piecewise \mathcal{C}^{2} with continuous reflection, for all i\in\mathcal{I} and \mathbf{x}\in\partial\Omega^{i} , \left\langle\mathbf{n}^{i}\left(\mathbf{x}\right),{\boldsymbol{\eta}}^{i}\left(\mathbf{x}\right)\right\rangle=1 , \mathcal{V}=\emptyset , \mathbf{b}\left(\cdot\right)\in\mathcal{C}^{1}\left(\overline{\Omega}\right) and \mathbf{A}\in\mathcal{C}^{2}\left(\overline{\Omega}\right) (elementwise), and the submartingale problem associated with \left(\Omega,\eta\right) and \mathcal{V} is well posed. Furthermore, suppose there exists a nonnegative function p\in\mathcal{C}^{2}\left(\overline{\Omega}\right) with Z_{p}=\int_{\overline{\Omega}}p\left(\mathbf{x}\right)d\mathbf{x}<\infty that solves the PDE defined by the following three relations: 1. For \mathbf{x}\in\Omega : \displaystyle 0=\frac{1}{2}\sum_{i,j=1}^{d}\frac{\partial^{2}}{\partial x_{i}\partial x_{j}}\left(a_{ij}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)-\sum_{i=1}^{d}\frac{\partial}{\partial x_{i}}\left(b_{i}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)\,. (41) 2. For each i\in\mathcal{I} and \mathbf{x}\in\partial\Omega\cap\mathcal{S} , \displaystyle 0=-2p\left(\mathbf{x}\right)\left\langle\mathbf{n}^{i}\left(\mathbf{x}\right),\mathbf{b}\left(\mathbf{x}\right)\right\rangle+\mathbf{n}^{i}\left(\mathbf{x}\right)^{\top}\mathbf{A}\left(\mathbf{x}\right)\nabla p\left(\mathbf{x}\right)-\nabla\cdot\left(p\left(\mathbf{x}\right)\mathbf{q}^{i}\left(\mathbf{x}\right)\right)+p\left(\mathbf{x}\right)K_{i}\left(\mathbf{x}\right)\,, (42) where \displaystyle\mathbf{q}^{i}\left(\mathbf{x}\right)\triangleq\mathbf{n}^{i}\left(\mathbf{x}\right)^{\top}\mathbf{A}\left(\mathbf{x}\right)\mathbf{n}^{i}\left(\mathbf{x}\right){\boldsymbol{\eta}}^{i}\left(\mathbf{x}\right)-\mathbf{A}\left(\mathbf{x}\right)\mathbf{n}^{i}\left(\mathbf{x}\right) and \displaystyle K_{i}\left(\mathbf{x}\right)\triangleq\left\langle\mathbf{n}^{i}\left(\mathbf{x}\right),\nabla\cdot\mathbf{A}\left(\mathbf{x}\right)\right\rangle=\sum_{k=1}^{d}n^{i}\left(\mathbf{x}\right)_{k}\sum_{j=1}^{d}\frac{\partial a_{kj}}{\partial x_{j}}\left(\mathbf{x}\right)\,. 3. For each i,j\in\mathcal{I} , i\neq j , and \mathbf{x}\in\partial\Omega^{i}\cap\partial\Omega^{j}\cap\partial\Omega , \displaystyle p\left(\mathbf{x}\right)\left(\left\langle\mathbf{q}^{i}\left(\mathbf{x}\right),\mathbf{n}^{j}\left(\mathbf{x}\right)\right\rangle+\left\langle\mathbf{q}^{j}\left(\mathbf{x}\right),\mathbf{n}^{i}\left(\mathbf{x}\right)\right\rangle\right)=0\,. (43) Then the probability measure on \overline{\Omega} defined by \displaystyle p_{\infty}\left(A\right)\triangleq\frac{1}{Z_{p}}\intop_{A}p\left(\mathbf{x}\right)d\mathbf{x}\,,\quad A\in\mathcal{B}\left(\overline{\Omega}\right)\,, (44) is a stationary distribution for the well-posed submartingale problem. We are now ready to state a characterization of stationary distributions of ( 39 ). Note that for simplicity, we do not maintain full generality. Corollary H.4 (Stationary distribution of weak solutions to SDERs) . Suppose that, \Omega is convex and bounded, \mathbf{b}\in\mathcal{C}^{1}\left(\overline{\Omega}\right) and \mathbf{A}\in\mathcal{C}^{2}\left(\overline{\Omega}\right) , \left(\Omega,\eta\right) is piecewise \mathcal{C}^{2} with continuous reflection, \mathbf{A} is uniformly elliptic (see ( 38 )), and \mathcal{V}=\emptyset . Then p\in\mathcal{C}^{2} satisfying the conditions in Theorem H.3 defines a stationary distribution for ( 39 ). Proof. Assumptions compactness of the domain, and continuous differentiability 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 a unique strong solution to the SDER ( 39 ). Then, piecewise \mathcal{C}^{2} with continuous reflection, the uniform ellipticity assumption, Theorems 1 and 3 of [ 32 ] , and Theorem H.3 imply that if there exists p\in\mathcal{C}^{2} satisfying ( 41 )-( 43 ), then ( 44 ) is 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 a box We proceed to assume that the diffusion term is a scalar matrix of the form \mathbf{A}\left(\mathbf{x}\right)=2\sigma^{2}\left(\mathbf{x}\right)\mathbf{I}_{d} , and that \Omega is a bounded box in \mathbb{R}^{d} , i.e. there exist \left\{m_{i}m_{i}\right\}\,,\;\Omega^{i}_{M}\triangleq\left\{\mathbf{x}\in\mathbb{R}^{d}\,\mid\,x_{i}0 such that for all \mathbf{x}\in\overline{\Omega} , \sigma^{2}\left(\mathbf{x}\right)>\sigma^{2} . If there exists p\in\mathcal{C}^{2} such that \displaystyle\begin{cases}0=\nabla\cdot\left(\nabla\left(\sigma^{2}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)-\mathbf{b}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)&\mathbf{x}\in\Omega\,,\\ 0=\left\langle\nabla\left(\sigma^{2}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)-\mathbf{b}\left(\mathbf{x}\right)p\left(\mathbf{x}\right),\mathbf{n}\left(\mathbf{x}\right)\right\rangle&\mathbf{x}\in\partial\Omega\,,\end{cases} (48) and \int_{\overline{\Omega}}p\left(\mathbf{x}\right)d\mathbf{x}=1 , then p is a stationary distribution of \displaystyle d\mathbf{x}_{t}=\mathbf{b}\left(\mathbf{x}_{t}\right)dt+\sqrt{2\sigma^{2}\left(\mathbf{x}_{t}\right)}d\mathbf{w}_{t}+d\mathbf{r}_{t} (49) in \Omega . Remark H.6 . ( 48 ) is exactly the stationarity condition derived from the Fokker-Planck 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 \displaystyle 0 \displaystyle=\frac{1}{2}\sum_{i,j=1}^{d}\frac{\partial^{2}}{\partial x_{i}\partial x_{j}}\left(a_{ij}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)-\sum_{i=1}^{d}\frac{\partial}{\partial x_{i}}\left(b_{i}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right) \displaystyle=\frac{1}{2}\sum_{i=1}^{d}\frac{\partial^{2}}{\partial x_{i}^{2}}\left(2\sigma^{2}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)-\sum_{i=1}^{d}\frac{\partial}{\partial x_{i}}\left(b_{i}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right) \displaystyle=\nabla\cdot\left(\nabla\left(\sigma^{2}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)-\mathbf{b}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)\,. Next, we can considerably simplify the boundary conditions. First, notice that \mathcal{S} consists of the interior of the domain’s faces so for \mathbf{x}\in\partial\Omega\cap\mathcal{S} , the set of active boundary regions \mathcal{I}\left(\mathbf{x}\right) is a singleton \mathcal{I}\left(\mathbf{x}\right)=\left\{\left(i,s\right)\right\} , for some i=1,\dots,d and s\in\left\{m,M\right\} . We focus on the lower boundaries ( m ), as the conditions for the upper boundaries are symmetric. For i=1,\dots,d and \mathbf{x}\in\partial\Omega\cap\mathcal{S} , {\boldsymbol{\eta}}^{i}_{m}\left(\mathbf{x}\right)=\mathbf{n}^{i}_{m}\left(\mathbf{x}\right)=\mathbf{e}_{i} so \displaystyle\mathbf{q}^{i}_{m}\left(\mathbf{x}\right) \displaystyle=\mathbf{n}^{i}_{m}\left(\mathbf{x}\right)^{\top}\mathbf{A}\left(\mathbf{x}\right)\mathbf{n}^{i}_{m}\left(\mathbf{x}\right){\boldsymbol{\eta}}^{i}_{m}\left(\mathbf{x}\right)-\mathbf{A}\left(\mathbf{x}\right)\mathbf{n}^{i}_{m}\left(\mathbf{x}\right) \displaystyle=\sigma^{2}\left(\mathbf{x}\right)\left(\mathbf{e}_{i}^{\top}\mathbf{I}_{d}\mathbf{e}_{i}\right)\mathbf{e}_{i}-\sigma^{2}\left(\mathbf{x}\right)\mathbf{I}_{d}\mathbf{e}_{i} \displaystyle=\mathbf{0}\,, so ( 43 ) is satisfied. In addition, \displaystyle K^{i}_{m}\left(\mathbf{x}\right)=\nabla\cdot\mathbf{a}_{i}\left(\mathbf{x}\right)=\frac{\partial}{\partial x_{i}}\sigma^{2}\left(\mathbf{x}\right)\,, so ( 42 ) becomes, for all i=1,\dots,d , \displaystyle 0 \displaystyle=-2p\left(\mathbf{x}\right)\left\langle\mathbf{n}^{i}_{m}\left(\mathbf{x}\right),\mathbf{b}\left(\mathbf{x}\right)\right\rangle+\mathbf{n}^{i}_{m}\left(\mathbf{x}\right)^{\top}\mathbf{A}\left(\mathbf{x}\right)\nabla p\left(\mathbf{x}\right)-\nabla\cdot\left(p\left(\mathbf{x}\right)\mathbf{q}^{i}_{m}\left(\mathbf{x}\right)\right)+p\left(\mathbf{x}\right)K^{i}_{m}\left(\mathbf{x}\right) \displaystyle 0 \displaystyle=-2p\left(\mathbf{x}\right)b_{i}\left(\mathbf{x}\right)+\mathbf{a}_{i}^{\top}\nabla p\left(\mathbf{x}\right)+p\left(\mathbf{x}\right)\frac{\partial}{\partial x_{i}}\sigma^{2}\left(\mathbf{x}\right) \displaystyle 0 \displaystyle=-2p\left(\mathbf{x}\right)b_{i}\left(\mathbf{x}\right)+\sigma^{2}\left(\mathbf{x}\right)\frac{\partial}{\partial x_{i}}p\left(\mathbf{x}\right)+p\left(\mathbf{x}\right)\frac{\partial}{\partial x_{i}}\sigma^{2}\left(\mathbf{x}\right)\,, which is \displaystyle 0 \displaystyle=-p\left(\mathbf{x}\right)b_{i}\left(\mathbf{x}\right)+\frac{1}{2}\frac{\partial}{\partial x_{i}}\left(p\left(\mathbf{x}\right)\sigma^{2}\left(\mathbf{x}\right)\right) \displaystyle=\left\langle\nabla\left(\sigma^{2}\left(\mathbf{x}\right)p\left(\mathbf{x}\right)\right)-\mathbf{b}\left(\mathbf{x}\right)p\left(\mathbf{x}\right),\mathbf{n}\left(\mathbf{x}\right)\right\rangle\,. ∎ H.2.1 Reflected Langevin dynamics in a box In this section, we derive some useful properties of the SDER \displaystyle d\mathbf{x}_{t}=-\nabla L\left(\mathbf{x}_{t}\right)+\sqrt{2\beta^{-1}\sigma^{2}\left(\mathbf{x}_{t}\right)}d\mathbf{w}_{t}+d\mathbf{r}_{t}\,, (50) in a box domain as defined in ( 45 )-( 47 ), where L\geq 0 is some (loss/potential) function, and \beta>0 is an inverse temperature parameter. First, we characterize the stationary distribution of this process. Recall Lemma D.1 . If L,\sigma^{2}\in\mathcal{C}^{2} , \sigma^{2}\left(\cdot\right)>0 is uniformly bounded away from 0 in \overline{\Omega} , \displaystyle Z=\intop_{\overline{\Omega}}\frac{1}{\sigma^{2}\left(\mathbf{x}\right)}\exp\left(-\beta\intop\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}d\mathbf{x}\right)<\infty\,, the integrals exist, and the field \nabla L/\sigma^{2} is conservative (curl-free), then \displaystyle p_{\infty}\left(\mathbf{x}\right)=\frac{1}{Z}\frac{1}{\sigma^{2}\left(\mathbf{x}\right)}\exp\left(-\beta\intop\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}d\mathbf{x}\right)\, (51) is a stationary distribution of ( 50 ). Proof. The drift term in this setting is \mathbf{b}=-\beta\nabla L . Therefore, from Lemma H.5 , we get that any distribution that satisfies \displaystyle 0=\nabla\left(\sigma^{2}\left(\mathbf{x}\right)p_{\infty}\left(\mathbf{x}\right)\right)+\beta p_{\infty}\left(\mathbf{x}\right)\nabla L\left(\mathbf{x}\right) on \overline{\Omega} , is a stationary distribution. We can solve this PDE as \displaystyle 0 \displaystyle=\beta\nabla L\left(\mathbf{x}\right)p_{\infty}\left(\mathbf{x}\right)+p_{\infty}\left(\mathbf{x}\right)\nabla\sigma^{2}\left(\mathbf{x}\right)+\sigma^{2}\left(\mathbf{x}\right)\nabla p_{\infty}\left(\mathbf{x}\right) \displaystyle=p_{\infty}\left(\mathbf{x}\right)\left(\beta\nabla L\left(\mathbf{x}\right)+\nabla\sigma^{2}\left(\mathbf{x}\right)\right)+\sigma^{2}\left(\mathbf{x}\right)\nabla p_{\infty}\left(\mathbf{x}\right) -\sigma^{2}\left(\mathbf{x}\right)\nabla p_{\infty}\left(\mathbf{x}\right)=p_{\infty}\left(\mathbf{x}\right)\left(\beta\nabla L\left(\mathbf{x}\right)+\nabla\sigma^{2}\left(\mathbf{x}\right)\right) \frac{\nabla p_{\infty}}{p_{\infty}}=-\frac{\beta\nabla L+\nabla\sigma^{2}}{\sigma^{2}} \nabla\ln p_{\infty}=-\frac{\beta\nabla L}{\sigma^{2}}-\nabla\ln\sigma^{2} \nabla\ln\left(p_{\infty}\cdot\sigma^{2}\right)=-\frac{\beta\nabla L}{\sigma^{2}}\,. Then, \ln\left(p_{\infty}\cdot\sigma^{2}\right)=-\beta\intop\frac{\nabla L}{\sigma^{2}}+C where we used the assumption that the integral on the RHS exists, and is well defined. Hence p_{\infty}\left(\mathbf{x}\right)\propto\frac{1}{\sigma^{2}\left(\mathbf{x}\right)}\exp\left(-\beta\intop\frac{\nabla L\left(\mathbf{x}\right)}{\sigma^{2}\left(\mathbf{x}\right)}d\mathbf{x}\right)\,. ∎ When the integral in ( 51 ) is solvable, we can find an explicit expression for the stationary distribution, as was done in Section D.1 .