Consistency versus Realizable H-Consistency
for Multiclass Classification
Philip M. Long
Microsoft, 1020 Enterprise Way, Sunnyvale, CA 94089

plong@microsoft.com

Rocco A. Servedio
Department of Computer Science, Columbia University, New York, NY 10027

rocco@cs.columbia.edu

Abstract
A consistent loss function for multiclass classification is one such that for any source oflabeled examples, any tuple of scoring functions that minimizes the expected loss will
have classification accuracy close to that of
the Bayes optimal classifier. While consistency has been proposed as a desirable property for multiclass loss functions, we giveexperimental and theoretical results exhibiting a sequence of linearly separable data
sources with the following property: a multiclass classification algorithm which optimizesa loss function due to Crammer and Singer(which is known not to be consistent) produces classifiers whose expected error goes to0, while the expected error of an algorithm
which optimizes a generalization of the loss
function used by LogitBoost (a loss function
which is known to be consistent) is bounded
below by a positive constant.
We identify a property of a loss function, realizable consistency with respect to a restrictedclass of scoring functions, that accounts forthis difference. As our main technical results
we show that the Crammer–Singer loss function is realizable consistent for the class of
linear scoring functions, while the generalization of LogitBoost is not. Our result for
LogitBoost is a special case of a more general theorem that applies to several other loss
functions that have been proposed for multiclass classification.

Proceedings of the 30 th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. JMLR:
W&CP volume 28. Copyright 2013 by the author(s).

1. Introduction
Classification into k > 2 classes is often addressedby learning a real-valued scoring function hz for eachclass z ∈ {1, . . . , k}, and then classifying an item x as
argmaxz hz (x). To learn the scoring functions, a popular approach is to minimize the average, over training examples (x, y), of L(y, h1 (x), ..., hk (x)) where L issome loss function.
One very natural loss function (Zhang, 2004), which
generalizes the loss function used by LogitBoost(Friedman et al., 2000), is
Llogit (y, h1 (x), ..., hk (x))
kX
1 + exp(hz (x))
log=
1z6=y + 1z=y × exp(hz (x))
z=1
= −hy (x) +kXlog (1 + exp(hz (x))) .

z=1

Minimizing this loss function has been shown to beconsistent (Zhang, 2004); informally, this means thatminimizing this loss function results in a classifier
whose accuracy is close to that of the Bayes optimalclassifier.1 (We give a precise definition of consistency
in Section 2.2.) Such consistency has been cited as ahallmark of a principled algorithm (Harchaoui et al.,2012).
Another loss function, due to Crammer & Singer(2001), is
LCS (y, h1 (x), ..., hk (x))
= max 0, 1 − hy (x) + max hz (x) .
z6=y1

Other papers on consistency for multiclass classification include (Lee et al., 2004; Tewari & Bartlett, 2007; Liu,
2007).

Consistency vs. Realizable H-Consistency

If all other scores hz (x) are at least 1 less than hy (x)then this loss is 0; otherwise this loss is the maximum,over all other scores, of the amount by which that scorefails to satisfy this constraint. LCS is not consistent(Tewari & Bartlett, 2007).
A puzzling empirical finding. Consider the following, apparently easy, synthetic learning problem.
Training and test examples are generated i.i.d. The
source used to generate examples is linearly separable:
there is a “target weight vector” wz ∈ R100 for eachclass z ∈ {1, . . . , 10}, and a random example (x, y)
is obtained by generating x ∈ R100 according to theuniform distribution on the unit ball, and assigninga label y that maximizes wy · x. The target weightvectors are the rows of a 10 × 100 matrix W that is
generated as follows: a 10 × 2 matrix A and a 2 × 100
matrix B are generated by i.i.d. sampling their components from the standard normal distribution, and W
is set to equal AB.
We generated 10000 training and 10000 test examples from such a source, and used them to evaluate
two algorithms. One algorithm learned the weights
v1 , ..., vk to minimize Llogit (y, v1 · x, ..., vk · x) using
100 epochs of ASGD (Polyak & Juditsky, 1992; Xu,
2011; Bottou, 2010) and the other was the same, except with LCS . (Both algorithms also used a mild
Frobenius norm regularizer. Please see Section 5 forthe details.) We repeated this process five times. The
algorithm that minimized (the consistent) Llogit had
average test accuracy 87.5%, while the algorithm thatminimized (the inconsistent) LCS had average test accuracy 94.4%. For one source, the accuracy obtained
from Llogit was 82.6%, while the accuracy from LCS
was 94.2%. Thus, in these experiments on a seemingly
easy synthetic learning problem, the consistent algorithm (minimizing Llogit ) performs significantly lesswell than the algorithm (minimizing LCS ) which is
known not to be consistent. Given how easy this learning problem seems to be, the outputs of the algorithm
minimizing Llogit are surprisingly inaccurate.
Discussion of the experimental results. What
happened? Because W has low rank, a given weightvector wy tends to be similar to weight vectors forsome other classes, and consequently a good classifier for a given example (x, y) will tend to also assign
high scores to some classes other than y. Minimizing LCS is compatible with this desideratum. During
training with a stochastic gradient descent algorithm,
once the weight vectors have sufficiently large magnitude, informally, LCS does not mind classes other thany also having a high score, and a stochastic gradient
update according to this loss function eventually will

