Two-Point Lower Bounds from Ambiguous Regions

Why Ambiguous Regions Create Lower Bounds

A classifier can fail because it has too little data, but a lower bound needs more than that general observation. It needs two distributions that demand different decisions and remain difficult to distinguish from the observed sample. A useful construction makes the distributions identical except on a region where the feature probability is small and the conditional label probabilities are close to one half. The region contributes to excess risk, yet the data provide only weak evidence about which decision is correct there.

This tutorial develops that two-point argument for binary classification. The central quantities are the region’s probability \(p\), the conditional margin \(\delta\), and the difficulty of testing between the resulting sample distributions.

Set-Up and Excess Risk

Let \(P_+\) and \(P_-\) be two distributions for an observation \((X,Y)\), where \(Y\in\{0,1\}\). Assume they have the same marginal distribution \(\mu\) for \(X\). Write \(\eta_\pm(x)=P_\pm(Y=1\mid X=x)\). A classifier \(g\) takes values in \(\{0,1\}\), and its risk under \(P\) is \(R_P(g)=P(g(X)\ne Y)\). A Bayes classifier chooses the more probable label given \(X=x\).

For a distribution with regression function \(\eta\), the excess risk of \(g\) over a Bayes classifier \(g^*\) has the identity \[ R_P(g)-R_P(g^*)=\int |2\eta(x)-1|\,\mathbf{1}\{g(x)\ne g^*(x)\}\,d\mu(x). \] Indeed, conditional on \(X=x\), predicting 0 has error probability \(\eta(x)\), while predicting 1 has error probability \(1-\eta(x)\). The difference between the larger and smaller of these two probabilities is \(|2\eta(x)-1|\). Integrating the conditional excess error gives the identity. In the ambiguous region, this weight is \(2\delta\).

The Two-Point Lower Bound

Proof. Fix \(x\in A\) and let \(B_x\) be the event, under the sample, that \(\hat g(x)=1\). Under \(P_+\), label 1 is Bayes-optimal at \(x\); under \(P_-\), label 0 is Bayes-optimal. The sum of the two probabilities of making the wrong decision at this \(x\) is \[ P_+^n(B_x^c)+P_-^n(B_x) =1-\bigl(P_+^n(B_x)-P_-^n(B_x)\bigr) \ge 1-\operatorname{TV}(P_+^n,P_-^n). \] The excess-risk identity assigns weight \(2\delta\) to each such error on \(A\). Integrating over \(A\), whose marginal probability is \(p\), therefore gives \[ E_{P_+^n}[R_{P_+}(\hat g)-R_{P_+}(g_+^*)] +E_{P_-^n}[R_{P_-}(\hat g)-R_{P_-}(g_-^*)] \ge 2\delta p\left(1-\operatorname{TV}(P_+^n,P_-^n)\right). \] The larger of two nonnegative numbers is at least half their sum. This proves the claim. The argument also applies to randomized classifiers by including their independent randomization in the decision rule. \(\square\)

The theorem converts testing difficulty into excess risk. To use it, we need an upper bound on the total variation distance between the sample distributions. If \(0<\delta<1/2\), the distributions are mutually absolutely continuous on their common support, and their one-observation Kullback–Leibler divergence is \[ \operatorname{KL}(P_+,P_-) =p\,2\delta\log\!\left(\frac{1+2\delta}{1-2\delta}\right). \] On \(A\), this follows by computing the divergence between Bernoulli probabilities \(1/2+\delta\) and \(1/2-\delta\); outside \(A\), the conditional distributions agree and contribute zero. Independence gives \(\operatorname{KL}(P_+^n,P_-^n)=n\operatorname{KL}(P_+,P_-)\).

To check the divergence bound, put \(u=2\delta\le1/2\). Since \(\log(1+v)\le v\) for \(v>-1\), \[ \log\!\left(\frac{1+u}{1-u}\right) =\log\!\left(1+\frac{2u}{1-u}\right) \le\frac{2u}{1-u}\le4u. \] Thus \(2\delta\log((1+2\delta)/(1-2\delta))\le16\delta^2\). Multiplying by \(p\) gives the one-observation bound. For the stated sample-size condition, \(n\operatorname{KL}(P_+,P_-)\le1/4\), so Pinsker’s inequality gives \(\operatorname{TV}(P_+^n,P_-^n)\le\sqrt{(1/4)/2}=1/(2\sqrt{2})\). Substitution in the theorem yields the result.

Worked Constructions

What the Construction Does—and Does Not—Show

The ambiguous region contributes \(p\delta\) to the scale of excess risk, while its contribution to the one-sample divergence is of order \(p\delta^2\). The latter determines whether \(n\) observations can reliably identify which Bayes decision is correct. A useful lower-bound design keeps \(np\delta^2\) bounded: the sample distributions then remain difficult to test, and the theorem forces a risk cost of order \(p\delta\).

The construction is a two-point argument: it proves that no procedure can perform well on both selected distributions. To obtain a lower bound for a larger model class, both distributions must belong to that class. Additional restrictions, such as smoothness or a prescribed feature distribution, can limit which choices of \(p\) and \(\delta\) are admissible.

• Common mistake: using small region probability alone. A rare region does not automatically imply a lower bound. If the labels there are easy to distinguish, enough observations may identify the correct decision. Check the divergence between the full sample distributions.
• Common mistake: comparing one observation when the learner has \(n\). A small one-observation divergence is not sufficient by itself. The relevant quantity is the sample divergence, which is \(n\) times the one-observation divergence for independent observations.
• Common mistake: forgetting the margin in excess risk. Disagreement on \(A\) contributes \(2\delta\) per unit of feature probability, not one. The resulting risk scale is \(p\delta\), up to constants.