Private Selection from Private Candidates

Introduction

Differential Privacy is the standard notion of privacy for statistical databases. It imposes a probabilistic constraint on the behavior of the algorithm on datasets that differ in one person’s input. Formally,

Let $\mathcal{M}:\mathcal{D}^{n}\rightarrow\mathcal{R}$ be a randomized algorithm mapping datasets to some range $\mathcal{R}$. We say that $\mathcal{M}$ is $(\varepsilon,\delta)$-differentially private if for all pairs of adjacent datasets $D,D^{\prime}\in\mathcal{D}^{n}$, and for all measurable subsets $S\subseteq\mathcal{R}$,

Here, two datasets are adjacent if they differ in one person’s input. When $\delta=0$, we will sometimes say that $\mathcal{M}$ is $\varepsilon$-differentially private.

Differential privacy (DP) satisfies nice post-processing and composition properties, allowing for complex differentially private algorithms to be built out of simpler building blocks. In the last decade or so, differentially private algorithms have been designed and analyzed for numerous statistical and machine learning tasks, in most cases by carefully putting together these building blocks. This approach to the design and analysis of differentially private algorithms has proven surprisingly robust and useful.

One can only hope to approximately maximize $q$ when single individuals in the dataset cannot change any of the score functions $q(i,\cdot)$ too much. This stability of $q$ under small changes in $D$ is usually codified in an assumption that each score function $q(i,D)$ is Lipschitz with respect to Hamming distance $1$ changes to $D$. The Exponential mechanism is an algorithm for DP selection under this assumption and has found numerous applications to the design of DP mechanisms. Several other mechanisms for the private selection problem have been proposed, that improve the utility guarantee under stronger assumptions .

In many settings however, the Lipschitzness assumption is much too strong. In this work, we ask: Are there weaker versions of the stability assumption that allow for private selection? We show that one can codify the stability simply as differential privacy: the function $q$, viewed as a randomized algorithm, satisfies differential privacy. Indeed, one can convert a Lipschitz function $q^{\prime}$ into an $\varepsilon$-DP random function $q$ by simply adding, say, a noise drawn from the Laplace distribution to $q^{\prime}$. We assume oracle access to a randomized function that on input $(i,D)$ computes a sample $(\widetilde{x},\widetilde{q})$ from the $i$-th candidate $\mathcal{M}_{i}(D)$, where $\widetilde{q}$ is the score and $\widetilde{x}$ can be any additional output. Moreover, the output distributions of $\mathcal{M}_{i}(D)$ and $\mathcal{M}_{i}(D^{\prime})$ are promised to be close whenever $D$ and $D^{\prime}$ are neighbors. Here closeness in distributions is taken to mean $\varepsilon$-DP or $(\varepsilon,\delta)$-DP. Motivated by applications, we assume that the scores are bounded, say $\widetilde{q}\in$.

Our first result is a simple algorithm that given as input a threshold $\tau$, outputs a sample $(\widetilde{x},\widetilde{q})$ with score $\widetilde{q}\geq\tau$, under the assumption that at least one candidate has a median score of at least $\tau$. This algorithm makes a near linear number of oracle calls, and improves on the quadratic bound that follows from a reinterpretation of a result in . We show that the loss in privacy, utility and efficiency for this algorithm are all close to optimal. Interestingly, this algorithm can be seen as, starting from a naive differentially private algorithm with a poor utility guarantee (e.g., pick a candidate uniformly at random), and then by repeating it in a private way to boost its utility guarantee. In doing so, we get simple algorithms that are both private and have good utility guarantees.

Fix any $\varepsilon_{1}>0,\tau\in$. Then given $\varepsilon_{1}$-DP algorithms $\mathcal{M}_{1},\ldots,\mathcal{M}_{K}$, there is an algorithm $\mathcal{M}$ that on any dataset $D$, outputs a sample $(\widetilde{x},\widetilde{q})$ such that

$\mathcal{M}$ is $(2\varepsilon_{1})$-DP.

Can we do this without knowing this target value $\tau$? We give two algorithms that compete with the best $i$ without knowing the target $\tau$. The first can be seen as modifying the naive non-private algorithm by employing a random stopping strategy. In doing so, it guarantees that “outputting the highest scored sample seen so far” is already private. However it pays a small additional privacy penalty: the final privacy cost is $3\varepsilon_{1}$ instead of $2\varepsilon_{1}$.

Fix any $\varepsilon_{1}>0,\gamma\in$. Then given $\varepsilon_{1}$-DP algorithms $\mathcal{M}_{1},\ldots,\mathcal{M}_{K}$, there is an algorithm $\mathcal{M}$ that on any dataset $D$, outputs a sample $(\widetilde{x},\widetilde{q})$ such that

$\mathcal{M}$ is $(3\varepsilon_{1})$-DP.

$\widetilde{q}$ is the highest scored sample among the $\widetilde{T}$ samples seen so far.

Our second algorithm keeps the privacy cost to essentially $2\varepsilon_{1}$, at the cost of a slightly higher runtime and a more complicated algorithm and analysis. This is valuable since in some settings, the utility of the base algorithm is quite sensitive with respect to the privacy parameter $\varepsilon_{1}$. In such settings, with a final target privacy parameter of $\varepsilon_{fin}$, the second algorithm can allow us to give each $\mathcal{M}_{i}$ a privacy budget of $\approx\varepsilon_{fin}/2$, which can lead to a better utility than the $\approx(\varepsilon_{fin}/3)$-DP $\mathcal{M}_{i}$’s needed for the first simpler algorithm.

$\mathcal{M}$ is $(2\varepsilon_{1}+\varepsilon_{0},\delta)$-DP.

Except with probability $\beta+\delta/R$, $\widetilde{x}$ has quality at least $\tau^{*}-\frac{1}{R}$.

The number of calls $\widetilde{T}$ that the algorithm makes to any $\mathcal{M}_{i}(D)$ satisfies (deterministically)

Furthermore, \Pr\inb{\mathcal{M}\hbox{ outputs\bot}}\leq\beta+\delta.

In the process, we develop an online version of our algorithm, which can be seen as a generalization of the sparse vector technique to this privacy-instead-of-Lipschitzness setting. This algorithm takes as input a sequence of mechanisms $\mathcal{M}_{i}(\cdot)$ and $\tau_{i}$, and stops at the first $i$ such that $\mathcal{M}_{i}(\cdot)$ has median score larger than $\tau_{i}$.

