User-friendly introduction to PAC-Bayes bounds

5.1 “Almost” Bounded Losses (Sub-Gaussian and Sub-gamma)

• The section covers “almost” bounded losses, including sub-Gaussian and sub-gamma cases.Source: §5 · p. 3

5.2 Heavy-tailed Losses

• It also addresses heavy-tailed losses.Source: §5 · p. 3

5.3 Dependent Observations

• A separate subsection considers dependent observations.Source: §5 · p. 3

5.4 Other Non i.i.d. Settings

• The section also includes other non-i.i.d. settings.Source: §5 · p. 3

Introduction

• The tutorial studies aggregated predictors, whose members vote by weights, and randomized predictors, which sample a predictor from a probability distribution.It introduces machine-learning concepts and PAC bounds to formalize these procedures and introduce PAC-Bayes.Source: Introduction · p. 6

1.1.1 Machine learning: notations

• The notation section defines predictors, losses, expected risk, and empirical risk for i.i.d. labeled examples, assuming bounded loss through Section 4.It notes that the bounded-loss assumption will be addressed in Section 5.Source: §1.1.1 · pp. 7–9

1.1.2 PAC bounds

• For a fixed predictor, empirical risk may underestimate risk; controlling data-dependent ERM requires a uniform bound, illustrated for finite parameter sets.The section notes that the fixed-predictor bound cannot directly be applied to the data-dependent ERM.Source: §1.1.2 · p. 11

1.2. WHAT ARE PAC-BAYES BOUNDS?

• The section stops short of general ERM analysis, which requires modifying the union-bound argument beyond finite predictor sets.PAC-Bayes is presented as a way to handle finite, infinite, or continuous parameter sets.Source: §1.2 · p. 13

1.2 What are PAC-Bayes Bounds?

• PAC-Bayes extends union-bound reasoning to finite or infinite parameter sets and bounds risks associated with data-dependent probability measures.These include randomized estimators and aggregated predictors.Source: §1.2 · pp. 13–14

1.2. WHAT ARE PAC-BAYES BOUNDS?

• For infinite parameter sets, PAC-Bayes replaces the log(M) term with KL divergence from a data-dependent distribution ρ to a fixed prior π.Bounds depend on prior probability assigned to empirical-risk level sets, so flatter minima can yield tighter bounds.Source: §1.2 · p. 15

1.3 Why this Tutorial?

• The tutorial aims to make PAC-Bayes literature easier to enter, noting that many papers assume prior knowledge and that Catoni’s techniques are often overlooked.It is intended as an accessible first approach for PhD students and provides references for more sophisticated results.Source: §1.3 · p. 16, §1.4 · p. 17

1.4. TWO TYPES OF PAC BOUNDS, ORGANIZATION OF THESE NOTES

• The notes prioritize highlighting main ideas over tight constants; many oracle and localized bounds in Section 4 have better constants in Catoni (2003; 2007), whose original publications are recommended.The author also recommends earlier introductions by McAllester (2013), van Erven (2014), and Fleuret (2011), while noting their focus on empirical bounds.Source: §1.4 · p. 17

1.4 Two Types of PAC Bounds, Organization of these Notes

• Empirical PAC bounds provide computable generalization certificates, whereas oracle or excess-risk bounds assess closeness to the best risk but cannot be computed because risk is unknown.Oracle bounds instead indicate how close the ERM risk can be to the smallest possible risk.Source: §1.4 · pp. 17–18
• McAllester (1998) and McAllester (1999) introduced empirical PAC-Bayes bounds; later oracle bounds came from Catoni (2003; 2004; 2007) and Zhang (2006).Empirical bounds also help prove oracle bounds, while oracle analysis can assess whether a data-dependent probability measure is likely to yield small empirical bounds.Source: §1.4 · p. 18
• Sections 2 and 3 develop empirical PAC-Bayes bounds, including their use for deep-learning generalization certificates discussed through Dziugaite and Roy (2017) and Pérez-Ortiz et al. (2021).Section 2 works through a Catoni (2003) example; Section 3 surveys empirical bounds and their pursuit of tighter results.Source: §1.4 · p. 18
• Section 4 derives oracle bounds from empirical bounds, applies them to classical predictor sets, and examines assumptions for fast rates; Section 5 considers extensions beyond bounded loss and i.i.d. data.Section 6 briefly discusses connections to regret bounds and Mutual Information bounds.Source: §1.4 · pp. 18–19

