PaperlayerView exact revision on arXiv

Source-linked AI summary

Strong data processing inequalities and $Φ$-Sobolev inequalities for discrete channels

Maxim Raginsky

arXiv:1411.3575v4cs.ITmath.PR

TL;DR

The paper asks how strongly discrete channels contract relative entropy and general Φ-divergences beyond ordinary data processing. It systematically characterizes optimal SDPI constants, derives bounds and product-space results, and relates them to Φ-Sobolev inequalities. The results include maximal-correlation lower bounds, structural tensorization findings, and channel-specific upper bounds, with some concentration-based bounds limited to sufficiently noisy channels.

  • Problem

    For a fixed reference input distribution, the contraction of relative entropy or a general Φ-divergence can be strictly stronger than ordinary data processing, motivating optimal SDPI constants and their relation to Φ-Sobolev inequalities.

  • Method

    The paper develops variational characterizations, upper and lower bounds, convexity and product-space structural results, and factorizations connecting SDPIs with Φ-Sobolev inequalities.

  • Results

    For sufficiently smooth Φ, ηΦ(µ, K) is lower-bounded by squared maximal correlation; the paper also establishes tensorization results and upper bounds based on posterior likelihood-ratio concentration.

  • Takeaways & Limitations

    SDPI constants provide a unified way to quantify channel noisiness across Φ-divergences and connect channel contraction with discrete probability and Markov-chain inequalities.

  • Takeaways & Limitations

    The concentration-based upper bounds are nontrivial only for sufficiently noisy channels and can be loose in some regimes.

Abstract

from arXiv · show

The noisiness of a channel can be measured by comparing suitable functionals of the input and output distributions. For instance, the worst-case ratio of output relative entropy to input relative entropy for all possible pairs of input distributions is bounded from above by unity, by the data processing theorem. However, for a fixed reference input distribution, this quantity may be strictly smaller than one, giving so-called strong data processing inequalities (SDPIs). The same considerations apply to an arbitrary $Φ$-divergence. This paper presents a systematic study of optimal constants in SDPIs for discrete channels, including their variational characterizations, upper and lower bounds, structural results for channels on product probability spaces, and the relationship between SDPIs and so-called $Φ$-Sobolev inequalities (another class of inequalities that can be used to quantify the noisiness of a channel by controlling entropy-like functionals of the input distribution by suitable measures of input-output correlation). Several applications to information theory, discrete probability, and statistical physics are discussed.

1 Introduction

The paper studies when channels contract relative entropy and more general Φ-divergences by a factor strictly below one for a fixed reference input distribution. It develops optimal SDPI constants and connects them to structural properties, product channels, and Φ-Sobolev inequalities.

  • For a fixed reference distribution µ, the output relative entropy can be strictly smaller than the input relative entropy unless ν = µ.
  • The SDPI constant η(µ, K) measures the worst-case contraction ratio of relative entropy under channel K at reference distribution µ.
  • For the binary symmetric channel BSC(ε) with uniform input, η(µ, K) equals (1 − 2ε)^2 and the squared maximal correlation.
  • Earlier work relates SDPI constants for Φ-divergences to maximal correlation, hypercontractivity constants, and the Dobrushin contraction coefficient.
  • This paper establishes bounds and structural results for SDPI constants, including product-space results and their relationship with Φ-Sobolev inequalities.
  • The framework treats channels as stochastic transformations acting on distributions, signed measures, and functions, with backward channels defined through Bayes’ rule for admissible pairs.

2 Background on Φ-entropies and Φ-divergences

This section introduces Φ-entropies and Φ-divergences as a common framework for entropy-like quantities, conditional information, and statistical decision problems. It also develops subadditivity criteria and links conditional Φ-entropy to Fisher-type information.

  • A Φ-entropy is defined for nonnegative random variables using a convex function Φ, and includes variance and ordinary entropy as special cases.
  • A Φ-divergence compares distributions through the density ratio dν/dµ relative to a strictly positive reference distribution µ.
  • Subtracting Φ(1) ensures DΦ(µ∥µ) = 0, while affine changes to Φ leave the resulting divergence unchanged.
  • Φ-divergences include total variation, squared Hellinger distance, χ2-type divergences, and Le Cam divergences.
  • The framework interprets certain Φ-divergences as Bayes or statistical information arising from optimal decision rules under observation channels.
  • Conditional Φ-entropy yields a Fisher-type information interpretation for the information about a variable contained in another variable.
  • 2.1 Subadditivity of Φ-entropies: Φ-entropy is subadditive under the stated convexity condition that 1/Φ′′ is concave, with the converse holding under strict convexity and twice differentiability.

