Rényi divergence constants reveal data loss limits in discrete channels
Contraction of Rényi Divergences for Discrete Channels
Information Theory
Summary
The authors study how certain mathematical measures called Rényi divergences shrink when information passes through a noisy channel. They find that these shrinking factors behave predictably as you change a parameter called the Rényi order. Their results show when simple cases are enough to understand these factors and provide formulas for extreme cases. Their work also helps analyze privacy protections and how quickly Markov chains settle down, sometimes giving better bounds than previous methods.
What this means in practice
- •For privacy engineers: Obtain tight guarantees on data loss for privacy mechanisms using Rényi-LDP parameters.
- •For network reliability teams: Use improved contraction bounds to model the speed of convergence in Markov chains representing network states.
Authors
Adrien Vandenbroucque, Amedeo Roberto Esposito, Michael Gastpar
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.