VC Dimension and Learnability of Sparse Polynomials and Rational Functions
Marek Karpiński, Thorsten Werther · 1989
We prove upper and lower bounds on the VC dimension of sparse univariate polynomials over reals, and apply these results to prove uniform learnability of sparse polynomials and rational functions. As another application we solve an open problem of Vapnik ([Vapnik 82]) on uniform approximation of the general regression functions, a central problem of computational statistics (cf. [Vapnik 82]), p. 256). Department of Computer Science, University of Bonn, and International Computer Science Institute, Berkeley, California. Supported in part by Leibniz Center for Research in Computer Science, by the DFG Grant KA 673/2-1, and by the SERC Grant GR-E 68297. y Department of Computer Science, University of Bonn, and International Computer Science Institute, Berkeley, California. 1 Introduction The paper studies the problem of computational identification (learnability) of sparse real polynomials and rational functions. In [Val 84], Valiant introduced a model of learning concepts from examp...