CS Paper Radar

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

Tom Maitre

cs.IT math.PR ·submitted 2026-10-22 16:13 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On the SoS Certifiability of Log-Concave Distributions

cs.LG cs.CCmath.PR ·2026-09-24 ·Aleksandr Storozhenko
theoryhot direction similarity 0.70
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.

0.55

Sharp Rogers--Shephard Inequalities for Rényi Entropy

cs.IT math.PRmath.MG ·2026-10-11 ·Bang-Xian Han, Guoqing Zhan, Chiyu Zhou, Zhuo-Nan Zhu
theory similarity 0.67
Abstract · 29 pages; comments are welcome!

We establish sharp weighted Rogers--Shephard inequalities for Rényi differential entropy. For independent copies $X,X'$ of a log-concave random vector in $\R^n$, we prove $h_p(aX-bX')\le h_p(X)+n\log(a+b)$ for all $a,b>0$ and $1\le p\le\infty$, where orders $1$ and $\infty$ correspond to Shannon entropy and min-entropy, respectively. The Shannon case settles the entropic Rogers--Shephard conjecture of Madiman and Kontoyiannis and its higher-dimensional formulation. For $1\le p<\infty$, equality holds precisely for invertible affine images of random vectors with independent exponential coordinates. At $p=\infty$, the larger equality class is characterized by possibly extended-valued convex potentials that are positively homogeneous of degree one. For every $0<p<1$, uniform laws on sufficiently high-dimensional simplices violate the unweighted bound. Thus $p=1$ is the critical order for this bound to hold in every dimension. The proof combines weighted convex intersections with an exponential lift to a log-affine probability density. At the Shannon endpoint, this lift yields an exact deficit decomposition with a conditional mutual information term for an additive channel with asymmetric Laplace noise.

0.43

Entropic Inequalities and Limit Theorems in Boolean Probability

cs.IT math.PR ·2026-10-14 ·Kewei Pan
theory similarity 0.67
Abstract

We study Boolean entropy and Fisher information in information inequalities and the Boolean central limit theorem. We prove a fractional Stam inequality for the Boolean Fisher information associated with arbitrary fractional partitions of subset sums, and derive an entropy power inequality for sums of Boolean independent random variables and its weighted version. We then establish a Boolean analogue of Barron's entropy convergence result along the Boolean central limit theorem: Boolean entropy converges to the entropy of the Rademacher law if and only if the initial entropy is finite. Furthermore, under a finite fourth moment, in the Boolean central limit theorem, we obtain \[ Γ(μ_n\mid\mathbf b)= \frac{m_4(μ)-1-m_3(μ)^2}{2}\frac{\log n}{n} +o\!\left(\frac{\log n}{n}\right), \] with an explicit example showing sharpness. For symmetric laws with finite fourth moment and finite Boolean Fisher information, \[ Ψ(μ_n\mid\mathbf b) =2\bigl(m_4(μ)-1\bigr)\frac{\log n}{n} +o\left(\frac{\log n}{n}\right). \] Our approach is based on the Nevanlinna representation of Cauchy transforms.

0.27

Optimal bound for the polynomial Littlewood-Offord problem

cs.CC math.COmath.PR ·2026-10-06 ·Alexandr Grebennikov
similarity 0.66
Abstract · 9 pages

We present an exposition of an argument, discovered by GPT-6 Pro, that gives an optimal bound for the polynomial Littlewood-Offord problem. Namely, let $F$ be a degree-$d$ multilinear polynomial that contains $r$ degree-$d$ monomials involving disjoint sets of variables. Then, for i.i.d. Rademacher random variables $ξ_1, \ldots, ξ_n$, we have $\mathbb{P}[F(ξ_1, \ldots, ξ_n) = 0] = O_d(r^{-1/2})$. This improves upon the previous bound of $(\log r)^{O_d(1)} r^{-1/2}$ due to Meka, O. Nguyen, and Vu, and resolves a conjecture attributed to H. Nguyen and Vu. The key part of the proof is an estimate for the total influence of bounded-degree rational functions, which resolves a recent conjecture of Kothari, Kovacs-Deak, Wang, and Yang.

0.22

A positive resolution of the gap-entropy conjecture

cs.LG stat.ML ·2026-09-09 ·P. M. Aronow, Nathan Kallus, Patrick Lopatto
theory similarity 0.65
Abstract

We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $Δ_i=μ_*-μ_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}Δ_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<Δ_i\le2^{-r}$, and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$. Among all algorithms that identify the optimal arm with probability at least $1-δ$ on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of $H(\log(1/δ)+\mathrm{Ent}(I))$. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus $g^{-2}\log\log(e^e/g)$, where $g=\min_{i\ne *}Δ_i$ is the gap to the closest competitor.

0.51

Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

cs.LG stat.MLmath.PRmath.ST ·2026-08-10 ·Thanh Nguyen-Cung, Binh T. Nguyen
theory similarity 0.64
Abstract

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor $\log n$, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let $Z=(Z_1,\ldots,Z_n)$ have independent coordinates and let $g_i(Z)$ satisfy $\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, $ where $Z_{-i}$ denotes all coordinates except $Z_i$. Assume additionally that changing any coordinate $Z_j$, $j\neq i$, changes $g_i$ by at most $β$, we prove that, for every $p\ge2$, for every $p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}. $$ This removes the $\log n$ factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.

0.34

High-Dimensional Ultra-Log-Concave Distributions

cs.DS math.PR ·2026-09-21 ·Zongchen Chen, Sihan Wang
similarity 0.64
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

Hermite-Fisher bounds and stability for min-entropy power inequalities

cs.IT math.FAmath.MGmath.PR ·2026-09-18 ·Silouanos Brazitikos, Martin Rapaport, Tomasz Tkocz
similarity 0.63
Abstract

We derive explicit lower bounds for relative Fisher information by combining a variational principle with suitably orthogonalized Hermite-polynomial test functions. The resulting cumulant bounds are asymptotically sharp and yield lower bounds for Gaussian entropy deficits. We also establish quantitative versions of sharp min-entropy power inequalities in all dimensions. En route, we develop a stability result for Brzezinski's sharp bound for block sections of products of Euclidean balls, which may be of independent interest.

0.39