PaperlayerView exact revision on arXiv

Source-linked AI summary

Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets

Benjamin Dupuis, Paul Viallard, George Deligiannidis, Umut Simsekli

arXiv:2404.17442v2stat.MLcs.LG

TL;DR

The paper addresses the difficulty of obtaining useful uniform generalization bounds when the hypothesis set depends on the training data. It extends PAC-Bayesian analysis to random hypothesis sets and applies the framework to fractal dimensions and Langevin trajectories, obtaining tighter unified fractal bounds and uniform CLD and SGLD guarantees.

  • Problem

    Fixed-set uniform bounds may be vacuous, while existing data-dependent fractal bounds use disparate information-theoretic terms and restrictive assumptions.

    Source: §1 · p. 3, §1.1.1 · p. 4

  • Method

    The paper formalizes PAC-Bayesian theory for random hypothesis sets generated by stochastic learning algorithms and derives data-dependent uniform bounds.

    Source: §1.2 · pp. 5–6

  • Results

    The framework yields tighter, unified fractal-dimension bounds, improves one rate from n^-1/3 to n^-1/2, and provides uniform bounds over CLD and SGLD trajectories.

    Source: §1.2 · p. 7

  • Takeaways & Limitations

    The results provide a single proof framework for data-dependent uniform bounds and guarantees that cover entire noisy optimization trajectories rather than only final iterates.

    Source: §1.1.2 · p. 4, §1.2 · pp. 5, 7

    The Euclidean-based fractal-dimension theorem has an advantage because its bound may hold under weaker assumptions.

    Source: §5.3 · p. 24

Abstract

from arXiv · show

We propose data-dependent uniform generalization bounds by approaching the problem from a PAC-Bayesian perspective. We first apply the PAC-Bayesian framework on "random sets" in a rigorous way, where the training algorithm is assumed to output a data-dependent hypothesis set after observing the training data. This approach allows us to prove data-dependent bounds, which can be applicable in numerous contexts. To highlight the power of our approach, we consider two main applications. First, we propose a PAC-Bayesian formulation of the recently developed fractal-dimension-based generalization bounds. The derived results are shown to be tighter and they unify the existing results around one simple proof technique. Second, we prove uniform bounds over the trajectories of continuous Langevin dynamics and stochastic gradient Langevin dynamics. These results provide novel information about the generalization properties of noisy algorithms.

1 Introduction

The paper develops data-dependent uniform generalization bounds by extending PAC-Bayesian analysis to random hypothesis sets, addressing limitations of fixed-set bounds. It applies this framework to fractal dimensions and Langevin trajectories, yielding unified, tighter, and trajectory-uniform results.

1.1 Motivation

  • Fixed hypothesis-set bounds can be vacuous for modern over-parameterized models, motivating data-dependent sets that reflect the training dataset and algorithm.Such sets may consist of empirical-risk minimizers or optimization trajectories.Source: §1 · pp. 2–3

1.1.1 Fractal-based generalization bounds

  • Existing fractal-dimension bounds use differing, often difficult-to-compute information-theoretic terms and may require intricate geometric stability assumptions.The paper targets a unified framework with the correct n-dependence without additional non-trivial assumptions.Source: §1.1.1 · pp. 3–4, §1.1 · p. 3

1.1.2 Langevin dynamics

  • Uniform trajectory bounds for Langevin methods provide guarantees regardless of stopping time, unlike last-iterate bounds that do not generally cover data-dependent stopping times.Near a local minimum, trajectory-wide bounds can also capture geometric and statistical properties that last-iterate bounds miss.Source: §1.1.2 · pp. 4–5

