Entropy and the combinatorial dimension
From MaRDI portal
Abstract: We solve Talagrand's entropy problem: the L_2-covering numbers of every uniformly bounded class of functions are exponential in its shattering dimension. This extends Dudley's theorem on classes of {0,1}-valued functions, for which the shattering dimension is the Vapnik-Chervonenkis dimension. In convex geometry, the solution means that the entropy of a convex body K is controlled by the maximal dimension of a cube of a fixed side contained in the coordinate projections of K. This has a number of consequences, including the optimal Elton's Theorem and estimates on the uniform central limit theorem in the real valued case.
Talagrand's entropy problem is solved. Dudley's theorem on classes of {0,1}-valued functions, for which the shattering dimension is the Vapnik-Chervonenkis dimension, is extended.
Recommendations
Cited in
(38)- Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions
- The shattering dimension of sets of linear functionals.
- Remarks on the geometry of coordinate projections in \(\mathbb{R}^n\)
- The universal Glivenko-Cantelli property
- Clustering of measures via mean measure quantization
- Statistical analysis of Mapper for stochastic and multivariate filters
- Almost optimal estimates for approximation and learning by radial basis function networks
- Sequential complexities and uniform martingale laws of large numbers
- Estimates of covering numbers of convex sets with slowly decaying orthogonal subsets
- \(L_{p}\)-norm Sauer-Shelah lemma for margin multi-category classifiers
- Approximation by neural networks and learning theory
- Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary
- Integer cells in convex sets
- Entropy dimensions and a class of constructive examples
- On martingale extensions of Vapnik-Chervonenkis theory with applications to online learning
- Measuring the capacity of sets of functions in the analysis of ERM
- Bounds for stochastic processes on product index spaces
- scientific article; zbMATH DE number 2089351 (Why is no real title available?)
- Theory of Classification: a Survey of Some Recent Advances
- VC bounds on the cardinality of nearly orthogonal function classes
- Entropy of theK-Satisfiability Problem
- Combinatorial Entropy and the Statistical Mechanics of Polydispersity
- Optimal rates of convergence for convex set estimation from support functions
- Outlaw distributions and locally decodable codes
- Discrepancy, chaining and subgaussian processes
- scientific article; zbMATH DE number 6400769 (Why is no real title available?)
- Adaptive metric dimensionality reduction
- Comments on: Support vector machines maximizing geometric margins for multi-class classification
- VC dimensions of principal component analysis
- Learning ability of interpolating deep convolutional neural networks
- Widths and rigidity
- Statistical learning on measures: an application to persistence diagrams
- Isotropic kernel machine
- Sample compression for real-valued learners
- Improved generalization bounds for robust learning
- Upper bounds for errors of estimators in a problem of nonparametric regression: the adaptive case and the case of unknown measure \(\rho _X\)
- Combinatorics of random processes and sections of convex bodies
- Entropy extension
This page was built for publication: Entropy and the combinatorial dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1396675)
