The Structure of Optimal Private Tests for Simple Hypotheses

Introduction

Hypothesis testing plays a central role in statistical inference, analogous to that of decision or promise problems in computability and complexity theory. A hypothesis testing problem is specified by two disjoint sets of probability distributions over the same set, called hypotheses, ${\mathcal{H}}_{0}$ and ${\mathcal{H}}_{1}$. An algorithm $T$ for this problem, called a hypothesis test, is given a sample $x$ from an unknown distribution $P$, with the requirement that $T(x)$ should, with high probability, output “0” if $P\in{\mathcal{H}}_{0}$, and “1” if $P\in{\mathcal{H}}_{1}$. There is no requirement for distributions outside of ${\mathcal{H}}_{0}\cup{\mathcal{H}}_{1}$. In computer science, such problems sometimes go by the name distribution property testing.

Hypothesis testing problems are important in their own right, as they formalize yes-or-no questions about an underlying population based on a randomly drawn sample, such as whether education strongly influences life expectancy, or whether a particular medical treatment is effective. Successful hypothesis tests with high degrees of confidence remain the gold standard for publication in top journals in the physical and social sciences. Hypothesis testing problems are also important in the theory of statistics and machine learning, as many lower bounds for estimation and optimization problems are obtained by reducing from hypothesis testing.

This paper aims to understand the structure and sample complexity of optimal hypothesis tests subject to strong privacy guarantees. Large collections of personal information are now ubiquitous, but their use for effective scientific discovery remains limited by concerns about privacy. In addition to the well-understood settings of data collected during scientific studies, such as clinical experiments and surveys, many other data sources where privacy concerns are paramount are now being tapped for socially beneficial analysis, such as Social Science One [Soc18], which aims to allow access to data collected by Facebook and similar companies.

We study algorithms that satisfy differential privacy (DP) [DMNS06], a restriction on the algorithm that ensures meaningful privacy guarantees against an adversary with arbitrary side information [KS08]. Differential privacy has come to be the de facto standard for the analysis of private data, used as a measure of privacy for data analysis systems at Google [EPK14], Apple [Dif17], and the U.S. Census Bureau [DLS+17]. Differential privacy and related distributional notions of algorithmic stability can be crucial for statistical validity even when confidentiality is not a direct concern, as they provide generalization guarantees in an adaptive setting [DFH+15b].

Consider an algorithm that takes a set of data points from a set $\mathcal{X}$—where each point belongs to some individual—and produces some public output. We say the algorithm is differentially private if no single data point can significantly impact the distribution on outputs. Formally, we say two data sets $x,x^{\prime}\in\mathcal{X}^{n}$ of the same size are neighbors if they differ in at most one entry.

A randomized algorithm $T$ taking inputs in $\mathcal{X}^{*}$ and returning random outputs in a space with event set $\mathcal{S}$ is ${\varepsilon}$-differentially private if for all $n\geq 1$, for all neighboring data sets $x,x^{\prime}\in\mathcal{X}^{n}$, and for all events $S\in\mathcal{S}$,

For algorithms with binary outputs, this definition is essentially equivalent to all other commonly studied notions of privacy and distributional algorithmic stability (see “Connections to Algorithmic Stability”, below).

Contribution: The Sample Complexity of Private Tests for Simple Hypotheses. We focus on the setting of i.i.d. data and singleton hypotheses ${\mathcal{H}}_{0},{\mathcal{H}}_{1}$, which are called simple hypotheses. The algorithm is given a sample of $n$ points $x_{1},\dots,x_{n}$ drawn i.i.d. from one of two distributions, $P$ or $Q$, and attempts to determine which one generated the input. That is, ${\mathcal{H}}_{0}=\left\{{P^{n}}\right\}$ and ${\mathcal{H}}_{1}=\left\{{Q^{n}}\right\}$. We investigate the following question.

Given two distributions $P$ and $Q$ and a privacy parameter ${\varepsilon}>0$, what is the minimum number of samples (denoted $\mathit{SC}^{P,Q}_{{\varepsilon}}$) needed for an ${\varepsilon}$-differentially private test to reliably distinguish $P$ from $Q$, and what are optimal private tests?

These questions are well understood in the classical, nonprivate setting. The number of samples needed to distinguish $P$ from $Q$ is $\Theta(1/H^{2}(P,Q))$, where $H^{2}$ denotes the squared Hellinger distance (3).This statement is folklore, but see, e.g., [BY02] for the lower bound, [Can17] or Corollary 2.2 for the upper bound. Furthermore, by the Neyman–Pearson lemma, the exactly optimal test consists of computing the likelihood ratio $P^{n}(x)/Q^{n}(x)$ and comparing it to some threshold.

Our result provides the first instance-specific characterization of a statistical problem’s complexity for differentially private algorithms. Understanding the private sample complexity of statistical problems is delicate. We know there are regimes where statistical problems can be solved privately “for free” asymptotically (e.g. [DMNS06, CMS11, Smi11, KV18]) and others where there is a significant cost, even for relaxed definitions of privacy (e.g. [BUV14, DSS+15]), and we remain far from a general characterization of the statistical cost of privacy. Duchi, Jordan, and Wainwright [DJW13] give a characterization for the special case of simple tests by local differentially private algorithms, a more restricted setting where samples are randomized individually, and the test makes a decision based on these randomized samples. Our characterization in the general case is more involved, as it exhibits several distinct regimes for the parameter ${\varepsilon}$.

Our analysis relies on a number of tools of independent interest: a characterization of private hypothesis testing in terms of couplings between distributions on $\mathcal{X}^{n}$, and a novel interpretation of Hellinger distance as the advantage over random guessing of a specific, randomized likelihood ratio test.

