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

DOI10.1016/0097-3165(95)90052-7zbMath0818.60005MaRDI QIDQ1345876

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 processes; Vapnik-Chervonenkis dimension

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

60C05: Combinatorial probability

05B40: Combinatorial aspects of packing and covering

Related Items

On the VC-Dimension of Binary Codes, Teaching and Compressing for Low VC-Dimension, Sign rank versus Vapnik-Chervonenkis dimension, CONVERGENCE OF A LEAST‐SQUARES MONTE CARLO ALGORITHM FOR AMERICAN OPTION PRICING WITH DEPENDENT SAMPLE DATA, Metric Entropy for Functions of Bounded Total Generalized Variation, Spaces of algebraic measure trees and triangulations of the circle, On finite sets of small tripling or small alternation in arbitrary groups, Unnamed Item, Entropy, Randomization, Derandomization, and Discrepancy, Finite sample properties of system identification of ARX models under mixing conditions, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, Improved bounds on the sample complexity of learning, Nonlinear approximations using sets of finite cardinality or finite pseudo-dimension, Learning When-to-Treat Policies, A simple proof of the shallow packing lemma, Linear and nonlinear approximation of spherical radial basis function networks, Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class, VC bounds on the cardinality of nearly orthogonal function classes, Generalization ability of fractional polynomial models, Discrepancy, chaining and subgaussian processes, Monte Carlo algorithms for optimal stopping and statistical learning, On combinatorial testing problems, Optimal adaptive sampling recovery, Covering numbers, dyadic chaining and discrepancy, Two proofs for shallow packings, Two-dimensional partial cubes, Risk bounds for statistical learning, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, Sharp estimate on the supremum of a class of sums of small i.i.d. random variables, Using the doubling dimension to analyze the generalization of learning algorithms, Constrained versions of Sauer's Lemma, Corrigendum to ``Shifting: One-inclusion mistake bounds and sample compression, One-inclusion hypergraph density revisited, Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path, A graph-theoretic generalization of the Sauer-Shelah lemma, The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension, Prediction, learning, uniform convergence, and scale-sensitive dimensions, On the learnability of rich function classes, Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, Symmetrization approach to concentration inequalities for empirical processes., On prediction of individual sequences, Bayesian predictiveness, exchangeability and sufficientness in bacterial taxonomy, Localization of VC classes: beyond local Rademacher complexities, Covering numbers for bounded variation functions, Improved upper bounds for probabilities of uniform deviations, Point sets on the sphere \(\mathbb{S}^{2}\) with small spherical cap discrepancy, The Lasso as an \(\ell _{1}\)-ball model selection procedure, Normal approximations for discrete-time occupancy processes, On weak \(\epsilon\)-nets and the Radon number, Tractability results for the weighted star-discrepancy, When are epsilon-nets small?, On density of subgraphs of halved cubes, Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model, Proof techniques in quasi-Monte Carlo theory, Model selection by bootstrap penalization for classification, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, Ranking and empirical minimization of \(U\)-statistics, Bracketing entropy and VC-dimension, Aspects of discrete mathematics and probability in the theory of machine learning, On the complexity of constrained VC-classes, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, Approximation by neural networks and learning theory, Empirical minimization, Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary, Shifting: one-inclusion mistake bounds and sample compression, Approximation of Sobolev-type classes with quasi-seminorms, Bounds and constructions for the star-discrepancy via \(\delta\)-covers, On the orders of nonlinear approximations for classes of functions of given form, Complexities of convex combinations and bounding the generalization error in classification, Local Rademacher complexities, A semi-algebraic version of Zarankiewicz's problem, Vapnik-Chervonenkis density in some theories without the independence property, I, Making Vapnik–Chervonenkis Bounds Accurate, Measuring the Capacity of Sets of Functions in the Analysis of ERM, Bounding Embeddings of VC Classes into Maximum Classes, Probabilistic Star Discrepancy Bounds for Double Infinite Random Matrices, On the Optimality of Sample-Based Estimates of the Expectation of the Empirical Minimizer, Theory of Classification: a Survey of Some Recent Advances, General Error Estimates for the Longstaff–Schwartz Least-Squares Monte Carlo Algorithm, Convergence of a Least‐Squares Monte Carlo Algorithm for Bounded Approximating Sets, On the VC-dimension and boolean functions with long runs

Cites Work