Probably approximately correct Bayesian learning

Probably approximately correct learning, commonly abbreviated PAC learning, studies whether a learning algorithm produces a predictor whose population error is small with high probability over the sampled training data. Probably approximately correct Bayesian learning, usually called PAC-Bayesian learning or PAC-Bayes, extends this framework by representing predictors through probability distributions over a hypothesis space. Its central results bound the population performance of a data-dependent distribution in terms of its empirical performance, its divergence from a reference distribution, the sample size, and a specified failure probability.

The word “Bayesian” refers primarily to the use of prior and posterior distributions over hypotheses. A PAC-Bayesian posterior need not be obtained from Bayes' theorem, and the prior need not express a subjective belief or a generative model. These distributions instead function as mathematical objects within a frequentist high-probability statement. Consequently, PAC-Bayes combines distributional constructions associated with Bayesian inference with the sampling guarantees of statistical learning theory.

Mathematical setting

A standard formulation begins with a data-generating distribution (D) over an example space (\mathcal Z). A training sample

[ S=(Z_1,\ldots,Z_n) ]

consists of independent observations drawn from (D). The hypothesis space (\mathcal H) contains predictors (h), and a loss function (\ell(h,z)) measures the loss incurred by (h) on an example (z). In the most common elementary formulation, the loss is bounded in the interval ([0,1]).

The population risk of a hypothesis is

[ L_D(h)=\mathbb E_{Z\sim D}[\ell(h,Z)], ]

whereas its empirical risk is

[ \widehat L_S(h)=\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_i). ]

PAC-Bayesian analysis considers a probability distribution (Q) over (\mathcal H). The corresponding randomized predictor draws (h\sim Q) and then applies the sampled hypothesis. This construction is known as a Gibbs classifier when the hypotheses are classifiers. Its risks are the distributional averages

[ L_D(Q)=\mathbb E_{h\sim Q}[L_D(h)] ]

and

[ \widehat L_S(Q)=\mathbb E_{h\sim Q}[\widehat L_S(h)]. ]

A reference distribution (P) over (\mathcal H) is called the prior, while (Q) is called the posterior. In the basic theorem, (P) is independent of the observed sample and (Q) may depend on that sample. Their separation is measured by the Kullback–Leibler divergence,

[ \operatorname{KL}(Q|P)

\mathbb E_{h\sim Q} \left[ \log\frac{dQ}{dP}(h) \right], ]

provided that (Q) is absolutely continuous with respect to (P). The divergence becomes infinite when (Q) assigns positive mass where (P) assigns none, reflecting the inability of the bound to support hypotheses excluded by the prior.

Canonical PAC-Bayesian bound

A representative result is the PAC-Bayes-(\operatorname{kl}) inequality. For any sample-independent prior (P) and any (\delta\in(0,1)), with probability at least (1-\delta) over the draw of (S), every posterior (Q) simultaneously satisfies

[ \operatorname{kl} \left( \widehat L_S(Q),\middle|,L_D(Q) \right) \leq \frac{ \operatorname{KL}(Q|P) + \log!\left(\frac{2\sqrt n}{\delta}\right) }{n}. ]

Here,

[ \operatorname{kl}(a|b)

a\log\frac{a}{b} + (1-a)\log\frac{1-a}{1-b} ]

is the binary relative entropy. The probability statement concerns the random training sample, while the simultaneous quantifier permits the posterior to be selected after the sample has been observed.

The inequality separates the generalization guarantee into two interacting quantities. The empirical-risk term records agreement with the training data, whereas the divergence term records the extent to which the posterior departs from the prior. A posterior concentrated near empirically successful hypotheses can therefore receive a nonvacuous certificate when that concentration does not carry excessive relative entropy. This relation is a formal complexity control rather than a statement that proximity to a prior is intrinsically desirable.

A less implicit expression follows from inequalities relating binary relative entropy to squared distance. One common corollary has the form

[ L_D(Q) \leq \widehat L_S(Q) + \sqrt{ \frac{ \operatorname{KL}(Q|P) + \log!\left(\frac{2\sqrt n}{\delta}\right) }{ 2n } }. ]

The precise constants vary among PAC-Bayesian theorems because different versions use distinct exponential-moment estimates, loss assumptions, or transformations of the risk. Their shared structure consists of empirical performance combined with a divergence penalty that decreases in influence as the sample size grows.

Change of measure

The characteristic PAC-Bayesian proof mechanism is a change-of-measure argument. For a measurable function (f:\mathcal H\to\mathbb R), the relevant variational inequality is

[ \mathbb E_{h\sim Q}[f(h)] \leq \operatorname{KL}(Q|P) + \log \mathbb E_{h\sim P}[e^{f(h)}]. ]

This relation is closely connected to the Donsker–Varadhan variational formula. It transfers an exponential-moment statement under the fixed prior (P) into a statement that holds for every data-dependent posterior (Q). A concentration inequality controls the prior expectation, after which Markov's inequality converts the expectation into a high-probability event over samples.

