CS Paper Radar

On the SoS Certifiability of Log-Concave Distributions

Aleksandr Storozhenko

cs.LG cs.CCmath.PR ·submitted 2026-09-24 16:48 UTC · v2
theoryhot direction

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é-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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT math.PR ·2026-10-22 ·Tom Maitre
theory similarity 0.70
Abstract

Let $μ$ be a log-concave isotropic probability measure on $R^d$ , and let $μ^n$ denote the law of the normalized sum of $n$ independent random vectors with law $μ$. We prove that \[ H(μ^n|γ)\leq \frac{C}{n} \min\left\{1+\log(ed)^2H(μ|γ)\ ,\ d\right\}. \] Compared to the previous best known bound, our estimate replaces the polynomial dependence on the dimension by a polylogarithmic one. The proof relies on a new combination of the De Bruijn identity with Eldan's stochastic localization process.

0.11

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

cs.CC stat.MLcs.LGmath.ST ·2026-11-02 ·Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao +1 more
theory similarity 0.66
Abstract

We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

0.17

An exact computer-assisted lower bound for Fisher-information convexity along the two-dimensional heat flow

cs.IT hep-thmath.PR ·2026-10-12 ·Fayez Abu-Ajamieh, Xiaoyan Huo
theory similarity 0.65
Abstract · 12 pages

We study the sharp constant in the differential inequality \[ I(t)I''(t)\geq c\,[I'(t)]^2 \] for Fisher information along the probability-normalized heat flow on $\mathbb R^2$. The unrestricted log-convexity value $c=1$ is false in two dimensions, whereas the known square-root convexity theorem gives the universal value $c=1/2$. We construct an exact, machine-verifiable sum-of-squares certificate proving the stronger universal bound \[ c\geq \frac{231691}{250000}=0.926764. \] Together with an independent exact Fourier/Gaussian-envelope construction, this gives \[ 0.926764\leq c_*<0.94176665012062, \] where $c_*$ is the sharp constant for positive-time Gaussian convolutions of arbitrary probability measures on $\mathbb R^2$. We formulate the proof in explicit two-dimensional index notation. The lower bound follows from an exact rational polynomial identity involving a strictly positive denominator, a weighted total derivative, and eleven positive rational Gram matrices. All $491$ recorded leading principal minors are strictly positive and the complete polynomial identity has zero residual. No symmetry, log-concavity, finite-variance, or finite-entropy assumption is imposed on the initial measure. The sharp value remains open.

0.35

Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions

cs.LG math.STmath.PR ·2026-09-11 ·Weiming Ou, Xiao Wang
hot direction similarity 0.64
Abstract · Under Review

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $d\geq1$. For $μ$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^\star$ in the ball $\mathbb{B}(0,μ^{-1/2})$, and unbiased gradient oracles with variance at most $σ^2$, the minimax worst-case expected query complexity is $Θ\left(\log(1+κ)+\frac{σ^2}{μ\varepsilon}\right)$, jointly optimal for the condition number $κ:=L/μ$, variance $σ^2\ge 0$, and TV accuracy $0<\varepsilon\leq 1/10$. In the noiseless setting $σ=0$, this tight complexity $Θ\left(\log(1+κ)\right)$ is independent of $\varepsilon$. Moreover, a gradient-only sampler generates an exact sample with ${O}(\log(1+κ))$ worst-case expected queries. Without previous ball $\mathbb{B}(0,μ^{-1/2})$, exact sampling from any initial point $x_0$ can be implemented with expected cost ${O}\left(\log(1+κ)+\log(1+\sqrtμ\|x_0-x_f^\star\|)\right)$, without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.

0.25

Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

cs.CC cs.DSmath.STstat.ML ·2026-11-04 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.62
Abstract

We study the query complexity of sampling from smooth distributions on $\mathbb R^d$ using first-order oracles. For $d$-dimensional strongly log-concave targets with condition number $κ=2$, we prove that any randomized sampler requires $\exp({Ω(\log^{1/3} d)})$ queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with $L$-smooth potentials satisfying an $α$-log-Sobolev inequality with $κ= L/α$, we prove an $Ω(κ)$ query lower bound for $d\gtrsim\log^2κ$. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.

0.06

Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions

cs.LG math.OCstat.ML ·2026-11-03 ·Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov, Fedor S. Stonyakin
theory similarity 0.62
Abstract · 57 pages, 4 figures, 5 tables, 5 algorithms. Second paper in the Descending Everest series; Part I: arXiv:2610.21461

We study the minimization of the average of $n$ convex $(L_0,L_1)$-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm. We assume known upper bounds $R$ on the distance from the starting point to a minimizer and $δ$ on the difference between the minimum of the average and the average of the infima of the components. We derive upper and lower bounds on the oracle complexity of reaching accuracy $\varepsilon$ in function value in expectation. Up to logarithmic factors, both bounds are of order $n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2δ)R^2}{\varepsilon}+n(L_1R)^2}$. The upper bound is attained by the proposed method YETI. The method combines ideas of accelerated proximal methods and variance reduction methods with a heuristic for choosing additional points. The number of oracle calls made by the heuristic is bounded, which preserves the upper bound on the total number of queries needed to reach the target accuracy. In the experiments, YETI is compared with first-order methods on synthetic problems and Poisson regression problems. We also examine the stopping criterion and the effect of the heuristic separately. The lower bound is obtained by an explicit construction of families of instances that are hard for any first-order method.