1.2 Contributions and Overview of Main Results

  • The paper rigorously formalizes PAC-Bayesian theory for random hypothesis sets generated by stochastic algorithms and derives uniform upper bounds involving complexity and information-theoretic terms.The framework also naturally supports data-dependent uniform lower bounds.Source: §1.2 · pp. 5–6
  • The fractal-dimension application uses the same information-theoretic terms and proof technique across dimension notions, producing tighter bounds and improving the convergence rate from n^-1/3 to n^-1/2 relative to Dupuis et al. (2023, Theorem 3.8).The data-dependent-dimension result removes that work’s stability assumption.Source: §1.1.1 · p. 4, §1.2 · p. 7
  • The framework yields uniform generalization bounds over continuous and stochastic Langevin trajectories, including the first such CLD bounds and an SGLD result whose expectation is outside the trajectory maximum.For CLD, the bounds relate uniform error to the average empirical-risk gradient norm; the SGLD result is not a trivial consequence of existing last-iterate results.Source: §1.1.2 · p. 5, §1.2 · p. 7
  • For CLD, the results provide uniform generalization bounds over trajectories, relating the uniform generalization error to the average gradient norm of the empirical risk along the random trajectory.Source: §1.2 · p. 7

1.3 Organization of the paper

  • The paper is organized around general PAC-Bayesian and Rademacher foundations, followed by random-set theory and applications to fractal bounds, CLD, and SGLD.Main-result proofs are provided in Appendix B.Source: §1.3 · p. 8

2 Preliminaries

This section introduces notation for risks, datasets, hypothesis sets, and data dependence, then reviews fixed-set uniform bounds and PAC-Bayesian bounds. It emphasizes that classical symmetrization fails for data-dependent sets, motivating the random-set framework.

2.1 Notations

  • The preliminaries define population risk, empirical risk, generalization error, hypothesis sets, data-dependent sets, and Markov kernels used throughout the paper.Probability measures over parameter vectors are denoted by (P, QS), while distributions over sets are denoted by (π, ρS).Source: §2 · p. 8, §2.1 · p. 9

2.2 Uniform generalization bounds with data-independent hypothesis sets

  • Rademacher complexity provides high-probability uniform generalization bounds for fixed hypothesis sets under bounded losses.The empirical Rademacher complexity is defined using independent Rademacher variables.Source: §2.2 · p. 9
  • The symmetrization lemma underlying fixed-set Rademacher bounds does not hold for data-dependent hypothesis sets, limiting the direct use of classical techniques.The paper later addresses this bottleneck using PAC-Bayesian theory and data-dependent Rademacher complexities.Source: §2.2 · p. 10

2.3 Background on PAC-Bayesian bounds

  • PAC-Bayesian bounds control expected generalization gaps for data-dependent posteriors through a data-independent prior, a posterior, and a KL-divergence term.The posterior QS is learned from the sample, while the prior P does not depend on it; the framework assumes absolute continuity QS ≪ P.Source: §2.3 · pp. 10–11
  • Disintegrated PAC-Bayesian bounds replace the posterior expectation with a pointwise upper bound involving a log Radon–Nikodym derivative.The result retains the same general mechanism of instantiating a function φ and controlling its rightmost term, under absolute continuity.Source: §2.3 · p. 11

3 PAC-Bayesian Theory on Random Sets

The paper extends PAC-Bayesian theory from randomized hypotheses to data-dependent random hypothesis sets. It provides both a measurable-space formulation and a random-closed-set construction that supports supremum-based generalization bounds.

3 PAC-Bayesian Theory on Random Sets

  • The central contribution is a PAC-Bayesian framework that treats a learning algorithm as generating a data-dependent probability distribution over hypothesis sets.The framework replaces random hypotheses w with random sets W and uses a measurable space of possible sets.Source: §3 · p. 12, §3.1 · p. 12

