Exp-Concavity of Logistic Loss on Bounded Score Ranges

Why the Score Range Matters

Logistic loss is a standard loss for binary prediction, but its curvature is not uniform over every possible score. When predictions are restricted to a bounded interval, the loss has a useful property: exponentiating its negative produces a concave function of the score. That property supports fast aggregation guarantees, with a comparator penalty proportional to the logarithm of the inverse prior weight rather than to the square root of sample size.

The size of the score interval matters. A wider interval permits more negative signed margins, where logistic loss is less favorable for exp-concavity. We derive the parameter directly from the second derivative, identify when it is sharp, and then use it to prove a finite-class online aggregation bound. The endpoint case of a score interval containing only zero is treated separately, since concavity on a singleton has a special consequence.

Logistic Loss and Exp-Concavity

Encode the binary label as $y\in\{-1,+1\}$, and let $t\in\mathbb{R}$ be a prediction score. The signed margin is $yt$: a positive margin means the score points toward the observed label. The logistic loss is

\ell(y,t)=\log\!\left(1+\exp(-yt)\right).

For a positive number $\eta$, exp-concavity concerns the function $t\mapsto\exp(-\eta\ell(y,t))$. The definition below is applied separately for each label, on the score interval under consideration.

Definition: A loss $\ell(y,t)$ is $\eta$-exp-concave on an interval $I$ if, for every allowed label $y$, the function $t\mapsto\exp(-\eta\ell(y,t))$ is concave on $I$. Concavity is understood on the interval itself: for $t_1,t_2\in I$ and $a\in[0,1]$, the function at $at_1+(1-a)t_2$ is at least the corresponding weighted average of its values at $t_1,t_2$.

We seek parameters that work uniformly for both labels on $I=[-S,S]$, where $S\geq0$. The calculation uses the signed margin, but concavity is with respect to the score $t$.

The Curvature Calculation

Write $q=(1+\exp(yt))^{-1}$. Differentiating the logistic loss with respect to $t$ gives

\ell_t(y,t)=-yq, \qquad \ell_{tt}(y,t)=q(1-q).

In particular, $(\ell_t)^2=q^2$, since $y^2=1$. For $g(t)=\exp(-\eta\ell(y,t))$, the chain rule yields

g''(t) = \eta g(t)\left\{\eta\bigl(\ell_t(y,t)\bigr)^2-\ell_{tt}(y,t)\right\}.

Here $\eta g(t)>0$, so the sign of $g''(t)$ is the sign of the expression in braces. Substitution gives the following precise condition.

Curvature condition: At a score $t$, the logistic exponential loss has nonpositive second derivative exactly when $$ \eta \leq \frac{\ell_{tt}(y,t)}{(\ell_t(y,t))^2} =\frac{q(1-q)}{q^2} =\frac{1-q}{q} =\exp(yt). $$

The last equality follows from $q=(1+\exp(yt))^{-1}$. On the symmetric interval $[-S,S]$, the smallest possible signed margin over both labels is $-S$. Thus, for a nontrivial interval, the curvature condition holds everywhere if $\eta\leq\exp(-S)$.

Worked Example: Checking Curvature at the Worst Margin

Let $S=2$, take $y=+1$, and consider the score $t=-2$. This gives the smallest margin $yt=-2$. The candidate parameter from the curvature condition is $\eta=\exp(-2)$, approximately $0.1353$.

At this score, $q=1/(1+\exp(-2))$, approximately $0.8808$. Consequently,

\ell_{tt}=q(1-q)\approx 0.8808(0.1192)\approx 0.1050, \qquad \eta(\ell_t)^2=\exp(-2)q^2\approx 0.1353(0.7758)\approx 0.1050.

The two quantities agree, as expected at the limiting parameter. Therefore $g''(-2)=0$ for this label and score when $\eta=\exp(-2)$; for smaller positive $\eta$, $g''(-2)<0$. This checks the boundary calculation numerically as well as algebraically.

The Valid Parameter and Its Sharpness

For $S>0$, the endpoint $-S$ is part of an interval containing points to its right. This allows the curvature calculation to establish not only validity but also sharpness. The case $S=0$ does not have such an interval and must not be folded into the same sharpness argument.

Theorem: Suppose $S>0$. For both labels $y\in\{-1,+1\}$, logistic loss is $\eta$-exp-concave on $[-S,S]$ whenever $0<\eta\leq\exp(-S)$. Moreover, $\exp(-S)$ is the largest positive parameter that works uniformly for both labels on that interval. If $S=0$, the restricted score domain is the singleton $\{0\}$, on which logistic loss is $\eta$-exp-concave for every $\eta>0$; there is no largest finite parameter.

