Sphere Packing Numbers for Subsets of the Boolean n-Cube with Bounded Vapnik-Chervonenkis Dimension

By David Haussler. 1995

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

GenDICE: Generalized Offline Estimation of Stationary Values (2020, background): “The covering number can then be bounded in terms of the function class’s pseudo-dimension: Lemma 5 (Haussler (1995), Corollary 3) For any set X , any points x1:N ∈ XN , any class F of functions on X taking values in [0,M ] with pseudo-dimension DF <∞, and any > 0, N1 ( ,F , x1:N ) ≤ e (DF + 1) (…”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “[Corollary 3, [20]] For any set X , any points x ∈ X , any class F of functions on X taking values in [0,M ] with pseudo-dimension DF <∞, and any > 0,”
Learning When-to-Treat Policies (2019, background): “In the case of linear thresholding policies with binary actions |A| = 2, that is, {π ∈ : τπ = min(t : θ S1:t > 0)} where θ ∈ Rd, we note that by Haussler (1995), the covering number of a policy class for single-step decision-making is bounded by NL1(Pn)(ε, t) ≤ cVC( t) expVC( t)(1/ε)VC( t) where…”
Smoothed Dual Embedding Control (2017, background): “amp; Chen (2002)) and is often necessary to prove large deviation bounds. Invoking a generalized version of Pollard’s tail inequality to -mixing sequences and prior results in Antos et al. (2008) and Haussler (1995), we show that Theorem 6 (Statistical error) Under Assumption 2, it holds with at lea”
Local Rademacher complexities (2005, neutral): “an construct an ǫ-cover for star(F,0) using an ǫ/2-cover for F and an ǫ/2-cover for the interval [0,1], which implies logN(ε,star(F,0),L 2(Pn))≤logN ε 2 ,F,L 2(Pn) ˘ 2 ǫ ˇ +1 . Now, recall that [14] for any probability distribution Pand any class F with VC-dimension d<∞, logN ε 2 ,F,L 2(P) ≤c”
Batch Policy Learning under Constraints (2019, background): “We can further bound the empirical covering number by invoking the following lemma due to Haussler (Haussler, 1995): Lemma E.6 ((Haussler, 1995), Corollary 3).”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “Lemma 19 (Bounding covering number by pseudo-dimension [Haussler, 1995]).”
Efficient Policy Learning (2017, methodology): “In particular, if Π is a Vapnik-Chervonenkis class, Haussler (1995) showed that log (NH(ε, Π)) ≤ d ( log ( ε−1 ) + log(2) + 1 ) + log (d+ 1) + 1, with d := VC(Π), (23) from which we can check that κ2(Π) ≤ 6d for any value of d = 1, 2, ....”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, background): “10 (Bounding L1 Covering Number by Pseudo Dimension, [Haussler, 1995]).”
A Data Prism: Semi-verified learning in the small-alpha regime (2018, methodology): “As was shown by Haussler (Theorem 1 in (Haussler, 1995)), for any subset S of the Boolean hypercube with VC dimension at most r, for every >0 there exists a set T⊂{0,1}n of size at most e(r+1) ( 2e )r such that for every point x∈S, there exists a point tx∈T that agrees with x on at least (1− )n coor”
Adaptive computation and machine learning (1998, unknown): “There are also close relationships between these complexity measures: for example, by Dudley’s theorem, the empirical Rademacher complexity can be bounded in terms of N2(G, ) [Dudley, 1967, 1987] and the covering and packing numbers can be bounded in terms of the VC-dimension [Haussler, 1995].”
The inverse of the star-discrepancy depends linearly on the dimension (2001, methodology): “This and (6) proves that the inverse of the ∗-discrepancy depends linearly on d.”
Theory of Disagreement-Based Active Learning (2014, methodology): “In particular, bounds of this type (having no direct dependence on PXY ), have been developed, for instance by Koltchinskii [2006], based on data-dependent Rademacher complexities.”
VC bounds on the cardinality of nearly orthogonal function classes (2010, background): “As d → ∞, our bound asymptotically behaves as ln[GKM(γ, d)] d → (ln 2)β(γ) while Haussler’s as ln[DH(γ, d)] d → ln ( 4e 1− γ ) .”
Offline Multi-Action Policy Learning: Generalization and Optimization (2018, background): “Both of these assumptions are standard and commonly adopted in both the estimation literature (Rosenbaum and Rubin (1983), Imbens (2004), Imbens and Rubin (2015), Athey et al.”
Finite time bounds for sampling based fitted value iteration (2005, background): “Proposition 1 (Haussler (1995), Corollary 3) For any set X , any points x1:N ∈ XN , any class F of functions on X taking values in [0, L] with pseudo-dimension VF+ < ∞, and any 2 > 0, N (2,F(x1:N )) ≤ e(VF+ + 1) ( 2eL 2 )VF+ .”