3.1 Random set formalization

  • The framework covers singleton distributions, stochastic-gradient trajectories, and stochastic differential equations as random-set examples.For stochastic dynamics, the posterior describes the distribution of sets formed by the trajectory over a fixed time horizon.Source: §3.1 · p. 12
  • Using a supremum function yields worst-case generalization bounds over data-dependent hypothesis sets, with information-theoretic terms measuring posterior–prior deviation.The relevant terms include KL(ρS∥π) and a disintegrated relative-entropy-like Radon–Nikodym term; the framework can also support data-dependent Rademacher complexity and lower bounds.Source: §3.1 · pp. 13–14
  • The random-set bounds extend classical and disintegrated PAC-Bayesian results by applying them to a measurable function Φ of a hypothesis set and dataset.The prior π is data-independent, the posterior family ρS is a Markov kernel, and absolute continuity ρS ≪ π is required.Source: §3.1 · pp. 12–13

3.2 More detailed measure-theoretic construction

  • The measure-theoretic construction restricts attention to random closed sets and uses the Effrös σ-algebra to ensure measurability.When the loss is continuous in w, considering only closed sets causes no loss of generality; the supremum of continuous stochastic processes is measurable.Source: §3.2 · pp. 14–15
  • For random closed sets, the supremum of the generalization error and analogous Rademacher-complexity terms is measurable under the constructed σ-algebra.This supplies the measurability conditions needed to apply the random-set PAC-Bayesian theory.Source: §3.2 · p. 15

4 Uniform Generalization Bounds with Data-dependent Hypothesis Sets

The paper develops PAC-Bayesian uniform bounds for hypothesis sets that depend on the training data, using a common framework with shared information-theoretic terms. It derives Rademacher-complexity upper bounds, a general recipe for set-dependent bounds, and a novel data-dependent lower bound.

4 Uniform Generalization Bounds with Data-dependent Hypothesis Sets

  • The framework proves three bounds: a moment-generating Rademacher bound, a data-dependent Rademacher-complexity bound, and a data-dependent uniform lower bound.All bounds use the same interpretable information-theoretic terms and apply across varied settings.Source: §4 · p. 16

4.1 Warm-up: a first bound with the moment generating Rademacher function

  • The warm-up PAC-Bayesian bound controls worst-case generalization error through the moment-generating function of Rademacher complexity and does not require bounded loss.Its parameter λ>0 can be optimized, but the prior expectation can prevent genuinely data-dependent complexity terms.Source: §4.1 · pp. 16–17

4.2 Generalization bounds with data-dependent Rademacher complexity

  • The main upper bound uses Rademacher complexity of a hypothesis set W drawn from the data-dependent posterior ρS, without requiring hypothesis-set stability assumptions.Its information-theoretic terms match those of the broader framework, while RadS(W) depends explicitly on the training dataset.Source: §4.2 · pp. 17–18
  • The general recipe extends PAC-Bayesian analysis to measurable set-dependent functionals under subgaussian fluctuations, with McDiarmid’s inequality supplying the condition here.Bernstein-type extensions could remove bounded-loss assumptions but would introduce variance terms.Source: §4.2 · p. 19

4.3 Data-dependent generalization lower bounds

  • The framework yields a data-dependent uniform lower bound based on desymmetrization, presented as a result not previously derived in this form.The lower bound controls the supremum absolute generalization gap over the random hypothesis set.Source: §4.3 · pp. 19–20

5 Fractal-Dimension-Based Data-Dependent Generalization Bounds

The paper applies its random-set PAC-Bayesian framework to fractal-dimension generalization bounds using data-dependent covering arguments. It obtains tighter information-theoretic terms, improves the data-dependent fractal rate, and derives Euclidean- and data-dependent variants through one proof technique.

5.1 Covering numbers and fractal dimensions

  • The framework extends covering arguments to data-dependent hypothesis sets, adding information-theoretic terms to the resulting fractal-dimension bounds.It treats both data-dependent pseudometric dimensions and Euclidean-based dimensions.Source: §5 · p. 20, §5.1 · pp. 21–22

5.2 Bounds with data-dependent fractal dimensions

  • The data-dependent fractal bound vanishes as n^-1/2, compared with order n^-2α/3 for Dupuis et al. (2023), under a uniform-in-n convergence assumption.The result has more explicit n-dependence and uses a simpler assumption than the prior geometric-stability condition.Source: §5.2 · pp. 22–23

