Logistic-Loss Kernel Classification and Regret

From Logistic Risk to Classification Regret

A kernel classifier may be trained by minimizing a regularized logistic objective, while its practical goal is to make accurate class decisions. The link between these goals is quantitative: a small enough excess logistic risk guarantees small classification regret. The link is not a direct identity, however. Logistic loss measures probability quality as well as which side of the decision boundary a score falls on, and its curvature weakens for large-magnitude scores.

Let $Y\in\{-1,+1\}$, let $X$ be the predictor, and write $\eta(x)=P(Y=+1\mid X=x)$. For a real-valued score $f$, use the prediction rule $g_f(x)=+1$ when $f(x)\geq 0$, and $g_f(x)=-1$ otherwise. The logistic loss at score $t$ and label $y$ is $\ell(y,t)=\log(1+\exp(-yt))$.

Definition: The conditional logistic risk at $x$ is $$ L_{\eta(x)}(t)=\eta(x)\log(1+\exp(-t))+ (1-\eta(x))\log(1+\exp(t)). $$ The logistic risk of $f$ is $\mathcal L(f)=E[\ell(Y,f(X))]$. Its unrestricted infimum is $\mathcal L^*=E[\inf_{t\in\mathbb R}L_{\eta(X)}(t)]$. The classification regret is $R_{01}(f)-R_{01}^*$, where $R_{01}(f)=P(g_f(X)\ne Y)$ and $R_{01}^*$ is the risk of a Bayes classifier.

For $0<\eta(x)<1$, the conditional logistic risk is minimized at $t^*(x)=\log\{\eta(x)/(1-\eta(x))\}$, and its minimum is the Bernoulli entropy $-\eta(x)\log\eta(x)-(1-\eta(x))\log(1-\eta(x))$. At $\eta(x)=0$ or $1$, the infimum is approached as $t$ tends to the corresponding infinite endpoint; it need not be attained by a finite score.

The score $t$ also represents the probability $q=\sigma(t)$, where $\sigma(t)=1/(1+\exp(-t))$. For $0<\eta<1$, the conditional excess has the exact form

L_\eta(t)-\inf_{s\in\mathbb R}L_\eta(s) =\eta\log\frac{\eta}{q}+(1-\eta)\log\frac{1-\eta}{1-q}.

This is the Kullback–Leibler divergence between Bernoulli probabilities $\eta$ and $q$. The identity follows by substituting $q=\sigma(t)$, so that $\log q=t-\log(1+\exp(t))$ and $\log(1-q)=-\log(1+\exp(t))$, and then subtracting the conditional minimum. At endpoint values of $\eta$, the same expression is interpreted by continuity.

A Regret Bound and Its Proof

The next result translates logistic excess risk into a bound on classification regret without requiring scores to be bounded. It is conservative in some problems, but it applies even when probabilities are very close to zero or one.

Theorem: Suppose the logistic risk is finite. Then $$ R_{01}(f)-R_{01}^*\leq \sqrt{2\{\mathcal L(f)-\mathcal L^*\}}. $$

The proof uses the binary form of Pinsker’s inequality. For $p,q\in(0,1)$, define $K(p,q)=p\log(p/q)+(1-p)\log\{(1-p)/(1-q)\}$. With $q$ fixed, the second derivative with respect to $p$ is $1/[p(1-p)]$, which is at least $4$. Thus the function $h(p)=K(p,q)-2(p-q)^2$ has $h''(p)\geq0$, while $h(q)=0$ and $h'(q)=0$. Convexity implies $h(p)\geq0$; continuity gives the endpoint cases. Therefore $K(p,q)\geq2(p-q)^2$.

At a fixed $x$, put $\eta=\eta(x)$, $q=\sigma(f(x))$, and $\delta=|\eta-1/2|$. If $g_f(x)$ disagrees with a Bayes decision, then $q$ is on the opposite side of $1/2$ from $\eta$, or equals $1/2$. In either case, $|\eta-q|\geq\delta$. The conditional classification regret is $2\delta$ on disagreement and zero otherwise. The Bernoulli inequality just proved therefore gives, pointwise,

