PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite-Sample Binary Hypothesis Testing via R\'enyi Divergences: Strong Converse and Local Privacy

Roberto Bruno, Adrien Vandenbroucque, Amedeo Roberto Esposito

arXiv:2609.27617v1cs.ITmath.ITmath.STstat.TH

TL;DR

Finite-sample performance guarantees are needed for asymmetric binary hypothesis testing. The paper derives Rényi-divergence converses and complementary achievability bounds, extending its analysis to locally private observations. Under an exponentially decaying Type I constraint, the bounds control Type II error on either side of the known phase transition.

  • Problem

    Asymptotic results do not provide performance guarantees at finite sample sizes for the optimal Type II error under a Type I constraint.

    Source: §I · pp. 1–2

  • Method

    The paper derives a finite-sample Rényi converse that tensorises and recovers data-processing converses, then extends the analysis to locally differentially private observations.

    Source: §IX · p. 23

  • Results

    Under an exponentially decaying Type I constraint, the two Rényi bounds provide explicit exponential control of the optimal Type II error on the respective sides of the known phase transition.

    Source: §IX · p. 23

  • Takeaways & Limitations

    The bounds extend to locally private testing, where a distribution-independent contraction coefficient yields finite-sample converse and sample-complexity lower bounds.

    Source: §IX · p. 23

Abstract

from arXiv · show

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\'enyi divergence of order $\alpha$, we derive our main result: a finite-sample converse with $\alpha>1$. The bound uses both directions of the divergence $D_\alpha(P_1\|P_0)$ and $D_\alpha(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_\gamma$, Hellinger, and Kullback Leibler divergences, thereby recovering familiar converses within a unified framework. Together with an achievability bound involving R\'enyi divergence with $\alpha\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.

I. INTRODUCTION

Finite-sample strong-converse guarantees are needed because asymptotic results do not ensure useful performance at finite sample sizes. The paper uses Rényi and f-divergence variational bounds to capture the phase transition and support sample-complexity estimates.

I. INTRODUCTION

  • Finite-sample guarantees are missing from asymptotic results, motivating bounds that remain informative at small to moderate sample sizes.The desired bounds should tensorise and recover convergence of the Type II error to one above the KL threshold.Source: §I · p. 2
  • Rényi converses with order α > 1 tensorise and capture the strong-converse regime, while orders below one provide complementary achievability bounds.The converse uses divergences in both directions and recovers data-processing converses as boundary cases.Source: §I · p. 2
  • The same variational approach extends to general f-divergences and recovers familiar converses for standard divergences within a unified framework.The framework makes comparisons with the Rényi bound transparent.Source: §I · p. 2
  • Under regularity conditions, the optimal Type II error vanishes exponentially for r < D(P1∥P0) and approaches one exponentially for r > D(P1∥P0).These bounds recover the phase transition under an exponentially decaying Type I constraint.Source: §I · p. 2
  • The finite-sample bounds can be inverted to characterise sample complexity.The paper applies this to behaviour on both sides of the phase transition.Source: §I · p. 2

A. Contributions

The paper develops finite-sample Rényi converses and complementary achievability bounds, then applies them to phase-transition and sample-complexity analyses, including locally private observations.

A. Contributions

  • The finite-sample converse based on D_λ for λ > 1 uses divergence terms in both directions and recovers standard data-processing converses at boundary parameter choices.The bound tensorises under independent observations.Source: A. Contributions · p. 2
  • For λ ∈ (0, 1), an achievability bound for log-likelihood-ratio tests complements the converse; together, the bounds recover the exponential Type II error phase transition.Under regularity conditions, β_n(ε_n) approaches one exponentially for r > D(P1∥P0) and vanishes exponentially for r < D(P1∥P0).Source: A. Contributions · p. 2
  • Inverting the finite-sample bounds gives sample-complexity lower and upper bounds, with the lower bound improving the leading constant in a recent Hellinger-based estimate.The improvement is stated under the same regularity conditions.Source: A. Contributions · p. 2
  • In strongly asymmetric regimes, the paper reports that its lower and upper bounds are asymptotically matching.The contribution summary does not specify the bounds' quantitative gap.Source: A. Contributions · p. 3
  • For locally differentially private observations, the paper derives privacy-dependent converse and sample-complexity lower bounds, plus achievability guarantees using two staircase mechanisms.These results identify achievability and strong-converse regimes under exponentially decaying Type I constraints.Source: A. Contributions · p. 3

II. RELATED WORK