5.3 Bounds with Euclidean-based fractal dimensions

  • The Euclidean-based bound extends Şim̧sekli et al. (2020, Theorem 2) with simpler information-theoretic terms and weaker geometric assumptions.It instead assumes an L-Lipschitz loss and posterior convergence to a data-independent distribution, while its bound may hold under weaker assumptions than the data-dependent variant.Source: §5.3 · pp. 23–24
  • Both fractal-dimension theorems follow from the same data-dependent Rademacher bound, unlike prior results that rely on different proof techniques.This unifies the existing fractal-based generalization results within the proposed framework.Source: §5.3 · p. 23, §5.4 · p. 25

5.4 Comparison of the information-theoretic terms and prior optimization

  • Optimizing the PAC-Bayesian prior yields information-theoretic terms smaller than those in existing fractal bounds, producing tighter guarantees.The comparison identifies the optimized prior with the marginal distribution of the random hypothesis set and relates expected KL divergence to mutual information.Source: §5.4 · pp. 24–25

6 Application to Langevin Dynamics

The paper applies its PAC-Bayesian random-set framework to continuous Langevin dynamics, obtaining uniform generalization bounds over entire trajectories. The derivation combines measure-theoretic random-set posteriors, Girsanov-based KL expressions, and Rademacher-complexity bounds under Lipschitz assumptions.

6.2 Expression of the KL divergence

  • Girsanov’s theorem yields analytic expressions for the KL divergence between the empirical-dynamics path measure and data-independent SDE priors.The paper considers Brownian and expected-dynamics priors, with the latter potentially tightening bounds under suitable conditions.Source: §6 · p. 25, §6.2 · p. 26

6.1 The setting

  • The framework treats a Langevin trajectory as a data-dependent random hypothesis set on an underlying probability space, ensuring the relevant quantities are measurable.The prior and posterior are defined directly on Ω, with equivalent measures inducing a complete probability-space structure.Source: §6.1 · pp. 25–26

6.2.1 Brownian prior

  • For the Brownian prior, the resulting bound requires no ℓ2-regularization, unlike several prior Langevin generalization bounds.The bound is stated under differentiability, smoothness, and Lipschitz assumptions, with its Rademacher term bounded separately.Source: §6.2.1 · p. 27

6.2.2 Expected dynamics prior

  • The expected-dynamics prior produces a KL integrand with generalization-term structure that may decrease as n grows, potentially improving the convergence order.The paper bounds this KL term and optimizes λ to obtain the corresponding result.Source: §6.2.2 · p. 27

6.3 Rademacher complexity of Langevin dynamics

  • Under Lipschitz losses, the paper bounds the trajectory’s Rademacher complexity and obtains fully computable uniform bounds over [0,T].The information-theoretic terms dominate the Rademacher term; unlike some time-at-T results, the bound has no exponential time decay and requires no convexity, dissipativity, or regularization.Source: §6.3 · p. 28
  • The PAC-Bayesian trajectory bounds differ from martingale bounds because posterior integration corresponds to expectation over algorithmic randomness and may yield a larger worst-case quantity.The comparison concerns the distinction between uniform trajectory control and bounds on expectations over the algorithm’s randomness.Source: §6.3 · p. 29

7 Uniform Generalization Bounds for SGLD

The paper extends its random-set PAC-Bayesian analysis to stochastic gradient Langevin dynamics. It derives a uniform generalization bound over the discrete trajectory and compares its time dependence and assumptions with prior results.

