Fast PAC-Bayes Rates Under Bernstein Conditions

Why a Variance Condition Can Give a Faster Rate

A usual PAC-Bayes generalization bound often balances empirical performance against a complexity penalty whose scale is proportional to \(1/\sqrt{n}\). In some problems, however, predictors that are already close to optimal also have less variable excess loss. When the variance of excess loss is bounded by a constant times its mean, this relationship can support a faster rate: the complexity contribution can scale as \(1/n\), rather than \(1/\sqrt{n}\).

The key is to compare each predictor with a fixed risk minimizer. Its excess loss is signed: it can be negative on some observations even though its expected value is nonnegative. The Bernstein condition controls the variance of this signed quantity, and an exponential-moment argument turns that control into a PAC-Bayes bound.

Because \(h^*\) is a risk minimizer, \(r(h)\ge0\). Since the losses lie in \([0,1]\), \(X_h(Z)\in[-1,1]\) and \(r(h)\in[0,1]\). The condition is meaningful even when the excess loss sometimes takes negative values: it controls its variance, not its pointwise sign.

The Exponential-Moment Step

We first establish the concentration inequality used in the PAC-Bayes argument. The proof is included to make clear why the temperature has an upper limit and where the constant \(2/3\) comes from.

Proof. Expand the exponential in its power series. The linear term vanishes because \(E[Y]=0\). For every integer \(k\ge2\), \(\displaystyle |E[Y^k]|\le E[|Y|^k]\le b^{k-2}E[Y^2]\). Also, \(k!\ge 2\cdot3^{k-2}\) for \(k\ge2\): equality holds for \(k=2,3\), and multiplying by \(k+1\ge3\) preserves the inequality at each subsequent step. Thus, with \(0\le tb<3\),

The last inequality is \(1+u\le e^u\) for \(u\ge0\). The power-series operations are valid because \(Y\) is bounded, so the exponential series is absolutely integrable. \(\square\)

For a fixed predictor \(h\), apply the lemma to \(Y=r(h)-X_h(Z)\). It has mean zero. Moreover, \(X_h(Z)\in[-1,1]\) and \(r(h)\in[0,1]\), so \(|Y|\le2\). Its variance is \(\operatorname{Var}(X_h(Z))\). The lemma therefore applies when \(0<\lambda<3/2\).

Independence of the observations lets us multiply the one-observation moment bounds. Define \(\displaystyle a_\lambda=1-\frac{\lambda B}{2(1-2\lambda/3)}\). Then

Indeed, the exponent inside the expectation equals \(\lambda\sum_{i=1}^n(r(h)-X_h(Z_i))-n\lambda^2B r(h)/(2(1-2\lambda/3))\). The expectation of its exponential is bounded by the product of \(n\) identical one-observation bounds, with the second term exactly canceling the resulting upper bound.

A Uniform PAC-Bayes Fast-Rate Bound

Let \(P\) be a prior probability distribution on predictors, fixed independently of the sample. A posterior \(Q\) may depend on the sample. For distributions \(Q\) absolutely continuous with respect to \(P\), \(\operatorname{KL}(Q\|P)\) denotes their Kullback–Leibler divergence. Define posterior-averaged excess risks by \(r(Q)=E_{h\sim Q}[r(h)]\) and \(\hat r(Q)=E_{h\sim Q}[\hat r(h)]\).

Proof. For each predictor, the exponential bound just derived holds. Integrating it with respect to \(P\) gives \(\displaystyle E_{Z_1^n} E_{h\sim P}[\exp\{\lambda n(a_\lambda r(h)-\hat r(h))\}]\le1\). By Markov's inequality, with probability at least \(1-\delta\), the inner prior expectation is at most \(1/\delta\).

On that event, use the change-of-measure inequality \(\displaystyle E_Q[g]\le\operatorname{KL}(Q\|P)+\log E_P[e^g]\). For completeness, this inequality follows by writing the \(Q\)-expectation on the part of the space where \(Q\) has density relative to \(P\), and applying Jensen's inequality to the logarithm. Applying it to \(g(h)=\lambda n(a_\lambda r(h)-\hat r(h))\) yields \(\displaystyle \lambda n(a_\lambda r(Q)-\hat r(Q))\le\operatorname{KL}(Q\|P)+\log(1/\delta)\). Dividing by the positive quantity \(\lambda n a_\lambda\) proves the assertion. The event was defined using the prior expectation alone, so it holds for every such \(Q\), including posteriors chosen after seeing the sample. \(\square\)

Choosing a Temperature for a Fast Rate

The theorem holds for any admissible temperature, but its constants depend on \(\lambda\). A convenient choice that works uniformly for \(B\ge1\) is \(\lambda=1/(2B)\). It lies strictly between zero and \(3/2\), and

The inequality follows from \(B\ge1\), which implies \(1-1/(3B)\ge2/3\). Substitution into the theorem gives the explicit consequence

Thus, when the posterior's empirical excess risk is zero or of the same order as the complexity term, the resulting excess-risk bound scales as \(B\{\operatorname{KL}(Q\|P)+\log(1/\delta)\}/n\). This is the fast-rate dependence: the variance assumption has changed the complexity scale from a square-root dependence on sample size to a dependence proportional to \(1/n\).

Common Pitfalls and Interpretation

• Including zero as a valid temperature. The condition \(a_\lambda>0\) alone does not rule out \(\lambda=0\), since \(a_0=1\). But the bound divides by \(\lambda n\). The theorem therefore requires \(0<\lambda<3/2\), as well as \(a_\lambda>0\).
• Treating excess loss as nonnegative. Although \(r(h)\ge0\), the observation-level difference \(X_h(Z)\) can be negative. The proof uses its boundedness in \([-1,1]\) and a variance condition; it does not assume \(X_h(Z)\in[0,1]\).
• Dropping the positivity condition on \(a_\lambda\). A positive temperature below \(3/2\) makes the moment bound valid, but the final division also requires \(a_\lambda>0\). A temperature satisfying only the first condition is not necessarily admissible.
• Calling the rate fast without considering empirical excess risk. The theorem includes \(\hat r(Q)\). A \(1/n\)-scale complexity term alone does not imply a \(1/n\)-scale total bound unless the empirical excess-risk term is suitably small.