A generalization of Sauer's lemma (Q1899068): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q244346 |
Changed an Item |
||
| Property / reviewed by | |||
| Property / reviewed by: Zheng Yan Lin / rank | |||
Normal rank | |||
Revision as of 01:00, 12 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A generalization of Sauer's lemma |
scientific article |
Statements
A generalization of Sauer's lemma (English)
0 references
11 February 1996
0 references
The authors generalize \textit{N. Sauer's} lemma [ibid. 13, 145-147 (1972; Zbl 0248.05005)] to multivalued functions, proving tight bounds on the cardinality of subsets of \(\prod^m_{i= 1} \{0,\dots, N_i\}\) which avoid certain patterns. In addition, the authors give an application of this result, bounding the uniform rate of convergence of empirical estimates of the expectations of a set of random variables to their true expectations.
0 references
Vapnik-Chervonenkis dimension
0 references
multivalued function
0 references
expectation estimate
0 references
