On the SoS Certifiability of Log-Concave Distributions
cs.LG, cs.CC, math.PR
Submitted: 2026-09-24
Updated: 2026-10-05
License: http://creativecommons.org/licenses/by/4.0/
The gist: We prove that for every isotropic log-concave distribution P on R d and every even m 2, the polynomial (Cm) mv 2 m - E X about P X,v m is a sum of squares, where C>0 is a universal constant.
Terminology
Abstract
We prove that for every isotropic log-concave distribution P on R d and every even m 2, the polynomial (Cm) m|v| 2 m - E X about P X,v m is a sum of squares, where C>0 is a universal constant. This improves on the Poincaré-dependent bounds (Kothari and Steinhardt, 2017), 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 statistical estimation problems. Our proof proceeds by using stochastic localization to decompose P as an average of strongly log-concave measures, whose centered moments admit the subgaussian certificates (Diakonikolas et al., 2025). With a covariance-adapted choice of localization, we show that a fourth-moment certificate derived from the variance inequality for quadratic forms (Letwin, 2026) suffices to control this averaging at every even degree.
Sources
- Convergence of SDP hierarchies for polynomial optimization on the hypersphere
- A note on Bourgain's slicing problem
- Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
- Isoperimetric inequalities in high-dimensional convex sets
- Outlier-robust moment-estimation via sum-of-squares
- Better Agnostic Clustering Via Relaxed Tensor Norms
- The Localization Method for High-Dimensional Inequalities
- The KLS constant is $O(\log^{1/4} n)$
- Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
- High-dimensional estimation via sum-of-squares proofs
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks