VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions
Marek Karpiński, Thorsten Werther · SIAM Journal on Computing · 1993
The authors 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 an application the solution to the open problem of Vapnik [in Estimation of Dependences Based on Empirical Data, Springer-Verlag, Berlin, 1982] on computational approximation of the regression in a class of polynomials used in the theory of empirical data dependences is given.