Combinatorial-dimension characterization of universal Donsker classes

Let FF be a uniformly bounded class of functions, and let v(F,t){\it v}(F,t) denote its combinatorial dimension at scale t0t\geq 0: the maximal cardinality of a subset that is tt-shattered by FF. A class is universal Donsker when it is Donsker for every probability law, uniformly over all such laws.

Combinatorial-dimension conjecture. For every uniformly bounded class FF,

0v(F,t)dt<F is universal Donskerv(F,t)=O(t2).\int_0^\infty \sqrt{{\it v}(F,t)}\,dt<\infty \quad\Rightarrow\quad F\text{ is universal Donsker} \quad\Rightarrow\quad {\it v}(F,t)=O(t^{-2}).

The conjecture proposes an optimal description of universal Donsker classes in terms of how much the class oscillates. The first implication gives a sufficient integrability condition, while the second gives a necessary polynomial bound on the combinatorial dimension; the source does not state that either implication is resolved in full generality.

Sources & referencesView supporting material

Primary source

Mark Rudelson and Roman Vershynin, “Random processes via the combinatorial dimension: introductory notes”, arXiv:math/0404193 (2004).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.