Finite-Collection Penalty Calibration

Why Penalties Need Calibration

Penalized empirical risk compares candidate models by adding a complexity cost to each model’s observed error. The penalty should do more than rank models according to a convenient notion of size: it should also reflect how much uncertainty is introduced by comparing several candidates. If each candidate has a risk bound that holds with high probability on its own, those separate guarantees do not automatically hold for the collection all at once.

Finite-collection calibration turns individual risk bounds into penalties that account for this multiple-model search. The key ingredients are a total failure probability, an allocation of that probability across models, and the form of each model’s individual bound. This tutorial develops the calibration step; it does not require all candidate models to have the same complexity or the same risk-bound formula.

From an Individual Bound to a Collection Penalty

Let \(\mathcal M_1,\ldots,\mathcal M_K\) be a finite collection of candidate model classes. Model \(j\) produces a fitted predictor \(\hat f_j\), with empirical risk \(\hat R_j\) and true risk \(R_j\). Here \(R_j\) is the risk of the fitted predictor on a fresh observation, conditional on the training data; both \(R_j\) and \(\hat R_j\) can therefore be random through the training data.

Suppose that for each model \(j\), a valid individual risk bound is available: for every \(t\geq 0\),

where \(\psi_j(t)\) is a nondecreasing function of \(t\). The function may depend on the sample size, the model’s complexity, and assumptions on the loss and data. This assumption is not a universal concentration formula: it must be justified for the particular setting. For example, if a class contains many predictors and fitting uses the same data on which empirical risk is computed, the bound must account for that fitting and search within the class.

The weight \(w_j\) determines how much of the total failure-probability budget is assigned to model \(j\). A larger weight gives that model a smaller confidence threshold and, because \(\psi_j\) is nondecreasing, a smaller penalty. A smaller weight gives a larger penalty. Equal weights \(w_j=1/K\) yield the familiar threshold \(\log(K/\delta)\), but unequal weights can reflect differing model complexities.

Proof. For each \(j\), substitute \(t_j=\log(1/(\delta w_j))\) into the individual bound. This value is nonnegative because \(\delta w_j\leq 1\), and \(e^{-t_j}=\delta w_j\). Therefore

The probability that at least one of these inequalities fails is no greater than the sum of their failure probabilities. Thus

Taking the complementary event proves the stated simultaneous guarantee. \(\square\)

This result calibrates the penalties; by itself, it does not claim that a particular selection rule is optimal. In penalized empirical risk selection, one commonly chooses a model minimizing \(\hat R_j+\operatorname{pen}_j\). Calibration ensures that the penalty levels have a collection-wide risk interpretation, rather than merely being separate model-by-model adjustments.

Choosing the Allocation

Equal allocation is natural when the models have comparable individual bounds. If the models differ substantially, weights can give more of the confidence budget to models for which a smaller penalty is especially valuable. Weights should be specified without using the observed outcomes in a way that invalidates the individual guarantees. A data-dependent allocation needs its own justification; it is not automatically covered by the theorem.

There is a precise reason equal allocation is a sensible default when all models have the same bound.

Derivation. For any valid allocation, at least one weight is at most \(1/K\). Otherwise all \(K\) weights would exceed \(1/K\), and their sum would exceed one. For an index \(j\) with \(w_j\leq1/K\),

Monotonicity gives \(\operatorname{pen}_j\geq\psi(\log(K/\delta))\), so the largest penalty cannot be smaller than this value. Equal weights make every penalty exactly \(\psi(\log(K/\delta))\), attaining that lower bound. \(\square\)

When the individual bounds differ, the result above no longer identifies an optimal allocation. The allocation is then a design choice: weights can be tilted toward simpler models, or toward models whose penalties most affect the intended selection. Whatever the choice, the weights must sum to at most one, and the resulting penalty for each model must still use its own valid function \(\psi_j\).

Worked Penalty Calibrations

Common Mistake and Practical Interpretation

A common mistake is to use the desired failure probability \(\delta\) separately for every model. That gives \(t=\log(1/\delta)\) for each penalty. The resulting individual guarantees are valid, but their failure probabilities can add across models; with \(K\) models, the resulting collection-wide failure probability is bounded only by \(K\delta\), not by \(\delta\). The correction is to allocate the total budget, for example by using \(\delta/K\) per model or, more generally, \(\delta w_j\).

Calibration also clarifies what a penalty does and does not say. It is not a universal surcharge determined by the number of parameters alone. It is built from an individual risk bound, a confidence target, and a specified allocation. If the individual bound is loose, the calibrated penalty will be loose; if the assumed bound does not account for fitting within a class, the penalty cannot repair that omission. Conversely, a well-calibrated penalty gives a principled way to compare candidate empirical risks while accounting for the finite search.