We show that the supremum of any centered Gaussian processcan be approximated to any arbitrary accuracy by a finite dimensional Gaussian process, where the dimension of the approximator is justdependent on the target error. As a corollary, we show that for any norm \Phi defined over R^n and target error \eps, there is a norm \Psi such that (i) \Psi is only dependent on t(\eps) = \exp (\exp(poly(1/\eps))) dimensions and (ii) \Psi(x)/\Phi(x) \in [1-\eps, 1+\eps] with probability 1-\eps (when x is sampled from the Gaussianspace). 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 Shivam Nadimpalli, Ryan O'Donnell and Rocco Servedio.
