On the SoS Certifiability of Log-Concave Distributions

Aleksandr Storozhenko

cs.LGSep 24, 2026

On the SoS Certifiability of Log-Concave Distributions

Authors: Aleksandr Storozhenko

Organizations: Princeton University.

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.

Explore similar work

Jun 10, 2026cs.DS

A unified complexity bound for logconcave sampling

We give a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm along with exponential lifting. The main new ingredient in the analysis is an improved bound on the Poincaré constant of a lifted distribution. As a consequence, the resulting convergence rate is nearly tight for both constrained settings (e.g., Gaussian restricted to a convex body) and well-conditioned settings (e.g., strongly logconcave and smooth densities).

Yunbum Kook, Santosh S. Vempala

Georgia Tech

Log-Concave Distributions Convergence Exponents

Ask PDF

May 12, 2026math.ST

A proximal gradient algorithm for composite log-concave sampling

We propose an algorithm to sample from composite log-concave distributions over

\mathbb{R}^d

, i.e., densities of the form

π\propto e^{-f-g}

, assuming access to gradient evaluations of

f

and a restricted Gaussian oracle (RGO) for

g

. The latter requirement means that we can easily sample from the density

\text{RGO}_{g,h,y}(x) \propto \exp(-g(x) -\frac{1}{2h}||y-x||^2)

, which is the sampling analogue of the proximal operator for

g

. If

f + g

α

-strongly convex and

f

β

-smooth, our sampler achieves

\varepsilon

error in total variation distance in

\widetilde{\mathcal O}(κ\sqrt d \log^4(1/\varepsilon))

iterations where

κ:= β/α

, which matches prior state-of-the-art results for the case

g=0

. We further extend our results to cases where (1)

π

is non-log-concave but satisfies a Poincaré or log-Sobolev inequality, and (2)

f

is non-smooth but Lipschitz.

Linghai Liu, Sinho Chewi

Yale University

Log-Concave Distributions Proximal Operators Optimal Sample Complexity Logarithmic Sobolev Inequalities Gaussian Primitives

Ask PDF

Sep 14, 2026cs.DS

Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start

We show that logconcave probability measures along the Gaussian cooling path have thin-shell stability, generalizing the thin-shell theorem. This result leads to improved complexity for the fundamental problem of sampling an arbitrary logconcave distribution from a cold start. For (near-)isotropic logconcave distributions, the complexity is nearly

n^{2.5}

, improving the previous bound of

n^{2.75}

, and matching the complexity of the abstract Speedy walk.

Yunbum Kook, Santosh S. Vempala

University of Michigan · Georgia Tech

Log-Concave Distributions Optimal Sample Complexity Gaussian Primitives Cold-Start Chemical Structures

Ask PDF