Model Selection and Error Estimation.
We study model selection strategies based on penalized empirical loss minimization. We point out a tight relationship between error estimation and data-based complexity penalization: any good error estimate may be converted into a data-based penalty function and the performance of the estimate is governed by the quality of the error estimate. We consider several penalty functions, involving error estimates on independent test data, empirical VC dimension, empirical VC entropy, and margin-based quantities. We also consider the maximal difference between the error on the first half of the training data and the second half, and the expected maximal discrepancy, a closely related capacity estimate that can be calculated by Monte Carlo integration. Maximal discrepancy penalty functions are appealing for pattern classification problems, since their computation is equivalent to empirical risk minimization over the training data with some labels flipped.
Introduction
We consider the following prediction problem. Based on a random observation
one has to estimate Y 2 Y. A prediction rule is a measurable
is a bounded loss function. The data
consist of a sequence of independent, identically distributed samples with
the same distribution as (X; Y ) and D n is independent of (X; Y ). The goal
is to choose a prediction rule f n from some restricted class F such that the
loss L(f is as close as possible to the best possible
loss, the inmum is taken over all prediction rules
Empirical risk minimization evaluates the performance of each prediction
rule f 2 F in terms of its empirical loss b L n
provides an estimate whose loss is close to the optimal loss L  if the class F
is (i) su-ciently large so that the loss of the best function in F is close to
L  and (ii) is su-ciently small so that nding the best candidate in F based
on the data is still possible. These two requirements are clearly in con
ict.
The trade-o is best understood by writing
The rst term is often called estimation error, while the second is the approximation
error. Often F is large enough to minimize L() for all possible
distributions of (X; Y ), so that F is too large for empirical risk minimiza-
tion. In this case it is common to x in advance a sequence of smaller model
whose union is equal to F . Given the data D n , one wishes
to select a good model from one of these classes. This is the problem of
model selection.
Denote by b
f k a function in F k having minimal empirical risk. One hopes
to select a model class FK such that the excess error EL(
is close to
min
The idea of structural risk minimization (also known as complexity regular-
ization) is to add a complexity penalty to each of the b
f k )'s to compensate
for the overtting eect. This penalty is usually closely related to a
distribution-free upper bound for sup f2F k
so that the penalty
eliminates the eect of overtting. Thus, structural risk minimization nds
the best trade-o between the approximation error and a distribution-free
upper bound on the estimation error. Unfortunately, distribution-free upper
bounds may be too conservative for specic distributions. This criticism has
led to the idea of using data-dependent penalties.
In the next section, we show that any approximate upper bound on error
(including a data-dependent bound) can be used to dene a (possibly data-
dependent) complexity penalty C n (k) and a model selection algorithm for
which the excess error is close to
min
Section 3 gives several applications of the performance bounds of Section 2:
Section 3.1 considers the estimates provided by an independent test sample.
These have the disadvantage that they cost data. Section 3.2, considers a
distribution-free estimate based on the VC dimension and a data-dependent
estimate based on shatter coe-cients. Unfortunately, these are di-cult to
compute. Section 3.3 brie
y considers margin-based error estimates, which
can be viewed as easily computed estimates of quantities analogous to shatter
coe-cients. Section 3.4 looks at an estimate provided by maximizing the
discrepancy between the error on the rst half of the sample and that on the
second half. For classication, this estimate can be conveniently computed,
simply by minimizing empirical risk with half of the labels
ipped. Section 3.5
looks at a more complex estimate: the expected maximum discrepancy. This
estimate can be calculated by Monte Carlo integration, and can lead to better
performance bounds. In Section 4 we review some concentration inequalities
that are central to our proofs. Finally, in Section 5 we oer an experimental
comparison of some of the proposed methods.
For clarity, we include in Table 1 notation that we use throughout the
paper.
For work on complexity regularization, see Akaike [1], Barron [2],[3] Bar-
ron, Birge, and Massart [4], Barron and Cover [5], Birge and Massart [8],[9],
Buescher and Kumar [11],[12], Devroye, Gyor, and Lugosi, [14], Gallant
[16], Geman and Hwang [17], Kearns, Mansour, Ng, and Ron [20], Krzy_zak
and Linder [23], Lugosi and Nobel [25] Lugosi and Zeger, [27], [26], Mallows
[28], Meir [33], Modha and Masry [34], Rissanen [35], Schwarz [37], Shawe-
Taylor, Bartlett, Williamson, and Anthony [38], Shen and Wong [39], Vapnik
f prediction rule,
sets of prediction rules (model classes)
F union of model classes F k
f
k element of F k with minimal loss
element of F k minimizing empirical loss
prediction rule from F minimizing ~
loss
loss,
minimal loss of functions in F k , L
b L n empirical loss
R n;k estimate (high condence upper bound) of loss L( b
~
penalized loss estimate, ~
L  loss of optimal prediction rule

Table

1: Notation.
[42], Vapnik and Chervonenkis [46], Yang and Barron [50], [51].
Data-dependent penalties are studied by Bartlett [6], Freund [15], Kolt-
chinskii [21], Koltchinskii and Panchenko [22], Lozano [24], Lugosi and Nobel
[25], Massart [30] and Shawe-Taylor, Bartlett, Williamson, and Anthony [38].
Penalization by error estimates
For each class F k , let b
f k denote the prediction rule that is selected from F k
based on the data. Our goal is to select, among these rules, one which has
approximately minimal loss. The key assumption for our analysis is that the
true loss of b
f k can be estimated for all k.
Assumption 1 For every n, there are positive numbers c and m such that
for each k an estimate R n;k on L( b
is available which satises
ce 2m 2
(1)
for all .
Notice that c and m might depend on the sample size n.
Now dene the data-based complexity penalty by
r
log k
The last term is required because of technical reasons that will become apparent
shortly. It is typically small. The dierence R n;k
simply
an estimate of the 'right' amount of penalization L( b
Finally,
dene the prediction rule:
~
where
~
r
log k
The following theorem summarizes the main performance bound for f n .
Theorem 1 Assume that the error estimates R n;k satisfy (1) for some positive
constants c and m. Then for all  > 0,
2ce 2m 2
Moreover, if for all k, b
minimizes the empirical loss in the model class F k ,
then
r
log(ce)
The second part of Theorem 1 shows that the prediction rule minimizing
the penalized empirical loss achieves an almost optimal trade-o between the
approximation error and the expected complexity, provided that the estimate
R n;k on which the complexity is based is an approximate upper bound on the
loss. In particular, if we knew in advance which of the classes F k contained
the optimal prediction rule, we could use the error estimates R n;k to obtain
an upper bound on EL(
, and this upper bound would not improve
on the bound of Theorem 1 by more than O
If the range of the loss function ' is an innite set, the inmum of the
empirical loss might not be achieved. In this case, we could dene b
f k as a
suitably good approximation to the inmum. However, for convenience, we
assume throughout that the minimum always exists. It su-ces for this, and
for various proofs, to assume that for all n and
is closed.
Proof. For brevity, introduce the notation
Then for any  > 0,
sup
(by the union bound)
r
log j
(by denition)
ce 2m
(by Assumption 1)
ce
(since
To prove the second inequality, for each k, we decompose L(f n ) L
k as
~
~
The rst term may be bounded, by standard integration of the tail inequality
shown above (see, e.g., [14, page 208]), as E
~
log(ce)=(2m). Choosing f
k such that L(f
k , the second term may be
bounded directly by
~
(by the denition of ~
minimizes the empirical loss on F k )
where the last step follows from the fact that E
Summing
the obtained bounds for both terms yields that for each k,
log(ce)=(2m);
which implies the second statement of the theorem.
Sometimes bounds tighter than Assumption 1 are available, as in Assumption
below. Such bounds may be exploited to decrease the term
log k=m
in the denition of the complexity penalty.
Assumption 2 For every n, there are positive numbers c and m such that
for each k an estimate R n;k of L( b
is available which satises
ce m (2)
for all .
Dene the modied penalty by
and dene the prediction rule
where
Then by a trivial modication of the proof of Theorem 1 we obtain the
following result.
Theorem 2 Assume that the error estimates R n;k satisfy Assumption 2 for
some positive constants c and m. Then for all  > 0,
Moreover, if for all k, b
minimizes the empirical loss in the model class F k ,
then
log(2ec)
So far we have only concentrated on the expected loss of the penalized
estimate. However, with an easy modication of the proof we obtain exponential
tail inequalities. We work out one such inequality in the scenario of
Theorem 1.
Theorem 3 Assume that the error estimates R n;k satisfy (1) for some positive
constants c and m, and that for all k, b
minimizes the empirical loss
in the model class F k . Then for all  > 0,

r
log k
Proof. Note that

r
log k
~
~

r
log k
sup

~
r
log k
(by the rst inequality of Theorem 1)
r
log k
(by the union bound and the denition of ~
r
log k
minimizes the empirical loss on F k )
e 2n
log k=n
(by Hoeding's inequality)
This concludes the proof.
In the examples shown below we concentrate on the expected loss of penalized
empirical error minimizers. Tail probability estimates may be obtained
in all cases by a simple application of the theorem above.
Applications
3.1 Independent test sample
Assume that m independent sample pairs
are available. We can simply remove m samples from the training data. Of
course, this is not very attractive, but m may be small relative to n. In this
case we can estimate L( b
We apply Hoeding's inequality to show that Assumption 1 is satised with
apply Theorem 1 to give the
following result.
Corollary 1 Assume that the model selection algorithm of Section 2 is performed
with the hold-out error estimate (3). Then
min
r
log k
In other words, the estimate achieves a nearly optimal balance between the
approximation error, and the quantity
which may be regarded as the amount of overtting.
With this inequality we recover the main result of Lugosi and Nobel [25],
but now with a much simpler estimate. In fact, the bound of the corollary
may substantially improve the main result of [25].
The square roots in the bound of Corollary 1 can be removed by increasing
the penalty term by a small constant factor and using Bernstein's inequality
in place of Hoeding's as follows: Choose the modied estimate
R n;k =1
"m
where  < 1 is a positive constant. Then Bernstein's inequality (see, e.g.,
[14]) yields
Thus, (2) is satised with m replaced by 3m(1 )=8. Therefore, dening
we obtain the performance bound
3.2 Estimated complexity
In the remaining examples we consider error estimates R n;k which avoid splitting
the data.
For simplicity, we concentrate in this section on the case of classication
and the 0-1 loss, dened by '(0;
arguments may be carried out for the general
case as well.
Recall the basic Vapnik-Chervonenkis inequality [45], [43],
sup
n) is the empirical shatter coe-cient of F k , that is, the number
of dierent ways the n points can be classied by elements of F k .
It is easy to show that this inequality implies that the estimate
r
log ES k (X 2n
Assumption 1 with We need to estimate the
quantity log ES k (X 2n). The simplest way is to use the fact that ES k (X 2n)
is the vc dimension of F k . Substituting this into Theorem
min
"r
log 4
r
rn
This is the type of distribution-free result we mentioned in the introduction.
A more interesting result involves estimating ES k (X 2n) by S k (X n).
Theorem 4 Assume that the model selection algorithm of Section 2 is used
with
r
min
"r
12E log S k (X n
r
log k
The key ingredient of the proof is a concentration inequality from [10] for
the random vc entropy, log 2 S k (X n).
Proof. We need to check the validity of Assumption 1. It is shown in [10]
that n) satises the conditions of Theorem 9 below.
First note that ES k (X 2n
log ES k (X 2n
log
by the last inequality of Theorem 9. Therefore,
r
3E log S k (X n)
sup
r
log ES k (X 2n
where we used the Vapnik-Chervonenkis inequality (4). It follows that
r
r
3E log S k (X n
"r
12 log S k (X n
r
3E log S k (X n
"r
12 log S k (X n
r
3E log S k (X n
The last term may be bounded using Theorem 9 as follows:
"r
r
3E log S k (X n)
log
expB @ 9
expB @ 9
log 2C A
exp
Summarizing, we have that
Therefore, Assumption 1 is satised with Applying
Theorem 1 nishes the proof.
3.3 Eective VC dimension and margin
In practice it may be di-cult to compute the value of the random shatter
coe-cients S k (X n). An alternative way to assign complexities may be easily
obtained by observing that S k (X n
is the empirical
vc dimension of class F k , that is, the vc dimension restricted to the points
Now it is immediate that the estimate
r
log 4
Assumption 1 in the same way as the estimate of Theorem 4. (In
fact, with a more careful analysis it is possible to get rid of the log n factor
at the price of an increased constant.)
Unfortunately, computing D k in general is still very di-cult. A lot of
eort has been devoted to obtain upper bounds for D k which are simple to
compute. These bounds are handy in our framework, since any upper bound
may immediately be converted into a complexity penalty. In particular,
the margins-based upper bounds on misclassication probability for neural
networks [6], support vector machines [38, 7, 44, 13], and convex combinations
of classiers [36, 29] immediately give complexity penalties and, through
Theorem 1, performance bounds.
We recall here some facts which are at the basis of the theory of support
vector machines, see Bartlett and Shawe-Taylor [7], Cristianini and Shawe-Taylor
[13], Vapnik [44] and the references therein.
A model class F is called a class of (generalized) linear classiers if there
exists a function such that F is the class of linear classiers in
R p , that is, the class of all prediction rules of the form
where w 2 R p is a weight vector satisfying
Much of the theory of support vector machines builds on the fact that
the \eective" vc dimension of those generalized linear classiers for which
the minimal distance of the correctly classied data points to the separating
hyperplane is larger than a certain \margin" may be bounded, independently
of the linear dimension p, by a function of the margin. If for some constant
then we say that the linear classier correctly
classies X i with margin
. We recall the following result:
Lemma 1 (Bartlett and Shawe-Taylor [7]). Let f n be an arbitrary
(possibly data dependent) linear classier of the form
where w n 2 R p is a weight vector satisfying kw
> 0 be
positive random variables and let K  n be a positive integer valued random
variable such that k (X i )k  R for all correctly classies
all but K of the n data points X i with margin
, then for all - > 0,
sn
-:
Assume now that b
f minimizes the empirical loss in a class F of generalized
linear classiers, such that it correctly classies at least n K data points
with margin
, an application of the lemma shows that if we take
sn
then we obtain
f)
sn
r2m
log-
sn
(using the inequality
This inequality shows that if all model classes F k are classes of generalized
linear classiers and for all classes the error estimate R n;k is dened as above,
then condition (1) is satised and Theorem 1 may be used. As a result, we
obtain the following performance bound:
Theorem 5
sn
kk
r
log k
k , and R k are the random variables K;
corresponding
to the class F k .
The importance of this result lies in the fact that it gives a computationally
feasible way of assigning data-dependent penalties to linear classiers.
On the other hand, the estimates R n;k may be much inferior to the estimates
studied in the previous section.
3.4 Penalization by maximal discrepancy
In this section we propose an alternative way of computing the penalties with
improved performance guarantees. The new penalties may be still di-cult to
compute e-ciently, but there is a better chance to obtain good approximate
quantities as they are dened as solutions of an optimization problem.
Assume, for simplicity, that n is even, divide the data into two equal
halves, and dene, for each predictor f , the empirical loss on the two parts
by
and
L (2)
Using the notation of Section 2, dene the error estimate R n;k by
L (2)
and the loss function is the 0-1 loss (i.e., '(0;
and '(0; then the maximum discrepancy,
L (2)
may be computed using the following simple trick: rst
ip the labels of the
rst half of the data, thus obtaining the modied data set
with (X 0
Next nd f k 2 F k which minimizes the empirical loss based on D 0
L (2)
Clearly, the function f k maximizes the discrepancy. Therefore, the same algorithm
that is used to compute the empirical loss minimizer b
may be used
to nd f k and compute the penalty based on maximum discrepancy. This
is appealing: although empirical loss minimization is often computationally
di-cult, the same approximate optimization algorithm can be used for both
nding prediction rules and estimating appropriate penalties. In particular,
if the algorithm only approximately minimizes empirical loss over the class
F k because it minimizes over some proper subset of F k , the theorem is still
applicable.
et al. [47] considered a similar quantity for the case of pattern
classication. Motivated by bounds (similar to (5)) on EL(f n ) b
dened an eective VC dimension, which is obtained by choosing a value
of the VC dimension that gives the best t of the bound to experimental
estimates of EL(f n ) b
They showed that for linear classiers in a
xed dimension with a variety of probability distributions, the t was good.
This suggests a model selection strategy that estimates EL(f n ) using these
bounds. The following theorem justies a more direct approach (using discrepancy
on the training data directly, rather than using discrepancy over a
range of sample sizes to estimate eective VC dimension), and shows that
an independent test sample is not necessary.
A similar estimate was considered in [49], although the error bound presented
in [49, Theorem 3.4] can only be nontrivial when the maximum discrepancy
is negative.
Theorem 6 If the penalties are dened using the maximum-discrepancy error
estimates (6), and
min
L (2)
r
log k
Proof. Once again, we check Assumption 1 and apply Theorem 1. Introduce
the ghost sample (X 0
n ), which is independent of the data and
has the same distribution. Denote the empirical loss based on this sample by
). The proof is based on the simple observation
that for each k,
Thus, for each k,
L (2)
sup
L (2)
sup
L (2)
sup
L (2)
Now, the dierence between the supremum and the maximum satises the
conditions of McDiarmid's inequality (see Theorem 8 below) with c
so this probability is no more than exp( 2 2 n=9). Thus, Assumption 1 is
satised with and the proof is nished.
3.5 A randomized complexity estimator
In this section we introduce an alternative way of estimating the quantity
which may serve as an eective estimate of the
complexity of a model class F . The maximum discrepancy estimate of the
previous section does this by splitting the data into two halves. Here we oer
an alternative which allows us to derive improved performance bounds: we
consider the expectation, over a random split of the data into two sets, of
the maximal discrepancy. Koltchinskii [21] considers a very similar estimate
and proves a bound analogous to Theorem 7 below. We improve this bound
further in Theorem ??.
be a sequence of i.i.d. random variables such that Pf
1and the  i 's are independent of the data D n . Introduce
the quantity
sup
D n
We use M n;k to measure the amount of overtting in class F k . Note that M n;k
is not known, but it may be computed with arbitrary precision by Monte-Carlo
simulation. In the case of pattern classication, each computation in
the integration involves minimizing empirical loss on a sample with randomly
ipped labels. We oer two dierent ways of using these estimates for model
selection. The rst is based on Theorem 1 and the second, with a slight
modication, on Theorem 2. We start with the simpler version:
Theorem 7 Let dene the error estimates R
M n;k , and choose f n by minimizing the penalized error estimates
~
r
log k
then
r
log k
Proof. Introduce a ghost sample as in the proof of Theorem 6, and recall
that by a symmetrization trick of Gine and Zinn [18],
sup
sup
D n
sup
sup
sup
The rest of the proof of Assumption 1 follows easily from concentration in-
equalities: for each k,
sup
sup
sup
(by
where at the last step we used McDiarmid's inequality. (It is easy to verify
that the dierence between the supremum and M n;k satises the condition
of Theorem 8 with c Assumption 1 holds with
Theorem 1 implies the result.
Concentration inequalities
Concentration-of-measure results are central to our analysis. These inequalities
guarantee that certain functions of independent random variables are
close to their mean. Here we recall the three inequalities we used in our
proofs.
Theorem 8 (McDiarmid [31]). Let X independent random
variables taking values in a set A, and assume that f : A n ! R satises
sup
c i
and
McDiarmid's inequality is convenient when f() has variance (
In other situations when the variance of f is much smaller, the following
inequality might be more appropriate.
Theorem 9 (Boucheron, Lugosi, and Massart [10]) Suppose that
are independent random variables taking values in a set A, and
R is such that there exists a function R such that
for all x
Then for any t > 0,
and
Moreover,
log
5 Experimental comparison of empirical penalization
criteria
5.1 The learning problem
In this section we report experimental comparison of some of the proposed
model selection rules in the setup proposed by Kearns, Mansour, Ng, and Ron
[20]. In this toy problem, the X i 's are drawn from the uniform distribution
on the interval [0; 1]. The class F k is dened as the class of all functions
such that for each f 2 F k there exists a partition of [0; 1]
such that f is constant over all these intervals. It is
straightforward to check that the vc-dimension of F k is k+1. Following [20],
we assume that the \target function" f  belongs to F k for some unknown
k and the label Y i of each example X i is obtained by
ipping the value of
denotes the noise level. Then
clearly, for any function g:
What makes this simple learning problem especially convenient for experimental
study is the fact that the computation of the minima of the empirical
loss min f2F k
can be performed in time O(n log n) using
a dynamic programming algorithm described in [20]. Lozano [24] also reports
an experimental comparison of model selection methods for the same
problem.
In this paper we studied several penalized model selection techniques:
a holdout (or cross-validation) method based on independent test sample,
penalization based on the empirical vc entropy, a maximum discrepancy
estimator, and a randomized complexity estimator. For the investigated
learning problem it is easy to see that the empirical vc entropy log 2 S k (X n)
of class F k is almost surely a constant and equal to
and therefore penalization based on the empirical vc entropy is essentially
equivalent to the Guaranteed Risk Minimization (grm) procedure proposed
by Vapnik [44]. Thus, we do not investigate empirically this method. Note
that Lozano [24] compares the grm procedure with a method based on
Rademacher penalties, very similar to our randomized complexity estimator
and nds that Rademacher penalties systematically outperform the grm
procedure.
In [20], grm is compared to the Minimum Description Length principle
and the independent test sample technique which is regarded as a simplied
cross-validation technique. The main message of [20] is that penalization
techniques that only take into account the empirical loss and some structural
properties of the models cannot compete with cross-validation for all
sample sizes. On the contrary, our conclusion (based on experiments) is
that data-based penalties perform favorably compared to penalties based on
independent test data.
In the gures shown below we report experiments for three methods: (1)
the Holdout method (holdout) bases its selection on independent
samples as described in Section 3.1; (2) the Maximum Discrepancy
(md) method selects a model according to the method of Section 3.4 and (3)
Rademacher penalization (rp) performs the randomized complexity method
proposed in Section 3.5. When using Maximum Discrepancy (Section 3.4) in
experiments, the penalties were:2
L (2)
We found that multiplying the penalty dened in Section 3.4 by 1=2 provides
superior performance. When using Randomized Complexity Estimators (Sec-
tion 3.5), the penalties were:
sup
D n
Note that in all experiments, the
log k
or log k
terms were omitted from
penalties. For reasons of comparison, the performance of \oracle selection"
is also shown on the pictures. This method selects a model by minimizing
the true loss L( b
among the empirical loss minimizers b
f k of all classes F k ,
The training error minimization algorithm described in [20] was implemented
using the templates for priority queues and doubly linked lists provided
by the leda library [32].
5.2 Results
The results are illustrated by the gures below. As a general conclusion, we
may observe that the generalization error (i.e., true loss) obtained by methods
mdp and rp are favorable compared to holdout. Even for sample sizes
between 500 and 1000, the data-dependent penalization techniques perform
as well as holdout. The data dependent penalization techniques exhibit
less variance than holdout.
The main message of the paper is that good error estimation procedures
provide good model selection methods. On the other hand, except for the
holdout method, the data-dependent penalization methods do not try to
estimate directly L( b
)). The
gures show that this is accurate when noise level is high and becomes rather
inaccurate when noise level decreases. This is a strong incentive to explore
further data-dependent penalization techniques that take into account the
fact that not all parts of F k are equally eligible for minimizing the empirical
loss.

Acknowledgements

Thanks to Vincent Mirelli and Alex Smola for fruitful conversations, and
thanks to the anonymous reviewers for useful suggestions.



--R

A new look at the statistical model identi
Logically smooth density estimation.
Complexity regularization with application to arti

Minimum complexity density estimation.
The sample complexity of pattern classi
Generalization performance of support vector machines and other pattern classi


A sharp concentration inequality with applications in random combinatorics and learning.
Learning by canonical smooth estima- tion
Learning by canonical smooth estima- tion
An Introduction to Support Vector Machines.

bounding learning algorithms.
Nonlinear Statistical Models.
Nonparametric maximum likelihood estimation by the method of sieves.


An experimental and theoretical comparison of model selection methods.
Rademacher penalties and structural risk minimization.
Rademacher processes and bounding the risk of function learning.
Radial basis function networks and complexity regularization in function learning.
Model selection using Rademacher penalization.
Adaptive model selection using empirical com- plexities
Nonparametric estimation via empirical risk minimization.
Concept learning using complexity regulariza- tion
Some comments on c p
Improved generalization through explicit optimization of margins.
Some applications of concentration inequalities to statis- tics
On the method of bounded di
A Platform for Combinatorial and Geometric Computing.
Performance bounds for nonlinear time series prediction.
Minimum complexity regression estimation with weakly dependent observations.
A universal prior for integers and estimation by minimum description length.
Boosting the margin
Estimating the dimension of a model.
Structural risk minimization over data-dependent hierarchies
Convergence rate of sieve estimates.
On the best constants in the Khintchine inequality.
Concentration of measure and isoperimetric inequalities in product spaces.
Estimation of Dependencies Based on Empirical Data.
The Nature of Statistical Learning Theory.
Statistical Learning Theory.
On the uniform convergence of relative frequencies of events to their probabilities.
Theory of Pattern Recognition.
Measuring the VC-dimension of a learning machine
Weak convergence and empirical processes

An asymptotic property of model selection criteria.

--TR

--CTR
Davide Anguita , Sandro Ridella , Fabio Rivieccio , Rodolfo Zunino, Quantum optimization for training support vector machines, Neural Networks, v.16 n.5-6, p.763-770, June
Clayton D. Scott , Robert D. Nowak, Learning Minimum Volume Sets, The Journal of Machine Learning Research, 7, p.665-704, 12/1/2006
Leila Mohammadi , Sara van de Geer, Asymptotics in Empirical Risk Minimization, The Journal of Machine Learning Research, 6, p.2027-2047, 12/1/2005
Peter L. Bartlett , Shahar Mendelson, Rademacher and gaussian complexities: risk bounds and structural results, The Journal of Machine Learning Research, 3, 3/1/2003
Andrs Antos , Balzs Kgl , Tams Linder , Gbor Lugosi, Data-dependent margin-based generalization bounds for classification, The Journal of Machine Learning Research, 3, p.73-98, 3/1/2003
Joel Ratsaby, Complexity of hyperconcepts, Theoretical Computer Science, v.363 n.1, p.2-10, 25 October 2006
Ron Meir , Tong Zhang, Generalization error bounds for Bayesian mixture algorithms, The Journal of Machine Learning Research, 4, 12/1/2003
Joel Ratsaby, On learning multicategory classification with sample queries, Information and Computation, v.185 n.2, p.298-327, September 15,
Magalie Fromont, Model selection by bootstrap penalization for classification, Machine Learning, v.66 n.2-3, p.165-207, March     2007
Shie Mannor , Ron Meir , Tong Zhang, Greedy algorithms for classificationconsistency, convergence rates, and adaptivity, The Journal of Machine Learning Research, 4, p.713-741, 12/1/2003
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
model selection;empirical penalties;concentration inequalities;penalization