0.28

High-Dimensional Ultra-Log-Concave Distributions

cs.DS math.PR ·2026-09-21 ·Zongchen Chen, Sihan Wang
similarity 0.61
Abstract

Ultra-log-concave distributions are ubiquitous in probability, combinatorics, and statistical mechanics and have been studied extensively. In this paper, we introduce a quantitative high-dimensional extension of this notion, called $δ$-ultra-log-concavity, for probability measures on $\mathbb{N}^d$ with downward closed support. When $δ= 1$, this notion coincides with the class studied by Gurvits (2009) via strongly log-concave generating functions, and with the class defined by Anari, Oveis Gharan, and Vinzant (2021) via completely log-concave generating functions; in one dimension, it reduces to classical ultra-log-concavity. We establish several functional inequalities, including a weighted Poincaré inequality, a discrete Brascamp--Lieb inequality, and a weighted Wu-type modified log-Sobolev inequality. Our approach combines integrated Bakry--Émery calculus for a canonical birth-death chain with Poisson stochastic localization, which arises as the time reversal of coordinatewise binomial thinning. We further establish concentration of measure, maximum-entropy principles, and several closure properties for ultra-log-concave measures, and develop applications to queueing models, polymatroids, antiferromagnetic Potts models, and hardcore models. Finally, a lattice scaling limit of the discrete theory yields Poincaré and Brascamp--Lieb inequalities for Laguerre diffusions.

0.48

Gaussian Partitioning for Reliable Learning of Multi-Index Models

cs.DS cs.LG ·2026-11-03 ·Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Mingchen Ma
theory similarity 0.61
Abstract · The abstract has been shortened for arXiv

We introduce Gaussian partitioning, an algorithmic primitive for distributions smooth with respect to a Gaussian. It partitions space into polyhedral regions so that almost all mass lies in thin strips restricting a few orthogonal directions. Within each strip, the conditional distribution approximately matches low-degree Gaussian moments in the unrestricted directions. Our construction builds on logconcave partitioning of Diakonikolas, Kane, and Ma (FOCS 2026). Under input marginals smooth with respect to the standard Gaussian, we obtain agnostic learners with error $(1+c)\mathrm{opt}+ε$ for broad classes of Boolean multi-index models, including functions of halfspaces, low-dimensional convex concepts, and low-dimensional polynomial threshold functions. For functions of $k$ halfspaces, both agnostic and testable agnostic learners achieve this error with dimension dependence $d^{\mathrm{poly}(k/c)}$, improving the previous exponential dependence on $k/c$ in the agnostic exponent. For learning from positive examples with imperfect unlabeled data (PUI), we give algorithms and Statistical Query (SQ) lower bounds that qualitatively characterize complexity through Gaussian moment matching. For fixed smoothness and positive-mass parameters, we learn intersections of $k$ halfspaces with dimension dependence $d^{O(\log(k/ε))}$ and matching SQ lower bounds, improving the previous $d^{\mathrm{poly}(1/ε)}$ upper bound even for one halfspace. A general reduction from agnostic reliable learning to PUI yields negative reliable learners for these intersections with the same dimension dependence, for fixed smoothness. Finally, for PQ learning and testable learning with distribution shift, we prove qualitatively optimal SQ lower bounds of $d^{Ω(1/ε^2)}$, even for intersections of two halfspaces with Gaussian training data and arbitrary test distributions.

0.22