SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications

Abstract

We prove that there is a universal constant C>0 so that for every d ∈ ℕ, every centered subgaussian distribution D on ℝd, and every even p ∈ ℕ, the d-variate polynomial (Cp)p/2 · ||v||2p − EX ∼ D ⟨ v,X⟩p is a sum of square polynomials. This establishes that every subgaussian distribution is SoS-certifiably subgaussian—a condition that yields efficient learning algorithms for a wide variety of high-dimensional statistical tasks. As a direct corollary, we obtain computationally efficient algorithms with near-optimal guarantees for the following tasks, when given samples from an arbitrary subgaussian distribution: robust mean estimation, list-decodable mean estimation, clustering mean-separated mixture models, robust covariance-aware mean estimation, robust covariance estimation, and robust linear regression. Our proof makes essential use of Talagrand’s generic chaining/majorizing measures theorem.