SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications
OPEN ACCESS
Loading...
Author / Producer
Date
2025-06
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We prove that there is a universal constant C > 0 so that for every d ϵ $\mathbb{N}$, every centered subgaussian distribution D on $\mathbb{R}$$^d$, and every even p ϵ $\mathbb{N}$, the d-variate polynomial (Cp)$^{p/2}$ · ||v||$_{2}^{p}$ - $\mathbb{E}$$_{X∼D}$$\langle$v,X$\rangle$$^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.
Permanent link
Publication status
published
External links
Book title
STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
1689 - 1700
Publisher
Association for Computing Machinery
Event
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
sum-of-squares; robust statistics; subgaussian distributions; injective tensor norms
Organisational unit
Notes
Funding
815464 - Unified Theory of Efficient Optimization and Estimation (EC)