Combinatorics of random processes and sections of convex bodies
From MaRDI portal
(Redirected from Publication:863631)
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.
Recommendations
Cited in
(23)- On martingale extensions of Vapnik-Chervonenkis theory with applications to online learning
- 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
- Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
- Sequential complexities and uniform martingale laws of large numbers
- Entropy and the combinatorial dimension
- Random combinatorial structures: the convergent case
- A class of dimension-free metrics for the convergence of empirical measures
- 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
- 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: 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)
