VC Dimension and Learnability of Sparse Polynomials and Rational Functions

TitleVC Dimension and Learnability of Sparse Polynomials and Rational Functions
Publication TypeTechnical Report
Year of Publication1989
AuthorsKarpinski, M., & Werther T.
Other Numbers559
Abstract

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).

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-60.pdf
Bibliographic Notes

ICSI Technical Report TR-89-060

Abbreviated Authors

M. Karpinski and T. Werther

ICSI Publication Type

Technical Report