Sparsifying Suprema of Gaussian Processes

Abstract

We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in R^n, and let _t\_t T be the canonical Gaussian process on T. We show that there is an O_(1)-size subset S T and a set of real values _s\_s S such that _s S _s + c_s\ is an -approximator of _t T X_t. Notably, the size of S is completely independent of both the size of T and of the ambient dimension n. We use this to show that every norm is essentially a junta when viewed as a function over Gaussian space: Given any norm (x) on R^n, there is another norm (x) which depends only on the projection of x along O_(1) directions, for which (g) is a multiplicative (1 )-approximation of (g) with probability 1- for g N(0,I_n). We also use our sparsification result for suprema of centered Gaussian processes to give a sparsification lemma for convex sets of bounded geometric width: Any intersection of (possibly infinitely many) halfspaces in R^n that are at distance O(1) from the origin is -close, under N(0,I_n), to an intersection of only O_(1) many halfspaces. We describe applications to agnostic learning and tolerant property testing.

Tasks

Reproductions