The Optimal Sample Complexity of PAC Learning

On the uniform convergence of relative frequencies of events to their probabilities

V. Vapnik and A. Chervonenkis · 1971

Earlier work this paper cites.

A polynomial algorithm in linear programming

L. G. Khachiyan · 1979

Earlier work this paper cites.

Estimation of Dependencies Based on Empirical Data

V. Vapnik · 1982

Earlier work this paper cites.

A new polynomial-time algorithm for linear programming

N. Karmarkar · 1984

Earlier work this paper cites.

A theory of the learnable

L. G. Valiant · 1984

Earlier work this paper cites.

Computational limitations on learning from examples

L. Pitt and L. G. Valiant · 1988

Earlier work this paper cites.

Learnability and the Vapnik-Chervonenkis dimension

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1989

Earlier work this paper cites.

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

A. Ehrenfeucht, D. Haussler, M. Kearns, and L. G. Valiant · 1989

Earlier work this paper cites.

Learning nested differences of intersection-closed concept classes

D. Helmbold, R. Sloan, and M. K. Warmuth · 1990

Cited alongside, same era.

Equivalence of models of polynomial learnability

D. Haussler, M. Kearns, N. Littlestone, and M. K. Warmuth · 1991

Cited alongside, same era.

Predicting { 0 , 1 } \{0,1\} -functions on randomly drawn points

D. Haussler, N. Littlestone, and M. K. Warmuth · 1994

Cited alongside, same era.

Weak Convergence and Empirical Processes

A. W. van der Vaart and J. A. Wellner · 1996

Cited alongside, same era.

An upper bound on the sample complexity of PAC learning halfspaces with respect to the uniform distribution

P. M. Long · 2003

Cited alongside, same era.

The optimal PAC algorithm

Original

M. K. Warmuth · 2004

A new PAC bound for intersection-closed concept classes

P. Auer and R. Ortner · 2007

Later among the works it cites.

Using the doubling dimension to analyze the generalization of learning algorithms

N. H. Bshouty, Y. Li, and P. M. Long · 2009

Later among the works it cites.

Theoretical Foundations of Active Learning

S. Hanneke · 2009

Later among the works it cites.

Active and passive learning of linear separators under log-concave distributions

M.-F. Balcan and P. M. Long · 2013

Later among the works it cites.

The optimal PAC bound for intersection-closed concept classes

M. Darnstädt · 2015

Closest in time.

Refined error bounds for several learning algorithms

Original

S. Hanneke · 2015