3 Strong data processing inequalities

The paper formulates strong data processing inequalities for general Φ-entropies and characterizes their optimal constants. It derives convexity, universal contraction bounds, and bounds based on maximal correlation, Dobrushin contraction, and channel minorization.

  • A Φ-type SDPI at µ bounds output Φ-entropy by a constant c below one times input Φ-entropy, and ηΦ(µ, K) is the tightest such constant.
  • For homogeneous Φ-entropies, the optimal SDPI constant can be characterized without fixing the input entropy level.
  • The SDPI constants ηΦ(µ, K) and ηΦ(K) are convex in the channel kernel K.
  • 3.1 A universal upper bound via Markov contraction: Every channel with Dobrushin coefficient below one satisfies an SDPI for every Φ-divergence and every reference input distribution, although the resulting bound can be loose.
  • 3.1 A universal upper bound via Markov contraction: A Doeblin minorization condition with parameter α yields the universal bound ηΦ(K) ≤ 1 − α.

3.2 Bounds via maximal correlation

This section relates SDPI constants for Φ-divergences to maximal correlation, establishing lower bounds and, under regularity conditions, upper bounds with distribution-dependent factors. It also connects these bounds to χ2-divergence, relative entropy, and Φ-Sobolev inequalities.

  • The squared maximal correlation S2(µ, K) equals the χ2-divergence SDPI constant ηχ2(µ, K).
  • For three-times differentiable Φ with Φ′′(1) > 0, maximal correlation provides a lower bound on ηΦ(µ, K).
  • Under additional regularity conditions, ηΦ(µ, K) has an upper bound proportional to S2(µ, K), with a multiplicative factor depending on the smallest input mass µ∗.
  • For Φ2(u) = u2 −1, the upper bound is exact, while the limit toward relative entropy yields a corresponding entropy bound.
  • The resulting upper bounds are nontrivial only when maximal correlation is sufficiently small relative to µ∗ and the relevant exponent.

3.3 Upper bounds for operator convex Φ

This section studies sharper SDPI upper bounds for operator convex Φ, using their matrix-analytic structure and integral representations. It recovers equality with squared maximal correlation for discrete channels and illustrates the result for Le Cam divergences.

  • A distribution-dependent upper bound is developed to address the multiplicative factor depending on µ in the earlier maximal-correlation bound.
  • Operator convexity is stronger than ordinary convexity and is characterized through matrix inequalities across all dimensions.
  • Loewner’s theorem characterizes operator convex functions on R+ through an integral representation involving α, β, and a positive measure.
  • The Hellinger-generating function Φ(u) = (√u −1)2 is operator convex but does not belong to the narrower class C used by some earlier bounds.
  • For operator convex Φ, the SDPI constant is bounded by the squared maximal correlation for every discrete channel.
  • For Le Cam divergences, the relevant SDPI constants are controlled by S2(K), using their representation as convex combinations of χ2-divergences.

3.4 Upper bounds via subgaussian concentration and information-transportation inequalities

