Learning from Survey Training Samples:
Rate Bounds for Horvitz-Thompson Risk Minimizers

arXiv:1610.03316v1 [math.ST] 11 Oct 2016

Stéphan Clémençon∗, Patrice bertail†, Guillaume Papa∗
October 12, 2016

Abstract
The generalization ability of minimizers of the empirical risk in the context of binary classification has been investigated under a wide variety of complexity assumptions for the collection
of classifiers over which optimization is performed. In contrast, the vast majority of the works
dedicated to this issue stipulate that the training dataset used to compute the empirical risk
functional is composed of i.i.d. observations and involve sharp control of uniform deviation of
i.i.d. averages from their expectation. Beyond the cases where training data are drawn uniformly without replacement among a large i.i.d. sample or modelled as a realization of a weakly
dependent sequence of r.v.’s, statistical guarantees when the data used to train a classifier are
drawn by means of a more general sampling/survey scheme and exhibit a complex dependence
structure have not been documented in the literature yet. It is the main purpose of this paper
to show that the theory of empirical risk minimization can be extended to situations where statistical learning is based on survey samples and knowledge of the related (first order) inclusion
probabilities. Precisely, we prove that minimizing a (possibly biased) weighted version of the
empirical risk, refered to as the (approximate) Horvitz-Thompson risk (HT risk), over a class
of controlled complexity lead to a rate for the excess risk of the order OP ((κN (log N)/n)1/2 )
with κN = (n/N)/ mini≤N πi , when data are sampled by means of a rejective scheme of (deterministic) size n within a statistical population of cardinality N ≥ n, a generalization of basic
sampling without replacement with unequal probability weights πi > 0. Extension to other
sampling schemes are then established by a coupling argument. Beyond theoretical results,
numerical experiments are displayed in order to show the relevance of HT risk minimization
and that ignoring the sampling scheme used to generate the training dataset may completely
jeopardize the learning procedure.

1

Introduction

Whereas statistical learning techniques crucially exploit data that can serve as examples to train
a decision rule, they may also make use of weights individually assigned to the observations, resulting from survey sampling stratification. Such weights could correspond either to true inclusion
probabilities or else to calibrated or post-stratification weights, minimizing some discrepancy under certain margin constraints for the inclusion probabilities. In the context of statistical inference
based on survey data, the asymptotic properties of specific statistics such as Horvitz-Thompson
∗
LTCI,
Télécom
ParisTech,
Université
Paris-Saclay,
75013,
Paris,
France.
{stephan.clemencon,guillaume.papa}@telecom-paristech.fr
†
Université Paris Ouest-Nanterre-La Défense, MODALX, Nanterre, France. patrice.bertail@u-paris10.fr

1

estimators (cf [14]), whose computation involves not only the observations but also the weights,
have been widely investigated: in particular, mean estimation and regression have been the subject
of much attention, refer to [13], [20], [3] for instance, and a comprehensive functional limit theory
for distribution function estimation is progressively documented in the statistical literature, see [8],
[7], [21]. At the same time, the last decades have witnessed a rapid development of the field of
machine-learning. Revitalized by different breakout algorithms (e.g. SVM, boosting methods), its
practice is now supported by a sound probabilistic theory based on recent non asymptotic results
in the study of empirical processes, see [17], [5]. However, most papers dedicated to theoretical
results grounding the Empirical Risk Minimization approach (ERM in short), the main paradigm
of statistical learning, assume that the training of a decision rule is based on a dataset formed of
independent replications of a generic random vector Z, a collection of N ≥ 1 i.i.d. observations
Z1 , . . . , ZN namely. In contrast, few results are available in situations where the training dataset is
generated by a more complex sampling scheme. One may refer to [1] for concentration inequalities
permitting to study the generalization ability of empirical risk minimizers when the training data
are obtained by standard sampling without replacement (SWOR in abbreviated form) or to [24] in
the case where the decision rule is learnt from a path of a weakly dependent stochastic process.
It is the goal of this paper to extend the ERM theory to situations where the training dataset is
generated by means of a more general sampling scheme, with possibly unequal probability weights.
We first consider the case of rejective sampling (sometimes refered to as conditional Poisson sampling), an important generalization of basic SWOR. The rate bound results obtained by means
of properties of so-termed negatively associated random variables in this case are next shown to
extend to a class of more general sampling schemes by a coupling argument. In addition, numerical
experiments have been carried out in order to provide empirical evidence of the approach developed.
They show in particular that statistical accuracy of the ERM approach may go down the drain if
the sampling scheme underlying the training dataset is ignored.
The paper is organized as follows. In section 2, the probabilistic framework of the present
study is described at length and basic results of the probabilistic theory of classification are briefly
recalled, together with some important notions of survey theory. The main theoretical results are
stated in section 3, while illustrative numerical experiments are presented in section 4. Certain
proofs are sketched in the Appendix section, whereas additional technical details are deferred to
the Supplementary Material.

2

Background and Preliminaries

As a first go, we start with recalling key concepts pertaining to the theory of empirical risk minimization in binary classification, the flagship problem in statistical learning. A few notions related
to survey theory are next described, which will be involved in the subsequent analysis. Throughout
the article, the indicator function of any event E is denoted by I{E}, the Dirac mass at any point a
by δa , the power set of any set E by P(E), the cardinality of any finite set A by #A.

2.1

Binary Classification - Empirical Risk Minimization Theory

