Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension

DOI10.1016/0097-3165(95)90052-7MaRDI QIDQ1345876zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

empirical processesVapnik-Chervonenkis dimension

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial probability (60C05) Combinatorial aspects of packing and covering (05B40)

Recommendations

• Density and dimension
• The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension
• Almost tight bounds for -nets
• On intersecting a point set with Euclidean balls
• VC dimension and a union theorem for set systems

Cites work

• scientific article; zbMATH DE number 3883309 (Why is no real title available?)
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 50933 (Why is no real title available?)
• scientific article; zbMATH DE number 51427 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• A generalization of Sauer's lemma
• Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension
• Central limit theorems for empirical measures
• Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions
• Colorings and orientations of graphs
• Convergence of stochastic processes
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Density and dimension
• Donsker classes and random geometry
• Donsker classes of sets
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Existence of submatrices with all possible columns
• Induced subsets
• Learnability and the Vapnik-Chervonenkis dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• On the trace of finite sets
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Quasi-optimal range searching in spaces of finite VC-dimension
• Sharper bounds for Gaussian and empirical processes
• Some limit theorems for empirical processes (with discussion)
• The Glivenko-Cantelli problem
• The complexity and construction of many faces in arrangements of lines and of segments
• Universal Donsker classes and metric entropy
• -nets and simplex range queries

Cited in

(only showing first 100 items - show all)

• Bayesian predictiveness, exchangeability and sufficientness in bacterial taxonomy
• Approximation of Sobolev-type classes with quasi-seminorms
• Probabilistic star discrepancy bounds for double infinite random matrices
• Quantitative structure of stable sets in arbitrary finite groups
• Bracketing entropy and VC-dimension
• Boosting simple learners
• Discrepancy, chaining and subgaussian processes
• On the orders of nonlinear approximations for classes of functions of given form
• Making Vapnik-Chervonenkis bounds accurate
• Metric entropy for functions of bounded total generalized variation
• The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension
• Normal approximations for discrete-time occupancy processes
• On combinatorial testing problems
• scientific article; zbMATH DE number 7561386 (Why is no real title available?)
• Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model
• Active learning for cost-sensitive classification
• Corrigendum to ``Shifting: One-inclusion mistake bounds and sample compression
• Optimal approximations made easy
• Teaching and Compressing for Low VC-Dimension
• VC bounds on the cardinality of nearly orthogonal function classes
• Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
• Ramsey properties of algebraic graphs and hypergraphs
• Nonexact oracle inequalities, \(r\)-learnability, and fast rates
• A simple proof of the shallow packing lemma
• Finite sample properties of system identification of ARX models under mixing conditions
• On the complexity of constrained VC-classes
• Optimal adjacency labels for subgraphs of Cartesian products
• Robust estimation of a regression function in exponential families
• Empirical minimization
• Measuring the capacity of sets of functions in the analysis of ERM
• 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
• A graph-theoretic generalization of the Sauer-Shelah lemma
• Covering numbers, dyadic chaining and discrepancy
• Nonlinear approximations using sets of finite cardinality or finite pseudo-dimension
• Convergence of a Least‐Squares Monte Carlo Algorithm for Bounded Approximating Sets
• Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class
• On the VC-dimension of binary codes
• Convergence of a least-squares Monte Carlo algorithm for American option pricing with dependent sample data
• Spaces of algebraic measure trees and triangulations of the circle
• 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 VC-dimension and boolean functions with long runs
• General error estimates for the Longstaff-Schwartz least-squares Monte Carlo algorithm
• On the learnability of rich function classes
• Sign rank versus Vapnik-Chervonenkis dimension
• Generalization ability of fractional polynomial models
• Discrepancy and sparsity
• 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
• On the geometry of polytopes generated by heavy-tailed random vectors
• Sharp estimate on the supremum of a class of sums of small i.i.d. random variables
• Concentration bounds for the empirical angular measure with statistical learning applications
• Covering numbers for bounded variation functions
• 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
• Monte Carlo algorithms for optimal stopping and statistical learning
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• A semi-algebraic version of Zarankiewicz's problem
• The Lasso as an \(\ell _{1}\)-ball model selection procedure
• Improved bounds on the sample complexity of learning
• Proof techniques in quasi-Monte Carlo theory
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• Two-dimensional partial cubes
• On finite sets of small tripling or small alternation in arbitrary groups
• Convolutions of sets with bounded VC-dimension are uniformly continuous
• Approximation by neural networks and learning theory
• Learning when-to-treat policies
• Point sets on the sphere \(\mathbb{S}^{2}\) with small spherical cap discrepancy
• On mean estimation for heteroscedastic random variables
• Risk bounds for statistical learning
• Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary
• Prediction, learning, uniform convergence, and scale-sensitive dimensions
• When are epsilon-nets small?
• Complexities of convex combinations and bounding the generalization error in classification
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• Entropy, Randomization, Derandomization, and Discrepancy
• On density of subgraphs of halved cubes
• Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
• On the optimality of sample-based estimates of the expectation of the empirical minimizer
• 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
• Shifting: one-inclusion mistake bounds and sample compression
• Model selection by bootstrap penalization for classification
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Theory of Classification: a Survey of Some Recent Advances
• Tractability results for the weighted star-discrepancy
• On weak \(\varepsilon\)-nets and the Radon number
• Bounding embeddings of VC classes into maximum classes

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)