not change any weights. On the other hand, if Llogit
is trained by stochastic gradient descent, it will keep
“knocking down” the scores for classes other than y.
Put another way, LCS is only trying to classify thedata correctly by a certain margin, while Llogit is trying to fit a model for the conditional probability thatthe class is y. The consistency of Llogit implies thatminimizing this loss will lead to near-optimal accuracy
if this minimization is done over the space of all scoring functions. However, in the above experiment, we
performed the minimization only over the class of linear functions. (We note that this is a standard practicefor large-scale multiclass image classification, see e.g.
(Weston et al., 2010; Lin et al., 2011; Perronnin et al.,2012)). This provides a possible explanation of Llogit ’s
relatively poor performance.
Our results. As described above, in our experiments,using LCS led to significantly better accuracy than
Llogit even though Llogit is consistent and LCS is not.
To explain this phenomenon we introduce a new notion, which we term realizable H-consistency, where H
is a restricted class of scoring functions. Informally, aloss function is realizable H-consistent if for any sourcethat admits a zero-error classifier using scoring functions from H, any scoring functions from H which
minimize the expected loss will have classification error close to zero. For learning algorithms that use a
restricted class H of scoring functions, H-consistency
may be more relevant than the original notion of consistency, which deals with all possible scoring functions, and realizable H-consistency is a more basic requirement.
We show that the loss function LCS is realizable Hconsistent for any class H of scoring functions thatis closed under scaling (i.e. if h ∈ H then αh ∈ H
for all real α). This implies that LCS is realizably
consistent with respect to linear scoring functions (aswell as with respect to deep nets, see the discussion
after Theorem 9). We also show that Llogit is notrealizably consistent with respect to the set of linear
functions. These results together imply that the ratio
between the error probabilities of an algorithm minimizing Llogit and an algorithm minimizing LCS canbe arbitrarily large, even if we restrict to linearly separable sources. Our lower bound for Llogit holds forany loss function satisfying some general conditions,and applies for several other loss functions previously
proposed for multiclass classification.
Our results suggest that the refined notion of Hconsistency may sometimes be a more useful and relevant one than the original notion of consistency. In settings where learning algorithms use a restricted classConsistency vs. Realizable H-Consistency

H of scoring functions, H-consistency may be moreclosely linked to classification accuracy than generalconsistency.

2. Preliminaries
2.1. Basics
Throughout this paper Y denotes the set [k] ={1, . . . , k}. A source is a joint distribution P over
X × Y . We write PX to denote the marginal distribution of P over X.
Recall that the Bayes optimal classifier for source P
is the mapping f : X → Y such that for each x′ in the
support of PX , we have Pr(x,y)∼P [y = f (x′ )|x = x′ ] ≥Pr(x,y)∼P [y = t|x = x′ ] for every t 6= f (x′ ).

there is a δ > 0 such that if h = (h1 , ..., hk ) δminimizes E(x,y)∼P [L(y, h1 (x), ..., hk (x))], and g satisfies g(x) ∈ argmaxŷ∈Y hŷ (x) for all x ∈ X, thenPr(x,y)∼P (g(x) 6= y) ≤ ǫ.
We now define a notion of consistency with respect to a
set H of scoring functions. This formalizes the notionthat choosing scoring functions from H so as to minimize the loss does nearly as well, in terms of classification error, as the best combination of scoring functions
from H. (Very similar notions have long been studied; see (Vapnik, 1989; Haussler, 1992; Kearns et al.,1992).)

2.2. Different notions of consistency

Let H be a set of functions mapping X to R. For
δ > 0, we say that a function h = (h1 , . . . , hk ) fromX to Rk δ-minimizes E(x,y)∼P [L(y, h1 (x), . . . , hk (x))]
with respect to H if

We begin by recalling the standard notion of consistency.

|E(x,y)∼P [L(y, h1 (x), . . . , hk (x))]

For δ > 0 and a source P , we say that a function h = (h1 , . . . , hk ) from X to Rk δ-minimizes
E(x,y)∼P [L(y, h1 (x), . . . , hk (x))] if|E(x,y)∼P [L(y, h1 (x), . . . , hk (x))] −inf

a1 ,...,ak :X→R

E(x,y)∼P [L(y, a1 (x), . . . , ak (x))]| ≤ δ.

