Combinatorics of random processes and sections of convex bodies

We find a sharp combinatorial bound for the metric entropy of sets in R n and general classes of functions. This solves two basic combinatorial conjectures on the empirical processes. 1. A class of functions satisfies the uniform Central Limit Theorem if the square root of its combinatorial dimension is integrable. 2. The uniform entropy is equivalent to the combinatorial dimension under minimal regularity. Our method also constructs a nicely bounded coordinate section of a symmetric convex body in R n . In the operator theory, this essentially proves for all normed spaces the restricted invertibility principle of Bourgain and Tzafriri.

• Publication year

  2004

• Venue

  Annals of Mathematics

• Publication date

  2004-04-08

• Fields of study

  Mathematics

• Identifiers
  DOI 10.4007/ANNALS.2006.164.603arXiv math/0404192
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• LECTURES ON DISCRETE GEOMETRY (Graduate Texts in Mathematics 212)

  2003cited by this paper
• Vapnik--Chervonenkis type conditions and uniform Donsker classes of functions

  2003cited by this paper
• Entropy, Combinatorial Dimensions and Random Averages

  2002cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• Entropy and the combinatorial dimension

  2002cited by this paper
• Uniform Central Limit Theorems

  2001cited by this paper
• On directional convexity

  2001cited by this paper
• Uniform Central Limit Theorems: Contents

  1999influential reference
• Neural Network Learning: Theoretical Foundations

  1999cited by this paper
• Prediction, Learning, Uniform Convergence, and Scale-Sensitive Dimensions

  1998influential reference
• On the Convexified Sauer-Shelah Theorem

  1997cited by this paper
• A Remark on the Szarek–Talagrand Theorem

  1997cited by this paper
• Covering numbers for real-valued function classes

  1997influential reference
• The Glivenko-Cantelli problem, ten years later

  1996cited by this paper
• A Generalization of Sauer's Lemma

  1995cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• Scale-sensitive dimensions, uniform convergence, and learnability

  1993influential reference
• Type, infratype and the Elton-Pajor theorem

  1992cited by this paper
• THE VOLUME OF CONVEX BODIES AND BANACH SPACE GEOMETRY (Cambridge Tracts in Mathematics 94)

  1991cited by this paper
• On a problem of Kadison and Singer.

  1991cited by this paper
• GAUSSIAN CHARACTERIZATION OF UNIFORM DONSKER CLASSES OF FUNCTIONS

  1991influential reference
• Unsolved Problems In Geometry

  1991cited by this paper
• Efficient distribution-free learning of probabilistic concepts

  1990cited by this paper
• Generalizing the PAC model: sample size bounds from metric dimension-based uniform convergence results

  1989cited by this paper
• Banach-Mazur distances and finite-dimensional operator ideals

  1989cited by this paper
• The volume of convex bodies and Banach space geometry

  1989influential reference
• The Glivenko-Cantelli Problem

  1987cited by this paper
• Invertibility of ‘large’ submatrices with applications to the geometry of Banach spaces and harmonic analysis

  1987cited by this paper
• ASYMPTOTIC THEORY OF FINITE DIMENSIONAL NORMED SPACES (Lecture Notes in Mathematics 1200)

  1987cited by this paper
• Asymptotic Theory Of Finite Dimensional Normed Spaces

  1986cited by this paper
• Convergence of stochastic processes

  1984cited by this paper
• Sign-Embeddings of l n 1

  1983cited by this paper
• Sign-embeddings of ⁿ₁

  1983cited by this paper
• Central Limit Theorems for Empirical Measures

  1978cited by this paper
• Probability on Banach spaces

  1978cited by this paper
• DIAMETERS OF SOME FINITE-DIMENSIONAL SETS AND CLASSES OF SMOOTH FUNCTIONS

  1977cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper

• Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means

  2025influential citation
• Consistency and Rate of Convergence for Deep ReLU Neural Networks

  2025influential citation
• Improved Margin Generalization Bounds for Voting Classifiers

  2025influential citation
• A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity

  2025cites this paper
• Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks

  2025cites this paper
• Revisiting Agnostic Boosting

  2025influential citation
• Oracle-Efficient Differentially Private Learning with Public Data

  2024cites this paper
• Adversarially Robust Multi-task Representation Learning

  2024influential citation
• Optimal PAC Bounds without Uniform Convergence

  2023influential citation
• A Characterization of Multioutput Learnability

  2023cites this paper
• The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning

  2023cites this paper
• GRAND-SLAMIN' Interpretable Additive Modeling with Structural Constraints

  2023influential citation
• An Improved Uniform Convergence Bound with Fat-Shattering Dimension

  2023influential citation
