On the Density of Families of Sets

By N. Sauer. 1972

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Counterfactual reasoning and learning systems: the example of computational advertising (2012, background): “Thanks to a famous combinatorial lemma (Vapnik and Chervonenkis, 1968, 1971; Sauer, 1972), for many usual parametric families F , the growth function N (n, ε,F) increases at most polynomially14 with both n and 1/ε. 14.”
A Model of Inductive Bias Learning (2000, background): “…functionof H is defined by H(m) := maxx2Xm Hjx : TheVapnik-Chervonenkis dimensionVCdim(H) is the size of the largest set shattered byH:VCdim(H) := maxfm : H(m) = 2mg: An important result in the theory of learning Boolean functions is Sauer’s Lemma (Sauer, 1972), of which we will also make use.”
On the Expressive Power of Deep Neural Networks (2016, methodology): “For non-random inputs and non-random functions, this is a well known question upper bounded by the Sauer-Shelah lemma (Sauer, 1972).”
Scale-sensitive dimensions, uniform convergence, and learnability (1993, background): “N. ALON ET AL. combinatorial result that generalizes Sauer s Lemma [Sauer 1972; Shelah 1972].”
VC dimension of neural networks (1998, background): “This result, frequently called \Sauer’s Lemma," is from Vapnik and Cervonenkis (1968) (see also Vapnik (1992)), and was discovered independently by Sauer (1972) and Shelah (1972); interestingly, Sauer credits Erd¨os with posing it as a conjecture.”
Private Query Release Assisted by Public Data (2020, background): “Moreover, one can also make the following simple claim, which is a direct consequence of the SauerShelah Lemma (Sauer, 1972) together with the fact that a representative domain XH̃ has a one-to-one correspondence with the dual class of H̃.”
The chromatic thresholds of graphs (2011, methodology): “This technique is based on the concept of paired VC-dimension, which generalises the well-known Vapnik-Červonenkis dimension of a set-system (see [35, 41]).”
Sequential complexities and uniform martingale laws of large numbers (2015, result): “There are several approaches to proving what is often called the Vapnik-Chervonenkis-Sauer-Shelah lemma.”
Covering Number Bounds of Certain Regularized Linear Function Classes (2002, methodology): “For a two-class classification problem, its covering number can be bounded by using a combinatorial quantity called VC-dimension (Sauer, 1972, Vapnik and Chervonenkis, 1971).”
PAC learning with nasty noise (1999, methodology): “The following is based on Sauer’s Lemma [19]: Lemma 1: For any set of points Q, |SCON(Q)| ≤ |Q|VC-dim(H) .”
Teaching a black-box learner (2019, background): “Moreover, since |X | = m, we know by VC bounds (Sauer, 1972) that the effective size of the hypothesis class is at most N = O(m), and we can set H to this finite set of candidate concepts.”
Limits of Private Learning with Access to Public Data (2019, background): “This follows from the fact that for any set V of size m , we , where the last inequality follows from Sauer’s Lemma [Sau72].”
Finite time bounds for sampling based fitted value iteration (2005, background): “The concept of VC-dimension was introduced by Sauer (1972); Vapnik and Chervonenkis (1971) and is defined as follows: Given a set system C with base set X we say that C shatters the points of A ⊂ X if all possible 2|A| subsets of A can be obtained by intersecting A with elements of C.”
Understanding Machine Learning: From Theory to Algorithms (2014, unknown): “Sauer’s lemma has been proved by Sauer in response to a problem of Erdos (Sauer 1972).”