Sparsification of Gaussian Processes

In this talk, we will 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 \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 Gaussian space). Our proof relies on Talagrand's majorizing measures theorem. 

Joint work with Shivam Nadimpalli, Ryan O'Donnell and Rocco Servedio.