The binary classification problem is considered as a running example all along the paper. Because
it can be easily formulated, it is undeniably the most documented statistical learning problem in
the literature and certain results extend to more general frameworks (e.g. multiclass classification,

2

regression, ranking). Let (Ω, A, P) be a probability space and (X, Y) a random pair defined on
(Ω, A, P), taking its values in some measurable product space X × {−1, +1}, with common distribution P(dx, dy): the r.v. X models some observation, hopefully useful for predicting the binary label
Y. The distribution P can also be described by the pair (F, η) where F(dx) denotes the marginal
distribution of the input variable X and η(x) = P{Y = +1 | X = x}, x ∈ X , is the posterior distribution. The objective is to build, based on the training dataset at disposal, a measurable mapping
g : X 7→ {−1, +1}, called a classifier, with minimum risk:
def

L(g) = P{g(X) 6= Y}.

(1)

It is well-known folklore in the probabilistic theory of pattern recognition that the Bayes classifier
g∗ (x) = 2I{η(x) ≥ 1/2} − 1 is a solution of the risk minimization problem inf g L(g), where the
infimum is taken over the collection of all classifiers defined on the input space X . The minimum
risk is denoted by L∗ = L(g∗ ). Since the distribution P of the data is unknown, one substitutes the
true risk with its empirical estimate
X
bn (g) = 1
L
I{g(Xi ) 6= Yi },
n
n

(2)

i=1

based on a sample (X1 , Y1 ), . . . , (Xn , Yn ) of independent copies of the generic random pair (X, Y).
The true risk minimization is then replaced by the empirical risk minimization
bn (g),
min L
(3)
g∈G

where the minimum is taken over a class G of classifier candidates, supposed rich enough to include
bn
the naive Bayes classifier (or a reasonable approximation of the latter). Considering a solution g
of (3), a major problem in statistical learning theory is to establish upper confidence bounds on
the excess of risk L(b
gn ) − L∗ in absence of any distributional assumptions and taking into account
the complexity of the class G (e.g. described by geometric or combinatorial features such as the
VC dimension)
P and some measure of accuracy of approximation of P by its empirical counterpart
Pn = (1/n) ni=1 δ(Xi ,Yi ) over the class G. Indeed, one typically bounds the excess of risk of the
empirical risk minimizers as follows


∗
∗
b
L(b
gn ) − L ≤ 2 sup |Ln (g) − L(g)| + inf L(g) − L .
g∈G

g∈G

The second term on the right hand side is referred to as the bias and depends on the richness of
the class G, while the first term, called the stochastic error, is controlled by means of results in
empirical process theory, see [5].
Remark 1. (On risk surrogates) Although its study is of major interest from a theoretical
perspective, the problem (3) is generally NP-hard. For this reason, the cost function I{−Yg(X) > 0}
is replaced in practice by a nonnegative convex cost function φ(Yg(X)), turning empirical risk
minimization to a tractable convex optimization problem. Typical choices include the exponential
cost φ(u) = exp(u) used in boosting algorithms, the hinge loss φ(u) = (1 + u)+ in the case of
support vector machines and the logit cost φ(u) = log(1 + exp(u)) for Neural Networks, see [2]
and the references therein. Extension of the results established in the present paper to such risk
surrogates are straightforward and left to the reader.
In this paper, we consider the situation where the training data used to compute of the empirical
risk (2) is not an i.i.d. sample but the product of a more general sampling plan of fixed size n ≥ 1.
3

2.2

Sampling Schemes and Horvitz-Thompson Estimation

