Threshold Perturbation Error for Plug-In Classifiers

Why Threshold Error Needs Its Own Accounting

A plug-in classifier first estimates the conditional probability of the positive class and then compares that estimate with a decision threshold. These two operations can each introduce error: the regression estimate may be inaccurate, and the threshold used for classification may differ from the Bayes threshold. A useful risk bound should show both contributions rather than hiding them in one undifferentiated deviation.

We work with binary labels $Y\in\{0,1\}$, covariates $X$, and the regression function $\eta(x)=P(Y=1\mid X=x)$. False negatives and false positives have respective costs $C_{\mathrm{FN}}>0$ and $C_{\mathrm{FP}}>0$. The threshold and regret identities below make the effect of a threshold perturbation explicit.

Definition: For a classifier $g:\mathcal{X}\to\{0,1\}$, define its cost-sensitive risk by $R(g)=C_{\mathrm{FN}}P(g(X)=0,Y=1)+C_{\mathrm{FP}}P(g(X)=1,Y=0)$. Let $S=C_{\mathrm{FN}}+C_{\mathrm{FP}}$ and $t=C_{\mathrm{FP}}/S$. The Bayes classifier is $g^*(x)=\mathbf{1}\{\eta(x)\ge t\}$. A plug-in classifier with threshold displacement $\delta$ is $\hat g_\delta(x)=\mathbf{1}\{\hat\eta(x)\ge t+\delta\}$, where $\hat\eta$ estimates $\eta$. The displacement $\delta$ may be positive or negative.

The conditional cost of predicting 1 is $C_{\mathrm{FP}}(1-\eta(x))$, while the conditional cost of predicting 0 is $C_{\mathrm{FN}}\eta(x)$. Predicting 1 is preferable precisely when $\eta(x)\ge t$. Write $M(x)=|\eta(x)-t|$ for the distance to this cost-sensitive decision boundary. The excess conditional cost of choosing the wrong label is $S M(x)$.

Exact Regret From Moving the Threshold

First suppose the regression function is known exactly, so that the only change is to use $t+\delta$ instead of $t$. The resulting excess risk is determined by the covariate points whose regression values fall between the two thresholds.

Proposition: Let $g_{t+\delta}(x)=\mathbf{1}\{\eta(x)\ge t+\delta\}$. Then $$ R(g_{t+\delta})-R(g^*)= S\,E\!\left[M(X)\mathbf{1}\{g_{t+\delta}(X)\ne g^*(X)\}\right]. $$ Equivalently, disagreement occurs when $\eta(X)$ lies between $t$ and $t+\delta$, with endpoints determined by the displayed “greater than or equal to” rule.

Proof. Conditional on $X=x$, the two possible prediction costs are $C_{\mathrm{FP}}(1-\eta(x))$ and $C_{\mathrm{FN}}\eta(x)$. Their difference, positive-prediction cost minus negative-prediction cost, is $$ C_{\mathrm{FP}}(1-\eta(x))-C_{\mathrm{FN}}\eta(x) =C_{\mathrm{FP}}-S\eta(x)=-S(\eta(x)-t). $$ Thus the Bayes prediction has the smaller conditional cost. If $g_{t+\delta}(x)=g^*(x)$, the conditional excess cost is zero. If the predictions differ, the classifier chooses the larger of the two costs, and the difference between them is $S|\eta(x)-t|=S M(x)$. Taking expectation over $X$ proves the identity. $\square$

Worked Example: Cost-Sensitive Threshold Displacement

Let $C_{\mathrm{FN}}=3$ and $C_{\mathrm{FP}}=1$. Then $S=4$ and $t=1/4=0.25$. Suppose $X$ takes three values with probabilities $0.2,0.4,0.4$, and the corresponding regression values are $0.20,0.30,0.80$. Move the threshold upward by $\delta=0.10$, to $0.35$.

At the Bayes threshold, the labels predicted at these three covariate values are $0,1,1$. At the displaced threshold, they are $0,0,1$. Only the middle value, with probability $0.4$, changes label. Its margin is $M=|0.30-0.25|=0.05$, so the proposition gives $$ R(g_{t+\delta})-R(g^*)=4(0.4)(0.05)=0.08. $$ To check directly, at $\eta=0.30$ predicting 1 costs $1(1-0.30)=0.70$, whereas predicting 0 costs $3(0.30)=0.90$. The cost increase is $0.20$ at that covariate value, and $0.4(0.20)=0.08$ in the population. The other two values retain their Bayes predictions and add no regret.

