Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC) Machine Learning Model

[author] v. Neumann, J.J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen 100 295–320

1928

Earlier work this paper cites.

[author] Hardy, G. H.G. H., Littlewood, J. E.J. E. and Pólya, G.G. (1967). Inequalities. Cambridge University Press, Cambridge Reprint of the 1952 edition

1952

Earlier work this paper cites.

[author] Sion, MauriceM. (1958). On general minimax theorems. Pacific J. Math. 8 171–176. 0097026 (20 ##3506)

1958

Earlier work this paper cites.

[author] Kingman, J. F. C.J. F. C. (1961). A convexity property of positive matrices. Quart. J. Math. Oxford Ser. (2) 12 283–284. 0138632

1961

Earlier work this paper cites.

[author] Ferguson, Thomas S.T. S. (1967). Mathematical statistics: A decision theoretic approach. Probability and Mathematical Statistics, Vol. 1. Academic Press, New York-London. 0215390

1967

Earlier work this paper cites.

[author] Vapnik, V. N.V. N. and Červonenkis, A. Ja.A. J. (1971). The uniform convergence of frequencies of the appearance of events to their probabilities. Teor. Verojatnost. i Primenen. 16 264–279. 0288823 (44 ##6018)

1971

Earlier work this paper cites.

[author] Valiant, Leslie G.L. G. (1984). A Theory of the Learnable. Commun. ACM 27 1134-1142

1984

Earlier work this paper cites.

[author] Pinelis, I. F.I. F. and Utev, S. A.S. A. (1989). Sharp exponential estimates for sums of independent random variables. Theory Probab. Appl. 34 340–346. 10.1137/1134032 MR1005745 (91a:60053)

1989

Earlier work this paper cites.

[author] Pinelis, I. F.I. F. (1991). Criterion for complete determinacy for concave-convexlike games. Math. Notes 49 277–279

1991

Earlier work this paper cites.

[author] Haussler, DavidD. (1992). Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications. Inf. Comput. 100 78–150. 10.1016/0890-5401(92)90010-D

1992

Cited alongside, same era.

[author] Kearns, Michael J.M. J. and Schapire, Robert E.R. E. (1994). Efficient distribution-free learning of probabilistic concepts. J. Comput. Syst. Sci. 48 464–497. http://dx.doi.org/10.1016/S0022-0000(05)80062-5

1994

Cited alongside, same era.

[author] Kearns, Michael J.M. J., Schapire, Robert E.R. E. and Sellie, LindaL. (1994). Toward Efficient Agnostic Learning. Machine Learning 17 115-141

1994

Cited alongside, same era.

[author] Talagrand, MichelM. (1994). Sharper Bounds for Gaussian and Empirical Processes. Ann. Probab. 22 28–76. 10.1214/aop/1176988847

1994

Cited alongside, same era.

[author] Devroye, L.L. and Lugosi, G.G. (1995). Lower bounds in pattern recognition and learning. Pattern Recognition 28 1011–1018

[author] Anthony, MartinM. and Bartlett, Peter L.P. L. (1999). Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge. 10.1017/CBO9780511624216 1741038 (2001b:68061)

1999

Later among the works it cites.

[author] Long, Philip M.P. M. (1999). The Complexity of Learning According to Two Models of a Drifting Environment. Mach. Learn. 37 337–354. 10.1023/A:1007666507971

1999

Later among the works it cites.

[author] Audibert, Jean-YvesJ.-Y. (2009). Fast learning rates in statistical inference through aggregation. Ann. Statist. 37 1591–1646. 10.1214/08-AOS623

2009

Later among the works it cites.

[author] Boucheron, StéphaneS., Lugosi, GáborG. and Massart, PascalP. (2013). Concentration inequalities. Oxford University Press, Oxford A nonasymptotic theory of independence, With a foreword by Michel Ledoux. 3185193

2013

Later among the works it cites.