Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension
From MaRDI portal
Publication:1345876
DOI10.1016/0097-3165(95)90052-7zbMATH Open0818.60005OpenAlexW2058239479MaRDI QIDQ1345876FDOQ1345876
Authors: David Haussler 
Publication date: 7 August 1995
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0097-3165(95)90052-7
Recommendations
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial probability (60C05) Combinatorial aspects of packing and covering (05B40)
Cites Work
- Title not available (Why is that?)
- Convergence of stochastic processes
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the density of families of sets
- Sharper bounds for Gaussian and empirical processes
- Learnability and the Vapnik-Chervonenkis dimension
- \(\epsilon\)-nets and simplex range queries
- Induced subsets
- Title not available (Why is that?)
- Some limit theorems for empirical processes (with discussion)
- Title not available (Why is that?)
- Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
- Central limit theorems for empirical measures
- Title not available (Why is that?)
- The complexity and construction of many faces in arrangements of lines and of segments
- On the trace of finite sets
- Colorings and orientations of graphs
- The Glivenko-Cantelli problem
- Density and dimension
- Universal Donsker classes and metric entropy
- Donsker classes of sets
- Donsker classes and random geometry
- Quasi-optimal range searching in spaces of finite VC-dimension
- A generalization of Sauer's lemma
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions
- Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Title not available (Why is that?)
- Existence of submatrices with all possible columns
Cited In (only showing first 100 items - show all)
- Quantitative structure of stable sets in arbitrary finite groups
- Discrepancy, chaining and subgaussian processes
- Metric entropy for functions of bounded total generalized variation
- Making Vapnik-Chervonenkis bounds accurate
- Active learning for cost-sensitive classification
- The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension
- On combinatorial testing problems
- Corrigendum to ``Shifting: One-inclusion mistake bounds and sample compression
- Ramsey properties of algebraic graphs and hypergraphs
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- VC bounds on the cardinality of nearly orthogonal function classes
- Finite sample properties of system identification of ARX models under mixing conditions
- A simple proof of the shallow packing lemma
- Empirical minimization
- Using the doubling dimension to analyze the generalization of learning algorithms
- One-inclusion hypergraph density revisited
- Linear and nonlinear approximation of spherical radial basis function networks
- Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path
- Two proofs for shallow packings
- Nonlinear approximations using sets of finite cardinality or finite pseudo-dimension
- A graph-theoretic generalization of the Sauer-Shelah lemma
- Covering numbers, dyadic chaining and discrepancy
- Convergence of a Least‐Squares Monte Carlo Algorithm for Bounded Approximating Sets
- Convergence of a least-squares Monte Carlo algorithm for American option pricing with dependent sample data
- Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class
- Local Rademacher complexities
- Improved upper bounds for probabilities of uniform deviations
- Vapnik-Chervonenkis density in some theories without the independence property. I
- Optimal adaptive sampling recovery
- On the learnability of rich function classes
- Generalization ability of fractional polynomial models
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
- On weak \(\epsilon\)-nets and the Radon number
- Ranking and empirical minimization of \(U\)-statistics
- Symmetrization approach to concentration inequalities for empirical processes.
- On prediction of individual sequences
- Sharp estimate on the supremum of a class of sums of small i.i.d. random variables
- Covering numbers for bounded variation functions
- A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
- Monte Carlo algorithms for optimal stopping and statistical learning
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Improved bounds on the sample complexity of learning
- A semi-algebraic version of Zarankiewicz's problem
- The Lasso as an \(\ell _{1}\)-ball model selection procedure
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- On finite sets of small tripling or small alternation in arbitrary groups
- Convolutions of sets with bounded VC-dimension are uniformly continuous
- Two-dimensional partial cubes
- Approximation by neural networks and learning theory
- Point sets on the sphere \(\mathbb{S}^{2}\) with small spherical cap discrepancy
- Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary
- Risk bounds for statistical learning
- Prediction, learning, uniform convergence, and scale-sensitive dimensions
- Complexities of convex combinations and bounding the generalization error in classification
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
- Two results about the hypercube
- Constrained versions of Sauer's Lemma
- Bounded \(VC\)-dimension implies the Schur-Erdős conjecture
- Aspects of discrete mathematics and probability in the theory of machine learning
- On weak \(\varepsilon\)-nets and the Radon number
- Shifting: one-inclusion mistake bounds and sample compression
- Theory of Classification: a Survey of Some Recent Advances
- Erdős-Hajnal conjecture for graphs with bounded VC-dimension
- Model selection by bootstrap penalization for classification
- Tractability results for the weighted star-discrepancy
- Bounding embeddings of VC classes into maximum classes
- Bayesian predictiveness, exchangeability and sufficientness in bacterial taxonomy
- Approximation of Sobolev-type classes with quasi-seminorms
- Boosting simple learners
- Probabilistic star discrepancy bounds for double infinite random matrices
- Bracketing entropy and VC-dimension
- On the orders of nonlinear approximations for classes of functions of given form
- Title not available (Why is that?)
- Normal approximations for discrete-time occupancy processes
- Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model
- Teaching and Compressing for Low VC-Dimension
- Optimal approximations made easy
- Nonexact oracle inequalities, \(r\)-learnability, and fast rates
- Optimal adjacency labels for subgraphs of Cartesian products
- On the complexity of constrained VC-classes
- Robust estimation of a regression function in exponential families
- Measuring the capacity of sets of functions in the analysis of ERM
- On the VC-dimension of binary codes
- Spaces of algebraic measure trees and triangulations of the circle
- On the VC-dimension and boolean functions with long runs
- General error estimates for the Longstaff-Schwartz least-squares Monte Carlo algorithm
- Sign rank versus Vapnik-Chervonenkis dimension
- Discrepancy and sparsity
- On the geometry of polytopes generated by heavy-tailed random vectors
- Concentration bounds for the empirical angular measure with statistical learning applications
- An improved bound for regular decompositions of 3-uniform hypergraphs of bounded \(\mathrm{VC}_2\)-dimension
- Model theory and agnostic online learning via excellent sets
- Proof techniques in quasi-Monte Carlo theory
- Learning when-to-treat policies
- On mean estimation for heteroscedastic random variables
- When are epsilon-nets small?
- Entropy, Randomization, Derandomization, and Discrepancy
- Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
- On density of subgraphs of halved cubes
- On the optimality of sample-based estimates of the expectation of the empirical minimizer
This page was built for publication: Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1345876)