There is an $(\varepsilon_{3},\delta)$-DP mechanism $\mathcal{M}_{sv}$ such that, for any $p^{*}\in(0,1),\beta\in(0,1)$, and for any sequence of $\varepsilon_{1}$-DP mechanisms $\mathcal{M}_{1},\cdots,\mathcal{M}_{K}$ and any sequence of thresholds $\tau_{1},\cdots,\tau_{k}$:

If there is an $i$ such that $\Pr[\mathcal{M}_{i}(D)\geq\tau_{i}]\geq p^{*}$, then $\mathcal{M}$ outputs $i$ with probability $(1-\beta)$.

If $\mathcal{M}$ outputs $i$, then except with probability $\beta$, $\Pr[\mathcal{M}_{i}(D)\geq\tau_{i}]\geq(\frac{\beta}{K})^{O(\varepsilon_{1}/\varepsilon_{3})}\cdot p^{*}$.

We next outline some motivating applications of our work.

Hyperparameter/algorithm Selection: When designing practical machine learning algorithms, one often ends up choosing amongst different algorithms/models, or setting values for common hyperparameters such as the learning rate in an algorithm. This hyperparameter selection problem has attracted a lot of interest in recent years . Differentially private ML algorithms such as have many of these hyperparameters, and often add on a few hyperparameters of their own. A common approach in the non-private setting is to try out several (or all) values of the hyperparameters and select the best one based on the performance on a validation set. Doing this with privacy requires more care. Chaudhuri and Vinterbo studied this problem formally under strong assumptions on the algorithm. These assumptions, however, can be hard to enforce and one would like to design an algorithm that works without any additional assumptions. Note that given $K$ choices for the hyperparameters, and an $\varepsilon$-DP learner, one can publish $K$ models and select the best, say using the exponential mechanism. This approach only gives $\varepsilon K$-DP, which allows for privacy budget of only $\varepsilon/K$ (or $\varepsilon\sqrt{\log\frac{1}{\delta}}/\sqrt{K}$ if using advanced composition) for the learner, which often translates to significantly poorer utility guarantee. In this setting, note also that each oracle call is a run of the DP learner for some hyperparameter setting, that can involve a large computational cost.

Our work shows how to compete with the best choices of hyperparameters in the non-private setting while satisfying $O(\varepsilon)$-DP, at a small computational overhead.

Generalizing the Exponential Mechanism: Beyond these applications, our result can be viewed as a generalization of the expoenential mechanism. Given a score fuction $q$ that has sensitivity $S$, observe that adding Laplace noise of scale $S/\varepsilon$ to the score gives us an $\varepsilon$-DP mechanism. Our algorithm can be then used to select amongst these. We can however relax the assumptions. If we allow the score functions to have different sensitivities, we can still use our framework and recover the generalized exponential mechanism of Raskhodnikova and Smith . If the score functions have small smoothed sensitivity , we get a smooth sensitivity version of the exponential mechanism. This last result does not seem to follow from known techniques.

Private amplification for private algorithms: Beyond these applications, our result can be viewed as an extension of the private amplification scheme introduced in . Given a private algorithm, which is usually a randomized algorithm, ideally one would like to run it multiple times, and then choose the best run so as to obtain an output with a higher quality. Here the quality measure can either be the success probability, or any other utility measure of the output. This is trivial in the non-private setting. Is it possible to compete with such a naive repetition strategy in a differentially private way? In this work, we present an algorithm that can be seen as modifying the naive repetition strategy with a random stopping time, which is arguably almost as competitive as the non-private naive repetition.

The Differentially Private Selection problem, often known as differentially private maximization, is a very general algorithmic problem that arises in many applications. Some examples include private PAC learning , private frequent itemset mining , private PCA and private multiple hypothesis testing . The Sparse Vector Technique can be viewed in hindsight as a novel solution to the online version of the selection problem, under the assumption that the target value $\tau$ is known in advance. This technique was introduced by Dwork et al. . We refer the reader to the book by Dwork and Roth for further applications of these techniques.

Several generalization of the exponential mechanims have been proposed. Smith and Thakurta and Beimel et al. showed that the utility guarantee can be improved using the propose-test-release framework of Dwork and Lei when there is a large margin between the maximum and the rest. Chaudhuri et al. gave an elegant algorithm that can exploit a large margin between the maximum and the $k$th maximum for any $k$. Raskhodnikova and Smith proposed the generalized exponential mechanism whose utility depends on the sensitivity of the maximizer, rather than the worst-case sensitivity. Minami et al. show that under certain assumptions on the base distribution, the sensitivity assumptions on the loss function can be significantly relaxed. Our algorithms can also be seen as a natural generalization of the Laplace mechanism. Given a Lipschitz score function $q^{\prime}$, one can convert it into an $\varepsilon$-DP score function $q$ by adding a Laplace noise. Then the Laplace mechanism says that one can just output the max of the noise-added scores. However, the Laplace relies crucially on the fact that the noise is a Laplace noise. As we will discuss in Section B.1, under the mere assumption that the score function is $\varepsilon$-DP, outputting the max will inevitably incur a factor of $K$ loss in privacy.

The problem of algorithm selection has also been studied in where the best parameters are learnt from features of the problem. Ligett et al. study the problem of picking from a sequence of algorithms with increasing privacy costs, until one with good utility is found, for a special class of mechanisms.

The problem of private median finding, and more generally private percentile estimation has been studied in several works . While syntactically similar to the threshold estimation problem studied in Section 4, the assumptions on the data in those works are very different from ours and we do not believe that the techniques in those works apply to the setting of interest in this work.

2. Organization

The rest of the paper is organized as follows. In Section 3 we present our algorithm for the known threshold case. Section 4 describes our sparse vector and general selection algorithms. We sketch applications of our results in Section 5. The appendices contain some deferred proofs, show why simpler natural approaches do not work for our problem, and show a lower bound on the privacy overhead.

Preliminary and Notations

For a random variable $X$ and distribution $Q$, we write $X\sim Q$ if $X$ is distributed according to the law of $Q$.

Given a function $f$ on dataset $D$, we say that $f$ is $t$-Lipschitz if for any two neighboring dataset $D,D^{\prime}$, $\left|f(D)-f(D^{\prime})\right|\leq t$.

Private selection