2\delta\,\mathbf 1\{g_f(x)\text{ disagrees with Bayes}\} \leq \sqrt{2\{L_{\eta(x)}(f(x))-\inf_t L_{\eta(x)}(t)\}}.

Taking expectations bounds the classification regret by the expectation of the right-hand side. Since the square root is concave, Jensen’s inequality gives $E[\sqrt{2D(X)}]\leq\sqrt{2E[D(X)]}$, where $D(X)$ is the nonnegative conditional logistic excess. Its expectation is $\mathcal L(f)-\mathcal L^*$. This proves the theorem. $\square$

Worked Example: A Wrong-Side Score

At a particular $x$, suppose $\eta(x)=0.7$ and the score is $t=-0.1$. The Bayes classifier predicts $+1$, whereas this score predicts $-1$. Its conditional classification regret is $2(0.7)-1=0.4$.

The probability represented by the score is $q=\sigma(-0.1)\approx0.4750208$. The conditional logistic excess is

0.7\log\frac{0.7}{0.4750208} +0.3\log\frac{0.3}{0.5249792} \approx 0.7(0.3877)+0.3(-0.5596) \approx 0.1035.

The theorem bounds the regret by $\sqrt{2(0.1035)}\approx0.4550$. This is above the actual regret $0.4$, as required. The bound is not an estimate of the actual regret; it is a guarantee that rules out regret larger than the stated value.

What Clipping and Bounded Scores Change

For $B>0$, clipping a score means replacing it by $f_B(x)=\max\{-B,\min\{f(x),B\}\}$. Then $\sigma(f_B(x))$ lies between $\sigma(-B)$ and $\sigma(B)$, and the logistic loss is bounded above by $\log(1+\exp(B))$. Clipping also leaves the sign of every nonzero score unchanged, so it leaves the associated class decisions unchanged under the stated threshold rule.

Clipping is useful for controlling the range of probability predictions, losses, and derivatives in analyses of kernel estimators. It is not a free improvement in logistic risk: clipping a large score that points toward the correct class can increase its logistic loss. The regret theorem itself needs no clipping; its input is the excess risk relative to the unrestricted infimum.

Bounded scores also reveal the role of curvature. Differentiating the conditional risk gives $L_\eta''(t)=\sigma(t)\{1-\sigma(t)\}$. This is largest at the decision threshold $t=0$, where it equals $1/4$, and decreases as $|t|$ grows. On $[-B,B]$, it is bounded below by

c_B=\sigma(B)\{1-\sigma(B)\}>0.

This lower bound can give a quadratic excess-risk bound, but only when the score and the conditional risk minimizer both lie in the interval. That condition matters: if $\eta$ is extremely close to zero or one, its unrestricted optimal logit may lie outside $[-B,B]$.

Theorem: If $t,t^*\in[-B,B]$, where $t^*=\log\{\eta/(1-\eta)\}$ is the conditional minimizer, then $$ L_\eta(t)-L_\eta(t^*)\geq \frac{c_B}{2}(t-t^*)^2. $$ In particular, this statement assumes $0<\eta<1$ and $\eta\in[\sigma(-B),\sigma(B)]$.

To prove it, the second derivative satisfies $L_\eta''(s)\geq c_B$ throughout $[-B,B]$. Taylor’s formula with integral remainder, using $L_\eta'(t^*)=0$, yields

L_\eta(t)-L_\eta(t^*)= (t-t^*)^2\int_0^1(1-u)L_\eta''(t^*+u(t-t^*))\,du \geq c_B(t-t^*)^2\int_0^1(1-u)\,du =\frac{c_B}{2}(t-t^*)^2.

The segment between $t^*$ and $t$ stays in $[-B,B]$, so the curvature bound applies at every point of the integral. This proves the result. $\square$

Worked Example: Curvature for a Clipped Wrong-Side Score

Take $\eta=0.6$, a score $t=-0.2$, and $B=1$. The optimal score is $t^*=\log(0.6/0.4)=\log(1.5)\approx0.4055$. Both scores lie in $[-1,1]$, so the curvature theorem applies. Here $c_1=\sigma(1)\{1-\sigma(1)\}\approx0.1966$, giving

