Hypothesis testing is a statistical inference framework for determining the true distribution among a set of possible distributions for a given dataset. Privacy restrictions may require the curator of the data or the respondents themselves to share data with the test only after applying a randomizing privacy mechanism. This work considers mutual information (MI) as the privacy metric for measuring leakage. In addition, motivated by the Chernoff-Stein lemma, the relative entropy between pairs of distributions of the output (generated by the privacy mechanism) is chosen as the utility metric. For these metrics, the goal is to find the optimal privacy-utility trade-off (PUT) and the corresponding optimal privacy mechanism for both binary and m-ary hypothesis testing. Focusing on the high privacy regime, Euclidean information-theoretic approximations of the binary and m-ary PUT problems are developed. The solutions for the approximation problems clarify that an MI-based privacy metric preserves the privacy of the source symbols in inverse proportion to their likelihoods.
@cite_14: Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where both the data providers and data analysts want to maximize the utility of statistical analyses performed on the released data, we study the fundamental trade-off between local differential privacy and utility. This trade-off is formulated as a constrained optimization problem: maximize utility subject to local differential privacy constraints. We introduce a combinatorial family of extremal privatization mechanisms, which we call staircase mechanisms, and show that it contains the optimal privatization mechanisms for a broad class of information theoretic utilities such as mutual information and @math -divergences. We further prove that for any utility function and any privacy level, solving the privacy-utility maximization problem is equivalent to solving a finite-dimensional linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the size of the alphabet the data lives in. To account for this, we show that two simple privatization mechanisms, the binary and randomized response mechanisms, are universally optimal in the low and high privacy regimes, and well approximate the intermediate regime.
Our problem differs from these efforts in using MI as the privacy metrics. In @cite_14 , the L-DP formulation, focused on the high privacy regime, requires the mechanism to limit distinction between any two letters of the source alphabet for a given output. The requirement also gathers all privacy mechanisms satisfying a desired privacy protection measured by L-DP within a hypercube. Therefore, the authors simplify the trade-off problem to a linear program by exploring the sub-linearity of the relative entropy function. In contrast, all privacy mechanisms giving a desired MI-based privacy form a convex set which is not a polytope. However, taking advantage of E-IT, we propose good approximations for the MI-based privacy utility trade-offs in high privacy regime. In fact, we present closed-form privacy mechanisms for both binary hypothesis testing with arbitrary alphabets as well as @math -ary hypothesis testing with binary alphabets. Furthermore, for @math -ary hypothesis testing with arbitrary sources, the privacy mechanism can be attained effectively by solving an SDP.