Improved bounds on the sample complexity of learning

DOI10.1006/jcss.2000.1741zbMath0990.68081MaRDI QIDQ5943102

Yi Li, Philip M. Long, Aravind Srinivasan

Publication date: 9 September 2001

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1741

zbMATH Keywords

PAC learning; sample complexity of learning

Mathematics Subject Classification ID

68Q32: Computational learning theory

68T05: Learning and adaptive systems in artificial intelligence

68T27: Logic in artificial intelligence

Related Items

Range minima queries with respect to a random permutation, and approximate range counting, Relative \((p,\varepsilon )\)-approximations in geometry, Theory of Classification: a Survey of Some Recent Advances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Sharper bounds for Gaussian and empirical processes
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• A theory of the learnable
• Probability Inequalities for Sums of Bounded Random Variables
• An inequality involving multinomial probabilities
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Convergence of stochastic processes