The Importance of Simple Hypotheses. Many of the hypotheses that arise in application are not simple, but are so-called composite hypotheses. For example, deciding if two features are independent or far from it involves sets ${\mathcal{H}}_{0}$ and ${\mathcal{H}}_{1}$ each containing many distributions. Yet many of those tests can be reduced to simple ones. For example, deciding if the mean of a Gaussian is less than 0 or greater than 1 can be reduced to testing if the mean is either 0 or 1. Furthermore, simple tests arise in lower bounds for estimation—the well-known characterization of parametric estimation in terms of Fisher information is obtained by showing that the Fisher information measures variability in the Hellinger distance and then employing the Hellinger-based characterization of nonprivate simple tests (e.g. [Bor99, Chap. II.31.2, p.180]).

Our characterization of private testing implies similar lower bounds for estimation (along the lines of lower bounds of Duchi and Ruan [DR18] in the local model of differential privacy).

Connection to Algorithmic Stability. For hypothesis tests with constant error probabilities, sample complexity bounds for differential privacy are equivalent, up to constant factors, to sample complexity bounds for other notions of distributional algorithmic stability, such as $({\varepsilon},\delta)$-DP [DKM+06], concentrated DP [DR16, BS16], KL- and TV-stability [WLF16, BNS+16] (see [ASZ18, Lemma 5]). (Briefly: if we ensure that $\Pr(T(x)=1)\in[0.01,0.99]$ for all $x$, then an additive change of ${\varepsilon}$ corresponds to an multiplicative change of $1\pm O({\varepsilon})$, and vice-versa.) Consequently, our results imply optimal tests for use in conjunction with stability-based generalization bounds for adaptive data analysis, which has generated significant interest in recent years [DFH+15b, DFH+15a, DFH+15c, RZ16, BNS+16, RRST16, XR17, FS17, FS18].

To put our result in context, we review classical results about non-private hypothesis testing. Let $P$ and $Q$ be two probability distributions over an arbitrary domain $\mathcal{X}$. A hypothesis test K\colon\mathcal{X}^{*}\to\{\text{``P''},\text{``Q''}\} is an algorithm that takes a set of samples $x\in\mathcal{X}^{*}$ and attempts to determine if it was drawn from $P$ or $Q$. Define the advantage of a test $K$ given $n$ samples as

for some threshold $\kappa$. We will sometimes abuse notation and use the test statistic $S$ and the implied hypothesis test $K_{S}$ interchangeably.

Another classical result says that the optimal sample complexity is characterized by the squared Hellinger distance between $P,Q$, which is defined as

Specifically, $\mathit{SC}^{P,Q}=\mathit{SC}^{P,Q}(\operatorname{LLR})=\Theta(1/H^{2}(P,Q))$. Note that the same metric provides upper and lower bounds on the sample complexity.

2 Our Results

Our main result is an approximate characterization of the sample complexity of ${\varepsilon}$-differentially private tests for distinguishing $P$ and $Q$. Analogous to the non-private case, we will write \mathit{SC}^{P,Q}_{{\varepsilon}}=\min_{\textrm{{\varepsilon}$-DP$K}}\mathit{SC}^{P,Q}(K) to denote the sample complexity of ${\varepsilon}$-differentially privately (${\varepsilon}$-DP) distinguishing $P$ from $Q$, and we characterize this quantity up to constant factors in terms of the structure of $P,Q$ and the privacy parameter ${\varepsilon}$. Specifically, we show that a privatized clamped log-likelihood ratio test is optimal up to constant factors. This privatization may be achieved through either the Laplace or Exponential mechanism, and we will prove optimality of both methods.

For parameters $b\geq a$, we define the clamped log-likelihood ratio statistic,

where $[\cdot]_{a}^{b}$ denotes the projection onto the interval $[a,b]$ (that is, $[z]_{a}^{b}=\max(a,\min(z,b))$).

Define the soft clamped log-likelihood test:

The test $\operatorname{scLLR}$ is an instance of the exponential mechanism [MT07], and thus $\operatorname{scLLR}_{a,b}$ satisfies ${\varepsilon}$-differential privacy for ${\varepsilon}=\frac{b-a}{2}$.

Similarly, define the noisy clamped log-likelihood ratio test:

The test $\operatorname{ncLLR}$ is an instance of postprocessing the Laplace mechanism [DMNS06], and satisfies ${\varepsilon}$-differential privacy.

Our main result is that, for every $P,Q$, and every ${\varepsilon}$, the tests $\operatorname{scLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}$ and $\operatorname{ncLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}$ are optimal up to constant factors, for some appropriate $0\leq{\varepsilon}^{\prime}\leq{\varepsilon}$. To state the result more precisely, we introduce some additional notation. First define

and assume without loss of generality that $\tau=\intop\nolimits_{\mathcal{X}}\max\{P(x)-e^{{\varepsilon}}Q(x),0\}\,dx$, which we assume for the remainder of this work.For $\alpha\geq 0$, the quantity $D_{\alpha}(P\|Q)=\intop\nolimits\max(P(x)-\alpha Q(x),0)\,dx$ is an $f$-divergence and has appeared in the literature before under the names $\alpha$-divergence, hockey-stick divergence, or elementary divergence [LCV15, BBG18] (for $\alpha=1$, one obtains the usual total variation distance). Thus, $\tau$ is the maximum of the divergences $D_{e^{{\varepsilon}}}(P\|Q)$ and $D_{e^{{\varepsilon}}}(Q\|P)$. It can also be described as the smallest value $\delta$ such that $P$ and $Q$ are $({\varepsilon},\delta)$-indistinguishable [DR14]. Next, let $0\leq{\varepsilon}^{\prime}\leq{\varepsilon}$ be the largest value such that

