Duplicate Candidates And Effective Dictionary Size

Why Repeated Candidates Matter

Finite-class selection often pays a complexity cost that grows with the logarithm of the number of candidates. That cost should reflect the number of genuinely different choices available, not the number of times a choice has been written in a list. If a dictionary contains the same predictor many times under different labels, counting every label can inflate the penalty without adding any predictive option.

The key is to specify what “the same candidate” means. For risk comparisons, two candidates can be treated as duplicates when they produce the same loss almost surely under the data distribution. Merely having equal population risks is weaker: their losses may vary differently from sample to sample, so empirical selection can distinguish them.

Definition: Let $Z$ have distribution $P$, and let $g_j$ be a fixed candidate predictor with measurable loss $\ell_{g_j}(Z)$. Candidates $g_j$ and $g_k$ are loss-equivalent under $P$ if $P(\ell_{g_j}(Z)=\ell_{g_k}(Z))=1$. This is an equivalence relation on a finite dictionary. Its equivalence classes form the effective dictionary; their number is the effective dictionary size, denoted $K$. If predictors are pointwise identical and use the same loss, they are loss-equivalent.

For a candidate $g$, write its risk as $R(g)=E[\ell_g(Z)]$. Given independent observations $Z_1,\ldots,Z_n$ from $P$, write its empirical risk as $\hat R(g)=n^{-1}\sum_{i=1}^n \ell_g(Z_i)$. The dictionary is fixed before these observations are collected. When losses are bounded, loss-equivalent candidates have the same risk and, with probability one, the same empirical risk. Thus selection among their labels cannot change the selected loss or its risk.

Collapsing Exact Duplicates

The quotient dictionary has one representative for each loss-equivalence class. Selecting a minimum empirical-risk candidate from the original list gives the same minimum empirical risk as selecting from this quotient. A tie-breaking rule may return a different label, but all labels in a class have the same loss almost surely and therefore represent the same choice for risk analysis.

Proposition: Suppose a finite dictionary of measurable loss functions is fixed in advance, and observations $Z_1,\ldots,Z_n$ are independent with common distribution $P$. If two candidates are loss-equivalent under $P$, then their risks are equal and their empirical risks are equal with probability one. Consequently, the minimum empirical risk over the labelled dictionary equals the minimum over its effective dictionary with probability one.

Proof. If $\ell_{g_j}(Z)=\ell_{g_k}(Z)$ with probability one, the two random losses have the same expectation whenever that expectation exists. For bounded losses it exists, so $R(g_j)=R(g_k)$. For each observation index $i$, the probability that the losses differ at $Z_i$ is zero. A finite union over $i=1,\ldots,n$ still has probability zero. Hence all $n$ observed losses agree with probability one, and their averages agree. The dictionary contains finitely many pairs, so the same argument holds simultaneously for every loss-equivalent pair. Taking minima over labels or over their equivalence classes therefore gives the same value with probability one. $\square$

This proposition explains why duplicate labels need not increase the complexity cost in a finite-class bound. The relevant counting step ranges over distinct loss functions up to almost-sure equality, rather than over all labels. For example, the usual finite union bound can be applied to the $K$ equivalence classes. A repeated label does not create another distinct deviation event.

A Risk Bound Using Effective Size

For a concrete result, suppose every candidate loss takes values in $[0,1]$. Let $\hat g$ minimize empirical risk over the dictionary, and let $g^*$ minimize population risk over it. Hoeffding’s inequality gives, for each fixed candidate and every $\varepsilon>0$, $P(|\hat R(g)-R(g)|>\varepsilon)\leq 2\exp(-2n\varepsilon^2)$. Applying this inequality to the effective dictionary gives the following guarantee.

Theorem: Suppose $Z_1,\ldots,Z_n$ are independent and identically distributed, the dictionary is finite and fixed in advance, and its measurable losses lie in $[0,1]$. Let $K$ be its effective dictionary size. If $\hat g$ is any empirical-risk minimizer, then for every $0<\delta<1$, with probability at least $1-\delta$, $$ R(\hat g)\leq \min_g R(g)+2\sqrt{\frac{\log(2K/\delta)}{2n}}. $$ The minimum is over the original dictionary or, equivalently, its effective dictionary.

