PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Hypercontractivity: Stronger Communication Converses via R\'enyi Contraction

Ryo Hommura Moore, Amedeo Roberto Esposito

arXiv:2610.13030v1cs.ITmath.IT

TL;DR

Rényi SDPI contraction is less understood than the well-studied KL case, despite its relevance to information contraction. The paper characterizes it through power contraction of a dual Markov operator, then derives rectangle-probability bounds and communication converses that are no weaker than, and can be sharper than, hypercontractive bounds.

  • Problem

    Rényi-divergence SDPIs have been less studied than KL-divergence SDPIs, and their contraction behavior appears different.

    Source: §I · p. 1

  • Method

    For α > 1, the paper characterizes Rényi SDPI contraction using Lα-power contraction of the dual Markov operator.

    Source: §I · p. 1, §III · p. 2

  • Results

    The Rényi SDPI coefficient yields rectangle-probability bounds no weaker than hypercontractive bounds and communication converses that can be strictly sharper.

    Source: §I · p. 1

  • Takeaways & Limitations

    For one-way communication-assisted agreement distillation, combining Rényi SDPI coefficients with binary divergence inversion gives refined communication lower bounds.

    Source: §I · p. 1

Abstract

from arXiv · show

We study the relationship between strong data-processing inequalities for R\'enyi divergences and hypercontractivity. For R\'enyi divergences of order greater than one, we characterize the contraction of R\'enyi divergences through a property of the dual Markov operator that we name power contraction. Using the contraction coefficient, we derive an upper bound on rectangle probabilities in terms of their marginals that is at least as strong as the corresponding bound obtained via hypercontractivity. Combining this result with inversion of the binary R\'enyi divergence, we derive communication lower bounds for one-way communication-assisted agreement distillation. Examples involving binary symmetric and rare-event Z-channels illustrate the improvements over standard hypercontractive converses.

I. INTRODUCTION

The paper studies Rényi strong data-processing inequalities (SDPIs), whose contraction properties are less understood than those for KL divergence. It introduces power contraction and uses Rényi SDPI coefficients to strengthen bounds relevant to communication-assisted agreement distillation.

I. INTRODUCTION

  • The paper situates this work against KL-divergence SDPI connections to maximal correlation and hypercontractivity, and prior Φ-divergence SDPIs.It notes that Rényi-α SDPI contraction appears different and has been studied in,.Source: §I · p. 1
  • Rényi-α SDPIs for α > 1 admit an operator interpretation through the dual Markov operator and Lα-power contraction.The property controls the output Lα-norm by a power of the input Lα-norm.Source: §I · p. 1
  • Hypercontractivity implies power contraction with an explicit exponent, but the converse need not hold.Hypercontractivity controls an output Lα-norm using an input Lβ-norm with β < α.Source: §I · p. 1
  • The optimal Rényi SDPI coefficient bounds rectangle probabilities in terms of their marginals, with a bound no weaker than the hypercontractive one.Source: §I · p. 1
  • Combining Rényi SDPI coefficients with binary Rényi divergence inversion yields refined communication converses that can be strictly sharper than hypercontractive converses.The setting is one-way communication-assisted agreement distillation, where parties seek a uniformly distributed binary string from correlated samples.Source: §I · p. 1

II. PRELIMINARIES

The preliminaries fix notation for Hölder conjugates and logarithms. Logarithms throughout the paper use base 2.

II. PRELIMINARIES

  • For nonzero real p, p′ denotes its Hölder conjugate, satisfying 1/p + 1/p′ = 1 when p ≠ 1.Source: §II · p. 1
  • When p = 1, the paper sets p′ = ∞.Source: §II · p. 1
  • The logarithmic function log(x) uses base 2.Source: §II · p. 1

A. Markov kernels

This section defines Markov kernels and their associated operators. It relates the kernel operator to conditional expectation and introduces its dual operator between function spaces.

A. Markov kernels

  • A Markov kernel assigns a probability measure K(·|x) to each input x, with measurable dependence on x for every measurable output set.Source: A. Markov kernels · p. 1
  • The kernel operator Kf integrates f against K(·|x); for p > 1, Jensen’s inequality gives an Lp contraction and permits extension between the stated Lp spaces.Source: A. Markov kernels · p. 1
  • For a pair with input law μ and conditional output law K, Kf(x) equals E[f(Y)|X = x] for μ-almost every x.Source: A. Markov kernels · pp. 1–2
  • The dual operator K⋆_μ is introduced as an adjoint mapping between Lp′(μ) and Lp′(μK).Source: A. Markov kernels · p. 2

B. Rényi Divergence, SDPI Constant

The section recalls Rényi divergence and its basic properties, then defines the Rényi SDPI constant as the optimal contraction factor for a fixed kernel and reference distribution.

B. Rényi Divergence, SDPI Constant

III. Lα-POWER CONTRACTION

The section defines Lα-power contraction and connects it to Rényi-SDPI for dual Markov operators. This yields a rectangle-probability bound that is no weaker than the corresponding hypercontractive bound.

III. Lα-POWER CONTRACTION

  • A positive operator is an Lα-power contraction when it controls the Lα output norm of mean-one nonnegative inputs using exponent c.The section also states that the resulting operator is a contraction, hence bounded.Source: §III · p. 2
  • Theorem III.2 extends the power-contraction control to arbitrary Lα functions.The proof reduces nonnegative inputs to mean one by normalization, then uses positivity for general functions.Source: §III · p. 2
  • For a Markov kernel, its dual is an Lα-power contraction with exponent given by the Rényi-α SDPI constant.The section identifies the optimal exponent with ηα(µ, K).Source: §III · p. 2
  • The resulting upper bound on rectangle probabilities improves on the corresponding hypercontractive result.The bound follows by applying the operator result to indicator functions.Source: §III · p. 3

IV. RÉNYI DIVERGENCE AND HYPERCONTRACTIVITY

The section relates hypercontractivity to power contraction and compares their resulting rectangle-probability bounds. Hypercontractivity implies power contraction, but a fixed Rényi-SDPI condition need not imply hypercontractivity.

IV. RÉNYI DIVERGENCE AND HYPERCONTRACTIVITY

  • Hypercontractivity implies Lα-power contraction with a specified exponent, making power contraction a necessary condition.The section also states that the converse need not hold.Source: §IV · p. 3
  • For K0.1, βK0.1(2) = 1.64, so the channel fails (2, 1.6)-hypercontractivity despite η2(Bern(1/2), K0.1) ≈ 0.7137 < 0.75.This example shows that satisfying the fixed-parameter Rényi-SDPI condition is not sufficient for hypercontractivity.Source: §IV · p. 3
  • The Rényi-SDPI rectangle-probability upper bound is never weaker than the corresponding hypercontractive bound.The comparison follows by applying the dual operator inequalities to indicators of measurable sets.Source: §IV · p. 3
  • Hypercontractivity tensorizes across multiple Markov kernels, with the product parameter determined by the largest constituent ratio sα(Ki).The section defines sα(K) as βK(α)/α.Source: §IV · pp. 3–4

V. CASE STUDY: COMMUNICATION ASSISTED AGREEMENT DISTILLATION

The section places the communication-assisted agreement distillation converse in the context of earlier hypercontractive impossibility results.

V. CASE STUDY: COMMUNICATION ASSISTED AGREEMENT DISTILLATION

  • Earlier work used hypercontractivity for impossibility results on BSCs and some BECs, and Zhao extended those results to general channels [8, Chapter 3].Source: §V · p. 4

A. Setting

Alice and Bob observe strings related through repeated uses of a binary channel, and aim to agree on a uniform binary string. Alice sends a one-way message, after which Bob estimates her output.

A. Setting

  • Alice observes Xn drawn from µ⊗n, and Bob observes Yn produced by passing Xn through the memoryless binary channel K.Source: A. Setting · p. 4
  • Alice maps her observation to an exactly uniform k-bit string and sends Bob an m-bit message, where m = ⌊ck⌋.The message may be any prescribed function of Alice’s observation, not only selected bits of her output.Source: A. Setting · p. 4
  • Bob combines his observation with Alice’s message to estimate her output; the protocol succeeds when he recovers the entire string.Source: A. Setting · p. 4

B. Communication converses

The section turns Rényi SDPI into communication lower bounds through binary Rényi inversion and compares them with hypercontractive converses. The resulting Corollary V.4 bound is never weaker than the hypercontractivity bound.

B. Communication converses

  • The agreement event has joint probability p ≥ 2^-γk and product-law probability q ≤ 2^-k(1-c), while the Rényi SDPI limits their divergence.The success requirement lower-bounds the joint-law event probability, and the communication length upper-bounds its product-law probability.Source: B. Communication converses · p. 4
  • Theorem V.2 uses binary inversion to derive a communication converse from qα(γ), defined by dα(pγ||qα(γ)) = khα(µ, K).The theorem specifies pγ := 2^-γk and qα(γ) ∈ (0, pγ]; the solution is unique and is the smallest product-law probability compatible with the stated constraints.Source: B. Communication converses · p. 4
  • Corollary V.4 gives an explicit bound by dropping the complementary term in the binary Rényi divergence.The proof then rearranges the inequality and takes a supremum over α > 1.Source: B. Communication converses · p. 5
  • The Corollary V.4 lower bound on communication is never weaker than the corresponding hypercontractivity bound.The comparison is stated directly for the bounds induced by the two methods.Source: B. Communication converses · p. 5
  • As α→∞, the hypercontractivity estimate becomes trivial for dependent X and Y, while the Rényi-SDPI estimate can remain positive if η∞(µ⊗n, K⊗n) < 1−γ.The paper gives (γ+ϵ)-ultra-mixing as one condition guaranteeing this SDPI condition.Source: B. Communication converses · p. 5

C. Examples

The examples illustrate the communication converse for a doubly symmetric binary symmetric channel and a rare-event Z-channel. They report an explicit Rényi-SDPI quantity for one DSBS setting and compare the binary-inversion and hypercontractivity bounds numerically for a Z-channel.

Example V.7 (Doubly symmetric binary symmetric channel)

  • For the example with λ = 0.1, γ = 0.01, and k = 20, the reported value is q₂ ≈ 1.516 × 10⁻⁵.For α = 2, q₂(γ) can be computed explicitly.Source: C. Examples · p. 5

Example V.8 (Rare-event Z-Channel)

  • The rare-event Z-channel has X ∼ Bern(t), Kt(1|0) = 0, and Kt(1|1) = t, giving Y ∼ Bern(t²).Its nonzero joint probabilities are PXY(0,0)=1−t, PXY(1,0)=t(1−t), and PXY(1,1)=t².Source: C. Examples · p. 5
  • For the Z-channel with t ≈ 0.048, n = 56, and k = 4, the example numerically compares the binary-inversion converse with hypercontractivity.The hypercontractivity value is obtained by bisection; the passages do not state which bound is larger in this example.Source: C. Examples · p. 5

AI STATEMENT

The authors report using OpenAI’s Codex for language editing and expository suggestions, mathematical consistency checks, literature and reference checks, and numerical verification for Examples V.7 and V.8, including Figure 1.

AI STATEMENT

  • OpenAI’s Codex assisted with editing, consistency and reference checks, and numerical verification for Examples V.7 and V.8, including Figure 1.The authors state that they reviewed and edited the AI-assisted material and take responsibility for the paper’s content.Source: AI STATEMENT · p. 6
Loading 2610.13030v1…