Separating Threshold and Regression Contributions

Now allow $\hat\eta$ to differ from $\eta$. The following bound separates the effect of the threshold displacement from the effect of regression estimation. It applies to a fixed $\delta$ and a regression estimate trained on data independent of the test covariate $X$. Expectations involving $\hat\eta$ include both the training data and an independent test covariate.

Theorem: Let $d=|\delta|$, $M=|\eta(X)-t|$, and $\varepsilon_p^p=E_{\mathrm{train}}E_X|\hat\eta(X)-\eta(X)|^p$, where $p\ge1$. For every $h>0$, $$ E_{\mathrm{train}}\!\left[R(\hat g_\delta)-R(g^*)\right] \le S\left\{E_X[M\mathbf{1}\{M\le 2d\}] +E_{\mathrm{train}}E_X[M\mathbf{1}\{M\le 2|\hat\eta(X)-\eta(X)|\}]\right\}, $$ and, in particular, $$ E_{\mathrm{train}}\!\left[R(\hat g_\delta)-R(g^*)\right] \le S\left\{E_X[M\mathbf{1}\{M\le 2d\}] +E_X[M\mathbf{1}\{M\le h\}] +2^p h^{1-p}\varepsilon_p^p\right\}. $$

Proof. Put $e(X)=|\hat\eta(X)-\eta(X)|$. If $\hat g_\delta(X)\ne g^*(X)$, the two decisions lie on opposite sides of $t$, so $M(X)\le|\hat\eta(X)-(t+\delta)|+d$ is not needed: directly, crossing from $\eta(X)$ to the thresholded estimate implies $M(X)\le e(X)+d$. Indeed, if $\eta(X)\ge t$ but $\hat\eta(X)<t+\delta$, then $\eta(X)-t\le|\eta(X)-\hat\eta(X)|+d$; if $\eta(X)<t$ but $\hat\eta(X)\ge t+\delta$, then $t-\eta(X)\le|\eta(X)-\hat\eta(X)|+d$. These inequalities also cover either sign of $\delta$.

For nonnegative $M,e,d$, $M\le e+d$ implies $M\le2d$ or $M\le2e$: if both inequalities failed, then $e<M/2$ and $d<M/2$, contradicting $M\le e+d$. The exact excess-risk identity therefore bounds regret by $S$ times the sum of the two indicators in the first inequality of the theorem, weighted by $M$. Taking expectations proves that inequality.

For the second inequality, split the regression term according to $M\le h$ or $M>h$. On the latter event, $M\le2e$ implies $e\ge M/2$. Since $p\ge1$, $$ M\mathbf{1}\{M>h,\ e\ge M/2\} \le M\left(\frac{2e}{M}\right)^p =2^p e^p M^{1-p} \le2^p h^{1-p}e^p. $$ The contribution from $M\le h$ is at most $E_X[M\mathbf{1}\{M\le h\}]$. Taking expectations proves the stated bound. $\square$

The first term is purely a threshold term: it remains even if $\hat\eta=\eta$. The second and third terms measure the additional effect of regression error. This separation is useful because threshold error is concentrated near the Bayes boundary, while regression error can be controlled through an appropriate norm of $\hat\eta-\eta$.

Worked Example: Threshold Error Under a Margin Condition

Suppose costs are equal to 1, so $S=2$ and $t=0.5$. Let $M=|\eta(X)-0.5|$ have the uniform distribution on $[0,0.5]$, and take a threshold displacement $\delta=0.1$. For $0\le u\le0.5$, $P(M\le u)=2u$, a margin condition with exponent $\alpha=1$ and constant $C=2$.

The threshold-only excess risk is $$ 2E[M\mathbf{1}\{M\le0.1\}] =2\int_0^{0.1}m(2)\,dm =4\left[\frac{m^2}{2}\right]_0^{0.1} =0.02. $$ The margin-condition bound on that term is $S C(2d)^{\alpha+1}=2(2)(0.2)^2=0.16$, which is valid but conservative. The exact calculation shows why the margin condition gives a useful rate without generally giving the sharp constant.

