Why Count Candidates Through Their Logarithm?
A finite dictionary may contain \(M\) predictors, and selecting one of them requires the data to provide enough information to distinguish the relevant possibilities. The number \(M\) itself is not usually the right measure of this burden: identifying one of \(M\) equally plausible labels requires about \(\log M\) units of information. This tutorial makes that intuition precise by constructing problems where selection cannot avoid a risk cost of order \(\log M/n\), or, under a different loss structure, \(\sqrt{\log M/n}\).
These are lower bounds. They show that no selection procedure can uniformly do better on the specified problems. They do not say that every finite dictionary incurs these costs, nor do they replace the upper bounds for finite selection: a favorable distribution or a favorable candidate collection can make selection easier.
Fano’s Inequality and Finite Identification
The following form of Fano’s inequality converts limited information into a lower bound on the probability of choosing the wrong hypothesis.
Proof. Write \(E=\mathbf{1}\{\hat V\ne V\}\) and \(p_e=P(E=1)\). Conditional on \(Z\), the entropy of \(V\) is at most the entropy of \(E\) plus the entropy of \(V\) given \(E\) and \(Z\). The first term is at most \(\log 2\). When \(E=0\), \(V\) is determined by \(\hat V(Z)\); when \(E=1\), it has at most \(M-1\) possible values. Therefore $$ H(V\mid Z)\le \log 2+p_e\log(M-1)\le \log 2+p_e\log M. $$ Since \(V\) is uniform, \(H(V)=\log M\), and \(I(V;Z)=H(V)-H(V\mid Z)\). Combining these relations gives $$ I(V;Z)\ge (1-p_e)\log M-\log 2, $$ which rearranges to the stated inequality. \(\square\)
In applications, the hypotheses are data-generating distributions, and each hypothesis has an associated best candidate predictor. If a wrong identification forces a certain excess risk, Fano’s inequality turns an information bound into a risk bound.
Worked Example: Gaussian Regression Forces a Log-Cardinality Cost
Worked Example: Gaussian Regression Forces a Log-Cardinality Cost
Let \(X\) be uniform on \(\{1,\ldots,M\}\). Under hypothesis \(j\), observe \(Y=a\mathbf{1}\{X=j\}+\varepsilon\), where \(\varepsilon\sim N(0,\sigma^2)\) is independent of \(X\). The finite dictionary contains \(f_k(x)=a\mathbf{1}\{x=k\}\), for \(k=1,\ldots,M\). Find the risk penalty for selecting the wrong candidate and use Fano’s inequality to bound it.
Under hypothesis \(j\), the conditional mean is \(f_j\), so \(f_j\) minimizes squared-error risk in the dictionary. For \(k\ne j\), the two predictors differ at \(x=j\) and \(x=k\), each of probability \(1/M\). Thus the excess risk is $$ E_j[(f_k(X)-Y)^2]-E_j[(f_j(X)-Y)^2] =E[(f_k(X)-f_j(X))^2] =\frac{2a^2}{M}. $$ The equality follows by expanding the squared errors and using \(E_j[Y\mid X]=f_j(X)\).
For one observation, the Kullback–Leibler divergence between hypotheses \(j\) and \(k\) is the average Gaussian conditional divergence. The covariate distribution is identical under both, and equal-variance normal distributions with means \(u\) and \(v\) have divergence \((u-v)^2/(2\sigma^2)\). Consequently, $$ D(P_j\Vert P_k)=\frac{1}{2\sigma^2}E[(f_j(X)-f_k(X))^2] =\frac{a^2}{\sigma^2 M}. $$ For \(n\) independent observations the divergence is \(n a^2/(\sigma^2 M)\), since product-distribution divergences add.
Choose \(a^2=\sigma^2 M\log M/(8n)\). The divergence between any two \(n\)-sample distributions is then \((\log M)/8\). For a uniform random hypothesis, mutual information is at most the average divergence to any fixed reference distribution; choosing one of these hypotheses as the reference gives \(I(V;Z)\le (\log M)/8\). When \(M\ge4\), \(\log 2/\log M\le1/2\), so Fano’s inequality gives $$ P(\hat V\ne V)\ge 1-\frac18-\frac12=\frac38. $$ Any procedure selecting a candidate therefore has average excess risk at least $$ \frac38\cdot\frac{2a^2}{M} =\frac{3a^2}{4M} =\frac{3}{32}\frac{\sigma^2\log M}{n}. $$ At least one hypothesis has risk at least this large. This explicit construction exhibits the \(\log M/n\) cost.
Why the Risk Cost Depends on the Loss
The Gaussian example has a useful feature: the divergence between two hypotheses is proportional to their squared-prediction separation, and that same separation is the excess squared-error risk. Fano’s inequality requires the data distributions to remain difficult to distinguish. If divergence grows linearly with excess risk, keeping the total divergence on the scale of \(\log M\) makes the risk gap scale as \(\log M/n\).
That relationship is not universal. With classification under noisy labels, small changes in the conditional label probabilities can produce excess 0–1 risk proportional to the size of the change, while the divergence between the data distributions is proportional to its square. This different relationship leads to the slower square-root scale.
Worked Example: A Classification Dictionary with a Slow-Rate Cost
Worked Example: A Classification Dictionary with a Slow-Rate Cost
Let \(d\) be a positive integer and index \(M=2^d\) candidate classifiers by vectors \(v\in\{-1,+1\}^d\). Each observation has \(X\) uniform on \(\{1,\ldots,d\}\), and \(Y\in\{-1,+1\}\). Under hypothesis \(\theta\in\{-1,+1\}^d\), suppose $$ P_\theta(Y=\theta_j\mid X=j)=\frac{1+\epsilon}{2}, \qquad 0<\epsilon\le\frac12. $$ The candidate \(f_v\) predicts \(v_j\) at \(X=j\). Compute its excess classification risk.
If \(v_j=\theta_j\), the error probability at coordinate \(j\) is \((1-\epsilon)/2\). If \(v_j\ne\theta_j\), it is \((1+\epsilon)/2\), a difference of \(\epsilon\). Averaging over the uniform covariate gives $$ R_\theta(f_v)-R_\theta(f_\theta) =\epsilon\,\frac{d_H(v,\theta)}{d}, $$ where \(d_H(v,\theta)\) is the number of coordinates on which the vectors differ.
To see why a selector cannot reliably recover all coordinates, compare two hypotheses that differ only at coordinate \(j\). For one observation, their conditional label distributions differ only when \(X=j\), an event of probability \(1/d\). The Bernoulli divergence at that coordinate is $$ \epsilon\log\!\left(\frac{1+\epsilon}{1-\epsilon}\right) \le \frac{8}{3}\epsilon^2,\qquad 0<\epsilon\le\frac12. $$ Indeed, \(\log((1+\epsilon)/(1-\epsilon))\le 2\epsilon/(1-\epsilon^2)\le(8/3)\epsilon\). Thus the divergence between the corresponding \(n\)-sample distributions is at most \(8n\epsilon^2/(3d)\).
Average \(\theta\) uniformly over the hypercube. For each coordinate, any decision about \(\theta_j\) is a binary test between two mixtures of data distributions, paired by hypotheses differing only at \(j\). Pinsker’s inequality, \(\operatorname{TV}(P,Q)\le\sqrt{D(P\Vert Q)/2}\), bounds the total variation distance in each paired comparison by \(\sqrt{4n\epsilon^2/(3d)}\). The average error probability for a binary test is at least \((1-\operatorname{TV})/2\). Hence, whenever \(n\epsilon^2/d\le 1/16\), the average coordinate error probability is at least $$ \frac{1-\sqrt{1/12}}{2}>0.35. $$ Summing over coordinates shows that the expected Hamming fraction of any selected vector is at least \(0.35\). Its expected excess risk is therefore at least \(0.35\epsilon\).
Taking \(\epsilon=\frac14\sqrt{d/n}\), when \(d\le4n\), satisfies both \(\epsilon\le1/2\) and \(n\epsilon^2/d=1/16\). Since \(\log M=d\log 2\), this gives a constant multiple of \(\sqrt{\log M/n}\). The example shows that finite cardinality alone does not determine the rate: the relation between risk and statistical distinguishability matters.
Worked Example: Reading the Scaling with \(M\)
Worked Example: Reading the Scaling with \(M\)
In the Gaussian construction, fix \(n\) and \(\sigma^2\). Compare dictionaries of sizes \(M=8\) and \(M=32\). The log-cardinality terms are \(\log 8=3\log 2\) and \(\log 32=5\log 2\). The lower-bound scale therefore increases by the factor $$ \frac{\log 32}{\log 8}=\frac{5\log 2}{3\log 2}=\frac53, $$ not by the factor \(32/8=4\). If instead \(M\) is fixed and the sample size increases from \(n\) to \(4n\), the \(\log M/n\) scale is divided by four. These comparisons concern the order and the displayed bound’s scale; they do not assert that every practical problem attains the lower bound.
What These Constructions Establish
The Gaussian calculation gives a finite collection of regression problems on which every candidate selector has excess risk at least a constant times \(\sigma^2\log M/n\). The classification calculation gives a different family on which a selector’s expected excess 0–1 risk is at least a constant times \(\sqrt{\log M/n}\), within its stated sample-size range. Both are minimax statements over explicitly constructed distributions and candidate dictionaries.
This distinction is useful when interpreting finite-class upper bounds. A logarithmic factor in an upper bound can reflect the genuine information required to distinguish many alternatives, rather than an artifact of a proof. But lower bounds are not predictions about every application: substantial separation between candidates, repeated candidates, or special structure can change the practical difficulty. In any particular problem, the relevant question is how much the distributions change when the preferred candidate changes, and how that change translates into risk.
Common Mistake
- Wrong reasoning: “There are \(M\) candidates, so selection must cost order \(M/n\).” This treats the number of candidate labels as if each one required a separate sample budget.
- Correction: The finite-identification argument works through \(\log M\), the information needed to encode one of \(M\) possibilities. The risk cost then depends on how risk relates to divergence: the constructions here give \(\log M/n\) for one relationship and \(\sqrt{\log M/n}\) for another.
- Another pitfall: A lower bound for a constructed family is not a guarantee that every dictionary or data distribution incurs that loss. It establishes an unavoidable worst-case cost over the stated family.
Check Your Understanding
Use the definitions and constructions above to answer the following questions.
- In the Gaussian regression example, why does selecting the wrong candidate incur excess risk \(2a^2/M\), rather than \(a^2\)?
- What upper bound on mutual information is used in the Gaussian example, and why is a reference distribution helpful?
- In the classification construction, what is the excess risk when a candidate differs from \(\theta\) at exactly \(r\) coordinates?
- Explain why the classification example yields a square-root scale while the Gaussian example yields a \(\log M/n\) scale.
- Does a lower bound for one constructed family imply that every finite dictionary has the same selection difficulty? Explain.