One-Versus-Rest Surrogates and Multiclass Consistency

Why Independent Binary Scores Need a Multiclass Check

One-versus-rest (OVR) classification turns a $K$-class problem into $K$ binary problems. For each class, a separate score is fitted to distinguish that class from all the others; prediction then selects the class with the largest score. This construction is convenient, but solving each binary problem well does not automatically solve the multiclass problem well. The key question is whether the optimal score for each binary problem preserves the ordering of the class probabilities.

We study this question through margin losses. The conclusions concern the population conditional risks: they describe what the OVR method targets when each class-specific score is optimized, rather than the additional effects of a particular finite-sample fitting algorithm.

Conditional Risk for One-Versus-Rest Scores

Let $Y$ take values in $\{1,\ldots,K\}$, and fix an input $x$. Write $\eta_k=P(Y=k\mid X=x)$, so $\eta_k\geq 0$ and $\sum_{k=1}^K\eta_k=1$. The score vector is $u=(u_1,\ldots,u_K)$. A margin loss $\phi:\mathbb{R}\to[0,\infty)$ assigns loss $\phi(u_k)$ when the label is $k$, and $\phi(-u_k)$ when it is not $k$. The OVR loss sums these $K$ binary losses.

Definition: The one-versus-rest conditional surrogate risk at class-probability vector $\eta=(\eta_1,\ldots,\eta_K)$ and score vector $u$ is $$ C_{\mathrm{OVR}}(\eta,u)=\sum_{k=1}^K C_{\eta_k}(u_k), \qquad C_q(t)=q\phi(t)+(1-q)\phi(-t). $$ The decoded prediction is $d(u)\in\arg\max_k u_k$, with a fixed rule for breaking ties. The conditional zero-one risk of predicting class $j$ is $1-\eta_j$, so its excess over the Bayes risk is $\eta_{\max}-\eta_j$, where $\eta_{\max}=\max_k\eta_k$.

The sum separates by coordinate: minimizing $C_{\mathrm{OVR}}$ means minimizing $C_{\eta_k}$ for each $k$. That fact explains both the appeal of OVR and its main risk. The binary conditional minimizer for a class is determined by $\eta_k$ alone; the final decoder succeeds when those separate minimizers rank classes in the same order as their probabilities.

Worked Example: Squared-Margin Scores Rank the Classes

Take $\phi(t)=(1-t)^2$. For a binary class probability $q$, expand the conditional risk: $$ C_q(t)=q(1-t)^2+(1-q)(1+t)^2 =1-2(2q-1)t+t^2. $$

Differentiating gives $C_q'(t)=2t-2(2q-1)$, so the unique minimizer is $g(q)=2q-1$. Now let $\eta=(0.6,0.3,0.1)$. The three independently optimal scores are $$ g(0.6)=0.2,\qquad g(0.3)=-0.4,\qquad g(0.1)=-0.8. $$ Their largest value is the first score, corresponding to the largest class probability. In this example, minimizing each binary conditional risk produces the Bayes class.

When the Optimal Score Preserves the Ranking

The useful condition is stronger than saying that a margin loss is calibrated for a binary decision at threshold $1/2$. OVR with an argmax decoder needs the optimal binary score to carry information about the ordering of probabilities, including probabilities below $1/2$.

Definition: Suppose that for every $q$ in the probability range under consideration, $C_q(t)$ has a unique minimizer $g(q)$. The loss has an increasing conditional minimizer on that range if $g$ is continuous and strictly increasing there. If each component of the score vector is minimized separately, this condition implies that a largest class probability has a largest optimal score.

For a precise risk-consistency statement, assume the probabilities lie in a compact interval $I\subseteq[0,1]$, and scores are restricted to a compact interval $J$. Assume $C_q(t)$ is continuous in $(q,t)$ on $I\times J$, has a unique minimizer $g(q)\in J$ for every $q\in I$, and $g$ is continuous and strictly increasing on $I$. Require also that $\eta_k\in I$ almost surely. These assumptions include the squared-margin loss with $I=[0,1]$ and $J=[-1,1]$. A logistic-loss example with bounded scores will be given below.