First Step in the PAC-Bayes World

• Catoni’s bound is presented as a pedagogical example because its technique can illustrate PAC-Bayes proofs and unify several bound variants, rather than because it is claimed to be the best bound (Catoni, 2003).The tutorial uses it to explain bounds for randomized and aggregated estimators before comparing alternative empirical bounds later.Source: First Step in the PAC-Bayes World · p. 20

2.1.1 Catoni’s bound (Catoni, 2003)

• With a fixed prior and bounded loss, the Donsker–Varadhan variational formula yields the Gibbs measure as the optimizer underlying Catoni’s bound (Kullback, 1959, Exercise 8.28; Donsker and Varadhan, 1976).The formula is introduced as a general lemma used throughout the notes.Source: §2.1.1 · pp. 20–21

2.1.2 Exact minimization of the bound

• The Gibbs posterior minimizes the right-hand side of Catoni’s bound, giving a data-dependent probability measure defined from the empirical risk.For finite predictor sets, the explicit bound can match the ERM bound without making the Gibbs posterior equivalent to the ERM; it can be tighter when empirical risks are close to their minimum. The prior affects tightness through the mass assigned to low-risk predictors, while optimizing λ for a nonuniform prior may depend on the data. PAC-Bayes bounds can also study the ERM and other classical estimators, and λ affects the Gibbs procedure itself, unlike the ERM.Source: §2.1.2 · pp. 23–24, §2.1.3 · pp. 25, 27

2.1.3 Some examples, and non-exact minimization of the bound

• For Lipschitz losses on R^d with a centered Gaussian prior, restricting PAC-Bayes optimization to Gaussian distributions gives a variational approximation, but optimizing λ may depend on the variational mean.Choosing a norm bound on the mean simplifies the bound at the cost of making it worse; the tutorial also describes the Gaussian variational measure as an approximation to the Gibbs posterior.Source: §2.1.3 · pp. 27–30
• With multiple predictor sets, minimizing over distributions across models gives model aggregation, while restricting distributions to one model at a time gives a model-selection procedure.The procedure builds a Gibbs posterior for each model and then selects a model.Source: §2.1.3 · pp. 30–31

2.1.4 The choice of λ

• A finite grid for λ permits bound minimization via a union bound, and a geometric grid can improve on the log(n) term of an arithmetic grid (Langford and Caruana, 2002; Catoni, 2003; Catoni, 2007, Theorem 1.2.8 page 13).The tutorial notes that some alternative PAC-Bayes bounds, including McAllester (1999), do not require optimizing λ.Source: §2.1.4 · pp. 31–34

2.2 PAC-Bayes Bound on Aggregation of Predictors and Weighted Majority Vote

• For convex losses such as quadratic or hinge loss, PAC-Bayes bounds also control the risk of aggregated predictors.The argument uses Jensen’s inequality to relate the aggregated predictor’s risk to the expected risk of randomized predictors.Source: §2.2 · p. 34, §2.3 · p. 35

2.3 PAC-Bayes Bound on a Single Draw from the Posterior

• A draw from a data-dependent posterior, such as the Gibbs posterior, has a risk bound holding with large probability over both the sample and the draw.The result concerns the risk of the sampled predictor.Source: §2.3 · pp. 35–36
• Clerico et al. (2022b) use a PAC-Bayes bound without sampling from the posterior to bound the risk of a deterministic gradient-descent predictor.They take the random initialization distribution as the prior and define the posterior implicitly as the distribution of the final iterate.Source: §2.3 · p. 36

2.4 Bound in Expectation

• Bounds in expectation are simpler and shorter to derive for oracle PAC-Bayes inequalities, but they do not hold with large probability and are not PAC bounds in the strict sense.The paper uses “PAC-Bayes bound in expectation” rather than the suggested EAC-Bayes or MAC-Bayes acronyms.Source: §2.4 · p. 37

