PaperlayerView exact revision on arXiv

Source-linked AI summary

PAC-Bayesian Theory Meets Bayesian Inference

Pascal Germain, Francis Bach, Alexandre Lacoste, Simon Lacoste-Julien

arXiv:1605.08636v4stat.MLcs.LG

TL;DR

The paper asks how frequentist PAC-Bayesian risk bounds relate to Bayesian marginal likelihood, especially when using negative log-likelihood. It establishes an equivalence between bound minimization and marginal-likelihood maximization, extends PAC-Bayes to relevant unbounded losses, and demonstrates the approach on Bayesian regression tasks.

  • Problem

    The relationship between frequentist PAC-Bayesian risk bounds and Bayesian marginal likelihood requires clarification, while negative log-likelihood falls outside standard bounded-loss results.

  • Method

    The paper uses negative log-likelihood to connect PAC-Bayesian bounds with Bayesian inference and develops PAC-Bayesian generalization bounds for unbounded sub-gamma losses.

  • Results

    Minimizing the PAC-Bayes bound is equivalent to maximizing marginal likelihood, with the optimal PAC-Bayes posterior coinciding with the Bayesian posterior.

  • Takeaways & Limitations

    The marginal likelihood can be understood as encoding the PAC-Bayesian trade-off between averaged negative log-likelihood and prior-posterior KL divergence.

  • Takeaways & Limitations

    The bridge requires addressing negative log-likelihood's general unboundedness, since existing PAC-Bayesian theorems typically use bounded losses or specific contexts.

Abstract

from arXiv · show

We exhibit a strong link between frequentist PAC-Bayesian risk bounds and the Bayesian marginal likelihood. That is, for the negative log-likelihood loss function, we show that the minimization of PAC-Bayesian generalization risk bounds maximizes the Bayesian marginal likelihood. This provides an alternative explanation to the Bayesian Occam's razor criteria, under the assumption that the data is generated by an i.i.d distribution. Moreover, as the negative log-likelihood is an unbounded loss function, we motivate and propose a PAC-Bayesian theorem tailored for the sub-gamma loss family, and we show that our approach is sound on classical Bayesian linear regression tasks.

1 Introduction

The paper connects Bayesian inference with PAC-Bayesian risk bounds, showing that marginal likelihood and PAC-Bayesian complexity-accuracy trade-offs describe the same model-selection principle. It also extends the analysis to unbounded regression losses and illustrates it on Bayesian regression tasks.

  • The paper establishes a direct connection between Bayesian inference techniques and PAC-Bayesian risk bounds.
  • For negative log-likelihood, PAC-Bayesian bounds provide an alternative explanation of Bayesian Occam's razor through a complexity-accuracy trade-off.
  • The authors extend PAC-Bayes theorems to regression with unbounded loss, adapting them to negative log-likelihood.
  • The proposed framework is illustrated on classical Bayesian regression tasks.

2 PAC-Bayesian Theory

PAC-Bayesian theory bounds the generalization risk of posterior-averaged predictors using data-dependent empirical losses and prior-posterior divergence. Its algorithmic interpretation is an optimization balancing empirical expected loss against KL complexity.

  • The learning setup assumes n i.i.d. observations sampled from a data-generating distribution D.
  • PAC-Bayesian theory studies losses averaged over a posterior distribution and bounds the corresponding unknown generalization risk.
  • The KL divergence measures the discrepancy between a prior chosen before observing data and a posterior typically obtained from the learning sample.
  • PAC-Bayesian theorems provide training-sample generalization bounds that are uniformly valid for all posterior distributions.
  • Optimizing the PAC-Bayesian bound selects a posterior by trading off empirical expected loss against KL divergence.

3 Bridging Bayes and PAC-Bayes

With negative log-likelihood as the loss, the paper identifies the PAC-Bayesian optimal posterior with the Bayesian posterior and rewrites the bound using marginal likelihood. The result is valid only after addressing the loss's unboundedness.

  • The Bayesian setup defines a prior over parameters, probabilistic estimators, likelihoods, and the posterior through Bayes' rule.
  • Under negative log-likelihood loss and proper parameterization, the optimal PAC-Bayes posterior coincides with the Bayesian posterior.
  • Minimizing the PAC-Bayes bound is equivalent to maximizing the Bayesian marginal likelihood.
  • The marginal likelihood encodes a trade-off between averaged negative log-likelihood and prior-posterior KL divergence.
  • Because negative log-likelihood is generally unbounded, existing bounded-loss PAC-Bayesian theorems do not directly suffice; the paper therefore extends the analysis to unbounded losses.

4 PAC-Bayesian Bounds for Regression

