00000cab a22000003a 4500 UP-99796217608823543 Buklod 20231007234830.0 m |o d | ta 090508s xx d | ||r ||||| || DENGII eng Simon, Hans Ulrich Bounds on the number of examples needed for learning functions. pp. 751-763 We prove general lower bounds on the number of examples needed for learning function classes within different natural learning 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 31st Annual Symposium on the Foundations of Computer Science with certain restrictions concerning their slope. Function learning. Sample complexity. SIAM journal on computing. 26, 3 (1997). FO UPD DENG-II Article