Scale-sensitive dimensions, uniform convergence, and learnability

By Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler. 1993

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 Gliveako-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 simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to characterize PAC learnability in the statistical regression framework of probabilistic concepts, solving an open problem posed by Kearns and Schapire. Our characterization shows that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.<<ETX>>

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Robustness and generalization (2010, background): “…Vapnik-Chervonenkis (VC) dimension (Vapnik and Chervonenkis 1991; Evgeniou et al. 2000), the fat-shattering dimension (Kearns and Schapire 1994; Alon et al. 1997; Bartlett 1998), and the Rademacher complexity (Koltchinskii 2002; Bartlett and Mendelson 2002; Bartlett et al. 2005).”
Stability and generalization (2002, background): “Many researchers [ 1 , 2, 3, 8, 13] have focus ed on these bounds by developing worst case analysis.”
Application of integral operator for regularized least-square regression (2009, methodology): “Consider the set H := { ∑∞ n=1 anφn :∑∞ n=1 a 2 n <∞} and define the inner product by < ∞∑ n=1 anφn , ∞∑ n=1 bnφn >H= ∞∑ n=1 anbn.”
A tutorial on support vector regression (2004, unknown): “The tacit assumption in (2) was that such a function f actually exists that approximates all pairs (xi , yi ) with ε precision, or in other words, that the convex optimization problem is feasible.”
Algorithmic Stability and Generalization Performance (2000, methodology): “covering numbers [1]) or to use a posteriori information about the solution found by the algorithm (e.”
Covering Number Bounds of Certain Regularized Linear Function Classes (2002, methodology): “We shall mention that traditionally, ∞-norm covering numbers are obtained through the so-called " fat-shattering " dimension (Alon et al., 1997).”
Adaptive computation and machine learning (1998, methodology): “For other examples of application of the probabilistic method demonstrating its full power, consult the reference book of Alon and Spencer [1992]. There are several other measures of the complexity of a family of functions used in machine learning, including covering numbers, packing numbers, and so”
Regularization Networks and Support Vector Machines (2000, background): “Unfortunately existing bounds of that type [2] [7] are not tight.”
Generalization bounds for learning the kernel (2009, background): “4 of [1]) to the function class φ ◦ Bλ implies that E(f z )− E z (f z ) ≤ supf∈Bλ ∣∣Eφ(f)− E z (f)∣∣ ≤ 8E [ N∞(ε, φ ◦ Bλ, z) ] e− nε2λ 128κ2 , where φ ◦ Bλ = {φ(yf(x)) : f ∈ Bλ} and N∞(ε, T, z) is the empirical covering number defined, for any f, g ∈ T , by the pseudo-metric dz(f, g) = supi∈Nn ∣∣f(z”
Partially labeled classification with Markov random walks (2001, background): “The 4 dimension [5] of the binary transductive classifier 6 is upper bounded by the number of connected components of a graph with O nodes and adjacency matrix E , where E &'S .”
Capacity of reproducing kernel spaces in learning theory (2003, methodology): “We first show this by applying the lower bound to the dimension [1].”
Statistical performance of support vector machines (2008, methodology): “The ﬁrst result about the SVM algorithm is due to Vapnik; who proved that the fat-shattering dimension (see e.g. [1] for a deﬁnition) at scale 1 of the set { ( x, y ) 7→ y h k ( x, .”