Proof. Choose one representative from each of the $K$ loss-equivalence classes. Set $\varepsilon=\sqrt{\log(2K/\delta)/(2n)}$. For any representative $g$, Hoeffding’s inequality gives $$ P\bigl(|\hat R(g)-R(g)|>\varepsilon\bigr) \leq 2\exp(-2n\varepsilon^2) =2\exp\bigl(-\log(2K/\delta)\bigr) =\frac{\delta}{K}. $$ The probability that this deviation occurs for at least one representative is at most the sum of the $K$ individual probabilities, hence at most $\delta$. With probability at least $1-\delta$, every representative therefore satisfies $|\hat R(g)-R(g)|\leq\varepsilon$. On this event, let $g^*$ be a risk minimizer and use empirical minimization: $$ R(\hat g)\leq \hat R(\hat g)+\varepsilon \leq \hat R(g^*)+\varepsilon \leq R(g^*)+2\varepsilon. $$ The proposition ensures that the same inequalities apply to any labels representing these classes. This proves the claim. $\square$

Worked Example: Twelve Labels but Three Distinct Candidates

Suppose a fixed dictionary has $M=12$ labels, with each of three different predictors listed four times. Losses lie in $[0,1]$, the sample size is $n=200$, and the desired failure probability is $\delta=0.05$. The effective dictionary size is $K=3$, not 12.

Using the theorem, the excess-risk term is $$ 2\sqrt{\frac{\log(2K/\delta)}{2n}} =2\sqrt{\frac{\log(2\cdot 3/0.05)}{400}} =2\sqrt{\frac{\log(120)}{400}} \approx 0.2188. $$ Here $\log(120)\approx 4.7875$, so the quantity inside the square root is approximately $0.01197$.

If all 12 labels were counted, the same bound would instead give $$ 2\sqrt{\frac{\log(2M/\delta)}{2n}} =2\sqrt{\frac{\log(2\cdot 12/0.05)}{400}} =2\sqrt{\frac{\log(480)}{400}} \approx 0.2485. $$ The nominal count yields a valid but looser bound. Its larger penalty reflects repeated notation, not additional predictive choices.

Equal Risk Is Not the Same as a Duplicate

The effective size is not generally the number of distinct numerical risk values. Two candidates can have the same expectation but different loss functions. Their empirical risks may then move in different directions, creating distinct events that a finite-class argument must control. Collapsing them based only on equal population risk can invalidate a bound that relies on simultaneous control of empirical deviations.

Worked Example: Equal Risks, Different Empirical Losses

Let $Z$ take values $a$ and $b$, each with probability $1/2$. Define two losses by $\ell_1(a)=1,\ \ell_1(b)=0$, and $\ell_2(a)=0,\ \ell_2(b)=1$.

Their population risks are $$ R_1=E[\ell_1(Z)]=\tfrac12(1)+\tfrac12(0)=\tfrac12, \qquad R_2=E[\ell_2(Z)]=\tfrac12(0)+\tfrac12(1)=\tfrac12. $$ Nevertheless, they are not loss-equivalent: on $Z=a$ their losses differ, and on $Z=b$ their losses also differ.

For a sample of size $n=1$, if the observation is $a$, then $\hat R_1=1$ and $\hat R_2=0$; if it is $b$, then $\hat R_1=0$ and $\hat R_2=1$. The empirical minimizer therefore depends on the observation, even though the two population risks tie. There are two distinct loss classes, so the effective dictionary size is $K=2$, not one.

Exact equality of empirical losses on a particular observed sample is also insufficient to establish a duplicate. A sample may simply fail to reveal where two loss functions differ. Safe merging requires equality almost surely under the sampling distribution, or a stronger structural fact such as pointwise equality. In applications, structural duplication is often easy to check when predictors have been copied or generated repeatedly; almost-sure equivalence under an unknown distribution may not be directly verifiable.