7 Uniform Generalization Bounds for SGLD

  • The SGLD result is obtained by extending the continuous Langevin argument to discrete updates and explicitly bounding the KL term in the PAC-Bayesian theorem.The derivation uses the Rademacher moment-generating-function bound and accounts for both gradient-estimation and Gaussian-noise randomness.Source: §7 · p. 29
  • The SGLD theorem controls the trajectory uniformly with high probability over the sample, while averaging over the algorithm’s gradient and Gaussian-noise randomness.The posterior expectation can be interpreted as an expectation over the algorithmic randomness.Source: §7 · p. 29
  • The proof requires a technical integrability assumption, satisfied for uniformly bounded gradients and, for minibatch-average gradients, by Lipschitz losses.The paper then optimizes λ in the bounded-gradient case to obtain a simplified bound.Source: §7 · p. 29
  • Unlike comparable results with exponential decay, the SGLD bound has no exponential time decay because it is uniform over the whole trajectory.Its order is comparable in the Lipschitz case to results by Negrea et al. (2019) and Neu et al. (2021), but the method assumes bounded loss rather than merely subgaussian loss.Source: §7 · p. 30

Conclusion

The paper concludes that PAC-Bayesian analysis on random sets yields data-dependent uniform bounds, tighter fractal-dimension results, and the first uniform trajectory bounds for Langevin dynamics and SGLD. The appendices supply measure-theoretic definitions, concentration tools, symmetrization results, and omitted proofs.

Conclusion

  • The proposed PAC-Bayesian random-set framework gives data-dependent uniform upper bounds, lower bounds, and applications to fractal dimensions and noisy optimization trajectories.For fractal dimensions, it yields tighter bounds, uses one information-theoretic term across dimension notions, and simplifies existing proofs.Source: Conclusion · p. 30
  • For continuous Langevin dynamics and SGLD, the framework converts information-theoretic terms into closed-form quantities and proves uniform bounds over algorithm trajectories.The conclusion identifies these as the first uniform generalization bounds over the trajectories of these algorithms.Source: Conclusion · p. 30
  • Future work includes weakening assumptions, improving Langevin time dependence, extending the framework with alternative concentration and PAC-Bayesian tools, and optimizing the random-set posterior.The paper also points to further links between generalization and topological data analysis.Source: Conclusion · p. 30

Appendix A. Additional Technical Background

  • The appendices define absolute continuity, KL divergence, probability laws, mutual information, and completeness for the measure-theoretic setup.They also record standard concentration and measure-theoretic results, including McDiarmid’s inequality in exponential form and Egoroff’s theorem.Source: Appendix A · p. 32, §A.1 · p. 32, §A.2 · pp. 32–33

A.2 A few technical lemmas

  • The technical appendices establish bounded-difference, symmetrization, desymmetrization, and exponential-symmetrization lemmas used in the main PAC-Bayesian proofs.They then apply these lemmas to the Rademacher MGF and related bounds, with omitted proofs supplied for the main results.Source: §A.2 · pp. 32–33

B.1.1 Omitted proofs of Section 4.1 - Rademacher MGF

The omitted proofs derive the Rademacher MGF and related PAC-Bayesian bounds through exponential symmetrization, independence under the prior, bounded differences, and classical symmetrization. These arguments establish the stated inequalities under the paper’s measurability and bounded-loss assumptions.

B.1.1 Omitted proofs of Section 4.1 - Rademacher MGF

  • The Rademacher MGF proof uses an exponential symmetrization lemma, Jensen’s inequality, Rademacher variables, and Cauchy–Schwarz to control the relevant exponential term.The proof applies Theorem 6 with a supremum-based test function and then invokes Fubini’s theorem.Source: §B.1.1 · pp. 33–34
  • Measurability of the quantities inside the expectations is required before the exponential-symmetrization inequality can be applied.This condition is stated explicitly alongside the lemma used in the proof.Source: §B.1.1 · p. 33

B.1.2 Omitted proofs of Section 4.2

  • The desired PAC-Bayesian inequalities follow directly after the preceding estimates, and Theorem 13 uses the same proof pattern with a modified test function.For Theorem 13, the bounded-difference condition follows through the inverted triangular inequality.Source: §B.1.2 · p. 36

B.2 Data-dependent uniform generalization bounds with IPMs