2.5 Applications of Empirical PAC-Bayes Bounds

• Empirical PAC-Bayes bounds apply to generic bounded losses, covering classification, bounded regression, and density estimation, as well as specific models.Examples include support vector classifiers, random forests, and ranking or scoring.Source: §2.5 · p. 38
• Applications also include density estimation, multiple testing, deep learning, generative adversarial networks, and unsupervised learning.The passage notes that applying PAC-Bayes bounds to deep learning is not straightforward; unsupervised examples include clustering, representation learning, and variational autoencoders.Source: §2.5 · p. 39

3.1 Why is there a Race to Tighter PAC-Bayes Bound?

• The Gibbs risk bound is below 0.322 for the small classifier set, but reaches 13.58 for the neural-network example and is vacuous.Even increasing that example’s sample size to 1,000,000 still gives a vacuous bound.Source: §3.1 · pp. 40–41

3.1. WHY IS THERE A RACE TO TIGHTER PAC-BAYES BOUND?211

• Dziugaite and Roy (2017) obtained non-vacuous PAC-Bayes bounds for practical neural networks, prompting wider attention to the theory.The text notes that the bounds were not yet very tight, and that tighter bounds were obtained later by these authors and others.Source: §3.1 · p. 42

3.2 A Few PAC-Bayes Bounds

• The bounds in this section apply to any [0, 1]-valued loss, not only classification with 0-1 loss.The section sets C = 1, so R and r also take values in [0, 1].Source: §3.2 · p. 42

3.2.1 The first PAC-Bayes bounds

• Asymptotically, Theorem 2.4 with a geometric grid can outperform Theorem 3.1, while Theorem 3.1’s smaller constants may help at small sample sizes.Theorem 3.1’s right-hand side can be minimized over ρ; Thiemann et al. (2017) provide a more recent bound that can be efficiently minimized in both λ and ρ.Source: §3.2.1 · pp. 43–44

3.2.2 A key for tigher bounds: kl-PAC-Bayes bounds

• Maurer’s version of Seeger’s kl-PAC-Bayes bound is central because many other bounds follow from it; Pinsker’s inequality yields a form essentially like McAllester’s bound with improved constants.The passage then indicates that substantially tighter explicit bounds are possible.Source: §3.2.2 · pp. 44–45

3.2.3 Explicit tight bounds

• When posterior empirical risk is zero, suitable PAC-Bayes bounds achieve 1/n rates; Thiemann’s bound also supports joint optimization and Gaussian-prior optimization without bounding the mean norm.The text highlights this rate for Theorems 3.2 and 3.3, and again for Theorem 3.4 when the posterior empirical risk is zero (for example, λ = 1).Source: §3.2.3 · pp. 45, 46, 48

3.2.4 Some proofs

• Germain et al. (2009)’s general bound underlies the bounds in this section and can also derive bounds for unbounded losses and non-i.i.d. observations; Foong et al. (2021) found no function D giving a lower expected bound than Theorem 3.2, up to log(2√n).Source: §3.2.4 · pp. 48, 51

3.2.5 PAC-Bayes-Bernstein

• PAC-Bayes-Bernstein bounds improve on Hoeffding-based bounds when the loss variance is small.When V(θ) is bounded by 1/4, the comparison bound is comparable to (1.1); for small V(θ), it is much better.Source: §3.2.5 · p. 53
• Empirical PAC-Bayes-Bernstein bounds replace the unknown variance term with an empirical variance bound and can yield a 1/n rate for predictors with zero risk.For bounded losses, the empirical variance can also be no greater than the risk, so the bound may be tighter even without a perfect predictor.Source: §3.2.5 · pp. 53–55

3.3.1 A milestone: non vacuous generalization error bounds for deep networks by Dziugaite and Roy (2017)