Existing testing bounds trade off sharp finite-sample characterisations, tensorisation, and strong-converse guarantees. The paper positions Rényi divergence as a tractable tensorising bridge and uses f-divergences to unify familiar converses.

II. RELATED WORK

  • Total variation gives the exact minimum sum of the two errors, while total variation and E_γ do not have a simple additive tensorisation rule.Exact evaluation under product measures can become computationally difficult as n grows.Source: §II · p. 3
  • Elementary KL finite-sample bounds generally give only a weak converse; stronger methods use blowing-up or smoothing-out arguments and may remain loose at moderate n.The stronger approaches rely on advanced machinery.Source: §II · p. 3
  • Hellinger-based methods tensorise and support sample-complexity characterisations, making them natural for estimating the samples needed to attain prescribed errors.The cited work characterises sample complexity up to universal constants.Source: §II · p. 4
  • Rényi divergence provides a finite-sample bridge through exact tensorisation, while optimising its order around one recovers the KL-governed phase transition.Related work connects Rényi divergence to hypothesis testing and strong-converse exponents –.Source: §II · p. 4
  • The paper's f-divergence analysis unifies well-known converses under the same variational principle, clarifying their relation to the Rényi bound.Source: §II · p. 4

III. PRELIMINARIES AND NOTATION

The paper formulates asymmetric testing on n-fold product distributions and defines randomized tests as conditional probabilities of choosing the alternative. It also defines the optimal Type II error subject to a Type I constraint.

III. PRELIMINARIES AND NOTATION

  • The testing setup compares n-fold product distributions P0^n and P1^n.The notation identifies P_j^n as the n-fold product of P_j.Source: §III · p. 4
  • A randomized test maps each observation to the conditional probability of deciding H1, with Type I and Type II errors defined for that test.A deterministic test takes values in {0, 1} and is identified with its rejection region.Source: §III · p. 4
  • β_ε(P, Q) is the smallest Type II error over tests whose Type I error under P is at most ε.The first argument is the null distribution and the second is the alternative distribution.Source: §III · p. 4

A. Divergences

The section defines Rényi and f-divergences and connects particular f choices to classical information measures. It also gives a variational representation and notes that Rényi divergence tensorises under products.

A. Divergences

  • Rényi divergence of order λ is defined for probability measures P and Q, with a stated right-limit property when D_1+s(P∥Q) is finite for some s > 0.The section also states that Rényi divergence tensorises exactly under products.Source: A. Divergences · p. 5
  • An f-divergence is defined from a convex, lower-semicontinuous function f with f(1) = 0, with conventions specified for zero denominators.Source: A. Divergences · p. 5
  • The squared Hellinger distance and Kullback–Leibler divergence are identified as particular f-divergences, with f_KL(t) = t log t.Source: A. Divergences · pp. 5–6
  • The f-divergence admits a variational representation using the convex conjugate f⋆ and measurable functions for which the expectations are well defined.For that representation, f is extended to +∞ for negative inputs.Source: A. Divergences · p. 6

IV. CONVERSE AND ACHIEVABILITY BOUNDS VIA R´ENYI DIVERGENCES

The section derives finite-sample converse bounds from Rényi divergence of order greater than one and gives an achievability bound using orders below one. The converse includes the data-processing bound as a boundary case, and the likelihood-ratio achievability result supports the phase-transition analysis.

IV. CONVERSE AND ACHIEVABILITY BOUNDS VIA R´ENYI DIVERGENCES

  • Theorem 1 gives a finite-sample converse using Rényi orders λ > 1 and divergence terms in both hypothesis directions.The bound assumes mutually absolutely continuous product measures and restricts the suprema to orders with finite displayed divergences.Source: §IV · p. 6
  • The full converse includes the Rényi data-processing bound and can be strictly tighter when its optimum occurs at finite c.Source: §IV · p. 7
  • The section derives a finite-sample upper bound on the Type II error of a likelihood-ratio test using Rényi divergence of order λ ∈ (0, 1).Source: §IV · p. 7

Appendix A-D.

  • The likelihood-ratio achievability bound is converted, via the Neyman–Pearson lemma, into a bound on β_n(ε) and is used to establish the achievability side of the phase transition.Source: Appendix A · pp. 7–8

V. PHASE TRANSITION OF THE OPTIMAL ERROR

The paper combines finite-sample converse and achievability bounds to characterize the Type II error phase transition, compares Rényi converses with other divergence bounds, and inverts finite-sample bounds for sample complexity.