The paper extends its PAC-Bayesian framework for data-dependent random hypothesis sets to integral probability metrics and connects the resulting bounds to covering-number and fractal-dimension analyses.

B.2 Data-dependent uniform generalization bounds with IPMs

  • The framework is extended to IPMs, yielding PAC-Bayesian bounds for data-dependent random hypothesis sets under measurability and boundedness conditions.The extension uses a family of bounded measurable functions and a data-dependent function Φ.Source: §B.2 · p. 36
  • The IPM result is obtained by applying the IPM definition, Jensen’s inequality, Markov’s inequality, and logarithmic rearrangement.Source: §B.2 · pp. 36–37
  • The resulting corollary specializes the general IPM theorem to the function Φλ appearing in the paper’s main PAC-Bayesian framework.Source: §B.2 · p. 37

B.3 Fractal based generalization bounds - Omitted proofs of Section 5

  • The fractal-based analysis first derives generalization bounds involving data-dependent covering numbers, from which the fractal-dimension bounds are subsequently obtained.Source: §B.3 · p. 37

B.3.1 Data-dependent covering numbers

The paper derives two data-dependent covering bounds from its Rademacher-complexity result, using a sample-dependent pseudometric and, under additional regularity, the Euclidean metric.

B.3.1 Data-dependent covering numbers

  • The first covering bound uses the data-dependent pseudometric ϑS and follows from Theorem 11 together with Massart’s lemma.Source: §B.3.1 · p. 37
  • Euclidean covering bounds require the loss ℓ to be Lipschitz in w and the random hypothesis set W to be π-almost surely bounded.Source: §B.3.1 · pp. 37–38
  • The Euclidean covering result is stated under Assumptions 1–3 and introduces a constant C together with probability and tuning-parameter conditions.Source: §B.3.1 · p. 38
  • Two types of covering bounds are deduced from the data-dependent Rademacher-complexity bound and then used to derive fractal-based generalization bounds.Source: §B.3.1 · p. 38

B.3.2 Proof of Theorem 16

The omitted proofs establish fractal-dimension results by controlling sample-size-dependent covering quantities and by combining convergence assumptions with covering bounds and union bounds.

B.3.2 Proof of Theorem 16

  • Theorem 16 uses an assumption ensuring convergence in probability is uniform in the sample size n, which controls the sample dependence of the covering-number limit.Source: §B.3.2 · p. 38
  • The proof of Theorem 16 selects δn = 1/n and combines the resulting bounds with a union bound and Corollary 32.Source: §B.3.2 · p. 38

B.3.3 Proof of Theorem 17

  • The arguments rely on measurability of the relevant mappings and on convergence properties under the joint law of the dataset and data-dependent posterior.Source: §B.3.3 · pp. 39–40
  • Theorem 17 assumes posterior distributions converge in total variation to a limiting distribution on hypothesis sets, without requiring that limit to equal the prior.Source: §B.3.3 · p. 39
  • Its proof applies Egoroff’s theorem to obtain uniform convergence on a high-probability subset, then combines this with Corollary 33 and a union bound.Source: §B.3.3 · pp. 39–40

B.3.4 Proof of Lemma 19

  • The proof of Lemma 19 introduces an infinite Rényi divergence and concludes by taking an essential supremum under the joint distribution of S and ρS.Source: §B.3.4 · p. 40

B.4.1 Expression of the KL divergence - omitted proofs of Section 6

The omitted proofs express the KL divergence for Langevin dynamics through a change of measure, using Girsanov’s theorem to relate a prior diffusion to a data-dependent posterior process.