Note that the scoring functions a1 , . . . , ak above may
range over all measurable mappings from X to R.
Definition 1. A loss function L is consistent if forany source P and any ǫ > 0 there exists someδ > 0 such that if h = (h1 , ..., hk ) δ-minimizes
E(x,y)∼P [L(y, h1 (x), ..., hk (x))], and g : X → Y satisfies g(x) ∈ argmaxŷ∈Y hŷ (x) for all x ∈ X, thenPr(x,y)∼P [g(x) 6= y] ≤ Pr(x,y)∼P [f (x) 6= y] + ǫ,
where f is the Bayes optimal classifier.
The notion of a consistent loss function definedin Definition 1 was studied by (Zhang, 2004). A
closely related notion was studied by Tewari and
Bartlett (Tewari & Bartlett, 2007). Following thoseauthors (and, others, including (Breiman, 2004;
Long & Servedio, 2010)), we abstract away estimation
error, and study the consequences of minimizing loss
with respect to the underlying distribution.
Definition 2. A source P is realizable if for eachx′ in the support of PX , there is a y ′ such thatPr(x,y)∼P [y = y ′ |x = x′ ] = 1.
Definition 3. A loss function L is realizable consistent if for any realizable source P , for any ǫ > 0−

inf

a1 ,...,ak ∈HE(x,y)∼P [L(y, a1 (x), . . . , ak (x))]| ≤ δ.

Definition 4. Let H be a set of measurable functions from X to R. A loss function L is H-consistent
if for any source P and any ǫ > 0, there is a
δ > 0 such that if h1 , . . . , hk ∈ H δ-minimize
E(x,y)∼P [L(y, h1 (x), ..., hk (x))] with respect to H andg : X → Y satisfies g(x) ∈ argmaxŷ∈Y hŷ (x) for
all x ∈ X, then for all, a1 , . . . , ak ∈ H, and any
f : X → Y such that f (x) ∈ argmaxŷ∈Y aŷ (x) for
all x ∈ X, we havePr(x,y)∼P [g(x) 6= y] ≤ Pr(x,y)∼P [f (x) 6= y] + ǫ.
Note that the original notion of consistency from Definition 1 corresponds to H-consistency when H is theclass of all measurable functions.
Definition 5. A source P is realizable w.r.t. H if
there exist h1 , . . . , hk ∈ H such that, for any g : X →[k] such that g(x) ∈ argmaxŷ∈Y hŷ (x) for all x ∈ X,
we have that Pr(x,y)∼P [y = g(x′ )|x = x′ ] = 1 for any
x′ in the support of PX .
Realizable sources correspond to learning scenarios inwhich there is a “target function” that always provides
the correct label for each example.
Definition 6. A loss function L is realizable Hconsistent if the following holds: for any source P
that is realizable w.r.t. H and any ǫ > 0, there
is a δ > 0 such that if h1 , . . . , hk ∈ H δ-minimize
E(x,y)∼P [L(y, h1 (x), . . . , hk (x))] with respect to H, andg satisfies g(x) ∈ argmaxŷ hŷ (x) for all x ∈ X, thenPr(x,y)∼P [g(x) 6= y] ≤ ǫ.

Consistency vs. Realizable H-Consistency

3. The Crammer-Singer loss

But E(x,y)∼P [LCS (y, g1 (x), ..., gk (x))] is an upperbound on the probability (over (x, y) ∼ P ) that y 6=
argmaxŷ gŷ (x). This completes the proof.

The Crammer-Singer loss is defined as follows:
LCS (y, s1 , ..., sk ) = max 0, 1 − sy + max sj .

Note that the proof of Theorem 9 goes through almost
without modification if LCS is replaced with

j6=y

One may easily use a construction due to Tewari and
Bartlett (Tewari & Bartlett, 2007) to prove that LCS
is not consistent (see also (Zhang, 2004)). Because ofdifferences in the details of our definitions and theirs,
we have included a proof of Theorem 7 in Appendix A.
Theorem 7. LCS is not consistent.
While LCS is not consistent, we now show that it isrealizable H-consistent for any class H of scoring functions that satisfies the following natural scaling condition:
Definition 8. A class H of scoring functions is closed
under scaling if for any h ∈ H and any real α, thefunction αh belongs to H.
The set of linear functions is closed under scaling, andany set of scoring functions can be easily closed underscaling by adding all scalings of all of its members.
Theorem 9. For any H that is closed under scaling,
the Crammer-Singer loss LCS is realizable consistentw.r.t. H.
Proof: Let P be a realizable source w.r.t. H. Let
h1 , ..., hk ∈ H be such that, if gap(x) = hy (x) −maxj6=y hj (x), where y = argmaxŷ∈Y hŷ (x), we havePr(x,y)∼P [gap(x) > 0] = 1.

(1)

Choose ǫ > 0, and let κ > 0 be such that
Prx∼PX [gap(x) ≤ κ] ≤ ǫ/2. Then, rescaling h1 , ..., hk
by 1/κ, we claim thatE(x,y)∼P [LCS (y, (1/κ)h1 (x), ..., (1/κ)hk (x))] ≤ ǫ/2.
To see this, note that since hy (x) > hj (x) for all x andall j 6= y, we have that LCS is always at most 1, andhence

