Nonuniform Penalties For Finite Predictor Collections

Why Penalize Candidates Differently?

A finite predictor collection need not be treated as a collection of equally plausible choices. For example, some candidates may be prespecified as especially relevant, while others are included as broader alternatives. If the weights expressing those priorities are set before examining the data, a selection rule can charge less for candidates with larger weights and more for candidates with smaller weights. The resulting risk bound depends on each candidate’s own weight rather than only on the dictionary’s total size.

The key quantity is the logarithm of the inverse weight. A candidate assigned weight $\pi_j$ pays a complexity cost involving $\log(1/\pi_j)$: small weights cost more, and large weights cost less. The logarithm also makes the cost additive when weights are described through successive choices.

Setup and Weighted Penalty

Let $Z_1,\ldots,Z_n$ be independent observations with a common distribution $P$. There are $M$ fixed candidate predictors, indexed by $j\in\{1,\ldots,M\}$. For candidate $j$, let $\ell_j(Z)$ be its loss on one observation, and assume $0\leq \ell_j(Z)\leq 1$ with probability one. Its risk and empirical risk are

R_j=E[\ell_j(Z)], \qquad \widehat R_j=\frac{1}{n}\sum_{i=1}^n \ell_j(Z_i).

The candidates and their loss functions are fixed independently of the observations used to compute the empirical risks. Assign each candidate a prespecified weight $\pi_j>0$, with $\sum_{j=1}^M\pi_j=1$. For a confidence level $\delta\in(0,1)$, define

c_j(\delta)= \sqrt{\frac{\log\!\left(2/(\delta\pi_j)\right)}{2n}}.

The penalty is larger for candidates with smaller weights. The factor $2$ inside the logarithm accounts for controlling deviations in both directions. We use the standard Hoeffding inequality: for independent random variables $W_i\in[0,1]$ with common mean $\mu$, the sample average $\overline W$ satisfies $P(|\overline W-\mu|>t)\leq 2\exp(-2nt^2)$ for every $t>0$.

Definition: A nonuniform penalized empirical-risk selector is any index $$ \widehat j\in\underset{1\leq j\leq M}{\arg\min}\, \left\{\widehat R_j+c_j(\delta)\right\}. $$ If more than one index minimizes the criterion, any deterministic tie-breaking rule may be used. The selected predictor is the candidate indexed by $\widehat j$.

Worked Example: Computing Candidate-Specific Penalties

Suppose $n=400$, $\delta=0.05$, and four candidates have weights $(0.50,0.25,0.15,0.10)$. These weights are positive and sum to one. The penalty for candidate $j$ is $c_j=\sqrt{\log(2/(0.05\pi_j))/800}$.

For candidate 1, $\pi_1=0.50$, so $c_1=\sqrt{\log(80)/800}=\sqrt{4.3820266/800}\approx0.07401$.

For candidate 2, $\pi_2=0.25$, so $c_2=\sqrt{\log(160)/800}=\sqrt{5.0751738/800}\approx0.07965$. Its oracle-comparison cost $2c_2$ is therefore approximately 0.1593.

For candidate 3, $\pi_3=0.15$, giving $c_3=\sqrt{\log(266.6667)/800}\approx\sqrt{5.5860/800}\approx0.08356$. For candidate 4, $\pi_4=0.10$, giving $c_4=\sqrt{\log(400)/800}\approx\sqrt{5.9914645/800}\approx0.08654$. Thus, the candidate with the largest weight pays the smallest penalty, and the one with the smallest weight pays the largest. These are penalties added to empirical risk; the corresponding oracle costs in the result below are twice these values.

A Weighted Simultaneous Deviation Bound

Theorem: Under the setup above, with probability at least $1-\delta$, every candidate satisfies $$ |\widehat R_j-R_j|\leq c_j(\delta), \qquad j=1,\ldots,M. $$ Consequently, the penalized selector satisfies the oracle inequality $$ R_{\widehat j}\leq \min_{1\leq j\leq M}\left\{R_j+2c_j(\delta)\right\}. $$

The first claim allocates a candidate-specific share of the total error probability. To verify it, apply Hoeffding’s inequality to the loss observations for candidate $j$, using $t=c_j(\delta)$:

P\!\left(|\widehat R_j-R_j|>c_j(\delta)\right) \leq 2\exp\!\left(-2n c_j(\delta)^2\right) =2\exp\!\left(-\log\!\frac{2}{\delta\pi_j}\right) =\delta\pi_j.

The union bound then gives

P\!\left(\text{at least one candidate violates its bound}\right) \leq \sum_{j=1}^M\delta\pi_j =\delta.

On the complementary event, both inequalities $R_j\leq\widehat R_j+c_j(\delta)$ and $\widehat R_j\leq R_j+c_j(\delta)$ hold for every $j$. Fix any candidate $j$. By the selector’s minimizing property and then the simultaneous deviation bounds,

\begin{aligned} R_{\widehat j} &\leq \widehat R_{\widehat j}+c_{\widehat j}(\delta)\\ &\leq \widehat R_j+c_j(\delta)\\ &\leq R_j+2c_j(\delta). \end{aligned}

This inequality holds for each fixed $j$ on the same event, so taking the minimum over $j$ proves the oracle inequality. The guarantee is simultaneous: the candidate that performs best in the comparison may be identified after seeing the data, because all candidates’ inequalities hold together. $\square$

How the Weights Change Selection