B.4.1 Expression of the KL divergence - omitted proofs of Section 6

  • Under boundedness, Lipschitz, smoothness, and loss assumptions, Girsanov’s theorem constructs a measure ρS under which W follows the desired data-dependent dynamics.The measures ρS and π are equivalent, and the transformed process has a ρS-Brownian motion.Source: §B.4.1 · p. 41
  • The change of measure is defined through a continuous π-martingale satisfying Novikov’s condition, after which Girsanov’s theorem identifies the transformed Brownian motion.Source: §B.4.1 · p. 41
  • The KL divergence is obtained from the martingale property and Fubini’s theorem using the relation established for the dynamics.Source: §B.4.1 · pp. 42–43
  • The Radon–Nikodym derivative dρS/dπ supplied by Girsanov’s theorem also enables more general changes of measure and disintegrated bounds.Source: §B.4.1 · p. 42
  • The proof applies the PAC-Bayesian theorem to a function built from the expected-dynamics prior and rewrites the resulting bound using the previously derived KL expression.Source: §B.4.1 · pp. 42–43

B.4.2 Rademacher complexity of CLD - omitted proofs of Section 6.3

The section develops proof ingredients for Rademacher-complexity bounds for continuous Langevin dynamics and specifies the adapted-noise setting used for SGLD.

B.4.2 Rademacher complexity of CLD - omitted proofs of Section 6.3

  • A maximal-inequality lemma bounds the expectation of the maximum of nonnegative random variables, providing the main probabilistic estimate used in the CLD argument.The proof combines this lemma with Brownian-motion estimates and Massart’s lemma.Source: §B.4.2 · pp. 43–45
  • The CLD proof discretizes time with t_i=iδ, δ=T/K, and analyzes Brownian coordinates and Rademacher variables across the resulting intervals.The construction assumes K is large enough that δ<1 and uses the strong Markov property to obtain independent, identically distributed interval increments.Source: §B.4.2 · pp. 43–44

B.5.1 Setting details

  • The SGLD setting uses a filtered probability space in which Gaussian noises and stochastic gradients are adapted, while each noise variable is independent of the preceding information and current gradient estimate.The stochastic-gradient estimate is unbiased for the gradient of the empirical risk, and the iterate sequence is consequently adapted to the filtration.Source: §B.5.1 · p. 45
  • Mini-batch stochastic gradients fit the assumed form by taking U_{k+1} as an independent random index set and averaging gradients over its selected examples.The construction is described as similar to settings used by Mou et al. (2018) and Negrea et al. (2019).Source: §B.5.1 · p. 45

B.5.2 Proof of Theorem 23

The proof of Theorem 23 changes measure so that the SGLD trajectory becomes a data-independent Gaussian random walk, while the appendix establishes measurability for random sets and covering numbers.

B.5.2 Proof of Theorem 23

  • The proof constructs martingales and uses a discrete Girsanov-style change of measure, with the approach also yielding a closed-form Radon–Nikodym derivative.The resulting framework can establish disintegrated uniform generalization bounds for SGLD, while the KL divergence can alternatively be obtained by decomposing the path law into conditional distributions.Source: §B.5.2 · pp. 45–46
  • Under the changed measure Q, the transformed process has independent N(0, Id) increments, so W follows a data-independent normal random walk.This characterization is the central probabilistic step behind the theorem’s posterior-prior comparison.Source: §B.5.2 · pp. 47–48
  • The posterior law of the SGLD hypothesis set is data-dependent, whereas its pushforward under the reference construction is data-independent and corresponds to the Gaussian random-walk dynamics.The proof then applies data processing to relate KL(ρS∥π) to KL(P∥Q).Source: §B.5.2 · p. 48

B.6 Random closed sets formalization: omitted proofs

  • The random-closed-set formalization defines a measurable structure through the Effrös σ-algebra and verifies measurability of the relevant supremum constructions.The argument uses countable unions and intersections after reducing existential conditions to rational points and radii.Source: §B.6 · pp. 48–49

B.6.1 Covering numbers measurability

  • Rational covering numbers are measurable for closed sets, preserve covering-number bounds up to a small absolute constant, and yield the same upper box-counting dimension.For data-dependent pseudometrics, measurability follows similarly when the loss is continuous.Source: §B.6.1 · p. 49
Loading 2404.17442v2…