ShowMe Analysis Meeting 2005
May 16, 2005
University of Missouri

Mark Rudelson, University of Missouri
Combinatorial dimension as a measure of complexity

Abstract: Let X1 . . . XN be independent identically distributed random variables taking values in a set Y. Then for a bounded function $f:Y\to \mathbb{R}$ the random variable $\frac{1}{N}(f(X_1)+\dots +X_n)$ converges to the average value of f(X1) (the Law of Large Numbers) and the random variable $\frac{1}{\sqrt{N}}\sum^N_{j=1}(f(X_J)-\int f(X_j))$ converges to a normaldistribution (the Central Limit Theorem).

Let now F be a set of bounded functions $f:Y\to \mathbb{R}$. An important question in probability and empirical process theory is whether the convergence in the Law of Large Numbers and the Central Limit Theorem is uniform with respect to $f\in F$. The answer depends on the complexity of the function class F. We show that this complexity can be characterized in terms of the combinatorial dimension of F. This notion of dimension arises in different areas of mathematics, such as probability (Pollard, Talagrand), combinatorics (Alon, Haussler), as well as in computer science. It allows to solve several basic questions in combinatorics of random processes.

The combinatorial dimension approach leads also to new results in convex geometry (Coordinate Dvoretzky-type theorem) as well as in operator theory (generalized Bourgain--Tzafriri restricted invertibility principle). The connection with Computer Science (Learning Theory) will be also discussed.