Combinatorial-dimension characterization of universal Donsker classes
Combinatorial-dimension characterization of universal Donsker classes
Let be a uniformly bounded class of functions, and let denote its combinatorial dimension at scale : the maximal cardinality of a subset that is -shattered by . 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 ,
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.