NeuroCOLT: Neural Networks and Computational Learning Theory

NeuroCOLT

Neural Networks and Computational Learning Theory

1994	1995
1996	1997
1998	1999
2000	2001

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-95-044

Neural Networks with Quadratic VC Dimension

Pascal Koiran
Ecole Normale Sup\'erieure de Lyon

Eduardo D. Sontag
Rutgers University

Abstract
This paper shows that neural networks which use continuous activation functions have VC dimension at least as large as the square of the number of weights $w$. This result settles a long-standing open question, namely whether the well-known $O(w \log w)$ bound, known for hard-threshold nets, also held for more general sigmoidal nets. Implications for the number of samples needed for valid generalization are discussed.

Download Compressed Postscript