Confidence sets with expected sizes for
Multiclass Classification
Christophe Denis∗ and Mohamed Hebiri†

arXiv:1608.08783v2 [] 18 Dec 2017

LAMA, UMR-CNRS 8050,
Université Paris Est – Marne-la-Vallée

Abstract
Multiclass classification problems such as image annotation can involve a large number
of classes. In this context, confusion between classes can occur, and single label classification
may be misleading. We provide in the present paper a general device that, given an unlabeled
dataset and a score function defined as the minimizer of some empirical and convex risk,
outputs a set of class labels, instead of a single one. Interestingly, this procedure does not
require that the unlabeled dataset explores the whole classes. Even more, the method is
calibrated to control the expected size of the output set while minimizing the classification
risk. We show the statistical optimality of the procedure and establish rates of convergence
under the Tsybakov margin condition. It turns out that these rates are linear on the number
of labels. We apply our methodology to convex aggregation of confidence sets based on the
V -fold cross validation principle also known as the superlearning principle [vdLPH07]. We
illustrate the numerical performance of the procedure on real data and demonstrate in
particular that with moderate expected size, w.r.t. the number of labels, the procedure
provides significant improvement of the classification risk.
Keywords : Multiclass classification, confidence sets, empirical risk minimization,
cumulative distribution functions, convex loss, superlearning.

1

Introduction

The advent of high-throughput technology has generated tremendous amounts of large and highdimensional classification data. This allows classification at unprecedented scales with hundreds
or even more classes. The standard approach to classification in the multiclass setting is to use
a classification rule for assigning a single label. More specifically, it consists in assigning a single
label Y ∈ Y, with Y = {1, . . . , K}, to a given input example X ∈ X among a collection of labels.
However, while a large number of classes can lead to precise characterizations of data points,
similarities among classes also bear the risk of confusion and misclassification. Hence, assigning
a single label can lead to wrong or ambiguous results.
In this paper, we address this problem by introducing an approach that yields sets of labels
as outputs, namely, confidence sets. A confidence set Γ is a function that maps X onto 2Y .
A natural way to obtain a set of labels is to use ranked outputs of the classification rule. For
example, one could take the classes that correspond to the top-level conditional probabilities
P(Y = ·|X = x). Here, we provide a more general approach where we control the expected size of
∗ Christophe.Denis@u-pem.fr
† Mohamed.Hebiri@u-pem.fr

1

the confidence sets. For a confidence set Γ, the expected size of Γ is defined as E[|Γ(X)|], where
| · | stands for the cardinality. For a sample X and given an expected set size β, we provide an
algorithm that outputs a set Γ̂(X) such that E[|Γ̂(X)|] ≈ β. Furthermore, the procedure aims
at minimizing the classification error given by


P Y ∈
/ Γ̂(X) ≈
min
P (Y ∈
/ Γ(X)) = R∗β .
Γ : E[|Γ(X)|]=β

We establish a close formula of the oracle confidence set Γ∗ = argminΓ : E[|Γ(X)|]=β P (Y ∈
/ Γ(X))
that involves the cumulative distribution functions of the conditional probabilities. Besides,
we formulate a data-driven counterpart of Γ∗ based on the minimization of the empirical risk.
However, the natural risk function in the multiclass setting is non convex, and then minimizing
it is proving to be a computational issue. As a remedy, convex surrogates are often used in
machine learning, and more specifically in classification as reflected by the popularity of methods
such as Boosting [FS97], logistic regression [FHT00] and support vector machine [Vap98]. In our
problem this translates by considering some convex surrogate of the 0/1-loss in P (Y ∈
/ Γ(X)); we
introduce a new convex risk function which enables us to emphasize specific aspects of confidence
sets. That convex risk function is partly inspired by the works in [Zha04, BJM06, YW10] that
deal with binary classification.
Our approach displays two main features. First, our method can be implemented in a semisupervised way [Vap98]. More precisely, the method is a two-steps procedure that requires the
estimation of score functions (as minimizers of some convex risk function) in a first step and
the estimation of the cumulative distribution of these scores in a second one. Hence, the first
step requires labeled data whereas the second one involves only unlabeled samples. Notably,
the unlabeled sample does not necessary consists of examples coming from the whole classes.
This aspects is fondamental when we deal with a large number of classes, some of which been
sparsely represented. Second, from the theoretical point of view, we provide an oracle inequality
satisfied by Γ̂, the empirical confidence set that results from the minimization of an empirical
convex risk. The obtained oracle inequality shall enable us to derive rates of convergence on a
particular class of confidence sets under the Tsybakov noise assumption on the data generating
distribution. These rates are linear in the number of classes K and also depend on the regularity
of the cumulative distribution functions of the conditional probabilities.
An obvious benefit of considering convex risk minimization is when we deal with aggregation. However, aggregating confidence sets is no simple matter. Another contribution of the
present paper is about applying the above methodology to aggregation of confidence sets. More
specifically, we provide a generalization of the superlearning algorithm [vdLPH07] initially introduced in the context of regression and binary classification. This algorithm relies on the V -fold
cross-validation principle. We prove the consistency of this aggregation procedure and illustrate
its relevance on real datasets. Let us point out that any arbitrary library of machine learning
algorithms may be used in this aggregation procedure; we propose in the present paper to exploit
support vector machines, random forest procedures or softmax regression since these methods
are popular in machine learning and that each of them is associated to a different shape.
We end up this discussion by highlighting in two words what we perceive as being the main
contributions of the present paper. We describe an optimal strategy for building confidence sets
in multiclass classification setting, and we derive a new aggregation procedure for confidence sets
that still allows controlling the expected size of the resulting confidence set.
Related works: The closest learning task to the present work is classification with reject option
which is a particular setting in binary classification. Several papers fall within the scope of this
area [Cho70, HW06, YW10, WY11, Lei14, DH15] and differ from each other by the goal they
2

consider. Among these references, our procedure is partially inspired by the paper [DH15] that
also considers a semi-supervised approach to build confidence sets invoking some cumulative
distribution functions (of the conditional probabilities themselves in their case). The similarity
is however limited to the definition of oracle confidence sets, the oracle confidence in the present
paper being an extension of the one defined in [DH15] to the multiclass setting. On the other
hand, all the data-driven considerations are completely different (in particular, [DH15] focuses on
plug-in rules) and importantly, we develop here new probabilistic results on sums of cumulative
distribution functions of random variables, that are of own interest.
Assigning a set of labels instead of a single one for an input example is not new [VGS05,
WLW04, dCDB09, LRW13, CCB16]. One of the most popular methods is based on Conformal
Prediction approach [VGS99, Vov02, VGS05]. In the multiclass classification framework, the goal
of this algorithm is to build the smallest set of labels such that its classification error is below a
pre-specified level. Since our procedure aims at minimizing the classification error while keeping
under control the size of the set, Conformal Prediction can be seen as a dual of our method. It is
worth mentioning that conformal predictors approaches need two labeled datasets where we only
need one labeled dataset, the second being unlabeled. We refer to the very interesting statistical
study of Conformal Predictors in the binary case in the paper [Lei14].
Notation: First, we state general notation. Let Y = {1, . . . , K}, with K ≥ 2 being an integer.
Let (X, Y ) be the generic data-structure taking its values in X × Y with distribution P. The goal
in classification is to predict the label Y given an observation of X. This is performed based on
a classifier (or classification rule) s which is a function mapping X onto Y. Let S be the set of
all classifiers. The misclassification risk R associated with s ∈ S is defined as
R(s) = P(s(X) 6= Y ).
Moreover, the minimizer of R over S is the Bayes classifier, denoted by s∗ , and is characterized
by
s∗ (·) = argmax pk (·),
k∈Y

where pk (x) = P(Y = k|X = x) for x ∈ X and k ∈ Y.
Let us now consider more specific notation related to the multiclass confidence set setting. Let
a confidence set be any measurable function that maps X onto 2Y . Let Γ be a confidence set.
This confidence set is characterized by two attributes. The first one is the risk associated to the
confidence set
R (Γ) = P (Y ∈
/ Γ(X)) ,
(1)
and is related to its accuracy. The second attribute is linked to the information given by the
confidence set. It is defined as
I(Γ) = E (|Γ(X)|) ,
(2)