L(y, s1 , ..., sk ) = ℓ(−sy + max sj ),j6=yfor any continuous monotone function ℓ : R → R+such that limx→−∞ ℓ(x) = 0, including the functionℓ defined by ℓ(x) = ln(1 + ex ). The key is that theseloss functions concern a competition among the scores,
instead of evaluating the scores independently.
We also note that beyond the class H of linear functions, Theorem 9 also implies that LCS is realizable
H-consistent in the case that H is the set of functions
computed by a deep network with a given architecture,or a convolutional network, if the squashing functions
are left off of the output nodes. (The loss function
can be viewed as taking on the role of the squashing
function for the output nodes, so this is reasonable.)

4. A sufficient condition for a loss
function to not be realizable
consistent w.r.t. linear functions
Throughout this section we fix X to be the domain Rn
and we let H denote the class of all linear functions
X → R, i.e. H = {x → v · x, v ∈ Rn }.
Our main result in this section is a proof that any
loss function that satisfies some general conditions, detailed below, is not realizable consistent for the classof linear scoring functions:
Theorem 10. Let ℓ : R → R>0 = {x ∈ R :x > 0} be any function such that (a) ℓ is twice continuously differentiable, (b) ℓ is strictly convex, (c)limx→+∞ ℓ(x) = +∞, and (d) inf x∈R ℓ(x) − x > −∞.
Then the loss function Lℓ defined as
Lℓ (y, h1 (x), . . . , hk (x)) := −hy (x) +kXℓ(hz (x))

z=1

is not realizable H-consistent, where H is the class of
all linear functions.

E[LCS (y, (1/κ)h1 (x), ..., (1/κ)hk (x))]≤ E[LCS (y, (1/κ)h1 (x), ..., (1/κ)hk (x))|gap(x) > κ] It can be easily checked that this theorem implies thatmany of the “decoupled” loss functions of (Zhang,+Pr[gap(x) ≤ κ] ≤ 0 + ǫ/2.
(2) 2004) (see Section 4.4.2 of (Zhang, 2004)), shown
there to be consistent, are in fact not realizable Hconsistent. These include the Llogit function (for which
Now suppose that g1 , ..., gk ∈ H approximately minℓ(x) = ln(1 + ex )) and the LQ loss function defined byimize E(x,y)∼P [LCS (y, g1 (x), ..., gk (x))] to within ǫ/2.
Then (2) implies thatk1X
hz (x)2
LQ (y, h1 (x), . . . , hk (x)) = −hy (x) +2 z=1E(x,y)∼P [LCS (y, g1 (x), ..., gk (x))] ≤ ǫ.

Consistency vs. Realizable H-Consistency(for which ℓ(x) = x2 /2). (Our proof will establish
lower bounds of 1/5 on the error probability for algorithms minimizing Llogit and LQ .)The main steps in proving Theorem 10 are to (I) define a source P that is realizable w.r.t. H, and (II)prove that the optimal (v1⋆ , . . . , vk⋆ ) ∈ H k that minimizes E(x,y)∼P [Lℓ (y, v1⋆ · x, . . . , vk⋆ · x)] (over all ktuples of functions in H as the final k arguments toLℓ ) is such that for g(x) = argmaxŷ∈Y hŷ (x), we havePr(x,y)∼P [g(x) 6= y] is bounded below by 4α where
α > 0 is a constant that depends only on ℓ (defined
below). Once this is done Theorem 10 is an immediate
consequence (taking ǫ = 4α in Definition 6). We now
turn to these two tasks.
(I): The source P . We now define the source P
over X × Y that we shall consider. This source is very
simple and in fact only uses the domain X = R2 . The
number k of classes is 8. The source depends on theloss ℓ through a parameter that is defined as follows.
Since ℓ is twice continuously differentiable and strictly
convex, there is a τ > 0 such that√ℓ′′ (x) √≤ 2.
∀x ∈ [−τ, τ ], (1/ 2) ≤ ′′
ℓ (0)

(3)

Choose such a τ . (For LQ , any positive constant will
work, and for Llogit , we may choose τ = 1.) Let α =min{τ ℓ′′ (0)/5, 1/20}. (For both LQ and Llogit , α is1/20.) Next, define the k × 2 matrix W whose rows
are w1 , . . . , wk : for i = 1, . . . , k,
wi = (wi,1 , wi,2 ) = (cos(2πi/k), sin(2πi/k)).

(4)