V. PHASE TRANSITION OF THE OPTIMAL ERROR

  • The finite-sample bounds provide explicit exponential estimates for the optimal Type II error and recover the classical phase transition as n → ∞.The threshold separates the achievability and strong-converse regimes.Source: §V · p. 8
  • For ε_n = e^−nr, the optimal Type II error vanishes exponentially when r < D(P1∥P0) and converges exponentially fast to one when r > D(P1∥P0).The result assumes mutual absolute continuity and D_1+s(P1∥P0) < ∞ for some s > 0; the boundary r = D(P1∥P0) is unresolved by this argument.Source: §V · p. 8

VI. COMPARISON WITH OTHER DIVERGENCES

  • The numerical comparison omits the E_γ converse because its lack of tensorisation makes computation intractable for large n.Source: §VI · p. 9
  • In numerical comparisons, the Rényi converse captures strong-converse behavior even at moderate sample sizes and generally characterizes Type II error more tightly than KL- and Hellinger-λ-based converses in constant and linear-decay regimes.Source: §VI · p. 10

VII. SAMPLE COMPLEXITY

  • The finite-sample converse and achievability bounds are inverted to obtain lower and upper bounds on the sample complexity.The displayed corollaries impose distinctness and mutual absolute continuity of P0 and P1.Source: §VII · pp. 10–12

A. Comparisons with existing results

The section compares finite-sample bounds with existing results, including sample-complexity behavior and asymptotic matching under stated regularity conditions, and extends the analysis to locally differentially private observations. It describes privacy-dependent Type II error regimes, a possible gap between their thresholds, and recovery of the non-private achievability bound as the privacy constraint vanishes.

A. Comparisons with existing results

  • With D1+η(P1∥P0)<∞, the lower sample-complexity bound improves, by a factor of two, and the upper and lower bounds match asymptotically when δ is fixed and ε vanishes.By symmetry, the corresponding conclusion holds when ε is fixed and δ vanishes, assuming D1+η(P0∥P1)<∞.Source: A. Comparisons with existing results · pp. 12–13, Appendix E · p. 13

Appendix E-C.

  • For ε_m=e^-mR, fixed δ, and 0<D(P1∥P0)<∞ with D1+η(P1∥P0)<∞, the sample-complexity bounds satisfy U_m/L_m→1.This gives the exact first-order scaling in the regime where the Type I error decays exponentially and the Type II error is fixed.Source: Appendix E · p. 14
  • In the Bernoulli comparison, Dλ(P0∥P1) gives the tighter lower bound when δ≪ε, while Dλ(P1∥P0) does so when ε≪δ; the proposed bounds are tighter than across sample sizes.The comparison reports that the proposed lower bounds particularly improve on in strongly asymmetric regimes.Source: Appendix E · p. 14, Figure 3 · p. 15
  • The numerical upper-bound comparison finds the proposed bound tighter in strongly asymmetric regimes, while the compared bounds behave similarly when ε=δ.This agrees with the analytical comparison described for symmetric and asymmetric regimes.Source: Appendix E · pp. 14–15, Figure 4 · p. 16