Theorem: Under these assumptions, OVR with the argmax decoder is multiclass consistent over the specified probabilities and scores: for any sequence of measurable score functions whose population OVR surrogate excess risk tends to zero, the population zero-one excess risk also tends to zero.

Here population risk means expectation over $X,Y$. The conditional probabilities are $\eta_k(X)=P(Y=k\mid X)$, and both excess risks are measured relative to their respective minimum population risks. The theorem relies on the increasing-minimizer condition and compactness; it does not claim consistency for every margin loss.

Proof. Fix any $\varepsilon>0$. We first show that there is a $\delta(\varepsilon)>0$ such that, at every allowed $\eta$ and every score vector $u$, a prediction with conditional classification excess at least $\varepsilon$ has conditional surrogate excess at least $\delta(\varepsilon)$.

If no such positive $\delta(\varepsilon)$ existed, there would be a sequence $(\eta^{(m)},u^{(m)})$ whose conditional classification excess is at least $\varepsilon$, but whose conditional surrogate excess tends to zero. Because the probability and score sets are compact, a subsequence converges to some $(\eta,u)$. There are finitely many classes, so we can take a further subsequence on which the decoded class is a fixed $j$. Continuity of the conditional risks implies that the limiting surrogate excess is zero. Since the conditional minimizer is unique in each coordinate, this forces $u_k=g(\eta_k)$ for every $k$.

Along this subsequence, $u^{(m)}_j\geq u^{(m)}_k$ for every $k$, so $g(\eta_j)\geq g(\eta_k)$ in the limit. But the limiting classification excess is at least $\varepsilon$, which means $\eta_{\max}-\eta_j\geq\varepsilon$. For an index $i$ attaining $\eta_{\max}$, strict increase gives $g(\eta_i)>g(\eta_j)$, a contradiction. Thus $\delta(\varepsilon)>0$.

Let $r(X)$ be the conditional classification excess and $s(X)$ the conditional surrogate excess. Both are nonnegative, and $r(X)\leq 1$. The separation just proved implies $$ P\{r(X)\geq\varepsilon\}\leq \frac{E[s(X)]}{\delta(\varepsilon)}, \qquad E[r(X)]\leq \varepsilon+\frac{E[s(X)]}{\delta(\varepsilon)}. $$ If population surrogate excess tends to zero, the limit superior of population classification excess is at most $\varepsilon$. Since this holds for every $\varepsilon>0$, classification excess tends to zero. $\square$

Worked Example: A Direct Excess-Risk Bound for Squared Margins

For squared margins, completing the square in the conditional risk gives $$ C_q(t)-C_q(g(q))=(t-(2q-1))^2. $$ Thus the OVR conditional surrogate excess is $\sum_k (u_k-(2\eta_k-1))^2$. Suppose the decoder selects class $j$, while $i$ has the largest probability, and the conditional classification excess is at least $\varepsilon$. Then $\eta_i-\eta_j\geq\varepsilon$, and $u_j\geq u_i$. Set $e_k=u_k-(2\eta_k-1)$. It follows that $$ e_j-e_i =u_j-u_i+2(\eta_i-\eta_j) \geq 2\varepsilon. $$ Since $a^2+b^2\geq(a-b)^2/2$, $$ \sum_k e_k^2\geq e_i^2+e_j^2 \geq \frac{(e_j-e_i)^2}{2}\geq 2\varepsilon^2. $$ So squared-margin OVR has an explicit conditional separation: classification excess of at least $\varepsilon$ requires surrogate excess of at least $2\varepsilon^2$. This verifies directly how score regret controls decision regret.

Logistic Loss and the Importance of Probability Ordering

