Learnability and the Vapnik-Chervonenkis dimension

By Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth. 1989

How researchers see this paper

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

In Scaling & Learning Theory

Citations in the corpus

Deep Learning Scaling is Predictable, Empirically (2017, background): “Early follow-on research tightens the bounds by relating sample complexity to generalization error through the Vapnik-Chervonenkis (VC) dimension of the target concept class (Ehrenfeucht et al. (1989); Blumer et al. (1989); Haussler et al. (1996)).”
A Model of Inductive Bias Learning (2000, methodology): “For Boolean learning problems (pattern classification) these parameters are the bias learning analogue of the Vapnik-Chervonenkis dimension (Vapnik, 1982; Blumer et al., 1989 ).”
Characterizing the sample complexity of private learners (2013, background): “It is well known that the sample complexity of learning a concept class C (non-privately) is proportional to a complexity measure of the class C knowns as the VC-dimension [20, 6, 13].”
Is your dataset big enough? Sample size requirements when using artificial neural networks for discrete choice analysis (2018, methodology): “…mathematical framework for studying data requirements, they have led to hardly any application in practice due to the prohibitive di ﬃ culty of mean-ingfully quantifying the VC dimension for complex learning models such as ANNs (Anthony and Bartlett, 2009; Blumer et al., 1989; Haussler, 1992a).”
Rademacher penalties and structural risk minimization (2001, background): “It plays also an important role in computational learning theory [8], [ 9 ].”
Ambiguous chance constrained problems and robust optimization (2006, methodology): “Proposition 1 (Sauer's Lemma [9, 1, 31]) Suppose the VC dimension d f of the function f (·, ·) is finite.”
Boosting and Hard-Core Set Construction (2003, result): “... on the other hand, a set S of examples is drawn from EX( f, D) once and for all at the beginning of the boosting process and the initial distribution D0 is taken to be the uniform distribution over S. Subsequent distributions Di are nonzero only on the points of S, and the final hypothesis h gen”
On the difficulty of approximately maximizing agreements (2000, background): “We now turn to listing the conditions under which the various Maximum Agreement problems we consider become easy to solve: Claim 23 ([7]) The RMA problem may be solved in polynomial time for inputs that are separable by an axis-aligned rectangle.”
On the complexity of teaching (1991, background): “We show that this new dimension measure is fundamentally di erent from the Vapnik-Chervonenkis dimension [3, 11, 20] and the dimension measure of Natarajan [13].”