Let N ≥ 1. In the standard superpopulation framework we consider, (X1 , Y1 ), . . . , (XN , YN ) is a
sample of independent copies of (X, Y) observed on a finite population IN := {1, . . . , N}. We call a
survey sample of (possibly random) size n ≤ N of the population IN , any subset s := {i1 , . . . , in(s) } ∈
P(IN ) with cardinality n =: n(s) less that N. A sampling design without replacement is determined
by a conditional probability distribution RN on the set of all possible samples s ∈ P(IN ) given
the original data DN = {(Xi , Yi ) : i ∈ IN }. For any i ∈ {1, . . . , N}, the first order inclusion
probability, πi = PRN {i ∈ S} is the probability that the unit i belongs to a random sample S drawn
from the conditional distribution RN . We set π = (π1 , . . . , πN ). The second order inclusion
probabilities are denoted by πi,j = PRN {(i, j) ∈ S2 }, for any i 6= j in {1, . . . , N}2 . The information
related to the observed sample S ⊂ {1, . . . , N} is fully enclosed in the r.v. N = (1 , . . . , N ),
where i = I{i ∈ S} for 1 ≤ i ≤ N. The 1-d marginal conditional distributions of the sampling
scheme N given DN are the Bernoulli distributions B(πi ) = πi δ1 + (1 − πi )δ0 , 1 ≤ i ≤ N, and the
covariance matrix ΓN of the r.v. N has entries given by ΓN (i, j) = πi,j − πi πj ,P
with πi,i = πi by
convention, for 1 ≤ i, j ≤ N. Observe that, equipped with the notations above, 1≤i≤N i = n(S).
One may refer to [10] for accounts of survey sampling techniques. Notice also that, in many
applications, the inclusion probabilities are built using some extra information, typically by means
of auxiliary random variables W1 , . . . , WN defined onP(Ω, A, P) and taking their values in some
measurable
space W: ∀i ∈ {1, . . . , N}, πi = nh(Wi )/ 1≤j≤N h(Wj ), where n max1≤i≤n h(Wi ) ≤
P
h(W
i ) almost-surely and h : W →]0, +∞[ is a measurable link function. The (Xi , Yi , Wi )’s
1≤i≤N
are generally supposed to be i.i.d. copies of a generic r.v. (X, Y, W). See [22] for more details. For
simplicity, the πi ’s are supposed to be deterministic in the subsequent analysis, which boils down
to carrying out the study conditionally upon the Wi ’s in the example aforementioned.
Horvitz-Thompson risk. As defined
in [14], the Horvitz-Thompson version of the (not
bN (g) = N−1 P
available) empirical risk L
1≤i≤N I{Yi 6= g(Xi )} of any classifier candidate g based on
the sampled data {(Xi , Yi ) : i ∈ S} with S ∼ RN is given by:
1 X i
1 X 1
I{g(Xi ) 6= Yi } =
I {g(Xi ) 6= Yi }
N
πi
N
πi
N

LN (g) =

i∈S

(4)

i=1

with the convention that 0/0 = 0 and where the subscript N = (1 , . . . , N ) denotes the vector
in correspondence with the sample S. Observe that, conditionally upon the (Xi , Yi )’s, the quantity
(4), that shall be referred to as the empirical Horvitz-Thompson risk (empirical HT risk in short)
bN (g). Its (pointwise) consisthroughout the paper, is an unbiased estimate of the empirical risk L
tency and asymptotic normality are established in [20] and [3] for a variety of sampling schemes.
This article is devoted to investigating the statistical performance of minimizers ḡN of the HT
risk (4) over the class G under adequate assumptions for the sampling scheme RN used to generate
the training dataset. We point out that such an analysis is far from straightforward due to the
possible depence structure of the terms involved in the summation (4): except in the Poisson case
(recalled below), concentration results for empirical processes cannot be directly applied to control
maximal deviations of the type
sup |LN (g) − L(g)|.
g∈G

Conditional Poisson sampling. One of the simplest sampling plan is undeniably the Poisson
survey scheme (without replacement), a generalization of Bernoulli sampling originally proposed
4

in [12] for the case of unequal weights: the i ’s are independent and the sampling distribution is
thus entirely determined by the first order inclusion probabilities pN = (p1 , . . . , pN ) ∈]0, 1[N :
Y Y
∀s ∈ P(IN ), PN (s) =
pi
(1 − pi ).
(5)
i∈S

i∈S
/

Observe in addition that the behavior of the quantity (4) can be then investigated by means of
results established for sums of independent random variables. However, the major drawback of this
sampling plan lies in the random nature of the corresponding sample size, impacting
P significantly
the variability of (4). The variance of the Poisson P
sample size is given by dN = N
i=1 pi (1 − pi ),
n
while the conditional variance of (4) is in this case: i=1 ((1 − pi )/pi )I{g(Xi ) 6= Yi }. For this reason,
rejective sampling, a sampling design RN of fixed size n ≤ N, is often preferred in practice. It
generalizes the simple random sampling without replacement (where all samples with cardinality n
are equally likely to be chosen, with probability (N − n)!/n!, all the corresponding first and second
order probabilities being thus equal to n/N and n(n − 1)/(N(N − 1)) respectively). Denoting by
πN = (π1 , . . . , πN ) its first order inclusion probabilities and by Sn = {s ∈ P(IN ) : #s = n} the
subset of all possible samples of size n, it is defined by:
Y Y
∀s ∈ Sn , RN (s) = C
pi
(1 − pi ),
(6)
i∈s

P

Q

i∈s
/

Q

N
where C = 1/ s∈Sn i∈s pi i∈s
/ (1 − pi ) and the vector pN = (p
P1 , . . . , pN ) ∈]0, 1[ yields first
order inclusion probabilities equal to the πi ’s and is such that i≤N pi = n. Under this latter
additional condition, such a vector pN exists and is unique (see [11]) and the related representation
(6) is then said to be canonical 1 . Comparing (6) and (5) reveals that rejective RN sampling of fixed
size n can be viewed as Poisson sampling given that the sample size is equal to n. It is for this
reason that rejective sampling is usually referred to as conditional Poisson sampling. One must
pay attention not to get the πi ’s and the pi ’s mixed up: the latter are the first order inclusion
probabilities of PN , whereas the former are those of its conditional version RN . However they can
be related by means of the results stated in [13] (see Theorem 5.1 therein): ∀i ∈ {1, . . . , N},

πi (1 − pi ) = pi (1 − πi ) × (1 − (π̃ − πi )/d∗N + o(1/d∗N ),

(7)

pi (1 − πi ) = πi (1 − pi ) × (1 − (p̃ − pi )/dN + o(1/dN ),
(8)
PN
PN 2
P
2
∗
where d∗N = N
i=1 πi (1 − πi ) and p̃ = (1/dN )
i=1 (pi ) (1 − pi ).
i=1 πi (1 − πi ), π̃ = (1/dN )
More examples of sampling schemes with fixed size are given in the Supplementary Material.
of survey theory.

3

Main Results

We first consider the case where statistical learning is based on the observation of a sample drawn
by means of a rejective scheme. As shall be seen below, the main argument underlying the results
obtained relies on the fact that the related scheme form a collection of negatively associated (binary)
random variables, a rather tractable type of dependence structure. This property being shared by
1
0
Notice that any vector pN
∈]0, 1[N such that pi /(1 − pi ) = cpi0 /(1 − pi0 ) for all i ∈ {1, . . . , n} for some constant
c > 0 can be used to write a representation of RN of the same type as (6)

5

many other sampling schemes of deterministic size, the same argument can be thus naturally applied
to carry out a similar rate analysis for training data produced by such plans. Extensions of these
results to more general sampling schemes are also considered by means of a coupling technique.

3.1

Horvitz-Thompson Empirical Risk Minimization in the Rejective Case

For clarity, we first recall the definition of negatively associated random variables, see [16].
Definition 1. Let Z1 , . . . , Zn be random variables defined on the same probability space, valued
in a measurable space (E, E). They are said to be negatively associated iff for any pair of disjoint
subsets A1 and A2 of the index set {1, . . . , n}
Cov (f((Zi )i∈A1 ), g((Zj )j∈A2 )) ≤ 0,

(9)

for any real valued measurable functions f : E#A1 → R and g : E#A2 → R that are both increasing
in each variable.
The theorem stated below reveals that any rejective scheme N forms a collection of negatively
associated r.v.’s. The proof is given in the Appendix section.
Theorem 1. Let N ≥ 1 and N = (1 , . . . , N ) be the vector of indicator variables related to a
rejective plan on IN . Then, the binary random variables 1 , . . . , N are negatively associated.
The result above permits to handle the dependence of the terms involved in the summation
(4). It is the key argument for proving the following proposition, which extends results for training
datasets generated by basic sampling without replacement (i.e. in the case of all equal weights:
πi = n/N for i = 1, . . . , N), refer to [1] (see also [23]).
Proposition 1. Suppose that the sampling scheme N is rejective with first order inclusion probabilities πN and that the class G is of finite VC dimension V < +∞. Set κN = (n/N)/ mini≤N πi .
Then, the following assertions hold true.
(i) For any δ ∈ (0, 1), with probability larger than 1 − δ, we have: ∀n ≤ N,
s
2
2
bN (g)| ≤ 2κN log( δ ) + V log(N + 1) + 2κN log( δ ) + V log(N + 1) .
sup |L̄N (g) − L
3n
n
g∈G

(10)

(ii) For any solution ḡN of the minimization problem inf g∈G LN (g) is such that, for any δ ∈ (0, 1),
with probability at least 1 − δ, we have: ∀N ≥ 1,
s
log( δ4 ) + V log(N + 1)
log( δ4 ) + V log(N + 1)
L(ḡN ) − L∗ ≤ 2 2κN
+ 4κN
n
3n
s
r
2 log( δ2 )
V
+C
+2
+ inf L(g) − L∗ .
g∈G
N
N

6

The factor κN involved in the bounds
P above reflects the influence of the sampling scheme
(notice incidentally that κN ≥ 1 since i≤N πi = n). In the SWOR case, i.e. when πi = n/N
for all i ∈ {1, . . . , N}, it is then minimum, equal to 1. More generally, when n = o(N) as
N → +∞, as soon as the weights cannot
p vanish faster than n/N, the rate achieved by minimizers
of the HT risk is of the order OP ( (log N)/n). Many sampling schemes (e.g. Rao-Sampford
sampling, Pareto sampling, Srinivasan sampling) of fixed size are actually described by random
vectors N with negatively associated components, see [6] or [18]. Hence, a rapid examination of
Proposition 1’s proof shows that the bounds stated above immediately extend to these cases. See
the Supplementary Material for more details and references. Before showing how the rate bounds
established can be extended to even more general sampling schemes, a few remarks are in order.
Remark 2. (Complexity assumptions) We point out that the results stated can be established,
essentially by means of the same argument as that developed in the Appendix, under complexity
assumptions of different nature, involving metric entropy conditions for instance (see e.g. [26]).
Such straightforward extensions are left to the reader.
Remark 3. (Model Selection) A slight modification of the argument involved in Proposition
1 straightforwardly leads to bounds on the expected excess risk E[L(ḡN )] − inf g∈G L(g). Following the Structural Risk Minimization principle (see [27]), such VC bounds can be next used as
complexity regularization terms to penalize additively the HT risk (4) and, for a sequence of
model classes Gk with k ≥ 1 of finite VC dimension, select the classifier among the minimizers
{arg ming∈Gk L̄N (g), k ≥ 1}, which has approximately minimal risk. Due to space limitations,
details are left to the reader.
Remark 4. (Biased HT risk) As recalled in the Supplementary Material, the canonical parameters pN are practically used to build a rejective sampling scheme N rather than its vector of first
order inclusion probabilities (π1 , . . . , πN ), whose explicit computation based on the pi ’s is a difficult task, refer to [9] for dedicated algorithms. For thisPreason, one could be naturally tempted to
e (g) = (1/N)
minimize the alternative risk estimate L
N
i≤N (i /pi )I{Yi 6= g(Xi )}. As proved in the
Supplementary Material, refinements of Eq. (7)-(8) show that
X 1
1
e (g) − L̄ (g)| ≤ 1
sup |L
≤ 6NκN /(ndN ),
−
N
N
N
pi πi
g∈G
N

(11)

i=1

e (g) from bound (ii) in Proposition1.
one may directly derive a rate bound for solutions of inf g∈G L
N
√
In particular, the learning rate achieved by ḡN is preserved when 1/ n = O(mini≤N πi ) as N, n →
+∞.

3.2

Extensions to More General Sampling Schemes

We now extend the rate bound analysis carried out in the previous subsection to more complex sampling schemes (described by a random vector ∗N possibly exhibiting a very complex
dependence structure). In order to give an insight into the arguments which the extension is
based on, additional notations are required. In this section, we consider a general sampling
design R∗N with first order inclusion probabilities π∗N = (π∗1 , . . . , π∗N ) described by the vector
∗N = (∗1 , . . . , ∗N ) and investigate the performance of minimizers ḡ∗N of the HT empirical risk
P
∗
∗
L̄∗N (g) = (1/N) N
i=1 (i /πi )I{Yi 6= g(Xi )} over a class G. We also consider a rejective sampling
7

scheme RN described by the r.v. N , with first order inclusion probabilities πN = (π1 , . . . , πN )
defined on the same probability space, as well as the following quantity:
1 X i
I{Yi 6= g(Xi )}
N
π∗i
N

ĽN (g) =

(12)

i=1

for any classifier g. Observe that (12) differs from the HT empirical risk L̄N (g) related to the rejective sampling scheme N in the weights it involves, the π∗i ’s instead of the πi ’s namely. Equipped
with this notation, the excess of risk of the HT empirical risk minimizer can be bounded as follows:
bN (g) − L̄ (g)
bN (g) + 2 sup L
L(ḡ∗N ) − inf L(g) ≤ 2 sup L(g) − L
N
g∈G

g∈G

g∈G

+ 2 sup L̄N (g) − ĽN (g) + 2 sup ĽN (g) − L̄∗N (g) .

(13)

g∈G

g∈G

Whereas the first term on the right hand side of (13) can be classically controlled using VapnikChervonenkis and McDiarmid inequalities (see e.g. [27]), assertion (i) of Proposition 1 provides a
control of the second term. Following in the footsteps of [13], the third term shall be bounded by
means of a coupling argument, i.e. a specific choice of the joint distribution of (∗N , N ) satisfying
the distributional margin constraints, while the second term is controlled by assumptions related
to the closeness between the first order inclusion probabilities π∗N and πN . More precisely, the
assumptions required in the subsequent analysis involve the total variation distance between the
sampling plans RN and R∗N :
def

dTV (RN , R∗N ) =

1
2

X

|RN (s) − R∗N (s)|.

s∈P(IN )

Theorem 2. Suppose that Proposition 1’s assumptions are fulfilled. Set κ∗N = (n/N) mini≤N π∗i
and κN = (n/N)/ mini≤N πi . Then, there exists a universal constant C < +∞ such that we have,
∀N ≥ 1,
r


V log(N + 1)
V log(N + 1)
∗
E L(ḡN ) − inf L(g) ≤ 2 2κN
+ 4κN
g∈G
n
3n
r
V
+C
+ 2(κ∗N + κN )(N/n)dTV (RN , R∗N ),
(14)
N
where the infimum is taken over the set of rejective schemes RN with first order inclusion probabilities πN = (π1 , . . . , πN ).
The proof is given in the Supplementary Material. The rate bound obtained depends on the
minimum error made when approximating the sampling plan by a rejective sampling plan in terms
of total variation distance. In practice, following in the footsteps of [13] or [3], it can be controlled
by exhibiting a specific coupling (∗N , N ). One may refer to [3] for many coupling results of this
nature, in particular when the approximating scheme N is of rejective type.

8

4

Illustrative Numerical Experiments

In this section we display numerical experiments to illustrate the relevance of HT risk minimization.
We first consider the case where g(X) = sign(k(X)T θ + b), where k is some mapping function, T
denotes the transposition operator, θ, b are some parameters. As mentionned in 1, we consider the
hinge loss as a convex surrogate of the 0 − 1 loss and add some l2 regularization term. This leads
to the ”Weighted SVM” formulation below:
min
θ,b

1 X 1
max(0, 1 − Yi (k(Xi )T θ − b)) + λkθk2 .
N
πi
i∈S

We use the gaussian r.b.f kernel and perform cross validation to appropriately choose the value
of λ. We then consider the task of learning classification trees using the CART algorithm. These
classifiers are trained using the scikit-learn library [19] and, we account for the randomness of our
experiments by shuffling our datasets and repeating the experiments 50 times.
We first generate a two class dataset D in R10 of size 20000 by sampling independent observations
from two multivariate normal distribution. A similar dataset Dtest of size 2000 is generated to test
our classifiers. Denoting by Id the identity matrix in Rd , the positive class has mean (0, . . . , 0) and
covariance matrix equal to I10 , the negative class has mean (1, . . . , 1) and covariance matrix equal
e of size 1100 via a rejective sampling scheme applied to D.
to 10 × I10 . We then build a dataset D
Observations from the negative class being more noisy we assign them first order probability equal
to 0.1, and assign first order probability equal to 0.01 to observation from the positive class. To
b of size 1100 by sampling without replacement
allow for a fair comparison, we also build a dataset D
e and D,
b and display the results in Table??.
within D. We then learn the different classifiers on D

e
Weighted SVM on D
e
Unweighted SVM on D
b
SVM on D
e
Weighted CART on D
e
Unweighted CART on D
b
CART on D

Mean

Std Deviation

0.02
0.18
0.04
0.06
0.11
0.08

0.005
0.02
0.005
0.01
0.03
0.01

Table 1: Average over 50 runs of the prediction error on Dtest and its standard deviation.
Overall, taking into accounts the inclusion probability allows to consider a training set of reduced size and therefore reduce the computationnal complexity of the learning procedure without
damaging the quality of the prediction . Similar experiments on real datasets are displayed in the
Supplementary Material for which similar conclusions hold.

5

Conclusion

Most theoretical studies providing a statistical explanation for the success of learning algorithms
based on the ERM paradigm fully ignore the possible impact of the sampling scheme producing
9

the training data and stipulate that observations are independent replications of a generic r.v.
or are uniformly sampled without replacement in a larger dataset. Through the generalizable
example of rejective sampling, this paper shows that such studies can be extended to situations
where training data are obtained by more general sampling schemes and possibly exhibit a complex
dependence structure, provided that related probablity weights are appropriately incorporated in
the risk functional.

Appendix
Proof of Theorem 1
Considering the usual representation of the distribution of (1 , . . . , N ) as the conditional distribution of a sample of independent Bernoulli variables (∗1 , . . . , ∗N ) conditioned upon the event
PN ∗
i=1 i = n (see subsection 2.2), the result is a consequence of Theorem 2.8 in [16].

Bernstein inequality for sums of negatively associated random variables
For simplicity, we first establish the following tail bound for negatively associated random variables,
which extends the usual Bernstein inequality in the i.i.d. setting, see [4]. Proofs of Proposition 1
and Theorem 2 are then deduced from Theorem 1 and Theorem 3 (see Supplementary Material) .
Theorem 3. Let Z1 , . . . , ZN be negatively associated real valued random variables such that
|Zi | ≤ c < +∞ a.s. E[Zi ] = 0 and E[Z2i ] 6 σ2i for 1 ≤ i ≤ N. Then, for all t > 0, we have: ∀N ≥ 1,
 N

!
X
t2
P
Zi ≥ t ≤ exp − 2
PN 2 .
ct
+
2
i=1 σi
3
i=1
Before detailing
observe that a similar bound holds true for the tail probability
P
 the proof,
P
N
N
P
i=1 Zi | ≥ t as well, up to a multiplicative factor 2). Refer also
i=1 Zi ≤ −t (and for P |
to Theorem 4 in [15] for a similar result in a more restrictive setting (i.e. for tail bounds related
to sums of negatively associated r.v.’s).
Proof. The proof starts off with the usual Chernoff method: for all λ > 0,
 N


h PN
i
X
P
Zi ≥ t ≤ exp −tλ + log E et i=1 Zi .

(15)

i=1

Next, observe that, for all t > 0, we have
h Pn
i
h
Pn−1 i
E et i=1 Zi = E etZn et i=1 Zi
h
i h Pn−1 i
≤ E etZn E et i=1 Zi
≤

n
Y

h

tZi

E e

i

,

i=1

using the property (9) combined with a descending recurrence on i. The proof is finished by
plugging (16) into (15), using an adequate control of the log-Laplace transform of the Zi ’s and
10

optimizing finally the resulting bound w.r.t. λ > 0, just like in the proof of the classic Bernstein
inequality, see [4].

Supplementary - Proof of Proposition 1


i
1 PN
bN (g) as sup
−
1
I {g(Xi ) 6= Yi } |
We start off by writing S := supg∈G L̄N (g) − L
|
g∈G N
i=1 πi


and apply Theorem 1 conditionnaly upon DN to the r.v Zi := N1 πii − 1 I {g(Xi ) 6= Yi } . Indeed,
N
the (πi )N
i=1 and (I {g(Xi ) 6= Yi })i=1 being positive real numbers, Theorem 1 altogether with [16]
κN
1
1
1
implies that (Zi )N
i=1 are negatively associated. Since |Zi | 6 N max(1, πi − 1) 6 Nπi 6 n and

E[Z2i ] 6

1−pii
N2 πi

6

κN
nN

we have :
 N
X
P


Zi ≥ t|DN

i=1

nt2
≤ exp − 2
3 κN t + 2κN

!
.

Applying the same method to the r.v (−Zi )N
i=1 and taking the union bound yields :
!
 N

X
nt2
.
P |
Zi | ≥ t|DN ≤ 2 exp − 2
κ
t
+
2κ
N
N
3
i=1
By virtue of Sauer’s lemma, since the class G has finite VC-dimension V, we have by taking expectation w.r.t DN :
!
nt2
V
P {S ≥ t} ≤ 2(N + 1) exp − 2
.
3 κN t + 2κN


nt2
V
so
The high probability bound is then easily deduced by choosing δ = 2(N + 1) exp − 2 κ t+2κ
3 N

N

that :
log( δ2 ) + V log(N + 1)
t−
κN
3n

!

!2
log( δ2 ) + V log(N + 1)
=
κN
3n

2 log( δ2 ) + V log(N + 1)
+
κN
n

leading to the following upperbound :
 s
2κN log( δ2 ) + V log(N + 1)
log( δ2 ) + V log(N + 1)
t6
+ 2
κN .
3n
n
The second claim of Proposition 1 is established using
L(ḡN ) − L∗

≤

bN (g)
inf L(g) − L∗ + 2 sup L(g) − L

g∈G

g∈G

bN (g) − L̄ (g) , (16)
+ 2 sup L
N
g∈G

bN (g) and a union
altogether with classical results on ERM applied to the term supg∈G L(g) − L
bound.
11

Supplementary - Proof of Theorem2
Starting from (13), we only have to derive bounds for the quantities S1 := supg∈G L̄N (g) − ĽN (g)
and S2 := supg∈G ĽN (g) − L̄∗N (g) . Starting with the first one, we have :
1 X
S1 = sup |
i
g∈G N
N



i=1

1
1
−
π∗i
πi



I {g(Xi ) 6= Yi } |

1 X
1
1
i | ∗ − |
N
πi
πi
N

6

i=1

so that taking expectation w.r.t N conditionned upon DN yields :
1 X π∗i − πi
|
|
N
πi
N

E[S1 |DN ] 6

i=1

N1 X
|πi − π∗i |
nN
N

6 κN

i=1

N
6 κN dTV (RN , R∗N ),
n
taking expectation w.r.t DN gives an upperbound on S1 . We now turn to the analysis of S2 which
is very similar :
1 X ∗i − i
I {g(Xi ) 6= Yi } |
N
π∗i
N

S2 = sup |
g∈G

6

1
N

N
X
i=1

i=1

|∗i − i |
.
π∗i

We then take expectation conditionned upon DN and easily obtain
E[S2 |DN ] 6 κ∗N

N
dTV (RN , R∗N )
n

which conclude the proof.

Supplementary - On biased HT risk minimization
Eq. (11) directly results from the following lemma.
Lemma 1. We have, for p0i s such Suppose that dN ≥ 1. We have, for all i ∈ {1, . . . , N},
|1/πi − 1/pi | ≤

6
× (1 − πi )/πi .
dN

12

Proof. The proof follows from the representation (5.14) on p1509 in [13]. Denote by PN a Poisson
sampling distribution on IN with inclusion probabilities p1 , . . . , pN , the canonical parameters of
RN . For all i ∈ {1, . . . , N}, we have:
−1

X
πi 1 − pi 
P(s)
=
pi 1 − πi
s∈P(IN ): i∈IN \{s}

X

×

P(s)

s∈P(IN ): i∈IN \{s}


=

X
X

1 − ph
j∈s (1 − pj ) + (ph − pi )

P

h∈s

−1
PN (s)

s: i∈IN \{s}

×

X

PN (s)

s: i∈IN \{s}

X

P

h∈s

1 − ph

(1
−
p
)
1+
j
j∈s

P(ph −pi )
j∈s (1−pj )



Now recall that for any x ∈] − 1, 1[, we have:
1−x≤

1
≤ 1 − x + x2 .
1+x

It follows that

πi 1 − pi
≤1−
pi 1 − πi

X

−1
P(s)

s: i∈IN \{s}

X

X (1 − ph )(ph − pi )
×
P(s)
P
2
h∈s
s: i∈IN \{s}
j∈s (1 − pj )

−1
X
X
X (1 − ph )(ph − pi )2
+
P(s)
P(s)
P
3
h∈s
(1
−
p
)
s: i∈IN \{s}
s: i∈IN \{s}
j
j∈s
P
Following now line by line the proof on p. 1510 in [13] and noticing that j∈s (1 − pj ) ≥ 1/2dN
(see Lemma 2.2 in [13]), we have
X (1 − ph )(ph − pi )
1
2
≤
P
2 ≤ P
d
N
h∈s
j∈s (1 − pj )
j∈s (1 − pj )
and similarly
X (1 − ph )(ph − pi )2
1
4
P
3 ≤ P
2 ≤ 2 .
dN
h∈s
j∈s (1 − pj )
j∈s (1 − pj )
This yieds: ∀i ∈ {1, . . . , N},
1−

2
πi 1 − pi
2
4
≤
≤1+
+
dN
pi 1 − πi
dN d2N
13

and
pi (1 − πi )(1 −

2
2
4
) ≤ πi (1 − pi ) ≤ pi (1 − πi )(1 +
+ 2 ),
dN
dN dN

leading then to
−

2
2
4
(1 − πi )pi ≤ πi − pi ≤ pi (1 − πi )(
+
)
dN
dN d2N

and finally to
−

(1 − πi ) 2
1
1
(1 − πi ) 2
4
≤
−
≤
(
+ 2 ).
πi
dN
pi πi
πi
dN dN

Since 1/d2N ≤ 1/dN as soon as dN ≥ 1, the lemma is proved.

Supplementary - Further details on the rejective scheme
Let n ≤ N and consider a vector π = (π1 , . . . , πN ) of first order inclusion probabilities. Further
define Sn := {s ∈ P(IN ) : #s = n}, the set of all samples in population IN with cardinality n.
The rejective sampling [13, 3], sometimes called conditional Poisson sampling, exponential design
without replacement or maximum entropy design, is the sampling design RP
N that selects samples
of fixed size n(s) = n so as to maximize the entropy measure H(RN ) = − s∈Sn RN (s) log RN (s),
subject to the constraint that its vector of first order inclusion probabilities coincides with π. It is
easily implemented in two steps:
1. Draw a sample S according to a Poisson plan PN , with properly chosen firstPorder inclusion
probabilities pN = (p1 , . . . , pN ). The representation is called canonical if N
i=1 pi = n. In
that case, relationships between each pi and πi , 1 ≤ i ≤ N, are established in [13].
2. If n(S) 6= n, then reject sample S and go back to step one, otherwise stop.
Vector p must be chosen in a way that the resulting first order inclusion probabilities coincide with
π, by means of a dedicated optimization algorithm [25]. The corresponding probability distribution
Q
Q
PN (s) I{#s=n}
is given for all s ∈ P(IN ) by RN (s) = P
pi i∈s
0) ∝
i∈s
/ (1 − pi ) × I{#s = n}, where ∝
P
(s
0
N
s ∈Sn
denotes the proportionality.

Supplementary - Stratified sampling
A stratified sampling design permits to draw a sample S of fixed size n(S) = n ≤ N within a
population IN that can be partitioned into K ≥ 1 distinct strata IN1 , . . . , INK (known a priori)
of respective sizes N1 , . . . , NK adding up to N. Let n1 , . . . , nK be non-negative integers such that
n1 + · · · + nK = n, then the drawing procedure is implemented in K steps: within each stratum
INk , k ∈ {1, . . . , K}, perform a SWOR of size nk ≤ Nk yielding a sample Sk . The final sample
S
is obtained by assembling these sub-samples: S = Kk=1 Sk . The probability of drawing a specific
 −1
PK
Nk
str
sample s by means of this survey design is RN (s) = k=1
. Naturally, first and second
nk
order inclusion
depend on the stratum
which each unit belong: for all i 6= j in UN ,
PK to
PK probabilities
nk (nk −1)
nk
str
2 }.
str
πi (RN ) = k=1 Nk I{i ∈ UNk } and πi,j (RN ) = k=1 Nk (Nk −1) I{(i, j) ∈ UN
k
14

Supplementary - Rao-Sampford sampling
The Rao-Sampford sampling design generates samples s ∈ P(IN ) of fixed size n(s) = n with
RS
respect to some given first order inclusion probabilities πRS := (πRS
1 , . . . , πN ), fulfilling the condition
PN RS
i=1 πi = n, with probability
RRS
N (s) = η

X

πRS
i

i∈s

Y

πRS
j

j∈s
/

1 − πRS
j

.

P
Here, η > 0 is chosen such that s∈P(IN ) RRS
N (s) = 1. In practice, the following algorithm is often
used to implement such a design [3]:
1. select the first unit i with probability πRS
i /n,
RS
2. select the remaining n − 1 units j with drawing probabilities proportional to πRS
j /(1 − πj ),
j = 1, . . . , N,

3. accept the sample if the units drawn are all distinct, otherwise reject it and go back to step
one.

Additional experiments
We consider the following datasets which were obtained via a stratified sampling design. We point
out that this sampling scheme involves negatively associated (binary) random variables so that the
theoretical results obtained in the rejective case extend to this scheme.

incaIndiv
GJB
privacy3
privacy4

N

Number of features

4079
2001
316
301

326
130
95
124

The dataset incaIndiv 2 contain informations on the food consumption of the french population.
The dataset GJB 3 contains questions about job seeking and the internet, workforce automation,
online dating and smartphone use among Americans. The datasets privacy3 4 and privacy4 5 contain
questions about privacy and information sharing. On the datasets incaIndiv and incaCompl we try
to predict whether or not someone is an adult, on the dataset GJB we will try to learn to predict
the gender, and on the datasets privacy3 and privacy4 we will predict an answer to some questions
among 5 possibilities.
We perform our experiments by randomly splitting the datasets incaIndiv, incaCompl,GJB into
a training set (roughly 70 percent of the initial dataset) and a test set. The size of privacy3 and
privacy4 being much smaller we perform 10-fold cross-validation.
2

https://https://www.data.gouv.fr/fr/datasets/
http://www.pewinternet.org/datasets/june-10-july-12-2015-gaming-jobs-and-broadband/
4
http://www.pewinternet.org/datasets/nov-26-2014-jan-3-2015-privacy-panel-3/
5
http://www.pewinternet.org/datasets/jan-27-feb-16-2015-privacy-panel-4/
3

15

Weighted SVM
Unweighted SVM
Weighted CART
Unweighted CART

incaIndiv

GJB

privacy3

privacy4

0.16
0.19
0.04
0.05

0.36
0.43
0.41
0.43

0.46
0.50
0.49
0.52

0.48
0.52
0.54
0.57

Table 2: Average over 50 runs of the prediction error

References
[1] R Bardenet and O.A. Maillard. Concentration inequalities for sampling without replacement.
Bernoulli, 21(3):1361–1385, 2015.
[2] P. Bartlett, M. Jordan, and J. McAuliffe. Convexity, classification and risk bounds. J. of the
A.M.S, 101(473):138–156, 2006.
[3] Y.G. Berger. Rate of convergence to normal distribution for the Horvitz-Thompson estimator.
J. Stat. Plan. Inf, 67(2):209–226, 1998.
[4] S. N. Bernstein. On a modification of chebyshev’s inequality and on the error in laplace
formula. Collected Works, Izd-vo ’Nauka’, Moscow (in Russian), 4:71–80, 1964.
[5] S. Boucheron, O. Bousquet, and G. Lugosi. Theory of Classification: A Survey of Some Recent
Advances. ESAIM: Probability and Statistics, 9:323–375, 2005.
[6] P. Brändén and J. Jonasson. Negative dependence in sampling. Scandinavian Journal of
Statistics, 39(4):830–838, 2012.
[7] N.E. Breslow, T. Lumley, C. Ballantyne, L. Chambless, and M. Kulich. Improved HorvitzThompson estimation of model parameters from two-phase stratified samples: applications in
epidemiology. Stat. Biosc., 1:32–49, 2009.
[8] N.E. Breslow and J.A. Wellner. Weighted likelihood for semiparametric models and two-phase
stratified samples, with application to Cox regression. Scandinavian Journal of Statistics,
35:186–192, 2007.
[9] X.H. Chen, Dempster A.P., and J.S. Liu. Weighted finite population sampling to maximize
entropy. Biometrika, 81(3):457–469, 1994.
[10] J.C. Deville. Réplications d’échantillons, demi-échantillons, Jackknife, bootstrap dans les
sondages. Economica, Ed. Droesbeke, Tassi, Fichet, 1987.
[11] J. Dupacova. A note on rejective sampling. Contribution to Statistics (J. Hajek memorial
volume) Academia Prague, pages 71–78, 1979.
[12] L.A. Goodman. On the estimation of the number of classes in a population. Annals of
Mathematical Statistics, 20:572–579, 1949.

16

[13] J. Hajek. Asymptotic theory of rejective sampling with varying probabilities from a finite
population. The Annals of Mathematical Statistics, 35(4):1491–1523, 1964.
[14] D.G. Horvitz and D.J. Thompson. A generalization of sampling without replacement from a
finite universe. JASA, 47:663–685, 1951.
[15] S. Janson. Large deviation inequalities for sums of indicator variables. 1994.
[16] K. Joag-Dev and F. Proschan. Negative Association of Random Variables with Applications.
The Annals of Statistics, 11(1):286–295, 1983.
[17] V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization
(with discussion). The Annals of Statistics, 34:2593–2706, 2006.
[18] J.B. Kramer, J. Cutler, and A.J. Radcliffe. Negative dependence and srinivasan’s sampling
process. Combinatorics, Probability and Computing, 20(3):347–361, 2011.
[19] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,
P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher,
M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine
Learning Research, 12:2825–2830, 2011.
[20] P.M. Robinson. On the convergence of the Horvitz-Thompson estimator. Australian Journal
of Statistics, 24(2):234–238, 1982.
[21] T. Saegusa and J.A. Wellner. Weighted likelihood estimation under two-phase sampling. 2011.
[22] C.E. Särndall and J. Wretman B. Swensson. Model assisted survey sampling. Springer-Verlag,
NY, 2003.
[23] R.J. Serfling. Probability inequalities for the sum in sampling without replacement. The
Annals of Statistics, 2:39–48, 1974.
[24] I. Steinwart, D. Hush, and C. Scovel. Learning from dependent observations. Journal of
Multivariate Analysis, 100(1):175–194, 2009.
[25] Y. Tillé. Sampling algorithms. Springer Series in Statistics, 2006.
[26] A.W. van der Vaart and J.A. Wellner. Weak convergence and empirical processes. Springer,
1996.
[27] V. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, New-York, 2001.

17