VIII. LOCAL DIFFERENTIAL PRIVACY

  • For independently privatized observations, the finite-sample bounds apply with Rényi divergences between the original distributions replaced by divergences between their privatized versions.The testing problem remains unchanged apart from replacing the original product measures with the corresponding privatized product measures.Source: §VIII · pp. 16–17
  • As ϵdp decreases toward zero, privacy becomes more stringent, yielding much larger converse lower bounds and larger private achievable upper bounds, thereby degrading the testing error trade-off.Each private upper bound is nonincreasing in ϵdp and approaches its corresponding non-private bound as ϵdp → ∞.Source: §VIII · pp. 18, 20, 21
  • The private sample-complexity lower bound is the non-private lower bound multiplied by a privacy-dependent factor.Corollary 7 derives the bound under its stated assumptions; the supplied passage does not specify the factor's value.Source: §VIII · p. 18
  • For sufficiently small εdp, the binary mechanism maximises every f-divergence between privatised distributions [32], but it discards information within A and its complement.Its binary-statistic reduction generally does not recover the non-private bound as εdp → ∞.Source: §VIII · pp. 19–20
  • The k-ary randomised response channel converges to the identity as εdp → ∞, so its achievability bound recovers the non-private bound.For sufficiently large εdp, it maximises the KL divergence between privatised distributions [32], though this does not establish optimality for every Rényi order.Source: §VIII · p. 20
  • The Corollary 8 upper bound tracks the exact optimal private Type II error more closely for vanishing Type I constraints, particularly in the exponential regime.For a fixed Type I constraint, it remains close to 1 − εn but becomes increasingly conservative as n grows; in the exponential regime, both bound and exact error increase toward one.Source: §VIII · pp. 21–22, Figure 8 · p. 22
  • For finite-alphabet testing with fixed finite εdp and exponentially decaying Type I error, Theorem 4 identifies regimes of exponential convergence of the optimal private Type II error to zero or one, possibly with a threshold gap.The theorem assumes mutually absolutely continuous distributions and the independent-channel LDP model.Source: §VIII · p. 21
  • Private Type II error converges to 1 for r > rcon and to 0 for 0 < r < rach, leaving the interval between thresholds unresolved.Here rach := Dach(ϵdp) and rcon := (1 − e^−ϵdp)D(P1∥P0); the paper conjectures the exact threshold is supT∈Cϵdp D(TP1∥TP0).Source: §VIII · pp. 22–23
  • The private converse uses a distribution-independent contraction bound, while achievability uses an explicit lower bound and two mechanisms suited to complementary privacy regimes.The binary mechanism is optimal in the high-privacy regime; randomised response attains supT∈Cϵdp D(TP1∥TP0) in the low-privacy regime and recovers the non-private bound as ϵdp → ∞.Source: §VIII · p. 23
  • Outside those regimes, the two mechanisms need not attain the converse's divergence bound, and matching privacy bounds across all levels remain open.The gap may reflect both the contraction estimate in the converse and restricting achievability to these two mechanisms.Source: §VIII · p. 23

IX. CONCLUSION

  • The paper's primary contribution is a finite-sample Rényi converse for asymmetric binary testing, derived variationally using both divergence directions and tensorising under independent observations.The optimisation recovers standard data-processing converses as a limiting case and extends the comparison framework to total variation, Eγ, and Hellinger converses.Source: §IX · p. 23
  • Rényi achievability and converse bounds give explicit exponential control of Type II error on either side of the phase-transition rate; inversion also bounds sample complexity.Under regularity conditions, the sample-complexity bounds are asymptotically matching in strongly asymmetric regimes.Source: §IX · p. 23
  • For local privacy, contraction gives converse and sample-complexity lower bounds, while the binary mechanism and k-ary randomised response provide achievability and upper bounds.The mechanisms suit complementary privacy regimes, and k-ary randomised response recovers the non-private achievability bound as the privacy constraint vanishes.Source: §IX · p. 23
  • The private bounds identify regimes where optimal Type II error converges exponentially to zero or one, but do not determine the exact threshold across all privacy levels.Closing the gap may require a stronger admissible achievability channel or a tighter contraction-based converse.Source: §IX · pp. 23–24

B. Proof of Corollary 1

The proof analyzes the two branches separately, locating their extrema through derivative signs and conditions on the directional Rényi divergences. Depending on those conditions, each branch’s supremum occurs at a boundary or at a unique positive maximizer.

B. Proof of Corollary 1

  • When λnDλ(P1∥P0)=1, the Rλ derivative is strictly negative throughout, placing its supremum at c→0+.Source: B. Proof of Corollary 1 · p. 27
  • For the Rλ branch, the derivative is positive for c<cλ,R and negative for c>cλ,R, so cλ,R is its unique maximizer.The proof also gives the value at that maximizer.Source: B. Proof of Corollary 1 · p. 28
  • For the other Rλ branch, the derivative is strictly positive throughout, so its supremum is attained as c→∞.Source: B. Proof of Corollary 1 · p. 28
  • When nDλ(P0∥P1)>0, monotonicity of Ψ yields a unique positive cλ,F and a global maximum of Fλ there.The proof evaluates Fλ at that maximizer using the stated identity.Source: B. Proof of Corollary 1 · pp. 28–29
  • When nDλ(P0∥P1)=0, the Fλ derivative is negative throughout, so its supremum is attained as c→0+.Source: B. Proof of Corollary 1 · pp. 28–29

C. Proof of Remark 1

This section develops converse results for binary hypothesis testing, showing how the bounds recover data-processing counterparts and extending them through a unified f-divergence framework. It also proves auxiliary sample-complexity and divergence refinements and analyzes the strongly asymmetric regime.