Let $\left\{M_{i}(D)\right\}_{i=1}^{K}$ be a set of differentially private mechanisms, that is, for every $i$, $M_{i}$ is a differentially private mechanism with respect to the dataset $D$. We will also refer to the set of $M_{i}$ as private candidates. For convenience, we will also treat a randomized mechanism $M_{i}(D)$ as a distribution, and write $m\sim M_{i}(D)$ if $m$ follows the output distribution of $M_{i}(D)$. Let $\left\{q_{i}\right\}$ be scoring functions over the output of these mechanisms, that is, for $m\sim M_{i}(D)$, $q_{i}(m)$ is the score for $m$. We assume that there is a total ordering of the candidates: when two candidates have the same score, we assume that there is an arbitrary tie-breaking rule (e.g., by alphabetical ordering). Given a total ordering of the candidates, without loss of generality we will further assume that each option has a different score.

The goal of private selection is to select $(m,i)$ that (approximately) maximizes the score of $q_{i}(m)$. Naively, a natural algorithm is to draw samples $m_{i}\sim M_{i}$ for every $i$, and then output the pair $(m_{i},i)$ with the highest score $q_{i}(m_{i})$. Unfortunately this naive algorithm is not private. The detailed discussion and analysis is deferred to Section B.1. The next natural algorithm would be to output the $p$-th percentile best, which unfortunately is also not private. Again we defer the analysis to Section B.3.

In this section, we will start with the following naive algorithm that is guaranteed to be private but not very useful (has poor utility guarantee): we choose a candidate $i$ uniformly at random and output $M_{i}(D)$. It is not hard to see that such a choice of candidate is at least as private as the individual candidates. However, the probability of getting a reasonably “good” candidate can be of the order $O(1/K)$. Nevertheless, we will show how to boost its usefulness (utility guarantee) by thresholding or random stopping. As a result, this leads to simple and practical algorithms that are also able to compete with the best candidates in a differentially private way.

We consider a thresholding algorithm, which for a given threshold, repeatedly samples from the candidates until we get one that is above the threshold. In addition, we have a small probability $\gamma$ of stopping at each step. See LABEL:alg:thresholding for a more formal description.

We assume that the adversary can only observe the final output of the algorithm. We show that for any choice of parameters, the algorithm is private; and if the given threshold $\tau$ is a “good” threshold, the algorithm is unlikely to output $\bot$.

Fix any $\varepsilon_{1},\delta_{1}>0,\varepsilon_{0}\in,\gamma\in$. Let $T$ be any integer such that $T\geq\max\left\{\frac{1}{\gamma}\ln\frac{2}{\varepsilon_{0}},1+\frac{1}{e\gamma}\right\}$, Then LABEL:alg:thresholding with these parameters satisfies the following:

If $Q$ is $\varepsilon_{1}$-DP, then the output is $(2\varepsilon_{1}+\varepsilon_{0})$-DP.

If $Q$ is $(\varepsilon_{1},\delta_{1})$-DP, then the output is $\inp{2\varepsilon_{1}+\varepsilon_{0},\;3e^{2\varepsilon_{1}+\varepsilon_{0}}\cdot\frac{\delta_{1}}{\gamma}}$-DP.

Let $\widetilde{T}$ be the number of iterations of the algorithm, and let $p_{1}=\Pr_{q\sim Q(D)}\inb{q\geq\tau}$, then

Furthermore, \Pr\inb{\hbox{output\bot}}\leq\frac{(1-p_{1})(1+\varepsilon_{0}/2)}{p_{1}}\gamma.

Due to space considerations, we defer this proof to Section A.1. As a remark, it is clear that in the worst case, the number of iterations of LABEL:alg:thresholding is no more than $T$; this theorem provides a more average-case guarantee: the larger $p_{1}$ (or $\gamma$) is, the more likely that the algorithm will terminate (much) sooner than $T$. Moreover, it is worth noting that the larger the setting of $T$ is, the smaller we can set $\varepsilon_{0},\gamma$, providing more privacy and utility. In particular, the above theorem holds even if we set $\gamma=0,\varepsilon_{0}=0$ but $T=\infty$, in other words, we run the algorithm till it stops by itself. However this would not be a very practical setting: if one started with a “bad” threshold, the algorithm may never stop. In that case, one may want to stop the algorithm and try a different threshold. Therefore, for practical purposes one may want to set $\gamma>0$ and $\varepsilon_{0}>0$.

2. Random stopping without thresholding

In this subsection, we show that the idea of random stopping leads to a simple private algorithm, even without knowing the threshold. It is similar to LABEL:alg:thresholding but without the thresholding part: draw a random number of samples, and then output the best option.

Fix any $\varepsilon_{1}>0,\gamma\in$. If $Q$ is $\varepsilon_{1}$-DP, then the output of LABEL:alg:maxRand is $(3\varepsilon_{1})$-DP.

We first consider the event of getting the output $(x,q)$ from LABEL:alg:maxRand on neighboring datasets $D$ and $D^{\prime}$. Without loss of generality, we assume that each option has a different score.Otherwise, whenever we write $q_{1}>q$, we break ties using the same total ordering of the candidates. Then we denote

Notice that $p=\Pr_{(\widetilde{x},\widetilde{q})\sim Q(D)}\inb{(\widetilde{x},\widetilde{q})=(x,q)}$, $p_{1}=p_{0}+p$, and $p_{1}^{\prime}=p_{0}^{\prime}+p^{\prime}$.

We define the highest score for a set (or a multiset) $S$ of tuples $(x,q)$ as

Since $Q$ is $\varepsilon_{1}$-DP, we have that $p,p_{0},p_{1}$ are $\varepsilon_{1}$-close (in a DP sense) to $p^{\prime},p_{0}^{\prime},p_{1}^{\prime}$, respectively. Then,

The following utility bound holds for this algorithm.

For $p>0$, let $Q^{(p)}(D)=\sup\{z:\Pr[Q(D)\geq z]>p\}$. Then the output of LABEL:alg:maxRand has score at least $Q^{(p)}(D)$ except with probability $\gamma/p$.

Instead of random stopping, one can also design a hard stopping variant of this algorithm similar to that of LABEL:alg:thresholding, and allow for $(\varepsilon,\delta)$-DP input algorithms.

