Discrepancy, chaining and subgaussian processes

Abstract: We show that for a typical coordinate projection of a subgaussian class of functions, the infimum over signs

i n f_{(e p s i l o n_{i})} s u p_{f i n F} | s u m_{i = 1}^{k} e p s i l o n_{i} f (X_{i}) |

is asymptotically smaller than the expectation over signs as a function of the dimension

k

, if the canonical Gaussian process indexed by

F

is continuous. To that end, we establish a bound on the discrepancy of an arbitrary subset of

m a t h b b R^{k}

using properties of the canonical Gaussian process the set indexes, and then obtain quantitative structural information on a typical coordinate projection of a subgaussian class.

Review text

This paper studies the discrepancy of a typical coordinate projection. Discrepancy of a class of functions \(F\) was introduced in a combinatorial context and is defined as follows \[ \text{disc} (F)=\inf_{\varepsilon_j}\sup_{f\in F}\left|\sum\limits^k_{j=1}\varepsilon_jf(x_j)\right| \] where \((\varepsilon_j)^k_{j=1}\in\{-1, 1\}^k\). The main result is that, if the canonical Gaussian process indexed by \(F\) is continuous and if the class satisfies a sub-Gaussian condition, then disc\((F)\) is asymptotically smaller than the expectation over signs as a function of the dimension \(k\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Discrepancy, chaining and subgaussian processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533745)