• Dziugaite and Roy (2017) obtained the first nonvacuous deep-network generalization bounds on MNIST, with empirical bounds of 0.16–0.22 versus posterior classification performance around 0.03.They concluded that the gap left room for improvement.Source: §3.3.1 · pp. 56–57
• Dziugaite and Roy (2017) made Seeger’s bound tractable by constraining the posterior to be Gaussian, upper bounding kl^-1, using a convex Lipschitz loss surrogate, and minimizing with SGD.The Gaussian posterior reduces optimization to its mean and variance parameters.Source: §3.3.1 · p. 56
• SGD’s tendency to find flat minima lets Dziugaite and Roy (2017) use a wider Gaussian posterior, while their data-dependent prior is centered at a randomly initialized weight vector.They choose the prior variance to minimize the bound, justified by a union bound.Source: §3.3.1 · p. 57

3.3.2 Bounds with data-dependent priors

• Catoni’s localization uses a data-dependent prior proportional to π weighted by exp(-βR), replacing unknown risk with empirical risk to obtain a typically tighter bound.Seeger’s earlier sample-splitting approach defines the prior using one part of the sample and applies the bound to the other; Catoni’s localized bound requires calibrating λ and β.Source: §3.3.2 · pp. 58–59
• Dziugaite and Roy (2018) showed that any data-dependent prior can be used in Seeger’s bound under a differential privacy condition, with a small modification to the bound.Source: §3.3.2 · p. 59

3.3.3 Comparison of the bounds and tight certificates

• 0.0279 on MNIST: Pérez-Ortiz et al. (2021) improved Dziugaite and Roy’s generalization bound, and Clerico et al. (2022a) later reported even tighter results.Pérez-Ortiz et al. also reported a 0.02 test error and found Thiemann et al. (2017) tightest among the bounds they compared. These results use sample splitting, which critics say can make the PAC-Bayes step barely necessary because the posterior is close to the prior.Source: §3.3.3 · p. 60

PAC-Bayes Oracle Inequalities and Fast Rates

• The first oracle PAC-Bayes inequality is derived from an empirical PAC-Bayes inequality, alongside examples of oracle bounds.Source: PAC-Bayes Oracle Inequalities and Fast… · p. 61

4.1 From Empirical Inequalities to Oracle Inequalities

• Oracle bounds can be given in expectation or in probability; the section focuses on expectation because its proofs are shorter, while noting probability counterparts by Catoni (2003) and Catoni (2007).Source: §4.1 · p. 61

4.1.1 Bound in expectation

• The expectation oracle inequality follows by applying the empirical inequality to the Gibbs posterior and identifying expected loss with risk.The derivation uses Tonelli’s theorem.Source: §4.1.1 · p. 62
• The expectation bound guarantees predictions are theoretically best possible up to an additive C log(M)/2n term, though it provides no numerical certificate.The passage notes that empirical PAC-Bayes inequalities do not provide this theoretical comparison.Source: §4.1.1 · p. 62

4.1. FROM EMPIRICAL INEQUALITIES TO ORACLE INEQUALITIES

• Faster rates cannot be guaranteed in the worst case, but they are possible quite often and are taken up in the following subsections.Source: §4.1 · p. 63

4.1.2 Bound in probability

• The probability oracle inequality is derived from the empirical inequality in probability using a more complicated proof, which yields worse constants.Source: §4.1.2 · p. 63

Example 4.2: Classification without noise

• In noiseless classification, Bernstein’s assumption holds with K = 1 for 0–1 loss, and with K = C for any loss bounded in [0, C] when R(θ∗) = 0.Noiseless classification here means the optimal classifier makes no mistakes.Source: §4.2 · p. 66

Example 4.3: Mammen and Tsybakov margin assumption

• For 0–1 classification, the Mammen and Tsybakov (1999) margin condition |η(Xi) − 1/2| ≥ τ > 0 implies Bernstein’s assumption for a K depending on τ.τ = 1/2 recovers noiseless classification; 0 < τ < 1/2 is more general.Source: §4.2 · pp. 66–67

Example 4.4: Lipschitz and strongly convex loss function

• For convex Θ, strong convexity and Lipschitz conditions imply Bernstein’s assumption with K = 4L2α; quadratic loss supplies an example when Xi, Yi, and Θ are bounded.For quadratic loss, the passage gives α = 1/2 and d_i(θ, θ∗) = ⟨Xi, θ − θ∗⟩2.Source: §4.2 · p. 67

Theorem 4.3