The distributions $P^{\prime},Q^{\prime}$ are such that

where $P^{\prime\prime}$ and $Q^{\prime\prime}$ are distributions with disjoint support. The quantity $\tau$ is the smallest possible number for which such a representation is possible. With these definitions in hand, we can now state our main result.

For every pair of distributions $P,Q$, and every ${\varepsilon}>0$, the optimal sample complexity for ${\varepsilon}$-differentially private tests is achieved by either the soft or noisy clamped log-likelihood test, and satisfies

When ${\varepsilon}\geq\max_{x}\left|\log P(x)/Q(x)\right|$, Theorem 1.2 reduces to $\mathit{SC}^{P,Q}_{{\varepsilon}}=\Theta\left(\frac{1}{H^{2}(P,Q)}\right)$, which is the sample complexity for distinguishing between $P$ and $Q$ in the non-private setting. This implies that we get privacy for free asymptotically in this parameter regime. We will focus on proving the first equality in this paper, the second is proved in Appendix E.

Comparison to Known Bounds. For ${\varepsilon}<1$, the bounds

follow directly from the non-private sample complexity. Namely, the lower bound is the non-private sample complexity and the upper bound is obtain by applying the sample-and-aggregate technique [NRS07] to the optimal non-private test. They can be recovered from Theorem 1.2 by noting that

where $\mathcal{S}=\left\{\;x\;\colon\;P(x)-e^{{\varepsilon}}Q(x)>0\;\right\}$.

As an application of our result, we obtain optimal private algorithms for change-point detection. Given distributions $P$ and $Q$, an algorithm solving offline change-point detection for $P$ and $Q$ takes a stream $x=(x_{1},x_{2},\dots,x_{n})\in\mathcal{X}^{n}$ with the guarantee that the there is an index $k^{*}$ such that first $k^{*}$ elements are sampled i.i.d. from $P$ and the latter elements are sampled i.i.d. from $Q$, and attempts to output $\hat{k}\approx k^{*}$. We can also consider an online variant where elements $x_{i}$ arrive one at a time.

Change-point detection has a long history in statistics and information theory (e.g. [She31, Pag54, Pag55, Shi63, Lor71, Pol85, Mou86, Pol87, Lai95, Kul01, Mei06, VB14]). Cummings et al. [CKM+18] recently gave the first private algorithms for change-point detection. Their algorithms are based on a private version of the log-likelihood ratio, and in cases where the log-likelihood ratio is not strictly bounded, they relax to a weaker distributional variant of differential privacy. Using Theorem 1.2, we can achieve the standard worst-case notion of differential privacy, and to achieve optimal error bounds for every $P,Q$.

For every pair of distributions $P$ and $Q$, and every ${\varepsilon}>0$, there is an ${\varepsilon}$-differentially private algorithm that solves offline change-point detection for $P$ and $Q$ such that, with probability at least $9/10$, $|\hat{k}-k^{*}|=O(\mathit{SC}^{P,Q}_{{\varepsilon}})$.

The expected error in this result is optimal up to constant factors for every pair $P,Q$, as one can easily show that the error must be at least $\Omega(\mathit{SC}^{P,Q}_{{\varepsilon}})$. Theorem 1.3 can be extended to give an arbitrarily small probability $\beta$ of failure, and can be extended to the online change-point detection problem, although with more complex accuracy guarantees. Our algorithm introduces a general reduction from private change-point detection for families of distributions ${\mathcal{H}}_{0}$ and ${\mathcal{H}}_{1}$ to private hypothesis testing for the same family, which we believe to be of independent interest.

3 Techniques

First Attempts. A folklore result based on the sample-and-aggregate paradigm [NRS07] shows that for every $P,Q$ and every ${\varepsilon}>0$, $\mathit{SC}^{P,Q}_{{\varepsilon}}=O(\frac{1}{{\varepsilon}}\mathit{SC}^{P,Q})$, meaning privacy comes at a cost of at most $O(\frac{1}{{\varepsilon}})$.See, e.g., [CDK17] for a proof. However, there are many examples where $\mathit{SC}^{P,Q}_{{\varepsilon}}=O(\mathit{SC}^{P,Q})$ even when ${\varepsilon}=o(1)$, and understanding this phenomenon is crucial.

The sample complexity of testing Bernoulli distributions (6) already demonstrates an important phenomenon in private hypothesis testing—for many distributions $P,Q$, there is a “phase transition” where the sample complexity takes one form when ${\varepsilon}$ is sufficiently large and another when ${\varepsilon}$ is sufficiently small, and often the sample complexity in the “large ${\varepsilon}$ regime” is equal to the non-private complexity up to lower order terms. A key challenge in obtaining Theorem 1.2 is to understand these transitions, and to understand the sample complexity in each regime.

Since each of the terms in (6) is a straightforward lower bound on the sample complexity of private testing, one might conjecture that (6) holds for every pair of distributions. However, our next illustrative example shows that this conjecture is false even for the domain $\mathcal{X}=\{0,1,2\}$. Consider the distributions given by the densities

For these distributions, (6) reduces to $\Theta(\frac{1}{\alpha^{3/2}}+\frac{1}{\alpha{\varepsilon}})$, so these distributions show that the optimal sample complexity can be much larger than (6). Moreover, these distributions exhibit that the optimal sample complexity can vary with ${\varepsilon}$ in complex ways, making several transitions and never matching the non-private complexity unless $\alpha$ or ${\varepsilon}$ is constant.

