A Graph-theoretic Generalization of the Sauer-Shelah Lemma

Nicolò Cesa-Bianchi, David HausslerDiscret. Appl. Math 1998 · DOI · OpenReview

Abstract

We show a natural graph-theoretic generalization of the Sauer-Shelah lemma. This result is applied to bound the ℓ∞ and L1 packing numbers of classes of functions whose range is an arbitrary, totally bounded metric space.
BibTeX
@article{cesabianchi1998graph,
  author = {Nicolò Cesa-Bianchi and David Haussler},
  title = {{A Graph-theoretic Generalization of the Sauer-Shelah Lemma}},
  journal = {Discret. Appl. Math.},
  year = {1998},
  doi = {10.1016/s0166-218x(98)00012-2},
}

Loading related content...

Figure