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-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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial probability (60C05) Combinatorial aspects of packing and covering (05B40)
Related Items (92)
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
- The complexity and construction of many faces in arrangements of lines and of segments
- Some limit theorems for empirical processes (with discussion)
- \(\epsilon\)-nets and simplex range queries
- Donsker classes of sets
- Universal Donsker classes and metric entropy
- The Glivenko-Cantelli problem
- Donsker classes and random geometry
- Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
- Colorings and orientations of graphs
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Existence of submatrices with all possible columns
- Central limit theorems for empirical measures
- Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension
- Sharper bounds for Gaussian and empirical processes
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the trace of finite sets
- Density and dimension
- Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions
- A generalization of Sauer's lemma
- Induced subsets
- On the density of families of sets
- Learnability and the Vapnik-Chervonenkis dimension
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Convergence of stochastic processes
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