Key Ingredients. The second example above demonstrates that the optimal test itself can vary with ${\varepsilon}$ in an intricate fashion, which makes it difficult to construct a single test for which we can prove matching upper and lower bounds on the sample complexity. The use of the clamped log-likelihood test arose out of an attempt to find a single test that is optimal for the second pair of distributions $P$ and $Q$, and relies on a few crucial technical ingredients.

This observation is crucial for our work, because it implies that $\operatorname{sLLR}$ is ${\varepsilon}$-DP if $\sup_{x\in\mathcal{X}}\left|\log\frac{P(x)}{Q(x)}\right|\leq{\varepsilon}$. That is, in the case that $\sup_{x\in\mathcal{X}}\left|\log\frac{P(x)}{Q(x)}\right|\leq{\varepsilon}$, we get ${\varepsilon}$-DP for free (since Hellinger distance, and thus $\operatorname{sLLR}$, characterizes the optimal asymptotic sample complexity). Thus, we use the clamped log-likelihood ratio test, which forces the log-likelihood ratio to be bounded. Our lower bound in a sense shows that any loss of power in the test due to clamping is necessary for differentially private tests.

The proof of the upper bound also splits into two parts, roughly corresponding to the same aspects of the distributions $P$ and $Q$ as above. That is, we view our tester as either counting the number of high-ratio elements or computing the log-likelihood ratio on low-ratio elements. A useful observation is that this duality between the upper and lower bounds is inevitable. In Section 3, we characterize the advantage of the optimal tester in terms of Wasserstein distance between $P$ and $Q$ with metric $\min\{{\varepsilon}d_{H}(X,Y),1\}$. That is, the advantage of the optimal tester must be matched by some coupling of $P^{n}$ and $Q^{n}$.

4 Related Work

Early work on differentially private hypothesis testing began in the Statistics community with [VS09, USF13]. More recently, there has been a significant number of works on differentially private hypothesis testing. One line of work [WLK15, GLRV16, KR17, KSF17, CBRG18, SGHG+19, CKS+19] designs differentially private versions of popular test statistics for testing goodness-of-fit, closeness, and independence, as well as private ANOVA, focusing on the performance at small sample sizes. Work by Wang et al. [WKLK18] focuses on generating statistical approximating distributions for differentially private statistics, which they apply to hypothesis testing problems. A recent work by Awan and Slavkovic [AS18] gives a universally optimal test when the domain size is two, however Brenner and Nissim [BN14] shows that such universally optimal tests cannot exist when the domain has more than two elements. A complementary research direction, initiated by Cai et al. [CDK17], studies the minimax sample complexity of private hypothesis testing. [ASZ18] and [ADR18] have given worst-case nearly optimal algorithms for goodness-of-fit and closeness testing of arbitrary discrete distributions. That is, there exists some worst-case distribution $P$ such that their algorithm has optimal sample complexity for testing goodness-of-fit to $P$. Recently, [AKSZ18] designed nearly optimal algorithms for estimating properties like support size and entropy.

Another related area [GR18, She18, ACFT19] studies hypothesis testing in the local model of differential privacy. In particular, Duchi, Jordan, and Wainwright [DJW13] proved an analogue of our result for the restricted case of locally differentially private algorithms. Their characterization shows that, the optimal sample complexity for ${\varepsilon}$-DP local algorithms is $\Theta(1/({\varepsilon}^{2}\mathit{TV}(P,Q)^{2}))$. This characterization does not exhibit the same phenomena that we demonstrate in the central model—privacy never comes “for free” if ${\varepsilon}=o(1)$, and the sample complexity does not exhibit different regimes depending on ${\varepsilon}$. More generally, local-model tests are considerably simpler, and simpler to reason about, than central-model tests.

There are also several rich lines of work attempting to give tight instance-specific characterizations of the sample complexities of various differentially private computations, most notably linear query release [HT10, BDKT12, NTZ16, Nik15, KN16] and PAC and agnostic learning [KLN+08, BNS13, FX14]. The problems considered in these works are arguably more complex than the hypothesis testing problems we consider here, the characterizations are considerably looser, and are only optimal up to polynomial factors.

There has been a recent line of work [DFH+15b, DFH+15a, DFH+15c, RZ16, CLN+16, BNS+16, RRST16, FS17, XR17, FS18] on adaptive data analysis, in which the same dataset is used repeatedly across multiple statistics analyses, the choice of each analysis depends on the outcomes of previous analyses. The key theme in these works is to show that various strong notions of algorithmic stability, including differential privacy imply generalization bounds in the adaptive setting. Our characterization applies to all notions of stability considered in these works.

As an application of our private hypothesis testing results, we provide algorithms for private change-point detection. As discussed in Section 1.2.1, change-point detection has enjoyed a significant amount of study in information theory and statistics. Our results are in the private minimax setting, as recently introduced by Cummings et al. [CKM+18]. We improve on their results by improving the detection accuracy and providing strong privacy guarantees for all pairs of hypotheses.

Upper Bound on Sample Complexity of Private Testing

Due to the number of named tests in this paper, the reader may find it useful to refer to Appendix A, where we enumerate all the tests that we mention.

It has long been known that the Hellinger distance characterizes the asymptotic sample complexity of non-private testing (see, e.g., [Bor99]). In this section we show that the Hellinger distance exactly characterizes the advantage of the following randomized test given a single data point:

Now, $g(x)=\frac{\sqrt{\frac{P(x)}{Q(x)}}}{\sqrt{\frac{P(x)}{Q(x)}}+1}=\frac{1}{2}\left(\frac{\sqrt{\frac{P(x)}{Q(x)}}-1}{\sqrt{\frac{P(x)}{Q(x)}}+1}+1\right)$, and therefore