Proof. First suppose $S>0$. For any $t\in[-S,S]$ and $y\in\{-1,+1\}$, the signed margin satisfies $yt\geq-S$. Since the exponential function is increasing, $\exp(yt)\geq\exp(-S)$. Thus every $0<\eta\leq\exp(-S)$ satisfies the curvature condition at every score in the interval. The function $g$ is twice continuously differentiable, so $g''(t)\leq0$ throughout the interval implies that $g$ is concave there.

To show that no larger parameter works uniformly, suppose $\eta>\exp(-S)$ and take $y=+1$ at $t=-S$. Then $\exp(yt)=\exp(-S)<\eta$, so the curvature condition fails strictly and $g''(-S)>0$. The derivative $g''$ is continuous. Since $S>0$, there are scores in $[-S,S]$ immediately to the right of $-S$; continuity therefore gives a subinterval of positive length on which $g''>0$. A twice-differentiable concave function cannot have positive second derivative on such a subinterval. Hence this $\eta$ does not give concavity on $[-S,S]$.

If $S=0$, any two scores in the domain are both zero. Every convex combination of them is also zero, so the defining concavity inequality holds with equality for any function restricted to this domain. It therefore holds for $\exp(-\eta\ell(y,t))$ for every $\eta>0$. There is no largest finite choice. $\square$

Worked Example: A Different Score Bound

Suppose scores are restricted to $[-\log 4,\log 4]$. Here $S=\log 4$, so the largest uniform parameter is

\eta_*=\exp(-S)=\exp(-\log 4)=\frac14.

The limiting case occurs at label $y=+1$ and score $t=-\log 4$, where the margin is $-\log 4$. At this point $q=1/(1+\exp(-\log 4))=1/(1+1/4)=4/5$. Thus $\ell_{tt}=q(1-q)=4/25=0.16$, while $(\ell_t)^2=q^2=16/25=0.64$. The curvature condition becomes $\eta(0.64)\leq0.16$, or $\eta\leq1/4$. For example, $\eta=0.3$ violates it, so it cannot give uniform exp-concavity on this interval.

From Exp-Concavity to an Aggregation Guarantee

Exp-concavity is useful for aggregation because it applies to a weighted average of scores. Let $t_1,\ldots,t_M\in[-S,S]$ be candidate scores and let $w_1,\ldots,w_M$ be nonnegative weights summing to one. Their average $\bar t=\sum_{j=1}^M w_jt_j$ also belongs to $[-S,S]$. Concavity of the exponential loss gives

\exp\!\left(-\eta\ell\!\left(y,\sum_{j=1}^M w_jt_j\right)\right) \geq \sum_{j=1}^M w_j\exp\!\left(-\eta\ell(y,t_j)\right).

Taking logarithms and rearranging, which is valid because both sides are positive, yields

\ell\!\left(y,\sum_{j=1}^M w_jt_j\right) \leq -\frac{1}{\eta}\log\!\left(\sum_{j=1}^M w_j\exp(-\eta\ell(y,t_j))\right).

This inequality controls the loss of the averaged score by a logarithmic average of the candidate exponential losses. The following result turns it into a cumulative comparator guarantee. It is deterministic: it holds for every sequence of labels and candidate scores satisfying the stated range condition.

Theorem: Consider $M$ experts with prior weights $\pi_1,\ldots,\pi_M>0$, where $\sum_{j=1}^M\pi_j=1$. At each round $i=1,\ldots,n$, expert $j$ gives a score $t_{ij}\in[-S,S]$, and the observed label is $y_i\in\{-1,+1\}$. Choose a parameter $\eta>0$ for which logistic loss is $\eta$-exp-concave on $[-S,S]$. Define $$ w_{ij} = \frac{\pi_j\exp\!\left(-\eta\sum_{r=1}^{i-1}\ell(y_r,t_{rj})\right)} {\sum_{k=1}^M\pi_k\exp\!\left(-\eta\sum_{r=1}^{i-1}\ell(y_r,t_{rk})\right)}, \qquad \bar t_i=\sum_{j=1}^M w_{ij}t_{ij}. $$ Then for every expert $j$, $$ \sum_{i=1}^n\ell(y_i,\bar t_i) \leq \sum_{i=1}^n\ell(y_i,t_{ij})+\frac{\log(1/\pi_j)}{\eta}. $$

Proof. Define the potential before round $i$ by

W_i=\sum_{j=1}^M\pi_j \exp\!\left(-\eta\sum_{r=1}^{i-1}\ell(y_r,t_{rj})\right).

In particular, $W_1=1$. The round-$i$ weights in the theorem are the normalized terms in this sum. Applying the weighted-score inequality from exp-concavity with those weights gives

\exp(-\eta\ell(y_i,\bar t_i)) \geq \sum_{j=1}^M w_{ij}\exp(-\eta\ell(y_i,t_{ij})) =\frac{W_{i+1}}{W_i}.