The paper extends PAC-Bayesian generalization guarantees from bounded classification losses to real-valued regression losses, including sub-Gaussian and sub-gamma families. These results support analysis of negative log-likelihood and Bayesian linear regression.

  • Scope: The section extends PAC-Bayesian results to real-valued unbounded losses, focusing on regression rather than the usual classification setting.The bounds apply to bounded, sub-Gaussian, or sub-gamma losses.
  • Bound behavior: For bounded losses, choosing λ := n can leave the bound at least 1/2(b − a)^2 even as n →∞, whereas λ := √n gives convergence.The fixed choice λ := n has the same trade-off as the earlier theorem but can prevent the bound from vanishing asymptotically.
  • Sub-Gaussian losses: Sub-Gaussian losses yield PAC-Bayesian generalization bounds under a variance-factor assumption.The sub-Gaussian condition bounds the loss’s moment generating function by that of a normal distribution with variance s^2.
  • Sub-gamma losses: Sub-gamma losses yield a new PAC-Bayesian result for unbounded regression losses, under variance factor s^2 and scale parameter c < 1.This result is introduced specifically to support the later linear-regression analysis.
  • Linear regression: The sub-gamma parameters depend on the loss, prior, and data-distribution assumptions, as illustrated for squared loss with a Gaussian prior in linear regression.The section uses this setting to instantiate the general sub-gamma framework.
  • Regression versus classification: The regression results bound the expected loss of a stochastic predictor, while convex losses also permit comparison with the averaged regressor through Jensen’s inequality.This differs from classification, where Gibbs-risk bounds can be loose or unrepresentative of majority-vote error.

5 Analysis of Model Selection

The paper links PAC-Bayesian model selection to Bayesian model evidence by evaluating bounds for candidate models and relating the lowest bound to the highest marginal likelihood. It also extends the comparison to hierarchical model averaging.

  • Model selection: PAC-Bayesian model selection evaluates the bound for each candidate model and selects the model with the lowest bound.This procedure is closely linked to Bayesian model selection through the negative log-likelihood formulation.
  • Bayesian connection: The Bayesian Occam’s razor criterion chooses the model with higher model evidence, matching the PAC-Bayesian bound-selection rule.The connection interprets model evidence through the complexity-accuracy trade-off represented by PAC-Bayesian bounds.
  • Model selection: Under a uniform prior over models, selecting the highest model evidence is equivalent to selecting the model with the lowest PAC-Bayesian bound.Corollary 6 formally establishes this equivalence with probability at least 1 − δ under the stated sub-gamma assumptions.
  • Hierarchical Bayes: Hierarchical Bayes introduces a hyperprior over hyperparameters and conditions the parameter prior on the selected hyperparameter.This provides the setup for proper inference over hyperparameters rather than only selecting among fixed models.
  • Hierarchical Bayes: Model averaging uses a sum of marginal likelihoods, whereas selecting the best model uses the maximum, yielding a tighter bound for the hierarchical representation.A deterministic hyperposterior recovers the single-model bound, allowing the bound values to quantify the consequence of selection versus averaging.

6 Linear Regression

The section formulates Bayesian linear regression in PAC-Bayesian terms and evaluates model selection and generalization bounds on polynomial and synthetic regression tasks.

  • Bayesian linear regression: Bayesian linear regression uses Gaussian likelihoods with fixed observation and prior variances, yielding a Gibbs optimal posterior defined through the design matrix.The posterior uses A := 1/σ2 ΦTΦ + 1/σ2π I and bw := 1/σ2 A−1ΦT y.
  • Bayesian linear regression: The negative log marginal likelihood decomposes into data-fit, regularization, determinant, and trace-related terms.Its displayed expression includes the residual norm, prior-weighted parameter norm, log determinant, and trace correction terms.
  • PAC-Bayesian formulation: Under the stated parameterization, the Bayesian regression optimization problem corresponds to minimizing a PAC-Bayesian bound balancing expected negative log-likelihood and complexity.The complexity contribution simplifies through the trace identity to d/2 in the presented derivation.
  • Model selection experiment: For polynomial models trained on 15 noisy samples, the marginal likelihood identifies degree d = 3 as the simplest model explaining the data well.The empirical risk drops sharply from d = 2 to d = 3, while the KL complexity term increases with degree.
  • Model selection experiment: For d ≥4, generalization risk tends to increase, whereas the empirical risk improves only slightly after degree 3.The test generalization risk is computed on a sample of size 1000.
  • Empirical comparison of bounds: For unbounded sub-gamma losses, Corollary 5 gives tighter guarantees than the two cropped-loss bounds up to n=10^6 in the studied synthetic regression setting.Its parameters are approximately s2 ≃ 0.280 and c ≃ 0.005; the alternative λ = 1/√n bound is useful only for large samples, n ≳10^5.

7 Conclusion