Thus, the advantage of $\operatorname{sLLR}$ is $H^{2}(P,Q)$, as claimed. ∎

This tells us the advantage of the test which takes only one sample. As a corollary, we can derive the sample complexity of distinguishing $P$ and $Q$ using $\operatorname{sLLR}$.

$SC^{P,Q}(\operatorname{sLLR})=O\left(\frac{1}{H^{2}(P,Q)}\right)$.

2 The Noisy Log-Likelihood Ratio Test

We now consider the noisy log-likelihood ratio test, which, similar to $\operatorname{scLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}$, is also ${\varepsilon}$-differentially private.

$SC^{P,Q}(\operatorname{ncLLR}_{-{\varepsilon}^{\prime},{\varepsilon}})=\Omega(SC^{P,Q}(\operatorname{scLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}))$.

Furthermore, if $-{\varepsilon}^{\prime}\leq\log\frac{P}{Q}\leq{\varepsilon}$ then $SC^{P,Q}(\operatorname{ncLLR}_{-{\varepsilon}^{\prime},{\varepsilon}})=\Theta(SC^{P,Q}(\operatorname{scLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}))$.

where $g_{{\varepsilon}}(X)=\frac{e^{\frac{1}{2}\operatorname{cLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}(X)}}{1+e^{\frac{1}{2}\operatorname{cLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}(X)}}$. If we let the threshold $\kappa=0$ then the test based on the test statistic $\operatorname{ncLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}$ is

Now, we will use the following two inequalities:

are the probabilities of success, we have

Therefore, if $\operatorname{ncLLR}$ has a probability of success of $5/6$ then $\operatorname{scLLR}$ has a probability of success of $2/3$. This implies that $SC^{P,Q}(\operatorname{ncLLR})\geq SC^{P,Q}(\operatorname{scLLR})$.

If $\log\frac{P}{Q}\in[-{\varepsilon}^{\prime},{\varepsilon}]$ then $\operatorname{cLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}(X)=\operatorname{LLR}(X)$ so we have $P^{n}(X)>Q^{n}(X)$ iff $\operatorname{LLR}(X)>0$ iff $g_{{\varepsilon}}(X)\leq h_{{\varepsilon}}(X)$ and therefore

If $\operatorname{ncLLR}$ has asymptotically optimal sample complexity then $\operatorname{scLLR}$ has asymptotically optimal sample complexity.

3 The Sample Complexity of ncLLRncLLR\operatorname{ncLLR}

The $\operatorname{ncLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}$ test is ${\varepsilon}$-DP and

Theorem 2.5 combined with a matching lower bound (given later in Theorem 3.5) imply that $\operatorname{ncLLR}_{-{\varepsilon}^{\prime}}^{{\varepsilon}}$ has asymptotically optimal sample complexity. Thus, by Corollary 2.4, $\operatorname{scLLR}_{-{\varepsilon}^{\prime}}^{{\varepsilon}}$ has asymptotically optimal sample complexity.

Before proving the bound, we pause to provide some intuition for its form. As discussed in the introduction, we can write $P$ and $Q$ as mixtures $P=(1-\tau)P^{\prime}+\tau P^{\prime\prime}$ and $Q=(1-\tau)Q^{\prime}+\tau Q^{\prime\prime}$ where $P^{\prime\prime},Q^{\prime\prime}$ have disjoint support. Now consider a thought experiment, in which the test that must distinguish $P$ from $Q$ using a sample of size $n$ is given, along with the sample $x$, a list of binary labels $b_{1},b_{2},...,b_{n}$ that indicate for each record whether it was sampled from the first component of the mixture (either $P^{\prime}$ or $Q^{\prime}$), or the second component (either $P^{\prime\prime}$ or $Q^{\prime\prime}$). Of course this can only be a though experiment—these labels are not available to a real test.

Because the mixture weights are the same for both $P$ and $Q$, the number of labels of each type would be distributed the same under $P$ and under $Q$, and so the tester would be faced with two independent testing problems: distinguishing $P^{\prime\prime}$ from $Q^{\prime\prime}$ using a sample of size about $\tau n$, and distinguishing $P^{\prime}$ from $Q^{\prime}$ using a sample of size about $(1-\tau)n$. It would suffice for the tester to solve either of these problems.

Theorem 2.5 shows that the real tests ($\operatorname{scLLR}$ and $\operatorname{ncLLR}$) do as well as the hypothetical tester that has access to the labels. The two arguments to the minimum in the theorem statement correspond directly to the ${\varepsilon}$-DP sample complexity of distinguishing $P^{\prime\prime}$ from $Q"$ (which requires $n\tau\geq 1/{\varepsilon}$) or distinguishing $P^{\prime}$ from $Q^{\prime}$ (which requires $n(1-\tau)\geq 1/H^{2}(P^{\prime},Q^{\prime})$). The proof proceeds by breaking the clamped log-likelihood ratio into two pieces, each corresponding to one of the two mixture components (again, this decomposition is not known to the algorithm). These two pieces correspond to the test statistics of the optimal testers for the two separate sub-problems in the thought experiment. We show that the test does well at distinguishing $P$ from $Q$ as long as either of these pieces is sufficiently informative.

On a more mechanical level, our proof of Theorem 2.5 bounds the expectation and standard deviation of the two pieces of the test statistic. We use the following simple lemma, which states that a test statistic $S$ performs well if the distribution of the test statistic on $P$ and $Q$, $S(P)$ and $S(Q)$, must not overlap too much. The proof is a simple application of Chebyshev’s inequality.

then $S$ can be used to distinguish between $P$ and $Q$ with probability of success 2/3 and sample complexity at most $n^{\prime}=12c^{2}n$.