The marginal PX is defined as follows. Each of
w1 , w3 , w5 , w7 have probability α (these are the “lightpoints”), and each of w2 , w4 , w6 , w8 have probability
1/4 − α (these are the “heavy points”). The weightmatrix W whose rows are w1 , ..., w8 is then used toclassify x as y = argmaxz wz · x, so P is realizablewith respect to H.
(II): The vector of functions in H that minimizes Lℓ has poor classification accuracy. Henceforth V shall denote a k × 2 matrix whose rows are
v1 , . . . , vk . Let us define the function Ψ as follows:

we get that Ψ(V ) equals
4
X
s=1

+

(1/4 − α) − v2s · w2s +

4
X
s=1

α − v2s−1 · w2s−1 +

8
X
z=1

8
X
z=1

ℓ(vz · w2s )ℓ(vz · w2s−1 ) .

Since• Ψ is convex,• ℓ is strictly convex (by property (b) of the theorem
statement), and• modifying any entry of V affects ℓ(vz · wj ) for atleast one z and j,
we have that Ψ is strictly convex.
Now, let us eliminate the possibility that the value ofΨ can get arbirarily small. First, because ℓ(t) > 0 for
all t, for any example (x, y) we have−vy ·x+kX
z=1ℓ(vz ·x) ≥ −vy ·x+ℓ(vy ·x) ≥ inf ℓ(u)−u.
u∈R

Since inf x∈R ℓ(x) − x > −∞ (by property (d) of thetheorem statement), and Ψ is an average of such losses,
the function Ψ is lower bounded (there is some value
C ∈ R such that Ψ(V ) > C for all V ).
Next, let us eliminate the possibility that Ψ has nominimum; since Ψ is strongly convex, this can only
occur if the value of Ψ gets smaller and smaller as V
heads to infinity in some direction. We claim that any
V with a very large entry must have Ψ(V ) > Ψ(Vzero )where Vzero is the all-zero input. To see this, suppose|Vzi | > M for some row z and column i. Choose somey ∈ {1, .., 8} other than z such that the angle between
vz and wy is at most π/4. (There must be at least
one such y.) Then√
Ψ(V ) ≥ αℓ(vz ·wy ) ≥ αℓ(||vz || cos(π/4)) ≥ αℓ(M/ 2),

We want to show that Ψ has a unique minimum. As astep in this direction, let us first show that Ψ is strictly
convex.

which is larger than Ψ(Vzero ) for M sufficiently large,
by our assumption that ℓ goes to +∞ as M → +∞(by property (c) of the theorem statement). So forthe purpose of minimizing Ψ, we can assume without
loss of generality that the domain of Ψ is [−M, M ]8×2
for some constant M > 0. Since Ψ is a strictly convex function defined on a bounded domain, there is aunique V ⋆ at which it achieves its minimum value.

Directly expanding the definition of P , separating the
expectation into the heavy points and the light points,

In the rest of the proof we will show that the error rateof V ⋆ w.r.t. P is at least 4α. To prove this, first let us

Definition 11. Ψ(V ) = E(x,y)∼P [Lℓ (y, v1 · x, . . . , vk ·x)].

Consistency vs. Realizable H-Consistency

characterize the form of V ⋆ . We claim that there arereal values q and r such thatT
r 0 −r −q −r 0
r
q
⋆
. (5)
V =
r q r
0
−r −q −r 0⋆First, let us prove that V2,1
= 0.

⋆
Suppose V2,1
6= 0.
′

Then the symmetry of Ψ implies that, if we form V⋆by negating V2,1
in V ⋆ , then V ′ 6= V ⋆ but Ψ(V ′ ) =⋆Ψ(V ). Since this contradicts the uniqueness of the⋆minimizing point V ⋆ , it must be the case that V2,1=
0. The other 0-entries in (5) can be established in asimilar way.
We can prove that⋆⋆
V4,1
= −V8,1,⋆⋆V5,1= −V7,1,⋆⋆
V3,1= −V1,1,⋆⋆
V3,2= V1,2,⋆⋆V5,2= V7,2similarly by exploiting the symmetry of Ψ across thex2 axis, and we can prove that⋆⋆
V1,1
= V1,2,⋆⋆
V3,2 = V7,1 ,

⋆
⋆
V2,2
= V8,1,⋆⋆
V4,1 = V6,2 ,= 0, we get
Setting ∂v∂Ψ
1,1 V ⋆√√√
α/ 2 = (α/ 2)t( 2r) + (1/4 − α)t(r).
It is clear that t(0) = 0. Furthermore,t′ (u) = ℓ′′ (u) − ℓ′′ (−u)(−1) = ℓ′′ (u) + ℓ′′ (−u) > 0,
since ℓ is strictly convex. Thus t is increasing on all of
R. Hence by (6) we have that r must be positive, andmoreover that
√
5α
α/ 2
(7)
≤√ .
t(r) ≤
1/4 − α2
Now we consider a different partial derivative,∂ΨCalculating ∂v∂Ψby evaluating∂v8,1 V ⋆ .
8,1 V ⋆∂L(z,v1 ·wz ,...,vk ·wz )
∂v8,1