where | · | stands for the cardinality. Moreover, for some β ∈ [1, K], we say that, for two
confidence sets Γ and Γ′ such that I (Γ) = I (Γ′ ) = β, the confidence set Γ is “better” than Γ′ if
R (Γ) ≤ R (Γ′ ).
Organization of the paper: The rest of the paper is organized as follows. Next section is devoted
to the definition and the main properties of the oracle confidence set for multiclass classification.
The empirical risk minimization procedure is provided in Section 3. Rates of convergence for the
confidence set that results from this minimization can also be found in this section. We present
an application of our procedure to aggregation of confidence sets in Section 4. We finally draw
some conclusions and present perspectives of our work in Section 5. Proofs of our results are
postponed to the Appendix.
3

2

Confidence set for multiclass classification

In the present section, we define a class of confidence sets that are suitable for multiclass classification and referred as Oracle β-sets. For some β ∈ (0, K), these sets are shown to be optimal
according to the risk (1) with an information (2) equal to β. Moreover, basic but fondamental
properties of Oracle β-sets can be found in Proposition 1, while Proposition 3 provides another
interpretation of these sets.

2.1

Notation and definition

First of all, we introduce in this section a class of confidence sets that specifies oracle confidence
sets. Let β ∈ (0, K) be a desired information level. The so-called Oracle β-sets are optimal
according to the risk (1) among all the confidence sets Γ such that I(Γ) = β. Throughout the
paper we make the following assumption
(A1) For all k ∈ {1, . . . , K}, the cumulative distribution function Fpk of pk (X) is continuous.
The definition of the Oracle β-set relies on the continuous and decreasing function G defined
for any t ∈ [0, 1] by
K
X
G(t) =
F̄pk (t),
k=1

where for any k ∈ {1, . . . , K}, we denote by F̄pk the tail distribution function of pk (X), that
is, F̄pk = 1 − Fpk with Fpk being the cumulative distribution function (c.d.f.) of pk (X). The
generalized inverse G−1 of G is given by (see [vdV98]):
G−1 (β) = inf{t ∈ [0, 1] : G(t) ≤ β}, ∀β ∈ (0, K).
The functions G and G−1 are central in the construction of the Oracle β-sets. We then provide
some of their useful properties in the following proposition.
Proposition 1. The following properties on G hold
i) For every t ∈ (0, 1) and β ∈ (0, K), G−1 (β) ≤ t ⇔ β ≥ G(t).
ii) For every β ∈ (0, K), G(G−1 (β)) = β.
iii) Let ε be a random variable, independent of X, and distributed from a uniform distribution
on {1, . . . , K} and let U be uniformly distributed on [0, K]. Define
Z=

K
X

k=1

pk (X)1{ε=k} .
L

L

If the function G is continuous, then G(Z) = U and G−1 (U ) = Z.
The proof of Proposition 1 relies on Lemma 1 in the Appendix. Now, we are able to defined
the Oracle β-set:
Definition 1. Let β ∈ (0, K), the Oracle β-set is given by
Γ∗β (X) = {k ∈ {1, . . . , K} : G(pk (X)) ≤ β}

=
k ∈ {1, . . . , K} : pk (X) ≥ G−1 (β) .
4

This definition of the Oracle β-set is intuitive and can be related to the binary classification
with reject option setting [Cho70, HW06, DH15] in the following way: a label k is assigned to the
Oracle β-set if the probability pk (X) is large enough. It is worth noting that the function G plays
the same role as the c.d.f. of the score function in [DH15]. As emphasized by Proposition 1, their
introduction allows to control exactly the information (2). Indeed, it follows from the definition
of the Oracle β-set that for each β ∈ (0, K)
|Γ∗β (X)| =

K
X

k=1

1{pk (X)≥G−1 (β)} ,

h
i
and then I(Γ∗β ) = E |Γ∗β (X)| = G(G−1 (β)). Therefore, Proposition 1 ensures that
I(Γ∗β ) = β.

This last display points out that the Oracle β-sets are indeed β-level (that is, its information
equals β). In the next section, we focus on the study of the risk of these oracle confidence sets.
Remark 1. Naturally, the definition of Oracle β-sets can be extended to any β ∈ [0, K]. However, the limit cases β = 0 and β = K are of limited interest and are completely trivial. We then
exclude these two limit cases from the present study.

2.2

Properties of the oracle confidence sets

Let us first state the optimality of the Oracle β-set:
Proposition 2. Let Assumption (A1) be satisfied. For any β ∈ (0, K), we have both:
1. The Oracle β-set Γ∗β satisfies the following property:

R Γ∗β = inf R (Γ) ,
Γ

where the infimum is taken over all β-level confidence sets.

2. For any β-level confidence set Γ, the following holds

X

0 ≤ R (Γ) − R Γ∗β = E 

k∈(Γ∗
(X) ∆ Γ(X))
β



pk (X) − G−1 (β)  ,

(3)

where the symbol ∆ stands for the symmetric difference of two sets, that is, for two subsets
A and B of {1, . . . , K}, we write A ∆ B = (A \ B) ∪ (B \ A).

Several remarks can be made from Proposition 2. First, for β ∈ (0, K), the Oracle β-set
is optimal for the misclassification risk, over the class of β-level confidence sets. Moreover, the
excess risk of any β-level confidence set relies on the behavior of the score functions pk around
the threshold G−1 (β). Finally, we can note that if K = 2 and β = 1, which implies that
G−1 (β) = 1/2, Equation (3) reduces to the misclassification excess risk in binary classification.
Remark 2. One way to build a confidence set Γ with information β is to set Γ as the β top
levels conditional probabilities. In the sequel this method is referred as the max procedure. This
strategy is natural but actually suboptimal as shown by the first point of Proposition 2. As an
illustration, we consider a simulation scheme with K = 10 classes. We generate (X, Y ) according
to a mixture model. More precisely,
5

i) the label Y is distributed from a uniform distribution on {1, . . . , K};
ii) conditional on Y = k, the feature X is generated according to a multivariate gaussian
distribution with mean parameter µk ∈ R10 and identity covariance matrix. For each
k = 1, . . . , K, the vectors µk are i.i.d realizations of uniform distribution on [0, 4].
For β = 2 we evaluate the risks of the Oracle β-set and the max procedure and obtain respectively
0.05 and 0.09 (with very small variance).
Remark 3. An important motivation behind the introduction of confidence sets and in particular
of Oracle β-sets is that they might outperform the Bayes rule which can be seen as the Oracle
β-set associated to β = 1. This gap in performance is even larger when the number of classes K
is large and there is a big confusion between classes. Such improvement will be illustrated in the
numerical study (see Section 4.3).
We end up this section by providing another characterization of the Oracle β-set.
Proposition 3. For t ∈ [0, 1], and Γ a confidence set, we define
Lt (Γ) = P (Y ∈
/ Γ(X)) + tI(Γ).
For β ∈ [0, K], the following equality holds:
LG−1 (β) (Γ∗β ) = min LG−1 (β) (Γ).
Γ

The proof of this proposition relies on the same arguments as those of Proposition 2. It is
then omitted. Proposition 3 states that the Oracle β-set is defined as the minimizer, over all
confidence sets Γ, of the risk function Lt when the tuning parameter t is set equal to G−1 (β).
Note moreover that the risk function Lt is a trade-off, controlled by the parameter t, between the
risk of a confidence set on the one hand, and the information provided by this confidence set on
the other hand. Hence, the risk function Lt can be viewed as a generalization to the multiclass
case of the risk function provided in [Cho70, HW06] for binary classification with reject option
setting.

3

Empirical risk minimization

In this section we introduce and study confidence sets which rely on the minimization of convex
risks. Their definitions and main properties are given in Sections 3.1-3.2. As a consequence, we
deduce a data-driven procedure described in Section 3.3 with several theoretical properties, such
as rates of convergence, that we demonstrate in Section 3.4.

3.1

φ-risk

PK
Let f = (f1 , . . . , fK ) : X → RK be a score function and Gf (.) = k=1 F̄fk (.). Assuming that
the function Gf is continuous and given an information level β ∈ (0, K), there exists δ ∈ R,
such that Gf (−δ) = β. Given this simple but important fact, we define the confidence set Γf,δ
associated to f and δ as
Γf,δ (X) = {k : fk (X) ≥ −δ}.
(4)

In this way, the confidence set Γf,δ consists of top scores, and the threshold δ is fixed so that
I (Γf,δ ) = β. As a consequence, we naturally aim at solving the problem
min R(Γf,δ ),
f ∈F

6

where F is a class of functions. Due to computational issues, it is convenient to focus on a
convex surrogate of the previous minimization problem. To this end, let φ : R → R be a convex
function. We define the φ-risk of f by
"K
#
X
Rφ (f ) = E
φ(Zk fk (X)) ,
(5)
k=1

where Zk = 2 1{Y =k} − 1 for all k = 1, . . . , K. Therefore, our target score becomes
f¯ ∈ argmin Rφ (f ) ,
f ∈F

