Lehrstuhl Mathematik & InformatikBounds on the number of examples needed for learning functions
Abstract. We prove general lower bounds on the number of examples needed for learning function classes within different natural models which are related to pac-learning (and coincide with the pac-learning model of Valiant in the case of {0, 1}-valued functions). The lower bounds are obtained by showing that all nontrivial function classes contain a "hard binary-valued subproblem." Although (at first glance) it seems to be likely that real-valued function classes are much harder to learn than their hardest binary-valued subproblem, we show, that these general lower bounds cannot be improved by more than a logarithmic factor. This is done by discussing some natural function classes like nondecreasing functions or piecewise-smooth functions (the function classes that were discussed in [KeSc] and [KiLo] with certain restrictions concerning their slope.
References:
[KeSc] M. J. Kearns and R.
E. Schapire, Proc. 31st Annual Symposium on the Foundations of Computer
Science
IEEE Computer Society Press, Los Alamitos, CA, 1990, pp. 382-392, full
version, J. Comput. System Sci., 48 (1994), pp. 464-497.
[KiLo] D. Kimber and P. M.
Long, Proc. 5th Annual Workshop on Computational Learning Theory, ACM,
New York, 1992, pp. 153-160