@article{dbf3c19cdce14eddaa53f163577810a5,

title = "A Metric Entropy Bound is Not Sufficient for Learnability",

abstract = "We prove by means of a counterexample that it is not sufficient, for probably approximately correct (PAC) learning under a class of distributions, to have a uniform bound on the metric entropy of the class of concepts to be learned. This settles a conjecture of Benedek and Itai.",

keywords = "Learning, PAC, class of distributions, estimation, metric entropy",

author = "Dudley, {R. M.} and Kulkarni, {S. R.} and T. Richardson and O. Zeitouni",

note = "Funding Information: We say that the concept class 8 is probably approximately correct (PAC) learnable under the class of probability measures 9 (in short: 8 is PAC learnable under 9)if , for every E > 0, 6 > 0, there exist an integer n = n(9,8, E, 6) and a learning of R. M. Dudley was partially supported by National Science Foundation grants. The work of S. Kukami was supported in part by the Army Research Office under Grant DAALO3-92-G-0320 and by the National Science Foundation under Grant IRI-92-09577. The work of 0. Zeitouni was done while visiting the Center for Intelligent Control Systems at M.I.T. under support of the U.S. Army Research Office Grant DAALO3-92-G-0115. R. M. Dudley is with the Dept. of Mathematics, M.I.T., Cambridge, MA 02139. S. Kulkarni is with the Dept. of Electrical Engineering, Princeton University, Princeton, NJ 08544. T. RIchardson is with AT & T Bell Labs, 600 Mountain Ave., Murray Hill, NJ 07974. 0. Zeitouni is with The Dept. of Electrical Engineering, Technion, Haifa 32000, Israel. IEEE Log Number 9401814. Funding Information: Manuscript received Oct. 1, 1991; revised Sept. 1, 1993. This work was partially supported by NSF Grant NCR-89-14538, DARPA Contract J-FBI-91-218, and JSEP Contract DAALB3-91-C-0010. S. Pombra is at 413 Mountain Laurel Court, Mountain View, CA 94043. T. M. Cover is with the Departments of Electrical Engineering and Statistics, Stanford University, Stanford, CA 94305. IEEE Log Number 9401815.",

year = "1994",

month = may,

doi = "10.1109/18.335898",

language = "English (US)",

volume = "40",

pages = "883--885",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}