This result follows by Chebyshev’s inequality. For completeness, it is proved in Appendix D.

and set $\mathcal{A}=\mathcal{X}\setminus(\mathcal{S}\cup\mathcal{T})$.

where the last equality follows by the definition of $\tau$. Moreover,

where the last inequality follows since $H^{2}(P,Q)\leq\operatorname{KL}(P\;\|\;Q)$ for any distributions $P$ and $Q$.

Recall that $P^{\prime\prime}$ is a distribution such that $P=\tau P^{\prime\prime}+(1-\tau)P^{\prime}$ and the support of $P^{\prime\prime}$ is contained in $\mathcal{S}$. Thus,

Since $\log\frac{P^{\prime}(x)}{Q^{\prime}(x)}\leq{\varepsilon}\leq 1$, $\lvert\log\frac{P^{\prime}(x)}{Q^{\prime}(x)}\rvert\leq 3\cdot\lvert 1-\sqrt{\frac{Q^{\prime}(x)}{P^{\prime}(x)}}\rvert$. Therefore,

Also, $P^{\prime\prime}(\mathcal{S})=1$ and thus,

Lower Bound on the Sample Complexity of Private Testing

We now prove the lower bound in Theorem 1.2. We do so by constructing an appropriate coupling between the distributions $P^{n}$ and $Q^{n}$, which implies lower bounds for privately distinguishing $P^{n}$ from $Q^{n}$. This style of analysis was introduced in [ASZ18], though we require a strengthening of their statement. Specifically, the lower bound of Acharya et al. involves $d^{\prime}_{\varepsilon}(X,Y)={\varepsilon}d_{H}(X,Y)$, whereas we have $d_{\varepsilon}(X,Y)=\min({\varepsilon}d_{H}(X,Y),1)$.

where the $\inf$ is over all couplings $\rho$ of $P^{n}$ and $Q^{n}$. Let $d_{{\varepsilon}}(X,Y)=\min\{{\varepsilon}d_{H}(X,Y),1\}$.

For every ${\varepsilon}$-DP algorithm $M\colon\mathcal{X}^{n}\to\{0,1\}$, if $X$ and $Y$ are neighboring datasets then

where the expectations are over the randomness of the algorithm $M$.

For every ${\varepsilon}$-DP algorithm $M\colon\mathcal{X}^{n}\to\{P,Q\}$ the advantage satisfies

The upper bound in Lemma 3.2 is in fact tight. We state the converse below for completeness, although we will not use it in this work. The proof of Lemma 3.3 is contained in Appendix F.

There is a ${\varepsilon}$-DP algorithm $M\colon\mathcal{X}^{n}\to\{P,Q\}$ such that

We will also rely on the following standard fact characterizing total variation distance in terms of couplings:

We can now prove the lower bound component of Theorem 1.2. Recall that $P^{\prime}$ and $Q^{\prime}$ were defined in Equation (5).

Given $P$ and $Q$, every ${\varepsilon}$-DP test $K$ that distinguishes $P$ and $Q$ has the property that

Recalling now that the distribution of $(X,Y)$ is that of the TV-coupling of $(P^{\prime})^{n^{\prime}}$ and $(Q^{\prime})^{n^{\prime}}$, and that $\lvert\bar{\Lambda}\rvert=n-n^{\prime}$, we get

Therefore, by Lemma 3.2, we have that for every ${\varepsilon}$-DP test $M$,

Thus, in order for the probability of success to be $\Omega(1)$, we need either ${\varepsilon}\tau n$ or $\sqrt{(1-\tau)n}H(P^{\prime},Q^{\prime})$ to be $\Omega(1)$. That is, $n\geq\Omega\left(\min\left\{\frac{1}{{\varepsilon}\tau},\frac{1}{(1-\tau)H^{2}(P^{\prime},Q^{\prime})}\right\}\right)$. ∎

Application: Differentially Private Change-Point Detection

In this section, we give an application of our method to differentially private change-point detection. In the change-point detection problem, we are given a time-series of data. Initially, it comes from a known distribution $P$, and at some unknown time step, it begins to come from another known distribution $Q$. The goal is to approximate when this change occurs. More formally, we have the following definition.

In the offline change-point detection problem, we are given distributions $P,Q$ and a data set $X=\{x_{1},\dots,x_{n}\}$. We are guaranteed that there exists $k^{\ast}\in[n]$ such that $x_{1},\dots,x_{k^{\ast}-1}\sim P$ and $x_{k^{\ast}},\dots,x_{n}\sim Q$. The goal is to output $\hat{k}$ such that $|\hat{k}-k^{\ast}|$ is small.

In the online change-point detection problem, we are given distributions $P,Q$, a stream of data points $X=\{x_{1},\dots\}$. We are guaranteed that there exists $k^{\ast}$ such that $x_{1},\dots,x_{k^{\ast}-1}\sim P$ and $x_{k^{\ast}},\dots\sim Q$. The goal is to output $\hat{k}$ such that $|\hat{k}-k^{\ast}|$ is small.

We study the parameterization of the private change-point detection problem recently introduced by Cummings et al. [CKM+18].

An algorithm for a (online) change-point detection problem is $(\alpha,\beta)$-accurate if for any input dataset (data stream), with probability at least $1-\beta$ outputs a $\hat{k}$ such that $|\hat{k}-k^{\ast}|\leq\alpha$, where the probability is with respect to the randomness in the sampling of the data set and the random choices made by the algorithm.

There exists an efficient $\varepsilon$-differentially private and $(\alpha,\beta)$-accurate algorithm for offline change-point detection from distribution $P$ to $Q$ with