The section bounds SDPI constants using concentration of posterior likelihood ratios and information-transportation inequalities. These bounds are illustrated for binary symmetric channels, general discrete channels, and random walks on graphs.

  • Concentration-based bounds: Theorems 3.7 and 3.8 bound η(µ, K) through concentration properties of the posterior likelihood ratio a(X, y) around its mean 1.Theorem 3.8 additionally connects relative-entropy SDPI bounds with information-transportation inequalities.
  • Information-transportation inequalities: Theorem 3.8 applies when µ satisfies an information-transportation inequality, linking Wasserstein-type control to SDPI for relative entropy.For the trivial metric, the Wasserstein distance reduces to total variation distance.
  • Examples: For binary symmetric channels with asymmetric Bernoulli inputs, the resulting bound is loose near p = 1/2 and is off by a factor of 2.Despite this looseness, it is tighter than the Dobrushin contraction bound for 1/4 < ε < 3/4 and is nontrivial for ε ≳ 0.156.
  • Examples: For random walks on graphs, the method yields graph-dependent bounds, including a nontrivial range for the complete graph and a piecewise bound for the ternary path graph.The complete two-point graph specializes to the binary symmetric channel case.
  • Scope and limitations: The general discrete-channel bounds are useful mainly for sufficiently noisy channels whose posterior likelihood ratios are nearly constant in the input symbol.Exact input-independence of the posterior likelihood ratio corresponds to η(µ, K) = 0.

3.5 Tensorization

The tensorization section studies whether product channels inherit SDPI behavior from their component channels. Under subadditivity and homogeneity of the Φ-entropy, the product SDPI constant is controlled by the largest component constant.

  • Tensorization: Tensorization asks whether the SDPI constant of a product channel can be determined from the SDPI constants of its component source-channel pairs.Earlier proofs used Φ-specific tools such as operator eigenvalues or the relative-entropy chain rule.
  • Tensorization: Theorem 3.9 establishes tensorization for Φ generating subadditive and homogeneous Φ-entropies.The theorem applies to arbitrary finite collections of admissible source-channel pairs.
  • Tensorization: The product SDPI constant equals the maximum of the component SDPI constants under the theorem’s assumptions.The lower bound follows by varying one coordinate while keeping the others at their reference distributions; the upper bound is proved by reduction to two factors.

3.6 Mixtures of local channels

This section analyzes channels that randomly select one local channel or block of coordinates while leaving the remaining coordinates unchanged. The resulting SDPI bounds depend on the selection probabilities and local constants, with sharpness shown in a binary example.

  • Mixture construction: A mixture channel selects coordinate i with probability p_i, applies K_i there, and leaves all other coordinates unchanged.Its Markov kernel is the corresponding convex combination of identity-and-local-channel products.
  • Mixture bounds: Theorem 3.10 relates the mixture SDPI constant to the local constants ηΦ(µ_i, K_i) and selection probabilities p_i.The theorem is posed for product reference distributions and local channels on the component spaces.
  • Mixture bounds: 1 − ηΦ(µ1 ⊗ … ⊗ µn, K) ≥ min_i p_i(1 − ηΦ(µ_i, K_i)).This lower bound on the mixture’s contraction complement is the principal quantitative result for randomly selected local channels.
  • Examples: For uniformly selected coordinate flips with Bernoulli inputs and BSC(ε) local channels, the bound is achieved with equality.When ε = 1/2, the resulting upper bound on the SDPI constant is 1 − 1/n.
  • Block mixtures: The same analysis extends to uniformly selected blocks, combining tensorization within blocks with mixture bounds across blocks.For a single block, the channel reduces to BSC(ε)^⊗n with η = (1 − 2ε)^2.

3.7 Comparison of SDPI constants

The section compares SDPI constants across different source-channel pairs using a change-of-measure argument. A pointwise domination condition between channels yields a direct comparison bound.

  • Change of measure: Theorem 3.11 converts an SDPI upper bound for one admissible source-channel pair into a bound for another under a homogeneity condition on Φ.The comparison uses a change-of-measure argument between the two joint laws.
  • Channel comparison: If K̄(y|x) ≤ A K(y|x) pointwise, Corollary 3.2 gives an SDPI comparison for any admissible reference distribution and homogeneous Φ.The constant A controls the channel domination used in the comparison.

3.8 Extremal functions

