Papers for

statistical estimation engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Sum of squares certification for log-concave distributions improves statistical estimation

On the SoS Certifiability of Log-Concave Distributions

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.

Thu 24 SeptMachine LearningComputational Complexity
The gist
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.
Open → 2609.30105v1