Kraft Penalties For Countable Predictor Classes

Why Countable Classes Need Unequal Complexity Costs

For a finite set of predictors, a simultaneous risk bound can distribute a fixed error probability across all candidates. A countably infinite class requires a different allocation: assigning the same positive amount of probability to every candidate would exceed the available total. Kraft weights solve this allocation problem. They assign more probability to simpler or more favored predictors and less to others, producing penalties proportional to negative log weight.

The resulting guarantee holds for every predictor at once, with probability at least the chosen confidence level. It can therefore be applied to a predictor selected from the data, provided the class and its weights were fixed in advance. Throughout, assume the observations $Z_1,\ldots,Z_n$ are independent and identically distributed, and each predictor $f$ has a measurable loss $\ell_f(Z)$ between zero and one.

Definition: Let $\mathcal{F}$ be a finite or countable predictor class. A collection of fixed weights $(\pi_f:f\in\mathcal{F})$ is a set of Kraft weights if $\pi_f>0$ for every $f$ and $$ \sum_{f\in\mathcal{F}}\pi_f\leq 1. $$ For code lengths $L_f$ measured in bits, the weights $\pi_f=2^{-L_f}$ satisfy this condition exactly when $\sum_f 2^{-L_f}\leq 1$, the Kraft inequality. The corresponding complexity cost in natural-log units is $-\log\pi_f$.

For $f\in\mathcal{F}$, define its population risk and empirical risk by

R(f)=E[\ell_f(Z)],\qquad \widehat R_n(f)=\frac{1}{n}\sum_{i=1}^n\ell_f(Z_i).

A small weight means a larger cost: a predictor given only a small share of the total probability budget must meet a more demanding deviation threshold. The key point is that the thresholds can be chosen in a way that all hold simultaneously.

Simultaneous Bounds From Kraft Weights

For a fixed predictor, Hoeffding's inequality applies because its $n$ losses are independent and lie in $[0,1]$. In particular, for every $t>0$,

P\left(\left|\widehat R_n(f)-R(f)\right|>t\right) \leq 2\exp(-2nt^2).

To make this bound simultaneous, allocate predictor $f$ a failure probability $\delta\pi_f$, where $0<\delta<1$. Choosing the deviation threshold to make Hoeffding's right-hand side equal to $\delta\pi_f$ gives the following result.

Theorem: Suppose the observations are independent and identically distributed, all losses are measurable and in $[0,1]$, and $(\pi_f)$ are fixed positive Kraft weights on a finite or countable class $\mathcal{F}$. For $0<\delta<1$, define $$ \operatorname{pen}_{\delta}(f) = \sqrt{\frac{\log(2/(\delta\pi_f))}{2n}}. $$ Then, with probability at least $1-\delta$, every $f\in\mathcal{F}$ satisfies $$ \left|R(f)-\widehat R_n(f)\right| \leq \operatorname{pen}_{\delta}(f). $$

Proof. Fix $f$ and substitute $t=\operatorname{pen}_{\delta}(f)$ into Hoeffding's inequality. Since $2n t^2=\log(2/(\delta\pi_f))$, this gives

P\left(\left|R(f)-\widehat R_n(f)\right|> \operatorname{pen}_{\delta}(f)\right) \leq 2\exp\left(-\log\frac{2}{\delta\pi_f}\right) =\delta\pi_f.

The probability that at least one predictor violates its bound is at most the sum of the individual violation probabilities. This countable union bound is valid for a finite or countable collection of measurable events. Therefore,

P\left(\text{some }f\in\mathcal{F}\text{ violates its bound}\right) \leq \sum_{f\in\mathcal{F}}\delta\pi_f \leq \delta.

The complementary event has probability at least $1-\delta$, as claimed. Countability ensures that the simultaneous event is a measurable countable intersection. $\square$

The penalty separates into a confidence cost and a predictor-specific cost:

\operatorname{pen}_{\delta}(f) = \sqrt{\frac{\log(2/\delta)-\log\pi_f}{2n}}.