The section characterizes extremal functions for Φ-SDPI constants through a variational equation and identifies when nonconstant extremizers exist. It also records existence, minimality, and limitations of solving that equation explicitly.

  • 3.8 Extremal functions: The paper characterizes functions attaining the infimum defining ηΦ(µ, K) as solutions of a variational equation.This characterization is established for sufficiently smooth Φ.
  • 3.8 Extremal functions: ηΦ(µ, K) is the smallest positive constant for which the variational equation has a solution among nonconstant functions.This establishes the equation’s minimality characterization of the SDPI constant.
  • 3.8 Extremal functions: The variational equation can have multiple solutions, and not all solutions are extremal; explicit closed forms are generally difficult to obtain.The paper gives u log u and power Φ functions as examples satisfying the required condition, while −log u does not.
  • 3.8 Extremal functions: If the SDPI infimum is not achieved, then ηΦ(µ, K) = S2(µ, K).The same equality also follows when the variational equation has only the relevant trivial solutions under the stated condition.

4 Connections with Φ-Sobolev inequalities

The paper relates SDPIs to Φ-Sobolev inequalities by expressing entropy contraction through input-output correlation measures. This connection yields bounds for Poincaré and logarithmic Sobolev constants and links them to decay along Markov processes.

  • 4.1 General framework: Φ-Sobolev inequalities relate input Φ-entropy to a measure of correlation between functions of X and the channel output Y.The framework uses an admissible pair (µ, K) and a function Ψ to define the inequality.
  • 4.1 General framework: The correlation functional is the covariance of the MMSE estimation errors of U and V given Z.Specifically, E(U, V |Z) = Cov[e(U|Z), e(V|Z)].
  • 4.1 General framework: If ηΦ(µ, K) ≤ c, then under concavity and homogeneity assumptions the Φ-Sobolev inequality holds with constant α = (1 −c)^−1.The implication is supplied by Theorem 4.1.
  • 4.2 Logarithmic Sobolev and Poincaré inequalities: Bounds on ηΦ automatically produce Φ-Sobolev bounds, including Poincaré and logarithmic Sobolev inequalities.The paper applies the framework to Φ(u) = u^2 −1 and Φ(u) = u log u.
  • 4.2 Logarithmic Sobolev and Poincaré inequalities: For Markov trajectories, Poincaré and log-Sobolev inequalities characterize exponential decay of variance and entropy, yielding ηχ2(µ, Mt) ≤ e^−λ̃(µ,M)t and η(µ, Mt) ≤ e^−4ρ̃1(µ,M)t.The decay statements apply to the channel Mt induced by the transition from X0 to Xt.
  • 4.3 The gap between SDPI and Φ-Sobolev: The SDPI-to-Φ-Sobolev implication can be strict for nonconstant functions when u ↦ −Ψ(u) is strictly convex at 1, but becomes equivalent when Ψ is affine.The distinction follows from the entropy decomposition involving E[f(X) Ent−Ψ[f(X)|Y]].

5 Some applications

The paper applies its SDPI framework to concentration, mutual-information contraction, fastest-mixing chains, Gibbs samplers, and reconstruction in graphical models.

  • 5.1 Concentration inequalities: A modified log-Sobolev inequality yields Gaussian concentration when the function variability is controlled by an operator norm.The paper identifies ||Γf||∞ as a measure of variability and derives v-subgaussianity with v = c||Γf||∞^2.
  • 5.1 Concentration inequalities: The optimal relative-entropy log-Sobolev constant can be expressed through SDPI constants over channel factorizations of a reversible Markov kernel.The construction uses the adjoint channel and optimizes over factorizations M = K*µK.
  • 5.2 Contraction of mutual information in a Markov chain: For a Markov chain U → X → Y, the paper generalizes mutual-information contraction results to mutual Φ-information and recovers squared maximal correlation for χ2-divergence.The treatment addresses a flaw in an earlier claim and gives a general Φ-information formulation.
  • 5.3 Fastest mixing Markov chain on a graph: The fastest-mixing Markov-chain problem is formulated as a convex program, with bounds involving total variation and the Dobrushin coefficient.The paper states that the FMMC problem is convex and provides propositions giving corresponding bounds.
  • 5.4 Mixing times of Swendsen-Wang and heat-bath dynamics: Theorem 5.3 transfers SDPI bounds between Swendsen–Wang and heat-bath dynamics, extending Ullrich’s χ2 result to other Φ-divergences.For q = 2, Δ = 3, and β = 0.001, the specialized bound is tighter than Ullrich’s bound, although both remain crude because of O(q^Δ) terms.
  • 5.5 Reconstruction and spatial mixing: Under the stated regularity conditions, non-Φ-reconstructibility is equivalent to exponential decay of correlations, and spatial mixing implies the corresponding conclusion.The equivalence is obtained by comparing Φ-information with χ2-information.

