PAC-Bayes Risk Bounds for Squared-Error Regression

Why Squared-Error PAC-Bayes Bounds Need a Range

Squared-error regression is familiar, but its loss is not automatically bounded: if either the outcome or a predictor’s output can grow without limit, then \((h(X)-Y)^2\) can also grow without limit. A bounded-loss PAC-Bayes inequality therefore applies only after the outcome and predictions have been restricted to a common finite interval, or after a justified transformation that gives a bounded loss. The range is part of the statistical model, not a technical detail that can be ignored.

Let \((X,Y)\) have distribution \(\mathcal D\), and let a sample \(S=((X_1,Y_1),\ldots,(X_n,Y_n))\) consist of independent observations from \(\mathcal D\). A predictor \(h\) maps an input \(x\) to a numerical prediction. We consider a prior distribution \(P\) over a measurable predictor class, fixed independently of \(S\), and a posterior distribution \(Q\), which may depend on \(S\). Assume that, for fixed finite \(L<U\), outcomes satisfy \(Y\in[L,U]\) almost surely and every predictor in the support of \(P\) and \(Q\) predicts in \([L,U]\) on the input domain of interest. Write \(D=U-L>0\).

Because both \(h(x)\) and \(y\) lie in an interval of width \(D\), their absolute difference is at most \(D\). Thus \(0\leq\ell_h(x,y)\leq1\). This normalization lets us use a bounded-loss result directly. It also gives an exact conversion back to the original squared-error scale: \(D^2R(Q)\) is the expected Gibbs squared error in the original units.

The PAC-Bayes-KL Bound for Squared Error

We use the PAC-Bayes-KL inequality. It applies to a bounded loss and provides one event on which the guarantee holds simultaneously for every posterior, including a posterior selected after observing the sample. For \(a,b\in[0,1]\), define the binary relative entropy by \(\operatorname{kl}(a\|b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))\), with the usual continuous endpoint conventions.

The right-hand side has two components. The divergence term measures how far the chosen posterior moves from the prior; the confidence term depends on sample size and the requested failure probability. Let \(c_Q=(\operatorname{KL}(Q\|P)+\log(2\sqrt n/\delta))/n\). On the stated event, the binary relative entropy is bounded above by \(c_Q\). This is a constraint on the pair of risks, not an additive risk-gap bound. In particular, a large \(c_Q\) can make the implied risk guarantee weak; it does not change the fact that the inequality bounds binary relative entropy by \(c_Q\).

For a convenient upper-risk interpretation, fix \(r=\hat R_S(Q)\) and define \(q_{\mathrm{up}}(r,c)=\sup\{q\in[r,1]:\operatorname{kl}(r\|q)\leq c\}\). The PAC-Bayes-KL inequality implies \(R(Q)\leq q_{\mathrm{up}}(r,c_Q)\). The endpoint \(q=1\) is included, so the definition remains meaningful when the constraint is too weak to improve on the trivial bound. In original squared-error units, the resulting upper bound is \(D^2q_{\mathrm{up}}(r,c_Q)\).

What Is Being Averaged?

The empirical Gibbs risk averages in two stages: first the observed normalized squared loss is averaged over the sample, then that quantity is averaged over predictors drawn from \(Q\). If \(h_1,\ldots,h_m\) have posterior probabilities \(q_1,\ldots,q_m\), then \(\hat R_S(Q)=\sum_{j=1}^m q_j\hat R_S(h_j)\), where \(\hat R_S(h_j)=n^{-1}\sum_{i=1}^n\ell_{h_j}(X_i,Y_i)\). This is the risk of a randomly drawn predictor under the posterior, averaged over that draw. It is not obtained by squaring an average residual: averaging squared losses and squaring an average prediction are generally different operations.

To verify the conversion, the definition of normalized loss gives \(\ell_h(x,y)=(h(x)-y)^2/D^2\) for every predictor, input, and outcome under consideration. Taking the empirical average and then the expectation over \(Q\) preserves division by the constant \(D^2\), giving the first identity. Taking population expectation and posterior expectation gives the second identity for the same reason. Substituting the normalized empirical risk into the upper-risk form of the theorem gives the displayed raw-scale guarantee. No assumption about the posterior beyond those in the theorem is added by this rescaling. \(\square\)

Worked Risk-Bound Calculations

Range Choices, Interpretation, and a Common Pitfall

The range assumption determines the scale of the guarantee. If an outcome is known to lie in \([L,U]\), constrain predictions to that same interval to obtain the normalized loss above. In practice, clipping a raw prediction to \([L,U]\) can enforce this condition, but it changes the predictor: the resulting guarantee concerns the clipped predictor. If predictions or outcomes can fall outside the interval, the claimed pointwise loss bound may fail. One cannot justify a bounded-loss theorem merely by noting that observed residuals in a particular sample were small.

The bound controls the posterior-averaged risk of a Gibbs predictor. Its empirical side must therefore average squared loss over the posterior, not substitute a single favored predictor unless the posterior is actually concentrated on it. A posterior with small empirical risk can still incur a substantial divergence penalty if it puts weight on predictors that were unlikely under the prior. Conversely, increasing the sample size reduces the contribution of a fixed divergence and confidence term through division by \(n\); this does not remove the need for representative independent observations or correct range conditions.

Common mistake: It is tempting to calculate unnormalized squared errors and insert them directly into a PAC-Bayes-KL inequality, or to assert that bounded observed errors make the loss bounded. The correction is to establish a population-level range condition first, divide squared error by \(D^2\), and apply the theorem to a loss in \([0,1]\). Only after obtaining the normalized risk statement should it be multiplied by \(D^2\) to return to the original units. The binary relative entropy is bounded above by \(c_Q\) on the theorem’s event; a weak threshold makes the resulting risk information weak, but does not erase or alter that inequality.