Combinatorics of random processes and sections of convex bodies
By Mark Rudelson, Roman Vershynin. 2004
66 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/fed5c08e85992f77a68d55aade3229cde68e586d
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Karthik Sridharan
- Alexander Rakhlin
- Ohad Shamir
- Ambuj Tewari
- Nati Srebro
- Gábor Lugosi
- David Lopez-Paz
- Peter Richtárik
In Computer Networks and Communications
- Alexander Rakhlin
- Sanjoy K. Mitter
- Olivier Bousquet
- Gábor Lugosi
- Charles Fefferman
- Ambuj Tewari
- Karthik Sridharan
- Ian Osband
In Statistics and Probability
- Stéphane Boucheron
- Gábor Lugosi
- Olivier Bousquet
- Alexander Rakhlin
- Sanjoy K. Mitter
- Hariharan Narayanan
- Karthik Sridharan
- Ambuj Tewari
Citations in the corpus
- Testing the Manifold Hypothesis (2013, background): “1, page 35 [48]) tells us that the integral in (149) can be bounded from above using an integral involving the square root of the fat shattering dimension (or in their terminology, combinatorial dimension).”
- Theory of classification : a survey of some recent advances (2005, result): “A few key references include Vapnik and Chervonenkis [232] [234], Dudley [79] [81] [82], Talagrand [211] [212] [214] [218], Dudley, Giné, and Zinn [84], Alon, Ben-David, Cesa-Bianchi, and Haussler [8], Li, Long, and Srinivasan [138], Mendelson and Vershynin [173].”
- Sequential complexities and uniform martingale laws of large numbers (2015, background): “It is interesting to note that the clean upper bound of Corollary 6 is not yet known for the classical case of `∞ covering numbers (see [25]).”