VC Dimension and Learnability of Sparse Polynomials and Rational Functions
| Title | VC Dimension and Learnability of Sparse Polynomials and Rational Functions |
| Publication Type | Technical Report |
| Year of Publication | 1989 |
| Authors | Karpinski, M., & Werther T. |
| Other Numbers | 559 |
| 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). |
| URL | http://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 |