L_{0.6}(-0.2)-L_{0.6}(t^*) \geq \frac{0.1966}{2}(0.4055-(-0.2))^2 \approx 0.0360.

Direct calculation checks the scale of this lower bound. Since $q=\sigma(-0.2)\approx0.450166$, the excess is

0.6\log\frac{0.6}{0.450166} +0.4\log\frac{0.4}{0.549834} \approx 0.6(0.2873)+0.4(-0.3182) \approx 0.04513.

The score predicts $-1$, so its classification regret is $2(0.6)-1=0.2$. The unrestricted square-root guarantee is $\sqrt{2(0.04513)}\approx0.3004$. The curvature calculation gives a valid lower bound on this example’s logistic excess; it does not replace the general regret theorem.

Interpreting Risk Guarantees

A regularized kernel analysis often first bounds the logistic risk of a fitted score relative to a comparator, rather than directly relative to $\mathcal L^*$. To use the regret theorem, the excess must be measured against the unrestricted logistic infimum. If an argument establishes $\mathcal L(\hat f)-\mathcal L^*\leq\varepsilon$, then it immediately gives $R_{01}(\hat f)-R_{01}^*\leq\sqrt{2\varepsilon}$. If the available inequality compares $\hat f$ only with a restricted comparator $f_0$, its approximation excess $\mathcal L(f_0)-\mathcal L^*$ must also be included before applying this conclusion.

The square-root form is distribution-free but can be loose. It converts a logistic excess of size $\varepsilon$ into a regret bound of order $\sqrt{\varepsilon}$. Curvature can provide more information when scores and conditional optima remain in a bounded interval. But as $B$ increases, $c_B$ decreases toward zero, reflecting the flat tails of logistic loss. A bound based on uniform curvature can therefore become weak when the allowed score range is large.

Worked Example: Correct Decision, Nontrivial Probability Error

Suppose $\eta=0.99$ and the score is $t=1$. Then $q=\sigma(1)\approx0.7310586$. Both the Bayes classifier and the score predict $+1$, so the conditional classification regret is zero, even though the score substantially understates the positive-class probability.

The conditional logistic excess is

0.99\log\frac{0.99}{0.7310586} +0.01\log\frac{0.01}{0.2689414} \approx 0.99(0.3032)+0.01(-3.2919) \approx 0.2673.

This example shows why logistic excess risk is not the same quantity as classification regret: logistic loss penalizes probability miscalibration even when the predicted class is correct. The regret guarantee remains valid, but it does not assert that a large logistic excess must imply a large classification regret.

Common Pitfall

Assuming clipping is required for calibration. It is not: the square-root regret theorem follows from the Bernoulli divergence inequality and applies to finite, unclipped scores.
Using bounded-score curvature without checking the optimum. The lower-curvature theorem requires both the score and $t^*$ to lie in $[-B,B]$. Bounded $f(x)$ alone does not ensure this when $\eta(x)$ is near zero or one.
Treating logistic excess as classification regret. A score can have positive logistic excess while making the Bayes decision, as the $\eta=0.99$ example shows.
Assuming clipping always reduces loss. Clipping preserves the sign for $B>0$, but it can increase loss when it shortens a correctly signed score.

The practical distinction is important: use unrestricted logistic excess to obtain the general regret conversion, and use bounded-score curvature only when its interval conditions are verified. Clipping can support boundedness arguments, but it does not by itself establish a sharper classification guarantee.

Check Your Understanding

Answer each question by identifying the relevant condition or calculation.

For a score $t$, what Bernoulli probability $q$ does the logistic model assign to class $+1$, and how is conditional excess risk expressed using $q$ and $\eta$?
Why does disagreement with the Bayes decision imply $|\eta-q|\geq|\eta-1/2|$?
State the square-root regret bound and identify the Jensen inequality used in its proof.
What extra condition, beyond $|t|\leq B$, is needed to apply the stated curvature theorem?
Does clipping a score at a positive threshold change its class decision? Can it increase logistic loss? Explain both answers.