Worked Example: Sample Agreement Does Not Prove Equivalence

Let $Z$ be uniform on $\{0,1,2\}$. Consider losses $\ell_A(z)=0$ for all $z$, and $\ell_B(0)=0,\ \ell_B(1)=\ell_B(2)=1$. If the observed sample consists only of zeros, the empirical risks are both zero, so they agree on that sample.

Their population risks are different: $$ R_A=\tfrac13(0+0+0)=0, \qquad R_B=\tfrac13(0+1+1)=\tfrac23. $$ The losses disagree with probability $2/3$, so the candidates are not loss-equivalent. Treating their observed agreement as duplication would remove a candidate with a different population risk and could change the oracle comparison. A coincidence in the data is not a justification for reducing the effective dictionary size.

When Labels Carry Unequal Weights

A finite selection argument may assign different confidence budgets or penalties to candidates rather than treating every label equally. In that case, duplicate labels can be combined by summing their weights at the class level. This is useful only when the weights describe the intended complexity allocation; splitting one substantive candidate into aliases should not, by itself, create extra complexity.

Worked Example: Combining Weight Within a Duplicate Class

Suppose three labels have weights $0.1,\ 0.1,\ 0.8$, summing to one. The first two labels are exact duplicates, forming class $A$; the third forms class $B$. The class weights are therefore $\pi_A=0.1+0.1=0.2$ and $\pi_B=0.8$.

For bounded losses, allocate failure probabilities $\delta_A=0.1\pi_A=0.02$ and $\delta_B=0.1\pi_B=0.08$. These sum to $0.1$. With $n=100$, Hoeffding’s inequality gives class-specific deviation thresholds $\sqrt{\log(2/\delta_C)/(2n)}$. Thus the threshold for $A$ is $$ \sqrt{\frac{\log(2/0.02)}{200}} =\sqrt{\frac{\log(100)}{200}} \approx 0.1517, $$ and the threshold for $B$ is $$ \sqrt{\frac{\log(2/0.08)}{200}} =\sqrt{\frac{\log(25)}{200}} \approx 0.1268. $$ The allocated failure probabilities control the two distinct classes with total failure probability at most $0.1$. Treating the duplicate labels separately would create two separate events for the same loss function; combining their class weight avoids that redundant accounting.

Common Pitfall and Practical Consequence

Incorrect reasoning: “These two candidates have the same risk, or happened to have the same empirical risk in this sample, so they are duplicates and I can divide the dictionary size by two.”

Correction: A safe merge for the finite-class argument requires the loss functions to agree almost surely under the data-generating distribution. Equal expectations do not imply equal loss distributions, and one sample cannot establish almost-sure equality. Conversely, if candidates are exact copies under the loss being analyzed, counting their labels separately is unnecessary: use the number of distinct loss classes in the cardinality term.

This distinction matters when reporting a complexity penalty. State what is being counted: labels, distinct prediction rules, or distinct loss functions under the relevant distribution. For a bound based on empirical losses, the last is the operative equivalence. If a sharper tail inequality is available, it may improve the numerical penalty, but it does not change the basic counting principle: exact duplicates contribute one distinct deviation event, not one per alias.

Key takeaway: Repeated labels inflate nominal dictionary size but do not add predictive options when their loss functions agree almost surely. Replace the label count by the effective dictionary size only for genuine loss-equivalence classes; do not merge candidates merely because their risks tie or their observed empirical losses happen to match.

Check Your Understanding

Use the distinction between duplicate labels and distinct loss functions to answer these questions.

A dictionary lists the same predictor five times and three other predictors once each. If all repeated copies use the same loss, what are the nominal and effective dictionary sizes?
Why does almost-sure equality of two losses imply equality of their population risks?
Two candidates have equal population risk but different losses on a set of positive probability. Can they automatically be merged for a finite-class empirical-risk bound? Explain.
Why is agreement of two empirical risks on one observed sample not sufficient evidence that the candidates are duplicates?
In the bounded-loss theorem, where does the effective dictionary size enter the risk bound, and why does it appear inside a logarithm?