Rocco Servedio: Sparsifying suprema of Gaussian processes скачать в хорошем качестве

Rocco Servedio: Sparsifying suprema of Gaussian processes

We show that the supremum of any centered Gaussian process can be approximated to any arbitrary accuracy by a finite dimensional Gaussian process, where the dimension of the approximator is just dependent on the target error. As a corollary, we show that for any norm Φ defined over R^n and target error ε, there is a norm Ψ such that (i) Ψ is only dependent on t(ε) = exp exp(poly(1/ε)) dimensions and (ii) Ψ(x)/Φ(x) ∈ [1 − ε, 1 + ε] with probability 1 − ε (when x is sampled from the Gaussian space). We prove a similar-in-spirit result for sparsifying high-dimensional polytopes in Gaussian space, and present applications to computational learning and property testing. Our proof relies on Talagrand's majorizing measures theorem. Joint work with Anindya De, Shivam Nadimpalli, and Ryan O'Donnell.