Kraft Weights For Countable Model Families

Why Weight a Countable Model Family?

A finite collection of models can share a confidence budget by assigning the same error allowance to each model. For a countably infinite collection, equal positive allowances cannot sum to a finite total. The remedy is to give each model its own positive weight, with all weights summing to at most one. A model given less weight receives a larger penalty in the resulting simultaneous risk bound.

This is the key idea behind a weighted union bound: the confidence level is divided unevenly, but the probability that any model’s bound fails is still controlled. The choice of weights can reflect the indexing of the family. For example, geometrically decreasing weights are natural when models are indexed by increasing complexity.

Weights and Their Penalty

Definition: Let $\mathcal M$ be a countable set of model indices. A collection of numbers $(\pi_m:m\in\mathcal M)$ is a set of weights for $\mathcal M$ if $\pi_m>0$ for every $m$ and $$ \sum_{m\in\mathcal M}\pi_m\leq 1. $$ The quantity $\log(1/\pi_m)$, using the natural logarithm, is the model’s weight penalty. A smaller weight produces a larger penalty.

The weights are chosen before the observations are used. They may depend on the model labels or other prespecified features, but not on the data in a way that selects favorable weights after seeing the empirical risks. Such data-dependent choices require additional justification; the weighted union-bound argument below does not automatically cover them.

The condition allows the weights to sum to less than one. Any unused amount is simply unallocated confidence budget. For a finite collection of $K$ models, taking $\pi_m=1/K$ gives each model the same share. For a countable collection, weights must decrease as the indices extend indefinitely.

Connection to Kraft’s Inequality

Weights are closely related to code lengths, but the distinction between real-valued weights and integer code lengths matters. For a binary prefix code, each codeword has a nonnegative integer length $L_m$. Kraft’s inequality states that such lengths can be assigned to a binary prefix code exactly when $$ \sum_m 2^{-L_m}\leq 1. $$ A prefix code is one in which no codeword is the initial segment of another codeword.

Thus, if the weights happen to have the form $\pi_m=2^{-L_m}$ for nonnegative integer lengths $L_m$, the weight condition is Kraft’s inequality. An arbitrary positive weight need not itself be $2^{-L_m}$ for an integer $L_m$. For example, $\pi=1/3$ is a valid weight, but $\log_2 3$ is not an integer code length.

There is still a precise coding connection for general weights. Given any weight $\pi_m$, set $L_m=\lceil\log_2(1/\pi_m)\rceil$. These are nonnegative integers and $2^{-L_m}\leq\pi_m$, so their sum is at most one. Kraft’s inequality therefore gives a prefix code with lengths no greater than this rounded-up assignment. The code interpretation is useful, but the risk bound itself only requires positive summable weights.

Worked Example: Geometric Weights for Models Indexed by Complexity

Suppose the models are indexed by $m=1,2,\ldots$, with larger indices representing greater complexity. Set $\pi_m=2^{-m}$. The weights are positive, and $$ \sum_{m=1}^{\infty}2^{-m}=1. $$ Thus they form a valid weight assignment. In binary coding terms, the lengths $L_m=m$ satisfy Kraft’s inequality; one possible sequence of codewords is $0,10,110,1110,\ldots$.

The penalty for model $m$, measured using natural logarithms, is $$ \log(1/\pi_m)=\log(2^m)=m\log 2. $$ Consequently, the model’s penalty grows linearly with its index. This assignment gives more confidence budget to lower-index models and progressively less to higher-index models.

A Weighted Simultaneous Risk Bound

First consider one candidate predictor for each model. Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations. For each fixed $m$, let $\ell_m(Z_i)$ be its loss on observation $Z_i$, with $0\leq \ell_m(Z_i)\leq 1$. Define its risk and empirical risk by $$ R_m=E[\ell_m(Z_1)],\qquad \widehat R_m=\frac{1}{n}\sum_{i=1}^n\ell_m(Z_i). $$ Because the predictor for each $m$ is fixed independently of these observations, Hoeffding’s inequality gives, for every $t>0$, $$ P(R_m-\widehat R_m>t)\leq \exp(-2nt^2). $$ The next result allocates a different deviation threshold to each model.

Theorem: Suppose $\mathcal M$ is countable, the weights $(\pi_m)$ are positive and sum to at most one, and each fixed model has independent, identically distributed losses in $[0,1]$ as above. For any $0<\delta<1$, with probability at least $1-\delta$, simultaneously for every $m\in\mathcal M$, $$ R_m\leq \widehat R_m+ \sqrt{\frac{\log(1/(\delta\pi_m))}{2n}}. $$

Proof. For each $m$, define $$ t_m=\sqrt{\frac{\log(1/(\delta\pi_m))}{2n}}. $$ Since $0<\delta\pi_m<1$, this is a positive real number. Applying the one-sided Hoeffding bound at $t_m$ gives $$ P(R_m-\widehat R_m>t_m) \leq \exp(-2nt_m^2) =\exp\bigl(-\log(1/(\delta\pi_m))\bigr) =\delta\pi_m. $$ The event that at least one model violates its inequality is the countable union of the events $\{R_m-\widehat R_m>t_m\}$. By countable subadditivity of probability, $$ P\bigl(\text{at least one model violates its bound}\bigr) \leq \sum_{m\in\mathcal M}\delta\pi_m =\delta\sum_{m\in\mathcal M}\pi_m \leq\delta. $$ Therefore, with probability at least $1-\delta$, none of the models violates its bound. This proves the simultaneous claim. $\square$