Taking logarithms and multiplying by $-1/\eta$ reverses the inequality because $-1/\eta<0$. Therefore

\ell(y_i,\bar t_i)\leq-\frac1\eta\log\!\left(\frac{W_{i+1}}{W_i}\right).

Summing over $i$ telescopes the logarithms, giving $\sum_{i=1}^n\ell(y_i,\bar t_i)\leq-\eta^{-1}\log W_{n+1}$, since $W_1=1$. For any fixed expert $j$, its term is one of the positive terms in $W_{n+1}$, so

W_{n+1}\geq \pi_j\exp\!\left(-\eta\sum_{i=1}^n\ell(y_i,t_{ij})\right).

Applying $-\eta^{-1}\log(\cdot)$ to this lower bound on $W_{n+1}$ gives the claimed comparator inequality. $\square$

Worked Example: Two Experts on a One-Round Sequence

Take $S=1$, two experts with equal prior weights $\pi_1=\pi_2=1/2$, and the valid parameter $\eta=\exp(-1)\approx0.3679$. In a single round, let their scores be $t_{11}=+1$ and $t_{12}=-1$, and let the observed label be $y_1=+1$. The initial weights are both $1/2$, so the aggregate score is $\bar t_1=(1/2)(1)+(1/2)(-1)=0$.

The aggregate loss is $\ell(+1,0)=\log 2\approx0.6931$. The two expert losses are

\ell(+1,+1)=\log(1+\exp(-1))\approx0.3133, \qquad \ell(+1,-1)=\log(1+\exp(1))\approx1.3133.

The per-round exp-concavity inequality gives an upper bound of

-\frac{1}{\eta}\log\!\left\{\frac12\exp(-\eta(0.3133))+ \frac12\exp(-\eta(1.3133))\right\} \approx 0.77.

Thus the aggregate loss $0.6931$ is below the logarithmic-average bound. The theorem also gives a comparator bound against the better expert: its right-hand side is $0.3133+\log(2)/\exp(-1)\approx0.3133+1.884=2.197$. This bound is valid but not tight for one round; its value is that it holds cumulatively, for every sequence, and with the prior weight made explicit.

Interpreting the Fast Penalty

When $S>0$, the largest valid uniform parameter is $\eta_*=\exp(-S)$. Using it in the theorem makes the comparator penalty $\exp(S)\log(1/\pi_j)$. With a uniform prior over $M$ experts, $\pi_j=1/M$, this becomes $\exp(S)\log M$. Dividing the cumulative inequality by $n$ gives an average-loss difference bounded by $\exp(S)\log M/n$. The $1/n$ dependence is the fast aggregation rate; the score-range dependence appears in the multiplicative factor $\exp(S)$.

This is a pathwise online guarantee, not by itself a statement about a random sample’s population risk. Its strength is that it needs no distributional assumption on the sequence. It compares the aggregate to each expert while accounting for that expert’s prior weight. A smaller prior weight increases the penalty through $\log(1/\pi_j)$.

For $S=0$, every expert can only predict the score zero, and every round has loss $\log 2$, regardless of the label. The aggregate and each expert therefore have identical cumulative losses. The generic theorem remains valid for any $\eta>0$, but the exact comparator difference is zero; there is no largest finite exp-concavity parameter to substitute into a formula.

Common Mistakes

Using the wrong margin endpoint. The restrictive margin is $-S$, not $S$, because $\exp(yt)$ is smallest there. This is why the parameter is $\exp(-S)$.
Confusing exp-concavity with convexity of the loss. Logistic loss is convex in the score, but the aggregation argument uses concavity of $\exp(-\eta\ell)$.
Calling the bound a population-risk result without assumptions. The proved inequality compares cumulative losses on the given sequence. A population statement requires additional probabilistic reasoning.
Applying the sharpness argument at $S=0$. Positive curvature at a point does not disprove concavity on a singleton. For $S=0$, the defining concavity inequality holds automatically on $\{0\}$, for every positive $\eta$.
Ignoring the range dependence. The fast comparator penalty with the largest uniform parameter grows as $\exp(S)$. A bound on scores is therefore part of the guarantee, not a cosmetic assumption.

Check Your Understanding

Use the curvature condition and aggregation proof to answer the following.

For scores in $[-3,3]$, what is the largest uniform exp-concavity parameter for both labels?
At what label and score is the curvature condition most restrictive on $[-S,S]$? Explain why.
Why does a parameter larger than $\exp(-S)$ fail when $S>0$, and why does that argument not apply when $S=0$?
With a uniform prior over $M$ experts, what comparator penalty follows from the largest valid parameter on $[-S,S]$ for $S>0$?
Does the cumulative aggregation theorem require the labels to be independent or identically distributed? State what assumptions it does require.