Sample size lower bounds in PAC learning by Algorithmic Complexity Theory

DOI10.1016/S0304-3975(97)00102-3zbMath0912.68162OpenAlexW2043360510MaRDI QIDQ1274920

Bruno Apolloni, Claudio Gentile

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00102-3

zbMATH Keywords

Kolmogorov complexitycomputational learningsample complexity

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Unnamed Item, Improved lower bounds for learning from noisy examples: An information-theoretic approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learnability with respect to fixed distributions
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension
• A Markovian extension of Valiant's learning model
• On the density of families of sets
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Randomness conservation inequalities; information and independence in mathematical theories
• Probably Approximate Learning over Classes of Distributions