C. Proof of Remark 1

  • Taking the limit as c grows without bound in each of the two bounds recovers its corresponding data-processing converse.The proof treats the bounds separately and concludes that each perfectly recovers the corresponding bound achieved via DPI.Source: C. Proof of Remark 1 · pp. 29–30

D. Proof of Theorem 2

  • Theorem 2’s bound follows by applying likelihood-ratio threshold properties of a possibly randomized test and optimizing over λ in (0, 1).The test selects under H1 above the threshold and under H0 below it, with randomization allowed at equality.Source: D. Proof of Theorem 2 · p. 30

E. Proof of Corollary 2

  • Corollary 2 follows by optimizing a strictly concave function and taking the infimum over λ in (0, 1).The argument uses a possibly randomized Neyman–Pearson test attaining β_n(ε) with Type I error ε.Source: E. Proof of Corollary 2 · pp. 30–31

APPENDIX B UNIFIED f-DIVERGENCE FRAMEWORK

  • Restricting the f-divergence variational representation to indicator functions yields the binary data-processing inequality for the induced test decision.The framework also establishes that optimizing this binary reduction recovers the f-divergence between the corresponding binary distributions.Source: Appendix B · pp. 31–32
  • The cited passages establish bounds on βn when a > b and when f⋆(a) > f⋆(b), and state that combining (112) with (114) proves (108).Source: Appendix B · pp. 33–34
  • The supplied Corollary 10 excerpt includes Eγ(P n 0 ∥P n 1 ) alongside ε and γ, but it lacks enough context to identify the result or its conditions.Source: Appendix B · p. 35
  • Corollary 11 gives a finite-sample Hellinger-divergence converse for mutually absolutely continuous hypotheses, while Corollary 12 recovers the classical Fano bound.The Hellinger bound applies for ε ∈ (0, 1) and λ ∈ (0, 1).Source: Appendix B · pp. 36, 38

APPENDIX C KL-BASED CONVERSE BOUNDS WITH REFINEMENTS

  • For finite alphabets with common support, smoothing-out yields a more refined pair of KL converse bounds than the classical bound; unbounded alphabets may make the required infinity norms unbounded.The smoothing-out argument can still be adapted to obtain finite-sample bounds when the alphabet is unbounded.Source: Appendix C · p. 38

APPENDIX D

  • Appendix D proves the two regimes by choosing Rényi orders near one on the appropriate side, so the exponential terms vanish as n grows.The proof treats r > D(P1∥P0) and r < D(P1∥P0) separately before combining the cases.Source: Appendix D · p. 39

A. Proof of Corollary 3

  • For sample complexity, the two converse bounds are optimized over λ and an auxiliary c, with the closed-form c optimizers positive whenever ε + δ < 1.The proof establishes a unique global maximum for each bound at its optimizer.Source: A. Proof of Corollary 3 · p. 40

B. Proof of Corollary 4

  • The Corollary 4 proof ensures βnλ(ε) ≤ δ, yielding n(ε, δ) ≤ nλ and hence an infimum bound over λ ∈ (0, 1).Source: B. Proof of Corollary 4 · p. 41

C. Proof of Remark 2

  • In the strongly asymmetric regime with fixed δ ∈ (0, 1/32] and ε → 0, the refined bound improves the leading constant by a factor of two.The proof compares its asymptotic bound with the earlier bound; it also shows the relevant term in the refined bound is independent of ε.Source: C. Proof of Remark 2 · pp. 41–42

D. Proof of Remark 3

The proof treats symmetric and asymmetric error regimes separately. In both, it verifies that the bounds have the stated matching behavior.

D. Proof of Remark 3

E. Proof of Corollary 5

The proofs establish asymptotic matching of the bounds for an exponentially decreasing error constraint, then apply the private-channel converse under mutual absolute continuity.

E. Proof of Corollary 5

  • With εm=e^-mR and fixed δ, the lower and upper bounds converge to the same positive limit, with Um/Lm→1.The lower-bound argument takes λ→1+ using convergence of Dλ(P1∥P0) to D(P1∥P0).Source: E. Proof of Corollary 5 · pp. 43–44

F. Proof of Corollary 8

  • For Corollary 8, mutual absolute continuity permits applying Corollary 2 to the two induced distributions; choosing bTλ for every channel and taking the infimum proves the result.Source: F. Proof of Corollary 8 · p. 44

G. Proof of Theorem 4

The proof establishes that the achievability rate is no greater than the converse rate. It handles the two rate regimes using Rényi-divergence continuity and an auxiliary inequality.

G. Proof of Theorem 4

Loading 2609.27617v1…