Rates Under a Margin Condition

A common assumption quantifies how much covariate probability lies close to the decision boundary. Suppose there are constants $C>0$ and $\alpha\ge0$ such that $$ P(M\le u)\le C u^\alpha \qquad\text{for every }u>0. $$ This is a margin condition centered at the cost-sensitive threshold $t$. It implies $E[M\mathbf{1}\{M\le u\}]\le uP(M\le u)\le C u^{\alpha+1}$. Applying this to the theorem gives the convenient bound $$ E_{\mathrm{train}}[R(\hat g_\delta)-R(g^*)] \le S\left\{C(2d)^{\alpha+1}+C h^{\alpha+1}+2^p h^{1-p}\varepsilon_p^p\right\}. $$ If $\varepsilon_p>0$, choosing $h=\varepsilon_p^{p/(\alpha+p)}$ balances the last two terms up to constants. Consequently, for a constant depending only on $C,p,\alpha$, the bound has the form $$ E_{\mathrm{train}}[R(\hat g_\delta)-R(g^*)] \le S\left\{C2^{\alpha+1}d^{\alpha+1} +K\varepsilon_p^{\,p(\alpha+1)/(\alpha+p)}\right\}. $$ When $\varepsilon_p=0$, the regression contribution is zero, as follows by letting $h$ decrease to zero in the preceding bound. The threshold term remains unless the displacement itself is zero or there is no probability near the affected boundary region.

Worked Example: A Threshold Shift and Regression Error Affect Different Points

Use equal costs, so $S=2$ and $t=0.5$. Let $X$ have four equally likely values, with regression values $\eta=0.45,0.51,0.56,0.80$, respectively. Set $\delta=0.02$, and suppose the fitted values are $\hat\eta=0.45,0.51,0.50,0.80$. The classification threshold is $0.52$.

The Bayes classifier predicts $0,1,1,1$. With the true regression function but the shifted threshold, the predictions would be $0,0,1,1$: the value $0.51$ is lost solely because of threshold displacement. Its margin is $0.01$, so its population regret is $2(0.01)(0.25)=0.005$.

The fitted classifier predicts $0,0,0,1$. In addition to the threshold-induced error at $0.51$, it misses the point with $\eta=0.56$, where the estimate has error $0.06$. That point has margin $0.06$, so its population regret is $2(0.06)(0.25)=0.03$. Total excess risk is $0.005+0.03=0.035$. This calculation isolates the two mechanisms: the shifted threshold changes the decision at $0.51$, while regression error creates the additional mistake at $0.56$.

Common Pitfall and Practical Interpretation

A common mistake is to argue that a good regression estimate guarantees a good classifier even when the decision threshold is wrong. The worked example with known $\eta$ already disproves this: setting $\hat\eta=\eta$ removes regression error, but a displaced threshold can still reverse predictions near $t$. Conversely, a threshold perturbation need not change any labels if no regression values lie in the interval between the two thresholds.

Another mistake is to treat $d$ as if it were simply another regression error and report only a bound in terms of $\varepsilon_p$. The threshold contribution depends on the probability mass near $t$, specifically through $E[M\mathbf{1}\{M\le2d\}]$. Under the margin condition it is of order $d^{\alpha+1}$, but without such a condition it should be retained in its expectation form. This is especially important when the regression function has substantial mass close to the decision boundary.

Key takeaway: A displaced threshold can create regret even with a perfect regression function. Bound it through the margin around the Bayes threshold, and account separately for regression estimation error.

Check Your Understanding

Use the definitions and bounds above to check your understanding.

For false-negative cost $C_{\mathrm{FN}}=4$ and false-positive cost $C_{\mathrm{FP}}=2$, calculate $S$ and the Bayes threshold $t$.
Why does an exact regression estimate not ensure zero excess risk when the classifier uses threshold $t+\delta$ with $\delta\ne0$?
State the margin condition centered at the cost-sensitive threshold, and explain what its exponent describes.
In the theorem's proof, why does $M\le e+d$ imply that either $M\le2d$ or $M\le2e$?
Under the margin condition, what order does the threshold-only contribution have as $d$ decreases?