The weights affect two parts of the procedure in the same direction. A larger $\pi_j$ gives candidate $j$ a smaller penalty in the selection criterion and a smaller risk cost in the oracle comparison. A small weight is not a prohibition: that candidate can still be selected if its empirical risk is sufficiently low. It simply needs stronger empirical evidence to compensate for its larger penalty.

Worked Example: Choosing by Penalized Empirical Risk

Suppose $n=1000$, $\delta=0.10$, and three candidates have weights $(0.70,0.20,0.10)$. Their observed empirical risks are $(0.16,0.14,0.12)$. Here $2n=2000$, so the penalties are computed as $c_j=\sqrt{\log(2/(0.10\pi_j))/2000}$.

For candidate 1, $c_1=\sqrt{\log(28.5714)/2000}\approx\sqrt{3.3524/2000}\approx0.04094$, and its penalized empirical risk is $0.16+0.04094=0.20094$.

For candidate 2, $c_2=\sqrt{\log(100)/2000}\approx\sqrt{4.6052/2000}\approx0.04799$, and its penalized empirical risk is $0.14+0.04799=0.18799$.

For candidate 3, $c_3=\sqrt{\log(200)/2000}\approx\sqrt{5.2983/2000}\approx0.05147$, and its penalized empirical risk is $0.12+0.05147=0.17147$.

Candidate 3 minimizes the penalized criterion, even though its smaller weight gives it the largest penalty. The theorem says that, with probability at least $0.90$, its risk is at most $R_j+2c_j$ for every comparison candidate $j$. In particular, comparing it with candidate 3 itself gives the tautological bound $R_3\leq R_3+2c_3$; the useful comparisons are often with other candidates whose risks are lower than the selected candidate’s risk might otherwise be.

Worked Example: Comparing Nonuniform and Uniform Weights

Consider four candidates, $n=500$, and $\delta=0.10$. Suppose a candidate of special interest receives weight $0.70$, with the remaining weights $(0.20,0.08,0.02)$. The special candidate’s penalty is $c_1=\sqrt{\log(2/(0.10\cdot0.70))/1000} =\sqrt{\log(28.5714)/1000}\approx0.0579$. Its oracle-comparison cost is $2c_1\approx0.1158$.

If instead the four candidates receive uniform weights $0.25$, the same candidate-specific cost would be $2\sqrt{\log(2/(0.10\cdot0.25))/1000} =2\sqrt{\log(80)/1000}\approx2(0.0662)=0.1324$. The nonuniform weight gives this candidate a smaller cost. It does not give every candidate a smaller cost: the candidate with weight $0.02$ has $2c_4=2\sqrt{\log(1000)/1000}\approx2(0.0831)=0.1662$, which exceeds the uniform-weight cost. The allocation of weights redistributes the bound rather than removing the need to account for the collection.

Interpretation and Scope

Because the weight appears inside a logarithm, the additional cost for making a candidate less heavily weighted grows gradually. For fixed $\delta$, the bound has the form $\sqrt{(\log(1/\pi_j)+\log(2/\delta))/(2n)}$. Thus the contribution from the candidate’s weight is measured on a logarithmic scale, while the overall deviation shrinks at the usual square-root rate in sample size. If all $M$ weights are uniform, then $\pi_j=1/M$, and every penalty is $\sqrt{\log(2M/\delta)/(2n)}$. The nonuniform result therefore includes the uniform finite-collection comparison as a special case.

The bounded-loss assumption matters for this particular penalty formula: the Hoeffding bound used above is for losses in $[0,1]$. If losses lie in a known interval $[a,b]$, rescale them to $[0,1]$, or equivalently multiply the displayed deviation radii by $b-a$ when working on the original scale. The fixed-candidate assumption also matters. The weights must be specified independently of the observations used to evaluate and select the candidates. Choosing weights after inspecting those same empirical risks is not justified by the union-bound argument as written; the data-dependent choice would need its own valid analysis.

Common Pitfall

Using only the selected candidate’s deviation radius in the oracle cost. The selection inequality compares penalized empirical risks, while converting from empirical risk to true risk requires a deviation allowance as well. The complete chain is $R_{\widehat j}\leq\widehat R_{\widehat j}+c_{\widehat j}\leq\widehat R_j+c_j\leq R_j+2c_j$. Omitting one of the two allowances understates the stated guarantee.
Treating the weights as rewards that make a candidate’s risk smaller. Weights do not change any candidate’s true risk. They change the penalty used for selection and the candidate-specific cost in the comparison bound.
Assuming a tiny weight makes a candidate unavailable. A candidate with a small positive weight remains eligible; it simply faces a larger penalty. A zero weight is different: its logarithmic penalty is infinite, so the theorem is stated for positive weights.

Key takeaway: For prespecified positive weights summing to one, penalizing each bounded-loss candidate by $\sqrt{\log(2/(\delta\pi_j))/(2n)}$ yields, with probability at least $1-\delta$, a risk bound within twice that candidate’s penalty of its true risk.

Check Your Understanding

Try these questions using the definitions and result above.

Why must the weights sum to one, or at least be controlled in total, for the displayed union-bound argument?
For a fixed sample size and confidence level, which candidate has the larger penalty: one with weight $0.4$ or one with weight $0.1$? Explain using the formula.
Show how the penalty simplifies when all $M$ candidates receive equal weights.
In the oracle inequality, identify the two steps that each contribute a penalty allowance.
Why does choosing the weights after inspecting the same empirical risks require additional justification?