• Under Bernstein’s assumption, Theorem 4.3 gives an excess-risk PAC-Bayes bound with rate 1/n when the posterior’s expected risk is close to the minimizer’s risk.The theorem takes λ = n/max(2K, C); applications are deferred to Section 4.3.Source: §4.2 · p. 68

Comparison with earlier bounds

• This section builds oracle inequalities at rates 1/√n and 1/n; the former uses an empirical inequality in its proof, while the latter does not directly use one.Earlier PAC-Bayes inequalities were empirical and mostly gave 1/√n, except when empirical error was close to zero, where the rate was 1/n.Source: §4.2 · pp. 68–69

Proof of Theorem 4.3

• The proof replaces Hoeffding’s inequality with Bernstein’s inequality and applies it to relative losses ℓi(θ∗) − ℓi(θ) so the Bernstein condition can be used.It then integrates over predictors and applies Tonelli’s theorem and Donsker–Varadhan’s variational formula.Source: §4.2 · pp. 69–70

4.3 Applications of Theorem 4.3

• Under a Bernstein condition, the finite-predictor application retains the log(M)/n rate from Example 2.1.It uses a uniform prior on M predictors, restricts the supremum to point-mass distributions, and sets λ = n/max(2K, C).Source: §4.3 · p. 71
• For Lipschitz losses on Rd with a Gaussian prior, Theorem 4.3 is applied under a Bernstein condition with λ = n/max(2K, C).The setup uses π = N(0, σ²Id); the text says it seeks an exact optimizer in s but the supplied choice is truncated.Source: §4.3 · p. 71
• With a uniform prior on the radius-B ball, the application restricts candidate distributions to uniform measures on balls B(θ0, s).It assumes a Lipschitz loss and Bernstein constant K, and applies Theorem 4.3 with λ = n/max(2K, C).Source: §4.3 · p. 72
• For any s > 0, a center θ0 can be chosen so that θ* lies in B(θ0, s) and that ball is contained in Θ.This condition supports the uniform-ball restriction in the bounded-domain example.Source: §4.3 · p. 72
• The uniform-ball bound's right-hand side is minimized at a radius specified in the text, with n large enough to ensure s ≤ B.The supplied radius and resulting bound are truncated, so their exact expressions cannot be stated.Source: §4.3 · p. 72
• The section closes by introducing a non-exhaustive list of more sophisticated models for which oracle PAC-Bayes inequalities derived convergence rates.The supplied passage does not include the models in that list.Source: §4.3 · p. 72

Applications of Theorem 4.3

• Applications include model selection, density estimation, scoring and ranking, and least-square regression, including robust variants.For classification, the minimization procedure in Example 2.3 is not always optimal; Lepski-based selection with PAC-Bayes bounds is used by Catoni (2007) and Alquier (2008). Related work includes Catoni (2004, Chapters 4 and 5), Catoni (2007), Ridgway et al. (2014), Audibert and Catoni (2011), and Catoni and Giulini (2017).Source: §4.3 · p. 73
• Sparse linear regression results include Gibbs-posterior rates similar to LASSO and variants covering group sparsity; applications also include single-index and additive regression.Dalalyan and Tsybakov (2008) prove the rate under more general assumptions; variants and improvements appear in Dalalyan and Tsybakov (2012), Alquier and Lounici (2011), and Dalalyan et al. (2018), with group sparsity in Luu et al. (2019). Single-index regression is studied in small dimension by Gaïffas and Lecué (2007) and in high dimension with sparsity by Alquier and Biau (2013); additive non-parametric regression is studied by Guedj and Alquier (2013).Source: §4.3 · p. 73
• Matrix regression and completion applications span continuous and binary cases, with related techniques extending to tensor completion.Matrix regression is studied by Suzuki (2012), Alquier (2013), Dalalyan et al. (2018), Dalalyan (2020), and Mai (2023a). Completion work includes the continuous case (Mai and Alquier, 2015; Mai, 2017; Mai, 2023b), the binary case, and tensor completion.Source: §4.3 · p. 73
• Other applications include quantum tomography, deep learning, and Gram-matrix estimation for PCA and kernel-PCA.Quantum tomography is covered by Mai and Alquier (2017), deep learning by Chérief-Abdellatif (2020) and Steffen and Trabs (2022), and Gram-matrix estimation for PCA and kernel-PCA by Catoni and Giulini (2017), Zhivotovskiy (2021), Giulini (2018), and Haddouche et al. (2020).Source: §4.3 · p. 73