Fix any $\gamma\in,\delta_{2}>0$ and let $T=\frac{1}{\gamma}\log\frac{1}{\delta_{2}}$. Consider a variant of LABEL:alg:maxRand that outputs the highest scored candidate from $S$ if $j$ reaches $T$. If $Q$ is $(\varepsilon_{1},\delta_{1})$-DP, then the output of this algorithm is $(3\varepsilon_{1}+3\sqrt{2\delta_{1}},\delta)$-DP for $\delta=\sqrt{2\delta_{1}}T+\delta_{2}$.

We simply reduce to Theorem 3.2 using simple properties of $(\varepsilon,\delta)$-DP. We give details next, using folklore results proven in Appendix E. Fix a pair of neighboring datasets $D$ and $D^{\prime}$. Then we can define an event $B$ such that $\Pr[B]\leq\sqrt{\delta_{1}}$ and that $Q(D)\mid B^{c}$ and $Q(D^{\prime})\mid B^{c}$ are multiplicatively $\varepsilon_{1}+\sqrt{2\delta_{1}}$ close. Let $B_{j}$ be the event $B$ in the $j$th call to $Q$. Further, let $C$ be the event that the algorithm reaches step $T$. Conditioned on $(\cup_{j=1}^{T}B_{j}\cup C)^{c}$, the run of this algorithm can be coupled with a run of LABEL:alg:maxRand for a pure DP $Q$. Further, the probability of the event $\cup_{j}B_{j}\cup C$ is at most $\sqrt{2\delta_{1}}T+\delta_{2}$. The claim follows. ∎

Since $\delta_{1}$ is typically smaller than a polynomial, we have not attempted to optimize the $\delta$ term in this theorem. We conclude with a remark that, in the case when $Q$ satisfies purely $\varepsilon_{1}$-DP, one can show that the hard stopping variant of LABEL:alg:maxRand preserves purely $\approx 3\varepsilon_{1}$-DP.

Fix any $\varepsilon_{0}\in(0,1/2),\gamma\in,\delta_{2}>0$ and let $T=\left\lceil\frac{1}{\gamma}\inp{\ln\frac{2(1+\gamma)^{2}}{\varepsilon_{0}\gamma^{2}}+\ln\ln\frac{2(1+\gamma)^{2}}{\varepsilon_{0}\gamma^{2}}}\right\rceil$. Consider a variant of LABEL:alg:maxRand that outputs the highest scored candidate from $S$ if $j$ reaches $T$. If $Q$ is $\varepsilon_{1}$-DP, then the output of this algorithm is $(3\varepsilon_{1}+3\varepsilon_{0})$-DP.

The proof of this theorem is quite involved and is deferred to Section A.2.

Searching for a percentile-threshold: privacy-preserving sparse vector

In this section we consider the problem of searching for a percentile-threshold $\tau$ for any given percentile $p_{*}$ in a differentially private way. We start by defining some notations. Given any sequence of randomized queries $\left\{Q_{i}\right\}$, we write $q_{i}\sim Q_{i}(D)$ to indicate that $q_{i}$ is obtained from running the randomized query $Q_{i}$ on dataset $D$. In other words, $q_{i}\sim Q_{i}(D)$ means that $q_{i}$ follows the output distribution of the randomized query $Q_{i}$ on dataset $D$. We will treat these $Q_{i}(D)$ as samplable distributions, where each $Q_{i}$ is $\varepsilon_{1}$-DP. Then for any sequence of thresholds $\left\{\tau_{i}\right\}$, and a target threshold $p_{*}\in(0,1)$, we would like to test if $\Pr_{q_{i}\sim Q_{i}(D)}[q_{i}\geq\tau_{i}]>p_{*}$ and output the first one that is above the threshold, and in a differentially private way.

It is worth noting that this can be seen as an extension of the standard sparse vector algorithm for Lipschitz queries: given $1$-Lipschitz queries $f_{1},\cdots,f_{k}$ and a threshold $\tau_{0}$, if we set $p_{*}=\frac{1}{2}$, $Q_{i}=f_{i}+\mathtt{Lap}\inp{\frac{4}{\varepsilon_{1}}}$ and $\tau_{i}=\tau_{0}$, then it is not hard to check that the queries $Q_{i}$ are now $\varepsilon_{1}$-DP, and the first query $Q_{i}$ above the percentile-threshold is exactly the same as the first query $f_{i}$ above the query threshold $\tau_{0}$ (that is, the first $f_{i}$ with median score at least $\tau_{0}$). Answering such a percentile query exactly is not private (see Section B.3 for an example for $p_{*}=1/2$), so we will have to relax the goal of finding the first above percentile-threshold query. Similar to the standard setting, we would like that:

if a query is much below the threshold, that is, $\Pr_{q_{i}\sim Q_{i}(D)}[q_{i}\geq\tau_{i}]\ll p_{*}$, then our algorithm should report “below threshold” (denoted by $\bot$);

if a query is much above the threshold, that is, $\inp{1-\Pr_{q_{i}\sim Q_{i}(D)}[q_{i}\geq\tau_{i}]}\ll\inp{1-p_{*}}$, then our algorithm should report “above threshold” (denoted by $\top$).

In fact, our algorithm will be a natural extension of the standard sparse vector algorithm.

To illustrate ideas, we will start by assuming that we have access to an exact percentile oracle: $p(\tau_{i},Q_{i}):=\Pr_{q_{i}\sim Q_{i}}[q_{i}\geq\tau_{i}]$. As a remark, such a percentile oracle is available in the standard sparse vector algorithm, which is just the cumulative distribution function of the Laplace distribution. We observe that if the randomized queries $Q_{i}$ are $\varepsilon_{1}$-DP, then both $\ln p(\tau_{i},Q_{i})$ and $\ln\inp{1-p(\tau_{i},Q_{i})}$ are $\varepsilon_{1}$-Lipschitz. In other words, although we no longer have Lipschitzness in the “answer of a query” space (that is, the quantile space), the fact that each query is $\varepsilon_{1}$-DP will ensure that we have Lipschitzness in the logarithm of the percentile space (that is, the log of the CDF). This allows us to adapt the sparse vector algorithm to the log of the percentile space.