Thus complexity enters through $-\log\pi_f$. For losses in $[0,B]$, applying the same argument after scaling the loss by $B$ multiplies the displayed penalty by $B$.

Worked Example: Geometric Weights for an Ordered Class

Suppose $\mathcal{F}=\{f_0,f_1,\ldots\}$, where larger indices represent increasingly complex candidates. Assign $\pi_j=2^{-(j+1)}$ to $f_j$. These are valid weights because

\sum_{j=0}^{\infty}\pi_j =\sum_{j=0}^{\infty}2^{-(j+1)} =\frac{1/2}{1-1/2}=1.

The penalty for $f_j$ is therefore

\operatorname{pen}_{\delta}(f_j) = \sqrt{\frac{\log(2/\delta)+(j+1)\log 2}{2n}}.

For example, with $n=100$, $\delta=0.05$, and $j=2$, the weight is $1/8$. The logarithmic term is $\log(2/(0.05/8))=\log(320)$, approximately $5.768$. Hence the simultaneous deviation allowance for $f_2$ is

\sqrt{\frac{\log(320)}{200}} \approx \sqrt{0.02884} \approx 0.170.

The guarantee applies to all indices, not just $j=2$; higher indices pay larger penalties because their weights are smaller.

Worked Example: Weights for a Two-Index Model Collection

Consider predictors indexed by a model size $k\geq 0$ and a within-model label $m\geq 0$. Set

\pi_{k,m}=\frac{1}{(k+1)(k+2)}\,2^{-(m+1)}.

To check the Kraft condition, first sum over $m$:

\sum_{m=0}^{\infty}2^{-(m+1)}=1.

The other factor is also a probability mass function, since

\frac{1}{(k+1)(k+2)} =\frac{1}{k+1}-\frac{1}{k+2}, \qquad \sum_{k=0}^{\infty}\frac{1}{(k+1)(k+2)}=1.

Consequently $\sum_{k,m}\pi_{k,m}=1$. The penalty for a predictor with indices $(k,m)$ is

\operatorname{pen}_{\delta}(f_{k,m}) = \sqrt{ \frac{ \log(2/\delta)+\log((k+1)(k+2))+(m+1)\log 2 }{2n} }.

For $k=1$ and $m=0$, the weight is $(1/6)(1/2)=1/12$, so the complexity contribution to the numerator is $\log 12$. This allocation charges separately for model size and for the label within that model, while keeping the total weight finite.

From Simultaneous Deviations to an Oracle Inequality

The simultaneous bound supports a direct guarantee for penalized empirical risk minimization. Define the penalized criterion $Q(f)=\widehat R_n(f)+\operatorname{pen}_{\delta}(f)$. A selected predictor need not exactly minimize $Q$; it is enough that its criterion is within a specified tolerance of the infimum.

Theorem: Under the assumptions of the simultaneous bound, suppose a data-dependent $\hat f\in\mathcal{F}$ satisfies $$ \widehat R_n(\hat f)+\operatorname{pen}_{\delta}(\hat f) \leq \inf_{f\in\mathcal{F}} \left\{\widehat R_n(f)+\operatorname{pen}_{\delta}(f)\right\} +\varepsilon $$ for some $\varepsilon\geq 0$. With probability at least $1-\delta$, $$ R(\hat f) \leq \inf_{f\in\mathcal{F}} \left\{R(f)+2\operatorname{pen}_{\delta}(f)\right\} +\varepsilon. $$

Proof. Work on the event where the simultaneous deviation bound holds for every $f$. Its upper-deviation half gives $R(\hat f)\leq\widehat R_n(\hat f)+\operatorname{pen}_{\delta}(\hat f)$. By the approximate minimization condition, for any comparator $f\in\mathcal{F}$,

\begin{aligned} R(\hat f) &\leq \widehat R_n(\hat f)+\operatorname{pen}_{\delta}(\hat f)\\ &\leq \widehat R_n(f)+\operatorname{pen}_{\delta}(f)+\varepsilon\\ &\leq R(f)+2\operatorname{pen}_{\delta}(f)+\varepsilon. \end{aligned}

