NeuroCOLT

Neural Networks and Computational Learning Theory

 

About NeuroCOLT

Papers Archive

1994 1995
1996 1997
1998 1999
2000 2001

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-96-047

A Graph-theoretic Generalization of the Sauer-Shelah Lemma

Nicoḷ Cesa-Bianchi
University of Milan
Italy

David Haussler
University of California Santa Cruz
USA

Abstract
We show a natural graph-theoretic generalization of the Sauer-Shelah lemma. This result is applied to bound the $\ell_{\infty}$ and $L_1$ packing numbers of classes of functions whose range is an arbitrary, totally bounded metric space.

 

Download Compressed Postscript