Sum of squares certification for log-concave distributions improves statistical estimation
On the SoS Certifiability of Log-Concave Distributions
Machine LearningComputational Complexity
Summary
Understanding properties of probability distributions helps improve data analysis and machine learning. This paper proves a key mathematical object related to log-concave distributions, which commonly arise in statistics, can be written as a sum of squares in a way that is both simpler and optimal. This result removes earlier limitations and leads to more efficient, reliable algorithms for high-dimensional data problems. The authors achieve this by combining advanced techniques that break the problem into well-understood parts.
What this means in practice
- •For statistical estimation engineers: Create algorithms with guaranteed error bounds for analyzing high-dimensional data without needing dimension-dependent assumptions.
- •For machine learning developers: Design reliable learning methods that use optimal moment information of complex data distributions to improve performance in diverse settings.
A theory result. No direct application yet.
Authors
Aleksandr Storozhenko
Abstract
For an arbitrary isotropic log-concave distribution $P$ on $\mathbb{R}^d$, we prove that the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares for every even $m\ge2$, where $C>0$ is a universal constant. This removes the dependence on the Poincaré constant in the theorem of Kothari and Steinhardt (arXiv:1711.07465), recovering the optimal moment bounds for log-concave distributions. As an immediate corollary, we obtain computationally efficient algorithms with dimension-free error guarantees for a wide range of high-dimensional statistical estimation problems. Our proof uses stochastic localization to decompose $P$ as an average of random strongly log-concave measures, whose centered moments admit the subgaussian certificates of Diakonikolas, Hopkins, Pensia, and Tiegel (STOC 2025; arXiv:2410.21194). With a covariance-adapted choice of localization, we show that a fourth-moment certificate derived from Letwin's variance inequality for quadratic forms (arXiv:2607.24164) suffices to control this averaging at every even degree.