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

DOI10.1016/0097-3165(95)90052-7zbMath0818.60005OpenAlexW2058239479MaRDI 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

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

Related Items

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

Cites Work