Sample size lower bounds in PAC learning by Algorithmic Complexity Theory

摘要

This paper focuses on a general setup for obtaining sample size lower bounds for learning concept classes under fixed distribution laws in an extended PAC learning framework. These bounds do not depend on the running time of learning procedures and are information-theoretic in nature, They are based on incompressibility methods drawn from Kolmogorov Complexity and Algorithmic Probability theories. (C) 1998-Elsevier Science B.V. All rights reserved. [References: 23]