Kullback-Leibler Divergence

Kullback-Leibler divergence appears in the PAC-Bayes theorem as a way to compare two distributions over hypotheses. The theorem compares the expected loss associated with a distribution Q over hypotheses with the loss measured on an i.i.d. training set. It also includes the divergence KL(Q||P), where P is a prior distribution over hypotheses. The result is a bound containing the training-set loss plus a square-root term involving KL(Q||P), the training-set size m, and the confidence parameter δ.

The PAC-Bayes theorem gives a mathematical bound on the generalization error of a hypothesis class. In schematic form, it says that the expected loss associated with Q is bounded by the loss measured on the training set, plus a square-root term. That square-root term contains KL(Q||P), the sample size m, and the confidence parameter δ. The source material does not specify the exact constants or the complete algebraic form of the square-root term, so the important structure is the separation between the observed training loss and the complexity contribution.

The theorem therefore does not use KL(Q||P) as a replacement for the training loss. The two quantities have different jobs. L_S(Q) records the loss associated with Q on the particular training set S, while KL(Q||P) measures the difference between Q and the reference distribution P. The bound combines them.

KL divergence measures the difference between Q, the distribution over hypotheses, and P, the prior distribution. In the PAC-Bayes bound, KL(Q||P) is part of the square-root term. Consequently, the comparison between Q and P contributes to the quantity added to the training-set loss. The source material emphasizes the role of this comparison, but does not provide numerical values or an explicit monotonicity calculation. The safe interpretation is that KL(Q||P) is the divergence-based component used to control the bound.

At a high level, the proof uses Markov's inequality to move from an expectation over training sets to a statement that holds with high probability over the sampled training set. The expectation describes average behavior across training sets. Markov's inequality then supplies a probability control for exceeding a specified level. In the PAC-Bayes statement, this produces a confidence parameter δ and the phrase with probability at least 1 - δ over an i.i.d. training set.

This is a statement about the random training set, not a claim that every possible training set satisfies the inequality. The training set is sampled independently and identically from the data distribution, and the theorem says that the inequality holds with probability at least 1 - δ over that sampling process.