Sparsifying Suprema of Gaussian Processes

We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in ℝn, and let boldsymbolXt := t · boldsymbolg t∈ T be the canonical Gaussian process on T, where boldsymbolg~ N(0, In). We show that there is an O_varepsilon(1)-size subset S subseteq T and a set of real values css ∈ S such that the random variable sups ∈ S boldsymbolXs + cs is an varepsilon-approximator,(in L1) of the random variable supt ∈ T boldsymbolXt. Notably, the size of the sparsifier S is completely independent of both |T| and the ambient dimension n. We give two applications of this sparsification theorem: - A "Junta Theorem" for Norms: We show that given any norm nu(x) on ℝn, there is another norm psi(x) depending only on the projection of x onto O_varepsilon(1) directions, for which psi(boldsymbolg) is a multiplicative (1 ± varepsilon)-approximation of nu(boldsymbolg) with probability 1-varepsilon for boldsymbolg ~ N(0,In). - Sparsification of Convex Sets: We show that any intersection of (possibly infinitely many) halfspaces in ℝn that are at distance r from the origin is varepsilon-close (under N(0,In)) to an intersection of only Or,varepsilon(1) halfspaces. This yields new polynomial-time agnostic learning and tolerant property testing algorithms for intersections of halfspaces.