A generalization of Sauer's lemma
Journal of Combinatorial Theory Series APublished 1 August 1995
David Haussler, Philip M. Long
Citations84
SJR quartileQ1
SJR score1.32
SNIP1.74
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Sauer''s lemma is generalized to multivalued functions, bounding the uniform rate of convergence of empirical estimates of the expectations of a set of random variables to their true expectations.
Abstract
We generalize Sauer's lemma to multivalued functions, proving tight bounds on the cardinality of subsets of ∏i = 1m {0, …, Nm} which avoid certain patterns. In addition, we 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.
Keywords
Computer Science
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Communications of the ACMA theory of the learnable
3,268 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension
1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more
This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Journal of Combinatorial Theory Series AOn the density of families of sets
866 Citations1972N. Sauer
This paper will answer the question in the affirmative by determining the exact upper bound of T if T is a family of subsets of some infinite set S then either there exists to each number n a set A ⊂ S with |A| = n such that |T ∩ A| = 2n or there exists some number N such that •A| c for each A⩾ N and some constant c.
Project Euclid (Cornell University)Empirical Processes: Theory and Applications
711 Citations1990David Pollard
Machine LearningOn Learning Sets and Functions
151 Citations1989B. K. Natarajan
This paper presents some results on the probabilistic analysis of learning, illustrating the applicability of these results to settings such as connectionist networks.
Machine LearningOn learning sets and functions
93 Citations1989B. K. Natarajan
This paper presents some results on the probabilistic analysis of learning, illustrating the applicability of these results to settings such as connectionist networks.
Journal of Combinatorial Theory Series AOn the trace of finite sets
81 Citations1983Péter Frankl
A unified proof for results of Bollobas, Bondy, and Sauer concerning this arrow function is given, and a conjecture of Bondy and Lovasz saying (⌋ n 2 4 ⌋ + n + 2,n)→ (3,7) is proved, which generalizes Turan's theorem on the maximum number of edges in a graph not containing a triangle.
Generalizing the PAC model: sample size bounds from metric dimension-based uniform convergence results
67 Citations1989David Haussler
The probably approximately correct (PAC) model of learning from examples is generalized, and a distribution-independent uniform convergence result for certain classes of functions computed by feedforward neural nets is obtained.
Discrete Applied MathematicsBounding sample size with the Vapnik-Chervonenkis dimension
61 Citations1993John Shawe‐Taylor, Martin Anthony +1 more
A proof that a concept class is learnable provided the Vapnik—Chervonenkis dimension is finite is given.
Discrete MathematicsCoordinate density of sets of vectors
45 Citations1978Mark G. Karpovsky, Vitali Milman
Conference on Learning TheoryInductive principles of the search for empirical dependences (methods based on weak convergence of probability measures)
34 Citations1989Vladimir Vapnik
Journal of Combinatorial Theory Series AExistence of submatrices with all possible columns
30 Citations1978John Steele
It is proved that any set of 2 k −2 + 1 points in R 2 contains a set of k points which form a convex polygon.
Discrete MathematicsForbidden submatrices
21 Citations1986R.P. Anstee, Zoltán Füredi
This summer I worked with Dr. Richard Anstee on the problem of forbidden submatrices, and asked what is the maximum number of unique columns a (0; 1)-matrix A with m rows may have, without containing a copy of F as a submatrix.
Graphs and CombinatoricsBounding one-way differences
16 Citations1987Péter Frankl, Zoltán Füredi +1 more
f(n, k) is proved to be the maximum length of a sequence of distinct subsets of ann-element set with the property thatFi∖Fj| < k for alli < j.
Journal of Combinatorial Theory Series AGeneral forbidden configuration theorems
15 Citations1985R.P. Anstee
Borders on the number of columns in a matrix when certain submatrices are forbidden are given, following from a configuration theorem that says, in essence, that matrices without a configuration are determined by row intersections of sets of rows of various sizes.
European Journal of CombinatoricsThe Subposet Lattice and the Order Polynomial
12 Citations1982Paul H. Edelman, Paul Klingsberg
The structure of the lattice of all subposets of a fixed poset is explored and this lattice is then used to prove some identities for the order polynomial of that poset.
Journal of Combinatorial Theory Series AA forbidden configuration theorem of Alon
7 Citations1988R.P. Anstee
An inductive proof and new f ( n, S ) × n matrices A as above are provided and Noga Alon proved that if A is an m × n (n; q 1, q 2 , …, q n ) -matrix with no repeated rows, and for each S ϵ S , not all possible rows on columns S, then m ⩽ f (n, S ).
Discrete MathematicsOn the density of sets of divisors
4 Citations1995R. E. L. Aldred, R.P. Anstee
A forbidden configuration theorem of the type that if a set of divisors D avoids certain configurations, then |D|? |?|?| is generalized and generalizes a result of Alon and in turn generalizesA result of Sauer, Perles and Shelah.
Discrete Mathematics“Dart calculus” of induced subsets
1 Citations1981Pavel Tomasta
The paper contains some basic results from ''dart calculus'' ofinduced subsets of induced subsets that obtain a negative answer to Hajnal's hypothesis.