Entropy and the combinatorial dimension

DOI10.1007/S00222-002-0266-3MaRDI QIDQ1396675zbMATH OpenOpenAlexFDO

Authors Shahar Mendelson, Roman Vershynin

Publication date 8 July 2003

Published in Inventiones Mathematicae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0203275

Mathematics Subject Classification ID

Probability theory on linear topological spaces (60B11) Geometric probability and stochastic geometry (60D05) Inequalities; stochastic orderings (60E15)

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.

Recommendations

• scientific article; zbMATH DE number 2089351
• Combinatorics of random processes and sections of convex bodies
• scientific article; zbMATH DE number 17995
• Covering numbers of \(L_{p}\)-balls of convex functions and sets
• Entropy extension

Cited in

(34)

• On martingale extensions of Vapnik-Chervonenkis theory with applications to online learning
• Entropy of theK-Satisfiability Problem
• Discrepancy, chaining and subgaussian processes
• The universal Glivenko-Cantelli property
• Integer cells in convex sets
• VC bounds on the cardinality of nearly orthogonal function classes
• Upper bounds for errors of estimators in a problem of nonparametric regression: the adaptive case and the case of unknown measure \(\rho _X\)
• The shattering dimension of sets of linear functionals.
• Adaptive metric dimensionality reduction
• Almost optimal estimates for approximation and learning by radial basis function networks
• Bounds for stochastic processes on product index spaces
• Measuring the capacity of sets of functions in the analysis of ERM
• Combinatorial Entropy and the Statistical Mechanics of Polydispersity
• Comments on: Support vector machines maximizing geometric margins for multi-class classification
• Outlaw distributions and locally decodable codes
• Sequential complexities and uniform martingale laws of large numbers
• Optimal rates of convergence for convex set estimation from support functions
• scientific article; zbMATH DE number 6400769 (Why is no real title available?)
• Remarks on the geometry of coordinate projections in \(\mathbb{R}^n\)
• VC dimensions of principal component analysis
• Learning ability of interpolating deep convolutional neural networks
• Clustering of measures via mean measure quantization
• Widths and rigidity
• Entropy dimensions and a class of constructive examples
• \(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
• Statistical analysis of Mapper for stochastic and multivariate filters
• Combinatorics of random processes and sections of convex bodies
• Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions
• Estimates of covering numbers of convex sets with slowly decaying orthogonal subsets
• Entropy extension
• scientific article; zbMATH DE number 2089351 (Why is no real title available?)
• Theory of Classification: a Survey of Some Recent Advances

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)