Let $\Phi(x):=\frac{x}{1-x}$. Note that $\ln\Phi\inp{p(\tau_{i},Q_{i})}$ is $2\varepsilon_{1}$-Lipschitz: since both $\ln p(\tau_{i},Q_{i})$ and $\ln\inp{1-p(\tau_{i},Q_{i})}$ are $\varepsilon_{1}$-Lipschitz, and $\ln\Phi\inp{p(\tau_{i},Q_{i})}$ is just the difference of two $\varepsilon_{1}$-Lipschitz functions. Also notice that $\Phi$ is a strictly increasing function for $x\in(0,1)$. Given access to the oracle $p(\tau_{i},Q_{i})$, we can then adapt the sparse vector algorithm as in LABEL:alg:gensparse0.

If for every $i$, $Q_{i}$ is $\varepsilon_{1}$-DP, then

LABEL:alg:gensparse0 is $\varepsilon_{3}$-DP.

Conditional on LABEL:alg:gensparse0 reporting the $R$-th query $Q_{R}$ is “above threshold”, we have that $\forall\beta\in(0,1),\Pr\inb{\Phi\inp{p(\tau_{R},Q_{R})}\leq\inp{\frac{\beta}{R+1}}^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}\Phi(p_{*})}\leq\beta$. In other words, the algorithm does not stop too early.

Conditional on LABEL:alg:gensparse0 reporting the $R$-th query $Q_{R}$ is “above threshold”, we have that $\forall\beta\in(0,1),\Pr\inb{\exists i<R:\Phi\inp{p(\tau_{i},Q_{i})}\geq\inp{\frac{R+1}{\beta}}^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}\Phi(p_{*})}\leq\beta$. In other words, the algorithm does not stop too late.

$\forall\beta\in(0,1)$, if for some $i$, $\Phi\inp{p(\tau_{i},Q_{i})}\geq\inp{\frac{1}{\beta}}^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}\Phi(p_{*}),$ then $\Pr\inb{a_{i}=\top|\forall j<i,a_{j}=\bot}\leq\beta$. In other words, on a query that is way above the threshold the algorithm will likely halt.

(Sketch) Part (a), part (b) and part (c) all follow from the standard sparse vector analysis (see, e.g., ), and the fact that $\ln\Phi\inp{p(\tau_{i},Q_{i})}$ is $2\varepsilon_{1}$-Lipschitz. Observe that the test $e^{\xi_{i}}\cdot\Phi\inp{p(\tau_{i},Q_{i})}>e^{\nu}\Phi(p_{*})$ is equivalent to $\xi_{i}+\ln\Phi\inp{p(\tau_{i},Q_{i})}>\nu+\ln\Phi(p_{*})$. Therefore, if we view $\ln\Phi\inp{p(\tau_{i},Q_{i})}$ as the $i$-th query (which is $2\varepsilon_{1}$-Lipschitz) and $\ln\Phi(p_{*})$ as the threshold, then this is indeed the standard sparse vector setting. The details are omitted here as we will see proofs for stronger claims for the actual algorithm in Theorem 4.4.

For part (d), observe that the test $e^{\xi_{i}}\cdot\Phi\inp{p(\tau_{i},Q_{i})}>e^{\nu}\Phi(p_{*})$ will pass if $\xi_{i}\geq-\frac{8\varepsilon_{1}}{\varepsilon_{3}}\ln\frac{1}{\beta}$ and $\nu\leq\frac{4\varepsilon_{1}}{\varepsilon_{3}}\ln\frac{1}{\beta}$. By a union bound, with probability at least $1-\beta$, both will happen at the same time. In other words, the probability of not halting after seeing a query way above the threshold is at most $\beta$. ∎

We give some estimates in the special case of $p_{*}=1/2$, which corresponds to the range of the standard sparse vector setting, as quick corollaries. In fact, if one apply this to the standard sparse vector setting, one can recover guarantees that match the standard setting up to constant factors.

If $p_{*}=1/2$, and for every $i$, $Q_{i}$ is $\varepsilon_{1}$-DP, then

LABEL:alg:gensparse0 is $\varepsilon_{3}$-DP.

Conditional on LABEL:alg:gensparse0 reporting the $R$-th query $Q_{R}$ is “above threshold”, we have that $\forall\beta\in(0,1),\Pr\inb{p(\tau_{R},Q_{R})\leq\frac{\beta^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}}{\beta^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}+(R+1)^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}}}\leq\beta$. In other words, the algorithm does not stop too early.

Conditional on LABEL:alg:gensparse0 reporting the $R$-th query $Q_{R}$ is “above threshold”, we have that $\forall\beta\in(0,1),\Pr\inb{\exists i<R:p(\tau_{i},Q_{i})\geq\frac{(R+1)^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}}{\beta^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}+(R+1)^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}}}\leq\beta$. In other words, the algorithm does not stop too late.

$\forall\beta\in(0,1)$, if for some $i$, $p(\tau_{i},Q_{i})\geq 1-\frac{\beta^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}}{1+\beta^{\frac{12\varepsilon_{1}}{\varepsilon_{3}}}},$ then $\Pr\inb{a_{i}=\top|\forall j<i,a_{j}=\bot}\leq\beta$. In other words, the algorithm will likely halt on a query that is way above the threshold.

2. Sparse vector for online private queries

Next we show that one could replace the exact percentile oracles $p(\tau_{i},Q_{i}(D))$ with unbiased estimators $\widetilde{p_{i}}$. Assuming that we have unlimited access to the randomized queries $\left\{Q_{i}(D)\right\}$, we consider the following natural unbiased estimator for $p(\tau_{i},Q_{i}(D))$: given iid samples $q_{i,1},\cdots,q_{i,N}$, where for each $j$, $q_{i,j}\sim Q_{i}(D)$, we define $\widetilde{p_{i}}:=\frac{1}{N}\sum_{j=1}^{N}\inb{q_{i,j}\geq\tau_{i}}$, where $\inb{q_{i,j}\geq\tau_{i}}$ is the Iverson bracket defined by

Since $\widetilde{p_{i}}$ is now a random function of the dataset, the usual Lipschitzness is not well-defined, unlike for the function $p(\tau_{i},Q_{i}(D))$. One approach of defining “Lipschitzness” for such a random function would be to consider the earth mover distance. This is what we will do next.

Let $\widetilde{p_{i}}^{\prime}$ be the analogous unbiased estimator for $p(\tau_{i},Q_{i}(D^{\prime}))$ on a neighboring dataset $D^{\prime}$. By $\varepsilon_{1}$-DP of $Q_{i}$, we have that

