Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy
Abstract
We study asymmetric simple binary hypothesis testing between H0:P0n and H1:P1n, 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α(P1|P0) and Dα(P0|P1), 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 α∈ (0,1), the main converse recovers the phase transition of the optimal Type II error under the exponentially decaying Type I error constraint εn=e−nr. Under regularity conditions, the optimal Type II error vanishes exponentially when r<D(P1|P0) and converges exponentially fast to one when r>D(P1|P0). 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.
Related
BibTeX
@misc{bruno2026finitesample,
title = {{Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy}},
author = {Roberto Bruno and Adrien Vandenbroucque and Amedeo Roberto Esposito},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27617},
eprint = {2609.27617},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27617},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy
AU - Roberto Bruno
AU - Adrien Vandenbroucque
AU - Amedeo Roberto Esposito
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27617
UR - https://arxiv.org/abs/2609.27617
AB - 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 α∈ (0,1), the main converse recovers the phase transition of the optimal Type II error under the exponentially decaying Type I error constraint ε_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.
ER -