The logistic margin loss is $\phi(t)=\log(1+e^{-t})$. Its OVR conditional risk has derivative $$ C_q'(t)=-\frac{q}{1+e^t}+\frac{(1-q)e^t}{1+e^t} =\frac{(1-q)e^t-q}{1+e^t}. $$ For $0<q<1$, setting this derivative to zero yields $e^t=q/(1-q)$, so the unique minimizer is $g(q)=\log(q/(1-q))$. This is strictly increasing in $q$. Therefore, when the probabilities stay bounded away from zero and one, and the score interval contains all these log-odds, the theorem applies. The bounded-away condition makes the optimal scores finite and ensures they fit in a compact score interval.

Worked Example: Logistic Scores Preserve a Three-Class Ordering

Let $\eta=(0.5,0.3,0.2)$. The independently optimal logistic scores are $$ g(0.5)=\log(1)=0,\qquad g(0.3)=\log(3/7)\approx-0.8473,\qquad g(0.2)=\log(1/4)\approx-1.3863. $$ Since $0>-0.8473>-1.3863$, the first score is largest, exactly as the first class probability is largest. The scores are log-odds for each class against its complement, not log-probabilities that sum to a normalized multiclass distribution. Their ranking, rather than such a normalization, is what supports the OVR decision here.

Why One-Versus-Rest Hinge Loss Can Fail

The binary hinge loss is $\phi(t)=(1-t)_+$, where $(a)_+=\max(a,0)$. Its conditional risk behaves differently from the squared and logistic risks. For $-1\leq t\leq1$, $$ C_q(t)=q(1-t)+(1-q)(1+t)=1+(1-2q)t. $$ If $q<1/2$, this expression decreases as $t$ decreases, and its minimum is at $t=-1$. If $q>1/2$, its minimum is at $t=1$. At $q=1/2$, every $t\in[-1,1]$ minimizes the risk. Thus, away from the tie, the optimal score records only which side of $1/2$ the probability lies on; it does not rank probabilities that are both below $1/2$.

Worked Example: Hinge OVR Gives the Same Score to Every Class

Take three class probabilities $\eta=(0.25,0.40,0.35)$. Each probability is below $1/2$, so the unique minimizing hinge score for each class is $-1$. The OVR score vector is therefore $(-1,-1,-1)$, even though class 2 is the unique Bayes class.

With a fixed rule that breaks ties in favor of the smallest index, this score vector predicts class 1, whose conditional excess risk is $0.40-0.25=0.15$. A different fixed tie rule can be defeated by choosing a probability vector whose unique largest component is not its preferred index. Thus the binary threshold property of hinge loss does not imply multiclass consistency under argmax decoding.

Common Mistake: Confusing Binary Calibration with Multiclass Consistency

A common error is to reason: “Each one-versus-rest classifier is binary calibrated, so the largest of their scores must identify the most probable class.” Binary calibration at threshold $1/2$ concerns whether a score chooses the positive or negative side of a binary decision. It does not require scores for two probabilities below $1/2$ to be ordered. With $K\geq3$, multiple class probabilities can all lie below $1/2$, as the hinge example shows.

The correction is to inspect the conditional minimizer $g(q)$. For argmax OVR to recover the Bayes class at the population optimum, the minimizer should preserve probability rankings: if $q_1>q_2$, then $g(q_1)>g(q_2)$. To obtain a risk-consistency result for approximate fits as well, a separation argument such as the theorem’s compactness condition is also needed. These are population properties; finite-sample estimation error and optimization error remain separate concerns.

Key takeaway: OVR losses decompose into binary conditional risks, but multiclass consistency depends on what their optimal scores retain. Strictly increasing conditional minimizers preserve class-probability rankings; threshold-only minimizers, such as hinge loss in the multiclass OVR construction, can discard the ordering needed by an argmax decoder.

Check Your Understanding

Use the conditional-risk definition and the ranking condition to answer these questions.

For squared-margin loss, derive the conditional minimizer and explain why it ranks any two class probabilities in the same order.
Why can a collection of probabilities all below one-half cause a problem for one-versus-rest hinge loss?
For logistic margin loss, solve the first-order condition for the conditional minimizer when $0<q<1$.
In the theorem, what role does compactness play in relating small surrogate excess to small classification excess?
Give a probability vector with a unique largest component for which all one-versus-rest hinge-optimal scores are equal.