CS Paper Radar

Discrete Isoperimetric Inequalities via Curvature

Zejia Chen, Zongchen Chen, Xinyuan Zhang

cs.DM math.PR ·submitted 2026-09-21 14:42 UTC · v1

Abstract

Isoperimetric inequalities on the Boolean hypercube play a fundamental role in the analysis of Boolean functions. These inequalities have been established primarily for the uniform measure and for biased product measures, often through Fourier-analytic or inductive arguments. We develop a curvature-based semigroup framework to establish isoperimetric inequalities for measures with weakly dependent coordinates. In particular, we show that a Dobrushin-type condition, together with marginal boundedness of the distribution, implies the local Bobkov inequality, Talagrand's $L^1$--$L^2$ and variance--surface-area inequalities, the Kahn--Kalai--Linial inequality, and the Eldan--Gross inequality. Our results apply to zero-field Ising models with interaction matrix $J$ throughout the Dobrushin uniqueness regime $\|J\|_1<1$. The framework builds on discrete Bakry--Émery theory and gradient estimates and can also be extended to measures on Hamming slices or hypergrids.

Comment
62 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Contraction of Rényi Divergences for Discrete Channels

cs.IT math.PR ·2026-09-28 ·Adrien Vandenbroucque, Amedeo Roberto Esposito, Michael Gastpar
highly cited similarity 0.59
Abstract

We investigate Strong Data-Processing Inequality (SDPI) constants for Rényi Divergences on finite spaces. We study their dependence on the Rényi order $α$, proving that they are non-decreasing and that their scaling by $(α-1)$ is convex for $α\geq1$. We also identify several support restrictions on the probability measures involved in determining these constants. In particular, in the distribution-independent setting, measures supported on a common set of at most two points suffice to evaluate the Rényi-SDPI constant. For $α\in[0,1]$, we further prove equality with the $χ^2$-SDPI constant, while at order infinity we obtain a closed-form expression. In order to link contraction over product spaces to contraction along individual coordinates, we provide tensorisation bounds for arbitrary product channels analogous to those known for $\varphi$-Divergences. At finite orders, the Rényi-SDPI constants are bounded above and below through comparisons with the $χ^2$-Divergence and Hellinger Divergences, with sharpness established in multiple cases. At order infinity, we instead relate these constants to the contraction of Total Variation Distance. Finally, our findings are applied to local differential privacy (LDP) and the analysis of Markov chains. This yields sharp contraction guarantees for pure-LDP mechanisms, and connects Rényi-LDP to Rényi-SDPI constants. For Markov chains, we derive finite-time convergence bounds and exhibit a family of chains for which Rényi-SDPIs improve on classical $χ^2$-based bounds by arbitrarily large factors.

0.34

Matrix $Φ$-Entropic Measures of Dependence

cs.IT ·2026-10-21 ·Chenyu Wang, Amin Gohari
similarity 0.59
Abstract

We introduce matrix $Φ$-ribbons, extending the scalar $Φ$-ribbons to the matrix case. For $Φ$ in the subadditivity class, we establish data processing and tensorization properties of matrix $Φ$-ribbons. We establish scalar and matrix $Φ$-entropy inequalities and use them to show that both $Φ$-ribbons characterize the corresponding $Φ$-strong data processing inequality (SDPI) constants. We obtain exact evaluations of the SDPI constants for several sources. We provide examples showing that the matrix $Φ$-SDPI constant can exceed the scalar counterpart. Finally, we derive inner bounds for $Φ$-ribbons from prescribed independence structures and prove that these bounds are optimal when $Φ(t)=t\log t$.

0.25

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

High-Dimensional Ultra-Log-Concave Distributions

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

Dimension-free comparison inequalities between $f$-divergences for Gaussian location mixtures

cs.IT math.STmath.PRstat.ML ·2026-10-18 ·Jeonghwan Lee, Cong Ma
similarity 0.54
Abstract · 21 pages; Comments would be appreciated!