In order to adapt LABEL:alg:gensparse0, ideally we would like a probabilistic version of $\widetilde{p_{i}}\leq e^{\varepsilon_{1}}\widetilde{p_{i}}^{\prime}$ to be true: if there is a coupling between $\widetilde{p_{i}}$ and $\widetilde{p_{i}}^{\prime}$ such that $\left|\ln\widetilde{p_{i}}-\ln\widetilde{p_{i}}^{\prime}\right|\leq\varepsilon_{1}$, then we can replace $p(\tau_{i},Q_{i}(D))$ with $\widetilde{p_{i}}$ in LABEL:alg:gensparse0. This turns out to be too much to ask for in such a general setting. We show in Lemma 4.3 that a slightly weaker statement in indeed true. This is the key lemma that leads us to LABEL:alg:gensparse1.

Let $\left\{X_{1},\cdots,X_{n}\right\}$ and $\left\{Y_{1},\cdots,Y_{n}\right\}$ be two sequences of independent $\left\{0,1\right\}$ random variables, and let $X=\sum_{i=1}^{n}X_{i}$, $Y=\sum_{i=1}^{n}Y_{i}$. For any fixed $\varepsilon_{1}\in(0,1),\varepsilon_{0}\in(0,1)$, $\delta_{0}\in(0,1)$, let $C=2(e^{\varepsilon_{0}+\varepsilon_{1}}+1+e^{\varepsilon_{0}/2})<21$.

Equivalently, if we let $\Delta:=\frac{C\ln\frac{2}{\delta_{0}}}{\varepsilon_{0}\inp{e^{\varepsilon_{0}+\varepsilon_{1}}-1}}=O\inp{\frac{1}{\varepsilon_{0}^{2}}\ln\frac{1}{\delta_{0}}}$, then

We defer the proof of this lemma to Section A.3. Now we are ready to describe the extended version of the AboveThreshold algorithm. We now consider a potential function $\Phi^{(N,\Delta)}(x)=\frac{Nx+\Delta}{N(1-x)+\Delta}$. As an intuition, we will see that thanks to Lemma 4.3, if $Q_{i}$ is $\varepsilon_{1}$-DP, then for suitable choices of $\varepsilon_{0}$ and $\Delta$, there exists a coupling in which, with high probability, $\ln\Phi^{(N,\Delta)}\inp{\widetilde{p_{i}}}$ is $2(\varepsilon_{0}+\varepsilon_{1})$-Lipschitz.

For any fixed $\varepsilon_{0}\in(0,1)$, $\delta\in(0,1)$, $\beta\in(0,1)$ and an integer $T>1$, let $S=2(\varepsilon_{1}+\varepsilon_{0})$, $C=2(e^{\varepsilon_{0}+\varepsilon_{1}}+1+e^{\varepsilon_{0}/2})<21$, and $\Delta=\frac{C\ln\frac{8T}{\delta}}{\varepsilon_{0}\inp{e^{\varepsilon_{0}+\varepsilon_{1}}-1}}=O\inp{\frac{1}{\varepsilon_{0}^{2}}\ln\frac{T}{\delta}}$. If for every $i$, $Q_{i}$ is $\varepsilon_{1}$-DP, then:

LABEL:alg:gensparse1 with the above parameters is $(\varepsilon_{3},\delta)$-DP.

Conditional on LABEL:alg:gensparse1 reporting the $R$-th query $Q_{R}$ is “above threshold”, we have that $\forall\beta\in(0,1),\Pr\inb{\Phi^{(N,\Delta)}\inp{p(\tau_{R},Q_{R})}\leq\inp{\frac{\beta}{R+1}}^{\frac{6S}{\varepsilon_{3}}}\cdot e^{-\varepsilon_{0}}\cdot\Phi^{(N,\Delta)}(p_{*})}\leq\beta+\delta/2$. In other words, the algorithm does not stop too early. Moreover,

Conditional on LABEL:alg:gensparse1 reporting the $R$-th query $Q_{R}$ is “above threshold”, we have that $\forall\beta\in(0,1),\Pr\inb{\exists i<R:\Phi^{(N,\Delta)}\inp{p(\tau_{i},Q_{i})}\geq\inp{\frac{R+1}{\beta}}^{\frac{6S}{\varepsilon_{3}}}\cdot e^{\varepsilon_{0}}\cdot\Phi^{(N,\Delta)}(p_{*})}\leq\beta+\delta/2$. In other words, the algorithm does not stop too late. Moreover,

$\forall\beta\in(0,1)$, if for some $i$, $\Phi^{(N,\Delta)}\inp{p(\tau_{i},Q_{i})}\geq e^{\varepsilon_{0}}\inp{\frac{1}{\beta}}^{\frac{6S}{\varepsilon_{3}}}\Phi^{(N,\Delta)}(p_{*}),$ then

In other words, on a query that is way above the threshold the algorithm will likely halt.

Before proving the theorem, we state the following sufficient condition for establishing $(\varepsilon,\delta)$-DP.

Let $X$ and $Y$ be two random variables that share the same sample space and $\sigma$-algebra, If there exists constants $\delta>0,\varepsilon>0$, and for any event $A$, there exists a joint event $\mathcal{G}:=\mathcal{G}(X,Y)$ on $X$ and $Y$ such that $\Pr[\mathcal{G}]\geq 1-\delta$, and

Informally, in order to show $(\varepsilon,\delta)$-DP, it suffices to construct a coupling where, except with probability $\delta$, the two neighboring distributions satisfy $\varepsilon$-DP. It is worth noting that $X$ and $Y$ need not be independent. Thus one could optimize $\delta$ by constructing a coupling between $X$ and $Y$ that maximizes $\Pr[\mathcal{G}]$. In addition, we note that the design of $\mathcal{G}$ and the coupling between $X$ and $Y$ can be dependent on the event $A$.