The penalty separates into a confidence-level term and a model-specific term: $$ \sqrt{\frac{\log(1/\delta)+\log(1/\pi_m)}{2n}}. $$ The shared term $\log(1/\delta)$ controls the overall failure probability. The term $\log(1/\pi_m)$ charges each model according to the confidence budget it receives. This is the countable-family analogue of dividing a finite collection’s confidence level among its members.

Worked Example: Polynomial Weights for a Countable Family

For models indexed by $m=1,2,\ldots$, consider $$ \pi_m=\frac{6}{\pi^2m^2}. $$ The Basel sum $\sum_{m=1}^{\infty}m^{-2}=\pi^2/6$ verifies that these weights sum to one. For $n=100$ and $\delta=0.05$, the penalty for model $m$ is $$ \sqrt{\frac{\log(1/0.05)+\log(\pi^2m^2/6)}{200}}. $$ For $m=1$, $\log(20)\approx2.9957$ and $\log(\pi^2/6)\approx0.4977$. The penalty is therefore $$ \sqrt{\frac{2.9957+0.4977}{200}}\approx0.132. $$ For $m=4$, $\log(\pi^2\cdot16/6)\approx3.2703$, giving $$ \sqrt{\frac{2.9957+3.2703}{200}}\approx0.177. $$ The fourth model receives less weight than the first, so its simultaneous risk penalty is larger.

Worked Example: Recovering the Equal-Weight Finite Bound

Suppose there are $K=8$ fixed candidate models. Assign $\pi_m=1/8$ to each; the weights sum to one. With $n=200$ observations and $\delta=0.05$, every model has the same penalty: $$ \sqrt{\frac{\log(1/(0.05/8))}{2(200)}} =\sqrt{\frac{\log(160)}{400}} \approx\sqrt{\frac{5.0752}{400}} \approx0.113. $$ Thus, with probability at least $0.95$, all eight risks are bounded by their empirical risks plus approximately $0.113$. The logarithm $\log(160)=\log(1/\delta)+\log K$ shows explicitly how the finite collection size enters the penalty.

Using the Bound With Fitted Models

The theorem as stated concerns a fixed candidate predictor per model. It does not, by itself, justify applying the same concentration inequality to a predictor selected by minimizing empirical risk over a rich model using the very same observations. In that setting, the fitted predictor is data-dependent, and the fixed-predictor Hoeffding bound need not hold for it.

There are two common ways to use the weighted allocation in fitted-model settings. One is to evaluate fitted predictors on an independent validation sample; conditional on the training data, the predictors are fixed relative to that validation sample. The other is to establish a valid modelwise bound that already accounts for fitting within each model, and then allocate its failure probability as $\delta\pi_m$. For example, if the modelwise failure probability at its chosen threshold is at most $\delta\pi_m$, the same countable union-bound proof yields simultaneous validity. The within-model analysis and the across-model weighting are separate tasks.

Choosing Weights and Avoiding Common Errors

A weight assignment should match the structure of the family. Geometric weights such as $2^{-m}$ make the penalty grow roughly linearly with the index. Polynomial weights proportional to $m^{-2}$ make it grow roughly like $\log m$, since $\log(1/\pi_m)$ is then a constant plus $2\log m$. Both are valid; their usefulness depends on how quickly model complexity grows and how much confidence budget one wants to reserve for high-index models.

Using equal positive weights on infinitely many models. Their sum is infinite, so they cannot allocate a finite total confidence budget. Choose a summable sequence instead.
Using weights that sum to more than one. The displayed weighted union-bound guarantee then has an upper bound exceeding $\delta$. Rescale the weights so their sum is at most one.
Treating every real-valued weight as a binary code length. A weight is a probability-like budget share; an exact binary length requires $\pi_m=2^{-L_m}$ with $L_m$ a nonnegative integer. General weights still give valid risk penalties.
Ignoring data dependence. The weights must be prespecified for this argument, and fixed-predictor concentration cannot automatically be applied after fitting to the same data.

Key takeaway: Positive weights with total at most one let a countable family share a single confidence level. Under the stated modelwise concentration conditions, model $m$ pays an additional penalty governed by $\log(1/\pi_m)$, while one event controls the risk bounds for every model simultaneously.

Check Your Understanding

Use the definitions and weighted bound to answer the following questions.

Why can an infinite countable collection not receive the same positive weight at every index while keeping the total weight at most one?
For weights $\pi_m=2^{-m}$, write the model-specific part of the penalty in terms of $m$.
Explain why $\pi=1/3$ is a valid weight but does not correspond to an exact integer binary code length through $\pi=2^{-L}$.
What assumption on the losses allows the stated Hoeffding inequality to be applied to each fixed model?
Why does the fixed-model argument not automatically provide a risk bound for a predictor selected using the same observations?