4.4 Dimension and Rate of Convergence

• For finite Θ with uniform π, raten(π) is log(M)/n generally and log(M)/n under the Bernstein condition.The section says all results considered so far assume a bounded loss function.Source: §4.4 · p. 74
• For Θ = R^d with π = N(0, σ^2I_d), raten(π) is [∥θ∗∥^2 + d log(n)]/n generally and under the Bernstein condition.The section identifies d as the model dimension.Source: §4.4 · p. 74
• For Θ = R^d with the multivariate Student prior of Dalalyan and Tsybakov (2008), raten(π) is [log ∥θ∗∥ + d log(n)]/n generally and under the Bernstein condition.Deriving this result is left as an exercise.Source: §4.4 · p. 74
• For compact Θ ⊂ R^d with uniform π, raten(π) is d log(n)/n generally and under the Bernstein condition.The section identifies d as the model dimension.Source: §4.4 · p. 74
• The examples assume conditions yielding an inequality with constants c and d, then apply Theorem 4.1 or, under the Bernstein assumption, Theorem 4.3 to obtain a convergence rate.The formal statement is given under the Bernstein assumption; the case without it is left as an exercise.Source: §4.4 · p. 74

4.4. DIMENSION AND RATE OF CONVERGENCE

• Under a Bernstein condition with constant K, Theorem 4.4 takes λ = n/max(2K, C), provided λ ≥ β0.The theorem assumes constants β0, cπ, and dπ satisfying a condition for β ≥ β0.Source: §4.4 · p. 75
• Catoni’s dimension assumption with dimension dπ implies condition (4.8) with cπ = dπ/(eC), for β ≥ β0 = dπ/C.The proof combines bounds on f′, including f′(ξ) ≤ min(C, dπ/ξ), and integrates them.Source: §4.4 · pp. 75–76
• The prior mass condition with constants c and dπ implies (4.8) with cπ = dπ/(ec), for β ≥ β0 = dπ/r0.This condition is classical for analyzing Bayesian estimator asymptotics (Ghosal and Van der Vaart, 2017).Source: §4.4 · p. 77

4.5 Getting Rid of the log Terms: Catoni’s Localization Trick

• A localized bound removes the log(n) terms from the listed convergence rates, both generally and under the Bernstein condition.Theorem 4.7 assumes the Bernstein condition and takes λ = n/max(2K, C).Source: §4.5 · pp. 77–78
• Corollary 4.8 gives a localized bound when Catoni’s dimension condition holds with dπ > 0 and the Bernstein condition holds, taking λ = n/max(2K, C).Source: §4.5 · p. 78
• For a finite class with M predictors and a uniform prior, the bound recovers the log(M)/n rate; a threshold-based refinement can be much smaller for large n.The refinement uses mτ, the number of predictors whose risk is within τ of the best predictor; a similar result was obtained by Lecué and Mendelson (2013) using a different technique.Source: §4.5 · pp. 78–79

Beyond “Bounded Loss” and “i.i.d. Observations”

• PAC-Bayes proofs use bounded-loss and i.i.d. assumptions to obtain Hoeffding- or Bernstein-type exponential-moment inequalities, which can be replaced by suitable inequalities for other settings.An exponential-moment inequality may also be assumed to hold on average under the prior rather than uniformly over predictors.Source: Beyond “Bounded Loss” and “i.i.d.… · pp. 83–84

5.1. “ALMOST” BOUNDED LOSSES (SUB-GAUSSIAN AND SUB-GAMMA)

• Independent sub-Gaussian losses with constant C permit PAC-Bayes bounds for some unbounded losses; bounded variables qualify with C = (b −a)2/8.Gaussian variables qualify with C = σ2/2; sub-gamma variables include gamma, exponential, Gaussian, and bounded variables.Source: §5.1.1 · p. 84, §5.1 · p. 85, §5.1.2 · p. 85

5.2.1 The truncation approach