The final inequality uses the lower-deviation half of the simultaneous bound for $f$. Since the inequality holds for every comparator, taking the infimum over $f$ proves the claim. The event has probability at least $1-\delta$ by the preceding theorem. $\square$

The factor of two has a transparent source: one penalty controls the selected predictor's risk above its empirical risk, and a second controls the comparator's empirical risk above its risk. The conclusion compares the selected predictor with the best risk-plus-complexity tradeoff in the class; it does not claim that the penalized empirical minimizer has the smallest population risk.

Worked Example: Comparing Two Candidates Numerically

Suppose two predictors have weights $\pi_1=1/2$ and $\pi_2=1/8$, which sum to $5/8\leq 1$. Let $n=200$, $\delta=0.05$, and suppose their empirical risks are $0.18$ and $0.17$, respectively. Their penalties are

\operatorname{pen}_{\delta}(f_1) =\sqrt{\frac{\log(80)}{400}} \approx 0.1047,\qquad \operatorname{pen}_{\delta}(f_2) =\sqrt{\frac{\log(320)}{400}} \approx 0.1201.

The penalized criteria are approximately $0.18+0.1047=0.2847$ and $0.17+0.1201=0.2901$. Thus $f_1$ has the smaller criterion and is the exact penalized minimizer in this two-candidate comparison. On the simultaneous event, the oracle calculation gives, for either comparator,

R(f_1)\leq R(f_1)+2(0.1047) \quad\text{and}\quad R(f_1)\leq R(f_2)+2(0.1201).

The first inequality is the self-comparison; the second compares the selected candidate with $f_2$. More usefully, if the two empirical risks are viewed as estimates of unknown risks, the theorem guarantees the second comparison with probability at least $0.95$; the numerical penalty is the price of protecting the lower-weight candidate simultaneously.

Choosing Weights and Avoiding Common Errors

Weights encode which parts of the class should receive the most favorable deviation allowances. If a predictor has a code length $L_f$ in bits and $\pi_f=2^{-L_f}$, then

-\log\pi_f=L_f\log 2.

Thus the penalty is determined by code length, up to the conversion from bits to natural-log units. Weights may also reflect a hierarchy or other structure, as long as their total is at most one. The choice is a statistical design choice: assigning a larger weight gives a smaller penalty, but leaves less weight to allocate elsewhere.

For a finite class of $M$ predictors, the uniform choice $\pi_f=1/M$ recovers a common penalty $\sqrt{\log(2M/\delta)/(2n)}$. This is the finite-class special case. For a countably infinite class, the same uniform assignment is impossible: if each predictor received weight $c>0$, then the sum of weights would be infinite. Assigning zero weight to some predictors is not a remedy for this theorem, because its deviation bound requires a positive weight for every predictor being covered.

A related mistake is to choose weights after inspecting the same sample and then apply the result as though the weights were fixed. The union-bound proof allocates failure probability using the specified weights; sample-adaptive allocation does not automatically preserve that calculation. Likewise, checking only a selected predictor is not a substitute for a simultaneous bound when that predictor was chosen by comparing empirical risks. The simultaneous event is what makes such data-dependent selection valid.

Key takeaway: A summable collection of positive weights turns the countability of a predictor class into explicit complexity costs. With bounded losses, the cost $-\log\pi_f$ yields simultaneous risk control, and penalized empirical risk minimization then satisfies an oracle inequality over the entire class.

Check Your Understanding

Use the definitions and arguments above to answer the following questions.

Why can equal positive weights not be assigned to every member of a countably infinite predictor class while satisfying the Kraft inequality?
For weights $\pi_j=2^{-(j+1)}$, how does the penalty change as the index $j$ increases, and what feature of the allocation causes this change?
In the oracle inequality proof, identify which deviation inequality controls the selected predictor and which controls the comparator.
If losses lie in $[0,B]$ rather than $[0,1]$, what change is needed in the simultaneous penalty?
Why does the simultaneous deviation theorem justify applying the bound to a predictor selected using the observed data?

Kraft Penalties For Countable Predictor Classes

What You'll Learn