Combinatorial-dimension characterization of universal Donsker classes

About 22 years old · traced to

Let FF be a uniformly bounded class of functions, and let v(F,t){\it v}(F,t) denote its combinatorial dimension at scale t≥0t\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,

∫0∞v(F,t) dt<∞⇒F is universal Donsker⇒v(F,t)=O(t−2).\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.

References

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.