Combinatorics of random processes and sections of convex bodies

DOI10.4007/ANNALS.2006.164.603zbMATH Open1114.60009arXivmath/0404192OpenAlexW2133442019MaRDI QIDQ863631FDOQ863631

Authors: Mark Rudelson, Roman Vershynin 

Publication date: 5 February 2007

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Abstract: 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.

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

Recommendations

• Entropy and the combinatorial dimension
• Gaussian processes and almost spherical sections of convex bodies
• scientific article; zbMATH DE number 2089351
• Empirical processes and random projections
• scientific article; zbMATH DE number 17995

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial probability (60C05)

Cited In (23)

• On the expected number of linear complementarity cones intersected by random and semi-random rays
• Testing the manifold hypothesis
• Integer cells in convex sets
• Adaptive risk bounds in univariate total variation denoising and trend filtering
• Upper bounds for errors of estimators in a problem of nonparametric regression: the adaptive case and the case of unknown measure \(\rho _X\)
• Combinatorial sublinear-time Fourier algorithms
• Embedding with a Lipschitz function
• Sequential complexities and uniform martingale laws of large numbers
• Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
• Entropy and the combinatorial dimension
• A class of dimension-free metrics for the convergence of empirical measures
• Random combinatorial structures: the convergent case
• The convex geometry of linear inverse problems
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Entropy estimate for high-dimensional monotonic functions
• Deep learning: a statistical viewpoint
• Dvoretzky type theorems for subgaussian coordinate projections
• An improved uniform convergence bound with fat-shattering dimension
• Estimation in high dimensions: a geometric perspective
• On the optimality of sample-based estimates of the expectation of the empirical minimizer
• Title not available (Why is that?)
• Theory of Classification: a Survey of Some Recent Advances
• On martingale extensions of Vapnik-Chervonenkis theory with applications to online learning

This page was built for publication: Combinatorics of random processes and sections of convex bodies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q863631)