for the purpose of building the confidence Γf¯,δ . In the sequel, we also introduce f ∗ , the minimizer
over the class of all measurable functions, of the φ-risk. The notation suppresses the dependence
on φ. It is worth mentioning at this point that the definition of the risk function Rφ is dictated
by Equation (3) and suits for confidence sets. Moreover, this function differs from the classical
risk function used in the multiclass setting (see [TB07]). The reason behind this is that building
a confidence set is closer to K binary classification problems.

3.2

Classification calibration for confidence sets

Convexification of the risk in classification is a standard technique. In this section we adapt
classical results and tools to confidence sets in the multiclass setting. We refer the reader to
earlier papers as [Zha04, BJM06, YW10] for interesting developments.
One of the main important concept when we deal with convexification of the risk is the notion
of calibration of the loss function φ. This property permits to connect confidence sets deduced
from the convex risk and from the classification risk.
Definition 2. We say that the function φ is confidence set calibrated if for all β > 0, there exists
δ ∗ ∈ R such that
Γf ∗ ,δ∗ = Γ∗β ,
with f ∗ being the minimizer of the φ-risk
f ∗ ∈ argmin Rφ (f ) ,
f

where the infimum is taken over the class of all measurable functions. Hence, the confidence set
based on f ∗ coincides with the Bayes confidence set.
Given this, we can state the following proposition that gives a characterization of the confidence set calibration property in terms of the function G.
Proposition 4. The function φ is confidence set calibrated if and only if for all β ∈ (0, K),
there exists δ ∗ ∈ R such that φ′ (δ ∗ ) and φ′ (−δ ∗ ) both exists, φ′ (δ ∗ ) < 0, φ′ (−δ ∗ ) < 0 and
G−1 (β) =

φ′ (δ ∗ )
,
+ φ′ (−δ ∗ )

φ′ (δ ∗ )

where φ′ denotes the derivative of φ.
The proof of the proposition follows the lines of Theorem 1 in [YW10] with minor modifications. These characterizations of calibration for confidence sets generalize the notion of
7

calibration in the classification setting as well as the necessary and sufficient condition for the
minimizer of the φ-risk to be calibrated. Indeed, if we pick δ = 0 in Definition 2 and Proposition 4 we exactly come back to the calibration property in the classical classification setting
(see [BJM06]). Note that commonly used loss functions as boosting (x 7→ exp(−x)), least squares
(x 7→ (x − 1)2 ) and logistic (x 7→ log(1 + exp(−x))) are examples of calibrated losses (see for
instance [BJM06, WY11]). Now, for some score function f and some real number δ such that
Gf (−δ) = β, we define the excess risk
∆R(Γf,δ ) = R(Γf,δ ) − R(Γ∗β ),
and the excess φ-risk
∆Rφ (f ) = Rφ (f ) − Rφ (f ∗ ) .

We also introduce the marginal conditional excess φ-risk on f = (f1 , . . . , fK ) as
∆Rφk (f (X)) = pk (X)(φ(fk (X)) − φ(fk∗ (X))) + (1 − pk (X))(φ(−fk (X)) − φ(−fk∗ (X))),
for k = 1, . . . , K. The following theorem shows that the consistency in terms of φ-risk implies
the consistency in terms of classification risk R.
Theorem 1. Assume that φ is confidence set calibrated and assume that there exists constants
C > 0 and s ≥ 1 such that1
|pk (X) − G−1 (β)|s ≤ C∆Rφk (−δ ∗ ).

(6)

Let fˆn be a sequence of scores. We assume that for each n, the function Gfˆn is continuous. Let
δn ∈ R be such that Gfˆn (−δn ) = β, then
P
∆Rφ (fˆn ) → 0

P

∆R(Γfˆn ,δn ) → 0.

⇒

The theorem ensures that the convergence in terms of φ risk implies the convergence in terms
of risk R. This convergence is made possible since we manage, in the proof, to bound the excess
risk by (a power of) the excess φ-risk. The assumption needed in this theorem is also standard
and is for instance satisfied for the boosting, least square and logistic losses with the parameter
s being equal to 2 (see [BJM06]).

3.3

Data-driven procedure

In this section we provide the steps of the construction of our empirical confidence set that
is deduced from the empirical risk minimization. Before going into further details, let us first
mention that our procedure is semi-supervised in the sense that it requires two datasets, one of
which being unlabeled. Hence we introduce a first data set Dn = {(Xi , Yi ), i = 1, . . . , n}, which
consists of independent copies of (X, Y ). We define the empirical φ-risk associated to a score
function f (which is the empirical counterpart of Rφ given in (5)):
n

R̂φ (f ) =

K

1 XX
φ(Zki fk (Xi )),
n i=1

(7)

k=1

where Zki = 2 1{Yi =k} − 1 for all k = 1, . . . , K. We also define the empirical risk minimizer over
F , a convex set of score functions, as
fˆ = arg min R̂φ (f ).
f ∈F

1 With

abuse of notation, we write

∆Rkφ (−δ∗ )

instead of ∆Rkφ ((−δ∗ , . . . , −δ∗ )) since no confusion can occur.

8

At this point, we have in hands the optimal score function fˆ and need to build the corresponding
confidence set with the right expected size. However, let us before introduce an intermediate
confidence set that would help comprehension since it mimics the oracle β-set Γ∗ with regard to
its construction using fˆ instead of f ∗ . For this purpose, we define


Ffˆk (t) = PX fˆk (X) ≤ t|Dn ,

for t ∈ R, where PX is the marginal distribution of X. As for the c.d.f. of pk and fk , we make
the following assumption:
(A2) The cumulative distribution functions Ffˆk with k = 1, . . . , K are continuous.
At this point, we are able to define an empirical approximation of the Oracle β-set for
β ∈ (0, K):
n
o
e β (X) = k ∈ {1, . . . , K} : G(
e fˆk (X)) ≤ β ,
Γ
(8)

where for t ∈ R

e =
G(t)

K
X

F̄fˆk (t),

(9)

k=1

e depends on the unknown distribution of X, we consider
with F̄fˆk = 1 − Ffˆk . Since the function G
a second but interestingly unlabeled dataset DN = {Xi , i = 1, . . . , N }, independent of Dn in order
to compute the empirical versions of the F̄fˆk ’s. By now, we can define the empirical β-set based
on fˆ:
Definition 3. Let fˆ be the minimizer of the empirical φ-risk given in (7) based on Dn , and
consider the unlabeled dataset DN . Let β ∈ (0, K). The empirical β-set is given by
n
o
Γ̂β (X) = k ∈ {1, . . . , K} : Ĝ(fˆk (X)) ≤ β ,
(10)

where

N K
1 XX
Ĝ(.) =
1{fˆk (Xi )≥.} .
N i=1
k=1

The most important remark about the construction of this data-driven confidence set is that
it is made in a semi-supervised way. Indeed, the estimation of the tail distribution functions of
fˆk requires only a set of unlabeled observations. This is particularly attractive in applications
where the number of label observations is small (because labelling examples is time consuming
or may be costly) and where one has in hand several unlabeled features that can be used to
make prediction more accurate. As an important consequence is that the estimation of the tail
distribution functions of fˆk does not depend on the number of observations in each class label.
That is to say, this unlabeled dataset can be unbalanced with respect to the classes, that can
often occur in multiclass classification settings where the number of classes K is quite large.
Next section deals with the theoretical performance of the empirical β-sets.

3.4

Rates of convergence

In this Section, we provide rates of convergence for the empirical confidence sets defined in
Section 3.3. First, we state some additional notation. In the sequel, the symbols P and E

9

stand for generic probability and expectation, respectively.
the empirical βMoreover, given

 
/ Γ̂β (X) and the information
set Γ̂β from Definition 3, we consider the risk R Γ̂β = P Y ∈
h
i
 
√
I Γ̂β = E |Γ̂β (X)| . Our first result ensures that Γ̂β is of level β up to a term of order K/ N .
Proposition 5. For each β ∈ (0, K), the following equality holds


 
K
.
I Γ̂β = β + O √
N

