A general lower bound on the number of examples needed for learning

By Andrzej Ehrenfeucht, David Haussler, Michael Kearns, Leslie G. Valiant. 1988

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

An Analysis of the Adaptation Speed of Causal Models (2020, background): “smaller VC-dimension (Vapnik & Chervonenkis, 1971), turns into a smaller generalization gap (Ehrenfeucht et al., 1989).”
A Meta-Transfer Objective for Learning to Disentangle Causal Mechanisms (2019, background): “Since sample complexity - the number of training examples necessary to learn a model - grows approximately linearly (Ehrenfeucht et al., 1989) with VC-dimension (Vapnik and Chervonenkis, 1971), and since VC-dimension grows approximately linearly in the number of parameters in linear models and…”
Learning Optimized Or's of And's (2015, background): “The closest work to ours are that of Hauser et al. (2010) in the marketing literature, and Wang et al. (2015) on Bayesian modeling of DNF formulae.”
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].”
Active and passive learning of linear separators under log-concave distributions (2012, background): “(Ehrenfeucht et al., 1989) proved a bound that implies anΩ(d/ǫ+(1/ǫ) log(1/δ)) lower bound for linear separators and explicitly posed the question of providing tight bounds for this class.”
Feature selection, L1 vs. L2 regularization, and rotational invariance (2004, methodology): “The proof of this result is given in Appendix B, and uses ideas from the lower-bounds originally proved by (Ehrenfeucht et al., 1989; Vapnik, 1982).”
Bandwidth choice for nonparametric classification (2005, background): “The setting where Bayes risk equals zero is sometimes addressed in the context of machine learning [see, e.g., Ehrenfeucht, Haussler, Kearns and Valiant (1989) ].”
Introduction to Statistical Learning Theory (2004, methodology): “The use of empirical processes in classification was pioneered by Vapnik and Chervonenkis [18, 15] and re-discovered 20 years later by Blumer, Ehrenfeucht, Haussler, and Warmuth [32], Ehrenfeucht, Haussler, Kearns, and Valiant [33].”
Cost-sensitive learning by cost-proportionate example weighting (2003, unknown): “A fundamental theorem from PAC-learning theory states that m 1 ε 1 δ Ω 1 ε ln 1 δ [4].”
Precision-Recall versus Accuracy and the Role of Large Data Sets (2019, background): “The asymptotic sample complexity of obtaining a given accuracy is now known exactly: A matching lower bound was proved in two parts; ﬁrst, a Ω( 1 log 1 δ ) lower bound was obtained by Blumer et al. (1989), and subsequently an Ω( d/(cid:15) ) bound was proved by Ehrenfeucht et al. (1989).”