• Truncation controls heavy-tailed losses by applying exponential-moment inequalities to a bounded part and tail inequalities to the remainder.The residual tail term can slow convergence; in the bounded-loss case it vanishes when n/λ is large enough.Source: §5.2.1 · p. 86, §5.2 · p. 87

5.2.2 Bounds based on moment inequalities

• Variance-only PAC-Bayes bounds for independent heavy-tailed losses can use divergences other than KL, but their δ-dependence is worse and convergence can be slow.Minimizing the bound over ρ gives an explicit solution; Ohnishi and Honorio (2021) later improved the δ-dependence.Source: §5.2.2 · p. 88

5.2.3 Bounds based on robust losses

• Holland (2019) bounds robustified losses with standard bounded-loss tools, yielding rates like the bounded case, but a π∗n(Θ) term can worsen rates for non-sub-Gaussian losses.The robust loss is bounded even when the original loss is unbounded, and the resulting bound includes KL(ρ∥π), rather than χ2(ρ∥π).Source: §5.2 · pp. 89–90

5.3.1 Inequalities for dependent variables

• Concentration inequalities for dependent data yield PAC-Bayes bounds for time series and other models; mixing time series have fast 1/n rates, versus earlier 1/√n rates for weak dependence.Martingale inequalities can also support bounds when sample size is a stopping time.Source: §5.3.1 · p. 90, §5.3 · p. 91

5.4.2 Shift in the distribution

• Many exponential-inequality results extend to independent, non-identically distributed observations; domain adaptation offers a PAC-Bayes approach when training and prediction distributions differ.Catoni (2007) treats independent, non-identically distributed observations; Germain et al. (2016b) propose domain adaptation for distribution shift.Source: §5.4.1 · p. 92, §5.4.2 · p. 92

5.4.3 Meta-learning

• In meta-learning, PAC-Bayes can learn task-specific predictors from sampled tasks and improve learning for a future task, for example through a better prior or parameter space.The described formalization treats tasks as i.i.d. draws from a distribution and draws an i.i.d. sample within each task.Source: §5.4.3 · p. 93

6.1 Bayesian Inference in Statistics

• The ordinary Bayesian posterior is a Gibbs posterior under negative log-likelihood loss, but unbounded log-likelihoods block the simplest PAC-Bayes consistency bounds (Audibert (2004); Germain et al. (2016a)).The connection is also discussed by those authors; the limitation concerns use of the simplest bounds to study consistency of the posterior.Source: §6.1 · p. 95

6.1.1 Gibbs posteriors, generalized posteriors

• Generalized and tempered Gibbs posteriors replace log-likelihood by risk; a sufficiently small temperature can yield consistency where the ordinary posterior is inconsistent (Grünwald and Van Ommen (2017)).Gibbs posteriors are also studied for parameter estimation without modeling the full data distribution, and in a decision-theoretic framework (Jiang and Tanner (2008); Syring and Martin (2019); Bissiri et al. (2016)).Source: §6.1.1 · p. 95

6.1.2 Contraction of the posterior in Bayes nonparametrics

• Posterior contraction targets concentration around the true parameter and typically requires tests and sufficient prior mass nearby; PAC-Bayes bounds plus a prior-mass condition establish tempered-posterior contraction (Bhattacharya et al. (2019, Theorem 3.1)).The prior-mass condition can be used with a PAC-Bayes inequality under a Bernstein condition to make the bound small.Source: §6.1.2 · p. 96, §6.1 · p. 97

6.1.3 Variational approximations

• Variational approximations make posterior inference tractable by restricting distributions, and non-exact PAC-Bayes minimization can be interpreted as variational approximation of Gibbs posteriors.For tempered posteriors, such approximations are constrained PAC-Bayes-bound minimizers; PAC-Bayes analyses have been used to study their consistency and generalize the prior-mass condition for variational inference. A broader formulation replaces negative log-likelihood with risk, optimization over all distributions with a tractable family, and KL with a general divergence.Source: §6.1.3 · pp. 97–98

6.2 Empirical Risk Minimization

