Skip to content

On the SoS Certifiability of Log-Concave Distributions

Sep 2026 · arXiv.org · Vol abs/2609.30105 · 1 citation · 22 references
Computer Science Mathematics

Abstract

We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ 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.

View source

Similar papers

Preprint Oct 2026

On the Quantitative Bounds of Nonlinear Roth Theorem

We prove that any subset $A \subseteq \{1, \dots, N\}$ lacking non-trivial polynomial progressions $(x, x + y, x + y^2)$ satisfies $\lvert A \rvert \le CN \exp\bigl(-c(\log \log N)^\beta\bigr)$ for effective absolute constants $C, c, \beta>0$. The argument develops a density increment framework localized to anisotropic...

Yun-Fan Zhao · 0 citations
Preprint Oct 2026

Exact bounds on the distribution function of isotropic log-concave distributions

For each real $b$, exact upper and lower bounds on the probability $\mathsf P(X\ge b)$ over all random variables $X$ with log-concave p.d.f.'s such that $\mathsf E X=0$ and $\mathsf E X^2=1$ are obtained, as well as the best constant factor $C$ in the inequality $\mathsf P(X\ge b)\le C e^{-b}$ for all real $b\ge0$. Exa...

I. Pinelis · 0 citations
Preprint Oct 2026

Improved Bounds for the Entropic Central Limit Theorem in the Log-Concave Case

Let $\mu$ be a log-concave isotropic probability measure on $R^d$ , and let $\mu^n$ denote the law of the normalized sum of $n$ independent random vectors with law $\mu$. We prove that \[ H(\mu^n|\gamma)\leq \frac{C}{n} \min\left\{1+\log(ed)^2H(\mu|\gamma)\ ,\ d\right\}. \] Compared to the previous best known bound, ou...

T. Maitre · 0 citations
Preprint Oct 2026

The Berry--Esseen estimate in the Boolean central limit theorem

We estimate the L\'evy distance to the symmetric Bernoulli distribution for normalized Boolean convolution powers of a probability measure with mean zero and variance one. If the absolute moment of order $r$ is finite, we obtain the upper bounds $o(n^{-(r-2)/6})$ for $2<r<5$ and $O(n^{-1/2})$ for $r\ge5$. The proof rel...

M. Maejima, Noriyoshi Sakuma · 0 citations
Preprint Oct 2026

Strichartz estimates on two-dimensional irrational tori

We prove an $L^4$ Strichartz estimate for the dispersion $n_1^2+\alpha n_2^2$ on $\mathbb T^2$, for every $\alpha>0$. The loss is controlled by the Shannon entropy of the normalized squared Fourier coefficients and the cardinality of their support $S$. In particular, we obtain a norm loss of $(\log\#S)^{1/2}$ on fixed...

Ming Wang, Yuan Xiong · 0 citations
Preprint Sep 2026

A spectral gap for Metropolis-adjusted Langevin algorithm with a uniformly randomized step size

Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\, \mathrm{d} x$ on $\mathbb{R}^d$, where $U$ is continuously differentiable and $m$-strongly convex with a globally $L$-Lipschitz gradient, $0<m\leq L<\infty$, and $\kappa=L/m$. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds...

Qian Qin · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.