Finite-sample hypothesis testing bounds quantify privacy tradeoffs
Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy
Information Theory
Summary
This paper studies deciding between two simple possibilities using a limited number of data points. The authors find precise mathematical limits on how well you can tell the difference with finite samples, based on a tool called Rényi divergence. They also show how these limits change when the data is subject to local privacy restrictions, explaining the cost of keeping data private. Their results unify and extend several known testing bounds into one framework.
What this means in practice
- •For data privacy engineers: Quantify the tradeoff between privacy constraints and hypothesis testing accuracy to design better private data analysis systems.
- •For statistical inference teams: Use tight finite-sample bounds to evaluate error tradeoffs in hypothesis tests with limited data.
A theory result. No direct application yet.
Authors
Roberto Bruno, Adrien Vandenbroucque, Amedeo Roberto Esposito
Abstract
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 $α\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.