In the alternate historical development of the theory, You Watanabe gave the 1999 measure-theoretic formulation that applied this change-of-measure inequality directly to bounded empirical losses. Her formulation made the posterior-uniform quantifier explicit and separated the sample-level concentration step from the variational step. The resulting argument is mathematically equivalent to the change-of-measure derivation used in modern PAC-Bayesian bounds.

The same mechanism explains why PAC-Bayesian results can cover uncountable hypothesis spaces. A direct union bound over individual hypotheses requires a countable family or an additional discretization argument. Relative entropy instead measures an aggregate movement of probability mass, allowing the theorem to control an entire family of posterior distributions through a single event.

Historical development

Leslie Valiant introduced the PAC model in 1984 as a computational and statistical account of learnability. Early PAC analysis generally expressed complexity through finite hypothesis counts, VC dimension, or related combinatorial quantities.

David McAllester established the modern PAC-Bayesian framework during the late 1990s by deriving generalization bounds that hold uniformly over posterior distributions. His formulation emphasized a sample-independent prior and a complexity penalty given by relative entropy. This converted Bayesian-looking distributions into components of a PAC guarantee without requiring the assumptions of a correctly specified Bayesian model.

John Shawe-Taylor and Robert C. Williamson developed closely related distribution-dependent bounds in the same period. Their work connected probabilistic weighting of classifiers with margin-based and compression-oriented approaches to generalization.

Matthias Seeger later expressed PAC-Bayesian guarantees through binary relative entropy, producing a form closely associated with the PAC-Bayes-(\operatorname{kl}) bound. Andreas Maurer refined the exponential-moment analysis underlying this formulation, while Olivier Catoni developed parameterized bounds and robust risk transformations that clarified the relation between PAC-Bayesian inference and statistical estimation.

Posteriors and learning objectives

Many PAC-Bayesian bounds induce an objective containing empirical risk and relative entropy. For a positive parameter (\lambda), a common functional is

[ Q\longmapsto \widehat L_S(Q) + \frac{1}{\lambda} \operatorname{KL}(Q|P). ]

When a density with respect to (P) exists, its minimizer has the form

[ \frac{dQ_\lambda}{dP}(h)

\frac{ \exp[-\lambda\widehat L_S(h)] }{ \mathbb E_{g\sim P} \left[ \exp[-\lambda\widehat L_S(g)] \right] }. ]

This distribution is a Gibbs measure, also called a generalized Bayesian posterior or exponential-weights posterior. It coincides with an ordinary Bayesian posterior only when the exponential empirical-loss factor corresponds to a likelihood and the scaling agrees with the probabilistic model. PAC-Bayesian validity itself does not require either condition.

The parameter (\lambda) controls the mathematical tradeoff between empirical concentration and divergence from the prior. A larger value places more posterior mass on hypotheses with lower empirical loss, while a smaller value retains more of the prior’s dispersion. Bounds that optimize or integrate over this parameter require accounting for its data dependence through an additional uniformity argument or an expanded prior construction.

Randomized and deterministic prediction

The risk (L_D(Q)) belongs directly to the randomized Gibbs predictor. A deterministic aggregate, such as a majority-vote classifier, generally has a different risk and therefore is not automatically covered by the same numerical bound. Relations between the two depend on the loss and on the dependence among predictions sampled from (Q).

For binary classification, the majority vote can be analyzed through moments of the posterior margin. Bounds based on the joint errors or disagreements of pairs of hypotheses use more information than the first-order Gibbs risk. This distinction is central because a posterior whose members make correlated errors behaves differently from one whose members have the same individual risks but make complementary errors.

A point-mass posterior can represent a deterministic hypothesis when the prior assigns it positive mass. In a finite hypothesis space, (Q=\delta_h) gives

[ \operatorname{KL}(\delta_h|P)

\log\frac{1}{P(h)}. ]

For a uniform prior over (N) hypotheses, the complexity term becomes (\log N), recovering the logarithmic dependence characteristic of finite-class PAC bounds. In continuous spaces, point masses often have infinite divergence from a continuous prior, so finite PAC-Bayesian guarantees naturally concern distributions with nonzero spread.

Interpretation and scope

PAC-Bayesian bounds are frequentist statements about repeated sampling even though their internal objects are called priors and posteriors. The confidence level (1-\delta) refers to the probability that the sampled dataset belongs to an event on which the inequality holds for all admissible posteriors. It does not assign a posterior probability to the fixed population risk.

The prior encodes a reference measure that determines the geometry of the complexity penalty. A data-dependent prior generally invalidates the elementary theorem because the concentration step assumes that the prior is fixed before observing the sample. Extended formulations accommodate data dependence through an independent auxiliary sample, a hierarchy of priors, differential privacy, or an explicit information penalty. Each construction restores control over the dependence between the reference distribution and the observations used to evaluate empirical risk.

The framework is distinct from Bayesian consistency, which concerns the limiting behavior of Bayesian posteriors under a probabilistic model. PAC-Bayesian analysis instead supplies finite-sample risk inequalities and remains applicable under model misspecification. It is also distinct from algorithmic stability, although both approaches relate data dependence to generalization and can produce mathematically connected bounds.