In order to precise rates of convergence for the risk, we need to formulate several assumptions.
First, we consider loss functions φ which have in common that the modulus of convexity of their
underlying risk function Rφ , defined by
)
(

 X
K


Rφ (f ) + Rφ (g)
f +g
2
2
(11)
δ(ε) = inf
EX (fk − gk ) (X) ≥ ε ,
,
− Rφ
2
2
k=1

satisfies δ(ε) ≥ c1 ǫ2 for some c1 > 0 (we refer to [BJM06, BM06] for more details on modulus
of convexity for classification risk). Moreover, we assume that φ is classification calibrated and
L-Lipschitz for L > 0. On the other hand, for α > 0, we assume a margin condition Mkα on each
pk , k = 1, . . . , K.

Mkα : PX 0 < |pk (X) − G−1 (β)| ≤ t ≤ c2 tα , for some constant c2 > 0 and for all t > 0.

It is important to note that since we assume that the distribution
functions of pk (X) are contin
uous for each k, we have PX 0 < |pk (X) − G−1 (β)| ≤ t → 0 with t → 0. Therefore, the margin
condition only precise the rate of this decay to 0. Now, we provide the rate of convergence that
we can expect for the empirical confidence sets defined by (10).
Theorem 2. Assume that kf k∞ ≤ B for all f ∈ F. Let Mn = N (1/n, L∞ , F ) be the cardinality
of the set of closed balls with radius 1/n in L∞ -norm needed to cover F . Under the assumptions
of Theorem 1, with the modulos of convexity δ(ε) ≥ c1 ǫ2 with c1 > 0, if φ is L-Lipschitz and if
the margin assumptions Mkα are satisfied with α > 0, then
α/(α+s)

h
i
′ K
K log(Mn )
1−α/(α+s)
inf ∆Rφ (f ) +
E |∆R(Γ̂β )| ≤ C(B, L, s, α)K
+C √ ,
f ∈F
n
N
′

where C > 0 is an absolute constant and C(B, L, s, α) > 0 is a constant that depends only on
L, B, s and α.

α/(α+s)
n)
From this theorem we obtain the following rate of convergence: K log(M
+ √KN .
n
This is the first bound for confidence sets in multiclass setting. The regularity parameter α plays
a crucial role and governs the rate; larger values of α lead to faster rates. Moreover, this rate is
linear in K, the number of classes, that seems to be the characteristic of multiclass classification
as compared to binary classification. Note that the exponent α/(α + s) is not classical
√ and is
due to the estimation of quantiles. The second part of the rates which is of order K/ N relies
on the estimation of the function G̃ given in (9). This part of the estimation is established under
the mild Assumptions (A1) and (A2). For this term the proof of the linearity on K is tricky and
is obtained thanks to a new technical probabilistic results on sums of cumulative distribution
functions (see Lemma 1). Let us conclude this paragraph by mentioning that Theorem 2 applies
for instance for F being the convex hull of a finite family of a score functions which is the scope
of the next section.
10

4

Application to confidence sets aggregation

This Section is devoted to an aggregation procedure which relies on the superlearning principle.
The specifics of our superlearning procedure is given in Section 4.1. In Section 4.2, we show the
consistency of our procedure and finally we provide a numerical illustration in Section 4.3 of our
algorithm.

4.1

Description of the procedure: superlearning

In this section, we describe the superlearning procedure for confidence sets. The superlearning
procedure is based on the V -fold cross-validation procedure (see [vdLPH07]). Initially, this
aggregation procedure has been introduced in the context of regression and binary classification.
Let V ≥ 2 be an integer and let (Bv )1≤v≤V be a regular partition of {1, . . . , n}, i.e., a partition
such that, for each v = 1, . . . , V , card(Bv ) ∈ {⌊n/V ⌋, ⌊n/V ⌋ + 1}, where we write ⌊x⌋ for the
(v)
floor of any real number x (that is, x − 1 ≤ ⌊x⌋ ≤ x). For each v ∈ {1, . . . , V }, we denote by Dn
(−v)
(respectively Dn ) the dataset {(Xi , Yi ), i ∈ Bv } (respectively {(Xi , Yi ), i 6∈ Bv }), and define
the corresponding empirical measures
Pn(v)

=

Pn(−v)

=

X
1
Dirac(Xi , Yi ), and
card(Bv )
i∈Bv
X
1
Dirac(Xi , Yi ).
n − card(Bv )
i6∈Bv

For a score algorithm f , that is to say a function which maps the empirical distribution to a
score function. We define the cross-validated risk of f as
V


X
(P (v) )
bφn (f ) = 1
Rφ n
f (Pn(−v) ) ,
R
V v=1
(Pn(v) )

where for each v ∈ {1, . . . , V }, Rφ

based on

(v)
Dn

(Pn(v) )




f (Pn(−v) ) =

Next, we consider F = f 1 , . . . , f
validated score by

(−v)

)) is the empirical estimator of Rφ (f (Pn

),

(−v)
Dn :

and conditionally on
Rφ

(−v)

(f (Pn

(12)


M

K
XX
1
φ(Zki fk (Pn(−v) )(Xi )).
card(Bv )
i∈Iv k=1

a family of M score algorithms. We define the cross-

bn (f ).
fb ∈ argmin R
φ
f ∈conv(F )

Finally, we consider the resulting cross-validated confidence set defined by
n
o
ˆ
Γ̂CV
β (X) = k ∈ {1, . . . , K} : Ĝ(fk (X)) ≤ β ,

that we analyse in the next section.

11

(13)

4.2

Consistency of the algorithm

In this Section, we show some results that illustrate the consistency of the superlearning procedure described above. To this end, we introduce the oracle counterpart of the cross-validated
risk defined in (12). For a score f , we define
R̃φn (f ) =

V
1 X
Rφ (f (Pn(−v) ),
V v=1

that yields to the oracle counterpart of the cross-validated score defined in (13)
f˜ ∈ argmin R̃φn (f ).
f ∈conv(F )

Here again, we assume that the loss function φ satisfies the properties described in Section 3.4
so that we can state the following result:
(−v)

Proposition 6. We assume that for each f ∈ conv(F ) and v ∈ {1, . . . , V }, kf (Pn
Then the following holds

)k∞ ≤ B.

h
i
KM log(n)
E R̃φn (fˆ) − R̃φn (f˜) ≤ C(B, L)
,
⌊n/V ⌋
where C(B, L) > 0 is a constant that depends only on B and L.
As usual when one deals with cross-validated estimators, the theorem compares fˆ to the
oracle counterpart f˜ in terms of the oracle cross-validated φ-risk. The theorem teaches us that,
for sufficiently large n, fˆ perform as well as f˜. However our main goal remains confidence
sets. Therefore the next step consists in showing that the confidence set associated to the crossvalidated score fˆ has good properties in terms of the classification risk. Let Γf,δ be the confidence
set that results from a choice of β ∈ (0, K) and a score function f ∈ conv(F ). We introduce the
following excess risks
∆R̃n (Γf,δ ) =
∆R̃φn (f ) =


V
1 X
R Γf
V v=1

(−v)
Pn



,δ



− R∗ ,

V
1 X
Rφ (f (Pn(−v) )) − Rφ (f ∗ ).
V v=1

These quantities can be view as cross-validated counterparts of the excess risks introduced in
Section 3.2. Hereafter, we provide a result which can be view as the cross-validation counterpart
of Theorem 2. It is interpreted in a same way.

 

(−v)
≤ t|Dn is conProposition 7. We assume that for each v ∈ {1, . . . , V }, t 7→ PX fˆ Pn

tinuous. Under the assumptions of Proposition 6 and if the margin assumptions Mkα are satisfied
with α > 0,


h
i

 KM log(n) α/(α+s)
′ K
n ˜
n
CV
1−α/(α+s)
E ∆R̃φ (f ) +
E |∆R̃ (Γ̂β )| ≤ C(B, L, α, s)K
+C √ .
⌊n/V ⌋
N

The proof of Proposition 7 relies on Proposition 6 and similar arguments as in Theorem 2.
12

Forest (K = 4)
β-set
β
2

rforest
R
I

0.02 (0.02)
2.00 (0.09)

softmax reg

svm

0.06 (0.02)
2.00 (0.08)

0.02 (0.01)
2.00 (0.09)

kknn
0.05 (0.03)
2.00 (0.08)

CV
0.02 (0.01)
2.00 (0.08)

Plant (K = 100)
β-set
β
2
10

rforest
R
I
R
I

0.18
2.00
0.02
9.95

(0.03)
(0.09)
(0.01)
(0.38)

softmax reg

svm

0.77 (0.02)
2.02 (0.18)
0.42 (0.04)
10.06 (0.58)

0.32
1.99
0.03
9.98

(0.04)
(0.10)
(0.02)
(0.22)

kknn
0.20
2.00
0.08
9.98

(0.03)
(0.08)
(0.03)
(0.23)

CV
0.17
2.00
0.02
9.96

(0.03)
(0.08)
(0.01)
(0.37)

Table 1: For each of the B = 100 repetitions and for each dataset, we derive the estimated
risks R and information I of the different β-sets w.r.t. β. We compute the means and standard
deviations (between parentheses) over the B = 100 repetitions. For each β, the β-sets are based
on, from left to right, rforest, softmax reg and svm, kknn and CV which are respectively the
random forest, the softmax regression, support vector machines, k nearest neighbors and the
superlearning procedure. Top: the dataset is the Forest – the dataset is the Plant.

4.3

Application to real datasets

In this section, we provide an application of our aggregation procedure described in Section 4.1.
For the numerical experiment we focus on the boosting loss and consider the library of algorithms
constituted by the random forest, the softmax regression, the support vector machines and the
k nearest neighbors (with k = 11) procedures. To be more specifics, we respectively exploit
the R packages randomForest, polspline, e1071 and kknn. All the R functions are used with
standard tuning parameters. Finally the parameter V of the aggregation procedure is fixed to 5.
We evaluate the performance of the procedure on two real datasets: the Forest type mapping
dataset and the one-hundred plant species leaves dataset coming from the UCI database. In the
sequel we refer to these two datasets as Forest and Plant respectively. The Forest dataset
consists of K = 4 classes and 523 labeled observations (we gather the train and test sets) with 27
features. Here the classes are unbalanced. In the Plant dataset, there are K = 100 classes and
1600 labeled observations. This dataset is balanced so that each class consists of 16 observations.
The original dataset contains 3 covariates (each covariate consists of 64 features). In order to
make the problem more challenging, we drop 2 covariates.
To get an indication of the statistical significance, it makes sense to compare our aggregated
confidence set (referred as CV) to the confidence sets that result from each component of the
library. Roughly speaking, we evaluate risks (and informations) of these confidence sets on each
dataset. To do so, we use the cross validation principle. In particular, we run B = 100 times
the procedure where we split the data each time in three: a sample of size n to build the scores
fˆ; a sample of size N to estimate the function G and to get the confidence sets; and a sample
of size M to evaluate the risk and the information. For both datasets, we make sure that in the
sample of size n, there is the same number of observations in each class. As a benchmark, we
notify that the misclassification risks of the best classifier from the library in the Forest dataset
is evaluated at 0.15 , whereas in the Plant dataset, it is evaluated at 0.40. As planned, the
performance of the classical methods are quite bad in this last dataset.
We set the sizes of the samples as n = 200, N = 100 and M = 223 for the Forest dataset,

13

and n = 1000, N = 200 and M = 400 for the Plant one. The results are reported in Table 1, and
confirm our expectations. In particular, our main observation is that the aggregated confidence
set (CV) outperforms all components of the library in the sense that it is at least as good as the
best component in all of the experiments. Second, let us state some remarks that hold for all
of the confidence sets and in particular our aggregated confidence set. First, we note that the
information I(Γ) has the good level β which is supported by our theory. Moreover, we see that
the risk gets drastically better with moderate β as compared to the best misclassification risk.
For instance, for the Plant, the error rate of the confidence set with β = 2 based on random
forests is 0.18 whereas the misclassification error rate of the best component is 0.40.

5

Conclusion

In multiclass classification setting, the present paper propose a new procedure that assigns a set
of labels instead of a single label to each instance. This set has a controlled expected size (or
information) and its construction relies on cumulative distribution functions and on an empirical
risk minimization procedure. Theoretical guarantees, especially rates of convergence are also
provided and rely on the regularity of these cumulative distribution functions. The obtained
rates of convergence highlight a linear dependence w.r.t the number of classes K. The procedure
described in Section 3 is defined as a two steps algorithm whose second step consists in the
estimation of the function G (which is a sum of tail distribution functions). Interestingly, this
step does not require a set of labeled data and neither to explore the whole classes, that is suitable
for semi-supervised learning. Moreover, we apply our methodology to derive an aggregation
algorithm which is based on the V -fold cross-validation principle. Future works will focus on
the optimality in the minimax sense with respect to the classification error. In particular, we
will investigate whether the rates of convergence are optimal in terms of their dependence on K.
We believe that this dependence (linearity on K) is the correct one. However we will instigate
whether this dependence can be reduced under some sparsity assumption.

6

Appendix

This section gathers the proofs of our results. Let us first add a notation that will be used
throughout the Appendix: for any random variable (or vector) Z, we denote by PZ the probability
w.r.t. Z and by EZ , the corresponding expectation.

6.1

Technical Lemmas

We first lay out key lemmata, which are crucial to establish the main theory. We consider K ≥ 2
be an integer, and Z1 , . . . , ZK , K random variables. Moreover we define function H by:
H(t) =

K
1 X
Fk (t), ∀t ∈ [0, 1],
K
k=1

where for all k = 1, . . . , K, Fk is the cumulative distribution function of Zk . Finally, let us define
the generalized inverse H −1 of H:
H −1 (p) = inf{t : H(t) ≥ p}, ∀p ∈ (0, 1).

14

Lemma 1. Let ε distributed from a uniform distribution on {1, . . . , K} and independent of Zk ,
k = 1, . . . , K. Let U distributed from a uniform distribution on [0, 1]. We consider
Z=

K
X

k=1

Zk 1{ε=k} .

If H is continuous then
L

L

H(Z) = U and H −1 (U ) = Z


Proof. First we note that for every t ∈ [0, 1], P (H(Z) ≤ t) = P Z ≤ H −1 (t) . Moreover, we
have
P (H(Z) ≤ t) =
=

K
X

k=1

P(Z ≤ H −1 (t), ε = k)

K
1 X
P(Zk ≤ H −1 (t)) with ε independent of X
K
k=1

=

H(H −1 (t))

=

t with H continuous.

To conclude the proof, we observe that
P H −1 (U ) ≤ t



=
=

P (U ≤ H(t))
K
1 X
Fk (t)
K
k=1

=

K
X

k=1

=

P (Zk ≤ t, ε = k)

P(Z ≤ t).

Lemma 2. There exists an absolute constant C ′ > 0 such that


′
K
e fˆk (X))| ≥ |G(
e fˆk (X)) − β| ≤ C
√ .
P |Ĝ(fˆk (X) − G(
N
k=1
K
X

Proof. We define, for γ > 0 and k ∈ {1, . . . K}
n
o
e fˆk (X)) − β ≤ γ
Ak0 =
G(
n
o
e fˆk (X)) − β| ≤ 2j γ , j ≥ 1.
Akj =
2j−1 γ < |G(
Since, for every k, the events (Akj )j≥0 are mutually exclusive, we deduce
K
X

k=1



e fˆk (X))| ≥ |G(
e fˆk (X)) − β| =
P |Ĝ(fˆk (X) − G(
K X
X
k=1 j≥0



e fˆk (X))| ≥ |G(
e fˆk (X)) − β|, Akj . (14)
P |Ĝ(fˆk (X) − G(
15

Now, we consider a random variable ε uniformly distributed on {1, . . . , K} and independent of
Dn and X. Conditional on Dn and under Assumption (A2), we apply Lemma 1 with Zk = fˆk (X),
PK
e
is uniformly distributed on [0, K]. Therefore,
Z = k=1 Zk 1{ε=k} and then obtain that G(Z)
for all j ≥ 0 and γ > 0, we deduce
K


1 X
e fˆk (X)) − β| ≤ 2j γ|Dn
PX |G(
K
k=1

Hence, for all j ≥ 0, we obtain

K
X

k=1

Next, we observe that for all j ≥ 1
K
X

k=1



e
− β| ≤ 2j γ|Dn
= PX |G(Z)

≤

2j+1 γ
.
K

P(Akj ) ≤ 2j+1 γ.

(15)



e fˆk (X))| ≥ |G(
e fˆk (X)) − β|, Akj ≤
P |Ĝ(fˆk (X) − G(
K
X

k=1

i


h
e fˆk (X))| ≥ 2j−1 γ|Dn , X 1Ak . (16)
E(Dn ,X) PDN |Ĝ(fˆk (X)) − G(
j

Now, since conditional on (Dn , X), Ĝ(fˆk (X)) is an empirical mean of i.i.d random variables of
e fˆk (X)) ∈ [0, K], we deduce from Hoeffding’s inequality that
common mean G(




N γ 2 22j−1
j−1
ˆ
ˆ
e
.
PDN |Ĝ(fk (X)) − G(fk (X))| ≥ 2 γ|Dn , X ≤ 2 exp −
K2

Therefore, from Inequalities (14), (15) and (16), we get
K
X

k=1



e fˆk (X))| ≥ |G(
e fˆk (X)) − β|
P |Ĝ(fˆk (X) − G(

!

 X
K

N γ 2 22j−1
k
P
+
2 exp −
≤
P Aj
K2
j≥1
k=1
k=1


X
N γ 2 22j−1
j+2
.
≤ 2γ + γ
2
exp −
K2
K
X

Ak0



X

j≥1

K
Finally, choosing γ = √ in the above inequality, we finish the proof of the lemma.
N

16

6.2

Proof of Proposition 2

Let β > 0 and Γ be a confidence set such that I(Γ) = β. First, we note that the following
decomposition holds
R(Γ) −

R(Γ∗β )
=

=

K X
K
X

K X
K
X

E

j=1 k=1

=

E

j=1 k=1

K X
K
X

"

E

j=1 k=1

"

K
X
l=1

K
X
l=1

(1{Y ∈Γ(X)}
− 1{Y ∈Γ
/
/ ∗
(X)} )1{Y =l} 1{|Γ(X)|=k} 1{|Γ∗
(X)|=j}
β
β

(1{l∈Γ(X)}
− 1{l∈Γ
/
/ ∗
(X)} )pl (X)1{|Γ(X)|=k} 1{|Γ∗
(X)|=j}
β
β

"K
X
l=1

#

#

#

(1{l∈Γ∗β (X)\Γ(X)} − 1{l∈Γ(X)\Γ∗β (X)} )pl (X)1{|Γ(X)|=k,|Γ∗β (X)|=j} ,

where we conditioned by X to get the second equality. From the last decomposition and with


E [|Γ(X)|] = E |Γ∗β (X)|


K X
K
X
= E
k1{|Γ(X)|=k} 1{|Γ∗β (X)|=j} 
j=1 k=1



K X
K
X
E
j1{|Γ(X)|=k} 1{|Γ∗ (X)|=j}  ,

=

β

j=1 k=1

we can express the excess risk as the sum of two terms:

R(Γ) −

R(Γ∗β )
+

=

K X
K
X

E

j=1 k=1

K X
K
X

j=1 k=1

E

"

"

−1

kG

K
X
l=1

−1

1{l∈Γ∗β (X)\Γ(X)} pl (X) − jG

(β) −

K
X
l=1

!

!

(β) 1{|Γ(X)|=k} 1{|Γ∗β (X)|=j}

1{l∈Γ(X)\Γ∗β (X)} pl (X) 1{|Γ(X)|=k} 1{|Γ∗β (X)|=j} . (17)

Now, for j, k ∈ {1, . . . , K} on the event {|Γ(X)| = k, |Γ∗β (X)| = j}, we have
k=

K
X

1{l∈Γ(X)\Γ∗β (X)} +

K
X

1{l∈Γ(X)∩Γ∗β (X)} ,

K
X

1{l∈Γ∗β (X)\Γ(X)} +

K
X

1{l∈Γ(X)∩Γ∗β (X)} .

l=1

and
j=

l=1

Therefore, since

#

#

l=1

l=1

l ∈ Γ∗β ⇔ pl (X) ≥ G−1 (β),
Equality (17) yields the result.

17

6.3

Proof of Theorem 1

First we recall that fˆn = (fˆn,1 , . . . , fˆn,K ) is a sequence of score functions and δn ∈ R is such that
Gfˆn (−δn ) = β. We suppress the dependence on n to simplify notation and write fˆ = (fˆ1 , . . . , fˆK )
and δ for fˆ and δn respectively. Moreover, since there is no doubt, we also suppress everywhere
the dependence on X. We also define the events
Bk = {fˆk ∈ (−δ, −δ ∗ ) or fˆk ∈ (−δ ∗ , −δ)},

(18)

for k = 1, . . . , K. We aim at controlling the excess risk ∆R(Γfˆ,δ ). Since the risk R is decomposable, it is convenient to introduce “marginal excess risks”:
∆Rk (Γf,δ ) = 1{k∈(Γfˆ,δ ∆ Γ∗β )} |pk − G−1 (β)|.
Recall also that by convexity of the loss function φ, we have that for all x, y ∈ R,
φ(y) − φ(x) ≥ φ′ (x)(y − x).

(19)

Assume that fˆk ≤ −δ and fˆk ≤ −δ ∗ ≤ fk∗ , which translates as pk − G−1 (β) ≥ 0, we get thanks
to (19)
pk (φ(fˆk ) − φ(−δ)) − (1 − pk )(φ(−fˆk ) − φ(δ)) ≥ (φ′ (δ ∗ ) − φ′ (−δ ∗ ))(pk − G−1 (β))(fˆk + δ ∗ ) ≥ 0.
Similarly, if fˆk ≥ −δ and fˆk ≥ −δ ∗ ≥ fk∗ , that is, pk − G−1 (β) ≤ 0 we have
pk (φ(fˆk ) − φ(−δ)) − (1 − pk )(φ(−fˆk ) − φ(δ)) ≥ 0.
Note that in the following two cases
• fˆk ≤ −δ
• fˆk ≥ −δ

and fk∗ ≤ −δ ∗ ;

and fk∗ ≥ −δ ∗ ,

we have ∆Rk (Γfˆ,δ ) = 0. Therefore, from the above inequalities, on Bkc and by assumption (6)
we get
(20)
1Bkc 1{k∈(Γfˆ,δ ∆ Γ∗β )} |pk − G−1 (β)|s ≤ C(∆Rφk (fˆ)).
Therefore, since s ≥ 1, we have
"K
#!s
X
E
1Bkc ∩{k∈(Γfˆ,δ ∆ Γ∗β )} |pk − G−1 (β)|
k=1

K
i
1 X h
E 1Bkc ∩{k∈Γfˆ,δ ∆Γ∗β } K s |pk − G−1 (β)|s
K

≤

k=1

CK s−1 ∆Rφ (fˆ).

≤

Moreover
E

"

K
X

k=1

−1

1Bk 1{k∈(Γfˆ,δ ∆ Γ∗β )} |pk − G

#

(β)|

≤
≤
≤

18

K
X

k=1

P(Bk )

h
i
E |Gfˆ(−δ) − Gfˆ(−δ ∗ )|
h
i
E |Gf ∗ (−δ ∗ ) − Gfˆ(−δ ∗ )| .

Finally, we get the following bound
∆R(Γfˆ,δ ) ≤ K

s−1
s

Now we observe that

i
h
∆Rφ (fˆ)1/s + E |Gf ∗ (−δ ∗ ) − Gfˆ(−δ ∗ )| .

|1{fˆk ≥−δ∗ } − 1{fk∗ ≥−δ∗ } | ≤ 1{|pk −G−1 (β)|s ≤C∆Rk (fˆ)} .
φ

(21)

Therefore, for each γ > 0, we have
i
h
EX |Gf ∗ (−δ ∗ ) − Gfˆ(−δ ∗ )| ≤
≤

K
X

k=1
K
X

k=1



PX |pk (X) − G−1 (β)|s ≤ C∆Rφk (fˆ)





PX |pk (X) − G−1 (β)| ≤ γ 1/s + PX γ ≤ C∆Rφk (fˆ) .

Now using Markov Inequality, we have that
K
X

k=1



≤
PX γ ≤ C∆Rφk (fˆ)

K
h
i
CX
EX ∆Rφk (fˆ)
γ
k=1

C∆Rφ (fˆ)
.
γ

≤
The above inequality yields

K


i C∆R (fˆ) X
h
φ
PX |pk (X) − G−1 (β)| ≤ γ 1/s .
+
EX |Gf ∗ (−δ ∗ ) − Gfˆ(−δ ∗ )| ≤
γ

(22)

k=1

Hence, with Equation (21), we get
∆R(Γfˆ,δ ) ≤ K

s−1
s

∆Rφ (fˆ)1/s +

K


C∆Rφ (fˆ) X
+
PX |pk (X) − G−1 (β)| ≤ γ 1/s .
γ
k=1


PK
The term k=1 PX |pk (X) − G−1 (β)| ≤ γ 1/s → 0 when γ → 0, given that the distribution
function of the p′k s are continuous. Then using the convergence in distribution of ∆Rφ (fˆ) to
zero, the last inequality ensures the desired result.

6.4

Proof of Proposition 5

For any β ∈ (0, K), and conditional on Dn we define
e−1 (β) = inf{t ∈ R : G(t)
e ≤ β}.
G

e
We note that Assumption (A2) ensures that t 7→ G(t)
is continuous and then
e G
e−1 (β)) = β.
G(
19

(23)

Now, we have
e β (X)| =
|Γ
=

K
X

k=1
K
X

k=1

Hence, the last equation implies that

1 {G
e(fˆ (X))≤β}
k

1{fˆ (X)≥G
e−1 (β)} .
k

K


i X
h
e G
e −1 (β)) = β.
e−1 (β)|Dn = G(
e β (X)||Dn =
PX fˆk (X) ≥ G
EX |Γ

(24)

k=1

h
i
e β (X)| = β. Also, we can write
Therefore, we obtain E |Γ
h
i
E Γ̂β (X) − β

≤

≤
≤
≤
≤

h
i
e β (X)|
E |Γ̂β (X)| − |Γ
"K
#

X
E
1{Ĝ(fˆk (X))≤β} − 1{G
e(fˆk (X))≤β}
k=1
h
i
e β (X)|
E |Γ̂β (X) ∆ Γ
K
X

k=1
K
X

k=1

h
i
E |1{Ĝ(fˆk (X))≤β} − 1{G
|
ˆ
e(f (X))≤β}
k



e fˆk (X))| ≥ |G(
e fˆk (X)) − β| .
P |Ĝ(fˆk (X) − G(

Hence, applying Lemma 2 in the above inequality, we obtain the desired result.

6.5

Proof of Theorem 2

When there is no doubt, we suppress the dependence on X. First, let us state a intermediate
result that is also needed to prove the theorem.
Lemma 3. Consider Γfˆ,δ the confidence set based on the score function fˆ with information β
(that is, Gfˆ(−δ) = β). Under assumptions Mαk , the following holds
o
n
∆R(Γfˆ,δ ) ≤ C(α, s) K 1−1/(s+λ−λs) ∆Rφ (fˆ)1/(s+λ−λs) + K 1−λ/(s+λ−λs) ∆Rφ (fˆ)λ/(s+λ−λs) ,

where λ =

α
α+1

and C(α, s) is non negative constant which depends only on α and s.

Proof. For each k = 1, . . . , K, we define the following events Sk = Bkc ∩ {k ∈ (Γfˆ,δ ∆ Γ∗β )} and
Tk = Bk ∩ {k ∈ (Γfˆ,δ ∆ Γ∗β )}, where the Bk ’s are the events given in Eq. (18). Now we observe
that
"K
#
"K
#
X
X
−1
−1
∆R(Γfˆ,δ ) = E
1Sk |pk − G (β)| + E
1Tk |pk − G (β)| = ∆R1 (Γfˆ,δ ) + ∆R2 (Γfˆ,δ ),
k=1

k=1

20

where
∆R1 (Γfˆ,δ )
∆R2 (Γfˆ,δ )

= E
= E

"

"

K
X

k=1
K
X

#

1Sk |pk − G−1 (β)| ,
−1

k=1

1Tk |pk − G

#

(β)| .

The end of the proof consists in controlling each of these two terms. Let us first consider
∆R1 (Γfˆ,δ ). For ε > 0, we have
∆R1 (Γfˆ,δ ) = E
≤ E

"

"

K
X

k=1

K
X

−1

1Sk |pk − G
1Sk ε

1−s

k=1

(β)| 1{|pk −G−1 (β)|≥ε} + 1{|pk −G−1 (β)|≤ε}
−1

|pk − G

≤ Cε1−s ∆Rφ (fˆ) + ε

K
X

s

(β)|

#

+ε

K
X

#


P(Sk )

k=1

P(Sk ),

(25)

k=1

where we used the assumption (6) and more precisely (20) to deduce the last inequality. To
PK
control
k=1 P(Sk ), we require the following result that is a direct application of Lemma 5
in [BJM06].
Lemma 4. Under the assumptions Mαk we have
K
X

k=1

α

 α+1
,
P (Sk ) ≤ C(α) K 1/α ∆R1 (Γfˆ,δ )

where C(α) > 0 is a constant that depends only on α.
Proof. The proof of this result relies on the following simple fact: for all ε > 0




E 1Sk |pk − G−1 (β)| ≥ εE 1Sk 1{|pk −G−1 (β)|≥ε}
Choosing ε =



1
c2 K(α+1)

PK

k=1

P (Sk ))

1/α

≥ ε [P (Sk ) − c2 εα ] .

we get the lemma.

We go back to the proof of Lemma 3. Applying Lemma 4 to (25), we get
α

 α+1
.
∆R1 (Γfˆ,δ ) ≤ Cε1−s ∆Rφ (fˆ) + εC(α) K 1/α ∆R1 (Γfˆ,δ )

Choosing ε =

s−1
(λ−1)
∆R1 (Γfˆ,δ )(1−λ) ,
sC(α) K

we obtain

∆R1 (Γfˆ,δ ) ≤ C1 (α, s)K 1−1/(s−λs+λ) ∆Rφ (fˆ)1/(s+λ−λs) ,
for a non negative constant C1 (α, s) that depends only on α and s.

21

(26)

Let us now focus on the second term, ∆R2 (Γfˆ,δ ). Since the assumptions of Theorem 1 are
satisfied, we can use Eq. (22) for any γ > 0. Combined with the Margin assumptions Mαk , we
obtain
i
h
∆R2 (Γfˆ,δ ) ≤ EX |Gf ∗ (−δ ∗ ) − Gfˆ(−δ ∗ )|
≤

C∆Rφ (fˆ)
+ c2 Kγ α/s .
γ

Therefore, optimizing in γ, we have
∆R2 (Γfˆ,δ ) ≤ C2 (α, s)K 1−λ/(s+λ−λs) ∆Rφ (fˆ)λ/(s+λ−λs) ,
for a non negative constant C2 (α, s) that depends only on α and s. The result stated in the
lemma is deduced by combining the last equation with Eq. (26) and by setting C(α, s) =
max{C1 (α, s); C2 (α, s)}.
We now state another important lemma that describes the behavior of the empirical minimizer
of the φ-risk on the class F :
Lemma 5. Let f¯ ∈ F be the minimizer of Rφ (f ) over F . Under the assumptions of Theorem 2,
we have that
h
i 3KL KC(B, L) log(N )
n
+
,
E Rφ (fˆn ) − Rφ (f¯) ≤
n
n
where C(B, L) > 0 is a constant that only depends on the constant B given in the Proposition 6
and on the Lipschitz constant L.
Proof. First, according to Eq. (11), for each f ∈ F, we can write

v
uK


uX
¯
¯


f +f
Rφ (f ) + Rφ (f )
≥ δ t
EX (fk − f¯k )2 (X)  ,
− Rφ
2
2
k=1

Hence, by assumption on the modulus of convexity, we deduce



K
X


Rφ (f ) + Rφ (f¯)
f + f¯
≥ c1
EX (fk − f¯k )2 (X) .
− Rφ
2
2
k=1

Since Rφ




¯

f +f
2

≥ Rφ (f¯), we obtain
K
X

k=1



1
Rφ (f ) − Rφ (f¯).
EX (fk − f¯k )2 (X) ≤
2c1

Now, denoting by h(z, f (x)) =

PK

k=1

φ(zk fk (x)) − φ(zk f¯k (x)), we get the following bound



EX h2 (Zf (X))

≤ KL2
≤

K
X

k=1



EX (fk − f¯k )2 (X)

KL2
EX [h(Zf (X))] ,
2c1
22

(27)

where L is the Lipschitz constant L for φ. On the other hand, we have the following decomposition
Rφ (fˆ) − Rφ (f¯) = Rφ (fˆ) + 2(R̂φ (fˆ) − R̂φ (f¯)) − 2(R̂φ (fˆ) − R̂φ (f¯)) − Rφ (f¯).
Also, since R̂φ (fˆ) − R̂φ (f¯) ≤ 0, we get
Rφ (fˆ) − Rφ (f¯)

≤ (Rφ (fˆ) − Rφ (f¯)) − 2(R̂φ (fˆ) − R̂φ (f¯))
3KL
+ sup (Rφ (f ) − Rφ (f¯)) − 2(R̂φ (f ) − R̂φ (f¯)),
≤
n
f ∈Fn

where Fn is the ǫ-net of F w.r.t the L∞ -norm and with ǫ = 1/n. Now, using Bernstein’s
Inequality, we have that for all f ∈ Fn and t > 0


P (Rφ (f ) − Rφ (f¯)) − 2(R̂φ (f ) − R̂φ (f¯)) ≥ t ≤


P 2((Rφ (f ) − Rφ (f¯)) − (R̂φ (f ) − R̂φ (f¯)) ≥ t + Rφ (f ) − Rφ (f¯)


n(t + E [h(Z, f (X))])2 /8
≤ exp −
.
E [h2 (Z, f (X))]) + (2KLB/3)(t + E [h(Z, f (X))]))

Using Eq. (27), we get for all f ∈ Fn




P (Rφ (f ) − Rφ (f¯)) − 2(R̂φ (f ) − R̂φ (f¯)) ≥ t ≤ exp −


nt
,
8(KL2 /(2c1 ) + KLB/3)

Therefore, using a union bound argument, and then integrating we deduce that
#
"
h
i
3KL
ˆ
¯
¯
¯
E Rφ (f ) − Rφ (f ) ≤
+ E sup (Rφ (f ) − Rφ (f )) − 2(R̂φ (f ) − R̂φ (f ))
n
f ∈Fn
≤

3KL KC(B, L) log(Mn )
+
.
n
n

We are now ready to conclude the proof of the theorem. We have the following inequality
e β ) + |R(Γ̂β ) − R(Γ
e β )|.
|R(Γ̂β ) − R∗β | ≤ ∆R(Γ

(28)

We deal which each terms in the r.h.s separately. First, we have from Jensen’s Inequality that
h
i
 h
i s+λ−λs
λ
e β ) s+λ−λs
eβ )
λ
≤ E ∆R(Γ
.
E ∆R(Γ

Hence, from Lemma 3, we deduce

 h
i s+λ−λs
h
i
s+λ−λs
s+λ−λs
λ
eβ )
≤ C(α, s) λ K λ −1 E ∆Rφ (fˆ) .
E ∆R(Γ

Moreover, from Lemma 5, we have that

h
i
3KL KC(B, L) log(Mn )
+
.
E ∆Rφ (fˆ) ≤ inf ∆Rφ (f ) +
f ∈F
n
n
23

Therefore, we can write
λ/(s+λ−λs)

h
i
e β ) ≤ C(α, s)K 1−λ/(s+λ−λs) inf ∆Rφ (f ) + 3KL + KC(B, L) log(Nn )
.
E ∆R(Γ
f ∈F
n
n
(29)
e β )| in (28), we observe that
For the second term |R(Γ̂β ) − R(Γ
1{Y ∈/ Γ̂β (X)} − 1{Y ∈/e
Γ

β (X)}

=

K
X

k=1

1{Y =k} 1{k∈/ Γ̂β (X)} −

K
X

k=1

Therefore, we can write

i
h
=
E 1Y ∈/ Γ̂β (X)} − 1{Y ∈/e
Γβ (X)}
=

K
X

k=1

K
X

k=1

1{Y =k} 1k∈/e
Γ

β (X)

.

i
h

E pk (X) 1{k∈/ Γ̂β (X)} − 1{k∈/e
Γβ (X)}

i
h

E pk (X) 1{Ĝ(fˆk (X))>β } − 1{G̃(fˆk (X))>β} .

Since 0 ≤ pk (X) ≤ 1 for all k ∈ {1, . . . , K}, the last equality implies
h
 

R Γ̂β − R Γ̃β = E 1Y ∈/ Γ̂β (X)} − 1{Y ∈/e
Γ

β (X)}

≤

K
X

k=1

i

h
i
E 1{Ĝ(fˆk (X))>β } − 1{G̃(fˆk (X))>β}
≤

K
X

k=1

Therefore, Lemma 2 implies



e fˆk (X))| ≥ |G(
e fˆk (X)) − β| .
P |Ĝ(fˆk (X) − G(

 

C ′K
R Γ̂β − R Γ̃β ≤ √ .
N
Injecting Eqs. (29) and (30) to Eq. (28) we conclude the proof of the theorem.

6.6

(30)

Proof of Proposition 6

We begin with the following decomposition
R̃φn (fˆ) − R̃φn (f˜) = R̃φn (fˆ) + 2(R̂φn (fˆ) − R̂φn (f˜)) − 2(R̂φn (fˆ) − R̂φn (f˜)) − R̃φn (f˜),
since R̂φn (fˆ) − R̂φn (f˜) ≤ 0, we get
R̃φn (fˆ) − R̃φn (f˜) ≤ (R̃φn (fˆ) − R̃φn (f˜)) − 2(R̂φn (fˆ) − R̂φn (f˜)).

(31)

Now, we denote by Cn = {(i1 /n, . . . , iM /n), (i1 , . . . , iM ) ∈ {0, . . . , n}} ∩ CM ,
PM
and Fn = {f = i=1 mi fi , m1 , . . . mM ) ∈ Cn }. For each f ∈ conv(F ), there exists fn ∈ Fn
such that
|R̃φn (f ) − R̃φn (fn )| ≤
|R̂φn (f ) − R̂φn (fn )| ≤
24

2KLBM
n
2KLBM
.
n

Therefore, with Equation (31), we obtain
6LKB
R̃φn (fˆ) − R̃φn (f˜) ≤
+ sup (R̃φn (f ) − R̃φn (f¯)) − 2(R̂φn (f ) − R̂φn (f¯)).
n
f ∈Fn
Now, Similar arguments as in [DvdL05] and Lemma 5 yield the proposition.

References
[BJM06]

P. Bartlett, M. Jordan, and J. McAuliffe. Convexity, classification, and risk bounds.
Journal of the American Statistical Association, 101(473):138–156, 2006.

[BM06]

P. Bartlett and S. Mendelson. Empirical minimization. Probability Theory and
Related Fields, 135(3):311–334, 2006.

[CCB16]

A. Choromanska, K. Choromanski, and M. Bojarski. On the boosting ability of topdown decision tree learning algorithm for multiclass classification. preprint, 2016.

[Cho70]

C.K. Chow. On optimum error and reject trade-off. IEEE Transactions on Information Theory, 16:41–46, 1970.

[dCDB09] J. del Coz, J. Díez, and A. Bahamonde. Learning nondeterministic classifiers. Journal
of Machine Learning Research, 10:2273–2293, 2009.
[DH15]

C. Denis and M. Hebiri. Consistency of plug-in confidence sets for classification in
semi-supervised learning. preprint, 2015.

[DvdL05]

S. Dudoit and M. van der Laan. Asymptotics of cross-validated risk estimation in
estimator selection and performance assessment. Statistical Methodology, 2(2):131–
154, 2005.

[FHT00]

J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical
view of boosting. The Annals of Statistics, 28(2):337–407, 2000.

[FS97]

Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and
an application to boosting. Journal of computer and system sciences, 55(1):119–139,
1997.

[HW06]

R. Herbei and M. Wegkamp. Classification with reject option. The Canadian Journal
of Statistics, 34(4):709–721, 2006.

[Lei14]

J. Lei. Classification with confidence. Biometrika, 101(4):755–769, 2014.

[LRW13]

J. Lei, J. Robins, and L. Wasserman. Distribution-free prediction sets. Journal of
the American Statistical Association, 108(501):278–287, 2013.

[TB07]

A. Tewari and P. Bartlett. On the consistency of multiclass classification methods.
Journal of Machine Learning Research, 8:1007–1025, 2007.

[Vap98]

V. Vapnik. Statistical learning theory. Adaptive and Learning Systems for Signal
Processing, Communications, and Control. John Wiley & Sons Inc., New York, 1998.
A Wiley-Interscience Publication.

25

[vdLPH07] M. van der Laan, E. Polley, and A. Hubbard. Super learner. Statistical Applications
in Genetics and Molecular Biology, 6, 2007.
[vdV98]

A. van der Vaart. Asymptotic statistics, volume 3 of Cambridge Series in Statistical
and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1998.

[VGS99]

V. Vovk, A. Gammerman, and C. Saunders. Machine-learning applications of algorithmic randomness. In International Conference on Machine Learning, pages
444–453. 1999.

[VGS05]

V. Vovk, A. Gammerman, and G. Shafer. Algorithmic learning in a random world.
Springer, New York, 2005.

[Vov02]

V. Vovk. Asymptotic optimality of transductive confidence machine. In Algorithmic
learning theory, volume 2533 of Lecture Notes in Computer Science, pages 336–350.
Springer, Berlin, 2002.

[WLW04]

T.-F. Wu, C.-J. Lin, and R. Weng. Probability estimates for multi-class classification
by pairwise coupling. Journal of Machine Learning Research, 5:975–1005, 2004.

[WY11]

M. Wegkamp and M. Yuan. Support vector machines with a reject option. Bernoulli,
17(4):1368–1385, 2011.

[YW10]

M. Yuan and M. Wegkamp. Classification methods with reject option based on
convex risk minimization. Journal of Machine Learning Research, 11:111–130, 2010.

[Zha04]

T. Zhang. Statistical behavior and consistency of classification methods based on
convex risk minimization. The Annals of Statistics, 32(1):56–85, 02 2004.

26