• Online Learning and Solving Infinite Games with an ERM Oracle

  2023cites this paper
• Smoothed Analysis of Sequential Probability Assignment

  2023influential citation
• Adversarially Robust Learning of Real-Valued Functions

  2022cites this paper
• Stochastic Strategic Patient Buyers: Revenue maximization using posted prices

  2022cites this paper
• Smoothed Online Learning is as Easy as Statistical Learning

  2022cites this paper
• Adversarially Robust PAC Learnability of Real-Valued Functions

  2022influential citation
• Learning Revenue Maximization Using Posted Prices for Stochastic Strategic Patient Buyers

  2022cites this paper
• Fat-Shattering Dimension of k-fold Aggregations

  2021cites this paper
• Fat-shattering dimension of k-fold maxima

  2021cites this paper
• A class of dimension-free metrics for the convergence of empirical measures

  2021cites this paper
• Analysis

  2021cites this paper
• Majorizing Measures, Sequential Complexities, and Online Learning

  2021influential citation
• IDS.160 – Mathematical Statistics: A Non-Asymptotic Approach

  2020cites this paper
• Nearly Optimal Clustering Risk Bounds for Kernel K-Means

  2020cites this paper
• IDS.160 – Mathematical Statistics: A Non-Asymptotic Approach

  2020cites this paper
• $\ell_{\infty}$ Vector Contraction for Rademacher Complexity

  2019cites this paper
• Optimization and statistical learning theory for piecewise smooth and switching regression. (Optimisation et théorie statistique de l'apprentissage pour la régression douce par morceaux et à commutations)

  2019cites this paper
• Sample Compression for Real-Valued Learners

  2018influential citation
• Combinatorial and Structural Results for γ-Ψ-dimensions

  2018influential citation
• Adaptive risk bounds in univariate total variation denoising and trend filtering

  2017influential citation
• Generalized dual Sudakov minoration via dimension-reduction—a program

  2016cites this paper
• Sequential complexities and uniform martingale laws of large numbers

  2015cites this paper
• Dvoretzky Type Theorems for Subgaussian Coordinate Projections

  2015influential citation
• On Martingale Extensions of Vapnik–Chervonenkis Theory with Applications to Online Learning

  2015cites this paper
• Measures of Complexity

  2015cites this paper
• Estimation in High Dimensions: A Geometric Perspective

  2014cites this paper
• Estimation in High Dimensions : a Geometric

  2014cites this paper
• Dvoretzky Type Theorems for Subgaussian Coordinate Projections

  2014influential citation
• Statistical Learning and Sequential Prediction

  2014cites this paper
• Sequential complexities and uniform martingale laws of large numbers

  2014cites this paper
• Testing the Manifold Hypothesis

  2013cites this paper
• Oracle inequalities and the isomorphic method

  2012influential citation
• ON THE OPTIMALITY OF SAMPLE-BASED ESTIMATES OF THE EXPECTATION OF THE EMPIRICAL MINIMIZER ∗, ∗∗

  2010cites this paper
• Поперечники, связанные с псевдоразмерностью@@@Widths related to pseudo-dimension

  2009cites this paper
• Верхние оценки погрешности оценщиков в задаче непараметрической регрессии: адаптивный случай и случай неизвестной меры $\rho_X$@@@Upper Bounds for Errors of Estimators in a Problem of Nonparametric Regression: The Adaptive Case and the Case of Unknown Measure $\rho_X$

  2009cites this paper
• Upper bounds for errors of estimators in a problem of nonparametric regression: the adaptive case and the case of unknown measure ρX

  2009influential citation
• Widths related to pseudo-dimension

  2009cites this paper
• Widths related to pseudo-dimension

  2009cites this paper
• Stability Properties of Empirical Risk Minimization over Donsker Classes

  2006cites this paper
• Applications of empirical processes in learning theory: algorithmic stability and generalization bounds

  2006cites this paper
• Optimal Sample-Based Estimates of the Expectation of the Empirical Minimizer

  2005cites this paper
• Data-Dependent Analysis of Learning Algorithms

  2005cites this paper
• Some Properties of Empirical Risk Minimization Over Donsker Classes

  2005cites this paper
• Entropy estimate for high-dimensional monotonic functions

  2005cites this paper
• Embedding with a Lipschitz function

  2005cites this paper
• Some Properties of Empirical Risk Minimization

  2005cites this paper
• Three-query PCPs with perfect completeness over non-Boolean domains

  2005cites this paper
• Theory of classification : a survey of some recent advances

  2005cites this paper
• Random processes via the combinatorial dimension: introductory notes

  2004cites this paper
• Asymptotic Convex Geometry Short Overview

  2004cites this paper
• Integer cells in convex sets

  2004cites this paper