VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions

DOI10.1137/0222076zbMath0799.68158OpenAlexW2024415066MaRDI QIDQ4277543

Thorsten Werther, Marek Karpinski

Publication date: 13 November 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222076

zbMATH Keywords

computational learning theoryVC dimensionregression functionsparse polynomials

Mathematics Subject Classification ID

Linear inference, regression (62J99) Learning and adaptive systems in artificial intelligence (68T05) Combinatorics in computer science (68R05) Pattern recognition, speech recognition (68T10) Real polynomials: analytic properties, etc. (26C05)

Related Items (8)

Computability of the additive complexity of algebraic circuits with root extracting ⋮ Descartes' Rule of Signs for Radial Basis Function Neural Networks ⋮ Generalization ability of fractional polynomial models ⋮ Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks ⋮ On the decidability of sparse univariate polynomial interpolation ⋮ On the Capabilities of Higher-Order Neurons: A Radial Basis Function Approach ⋮ Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis ⋮ On the Complexity of Computing and Learning with Multiplicative Neural Networks

This page was built for publication: VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions