Scale-sensitive dimensions, uniform convergence, and learnability.
Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or agnostic) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.
Introduction
In typical learning problems, the learner is presented with a finite sample of data generated by an
unknown source and has to find, within a given class, the model yielding best predictions on future
data generated by the same source. In a realistic scenario, the information provided by the sample
is incomplete, and therefore the learner might settle for approximating the actual best model in
the class within some given accuracy. If the data source is probabilistic and the hypothesis class
consists of functions, a sample size sufficient for a given accuracy has been shown to be dependent on
different combinatorial notions of "dimension", each measuring, in a certain sense, the complexity
of the learner's hypothesis class.
Whenever the learner is allowed a low degree of accuracy, the complexity of the hypothesis class
might be measured on a coarse "scale" since, in this case, we do not need the full power of the entire
set of models. This position can be related to Rissanen's MDL principle [17], Vapnik's structural
minimization method [22], and Guyon et al.'s notion of effective dimension [11]. Intuitively, the
"dimension" of a class of functions decreases as the coarseness of the scale at which it is measured
increases. Thus, by measuring the complexity at the right "scale" (i.e., proportional to the accuracy)
the sample size sufficient for finding the best model within the given accuracy might dramatically
shrink.
As an example of this philosophy, consider the following scenario. 1 Suppose a meteorologist
is requested to compute a daily prediction of the next day's temperature. His forecast is based
on a set of presumably relevant data, such as the temperature, barometric pressure, and relative
humidity over the past few days. On some special events, such as the day before launching a Space
Shuttle, his prediction should have a high degree of accuracy, and therefore he analyzes a larger
amount of data to finely tune the parameters of his favorite mathematical meteorological model.
On regular days, a smaller precision is tolerated, and thus he can afford to tune the parameters of
the model on a coarser scale, saving data and computational resources.
In this paper we demonstrate quantitatively how the accuracy parameter plays a crucial role in
determining the effective complexity of the learner's hypothesis class. 2
We work within the decision-theoretic extension of the PAC framework, introduced in [12]
and also known as agnostic learning. In this model, a finite sample of pairs (x; y) is obtained
through independent draws from a fixed distribution P over X \Theta [0; 1]. The goal of the learner
is to be able to estimate the conditional expectation of y given x. This quantity is defined by a
called the regression function in statistics. The learner is given a class H
of candidate regression functions, which may or may not include the true regression function f .
This class H is called ffl-learnable if there is a learner with the property that for any distribution
P and corresponding regression function f , given a large enough random sample from P , this
learner can find an ffl-close approximation 3 to f within the class H, or if f is not in H, an ffl-close
approximation to a function in H that best approximates f . (This analysis of learnability is purely
information-theoretic, and does not take into account computational complexity.) Throughout the
1 Adapted from [14].
Our philosophy can be compared to the approach studied in [13], where the range of the functions in the hypothesis
class is discretized in a number of elements proportional to the accuracy. In this case, one is interested in bounding
the complexity of the discretized class through the dimension of the original class. Part of our results builds on this
discretization technique.
3 All notions of approximation are with respect to mean square error.
paper, we assume that H (and later F) satisfies some mild measurability conditions. A suitable
such condition is the "image admissible Suslin" property (see [8, Section 10.3.1, page 101].)
The special case where the distribution P is taken over X \Theta f0; 1g was studied in [14] by Kearns
and Schapire, who called this setting probabilistic concept learning. If we further demand that the
functions in H take only values in f0; 1g, it turns out that this reduces to one of the standard
PAC learning frameworks for learning deterministic concepts. In this case it is well known that the
learnability of H is completely characterized by the finiteness of a simple combinatorial quantity
known as the Vapnik-Chervonenkis (VC) dimension of H [24, 6]. An analogous combinatorial
quantity for the probabilistic concept case was introduced by Kearns and Schapire. We call this
quantity the P fl -dimension of H, where fl ? 0 is a parameter that measures the "scale" to which the
dimension of the class H is measured. They were only able to show that finiteness of this parameter
was necessary for probabilistic concept learning, leaving the converse open. We solve this problem
showing that this condition is also sufficient for learning in the harder agnostic model.
This last result has been recently complemented by Bartlett, Long, and Williamson [4], who
have shown that the P fl -dimension characterizes agnostic learnability with respect to the mean
absolute error. In [20], Simon has independently proven a partial characterization of (nonagnostic)
learnability using a slightly different notion of dimension.
As in the pioneering work of Vapnik and Chervonenkis [24], our analysis of learnability begins
by establishing appropriate uniform laws of large numbers. In our main theorem, we establish the
first combinatorial characterization of those classes of random variables whose means uniformly
converge to their expectations for all distributions. Such classes of random variables have been
called Glivenko-Cantelli classes in the empirical processes literature [9]. Given the usefulness of
related uniform convergence results in combinatorics and randomized algorithms, we feel that this
result may have many applications beyond those we give here. In addition, our results rely on
a combinatorial result that generalizes Sauer's Lemma [18, 19]. This new lemma considerably
extends some previously known results concerning f0; 1; \Lambdag tournament codes [21, 7]. As other
related variants of Sauer's Lemma were proven useful in different areas, such as geometry and
Banach space theory (see, e.g., [15, 1]), we also have hope to apply this result further.
The uniform, distribution-free convergence of empirical means to true expectations for classes of
real-valued functions has been studied by Dudley, Gin'e, Pollard, Talagrand, Vapnik, Zinn, and
others in the area of empirical processes. These results go under the general name of uniform laws
of large numbers. We give a new combinatorial characterization of this phenomenon using methods
related to those pioneered by Vapnik and Chervonenkis.
Let F be a class of functions from a set X into [0; 1]. (All the results presented in this section
can be generalized to classes of functions taking values in any bounded real range.) Let P denote
a probability distribution over X such that f is P -measurable for all f 2 F . By P (f) we denote
the P-mean of f , i.e., its integral w.r.t. P . By P n (f) we denote the random variable 1
are drawn independently at random according to P .
Following Dudley, Gin'e and Zinn [9], we say that F is an ffl-uniform Glivenko-Cantelli class if
lim
sup
Pr
sup
m-n
sup
0: (1)
Here Pr denotes the probability with respect to the points x 1 drawn independently at
random according to P . 4 The supremum is understood with respect to all distributions P over X
(with respect to some suitable oe-algebra of subsets of X ; see [9]).
We say that F satisfies a distribution-free uniform strong law of large numbers, or more briefly,
that F is a uniform Glivenko-Cantelli class, if F is an ffl-uniform Glivenko-Cantelli class for all
We now recall the notion of VC-dimension, which characterizes uniform Glivenko-Cantelli classes
of f0; 1g-valued functions.
Let F be a class of f0; 1g-valued functions on some domain set, X . We say F C-shatters
a set A ' X if, for every E ' A, there exists some f E 2 F satisfying: For every x 2 A n E,
1. Let the V C-dimension of F , denoted V C-dim(F ),
be the maximal cardinality of a set A ' X that is V C-shattered by F . (If F V C-shatters sets of
unbounded finite sizes, then let V
The following was established by Vapnik and Chervonenkis [24] for the "if " part and (in a
stronger version) by Assouad and Dudley [2] (see [9, proposition 11, page 504].)
Theorem 2.1 Let F be a class of functions from X into f0; 1g. Then F is a uniform Glivenko-
Cantelli class if and only if V C-dim(F) is finite.
Several generalizations of the V C-dimension to classes of real-valued functions have been previously
proposed: Let F be a class of [0; 1]-valued functions on some domain set X .
ffl (Pollard [16], see also [12]): We say F P -shatters a set A ' X if there exists a function
R such that, for every E ' A, there exists some f E 2 F satisfying: For every
Let the P-dimension (denoted by P-dim) be the maximal cardinality of a set A ' X that is
-shattered by F . (If F P -shatters sets of unbounded finite sizes, then let
-shatters a set A ' X if there exists a constant ff 2 R such that,
for every E ' A, there exists some f E 2 F satisfying: For every x 2 A n E, f
for every x 2
Let the V -dimension (denoted by V -dim) be the maximal cardinality of a set A ' X that is
-shattered by F . (If F V -shatters sets of unbounded finite sizes, then let V
It is easily verified (see below) that the finiteness of neither of these combinatorial quantities
provides a characterization of uniform Glivenko-Cantelli classes (more precisely, they both provide
only a sufficient condition.)
Kearns and Schapire [14] introduced the following parametrized variant of the P-dimension. Let
F be a class of [0; 1]-valued functions on some domain set X and let fl be a positive real number.
We say F -shatters a set A ' X if there exists a function s : A ! [0; 1] such that for every
Actually Dudley et al. use outer measure here, to avoid some measurability problems in certain cases.
there exists some f E 2 F satisfying: For every x 2 A n E, f E and, for every
Let the P fl -dimension of F , denoted P fl -dim(F ), be the maximal cardinality of a set A ' X that
is P fl -shattered by F . (If F P fl -shatters sets of unbounded finite sizes, then let P
A parametrized version of the V -dimension, which we'll call V fl -dimension, can be defined in
the same way we defined the P fl -dimension from the P-dimension. The first lemma below follows
directly from the definitions. The second lemma is proven through the pigeonhole principle.
Lemma 2.1 For any F and any fl ? 0, P
Lemma 2.2 For any class F of [0; 1]-valued functions and for all fl ? 0,
The P fl and the V fl dimensions have the advantage of being sensitive to the scale at which differences
in function values are considered significant.
Our main result of this section is the following new characterization of uniform Glivenko-Cantelli
classes, which exploits the scale-sensitive quality of the P fl and the V fl dimensions.
Theorem 2.2 Let F be a class of functions from X into [0; 1].
1. There exist constants a; b ? 0 (independent of F) such that for any fl ? 0
(a) If P fl -dim(F) is finite, then F is an (afl)-uniform Glivenko-Cantelli class.
(b) If V fl -dim(F) is finite, then F is a (bfl)-uniform Glivenko-Cantelli class.
(c) If P fl -dim(F) is infinite, then F is not a (fl \Gamma -uniform Glivenko-Cantelli class for any
(d) If V fl -dim(F) is infinite, then F is not a (2fl \Gamma -uniform Glivenko-Cantelli class for
any - ? 0.
2. The following are equivalent:
(a) F is a uniform Glivenko-Cantelli class.
(b) P fl -dim(F) is finite for all fl ? 0.
(c) V fl -dim(F) is finite for all fl ? 0.
(In the proof we actually show that a - 24 and b - 48, however these values are likely to be
improved through a more careful analysis.)
The proof of this theorem is deferred to the next section. Note however that part 1 trivially
implies part 2.
The following simple example (a special case of [9, Example 4, page 508], adapted to our pur-
poses) shows that the finiteness of neither P-dim nor V -dim yields a characterization of Glivenko-
Cantelli classes. (Throughout the paper we use ln to denote the natural logarithm and log to denote
the logarithm in base 2.)
Example 2.1 Let F be the class of all [0; 1]-valued functions f defined on the positive integers
and such that f(x) - e \Gammax for all x 2 N and all f 2 F . Observe that, for all
. Therefore, F is a uniform Glivenko-Cantelli class by Theorem 2.2. On the
other hand, it is not hard to show that the P-dimension and the V -dimension of F are both infinite.
Theorem 2.2 provides the first characterization of Glivenko-Cantelli classes in terms of a simple
combinatorial quantity generalizing the Vapnik-Chervonenkis dimension to real-valued functions.
Our results extend previous work by Dudley, Gin'e, and Zinn, where an equivalent characterization
is shown to depend on the asymptotic properties of the metric entropy. Before stating the metric-
entropy characterization of Glivenko-Cantelli classes we recall some basic notions from the theory
of metric spaces.
Let (X; d) be a (pseudo) metric space, let A be a subset of X and ffl ? 0.
ffl A set B ' A is an ffl-cover for A if, for every a 2 A, there exists some b 2 B such that
ffl. The ffl-covering number of A, N d (ffl; A), is the minimal cardinality of an ffl-cover for
A (if there is no such finite cover then it is defined to be 1).
ffl A set A ' X is ffl-separated if, for any distinct a; b 2 A, ffl. The ffl-packing number of
A, M d (ffl; A), is the maximal size of an ffl-separated subset of A.
The following is a simple, well-known fact.
Lemma 2.3 For every (pseudo) metric space (X; d), every A ' X, and ffl ? 0
For a sequence of n points x class F of real-valued functions defined on
xn (f; g) denote the l 1 distance between f; g 2 F on the points x n , that is
l 1
xn
1-i-n
As we will often use the l 1
xn distance, let us introduce the notation N (ffl; F ; x n ) and M(ffl; F ; x n )
to stand for, respectively, the ffl-covering and the ffl-packing number of F with respect to l 1
xn .
A notion of metric entropy H n , defined by
log N (ffl; F ; x n );
has been used by Dudley, Gin'e and Zinn to prove the following.
Theorem 2.3 ([9, Theorem 6, page 500]) Let F be a class of functions from X into [0; 1].
Then
1. F is a uniform Glivenko-Cantelli class if and only if lim n!1 H n (ffl;
2. For all ffl ? 0, if lim n!1 H n (ffl; is an (8ffl)-uniform Glivenko-Cantelli class.
The results by Dudley et al. also give similar characterizations using l p norms in place of the l 1
norm.
Related results were proved earlier by Vapnik and Chervonenkis [24, 25]. In particular, they
proved an analogue of Theorem 2.3, where the convergence of means to expectations is characterized
for a single distribution P . Their characterization is based on H n (ffl; F) averaged with respect to
samples drawn from P .
3 Proof of the main theorem
We wish to obtain a characterization of uniform Glivenko-Cantelli classes in terms of their P
dimension. By using standard techniques, we just need to bound the fl-packing numbers of sets of
real-valued functions by an appropriate function of their P cfl -dimension, for some positive constant
c. Our line of attack is to reduce the problem to an analogous problem in the realm of finite-
valued functions. Classes of functions into a discrete and finite range can then be analyzed using
combinatorial tools.
We shall first introduce the discrete counterparts of the definitions above. Our next step will
be to show how the real-valued problem can be reduced to a combinatorial problem. The final, and
most technical part of our proof, will be the analysis of the combinatorial problem through a new
generalization of Sauer's Lemma.
Let X be any set and let bg. We consider classes F of functions f from X to B.
Two such functions f and g are separated if they are 2-separated in the l 1 metric, i.e., if there
exists some x 2 X such that 2. The class F is pairwise separated if f and g are
separated for all f 6= g in F .
F strongly shatters a set A ' X if A is nonempty and there exists a function s
that, for every E ' A, there exists some f E 2 F satisfying: For every x 2 A n E, f E
and, for every x 2 E, f E (x) - s(x)+ 1. If s is any function witnessing the shattering of A by F , we
shall also say that F strongly shatters A according to s. Let the strong dimension of F , S-dim(F ),
be the maximal cardinality of a set A ' X that is strongly shattered by F . (If F strongly shatters
sets of unbounded finite size, then let
For a function f and a real number ae ? 0, the ae-discretization of f , denoted
by f ae , is the function f ae (x) def
ae c, i.e. f ae f(x)g. For a class F of
nonnegative real-valued functions let
Fg.
We need the following lemma.
Lemma 3.1 For any class F of [0; 1]-valued functions on a set X and for any ae ? 0,
1. for every
2. for every ffl - 2ae and every x
Proof. To prove part 1 we show that any set strongly shattered by F ae is also P ae=2 -shattered by
F . If A ' X is strongly shattered by F ae , then there exists a function s such that for every E ' A
there exists some f (E) 2 F satisfying: for every x 2 A n E, f ae
and for every x 2 E,
Assume first f ae
holds and, by definition of f ae
we have f (E)
by definition of f ae
, we have f (E) (x) - aef ae
(x), which implies
f (E) (x) - ae \Delta s(x)+ae. Thus A is P ae=2 -shattered by F , as can be seen using the function s
defined by s
To prove part 2 of the lemma it is enough to observe that, by the definition of F ae , for all
f; 2. 2
We now prove our main combinatorial result which gives a new generalization of Sauer's Lemma.
Our result extends some previous work concerning f0; 1; \Lambdag tournament codes, proven in a completely
different way (see [21, 7]).
The lemma concerns the l 1 packing numbers of classes of functions into a finite range. It
shows that, if such a class has a finite strong dimension, then its 2-packing number is bounded
by a subexponential function of the cardinality of its domain. For simplicity, we arbitrarily fix a
sequence x n of n points in X and consider only the restriction of F to this domain, dropping the
subscript x n from our notation.
Lemma 3.2 If F is a class of functions from a finite domain X of cardinality n to a finite range,
Note that for fixed d the bound in Lemma 3.2 is n O(log n) even if b is not a constant but a polynomial
in n.
Proof of Lemma 3.2. Fix b - 3 (the case b ! 3 is trivial.) Let us say that a class F as
above strongly shatters a pair (A; s) (for a nonempty subset A of X and a function s
if F strongly shatters A according to s. For all integers h - 2 and n - 1, let t(h; n) denote the
maximum number t such that for every set F of h pairwise separated functions f from X to B, F
strongly shatters at least t pairs (A; s) where A ' X , A 6= ;, and s : A ! B. If no such F exists,
then t(h; n) is infinite.
Note that the number of possible pairs (A; s) for which the cardinality of A does not exceed
(as for A of size i ? 0 there are strictly less than b i possibilities to
choose s.) It follows that, if t(h; n) - y for some h, then M l 1(2; F) ! h for all sets F of functions
from X to B and such that S-dim(F) - d. Therefore, to finish the proof, it suffices to show that
We claim that t(2;
2. The first part of the claim is readily verified. For the second part, first note that if no
set of 2mnb 2 pairwise separated functions from X to B exists, then t(2mnb
the claim holds. Assume then that there is a set F of 2mnb 2 pairwise separated functions from
X to B. Split it arbitrarily into mnb 2 pairs. For each pair (f; g) find a coordinate x 2 X where
1. By the pigeonhole principle, the same coordinate x is picked for at least mb 2
pairs. Again by the pigeonhole principle, there are at least mb
? 2m of these pairs (f; g) for
which the (unordered) set ff(x); g(x)g is the same. This means that there are two sub-classes of
F , call them F 1 and F 2 , and there are x 2 X and so that for each
for each g 2 F 2 Obviously, the members of
F 1 are pairwise separated on X n fxg and the same holds for the members of F 2 . Hence, by the
definition of the function t, F 1 strongly shatters at least t(2m;
and the same holds for F 2 . Clearly F strongly shatters all pairs strongly shattered by F 1 or F 2 .
Moreover, if the same pair (A; s) is strongly shattered both by F 1 and by F 2 , then F also strongly
shatters the pair It follows that
establishing the claim.
Now suppose n ? r - 1. Let repeated application
of the above claim, it follows that t(h; n) - 2 r . Since t is clearly monotone in its first argument,
and h, this implies t(2(nb 2
. However, since the total number of functions from
to B is b n , there are no sets of pairwise separated functions of size larger than this, and hence
y in this case. On the other hand, when the
result above yields t(2(nb 2 y. Thus in either case y,
completing the proof. 2
Before proving Theorem 2.2, we need two more lemmas. The first one is a straightforward adaptation
of [22, Section A.6, p. 223].
Lemma 3.3 Let F be a class of functions from X into [0; 1] and let P be a distribution over X.
Then, for all ffl ? 0 and all n - 2=ffl 2 ,
Pr
sup
\Theta N (ffl=6; F ; x 0
where Pr denotes the probability w.r.t. the sample x drawn independently at random according
to P , and E the expectation w.r.t. a second sample x 0
2n also drawn independently
at random according to P .
Proof. A well-known result (see e.g. [8, Lemma 11.1.5] or [10, Lemma 2.5]) shows that, for all
Pr
sup
sup
ffl)
where
We combine this with a result by Vapnik [22, pp. 225-228] showing that for all ffl ? 0
Pr
sup
\Theta N (ffl=3; F ; x 0

This concludes the proof. 2
The next result applies Lemma 3.2 to bound the expected covering number of a class F in terms
of P fl -dim(F ).
Lemma 3.4 Let F be a class of functions from X into [0; 1] and P a distribution over X. Choose
where the expectation E is taken w.r.t. a sample x drawn independently at random according
to P .
Proof. By Lemma 2.3, Lemmas 3.1 and 3.2, and Stirling's approximation,
xn
xn
xn
We are now ready to prove our characterization of uniform Glivenko-Cantelli classes.
Proof of Theorem 2.2. We begin with part 1.d: If V fl
show that F is not a (2fl \Gamma -uniform Glivenko-Cantelli class for any - ? 0. To see this, assume
1. For any sample size n and any d ? n, find in X a set S of d points that are
-shattered by F . Then there exists ff ? 0 such that for every E ' S there exists some f E 2 F
satisfying: For every x 2 A n E, f E
the uniform distribution on S. For any sample x there is a function f 2 F
such that f(x i g. Thus, for any
large enough we can find some f 2 F such that jP This
proves part 1.d. Part 1.c follows from Lemma 2.2.
To prove part 1.a we use inequality (2) from Lemma 3.3. Then, to bound the expected covering
number we apply Lemma 3.4. This shows that
lim
sup
Pr
sup
for some a ? 0 whenever P fl -dim(F) is finite.
Equation (4) shows that P n (f) ! P (f) in probability for all f 2 F and all distributions P .
Furthermore, as Lemma 3.3 and Lemma 3.4 imply that
1, one may apply the Borel-Cantelli lemma and strengthen (4) to almost sure convergence, i.e.
lim
sup
Pr
sup
m-n
sup
0:
This completes the proof of part 1.a. The proof of part 1.b follows immediately from Lemma 2.2.The proof of Theorem 2.2, in addition to being simpler than the proof in [9] (see Theorem 2.3
in this paper), also provides new insights into the behaviour of the metric entropy used in that
characterization. It shows that there is a large gap in the growth rate of the metric entropy
either F is a uniform Glivenko-Cantelli class, and hence, by (3) and by definition of H n ,
for or F is not a uniform Glivenko-Cantelli class, and hence there
exists ffl ? 0 such that P ffl which is easily seen to imply that H n (ffl; n). It is
unknown if log 2 n can be replaced by log ff n where 1 - ff ! 2.
From the proof of Theorem 2.2 we can obtain bounds on the sample size sufficient to guarantee
that, with high probability, in a class of [0; 1]-valued random variables each mean is close to its
expectation.
Theorem 3.1 Let F be a class of functions from X into [0; 1]. Then for all distributions P over
X and all ffl;
Pr
sup
for
where d is the P ffl=24 -dimension of F .
Theorem 3.1 is proven by applying Lemma 3.3 and Lemma 3.4 along with standard approximations.
We omit the proof of this theorem and mention instead that an improved sample size bound has
been shown by Bartlett and Long [3, Equation (5), Theorem 9]. In particular, they show that if
the P (1=4\Gamma- )ffl -dimension d 0 of F is finite for some - ? 0, then a sample size of order
O
is sufficient for (5) to hold.
4 Applications to Learning
In this section we define the notion of learnability up to accuracy ffl, or ffl-learnability, of statistical
regression functions. In this model, originally introduced in [12] and also known as "agnostic
learning", the learning task is to approximate the regression function of an unknown distribution.
The probabilistic concept learning of Kearns and Schapire [14] and the real-valued function learning
with noise investigated by Bartlett, Long, and Williamson [4] are special cases of this framework.
We show that a class of functions is ffl-learnable whenever its P affl -dimension is finite for some
constant a ? 0. Moreover, combining this result with those of Kearns and Schapire, who show
that a similar condition is necessary for the weaker probabilistic concept learning, we can conclude
that the finiteness of the P fl -dimension for all fl ? 0 characterizes learnability in the probabilistic
concept framework. This solves an open problem from [14].
Let us begin by briefly introducing our learning model. The model examines learning problems
involving statistical regression on [0; 1]-valued data. Assume X is an arbitrary set (as above), and
be an unknown distribution on Z. Let X and Y be random
variables respectively distributed according to the marginal of P on X and Y . The regression
function f for distribution P is defined, for all x 2 X , by
The general goal of regression is to approximate f in the mean square sense (i.e. in L 2 -norm) when
the distribution P is unknown, but we are given z
independently generated from the distribution P .
In general we cannot hope to approximate the regression function f for an arbitrary distribution
. Therefore we choose a hypothesis space H, which is a family of mappings
settle for a function in H that is close to the best approximation to f in the hypothesis space
H. To this end, for each hypothesis h 2 H, let the function defined by:
is the mean square loss of h. The
goal of learning in the present context is to find a function b h 2 H such that
for some given accuracy ffl ? 0. It is easily verified that if inf h2H P (' h ) is achieved by some h 2 H,
then h is the function in H closest to the true regression function f in the L 2 norm.
A learning procedure is a mapping A from finite sequences in Z to H. A learning procedure
produces a hypothesis b training sample z n . For given accuracy parameter ffl, we
say that H is ffl-learnable if there exists a learning procedure A such that
lim
sup
Pr
ae
oe
0: (7)
Here Pr denotes the probability with respect to the random sample z n 2 Z n , each z i drawn
independently according to P , and the supremum is over all distributions P defined on a suitable
oe-algebra of subsets of Z. Thus H is ffl-learnable if, given a large enough training sample, we can
reliably find a hypothesis b h 2 H with mean square error close to that of the best hypothesis in H.
Finally, we say H is learnable if and only if it is ffl-learnable for all ffl ? 0.
1g the above definitions of learnability yield the probabilistic concept learning
model. In this case, if (7) holds for some ffl ? 0 and some class H, we say that H is ffl-learnable in
the p-concept model.
We now state and prove the main results of this section. We start by establishing sufficient
conditions for ffl-learnability and learnability in terms of the P fl -dimension.
Theorem 4.1 There exist constants a; b ? 0 such that for any fl ? 0:
1. If P fl -dim(H) is finite, then H is (afl)-learnable.
2. If V fl -dim(H) is finite, then H is (bfl)-learnable.
3. If P fl -dim(H) is finite for all fl ? 0 or V fl -dim(H) is finite for all fl ? 0, then H is learnable.
We then prove the following, which characterizes p-concept learnability.
Theorem 4.2
1. If P fl -dim(H) is infinite, then H is not (fl 2 =8 \Gamma -learnable in the p-concept model for any
2. If V fl -dim(H) is infinite, then H is not (fl 2 =2 \Gamma -learnable in the p-concept model for any
3. The following are equivalent:
(a) H is learnable in the p-concept model.
(b) P fl -dim(H) is finite for all fl ? 0.
(c) V fl -dim(H) is finite for all fl ? 0.
(d) H is a uniform Glivenko-Cantelli class.
Proof of Theorem 4.1. It is clear that part 3 follows from part 1 using Theorem 2.2. Also,
by Lemma 2.2, part 1 is equivalent to part 2. Thus, to prove Theorem 4.1 it suffices to establish
part 1. We do so via the next two lemmas.
Hg.
Lemma 4.1 If ' H is an ffl-uniform Glivenko-Cantelli class, then H is (3ffl)-learnable.
Proof. The proof uses the method of empirical risk minimization, analyzed by Vapnik [22]. As
the empirical loss on the given sample z that is
A learning procedure, A
ffl , ffl-minimizes the empirical risk if A
ffl (z n ) is any b
us show that any such procedure is guaranteed to 3ffl-learn H.
Fix any n 2 N. If
for all h 2 H, then
and thus P (' A   ffl (zn Hence, since we chose n and ffl arbitrarily,
lim
sup
Pr
sup
m-n
sup
implies
lim
sup
Pr
ae
oe
0:The following lemma shows that bounds on the covering numbers of a family of functions H can be
applied to the induced family of loss functions ' H . We formulate the lemma in terms of the square
loss but it may be readily generalized to other loss functions. A similar result was independently
proven by Bartlett, Long, and Williamson in [4] for the absolute loss L(x; (and with
respect to the l 1 metric rather than the l 1 metric used here).
Lemma 4.2 For all ffl ? 0, all H, and any z
Proof. It suffices to show that, for any f; g 2 H and any 1 -
then This follows by noting that, for every s; t; w 2 [0; 1],
We end the proof of Theorem 4.1 by proving part 1. By Lemma 4.1, it suffices to show that ' H
is (afl)-uniform Glivenko-Cantelli for some a ? 0. To do so we use (2) from Lemma 3.3. Then,
to bound the expected covering number, we apply first Lemma 4.2 and then Lemma 3.4. This
establishes
lim
sup
Pr
sup
for some a ? 0 whenever P fl -dim(H) is finite. An application of the Borel-Cantelli lemma to get
almost sure convergence yields the proof. 2
We conclude this section by proving our characterization of p-concept learnability.
Proof of Theorem 4.2. As ffl-learnability implies ffl-learnability in the p-concept model, we have
that part 3 follows from part 1, part 2, and from Theorem 4.1 using Theorem 2.2.
The proof of part 2 uses arguments similar to those used to prove part 1.d of Theorem 2.2.
Finally note that part 1 follows from part 2 by Lemma 2.2 (we remark that a more restricted
version of part 1 was proven in Theorem 11 of [14].) 2
5 Conclusions and open problems
In this work we have shown a characterization of uniform Glivenko-Cantelli classes based on a
combinatorial notion generalizing the Vapnik-Chervonenkis dimension. This result has been applied
to show that the same notion of dimension provides the weakest combinatorial condition known to
imply agnostic learnability and, furthermore, characterizes learnability in the model of probabilistic
concepts under the square loss. Our analysis demonstrates how the accuracy parameter in learning
plays a central role in determining the effective dimension of the learner's hypothesis class.
An open problem is what other notions of dimension may characterize uniform Glivenko-Cantelli
classes. In fact, for classes of functions with finite range, the same characterization is achieved by
each member of a family of several notions of dimension (see [5]).
A second open problem is the asymptotic behaviour of the metric entropy: we have already
shown that for all ffl ? 0, H n (ffl; is a uniform Glivenko-Cantelli class and
We conjecture that for all ffl ? 0, H n (ffl;
is a uniform Glivenko-Cantelli class. A positive solution of this conjecture would also affect the
sample complexity bound (6) of Bartlett and Long. In fact, suppose that Lemma 3.4 is improved by
showing that sup xn M(ffl; F ; x n
\Delta cd for some positive constant c and for
(note that this implies our conjecture.) Then, combining this with [3, Lemma 10-11], we can easily
show a sample complexity bound of
O
for any 0 ! - ! 1=8 for which is finite. It is not clear how to bring the
constant 1=8 down to 1=4 as in (6), which was proven using l 1 packing numbers.

Acknowledgments

We would like to thank Michael Kearns, Yoav Freund, Ron Aharoni and Ron Holzman for fruitful
discussions, and Alon Itai for useful comments concerning the presentation of the results.
Thanks also to an anonymous referee for the many valuable comments, suggestions, and references




--R

Embedding of
Minimax nonparametric estimation over classes of sets.
More theorems about scale-sensitive dimensions and learning

Characterizations of learnability for classes of f0
Learnability and the Vapnik-Chervonenkis dimension
A lower bound for f0
A course on empirical processes.
Uniform and universal Glivenko-Cantelli classes
Some limit theorems for empirical processes.
Structural risk minimization for character recognition.
Decision theoretic generalizations of the PAC model for neural net and other learning applications.
A generalization of Sauer's lemma.
Efficient distribution-free learning of probabilistic concepts
Some remarks about embedding of
Empirical Processes
Modeling by shortest data description.
On the density of families of sets.
A combinatorial problem: Stability and order for models and theories in infinitary languages.
Bounds on the number of examples needed for learning functions.

Estimation of Dependences Based on Empirical Data.
Inductive principles of the search for empirical dependencies.
On the uniform convergence of relative frequencies of events to their probabilities.
Necessary and sufficient conditions for uniform convergence of means to mathematical expectations.
--TR
A lower bound for 0,1, * tournament codes
Learnability and the Vapnik-Chervonenkis dimension
Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures)
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Efficient distribution-free learning of probabilistic concepts
Characterizations of learnability for classes of {0, MYAMPERSANDhellip;, <italic>n</italic>}-valued functions
A generalization of Sauer''s lemma
Bounds on the number of examples needed for learning functions
More theorems about scale-sensitive dimensions and learning
Fat-shattering and the learnability of real-valued functions

--CTR
Philip M. Long, On the sample complexity of learning functions with bounded variation, Proceedings of the eleventh annual conference on Computational learning theory, p.126-133, July 24-26, 1998, Madison, Wisconsin, United States
Martin Anthony , Peter L. Bartlett, Function Learning from Interpolation, Combinatorics, Probability and Computing, v.9 n.3, p.213-225, May 2000
Massimiliano Pontil, A note on different covering numbers in learning theory, Journal of Complexity, v.19 n.5, p.665-671, October
John Shawe-Taylor , Robert C. Williamson, A PAC analysis of a Bayesian estimator, Proceedings of the tenth annual conference on Computational learning theory, p.2-9, July 06-09, 1997, Nashville, Tennessee, United States
John Shawe-Taylor , Nello Cristianini, Further results on the margin distribution, Proceedings of the twelfth annual conference on Computational learning theory, p.278-285, July 07-09, 1999, Santa Cruz, California, United States
Olivier Bousquet , Andr Elisseeff, Stability and generalization, The Journal of Machine Learning Research, 2, p.499-526, 3/1/2002
Shahar Mendelson, On the size of convex hulls of small sets, The Journal of Machine Learning Research, 2, p.1-18, 3/1/2002
Tong Zhang, Covering number bounds of certain regularized linear function classes, The Journal of Machine Learning Research, 2, p.527-550, 3/1/2002
Don Hush , Clint Scovel, Fat-Shattering of Affine Functions, Combinatorics, Probability and Computing, v.13 n.3, p.353-360, May 2004
Don Hush , Clint Scovel, On the VC Dimension of Bounded Margin Classifiers, Machine Learning, v.45 n.1, p.33-44, October 1 2001
Martin Anthony, Generalization Error Bounds for Threshold Decision Lists, The Journal of Machine Learning Research, 5, p.189-217, 12/1/2004
Shahar Mendelson , Petra Philips, On the Importance of Small Coordinate Projections, The Journal of Machine Learning Research, 5, p.219-238, 12/1/2004
Kristin P. Bennett , Nello Cristianini , John Shawe-Taylor , Donghui Wu, Enlarging the Margins in Perceptron Decision Trees, Machine Learning, v.41 n.3, p.295-313, Dec. 2000
Philip M. Long, Efficient algorithms for learning functions with bounded variation, Information and Computation, v.188 n.1, p.99-115, 10 January 2004
John Shawe-Taylor , Peter L. Bartlett , Robert C. Williamson , Martin Anthony, A framework for structural risk minimisation, Proceedings of the ninth annual conference on Computational learning theory, p.68-76, June 28-July 01, 1996, Desenzano del Garda, Italy
Barbara Hammer, Generalization Ability of Folding Networks, IEEE Transactions on Knowledge and Data Engineering, v.13 n.2, p.196-206, March 2001
Alberto Bertoni , Carlo Mereghetti , Beatrice Palano, Small size quantum automata recognizing some regular languages, Theoretical Computer Science, v.340 n.2, p.394-407, 27 June 2005
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
Yiming Ying , Ding-Xuan Zhou, Learnability of Gaussians with Flexible Variances, The Journal of Machine Learning Research, 8, p.249-276, 5/1/2007
Bernhard Schlkopf , Alexander J. Smola, A short introduction to learning with kernels, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
Shahar Mendelson, A few notes on statistical learning theory, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
Shahar Mendelson, Learnability in Hilbert spaces with reproducing kernels, Journal of Complexity, v.18 n.1, p.152-170, March 2002
Bin Zou , Luoqing Li, The performance bounds of learning machines based on exponentially strongly mixing sequences, Computers & Mathematics with Applications, v.53 n.7, p.1050-1058, April, 2007
uniform laws of large numbers;vapnik-chervonenkis dimension;PAC learning