6 Summary of contributions and concluding remarks

The paper presents a unified theory of SDPIs for discrete channels, deriving bounds, tensorization results, and connections to Φ-Sobolev inequalities. Applications extend these results to concentration, information contraction, mixing, and reconstruction.

  • Definitions and overview: The paper defines Φ-type SDPIs through contraction of Φ-divergences relative to a reference input distribution.The best constant is denoted ηΦ(µ,K), with ηΦ(K) obtained by taking the supremum over reference distributions.
  • SDPI bounds: For smooth Φ, ηΦ(µ,K) is lower-bounded by squared maximal correlation, which equals the χ2 SDPI constant.This refines earlier lower bounds for relative entropy and general Φ-divergences.
  • SDPI bounds: For operator convex Φ, the paper proves an upper bound involving the Le Cam divergence and recovers the maximal-correlation bound after optimizing over input distributions.The result refines a prior channel-level inequality.
  • SDPI bounds: For relative entropy, the SDPI constant is bounded by twice the expected subgaussian constant of the posterior likelihood ratio.The posterior likelihood ratio is nearly one when the observation is nearly uninformative about the input.
  • Tensorization: Under mild regularity conditions, SDPI constants tensorize for product distributions and product channels, with an additional inequality for randomly selected local channels.This extends prior tensorization results for χ2-divergence and relative entropy.
  • Φ-Sobolev inequalities: The paper establishes deep links between SDPIs and Φ-Sobolev inequalities, which support quantitative convergence-to-equilibrium analysis.For relative entropy, it relates log-Sobolev constants of reversible chains to SDPI constants.
  • Applications and scope: Applications cover concentration of measure, generalized mutual-information contraction, computation of SDPI constants, and discrete statistical-physics models.The paper also notes that SDPIs have limitations in some continuous-alphabet additive-noise settings but remain broadly useful.

A Miscellaneous lemmas

The appendix develops technical lemmas for Φ-divergences, conditional Φ-entropies, derivative bounds, and exchangeable-pair calculations used throughout the paper.

  • Channel identities: The appendix introduces the backward channel induced by a reference distribution and a forward channel.This channel notation supports later calculations involving conditional expectations and adjoint kernels.
  • Direct calculations: The appendix records direct calculations for functions and channel expressions under the paper’s finite-alphabet assumptions.These calculations include identities valid for every y in the output alphabet.
  • Φ-entropy lemmas: For admissible Φ, the function Ψ(u) = (Φ(u)−Φ(0))/u is assumed concave in a key entropy comparison lemma.The proof uses a size-biased probability measure and Jensen’s inequality.
  • Φ-divergence lemmas: Monotonicity of Φ′′ yields bounds involving the essential supremum of a nonnegative unit-mean random variable.The argument applies when Φ is twice differentiable and Φ′′ is nonincreasing.
  • Conditional Φ-entropy: A conditional Φ-entropy admits a variational representation whose optimizer is the conditional expectation.Equality is achieved by choosing the variational function ξ(z) = E[U|Z = z].
  • Regularity arguments: Differentiability and boundedness of Φ′ near one justify exchanging expectation and differentiation in the appendix’s limiting argument.The proof controls the relevant difference quotients using dominated convergence.

B Proof of Proposition 4.1

The proof analyzes the joint law of an exchangeable pair generated by a channel and its adjoint, then uses symmetry and equal marginals to derive the required identities.

  • Exchangeable-pair construction: The channel and its backward counterpart generate an exchangeable pair (X,X′) under the invariant input distribution.Exchangeability implies that X and X′ have the same marginal distribution µ.
  • Proof identities: The proof uses equal marginals and exchangeability to rewrite conditional and covariance-like expressions needed for the proposition.The remaining steps are algebraic consequences of these two distributional properties.
Loading 1411.3575v4…