• PAC-Bayes connects to empirical-risk minimization through VC-dimension, margin, chaining, and Rademacher-complexity results, and to statistical aggregation through oracle PAC-Bayes bounds with fast rates (Dalalyan and Tsybakov (2008, Theorem 1)).For non-finite parameter spaces, data-dependent priors can make VC-dimension explicit, though finite VC-dimension alone may not suffice; conditional PAC-Bayes bounds address the cited failure (Catoni (2003, Section 2); Catoni (2007, Chapter 3, page 115–130); Livni and Moran (2020); Grünwald et al. (2021)). Aggregation methods also share formal similarities with EWA and Gibbs posteriors, while the cited oracle bound uses different assumptions, including nonrandom Xi’s.Source: §6.2 · pp. 99–100, §6.5 · pp. 103–104

6.3 Non-Bayesian Estimators

• Catoni’s PAC-Bayes technique controls the error norm of non-Bayesian estimators and has been applied to robust Gram-matrix and covariance estimation, including kernel-PCA (Catoni and Giulini (2017); Giulini (2018)).The method builds on earlier robust-estimation work and has also been used for covariance-matrix estimation (Audibert and Catoni (2011); Catoni (2012); Zhivotovskiy (2021); Nakakita et al. (2022)).Source: §6.3 · p. 100

6.4. ONLINE LEARNING

• Most online regret bounds require no stochastic-data assumption, though assumptions on the loss are unavoidable; the stated EWA bound assumes losses in [0,C] and convexity in the predictor parameter.For bandits, some strategies are EWA-derived, and strategies or regret bounds have been derived directly from PAC-Bayes bounds; PAC-Bayes bounds or related generalization bounds for RL were derived by Wang et al. (2019) and Tasdighi et al. (2023).Source: §6.4 · pp. 101–102, §6.4.2 · p. 103

6.6 Information Theoretic Approaches

• Information-theoretic links include MDL, where code lengths can define PAC-Bayes priors, and mutual-information generalization bounds, including bounds that recover VC-dimension dependence for empirical risk minimization (Russo and Zou (2019)).The MI complexity is measured between the sample and estimator; the section also notes PAC-Bayesian results described as “information theoretic bounds” (Zhang (2006)).Source: §6.6.1 · p. 104, §6.6.2 · p. 104, §6.6 · pp. 104–105

6.6. INFORMATION THEORETIC APPROACHES

• The MI bound is tighter than the PAC-Bayes bound in expectation, but cannot be used directly because I(θ, S) depends on the unknown sample distribution.Its use requires upper-bounding I(θ, S) by a quantity independent of the sample.Source: §6.6 · p. 106
• The expected KL penalty decomposes into I(θ, S) plus KL(ES(˜ρ)∥π), linking PAC-Bayes prior optimization directly to mutual information.The decomposition is ES[KL(˜ρ∥π)] = I(θ, S) + KL(ES(˜ρ)∥π).Source: §6.6 · p. 107
• MI bounds can be viewed as PAC-Bayes bounds optimized over the prior; Catoni’s localized prior approximates that optimizer and supports empirical and improved oracle bounds.Grünwald et al. (2021) point out that the prior minimizing a PAC-Bayes bound turns its KL term into mutual information.Source: §6.6 · p. 107
• MI bounds provide an exact formula, rather than an upper bound, for the Gibbs posterior’s generalization error in terms of symmetrized KL (Aminian et al., 2021).Source: §6.6 · p. 108
• MI and PAC-Bayes bounds can fail for finite-VC classes, whereas Grünwald et al. (2021) unify them with conditional bounds that are small for every finite-VC classifier class.MI bounds can also use divergences other than KL.Source: §6.6 · p. 108

• The introduction aims to give readers a better understanding of what PAC-Bayes bounds are and what they can do.Source: Conclusion · p. 109
• PAC-Bayes bounds are presented as flexible tools for a wide range of contexts and machine-learning objectives.Source: Conclusion · p. 109
• The author expects PAC-Bayes and related approaches to play an important role in deep learning, reinforcement learning, and meta-learning, following Dziugaite and Roy (2017), Wang et al. (2019), Pentina and Lampert (2014), Amit and Meir (2018), and Rothfuss et al. (2021).Source: Conclusion · p. 109