Furthermore, there exists an efficient $\varepsilon$-differentially private and $(\alpha,\beta)$-accurate algorithm for online change-point detection from distribution $P$ to $Q$ with the same value of $\alpha$. This latter algorithm also requires as input a value $n$ such that $n=\Omega\left(\mathit{SC}^{P,Q}_{{\varepsilon}}\cdot\log\left(\frac{k^{\ast}}{n\beta}\right)\right)$. If the algorithm is accurate, it will observe at most $k^{\ast}+2n$ data points, and with high probability observe $k^{\ast}+O(n\log n)$ data points.

As one might guess, this problem is intimately related to the hypothesis testing question studied in the rest of this paper. Indeed, our change-point detection algorithm will use the hypothesis testing algorithm of Theorem 1.2 as a black box, in order to reduce to a simpler Bernoulli change-point detection problem (see Lemma 4.4 in Section 4.1). We then give an algorithm to solve this simpler problem (Lemma 4.5 in Section 4.2), completing the proof of Theorem 4.3. In Section 4.3, we show that our reduction is applicable more generally, as we describe an algorithm change-point detection in a goodness-of-fit setting.

In this section, we provide a reduction from private change-point detection with arbitrary distributions to non-private change-point detection with Bernoulli distributions.

Then there exists an $\varepsilon$-differentially private and $((\alpha+1)\cdot\mathit{SC}^{P,Q}_{{\varepsilon}},\beta)$-accurate algorithm which solves the change-point detection problem, where $\mathit{SC}^{P,Q}_{{\varepsilon}}$ is as defined in Theorem 1.2.

We describe the reduction for the offline version of the problem, the reduction in the online setting is identical. The reduction is easy to describe. We partition the sample indices into intervals of length $\mathit{SC}^{P,Q}_{\varepsilon}$. More precisely, let $Y_{j}=\{x_{(i-1)\mathit{SC}^{P,Q}_{\varepsilon}+1},\dots,x_{i\mathit{SC}^{P,Q}_{\varepsilon}}\}$, for $j=1$ to $\lfloor n/\mathit{SC}^{P,Q}_{\varepsilon}\rfloor$, and disregard the remaining “tail” of $x_{i}$’s. We run the algorithm of Theorem 1.2 on each $Y_{j}$, and produce a bit $z_{j}=1$ if the algorithm outputs that the distribution is $P$, and a $z_{j}=-1$ otherwise.

Finally, we show that the existence of an $(\alpha,\beta)$-accurate algorithm that solves this problem also solves the original problem. Suppose that the output of the algorithm on the restricted change-point detection problem is $j$. To map this to an answer to the original problem, we let $\hat{k}=(j-1)\mathit{SC}^{P,Q}_{\varepsilon}$.

First, note that $\hat{k}$ will be $\varepsilon$-differentially private. We claim that the sequence of $z_{j}$’s is $\varepsilon$-differentially private. This is because the algorithm of Theorem 1.2 is $\varepsilon$-differentially private, we apply the algorithm independently to each component of the partition, and each data point can only affect one component (since they are disjoint). Privacy of $\hat{k}$ follows since privacy is closed under post-processing.

2 Solving Bernoulli Change-Point Detection

In this section, we show that there is a $(\Theta(\log(1/\beta))+1,\beta)$-accurate algorithm for the restricted change-point detection problem. Combined with Lemma 4.4, this implies Theorem 4.3.