Proof of Theorem 4.4. For part (a), we follow the standard analysis of sparse vector. Fix any two neighboring datasets $D$ and $D^{\prime}$. By Lemma 4.5, in order to show $(\varepsilon_{3},\delta)$-DP, it suffices to find a conditioning event $\mathcal{G}$, and a coupling between the output distribution of LABEL:alg:gensparse1 running on $D$ and $D^{\prime}$, such that they are $\varepsilon_{3}$-close except with probability $\delta$. Observe that in order to obtain the same output, it suffices if we can couple all the noisy tests of the form $e^{\xi_{i}}\cdot\Phi^{(N,\Delta)}\inp{\widetilde{p_{i}}}\geq e^{\nu}\Phi^{(N,\Delta)}(p_{*})$. These tests depend only on two types of randomness: the perturbations to the current percentile (in the form of $\xi_{i}$), and the perturbations to the desired percentile (in the form of $\nu$). We denote these randomness by $\left\{\xi_{i}\right\}$ and $\nu$ when running on dataset $D$ , and by $\left\{\xi_{i}^{\prime}\right\}$ and $\nu^{\prime}$ when running on $D^{\prime}$.

We consider the event that $a_{R}=\top$ and $\forall i<R,a_{i}=\bot$. Let $\Phi*:=\Phi^{(N,\Delta)}(p_{*})$, and

Now we are ready to specify the coupling. Given $\left\{\xi_{i}\right\}$ and $\nu$, we let $\nu^{\prime}=\nu+\ln\frac{g^{\prime}}{g}$, and \xi_{i}^{\prime}=\begin{cases}\xi_{i},&\hbox{ ifi}\\ \xi_{R}+\ln\frac{g^{\prime}}{g}+\ln\frac{\Phi_{R}}{\Phi_{R}^{\prime}},&\hbox{ ifi=R}\end{cases}. Then, it is not hard to check that under this coupling,

In the following we will abuse notation, and write $\Pr_{\mathtt{Lap}}[\xi_{R}]$ to denote the probability density function of the Laplace distribution. Then, let $a_{i}$ be the $i$-th output of the algorithm running on dataset $D$, and $a_{i}^{\prime}$ be that of $D^{\prime}$.

Similarly if we let $X_{2}=N(1-\widetilde{p_{i}})$ and $Y_{2}=N(1-\widetilde{p_{i}}^{\prime})$, then under the trivial coupling,

We consider the following conditioning event:

By a union bound, we have $\Pr\inb{\mathcal{G}}\geq 1-\delta$. Conditional on $\mathcal{G}$, by triangle inequality we have:

In other words, conditional on $\mathcal{G}$,

where the last inequality uses the probability density function of the two Laplace distributions.

Finally consider the event that $R=T$ and $a_{i}=\bot$ for all $i\in[T]$, by a similar argument we have

Since our choice of $R$ is arbitrary, this shows that conditioned on $\mathcal{G}$, we have $\varepsilon_{3}$-DP for the output of our algorithm. Since $\Pr[\mathcal{G}]\geq 1-\delta$, by Lemma 4.5 this concludes $(\varepsilon_{3},\delta)$-DP for the output unconditionally.

For part (b), we consider the events of non-concentration:

where the bounds for $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ follows directly from CDF of the Laplace distribution, and the bound for $\mathcal{F}_{3}$ follows from a concentration bound (see Lemma A.4). Therefore, conditional on avoiding $\mathcal{F}_{1}\cup\mathcal{F}_{2}$, if the algorithm stops at the $k$-th iteration, we have that

Next, conditioning further on avoiding $\mathcal{F}_{3}$, we have that

Let $N\geq\frac{e^{\varepsilon_{0}}\Delta}{p_{*}}\inp{\frac{T+1}{\beta}}^{\frac{6S}{\varepsilon_{3}}}$, then we have

For part (c), it will be similar to part (b), except that we consider

Then, conditioning on avoiding $\mathcal{F}_{1},\mathcal{F}_{2},\mathcal{F}_{3}$, we have that

Let $N\geq\frac{e^{\varepsilon_{0}}\Delta}{1-p_{*}}\inp{\frac{T+1}{\beta}}^{\frac{6S}{\varepsilon_{3}}}$, then we have

3. A more efficient sparse vector for a one-sided guarantee

In this subsection we consider searching for the unknown “good” threshold $\tau$ for LABEL:alg:thresholding in a more efficient yet private way. The idea is that, instead of trying to tackle adversarily chosen randomized online queries, here we design better queries for our algorithm.

Specifically, let $Q(D)$ be a distribution dependent on dataset $D$, and let $q\sim Q$. Let $p(\tau,Q):=\Pr_{q\sim Q}[q\geq\tau]$. Then, given $p_{*}\in(0,1)$, our goal is to find $\tau_{*}:=\max\left\{\tau:p(\tau,Q)\geq p_{*}\right\}$ in a differentially private way.

Since $\tau_{*}$ can be very sensitive for neighboring datasets (see Section B.3 for an example for $p_{*}=1/2$), outputting $\tau_{*}$ directly would not be private. The relaxed goal is to find, with high probability, a private threshold $\widetilde{\tau}$ so that:

$\widetilde{\tau}$ is almost as large as $\tau_{*}$, and $p(\widetilde{\tau},Q)$ is not much smaller than $p_{*}$.

It is worth noting that, due to the one-sided nature of our goal (instead of asking $p(\widetilde{\tau},Q)$ to be close to $p_{*}$, we only want $p(\widetilde{\tau},Q)$ to be not much smaller than $p_{*}$), we find it much more convenient to shift the target by a constant factor: from $p_{*}$ to a smaller target $\approx\beta^{\frac{6\varepsilon_{1}}{\varepsilon_{3}}}\cdot p_{*}$. Such a tradeoff enables us to find a $\widetilde{\tau}$ that is closer to $\tau_{*}$, at the cost of a potentially smaller $p(\widetilde{\tau},Q)$. In the settings that we consider, a higher $\widetilde{\tau}$ allows for better “quality” of the selected candidate, while a larger $p_{*}$ is usually only for smaller computational cost.

Let $Q$ be a $\varepsilon_{1}$-DP distribution. For any fixed $\varepsilon_{0}\in(0,1)$, $\delta\in(0,1)$, $\beta\in(0,1)$ and an integer $R>1$, let $S=\varepsilon_{1}+\varepsilon_{0}$, $C=2(e^{\varepsilon_{0}+\varepsilon_{1}}+1+e^{\varepsilon_{0}/2})<21$, and $\Delta=\frac{C\ln\frac{4R}{\delta}}{\varepsilon_{0}\inp{e^{\varepsilon_{0}+\varepsilon_{1}}-1}}=O\inp{\frac{1}{\varepsilon_{0}^{2}}\ln\frac{R}{\delta}}$. Then the following holds for the output $\widetilde{\tau}$ of LABEL:alg:sparse1 with the above parameters:

