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 {t := t · g }t∈ T be the canonical Gaussian process on T, where g∼ N(0, In). We show that there is an Oε(1)-size subset S ⊆ T and a set of real values {cs}s ∈ S such that the random variable sups ∈ S {Xs + cs} is an ε-approximator (in L1) of the random variable supt ∈ T Xt. 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 ν(x) on n, there is another norm ψ(x) depending only on the projection of x onto Oε(1) directions, for which ψ(g) is a multiplicative (1 ± ε)-approximation of ν(g) with probability 1−ε for g ∼ 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 ε-close (under N(0,In)) to an intersection of only Or,ε(1) halfspaces. This yields new polynomial-time agnostic learning and tolerant property testing algorithms for intersections of halfspaces.