On the SoS Certifiability of Log-Concave Distributions
Not on the map. Why?
Abstract (arXiv)
We prove that for every isotropic log-concave distribution P on ℝd and every even m≥2, the polynomial (Cm)m|v|2m - mathbbEX~ Plangle X,vranglem is a sum of squares, where C>0 is a universal constant. This improves on the Poincar'e-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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 10 of its 22 references that are in the map. First posted on arXiv 24 Sep 2026.
Builds on
10 of 22 references.
References · 10
- 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
- 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
- 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
- 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
- 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
- 2018High-dimensional estimation via sum-of-squares proofscited by 25
- 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
- 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
- 2016Strongly Refuting Random CSPs Below the Spectral Thresholdcited by 9
- 2025The Localization Method for High-Dimensional Inequalitiescited by 2
Built on by
Not cited yet.