$\widetilde{\tau}$ is $(\varepsilon_{3},\delta)$-DP.

$Pr\inb{\widetilde{\tau}\leq\tau_{*}-\frac{1}{R}}\leq 2\beta+\frac{\delta}{2R}$. In other words, the algorithm does not stop too late.

(Sketch) For part (a), this basically follows from the same proof of Theorem 4.4 part (a), except the following changes:

We consider $\Phi^{(N,\Delta)}(x)=Nx+\Delta$. It is not hard to see that the proof only relies on the fact that $\Phi^{(N,\Delta)}(x)$ is monotone, and $\Phi^{(N,\Delta)}\inp{\widetilde{p_{i}}}$ can be coupled with $\Phi^{(N,\Delta)}\inp{\widetilde{p_{i}}^{\prime}}$ multiplicatively.

Here we can re-use randomness, due to the fact that we essentially have the same distribution, and only need to change $\tau_{i}$. It is worth noting that we did not require independence of the $\left\{\widetilde{p_{i}}\right\}$ since we only used union bound.

We have also shifted the target of $\Phi^{(N,\Delta)}(p_{*})$ multiplicatively. However it does not affect privacy, since one can view such a shift as considering a different $p_{*}$ to begin with.

For part (b), similarly we consider the events of non-concentration:

where the bounds for $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ follows directly from CDF of the Laplace distribution, and the bound for $\mathcal{F}_{3}$ follows from a concentration bound (see Lemma A.4). Therefore, conditional on avoiding $\mathcal{F}_{1}\cup\mathcal{F}_{2}$, if the algorithm stops at the $k$-th iteration, we have that

Set $N=\frac{3\Delta e^{\varepsilon_{0}/2}}{p_{*}}\cdot\beta^{\frac{-12S}{\varepsilon_{3}}}(R+1)^{\frac{6S}{\varepsilon_{3}}}$, then we have

Next, conditioning further on avoiding $\mathcal{F}_{3}$, we have that

For part (c), as soon as $\tau_{i}\leq\tau_{*}$, we have $p(\tau_{i},Q)\geq p_{*}$. Therefore the test $\exp(\xi_{i})\cdot(N\widetilde{p_{i}}+\Delta)\geq\exp\inp{\nu-\Lambda}\cdot(Np_{*}+\Delta)$ will pass if $\xi_{i}\geq-\frac{4S}{\varepsilon_{3}}\ln\frac{1}{\beta}$, $\nu\leq\frac{2S}{\varepsilon_{3}}\ln\frac{1}{\beta}$, and $N\widetilde{p_{i}}+\Delta\geq e^{-\varepsilon_{0}/2}\inp{Np(\tau_{i},Q)+\Delta}$. Similar to part (b), we get that this will happen except with probability $2\beta+\frac{\delta}{2R}$. In other words, the probability of not halting after the first iteration with $\tau_{i}\leq\tau_{*}$ is at most $2\beta+\frac{\delta}{2R}$. ∎

Finally, by combining Theorem 4.6 and Theorem 3.1, we get the following:

Furthermore, \Pr\inb{\mathcal{M}\hbox{outputs\bot}}\leq\beta+\delta.

Here we set $p_{1}=\frac{1}{12K}\cdot\inp{\frac{\beta^{2}}{R+1}}^{6+\frac{12\varepsilon_{1}}{\varepsilon_{0}}}$, and $\gamma=p_{1}\beta$, $\varepsilon_{3}=\varepsilon_{0}$.

Applications

Suppose that we are given $K$ choices of hyperparameters, and for each choice $i\in[K]$, there is a differentially private learning algorithm $\mathcal{M}_{i}$. Given a training dataset $D_{1}$, $\mathcal{M}_{i}(D_{1})$ is a randomized mechanism that returns a model, which we often denote as $m$. Next, for a validation dataset $D_{2}$, we let $\widetilde{q_{i}}(m,D_{2})$ be the validation score of model $m$ and hyperparameter $i$. Then the goal of hyperparameter selection is to find a pair $(m,i_{*})$, that approximately maximizes the validation score.

It is worth noting that the dependencies on the validation set are only through the scoring functions $\widetilde{q_{i}}$, which are usually counting queries and thus have small sensitivity. This is the setting we will consider. Therefore, we let $q_{i}:=\widetilde{q_{i}}+\mathtt{Lap}\inp{\frac{1}{n\varepsilon_{2}}}$, where $n$ is the size of the validation set. Then, we define $Q_{i}(D_{1},D_{2})$ to be the distribution of $q_{i}(m,D_{2})$ when $m\sim\mathcal{M}_{i}(D_{1})$. Finally we let $Q$ be the distribution of $Q_{i}$ when we draw $i$ uniformly from $[K]$.

Then, in order to apply Theorem 4.7 or Theorem 3.2, it remains to verify that $Q$ is differentially private with respect to both datasets.

The distribution $Q(D_{1},D_{2})$ defined as above is always $\varepsilon_{2}$-DP for the validation set $D_{2}$. Moreover:

if $\left\{\mathcal{M}_{i}\right\}_{i=1}^{K}$ are $\varepsilon_{1}$-DP learning algorithms, then $Q(D_{1},D_{2})$ is $\varepsilon_{1}$-DP for the training set $D_{1}$;

if $\left\{\mathcal{M}_{i}\right\}_{i=1}^{K}$ are $(\varepsilon_{1},\delta_{1})$-DP learning algorithms, then $Q(D_{1},D_{2})$ is $(\varepsilon_{1},\delta_{1})$-DP for $D_{1}$.

It is worth noting that this holds for every $m$ in the support. Then $\varepsilon_{2}$-DP for $D_{2}$ follows from the fact that $\xi$ and $\nu$ follow the same $\mathtt{Lap}\inp{\frac{1}{n\varepsilon_{2}}}$ distribution and $\left|\xi-\nu\right|\leq 1/n$.

Then for $D_{1}$, note that the dependency of $Q_{i}$ on $D_{1}$ is only through $\mathcal{M}_{i}(D)$, which is $\varepsilon_{1}$-DP. Thus for every $i$, $Q_{i}(D_{1},D_{2})$ is $\varepsilon_{1}$-DP for $D_{1}$, thus $Q$ is also $\varepsilon_{1}$-DP for $D_{1}$.