√
√
αℓ′ (q/ 2)(1/ 2)+0√√+αℓ′ (q/ 2)(1/ 2)

similarly by exploiting the symmetry across the line
x1 = x2 .

+(1/4 − α)ℓ′ (−q)(−1)√√+αℓ′ (−q/ 2)(−1/ 2)+0√√+αℓ′ (−q/ 2)(−1/ 2)+(1/4 − α)(−1 + ℓ′ (q)(1))= 0, we haveso setting ∂v∂Ψ8,1 V ⋆

So, if q/r > 2, then V ⋆ misclassifies w1 , and, similarly,
all the other light points.
We now proceed to show that q > 2r. Our analysis
will make use of the function t : R → R defined byt(x) = ℓ′ (x) − ℓ′ (−x).
z ,...,vk ·wz )by evaluating ∂L(z,v1 ·w
Calculating ∂v∂Ψ∂v1,1
1,1 V ⋆
for z = 1, ..., 8 in order, one per line, we get√√√α(−1/ 2 + ℓ′ (2r/ 2)(1/ 2))+0√+αℓ′ (0)(−1/ 2)+(1/4 − α)ℓ′ (−r)(−1)√√+αℓ′ (−2r/ 2)(−1/ 2)+0√+αℓ′ (0)(1/ 2)+(1/4 − α)ℓ′ (r).
This simplifies to√√√−α/ 2 + (α/ 2)t( 2r) + (1/4 − α)t(r).

for z = 1, ..., 8 in order, one perline, we get

⋆
⋆
V3,1
= V7,2,⋆⋆
V5,1 = V5,2

Below we will show that q > 2r; we claim that this
implies Pr(x,y)∼P [g(x) 6= y] ≥ 4α as desired. To see
this, consider first the classification of w1 . We have√√√v1⋆ · w1 = (r, r) · (1/ 2, 1/ 2) = 2r√√√v2⋆ · w1 = (0, q) · (1/ 2, 1/ 2) = q/ 2.

(6)(1/4 − α)t(q) +√√2αt(q/ 2) = 1/4 − α.

(8)Note that from the above equation it is clear that q
must be positive (recall that t(0) = 0 and t is increasing). Also, since t is increasing (8) impliest(q) ≥

1/4 − α√ .
1/4 − α + 2α

(9)We want to combine this constraint with (7) to provethat q > 2r.
√
Toward this end, we claim that t(r) ≤ 5α/ 2, which
we have from (7), implies that r ≤ τ /2. (Recall that τ
was defined back at (3).) To see this, first assume forcontradiction that r > τ /2. Then,t(r) =Z r−r≥

Z τ /2−τ /2′′ℓ (u) du >Z τ /2ℓ′′ (u) du

−τ /2

√
√
√
ℓ′′ (0)/ 2 du = τ ℓ′′ (0)/ 2 ≥ 5α/ 2,

Consistency vs. Realizable H-Consistency

since α ≤ τ ℓ′′ (0)/5. Since this is a contradiction, we
have r ≤ τ /2.

−2r

−2r

√
and, similarly t(r) ≥ 2rℓ′′ (0)/ 2, so thatt(2r) ≤ 4t(r)
≤4

√ !
α/ 2
1/4 − α1/4 − α√<1/4 − α + 2α
≤ t(q),

"cs1"
"cs2"
"cs3"
"cs4"
"cs5"
"logit1""logit2""logit3""logit4""logit5""quad1""quad2""quad3""quad4""quad5"0.95

0.9

Test set accuracy

Since r ≤ τ /2, we have
Z 2r √
Z 2r√2ℓ′′ (0) du = 4 2rℓ′′ (0),ℓ′′ (u) du ≤t(2r) =

1

0.85

0.8

0.75

0.7

0.65

(by (7))
0.6
0

20

40

60

80

100

Number of epochs(since α ≤ 1/20)

by (9). Since t is increasing, this implies q > 2r. Thisconcludes the proof of Theorem 10.

Figure 1. Comparison between the learning curves of classifiers trained using ASGD with different loss functions,
run on data labeled with five different randomly generated
target functions.

5. Experiments

6. Conclusion

Experiments used a source P generated as follows.
The domain X was Rd for d = 100. The number k ofclasses was 10. Class labels were assigned by applying a “target classifier” generated as follows. A weightmatrix W ∈ R10×100 was generated by randomly generating a 10 × 2 matrix A and a 2 × 100 matrix B, andsetting W = AB. The components of A and B were
sampled i.i.d. from the standard normal distribution.
If we refer to the rows of W as w1 , ..., wk as before,
then the class y assigned to x was chosen to maximize wy · x. Elements of X were chosen uniformly at
random from the surface of the unit ball.

In this work we proposed the new notion of realizable
H-consistency, which is a variant of the standard notion of consistency for loss functions. Our experimental and theoretical results indicate that for multiclasslearning algorithms that work by minimizing a loss
function over a restricted class H of scoring functions,realizable H-consistency may sometimes be more useful than consistency as a guide to classification performance.

We did experiments with three different loss functions:
LCS , Llogit and LQ (Zhang, 2004). For each loss function L in this list, we experimented with the algorithm that, given (x1 , y1 ), ..., (xm , ym ), chooses V andb1 , ..., bk to minimizem
1 X
λ||V ||2F +L(yt , v1 · xt + b1 , ..., vk · xt + bk ),2
m t=1

where || · ||F is the Frobenius norm, and λ = 10−6 .
The minimization was done using Averaged Stochastic
Gradient Descent (Polyak & Juditsky, 1992;
p Xu, 2011;
Bottou, 2010) (ASGD) with a step size of 1/t on thetth update.
In our experiments, we used 10000 training examples
and 10000 test examples. We ran each algorithm for
100 epochs. At the end of each epoch we evaluatedthe accuracy of the algorithm on the test data. We
repeated this process, including the random generationof the target weight matrix W , five times. Results areplotted in Figure 1.

Consideration of realizable H-consistency highlights
circumstances where loss functions like LCS , which
involve a competition among the scores for different
classes, may be preferred to generalizations of one-vsrest, such as Llogit . As discussed after the proof of
Theorem 9, LCS is realizable H-consistent because it
incorporates such a competition, and not, for example,
because it generalizes the hinge loss. (The hinge loss
was shown to be optimally noise-tolerant for binaryclassification, in a certain sense, in (Ben-David et al.,2012).)
In future work it would be interesting to extend ouranalyses to a non-realizable setting.

Acknowledgements
We thank Shenghuo Zhu, Anelia Angelova and Yuanqing Lin for valuable conversations.

A. Proof of Theorem 7
We will analyze the following source P . The domain
consists of a single element x and the number k ofConsistency vs. Realizable H-Consistencyclasses is 3.
P (x, 1) = 3/7, P (x, 2) = 2/7, P (x, 3) = 2/7.
We first characterize the optimal value of P with respect to LCS .
Lemma 12. E(x,y)∼P [LCS (y, h1 (x), h2 (x), h3 (x)] is
minimized by setting h1 (x) = h2 (x) = h3 (x) = 1,
where it takes the value 1.
Before proving Lemma 12, we point out the following sanity check: one can easily verify that perturbing
the solution h1 (x) = h2 (x) = h3 (x) = 1 by adding
or subtracting a small positive constant to any of thevariables while keeping the others constant makes thesolution worse.
Now we proceed with the detailed proof.
Proof (of Lemma 12): For possible values u1 , u2 , u3 ofdef

h1 (x), h2 (x), h3 (x), if [z]+ = max{z, 0}, the quantity
to be minimized isdefψ(u1 , u2 , u3 ) = (3/7)[1 − u1 + max{u2 , u3 }]++ (2/7)[1 − u2 + max{u1 , u3 }]++ (2/7)[1 − u3 + max{u1 , u2 }]+ .

Let us now check the KKT conditions.
First,
let’s check partial derivatives with respect toz1 , z2 , z3 , u1 , u2 , u3 respectively:
3/7 − λ∗1,2 − λ∗1,3 − λ∗1,+= 3/7 − 3/14 − 3/14 − 0 = 0

2/7 − λ∗2,1 − λ∗2,3 − λ∗2,+= 2/7 − 3/14 − 1/14 − 0 = 0

2/7 − λ∗3,1 − λ∗3,2 − λ∗2,+= 2/7 − 3/14 − 1/14 − 0 = 0−λ1,2 − λ1,3 + λ2,1 + λ3,1

= −3/14 − 3/14 + 3/14 + 3/14 = 0−λ2,1 − λ2,3 + λ1,2 + λ3,2

= −3/14 − 1/14 + 3/14 + 1/14 = 0−λ3,1 − λ3,2 + λ1,3 + λ2,3= −3/14 − 1/14 + 3/14 + 1/14 = 0.

All of the inequalities relating z1 , z2 , z3 to u1 , u2 , u3
are binding at z1∗ , z2∗ , z3∗ , u∗1 , u∗2 , u∗3 , so the complementary slackness conditions are satisfied for those constraints; since λ∗i,+ = 0 for all i, the complementaryslackness constraints are satisfied for those constraints
also. This completes the proof.
Armed with Lemma 12, we are ready for the following.

The minimimum of ψ can be equivalently representedasmin(3z1 + 2z2 + 2z3 )/7s.t.
z1 ≥ 1 − u 1 + u 2 , z1 ≥ 1 − u 1 + u 3 , z1 ≥ 0
z2 ≥ 1 − u 2 + u 1 , z2 ≥ 1 − u 2 + u 3 , z2 ≥ 0
z3 ≥ 1 − u3 + u1 , z3 ≥ 1 − u3 + u2 , z3 ≥ 0.
A Lagrange multiplier formulation isL=(3z1 + 2z2 + 2z3 )/7+λ1,2 (1 − u1 + u2 − z1 )+λ1,3 (1 − u1 + u3 − z1 ) + λ1,+ (−z1 )+λ2,1 (1 − u2 + u1 − z2 )+λ2,3 (1 − u2 + u3 − z2 ) + λ2,+ (−z2 )+λ3,1 (1 − u3 + u1 − z3 )+λ3,2 (1 − u3 + u2 − z3 ) + λ3,+ (−z3 ).

We claim that the following solution is optimal:u∗1 = u∗2 = u∗3 = 1
z1∗ = z2∗ = z3∗ = 1
λ∗1,+ = λ∗2,+ = λ∗3,+ = 0
λ∗1,2 = λ∗1,3 = λ∗2,1 = λ∗3,1 = 3/14
λ∗2,3 = λ∗3,2 = 1/14.

Proof (of Theorem 7):
Choose δ > 0, and consider g1 , ..., g3 for which g1 (x) =g2 (x) = 1 and g3 (x) = 1 + δ/2. We haveE(x,y)∼P [LCS (y, h1 (x), h2 (x), h3 (x))]= (3/7)[1 − 1 + max{1, 1 + δ/2}]++(2/7)[1 − 1 + max{1, 1 + δ/2}]++(2/7)[1 − (1 + δ/2) + max{1, 1}]+

< 1 + δ.

But, if q(x) = argmaxŷ∈Y gŷ (x), no matter how smallδ is, we have q(x) = 3, so, for the Bayes optimal f , wehavePr(x,y)∼P [q(x) 6= y] = Pr(x,y)∼P [f (x) 6= y] + 1/7,
completing the proof.

References
Ben-David, S., Loker, D., Srebro, N., and Sridharan,
K. Minimizing the misclassification error rate using
a surrogate convex loss. In ICML, 2012.
Bottou, L. Large-scale machine learning with stochastic gradient descent. In Proceedings of the 19th International Conference on Computational Statistics(COMPSTAT’2010), pp. 177–187, 2010.

Consistency vs. Realizable H-Consistency

Breiman, L. Some infinity theory for predictor ensembles. Annals of Statistics, 32(1):1–11, 2004.

1989 Workshop on Computational Learning Theory,
1989.

Crammer, K. and Singer, Y. On the algorithmic implementation of multiclass kernel-based vector machines. JMLR, 2:265–292, 2001.

Weston, J., Bengio, S., and Usunier, N. Large scale
image annotation: learning to rank with joint wordimage embeddings. Machine Learning, 81(1):21–35,
2010.

Friedman, J., Hastie, T., and Tibshirani, R. Additive
logistic regression: A statistical view of boosting.
The Annals of Statistics, 38(2):337–407, 2000.
Harchaoui, Zaı̈d, Douze, Matthijs, Paulin, Mattis,
Dudı́k, Miroslav, and Malick, Jérôme. Large-scale
image classification with trace-norm regularization.
In CVPR, pp. 3386–3393, 2012.
Haussler, D. Decision theoretic generalizations of the
PAC model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992.
Kearns, M. J., Schapire, R. E., and Sellie, L. M. Toward efficient agnostic learning. Proceedings of the
1992 Workshop on Computational Learning Theory,
pp. 341–352, 1992.
Lee, Y., Lin, Y., and Wahba, G. Multicategory support vector machines: Theory and application to theclassification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67–81, 2004.
Lin, Y., Lv, F., Zhu, S., Yang, M., Cour, T., Yu, K.,
Cao, L., and Huang, T. Large-scale image classification: fast feature extraction and SVM training. In
CVPR, pp. 1689 – 1696, 2011.
Liu, Y. Fisher consistency of multicategory support
vector machines. In UAI, pp. 291–298, 2007.
Long, P. M. and Servedio, R. A. Random classificationnoise defeats all convex potential boosters. Machine
Learning, 78(3):287–304, 2010.
Perronnin, F., Akata, Z., Harchaoui, Z., and Schmid,
C. Towards good practice in large-scale learning forimage classification. CVPR, pp. 3482–3489, 2012.
Polyak, B. T. and Juditsky, A. B. Acceleration ofstochastic approximation by averaging. SIAM J.
Control Optim., 30(4):838–855, 1992.
Tewari, A. and Bartlett, P. L. On the consistency ofmulticlass classification methods. JMLR, 8:1007–
1025, 2007.
Vapnik, V. N. Inductive principles of the search for
empirical dependences (methods based on weak convergence of probability measures). Proceedings of theXu, W. Towards optimal one pass large scale learningwith averaged stochastic gradient descent. Arxiv,
2011.
Zhang, T. Statistical analysis of some multi-category
large margin classification methods. Journal of Machine Learning Research, 5:1225–1251, 2004.