We establish dimension-free comparison inequalities between the Kullback-Leibler (KL) and $χ^2$-divergences and the squared Hellinger distance for Gaussian location mixtures with compactly supported mixing distributions. We show that both divergences are bounded by the squared Hellinger distance up to constants depending only on the radius of the support, independently of the ambient dimension and the number of mixture components. These results resolve an open question raised by \cite{jia2023entropic} and strengthen existing comparison inequalities. Our proof relies on a Gaussian interpolation argument that relates the derivatives of these divergences to differences between posterior means.

0.29

Lipschitz-Constrained Discriminators in Generative Modeling: Asymptotic Behavior and Support Mismatch

cs.LG stat.ML ·2026-11-13 ·Eduardo Pinto, Panagiota Birmpa
similarity 0.54
Abstract

We study the asymptotic behavior of optimal discriminators associated to $L-$Lipschitz regularized KL-divergences of two probability distributions $Q$ and $P$ that interpolate between the rescaled Wasserstein$-1$ metric by some parameter $L>0$ and the KL divergence. The parameter $L$ plays the role of a Lipschitz constraint and is viewed as a regularization parameter: small values of $L$ enforce a more geometry-aware discriminator, while as $L$ increases the geometric regularization is progressively relaxed. It is a known result [3] that such divergences converge to the KL divergence as $L\to\infty$. In this paper, we characterize the asymptotic behavior of the optimal discriminators as $L\to\infty$ in different regimes: Firstly, under $Q\ll P$ and the Radon-Nikodym derivative $\frac{dQ}{dP}$ is bounded from above and bounded away from zero. Secondly, when $Q$ and $P$ are discrete distributions satisfying $Q\ll P$, and finally when $Q$ and $P$ are non absolutely continuous discrete distributions. This result motivates training strategies which involve discriminators, such as adversarial generative models. In practice, the data distribution is often represented by a discrete empirical measure, while, especially at the early stages of the training, the model distribution may have little or no overlap with the empirical data distribution.

0.27

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.54
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.43

Nonnegative Rank Bounds for the Algebraic Monotone Calculus

cs.CC ·2026-10-31 ·Fedor Part
theory similarity 0.54
Abstract

In Hrubes' Algebraic Monotone Calculus a DNF tautology $A$ is proved by a monotone arithmetic circuit computing $χ(A)-εχ(1)$ for some $ε>0$, where the coefficient of $χ(A)$ at $x^σ$ counts the terms of $A$ satisfied by $σ$, and $χ(1)=\prod_i(x_i^0+x_i^1)$. Proof size is circuit size, and $ε$ is existentially quantified, so lower bounds must hold at arbitrarily small $ε$. We prove lower bounds for bounded-depth fragments by two nonnegative rank measures of the target: monotone tensor rank and the nonnegative rank of a flattening. At depth three a proof is a nonnegative tensor decomposition. Restricting its terms to subcube indicators gives conical juntas, a system polynomially equivalent to Sherali-Adams in twin variables. For arbitrary terms we adapt Rothvoss' hyperplane separation to monotone tensor rank: Tseitin formulas on constant-degree expanders of large girth need proofs of size $2^{Ω(εn)}$ whenever $ε=ω(\log n/n)$. This cannot reach every $ε$: at shift $2^{-Θ(n\log n)}$ Tseitin acquires polynomial-size depth-three proofs, separating the two fragments exponentially. A constant-size index gadget gives bounds for every $ε\geq2^{-Ω(n)}$, converting a Sherali-Adams degree bound into a size bound. Depth three is essential: Tseitin has monotone proofs of size $O(n^3)$ and depth $O(\log n)$ at every $ε$. Beyond depth three we bound the nonnegative rank of a flattening by $L^{2^t}$ for a monotone formula with $L$ leaves and mixed-product depth $t$: the largest number of product gates on a root-to-leaf path whose two inputs each meet both sides of the bipartition. Approximate extension complexity then bounds perfect matching and odd factor instances, and planted CSP integrality gaps give an explicit family of planted Tseitin DNFs hard at inverse-polynomial shift.

0.25