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 informationtheoretic in nature. They are based on incompressibility methods drawn from Kolmogorov Complexity and Algorithmic Probability theories. 1 INTRODUCTION In recent years the job of algorithmically understanding data, above and beyond simply using them as input for some function, has been emerging as a key computing task. Requests for this job derive from a need to save memory space of devices such as the silicium computer, CD ROMs or, directly, our brain. The usual efficient methods of data compression, such as fractal [12] or wavelet [23] compression, aim at capturing the inner structure of the data. A parametric description of this structure is stored, tolerating bounded mistakes in rendering the original data. In the PAC-lear..