CS Paper Radar

Distribution-Dependent Improvements of McDiarmid's Inequality via Rényi Divergence

Amedeo Roberto Esposito, Adrien Vandenbroucque, Michael Gastpar

cs.IT math.PR ·submitted 2026-10-13 05:14 UTC · v1

Abstract

We investigate whether Rényi divergence can sharpen McDiarmid's inequality and its distribution-dependent refinement induced by KL divergence. Starting from Marton's transportation proof, we show that its transport inequality fails in general when KL divergence is replaced by Rényi divergence of order $0<α<1$. For sums of independent bounded random variables, however, the additivity of Rényi divergence allows us to adapt the argument and derive concentration bounds. For Bernoulli sums, these bounds strictly improve on the distribution-dependent bound induced by KL divergence over a range of deviation thresholds. We also establish a distribution-dependent refinement of Gilardoni's inequality relating total variation to Rényi divergence, providing explicit constants for our general concentration bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization

cs.IT math.STmath.PRstat.ML ·2026-10-15 ·Hanuka Eshima, Amedeo Roberto Esposito, Andrea Paudice
similarity 0.68
Abstract

We revisit McDiarmid's inequality, a central tool in statistical learning theory and algorithm analysis. We show that large deviations above the mean are exponentially unlikely for functions of independent random variables that are almost surely bounded above and satisfy a conditional moment assumption of order $p\in(1,2]$. When $p<2$, the result applies even when the function has infinite variance. Our proof relies on a new tensorization inequality for the Kullback--Leibler divergence, termed reverse KL tensorization, which may be of independent interest. Applications include concentration of the sample mean and median-of-means estimator, and one-sided uniform risk bounds for unbounded losses.

0.22

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

Multiplicative comparisons of Rényi entropies for weighted Bernoulli sums

cs.IT math.PRmath.CO ·2026-09-01 ·Jiange Li
theory similarity 0.59
Abstract

We establish multiplicative comparisons between Rényi entropies of different orders for weighted sums of independent Bernoulli random variables. In particular, we prove a logarithmic comparison between the zeroth- and infinity-order Rényi entropies, which yields a polynomial improvement over the square-root bound of Jain, Sah, and Sawhney. As an application, this leads to an improved parameterized running time for the randomized bin-packing algorithm of Nederlof, Pawlewicz, Swennenhuis, and Wȩgrzycki. We also obtain explicit dimension-free, constant-factor comparisons between Rényi entropies of positive orders.

0.24

Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy

cs.IT math.ST ·2026-09-23 ·Roberto Bruno, Adrien Vandenbroucque, Amedeo Roberto Esposito
published similarity 0.59
Abstract · Extended version of a paper presented at the 2026 IEEE International Symposium on Information Theory (ISIT). Submitted to the IEEE Transacti…

We study asymmetric simple binary hypothesis testing between $H_0:P_0^{n}$ and $H_1:P_1^{n}$, based on $n$ independent and identically distributed observations. Leveraging a variational representation of Rényi divergence of order $α$, we derive our main result: a finite-sample converse with $α>1$. The bound uses both directions of the divergence $D_α(P_1\|P_0)$ and $D_α(P_0\|P_1)$, tensorises under product measures, and contains familiar data-processing converses as boundary cases. For comparison, we apply the same variational approach to general $f$-divergences and specialise it to total variation, $E_γ$, Hellinger, and Kullback Leibler divergences, thereby recovering familiar converses within a unified framework. Together with an achievability bound involving Rényi divergence with $α\in (0,1)$, the main converse recovers the phase transition of the optimal Type II error under the exponentially decaying Type I error constraint $\varepsilon_n=e^{-nr}$. Under regularity conditions, the optimal Type II error vanishes exponentially when $r<D(P_1\|P_0)$ and converges exponentially fast to one when $r>D(P_1\|P_0)$. We also derive sample-complexity bounds and extend both the converse and achievability analyses to locally differentially private observations, quantifying the cost of privacy and recovering the non-private achievability bound as the privacy constraint vanishes.

0.34

Optimal Transport PAC-Bayes Bounds

cs.LG ·2026-10-12 ·Armin Beck, Peter Ochs, Jalal Fadili
similarity 0.58
Abstract

PAC-Bayesian generalization bounds are among the strongest distribution-dependent guarantees in statistical learning and are typically expressed in terms of the Kullback-Leibler (KL) divergence between a prior and posterior distribution. While analytically convenient, the KL divergence requires the posterior to be absolutely continuous w.r.t. the prior, imposing support constraints that can substantially restrict the choice of posterior. Moreover, the KL divergence does not account for the underlying geometry of the probability space. In this work, we derive new PAC-Bayesian bounds replacing the KL divergence with general optimal transport (OT) distances, including the total variation and Wasserstein-$p$ distances.

0.33

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

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

Entropic Inequalities and Limit Theorems in Boolean Probability

cs.IT math.PR ·2026-10-14 ·Kewei Pan
theory similarity 0.55
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