# Sparsifying Suprema of Gaussian Processes

arXiv: https://arxiv.org/abs/2411.14664 · HTML: https://mlsanity.com/paper/2411.14664/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 68 references that are in the map.
- First posted on arXiv 22 Nov 2024.

## Builds on (most cited first, 17 of 17)

- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/1807.04974/) (2018)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees](https://mlsanity.com/paper/1304.0730/) (2013)
- [Isometric sketching of any set via the Restricted Isometry Property](https://mlsanity.com/paper/1506.03521/) (2015)
- [Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas](https://mlsanity.com/paper/1307.3301/) (2013)
- [Robust testing of low-dimensional functions](https://mlsanity.com/paper/2004.11642/) (2020)
- [Towards Tight Bounds for Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/2011.06530/) (2020)
- [Majorizing Measures for the Optimizer](https://mlsanity.com/paper/2012.13306/) (2020)
- [Sparsifying sums of norms](https://mlsanity.com/paper/2305.09049/) (2023)
- [New Notions and Constructions of Sparsification for Graphs and Hypergraphs](https://mlsanity.com/paper/1905.01495/) (2019)
- [Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification](https://mlsanity.com/paper/2209.10539/) (2022)
- [Sketching Cuts in Graphs and Hypergraphs](https://mlsanity.com/paper/1409.2391/) (2014)
- [Beating CountSketch for Heavy Hitters in Insertion Streams](https://mlsanity.com/paper/1511.00661/) (2015)
- [Spectral hypergraph sparsification via chaining](https://mlsanity.com/paper/2209.04539/) (2022)
- [Lower Bounds for Convexity Testing](https://mlsanity.com/paper/2410.17958/) (2024)
- [Efficient Algorithms and New Characterizations for CSP Sparsification](https://mlsanity.com/paper/2404.06327/) (2024)

## Abstract (arXiv)

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.