There exists an efficient $(O(\log(1/\beta),\beta)$-accurate algorithm for the offline restricted change-point detection problem (as defined in Lemma 4.4).

Similarly, there exists an efficient $(O(\log(1/\beta),\beta)$-accurate algorithm for the online restricted change-point detection problem. This algorithm requires as input a value $n$ such that $n=\Omega\left(\log\left(\frac{k^{\ast}}{n\beta}\right)\right)$. If the algorithm is accurate, it will observe at most $k^{\ast}+2n$ data points, and with high probability observe $k^{\ast}+O(n\log n)$ data points.

We start by describing the algorithm for the offline version of the problem. We then discuss how to reduce from the online problem to the offline problem.

Let $c>0$ be some absolute constant. With probability at least $1-\beta$, for all $i\geq c\log(1/\beta)$ simultaneously,

This implies that, with probability at least $1-\beta$, we have that for all $i\geq c\log(1/\beta)$

Note that the right-hand side is non-increasing in $i$, so it is maximized at $i=c\log(1/\beta)$, and thus

where the last inequality follows for a sufficiently large choice of $c$.

The algorithm will be as follows. Partition the stream into consecutive intervals of length $n$, which we will draw in batches. If an interval has more $-1$’s than $+1$’s, then call the offline change-point detection algorithm on the final $2n$ data points with failure probability parameter set to $\beta/4$, and output whatever it says.

Let $k^{\ast}$ be the true change-point index. First, we show that with probability $\geq 1-\beta/4$, the algorithm will not see more $-1$’s than $+1$’s in any interval before the one containing $k^{\ast}$. The number of $+1$’s in this interval will be distributed as $\operatorname{Binomial}(n,\tau_{0})$ for $\tau_{0}>2/3$. By a Chernoff bound, the probability that we have $>n/2$ $-1$’s is at most $\exp(-\Theta(n))$. Taking a union bound over all $O\left(\frac{k^{\ast}}{n}\right)$ intervals before the change point gives a failure probability of $\frac{k^{\ast}}{n}\exp(-\Theta(n))\leq\beta/4$, where the last inequality follows by our condition on $n$.

Next, note that the interval following the one containing $k^{\ast}$ will have a number of $+1$’s which is distributed as $\operatorname{Binomial}(n,\tau_{1})$ for $\tau_{1}<1/3$. By a similar Chernoff bound as before, the probability that we have $>n/2$ $+1$’s is at most $\exp(-\Theta(n))\ll\beta/4$. Therefore, with probability $1-\beta/2$, the algorithm will call the offline change-point detection algorithm on an interval containing the true change point $k^{\ast}$.

We conclude by the correctness guarantees of the offline change-point detection algorithm. Note that we chose the failure probablity parameter to be $\beta/4$, as the offline algorithm may either be called at the interval containing $k^{\ast}$, or the following one, and we take a union bound over both of them. ∎

3 Private Goodness-of-Fit Change-Point Detection

Our reduction as given above is rather general: and it can apply to more general change-point detection settings than those described above. For instance, the above discussion assumes we know both the initial and final distributions $P$ and $Q$. Instead, one could imagine a setting where one knows the initial distribution $P$ but not the final distribution $Q$, which we term goodness-of-fit change-point detection.

We note that analogous definitions and results hold for the online version of this problem, as in the previous sections.

We omit the full details of the proof, but it proceeds by a very similar argument to that in Sections 4.1 and 4.2. In particular, it is possible to prove an analogue of Lemma 4.4, at which point we can apply Lemma 4.5. The only difference is that we need an algorithm for private goodness-of-fit testing, rather than Theorem 1.2 for hypothesis testing. We use the following result from [ASZ18].

With this in hand, we have the following result for goodness-of-fit changepoint detection.

There exists an efficient $\varepsilon$-differentially private and $(\alpha,\beta)$-accurate algorithm for offline $\gamma$-goodness-of-fit change-point detection with

Acknowledgments

We are grateful to Salil Vadhan for valuable discussions in the early stages of this work.

References

Appendix A Glossary of Tests

In this section, we list all the tests mentioned in this paper. As some mnemonics, the prefix “s” indicates that a test is “soft,” meaning that the test’s output is distributed as Bernoulli random variable with parameter proportional to some test statistic. The prefix “n” means that a statistic is “noisy,” which we enforce by adding Laplace noise. The prefix “c” means that a statistic is “clamped”: to limit the sensitivity of the statistic, we clamp the value of each summand to a fixed range, so that terms can not be unboundedly large.

The $\operatorname{LLR}$ is the log-likelihood ratio statistic:

The $\operatorname{sLLR}$ is the soft log-likelihood ratio test:

The $\operatorname{cLLR}$ is the clamped log-likelihood ratio statistic:

The $\operatorname{scLLR}$ is the soft clamped log-likelihood ratio test:

The $\operatorname{ncLLR}$ is the noisy log-likelihood ratio test, which is also ${\varepsilon}$-differentially private:

Let $P$ and $Q$ be two arbitrary distributions and let $\tau$ be as defined in (4). Assume without loss of generality that $\tau=\intop\nolimits_{\mathcal{X}}\max\{P(x)-e^{{\varepsilon}}Q(x),0\}\,dx$. Then there exists ${\varepsilon}^{\prime}\in[0,{\varepsilon}]$ such that $\tau=\intop\nolimits_{\mathcal{X}}\max\{Q(x)-e^{{\varepsilon}^{\prime}}P(x),0\}\,dx$.

Appendix C Proof of Theorem 1.2 when P𝑃P and Q𝑄Q have disjoint support.

If $P$ and $Q$ have disjoint support then $\operatorname{scLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}$ and $\operatorname{ncLLR}_{-{\varepsilon}^{\prime},{\varepsilon}}$ are asymptotically optimal among all ${\varepsilon}$-DP tests and have sample complexity $SC^{P,Q}(\operatorname{scLLR}_{-{\varepsilon}^{\prime},{\varepsilon}})=SC^{P,Q}(\operatorname{ncLLR}_{-{\varepsilon}^{\prime},{\varepsilon}})=\Theta\left(\frac{1}{{\varepsilon}}\right)$.

For the lower bound, consider the coupling of $P^{n}$ and $Q^{n}$ that takes a sample $X\sim P^{n}$ and simply resamples it from $Q^{n}$. Since $P^{n}$ and $Q^{n}$ have disjoint support, $d_{{\varepsilon}}(X,Y)=\min\{{\varepsilon}n,1\}$. Thus, by Lemma 3.2, we have that $n\geq\Omega(1/{\varepsilon})$ is a necessary condition. ∎

Appendix D Proof of Lemma 2.6

Appendix E The Advantage of scLLRscLLR\operatorname{scLLR}

In this section, we show that the Soft Clamped Log-Likelihood Ratio test ($\operatorname{scLLR}$) achieves advantage related to the quantities $\tau$ and transformed distributions $P^{\prime},Q^{\prime}$ introduced earlier. Recall the definition

so the term 1 is only non-zero if $x\in\mathcal{S}$, where it takes the value

so term 2 is only non-zero if $x\in\mathcal{T}$, where it takes the value

We can therefore simplify the expression in (8) to obtain:

Appendix F Proof of Lemma 3.3

The proof of Lemma 3.3 relies on the following dual formulation of Wasserstein distance:

$f$ is $1$-Lipschitz with respect to $d$, and

$\max_{X\in\mathcal{X}}f(X)\leq 2\cdot\max_{X,Y\in\mathcal{X}}d(X,Y)$.

The second claim is immediate from the definition of $M$. To see that $M$ is ${\varepsilon}$-DP, note that any function that is $1$-Lipschitz with respect to $d_{\varepsilon}$ is ${\varepsilon}$-Lipschitz with respect to $d_{H}$. For any pair of neighbours $X$ and $Y$, we have