The conclusion presents a bridge between Bayesian inference and PAC-Bayesian analysis and extends PAC-Bayesian generalization bounds to unbounded sub-gamma losses in regression.

  • Contributions: Under proper parameterization, minimizing the PAC-Bayesian bound maximizes the Bayesian marginal likelihood.This connection links Bayesian model selection with the PAC-Bayesian complexity-accuracy trade-off.
  • Contributions: The paper proves PAC-Bayesian generalization bounds for regression with unbounded sub-gamma losses, including the squared loss used in regression tasks.The conclusion frames Bayesian linear regression as an application of this extension.
  • Implications: The authors study model selection and suggest that Bayesian predictors can benefit from frequentist PAC-Bayesian guarantees under the i.i.d. assumption.They also suggest incorporating Bayesian tools into PAC-Bayesian algorithms and risk-bounding techniques.

A.1 Related Work

Related work connects PAC-Bayesian theory with Bayesian inference through shared divergences, losses, and learning-rate ideas, while differing in bounds, marginal likelihood, or motivation.

  • Seeger (2002, 2003): Seeger applied PAC-Bayesian theorems to bound Gaussian-process classification generalization error using a Bernoulli Kullback-Leibler divergence.This work is cited as an earlier PAC-Bayesian application rather than as a marginal-likelihood analysis.
  • Banerjee (2006): Banerjee connects early PAC-Bayesian results with Bayesian log-loss bounds through a shared compression lemma equivalent to the paper’s change-of-measure proof step.Banerjee’s result bounds training loss in online learning rather than generalization loss and does not address marginal likelihood or model selection.
  • Zhang (2006): Zhang’s information-theoretic bounds yield the same optimal Gibbs posterior, and negative log-likelihood produces the Bayesian posterior without connecting it to marginal likelihood.The bounded quantity is not directly the generalization error.
  • Grünwald (2012): Grünwald’s Safe Bayesian algorithm selects a learning rate for misspecified models and links marginal likelihood to the PAC-Bayesian trade-off.Unlike the current paper, it does not compute explicit bounds on generalization loss.
  • Bissiri et al. (2016): Bissiri et al.’s loss-based Bayesian framework coincides with Bayesian updating for negative log-likelihood but has different motivation and construction from PAC-Bayesian theory.The relationship is presented as a conceptual connection rather than an identity of frameworks.

A.2 Proof of Theorem 3

The proof of Theorem 3 is presented through a standard PAC-Bayesian sequence using change of measure, Markov’s inequality, and a high-probability uniform statement.

  • Proof strategy: The proof begins with the Donsker–Varadhan change-of-measure identity for a measurable function on the predictor space.This alternative proof follows the general PAC-Bayesian strategy highlighted in the cited theorem lineage.
  • Proof strategy: Markov’s inequality is applied to an expectation-based random variable constructed from the prior-weighted loss expression.This converts the expectation control into a probabilistic statement over the sampled dataset.
  • Proof conclusion: The resulting claim holds with probability at least 1−δ over the dataset and simultaneously for every posterior distribution on the predictor space.The uniformity over posteriors is the key form of the PAC-Bayesian guarantee stated in the proof.

A.3 Proof of Equations (13) and (14)

The proof develops the PAC-Bayesian and Bayesian expressions for linear regression, showing how the posterior, marginal likelihood, and sub-gamma control are connected.

  • Squared-loss regression: The regression setting uses linear predictors with a Gaussian prior, Gaussian inputs, and Gaussian observation noise under squared loss.The model specifies f_w(x)=w·x, x∼N(0,σ_x^2I), y=w*·x+ϵ, and ℓ_sqr(w,x,y)=(w·x−y)^2.
  • Sub-gamma control: For unbounded squared-loss analysis, the proof seeks variance factor s^2 and scale parameter c satisfying the sub-gamma moment-generating-function criterion.The criterion is ψ_v(λ)≤λ^2s^2/[2(1−cλ)] for λ in the stated domain.
  • Posterior derivation: The Gibbs optimal posterior is Gaussian with precision matrix A:=σ^-2Φ^TΦ+σ_π^-2I and mean b_w:=σ^-2A^-1Φ^Ty.Here Φ is the n×d design matrix and y is the vector of observed labels.
  • Marginal-likelihood decomposition: The PAC-Bayesian trade-off decomposes into a data-fit term, prior-penalty term, determinant term, and trace-related terms.The displayed decomposition contains the residual norm, n/2 log(2πσ^2), posterior norm, log|A|, trace(A^-1), and dimension-dependent terms.
  • Marginal-likelihood decomposition: The trace terms cancel through the expectation of the quadratic form and the definition of A, yielding the classic negative log marginal likelihood.Line (†) is identified with the standard Bayesian linear-regression negative log marginal likelihood.
Loading 1605.08636v4…