# Generalized Private Selection and Testing with High Confidence

Edith Cohen Google Research and Tel Aviv University<EMAIL_ADDRESS>Xin
Lyu UC Berkeley and Google Research<EMAIL_ADDRESS>Most of the work
was done while interning at Google in Summer 2022. Jelani Nelson UC Berkeley
and Google Research<EMAIL_ADDRESS>Tamás Sarlós Google Research.
<EMAIL_ADDRESS>Uri Stemmer Tel Aviv University and Google Research.
<EMAIL_ADDRESS>
###### Abstract

Composition theorems are general and powerful tools that facilitate privacy
accounting across multiple data accesses from per-access privacy bounds.
However they often result in weaker bounds compared with end-to-end analysis.
Two popular tools that mitigate that are the exponential mechanism (or report
noisy max) and the sparse vector technique, generalized in a recent private
selection framework by Liu and Talwar (STOC 2019). In this work, we propose a
flexible framework of private selection and testing that generalizes the one
proposed by Liu and Talwar, supporting a wide range of applications. We apply
our framework to solve several fundamental tasks, including query releasing,
top-$k$ selection, and stable selection, with improved confidence-accuracy
tradeoffs. Additionally, for online settings, we apply our private testing to
design a mechanism for adaptive query releasing, which improves the sample
complexity dependence on the confidence parameter for the celebrated private
multiplicative weights algorithm of Hardt and Rothblum (FOCS 2010).

##  1 Introduction

Computations over large datasets often involve multiple intermediate accesses
to the data by different algorithms with the final output being some function
or aggregate of the outputs of these individual accesses. When we are
interested in differential privacy [DMNS16], we typically have privacy or
stability guarantees for each intermediate access which we would like to use
to bound the end-to-end privacy cost.

One approach to do that is to use composition theorems [DRV10]. Compositions
theorems yield overall privacy cost that scales linearly or sometimes even
with square-root dependence in the number of accesses. The disadvantage,
however, is that compositions theorems are designed for a scenario where all
the intermediate outputs are released and do not benefit in their privacy
accounting from the particular way in which the results of the intermediate
accesses are aggregated. Powerful tools from the literature for mitigating
this generally fall under the two categories of private testing and private
selection. Private testing includes the sparse vector technique [DNR+09, RR10,
HR10], where each access tests a hypothesis over the data, and only accesses
with positive output incur a privacy “charge.” Private selection includes the
exponential mechanism [MT07] that allows to select an approximate best
solution (out of a large set of possible solutions) while incurring a privacy
cost close to that of estimating the quality of a single solution. These tools
have many variations and extensions [LSL17, KMS21, PS22], most prominently, a
fairly recent framework by Liu and Talwar [LT19].

We propose a general template for private selection and testing that is
described in Algorithm 1. We view it as a system that provides two functions
to users, Selection and Test. The calls to these functions can be interleaved
and adaptive (that is, inputs may depend on prior outputs). Algorithm 1 is
initialized by randomly sampling an internal parameter $p$ that later serves
as a “pass” probability (where the data is not accessed if not “passed”). The
distribution of $p$ is controlled by the parameter $\gamma$, where a smaller
$\gamma$ pushes the distribution closer to $0$, lowering the privacy cost, and
a higher $\gamma$ pushes the distribution closer to $1$, increasing utility.
Generally, the choice of $\gamma$ provides a tradeoff between privacy and
utility. We will illustrate the tradeoff in several applications later.

The function Selection inputs a parameter $\tau$ and a collection of $k$
mechanisms $\\{M_{i}\\}_{i=1}^{k}$, all with outputs from the same ordered
domain111For example, the output space of $M_{i}$ can consist of pairs
$(s,q)\in X\times\mathbb{R}$, where $s$ is a solution and $q\in\mathbb{R}$ is
a quality score measuring how good $s$ is. We can then order pairs in the
decreasing order of $q$, and use Selection to select a solution with the best
quality score. We remark that this is also the illustrating example presented
in [LT19].. It generates a collection $S$ of outputs and then returns
$\textnormal{{Best}}(S):=\max_{x\in S}x$. The parameter $\tau$ may be set
differently in each call to Selection, and its role is to amplify utility by
repetition. Intuitively, a larger $\tau$ can compensate for a smaller $p$ as
each of the mechanisms $M_{i}$ produces in expectation $\tau p$ candidates for
the Best selection. Surprisingly, as we shall soon see, the privacy accounting
allows us to gain from separating $p$ and $\tau$. The function Test provides a
basic functionality of hypothesis testing subjected to the “pass” probability
$p$. Utility amplification (that also compensates for small pass probability
$p$) can be achieved by multiple calls to Test with the same hypothesis.

##### Meta Privacy Theorems.

We establish meta privacy theorems for the system in Algorithm 1. We first
provide separate bounds for Selection and Test calls.

######  Theorem 1 (Privacy guarantee for Selection).

Suppose that following initialization of Algorithm 1, there are $c\geq 1$
calls to Selection (with possibly varying inputs $\tau,k$, and
$\\{M_{i}\\}_{i=1}^{k}$). If the mechanisms fed into Selection in this process
satisfy $(\varepsilon,\delta_{i})$-DP with $\delta_{i}\geq 0$, then the list
of $c$ outputs satisfies $((2c+\gamma)\varepsilon,\tau\sum_{i}\delta_{i})$-DP.

######  Theorem 2 (Privacy guarantee for Test).

Suppose that following initialization of Algorithm 1, there are repeated calls
to Test until $c\geq 1$ $\top$ responses are received. If all the mechanisms
fed into Test in this process satisfy $(\varepsilon,\delta_{i})$-DP with
$\delta_{i}\geq 0$, then the collection of outputs satisfies
$((2c+\gamma)\varepsilon,\sum_{i}\delta_{i})$-DP or
$\left(O\left(\varepsilon\gamma+\varepsilon\sqrt{c\log(1/\delta)}\right),\delta+\sum_{i}\delta_{i}\right)$-DP
for all $\delta>0$.

The statements of Theorem 1 and Theorem 2 provide separate bounds for the
privacy cost of each type of call (Selection or Test). Importantly, our
framework allows for interleaved calls where the inputs are adaptive
(depending on prior outputs). In this case, the privacy costs simply add up
except for the $\gamma\varepsilon$ factor: If there are $c_{1}$ calls to
Selection and $c_{2}$ calls with $\top$ output to Test, each with mechanisms
that are $(\varepsilon,0)$-DP, then the total privacy cost is
$((2c_{1}+2c_{2}+\gamma)\varepsilon,0)$-DP.

The proofs of the meta-privacy theorems are provided in Section 2.
Interestingly, the $O(\varepsilon\sqrt{c\log(1/\delta)})$ dependence in the
statement of Theorem 2 does not follow as a direct consequence of advanced
composition [DRV10]. It requires some delicate calculations and is one of the
primary technical contributions of our work.

Input: A dataset $D=\\{x_{1},\dots,x_{n}\\}$. Parameter $\gamma\in(0,\infty)$.

1 initialize  __:

2 Sample $p$ from $[0,1]$ where $\Pr[p\leq x]=x^{\gamma},\forall x\in[0,1]$.

3

4Function  _Selection(_$\tau,k,M_{1},\dots,M_{k}$_)_: // $(M_{i})$ are
mechanisms with outputs from an ordered domain

5 $S\leftarrow\emptyset$

6 for  _$i=1,\dots,k$_ do

7 for  _$j=1,\dots,\tau$_ do

8 $r_{i,j}\sim\mathbf{Ber}(p)$

9 if  _$r_{i,j}=1$_ then

10 $s_{i,j}\leftarrow M_{i}(D)$

11 $S\leftarrow S\cup\\{s_{i,j}\\}$

12

13

14

15 return _$\textnormal{{Best}}(S)$_ // The top value in the ordered set $S$.

16

17Function  _Test(_$H$_)_: // $H$ is a private algorithm with output
$\\{\top,\perp\\}$

18 $r\sim\mathbf{Ber}(p)$

19 if  _$r=1$_ then

20 $\Gamma\leftarrow H(D)$

21 return _$\Gamma$_

22 else

23 return _$\perp$_

24

Algorithm 1 Private Selection and Testing

###  1.1 Relation to Prior Work

Our framework and its applications can be viewed as both a natural extension
of the sparse vector technique (SVT) [DNR+09, RR10, HR10] and a simpler and
more versatile alternative to the private selection framework of Liu and
Talwar [LT19].

##### Comparison with SVT.

In a nutshell, SVT allows one to test hypotheses of the form
“$f_{i}(D)\lessapprox t$” (i.e., test if $f_{i}(D)$ is approximately below the
threshold $t$ up to small additive error) while only incurring privacy loss
for “Above” results. We first show that Test calls provide this functionality:
To test if $f_{i}(D)\lessapprox t$ we specify an algorithm $H$ as follows: $H$
computes $\hat{f}_{i}(D)=f_{i}(D)+\mathbf{Lap}(1/\varepsilon)$ and outputs
$\top$ if and only if $\hat{f}_{i}(D)\geq t$. It is easy to see that $H$ is
$(\varepsilon,0)$-private. Given the pass parameter $p$, a single call of
$\textnormal{{Test}}(H)$ is insufficient for a reliable response and we
therefore amplify the confidence by repetition. For example, when $p\sim[0,1]$
it holds that $\Pr[p\geq\beta]=1-\beta$, therefore, if we repeat
$\textnormal{{Test}}(H)$ for $\frac{1}{\beta^{2}}$ times and none of these
test returns $\top$, we are very confident that $f_{i}(D)\lessapprox t$. On
the other hand, if $f_{i}(D)\leq t-\frac{10}{\varepsilon}\log(1/\beta)$, the
probability that we observe a $\top$ response is at most $\beta$.

Our meta-privacy proofs for Selection and Test turn out to be natural
generalization of the proof of the standard SVT [DR14]. The role of the “pass”
probability $p$ in our algorithm is very similar to the noisy threshold in
SVT, and we prove the privacy property by carefully coupling the executions of
Algorithm 1 on two neighboring inputs $D,D^{\prime}$ with different $p$
parameters. See Section 2 for the detail.

In Section 1.5, we further extend our framework to design a private Test
procedure, which yields improved confidence-accuracy tradeoffs for SVT. In
doing so, we borrow insights from several previous works. This includes the
observation that SVT does not necessarily need to re-initialize the noisy
threshold [LSL17], the framework that uses Rényi-Differential Privacy [Mir17]
to analyze SVT [ZW20], and the reductions from analyzing general mechanisms to
analyzing simpler coin-flipping games with binary outcomes [GLM+10, OV13,
MV18, KMS21].

##### Comparison with Liu-Talwar [LT19] private selection framework.

The hypothesis testing functionality, Test, in our framework does not seem to
have an analogue in [LT19]. The advantages of our Selection procedure compared
with [LT19] are as follows:

  * •

Operationally, [LT19] implements selection from $k$ mechanisms by “combining”
the $k$ mechanisms into a single mechanism $M$, defined as follows. $M$
chooses a random index $i\sim[k]$, runs $M_{i}$ and outputs its result. Then
$M$ is run for a random number $T$ times and the best output is returned. A
disadvantage is that to ensure utility, we need to set $T$ to be large enough
so that all mechanisms are selected enough times, which increases privacy
costs when the base mechanisms $M_{i}$’s only satisfy approximate DP. In
contrast, we avoid a random search and consider each mechanism separately,
which significantly simplifies the derivation of utility and privacy bounds.
This advantage is illustrated in the application to the stable selection task:
see Section 1.4.3.

  * •

The privacy analysis in [LT19] considers one-time private selection calls and
is not known to benefit from composition. In contrast, our algorithm (see
Theorems 1 and 2) only pays the $\gamma\varepsilon$ term once (which is
possible because we initialize $p$ once). This tighter composition benefits
applications where there are multiple accesses to the data and adaptive
accesses. In particular, the tighter composition for Test facilitates our
improved sparse vector algorithm.

There is another improvement to [LT19] by Papernot and Steinke [PS22], who
primarily consider private selection subject to Rényi-DP constraints. They
showed that given a private algorithm $\mathcal{A}$, privately running
$\mathcal{A}$ for $T$ rounds and selecting the best trial preserves privacy,
as long as $T$ is a random variable drawn from a carefully designed
distribution. They established privacy theorems for $T$ drawn from the Poisson
distribution or the truncated negative binomial distribution. To compare, the
Liu-Talwar algorithm shows that when $T$ obeys a geometric distribution, the
privacy is also preserved. Our result implies that when $T$ is uniform in
$\\{0,1,\dots,n\\}$, the selection is private. However, the algorithm by
[PS22] works by random search, and is subject to the same limitations as we
have discussed above: namely, the utility of the algorithm is harder to
characterize, and the algorithm is not known to benefit from compositions.

###  1.2 Applications

We overview applications of our framework in Section 1.3, where we demonstrate
improvements of results in [LT19], and in Section 1.4, where we list direct
applications of private selection to fundamental tasks in differential
privacy, including query releasing, top-$k$ selection and stable selection

A separate major contribution of our work is detailed in Section 1.5, where we
apply our privacy accounting theorem (Theorem 2) to improve the sparse vector
techniqe (SVT) and through that, improve the private multiplicative weight
update algorithm [HR10] and the sample complexity for adaptive data analysis
with linear queries.

###  1.3 Private Selection: Improving better-than-median selection

Liu and Talwar [LT19] formulated the problem of finding a better-than-median
solution of a private algorithm using oracle calls to the algorithm. The
problem was also implicitly studied in [GLM+10].

######  Definition 1 (Private Better-than-median).

Let $\mathcal{A}:{\mathcal{X}}^{n}\to{\mathcal{Y}}\times\mathbb{R}$ be an
$(\varepsilon,\delta)$-DP algorithm, where the output of $\mathcal{A}$
consists of a solution $y\in{\mathcal{Y}}$ and a score $s\in\mathbb{R}$.

Fix $D\in{\mathcal{X}}^{n}$ to be a dataset. Let
$s_{m}=\mathrm{median}\\{s(\mathcal{A}(D))\\}$ be the median score one gets
when running $\mathcal{A}$ on $D$. A better-than-median algorithm
$\mathcal{A}^{*}$ with confidence parameter $\beta$ uses oracle calls to
$\mathcal{A}$ and is such that the score of the output of $\mathcal{A}^{*}(D)$
is larger than $s_{m}$ with probability at least $1-\beta$.

The performance of a better-than-median algorithm is measured by computation
(number of oracle calls to $\mathcal{A}$), privacy guarantee, and confidence.
Liu and Talwar provided algorithms with the following tradeoffs:

######  Theorem 3 ([LT19]).

For every $\beta\in(0,1)$, for $(\varepsilon,\delta)$-DP $\mathcal{A}$ with
$\varepsilon\in(0,1)$ and $\delta\geq 0$, there is a better-than-median
algorithm $\mathcal{A}^{*}$ with confidence $1-\beta$ and the following
properties.

  * •

In expectation, $\mathcal{A}^{*}$ makes $O(\frac{1}{\beta})$ oracle calls to
$\mathcal{A}$.

  * •

$\mathcal{A}^{*}$ is $(3\varepsilon,O(\delta/\beta))$-differentially private.

Furthermore, for every $\alpha\in(0,1)$ and $\beta,\hat{\delta}\in(0,1)$,
there is an algorithm $\mathcal{A}^{*}$ such that:

  * •

With probability $1$, $\mathcal{A}^{*}$ makes
$T\leq\tilde{O}((\frac{1}{\beta})^{12+\frac{24}{\alpha}}\ln(1/\hat{\delta}))$
oracle calls to $\mathcal{A}$.

  * •

$\mathcal{A}^{*}$ is
$((2+\alpha)\varepsilon,T\delta+\hat{\delta})$-differentially private.

It was shown in [LT19] that the privacy guarantee of any better-than-median
algorithm is at least $2\varepsilon$. Surprisingly, Theorem 3 shows that the
failure probability $\beta$ can be made as small as desired at the cost of (1)
additive increase of $\varepsilon$ in the privacy parameter and (2) number of
oracle calls that scales linearly with $\frac{1}{\beta}$. The privacy cost can
be lowered further smoothly to be arbitrarily close to $2\varepsilon$ by
increasing the number of oracle calls using the parameter $\alpha\in(0,1)$.

##### Our improvement.

We design a new algorithm that provides a smooth trade-off between utility and
efficiency:

######  Theorem 4.

For every $\alpha\in(0,\infty)$ and $\beta\in(0,1)$, for
$(\varepsilon,\delta)$-DP $\mathcal{A}$ with $\varepsilon\in(0,1)$ and
$\delta\geq 0$, there is a better-than-median algorithm $\mathcal{A}^{*}$ with
confidence $1-\beta$ that satisfies the following:

  * •

With probability $1$, $\mathcal{A}^{*}$ makes at most $T$ oracle calls to
$\mathcal{A}$, where

$T=\begin{cases}\leavevmode\nobreak\ \leavevmode\nobreak\
\left\lceil\frac{2}{\beta}\right\rceil&\text{if $\alpha=1$}\\\ \left\lceil
5(\frac{2}{\beta})^{1/\alpha}\log(1/\beta)\right\rceil&\text{otherwise}\end{cases}.$

  * •

$\mathcal{A}^{*}$ is $((2+\alpha)\varepsilon,T\delta)$-differentially private.

Theorem 4 follows using Algorithm 1: Consider the case $\alpha=1$ and
(arbitrary) $\beta\in(0,1)$. $\mathcal{A}^{*}$ initializes Algorithm 1 with
$\gamma=1$ and calls Selection with arguments
$(k=1,\tau=\lceil\frac{2}{\beta}\rceil,M_{1}=\mathcal{A})$. It follows from
Theorem 1 that $\mathcal{A}^{*}$ is $(3\varepsilon,\tau\delta)$-DP. As for the
utility, note that Selection runs $\mathcal{A}$ for
$m\sim\mathbf{Bin}(\tau,p)$ times where $p$ is uniformly random in $[0,1]$.
Equivalently, $m$ is uniformly random in $\\{0,1,\dots,\tau\\}$222As for all
$m\in\\{0,1,\ldots,\tau\\},\mathbb{E}_{p\sim U[0,1]}{\tau\choose
m}p^{m}(1-p)^{\tau-m}=1/(\tau+1)$.. Therefore, the probability that
$\mathcal{A}^{*}$ fails to get a better-than-median solution is at most

$\frac{1}{\tau+1}\sum_{m=0}^{\tau}2^{-m}\leq\frac{2}{\tau+1}\leq\beta.$

The privacy-computation tradeoffs by varying $\alpha$, as stated in Theorem 4,
are obtained by varying $\gamma$ in the initialization of Algorithm 1. We
provide details in Section 3.1. In contrast, in the regime $\alpha\in(0,1)$,
the Liu-Talwar algorithm (Theorem 3) uses estimates of the “quantiles” of the
outputs of $\mathcal{A}$ and a complex simulation of SVT. Consequently, they
only obtain approximate-DP guarantees333Namely, the parameter $\hat{\delta}$
has to be non-zero in Theorem 3. and utilize many more (in the _exponent_)
oracle calls to $\mathcal{A}$. Our improvement in the number of oracle calls
in the regime $\alpha<1$ answers an open question posed in [LT19].

An additional advantage of Theorem 4 is that it applies in the regime
$\alpha>1$ that allow for dramatic improvement in the number of oracle calls
when we sacrifice a bit more privacy. For example, with $\alpha=2$, the number
of oracle calls has square-root dependence on $1/\beta$ and with
$\alpha=\log(1/\beta)$, the number of oracle calls is only logarithmic in
$1/\beta$.

###  1.4 Direct Applications of Private Selection

In the following, we mention several applications of the private selection
algorithm. We note that the applications can also be obtained using the Liu-
Talwar framework but using Algorithm 1 gives simpler proofs and smaller
constants. The primary contribution in this subsection is making the
connection between the private selection framework and these concrete
applications.

####  1.4.1 Query Releasing

Consider the task of answering $k$ sensitivity-$1$ queries
$f_{1},\dots,f_{k}:{\mathcal{X}}^{n}\to\mathbb{R}$. A fundamental and
extensively studied [SU17, GZ21, GKM21, DK20] problem is to characterize the
privacy-accuracy tradeoff for the query releasing task. That is, for a given
privacy budget $(\varepsilon,\delta)$, determine the smallest error $e$, such
that there is an $(\varepsilon,\delta)$-DP algorithm that releases answers to
all of the $k$ queries within $\ell_{\infty}$-error $e$. A naive application
of the Gaussian mechanism gives expected $\ell_{\infty}$-error
$O\left(\frac{\sqrt{k\log(1/\delta)\log(k)}}{\varepsilon}\right)$, which was
improved to
$O\left(\frac{\sqrt{k\log(1/\delta)\log\log(k)}}{\varepsilon}\right)$ by
Steinke and Ullman [SU16]. Recently, the question was raised again as an open
question [SU20] and two significant advances were made [GKM21, DK20]. We
resolve the problem completely by applying the private selection framework
together with an algorithm from [GKM21]:

######  Theorem 5.

There is a constant $C>0$ such that the following holds. For every
$\varepsilon\in(0,1),\delta\in(0,1/2)$ and $k\in\mathbb{N}$, there is an
$(\varepsilon,\delta)$-DP algorithm that answers $k$ given sensitivity-$1$
queries $f_{1},\dots,f_{k}$, such that

$\Pr_{\tilde{f}}\left[\|f-\tilde{f}\|_{\infty}\leq C\frac{\sqrt{k\log
1/\delta}+\log(1/\delta)}{\varepsilon}\right]=1,$

where $\tilde{f}:=(\tilde{f}_{1},\dots,\tilde{f}_{k})$ denotes the responses
released by the algorithm.

######  Remark 1.

The $\frac{\log(1/\delta)}{\varepsilon}$ term in the error is necessary if one
desires the answers to be accurate with probability one. There is a lower
bound even for the case $k=1$444To see this lower bound, let $\mathcal{A}$ be
an arbitrary query-releasing mechanism. We construct a sensitivity-$1$
function $f$ and two private inputs $D^{0},D^{1}$ of distance
$\frac{\log(1/\delta)}{5\varepsilon}$ such that
$f(D^{0})-f(D^{1})=\frac{\log(1/\delta)}{5\varepsilon}$. Since $\mathcal{A}$
is $(\varepsilon,\delta)$-DP, the supports of $\mathcal{A}(f,D^{0})$ and
$\mathcal{A}(f,D^{1})$ overlap, which means that there is $v\in\mathbb{R}$ and
$D\in\\{D^{0},D^{1}\\}$ such that
$|v-f(D)|\geq\frac{\log(1/\delta)}{10\varepsilon}$ but
$\Pr[\mathcal{A}(f,D)=v]>0$. .

Theorem 5 is tight, and improves on the two incomparable previous works
[GKM21, DK20].

  * •

[DK20] shows how to achieve the aforementioned accuracy with probability $1$.
However, their algorithm only works for
$\delta>2^{-\frac{k}{\log^{2}k\log^{4}(\log k)}}$.

  * •

[GKM21] shows an algorithm for the full range of $\delta\in(0,1/2)$. However,
their algorithm only promises to release an answer vector $\tilde{f}$ that is
accurate (in $\ell_{\infty}$ sense) with probability
$1-\frac{1}{\mathrm{poly}(k)}$. It was posed as an open question in [GKM21]
whether one can release accurate responses (within $\ell_{\infty}$ distance)
with probability one. Theorem 5 answers this question affirmatively.

##### Proof intuition.

In [GKM21], it was shown how to $(\varepsilon,\delta^{2})$-privately release a
vector $(\tilde{f}_{1},\dots,\tilde{f}_{k})$ such that, with probability at
least $\frac{1}{2}$, one has

$\|f-\tilde{f}\|_{\infty}\leq
O\left(\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\right).$

In the following, we use $\mathcal{A}$ to denote the GKM algorithm with
privacy parameters $(\varepsilon,\delta^{2})$.

The high level idea is to use the better-than-median algorithm of Theorem 4 to
amplify the success probability. Consider applying Theorem 4 on top of
$\mathcal{A}$ with $\alpha=1$ and $\beta=\delta$. Theorem 4 shows that the
number of oracle calls to $\mathcal{A}$ is bounded by $O(1/\delta)$. Then, it
follows that the resulting algorithm is
$(O(\varepsilon),O(\delta))$-differentially private. Moreover, the algorithm
releases an accurate vector with probability $1-\delta$. We can further
improve the success probability to $1$ by non-privately correcting erroneous
vectors. Since we do the non-private correction with probability at most
$\delta$, the result algorithm is still $(O(\varepsilon),O(\delta))$-DP. See
Section 3.2 for the detail.

####  1.4.2 Top-$k$ Selection

We consider optimization over a finite set, which is another fundamental task
in DP. Suppose there are $m$ candidates. Each of them is associated with a
sensitivity-$1$ score function
$f_{1},\dots,f_{m}:\mathcal{X}^{n}\to\mathbb{R}$. We want to select $k$
candidates from the $m$ options with largest scores. This is a well-known and
fundamental task that has been studied extensively (see, e.g., [MT07, DR14,
MS20, DR19, DDR20, QSZ21]).

To measure the utility of a selection algorithm, a common criterion is the
suboptimality gap. Suppose the algorithm releases a subset $S\subseteq[m]$ of
candidates. The suboptimality gap of $S$ is defined as

$\Gap(S):=\max_{i\not\in S}\\{f_{i}(D)\\}-\min_{j\in S}\\{f_{j}(D)\\}.$

Namely, this is the difference between the _best_ option outside $S$ and the
_worst_ option inside $S$.

The standard algorithm for top-$k$ applies the exponential mechanism
sequentially for $k$ times. If we aim for $(\varepsilon,\delta)$-DP for the
final algorithm, each round of the exponential mechanism needs to be
$(\frac{\varepsilon}{\sqrt{k\log(1/\delta)}},0)$-DP. Let $\mathbf{S}$ denote
the output of this algorithm. The standard calculation shows that

$\Pr\left[\Gap(\mathbf{S})\geq\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\cdot\log(m/\beta)\right]\leq\beta.$

Namely, with probability $1-\beta$, the suboptimality gap is
$\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\log(m/\beta)$. If one is
interested in very high confidence $\beta\leq m^{-\omega(1)}$, this bound on
the gap can be very large. We offer an algorithm where the suboptimality gap
has improved dependency on $1/\beta$.

######  Theorem 6.

There is an absolute constant $C>0$ such that the following holds. For every
$\varepsilon,\delta,\beta\in(0,1)$, there is an $(\varepsilon,\delta)$-DP
algorithm for top-$k$ selection satisfying the following. Let $\mathbf{S}$
denote the output of the algorithm. Then

$\Pr\left[\Gap(\mathbf{S})\geq
C\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\cdot\log(m)+C\frac{\log(1/\beta)}{\varepsilon}\right]\leq\beta.$

While we cannot avoid paying $\log(1/\beta)$ completely, we only pay
$\log(1/\beta)$ _once_ instead of $\sqrt{k\log(1/\delta)}$ times as was in the
standard algorithm.

The proof of Theorem 6 uses a similar strategy as that of Theorem 5. Suppose
we iteratively run the exponential mechanism for $k$ rounds to get $k$
candidates $\mathbf{S}$. With probability at least $\frac{1}{2}$ we have that
$\Gap(\mathbf{S})\leq
O(\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\cdot\log(m))$. We can use Theorem
4 on top of the naive algorithm to boost the success probability from
$\frac{1}{2}$ to $1-\beta$. See Section 3.3.

####  1.4.3 Stable Selection

The private selection algorithm also has implications to stable selections.
Generally, there is a lower bound saying that the
$\Omega(\frac{1}{\varepsilon}\log(m))$ suboptimality gap is necessary when we
select from $m$ candidates with sensitivity-$1$ score functions. However, when
there is a “structure” within the candidate family, we can often do better. We
show two representative examples in the following.

##### Choosing Mechanism.

Let $\mathcal{F}$ be a family of sensitivity-$1$ functions. Say that
$\mathcal{F}$ is $k$-bounded, if for any two neighboring datasets
$D,D^{\prime}$, it holds that $\sum_{f\in\mathcal{F}}|f(D)-f(D^{\prime})|\leq
k$. For $k$-bounded function families, we can do private selection with
suboptimaility gap $O(\frac{1}{\varepsilon}\log(k))$.

######  Theorem 7.

Suppose $\mathcal{F}$ is a $k$-bounded function family. For every
$\varepsilon,\delta\in(0,1)$, there is an $(\varepsilon,\delta)$-DP algorithm
$\mathcal{A}$ that holds a dataset $D$ and selects a function
$f\in\mathcal{F}$ such that, with probability at least $1-\beta$,

$f(D)\geq\max_{f^{*}\in\mathcal{F}}\\{f^{*}(D)\\}-O(\frac{1}{\varepsilon}\log(k/\delta\beta)).$

Theorem 7 generalizes several previous mechanisms for this setting [BNS16b,
GKM20], which all require additional assumptions on the family $\mathcal{F}$.

##### Stable Selection.

In some settings, there is a noticeable quality gap between the best solution
in $\mathcal{F}$ and the $(k+1)$-th best solution. In this case, we can also
obtain a private selection algorithm with improved suboptimality gap. In more
detail, let $\mathcal{F}$ be the function family. For any given dataset $D$,
sort functions in $\mathcal{F}$ by the decreasing order of $f(S)$. Namely,
write $\mathcal{F}=\\{f_{1},f_{2},\dots,f_{m}\\}$ so that $f_{1}(D)\geq
f_{2}(D)\geq\dots\geq f_{m}(D)$. Define the $k$-th gap of $S$ on $\mathcal{F}$
as $G_{k}(S,\mathcal{F})=f_{1}(D)-f_{k+1}(D)$.

######  Theorem 8.

For any $k\geq 1$ and $\varepsilon,\delta,\beta\in(0,1)$, there is an
$(\varepsilon,\delta)$-DP algorithm $\mathcal{A}$ that holds a dataset $D$ and
achieves the following. For any $1$-Lipschitz function family $\mathcal{F}$,
suppose $G_{k}(D,\mathcal{F})\geq\frac{10}{\varepsilon}\log(k/\delta\beta)$.
Then, with probability at least $1-\beta$, $\mathcal{A}$ selects a function
$f\in\mathcal{F}$ such that

$f(D)\geq\max_{f^{*}\in\mathcal{F}}\\{f^{*}(D)\\}-O(\frac{1}{\varepsilon}\log(k/\delta\beta)).$

There is a known algorithm for this task with asymptotically the same
performance (see [BDRS18, BKSW21] and references therein). However, our
algorithm and its analysis are very different. In particular, we demonstrate
how easily this problem can be solved under the private selection framework.

The proofs of Theorems 7 and 8 are deferred to Section 3.4.

###  1.5 Improved Sparse Vector Technique with Applications

In Section 1.4, we have shown that one can use the private selection framework
to improve the confidence-accuracy tradeoff for query releasing and top-$k$
selection. However, note that these two applications work in the _offline_
setting: in the query releasing and top-$k$ selection tasks, we are given the
$k$ queries and the $m$ candidates in advance, respectively.

It is natural to ask if similar improvements can be obtained in the online
setting. In the following, we demonstrate this is possible by designing a
modification of the well-known sparse vector technique, which offers an
improved confidence-accuracy tradeoff. We further apply our SVT to improve the
private multiplicative weight algorithm [HR10] and the sample complexity of
adaptive data analysis.

####  1.5.1 Review of Sparse Vector Technique and its Applications

Roughly speaking, the sparse vector technique provides an algorithm to answer
an _unbounded number_ of queries of the form $f_{i}(S)\lessapprox t$, while
one only incurs privacy loss for queries that are above the thresholds. See
Section 1.5.2 for a more technical and precise description.

##### Application to Private Multiplicative Weights.

SVT is the main subroutine in the celebrated private multiplicative weights
algorithm [HR10], which can be used to answer a large number of linear queries
subject to privacy constraints. We recall the problem setup first. Suppose
there is a universe ${\mathcal{X}}$ of size $|{\mathcal{X}}|$. We want to
design an algorithm $\mathcal{A}$ that receives a private input
$S=(x_{1},\dots,x_{n})\in{\mathcal{X}}^{n}$ consisting of $n$ data points from
${\mathcal{X}}$, and answers $m$ queries from an adversary ${\mathcal{B}}$.
Each query is specified by a function $f_{i}:{\mathcal{X}}^{n}\to[0,1]$, and
the algorithm needs to report an estimation $\tilde{f}_{i}$ for
$\mathbb{E}_{j\sim[n]}[f_{i}(x_{j})]$. The error of the algorithm is defined
as $\max_{i\in[m]}\\{|\tilde{f}_{i}-\mathbb{E}_{j\sim[n]}[f_{i}(x_{j})]|\\}$.

The private multiplicative weight update (MWU) algorithm allows one to
privately answer $m$ linear queries, while the error grows only
logarithmically with $m$, as shown in the following theorem.

######  Theorem 9 ([HR10], see also [DR14]).

For every $\varepsilon,\delta\in(0,1)$, there is an $(\varepsilon,\delta)$-DP
algorithm that answers $m$ adaptively chosen linear queries with the following
utility guarantee. Let $(\tilde{f}_{i})_{i\in[m]}$ denote the outputs of
$\mathcal{A}$. For every $\beta\in(0,1)$, with probability $1-\beta$ we have
that
$\max_{i\in[m]}\\{|\tilde{f}_{i}-\mathbb{E}_{j\in[n]}[f_{i}(x_{j})]|\\}\leq\alpha=\alpha(\beta)$,
where

$\alpha(\beta)^{2}\leq
O\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m/\beta)}{n\varepsilon}\right).$

Theorem 9 can be used to perform adaptive data analysis with linear queries.
We recall the setup: given the universe ${\mathcal{X}}$, there is a
distribution $\mathcal{D}$ over ${\mathcal{X}}$. An adaptive data analysis
algorithm receives as input $n$ samples from $\mathcal{D}$, denoted by
$S\sim\mathcal{D}^{n}$. It needs to adaptively answer $m$ linear queries,
where each query is specified by a function $f_{i}:{\mathcal{X}}\to[0,1]$ and
the algorithm needs to output an estimation of
$\mathbb{E}_{x\sim\mathcal{D}}[f(x)]$. An algorithm is called
$(\alpha,\beta,m)$-accurate, if it can answer $m$ (adaptive) linear queries
within additive error $\alpha$ with probability at least $1-\beta$. We
consider the _sample complexity_ of the problem. That is, fixing
${\mathcal{X}},m,\alpha,\beta$, we want to find out the smallest $n$ such that
there exists an $(\alpha,\beta,m)$-accurate algorithm that only uses $n$
samples from $\mathcal{D}$.

The generalization property of DP [DFH+15, BNS+16a] shows that, if we design
an algorithm to output estimations of $\mathbb{E}_{x\sim S}[f_{i}(x)]$ in a
privacy-preserving manner, then $\mathbb{E}_{x\sim S}[f_{i}(x)]$ is a good
approximation of $\mathbb{E}_{x\sim\mathcal{D}}[f_{i}(x)]$. Combining the
privacy-preserving algorithm by Theorem 9 with the generalization property,
one obtains the following well-known sample complexity upper bound.

######  Theorem 10 ([BNS+16a]).

For every finite universe ${\mathcal{X}}$, every $m\geq 1$ and
$\alpha,\beta\in(0,1)$, there is an $(\alpha,\beta,m)$-accurate adaptive data
analysis algorithm with sample complexity

$n\leq
O\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\beta)}\log(m/\beta)}{\alpha^{3}}\right).$

##### Our improvement.

Using our improved sparse vector algorithm, we obtain the following improved
private multiplicative weight update algorithm.

######  Theorem 11.

There is an absolute constant $C>0$ such that the following is true. For every
$\varepsilon,\delta\in(0,1)$, $m\in\mathbb{N}$ and $\beta\geq 2^{-m}$, there
exists

$\alpha\leq
C\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m)}{n\varepsilon\cdot\alpha}+\frac{\log(1/\beta)}{n\varepsilon}\right)$

and an $(\varepsilon,\delta)$-DP algorithm that answers $m$ adaptively chosen
linear queries such that, with probability $1-\beta$, we have
$\max_{i\in[m]}\\{|\tilde{f}_{i}-\mathbb{E}_{j\in[n]}[f_{i}(x_{j})]|\\}\leq\alpha$.

We get the following improved sample complexity for adaptive data analysis as
a corollary of Theorem 11 and the generalization property by [BNS+16a].

######  Theorem 12.

For every finite universe ${\mathcal{X}}$, every $m\geq 1$ and
$\alpha\in(0,1),\beta\geq 2^{-m}$, there is an $(\alpha,\beta,m)$-accurate
adaptive data analysis algorithm with sample complexity

$n\leq
O\left(\min\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\beta)}}{\alpha^{3}},\frac{\log|{\mathcal{X}}|}{\alpha^{4}}\right)\log
m+\frac{\log(1/\beta)}{\alpha^{2}}\right).$

We compare Theorem 12 with Theorem 10. Overall, the sample complexity given by
Theorem 12 scales at most linearly with $\log(1/\beta)$, and we manage to
“decouple” the dependence on $\log(1/\beta)$ from that on other parameters.
For the non-adaptive setting, it is known (by the Chernoff bound) that the
optimal sample complexity is $\Theta(\frac{\log m/\beta}{\alpha^{2}})$.
Therefore, in the high confidence regime (in particular, when
$\log(1/\beta)>\frac{\log|{\mathcal{X}}|}{\alpha^{2}}\log m$), the bound given
by Theorem 12 asymptotically matches the non-adaptive bound.

####  1.5.2 Intuition

Now we discuss the proof idea of our improved sparse vector technique.

##### Review of the standard SVT.

Let us briefly review how the standard SVT works. Let $X$ be the private
input, $t\in\mathbb{R}$ be a threshold, and $f_{1},\dots,f_{m}$ be a list of
sensitivity-$1$ queries. The sparse vector algorithm works by adding
independent Laplace noises $\mathbf{Lap}(1/\varepsilon)$ to the threshold and
each query function. Then, it outputs the first index $i$ such that the
(noisy) query value $\hat{f}_{i}(X)$ is larger than the (noisy) threshold
$\hat{t}$.

The standard approach to argue the utility of the algorithm works as follows.
First, with probability at least $1-\beta$, all the Laplace noises sampled in
the SVT algorithm are bounded by $\frac{1}{\varepsilon}\log(m/\beta)$.
Conditioning on this event and letting $i^{*}$ be the index returned by the
algorithm, we have that $f_{i^{*}}(X)\geq
t-\frac{2}{\varepsilon}\log(m/\beta)$ and $f_{j}(X)\leq
t+\frac{2}{\varepsilon}\log(m/\beta)$ for every $j<i^{*}$. Therefore, we
conclude that the algorithm is “approximately accurate” within error
$O(\frac{1}{\varepsilon}\log(m/\beta))$ with probability $1-\beta$.

In many scenarios (including the private MWU algorithm), one usually wants to
repeatedly run SVT for $k$ rounds, to identify $k$ meaningful queries. Suppose
we desire the final algorithm to be $(\varepsilon,\delta)$-private. In each
round of SVT, we need to set the privacy budget as
$\varepsilon^{\prime}=\frac{\varepsilon}{\sqrt{k\log(1/\delta)}}$. Doing the
analysis above, the error bound becomes
$\frac{1}{\varepsilon}\sqrt{k\log(1/\delta)}\log(m/\beta)$. This is somewhat
unsatisfactory, as we need to pay the $\log(1/\beta)$ term “$O(\sqrt{k})$”
times555However, we remark that the $\sqrt{k}\log(m)$ term is necessary (i.e.,
there is a lower bound of $\Omega(\sqrt{k}\log(m))$. See, e.g. [BUV14, SU17,
Vad17])..

##### Our improvement.

In the following, we show a modification of the sparse vector algorithm with
better confidence-accuracy trade-off. In particular, our algorithm is accurate
within error
$O(\frac{1}{\varepsilon}\sqrt{k\log(1/\delta)}\log(m)+\frac{\log(1/\beta)}{\varepsilon})$
with probability $1-\beta$. To compare, the standard SVT has error bound
$O(\frac{1}{\varepsilon}\sqrt{k\log(1/\delta)}\log(m/\beta))$. See Algorithm 3
in Section 4 for the complete description of our new algorithm; we explain the
intuition and the main technical challenges below.

Recall that we want to run SVT for $k$ rounds, and desire the final privacy
guarantee to be $(\varepsilon,\delta)$-DP. Given this constraint, each round
of SVT has to be $(\varepsilon^{\prime},0)$-DP for
$\varepsilon^{\prime}=\frac{\varepsilon}{\sqrt{k\log(1/\delta)}}$.

To illustrate the idea, suppose for now that we do not need to add a noise to
the threshold. (Namely, let us suppose that $\hat{t}=t$ always holds.) Now,
given a query $f_{i}(X)$, the sparse vector algorithm first obtains a noisy
estimation $\hat{f}_{i}(X)=f_{i}(X)+\mathbf{Lap}(1/\varepsilon^{\prime})$, and
then compares $\hat{f}_{i}(X)$ against $\hat{t}$. If the comparison result is
$\hat{f}_{i}(X)\leq\hat{t}$, then we are $(1-\beta)$-confident that
$\hat{f}_{i}(X)\leq\hat{t}+\frac{2}{\varepsilon^{\prime}}\log(1/\beta)$.
Observe that the error gap $\frac{2}{\varepsilon^{\prime}}\log(1/\beta)$ keeps
increasing as we desire a higher and higher confidence.

We can amplify confidence more economically by repetition. Let
$\tau=\log(1/\beta)$. Consider drawing $\tau$ independent noisy estimations of
$f_{i}(X)$. Namely, we calculate
$f_{i}^{(j)}(X)=f_{i}(X)+\mathbf{Lap}(1/\varepsilon^{\prime})$ for every
$j\in[\tau]$. Suppose that all of these noisy estimations are below $\hat{t}$.
Then we are $(1-\beta)$-confident that $f_{i}(X)\leq\hat{t}$. Here, somewhat
magically, we get the higher confidence without compromising privacy, as the
SVT algorithm only incurs a privacy loss when one observes an “Above-
Threshold” result.

However, the situation becomes more complicated when we get the “Above-
Threshold” result. If there is one estimation $f_{i}^{(j)}(X)$ exceeding
$\hat{t}$, we cannot immediately declare that $f_{i}(X)\geq\hat{t}$. Indeed,
for every fixed $f_{i}(X)$ and $\hat{t}$, as $\tau$ tends to infinity, with
probability one, we will eventually see a noisy estimation that is above
$\hat{t}$. Hence, the larger $\tau$ is, the less confident we are about the
conclusion $f_{i}(X)\geq\hat{t}$. To ensure that we can be equally confident
in the “Above-Threshold” case, we use the following strategy. We set a new
threshold $\hat{t}_{lower}=\hat{t}-\frac{6\log(m)}{\varepsilon^{\prime}}$.
Then we test if $f_{i}(X)\geq\hat{t}_{lower}$. Similarly, we amplify
confidence by repetition. Namely, we obtain $\tau$ independent estimations of
$f_{i}(X)$, and compare them against $\hat{t}_{lower}$. We pass the test if
and only if all the $\tau$ estimations are above $\hat{t}_{lower}$. If we pass
the test, then we are very confident that $f_{i}(X)\geq\hat{t}_{lower}$. If we
fail the test, we switch back to test if $f_{i}(X)\leq\hat{t}$ (using another
$\tau$ independent estimations of $f_{i}(X)$). In general, we alternate
between two tests $f_{i}(X)\stackrel{{\scriptstyle?}}{{\leq}}\hat{t}$ and
$f_{i}(X)\stackrel{{\scriptstyle?}}{{\geq}}t_{lower}$, until we pass one of
them.

##### Two challenges.

To implement the idea, there are two remaining issues.

  * •

In the standard SVT algorithm, we only pay for each “Above-Threshold” answer,
and every such answer can identify a meaningful query for us. However, in our
modified version of SVT, we will repeatedly test
$f_{i}(X)\stackrel{{\scriptstyle?}}{{\leq}}\hat{t}$ and
$f_{i}(X)\stackrel{{\scriptstyle?}}{{\geq}}\hat{t}_{lower}$ until we pass one
of them. Each time we fail a test, we need to pay the privacy loss. How do we
ensure that we can use the vast majority of our “privacy budget” to answer
meaningful queries?

  * •

In the argument above, we ignored the issue that $\hat{t}$ is only a noisy
version of $t$. Indeed, if we construct $\hat{t}$ by
$\hat{t}=t+\mathbf{Lap}(1/\varepsilon^{\prime})$, we are only
$(1-\beta)$-confident that
$|\hat{t}-t|\leq\frac{1}{\varepsilon^{\prime}}\log(1/\beta)$. Therefore, there
is a noticeable chance (e.g., with probability $10\beta$) that we will start
with an erroneous noisy threshold $\hat{t}$ (e.g.,
$|\hat{t}-t|\geq\frac{1}{\varepsilon^{\prime}}\log(\frac{1}{10\beta})$). If
this does happen, then the “alternate testing” algorithm does not make much
sense.

We resolve the first issue by allowing a gap of
$\frac{6}{\varepsilon^{\prime}}\log(m)$ between $\hat{t}_{lower}$ and
$\hat{t}$. Then, for any query $f_{i}(X)$, at least one of the following is
true:

$f_{i}(X)\leq\hat{t}-\frac{3}{\varepsilon^{\prime}}\log(m),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\text{or}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
f_{i}(X)\geq\hat{t}_{lower}+\frac{3}{\varepsilon^{\prime}}\log(m).$

We assume $\tau=\log(1/\beta)\leq m$. In this case, if
$f_{i}(X)\leq\hat{t}-\frac{3}{\varepsilon^{\prime}}\log(m)$, we can pass the
test $f_{i}(X)\stackrel{{\scriptstyle?}}{{\leq}}\hat{t}$ with probability at
least $1-\frac{1}{m^{2}}$. If
$f_{i}(X)\leq\hat{t}-\frac{3}{\varepsilon^{\prime}}\log(m)$ and we do fail the
test $f_{i}(X)\stackrel{{\scriptstyle?}}{{\leq}}\hat{t}$, then we say that a
“mistake” happens and one round of SVT is “wasted”. Similarly, we will say one
round of SVT is wasted if
$f_{i}(X)\geq\hat{t}_{lower}+\frac{3}{\varepsilon^{\prime}}\log(m)$ but we
fail the test $f_{i}(X)\stackrel{{\scriptstyle?}}{{\geq}}\hat{t}_{lower}$.
Since the probability of making a mistake is small (i.e., the probability is
at most $\frac{1}{m^{2}}$), we can show that if we run our version of SVT for
$k$ rounds to handle $m$ queries, then with probability $1-\beta$, at most
$\frac{\log(1/\beta)}{\log(m)}$ rounds are wasted. Therefore, we can still use
the algorithm to identify $k-\frac{\log(1/\beta)}{\log(m)}$ meaningful
queries.

We resolve the second issue by noting that there is a version of SVT that only
requires one to noisify the threshold once (see, e.g., [LSL17]). Here, the
crucial point is that when we only add noise to the threshold once, we can add
a much smaller noise to ensure privacy. However, the result from [LSL17] only
considers pure-DP case, and the privacy loss scales linearly with
$k\varepsilon$ in their analysis. We manage to prove Theorem 2, which shows
that the privacy scales proportionally with $\sqrt{k}\varepsilon$ if we relax
the requirement to approximate DP.

To be more precise, we explain the utility improvement quantitatively. In the
standard SVT algorithm, we need to re-initialize the noisy threshold before
starting each of the $k$ rounds, and we draw noises from the distribution
$\mathbf{Lap}(1/\varepsilon^{\prime})$ to achieve privacy. With our new
composition theorem, we only need to add one noise drawn from
$\mathbf{Lap}(1/\varepsilon)$. Recall that
$\frac{1}{\varepsilon^{\prime}}\approx\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}$.
The latter noise is considerably smaller than the former one.

In the formal proof (Section 4), we design our algorithm under the framework
of Algorithm 1, using the Test procedure as the main subroutine, which turns
out to be more amenable to mathematical manipulations. In the discussion
above, we chose to discuss our algorithmic idea under the standard SVT
framework, because SVT is arguably more well-known, and it might help readers
gain the intuition better.

##### The possibility of not noisifying threshold.

We also note that there are variants of SVT that do not add noise to the
threshold at all (see, e.g., [HR10, KLM+20]). It is tempting to apply those
variants to address the second issue. However, looking into the privacy proofs
for those variants, one can note that their $\delta$ parameter has to be at
least $2^{-k}$, where $k$ is the number of rounds that we run SVT (i.e., the
number of $\top$ responses we can get before halting the algorithm). In most
applications, requiring $\delta$ to be at least $2^{-k}$ would not be an
issue. However, in the application to private multiplicative weights and data
analysis, we are also interested in the case where $\delta\ll 2^{-k}$. In this
case, adding a noise to the threshold and using Theorem 2 to do the privacy
accounting give us the best possible result.

More precisely, if we use a version of SVT that does not noisify the
threshold, we will end up with weaker versions of Theorems 11 and 12.
Specifically, the error bound in Theorem 11 degrades to

$O\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m)}{n\varepsilon\alpha}+\frac{\log(1/\delta)\log(m)}{n\varepsilon}\right),$

and the sample complexity in Theorem 12 degrades to

$n\leq
O\left(\min\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\beta)}}{\alpha^{3}},\frac{\log|{\mathcal{X}}|}{\alpha^{4}}\right)\log
m+\frac{\log(1/\beta)}{\alpha^{2}}\right).$

##  2 Proof of Privacy Theorems

###  2.1 Proof of Theorem 1

###### Proof.

We first consider the case that all the mechanisms $M_{i}$’s satisfy pure-DP
(i.e., $\delta_{i}=0$ for all $i$). At the end the proof, we explain how to
deal with candidates with approximate DP property. Let $P_{\gamma}$ denote the
CDF for the parameter $p$. Namely, $P_{\gamma}(v)=\Pr[x\leq v]=v^{\gamma}$.
Fix $c\geq 1$. Let ${\mathcal{B}}$ be an adversary that adaptively calls
Selection for $c$ rounds. Denote Algorithm 1 as $\mathcal{A}$. For each
$p\in[0,1]$, let $\mathcal{A}^{p}$ denote Algorithm 1 conditioning on it
having sampled $p$ in the initialization step.

In one round, suppose that the ${\mathcal{B}}$ calls Selection with
$(\tau,k,M_{1},\dots,M_{k})$. By duplicating each mechanism for $\tau$ times,
we can assume without loss of generality that $\tau=1$. Let
$(i,s)\in[k]\times{\mathcal{Y}}$ be a potential outcome. Let $D$ and
$D^{\prime}$ be two neighboring datasets. Let
$\mathcal{A}^{p}(D,(M_{1},\dots,M_{k}))$ denote the output of
$\mathcal{A}^{p}$ given input $D$ and query $(M_{1},\dots,M_{k})$. We prove

$\Pr[\mathcal{A}^{p}(D,(M_{1},\dots,M_{k}))=(i,s)]\leq
e^{2\varepsilon}\Pr[\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime},(M_{1},\dots,M_{k}))=(i,s)].$

Note that $\mathcal{A}$ on this Selection call returns $(i,s)$, if and only if
both of the following events hold:

  * •

Event ${\mathcal{E}}_{1}$: $r_{i,1}=1$ and $M_{i}$ outputs $s$.

  * •

Event ${\mathcal{E}}_{2}$: For every $i^{\prime}\neq i$, either
$r_{i^{\prime},1}=0$ or $M_{i^{\prime}}$ outputs a solution that is inferior
than $s$.

Now, observe that

$\displaystyle\Pr[{\mathcal{E}}_{1}\mid\mathcal{A}^{p}(D)]$
$\displaystyle=p\cdot\Pr[M_{i}(D)=s]$ $\displaystyle\leq
e^{\varepsilon}p\Pr[M_{i}(D^{\prime})=s]$ $\displaystyle\leq
e^{2\varepsilon}\frac{p}{e^{\varepsilon}}\Pr[M_{i}(D^{\prime})=s]$
$\displaystyle=e^{2\varepsilon}\Pr[{\mathcal{E}}_{1}\mid\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime})].$
(1)

For every $i^{\prime}\neq i$, we have

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \Pr[r_{i^{\prime},1}=1\land M_{i^{\prime}}\text{ outputs
a solution better than $s$}\mid\mathcal{A}^{p}(D)]$
$\displaystyle=p\cdot\Pr[M_{i^{\prime}}(D)\text{ outputs a solution better
than $s$}]$
$\displaystyle\geq\frac{p}{e^{\varepsilon}}\cdot\Pr[M_{i^{\prime}}(D^{\prime})\text{
outputs a solution better than $s$}]$
$\displaystyle=\Pr[r_{i^{\prime},1}=1\land M_{i^{\prime}}\text{ outputs a
solution better than $s$}\mid\mathcal{A}^{p/\varepsilon}(D^{\prime})].$

Therefore,

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \Pr[r_{i^{\prime},1}=0\lor M_{i^{\prime}}\text{ outputs a
solution worse than $s$}\mid\mathcal{A}^{p}(D)]$
$\displaystyle\leq\Pr[r_{i^{\prime},1}=0\lor M_{i^{\prime}}\text{ outputs a
solution worse than $s$}\mid\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime})].$

Consequently,

$\displaystyle\Pr[{\mathcal{E}}_{2}\mid\mathcal{A}^{p}(D)]\leq\Pr[{\mathcal{E}}_{2}\mid\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime})].$
(2)

Combining (1) and (2) yields that

$\Pr[\mathcal{A}^{p}(D,(M_{1},\dots,M_{k}))=(i,s)]\leq
e^{2\varepsilon}\Pr[\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime},(M_{1},\dots,M_{k}))=(i,s)].$

Note that this inequality holds for all $(M_{1},\dots,M_{k})$, _independently
of_ the private input. Now, suppose ${\mathcal{B}}$ interacts with
$\mathcal{A}^{p}(D)$ (or $\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime})$) for
$c$ rounds. We can apply the argument above for the $c$ rounds separately. Let
$\mathbf{IT}({\mathcal{B}}:\mathcal{A})$ denote the random variable recording
the interaction transcript between ${\mathcal{B}}$ and $\mathcal{A}$. For
every possible collection $E$ of outcomes, we have

$\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p}(D))\in E]\leq
e^{2c\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime}))\in
E].$

Finally, we have

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}(D))\in E]$
$\displaystyle=\int_{0}^{1}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p}(D))\in
E]dP(p)$
$\displaystyle\leq\int_{0}^{1}e^{2c\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime}))\in
E]\cdot(\gamma p^{\gamma-1})\cdot dp$
$\displaystyle\leq\int_{0}^{e^{\varepsilon}}e^{2c\varepsilon+\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime}))\in
E]\cdot(\gamma(p/e^{\varepsilon})^{\gamma-1})\cdot
e^{(\gamma-1)\varepsilon}\cdot d(p/e^{\varepsilon})$
$\displaystyle\leq\int_{0}^{e^{\varepsilon}}e^{(2c+\gamma)\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(D^{\prime}))\in
E]\cdot dP(p/e^{\varepsilon})$
$\displaystyle=e^{(2c+\gamma)\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}(D^{\prime}))\in
E].$

This completes the proof.

Now, we consider the case that each mechanism $M_{i}$ is
$(\varepsilon,\delta_{i})$-DP with $\delta_{i}\geq 0$. For two neighboring
inputs $D,D^{\prime}$, we can decompose
$M_{i}(D)=(1-\delta_{i})N_{i}(D)+\delta_{i}E_{i}(D)$ and
$M_{i}(D^{\prime})=(1-\delta_{i})N_{i}(D^{\prime})+\delta_{i}E_{i}(D^{\prime})$,
where $N_{i}(D)$ and $N_{i}(D^{\prime})$ are
$(\varepsilon,0)$-indistinguishable and $E_{i}(D),E_{i}(D^{\prime})$ are
arbitrary. Then, each time we run $M_{i}(D)$, we can first sample from
$(N_{i}(D),E_{i}(D))$ with probability $(1-\delta,\delta)$, and run the chosen
mechanism. It follows that with probability at least $1-\tau\delta_{i}$, all
the executions involve only the $N_{i}$-part. We union-bound over $i$, and
conclude that with probability at least $1-\tau\sum_{i}\delta_{i}$, all the
executions involve only the $N_{i}$-part. Conditioning on this event, the
argument above shows that the outputs of the algorithm on $D,D^{\prime}$ are
$((2c+\gamma)\varepsilon,0)$-DP. It follows that the original system is
$((2c+\gamma)\varepsilon,\tau\sum_{i}\delta_{i})$-DP. ∎

###  2.2 Proof of Theorem 2

In this section, we prove Theorem 2. To ease the presentation, we will assume
that all the mechanisms fed into Test satisfy pure-DP. Having proved for this
case, the proof for approximate-DP mechanisms can be verified using similar
arguments as in the proof of Theorem 1.

####  2.2.1 Preliminaries

We will use the Rényi Differential Privacy [Mir17] framework to prove Theorem
2. Recall the definition. For two distributions $P,Q$ on the universe $X$ and
a real $\alpha\in(1,\infty)$, we define the $\alpha$-order Rényi divergence of
$P$ from $Q$ as

$D_{\alpha}(P\|Q):=\frac{1}{\alpha-1}\log\left(\sum_{x\in
X}P(x)\left(\frac{P(x)}{Q(x)}\right)^{\alpha-1}\right).$

The max-divergence is defined as

$D_{\infty}(P\|Q):=\log(\max_{x}\\{P(x)/Q(x)\\}).$

Since we will defer most of the technical manipulations to Appendix A, we
don’t discuss properties of divergences in the main paper.

####  2.2.2 Reduction to an Asymmetrical Coin Game

We use $\mathcal{A}$ to denote Algorithm 1. For $p\in[0,1]$, let
$\mathcal{A}^{p}$ denote the algorithm $\mathcal{A}$ conditioning on it having
sampled $p$ in the initialization step. Fix two neighboring dataset
$S,S^{\prime}$666We use $S,S^{\prime}$ to denote data sets in this subsection,
since the letter “$D$” is reserved for divergence.. Let
$\mathbf{IT}({\mathcal{B}}:\mathcal{A})$ denote the random variable recording
the interaction between the two randomized systems ${\mathcal{B}}$ and
$\mathcal{A}$. Let ${\mathcal{B}}$ be an adversary that interacts with
$\mathcal{A}$ by calling Test. Fix $p\in[0,1]$, we first compare
$\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p}(S))$ with
$\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime}))$. It
turns out that the two interactions can be captured by the following
experimental game, which we call the “$0$-favored” coin flipping game. Our
formulation of the coin-flipping game is inspired by several coin-flipping
mechanisms appeared in previous works [GLM+10, OV13, MV18, KMS21].

Input: An input bit $b\in\\{0,1\\}$, a privacy parameter
$\varepsilon\in(0,1)$, an integer $k\geq 1$.

1 initialize  __:

2 $c\leftarrow 0$

3

4while  _$c <k$_ do

5 Receive a query $(p,q)\in[0,1]^{2}$, promised that $0\leq q\leq p\leq
e^{\varepsilon}q$ and $(1-q)\leq e^{\varepsilon}(1-p)$

6 if  _$b=0$_ then

7 Sample $r\sim\mathbf{Ber}(p)$

8

9 else

10 Sample $r\sim\mathbf{Ber}(q)$

11

12 if  _$r=1$_ then

13 $c\leftarrow c+1$

14

15 Output $r$

16

Algorithm 2 The $0$-favored coin-flipping mechanism.

We call this mechanism $0$-favored, because for each query $(p,q)$, we always
have $q\leq p$, meaning that the algorithm is more likely to output $1$ when
its private input is $b=0$.

We claim that Algorithm 2 with privacy parameter $2\varepsilon$ can simulate
$\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p}(S))$ and
$\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime}))$. To
see this, suppose that ${\mathcal{B}}$ knows that he is interacting with
either $\mathcal{A}^{p}(S)$ or $\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime})$.
When ${\mathcal{B}}$ prepares a hypothesis $H$, he can compute

$p_{0}=\Pr[\mathcal{A}^{p}(S)\text{ on }\textnormal{{Test}}(H)\text{ outputs
}\top]$

and

$p_{1}=\Pr[\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime})\text{ on
}\textnormal{{Test}}(H)\text{ outputs }\top].$

It follows that
$p_{0}=p\cdot\Pr[H(S)=\top]\geq\frac{p}{e^{\varepsilon}}\Pr[H(S^{\prime})=\top]=p_{1}$,
$p_{0}\in(e^{-2\varepsilon}p_{1},e^{2\varepsilon}p_{1})$ and
$(1-p_{0})\in(e^{-2\varepsilon}(1-p_{1}),e^{2\varepsilon}(1-p_{1}))$.
Therefore, sending a query $H$ to Algorithm 1 is equivalent to sending a query
$(p_{0},p_{1})$ to Algorithm 2.

####  2.2.3 Analysis of the Coin Game

Algorithm 2 appears not to be differentially private. Nevertheless, it
satisfies a “one-sided” stability property, which can be captured by max-
divergence and Rényi divergence, as shown in the following two lemmas.

######  Lemma 1.

Consider Algorithm 2. Fix ${\mathcal{B}}$ to be an arbitrary adversary
interacting with Algorithm 2. Let $P,Q$ denote the distributions of the
interaction between $\mathcal{A}$ and Algorithm 2 when the private input is
$0$ or $1$, respectively. Then, for any $\alpha\in(1,\infty)$, we have
$D_{\infty}(P\|Q)\leq k\varepsilon$.

######  Lemma 2.

Consider the same setup as in Lemma 1. For any $\alpha\in(1,\infty)$, we have
$D_{\alpha}(P\|Q)\leq 3k\alpha\varepsilon^{2}$.

Intuitively, the two lemmas hold because for each query $(p,q)$ with $q\leq
p$, the algorithm is _always_ more likely to output $0$ when the private input
is $b=1$. Hence, when we consider $D_{\infty}(P\|Q)$ (i.e., when we consider
the divergence of $P$ from $Q$), we can “pass” the “$0$” outputs “for free”.
Essentially, the divergence increases only when we observe “$1$” outputs. The
counter $c$ counts the number of “$1$” outputs that we have seen so far. Since
we halt the algorithm once $c$ reaches a pre-defined threshold $k$, naturally,
one would expect that the divergence bound of $P$ from $Q$ grows only with $k$
(and is independent of the number of queries). Lemmas 1 and 2 confirm this
intuition.

The formal proof for Lemma 2, however, is quite delicate and involved. We
defer proofs of both lemmas to Appendix A.

####  2.2.4 Wrap-up

Now, let ${\mathcal{B}}$ be an adversary interacting with $\mathcal{A}^{p}(S)$
or $\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime})$. Lemma 1 shows that for every
collection of outputs $E$, it holds that

$\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p}(S))\in E]\leq
e^{2c\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime}))\in
E].$

By Hölder’s inequality and Lemma 2 (see also the conversion from Rényi DP to
approximate DP, e.g., [Mir17]), there is an absolute constant $D\geq 1$ such
that

$\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p}(S))\in E]\leq
e^{2D\sqrt{c\log(1/\delta)}\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime}))\in
E]+\delta.$

To finish the proof of Theorem 2, we integrate over $p\in[0,1]$. This step is
the same as the proof of Theorem 1 and we do not repeat it here.

####  2.2.5 Using Selection and Test Concurrently

We claimed in the introduction that our framework allows an analyst to
interleave its calls to Selection and Test, and only pay the privacy loss for
every call to Selection and every $\top$ response received from Test.
Specifically, if there are $c_{1}$ calls to Selection and $c_{2}$ calls with
$\top$ output to Test, each with mechanisms that are $(\varepsilon,0)$-DP,
then the total privacy cost is $((2c_{1}+2c_{2}+\gamma)\varepsilon,0)$-DP.

To see why this is true, let ${\mathcal{B}}$ be an adversary that interacts
with $\mathcal{A}$ arbitrarily. Consider the interaction between
${\mathcal{B}}$ and
$\mathcal{A}^{p}(S),\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime})$. Combining
the proofs of Theorems 1 and 2, we have

$\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p}(S))\in E]\leq
e^{2c_{1}\varepsilon+2c_{2}\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}^{p/e^{\varepsilon}}(S^{\prime})\in
E].$

Integrating over $p\in[0,1]$ shows that

$\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}(S))\in E]\leq
e^{2c_{1}\varepsilon+2c_{2}\varepsilon+\gamma\varepsilon}\Pr[\mathbf{IT}({\mathcal{B}}:\mathcal{A}(S^{\prime})\in
E],$

as desired.

##  3 Proofs for Applications

In this section, we prove theorems listed in Sections 1.3 and 1.4.

##### Notation.

For $\varepsilon,\delta>0$, we define the truncated Laplace mechanism
$\mathbf{TLap}(\varepsilon,\delta)$ as follows. The support of
$\mathbf{TLap}(\varepsilon,\delta)$ is
$[-\frac{\log(1/\delta)}{\varepsilon},\frac{\log(1/\delta)}{\varepsilon}]$.
For every
$v\in[-\frac{\log(1/\delta)}{\varepsilon},\frac{\log(1/\delta)}{\varepsilon}]$,
we have $\Pr[\mathbf{TLap}(\varepsilon,\delta)=v]\propto e^{-|v|\varepsilon}$.
The truncated Laplace mechanism can answer a sensitivity-$1$ query
$f:{\mathcal{X}}^{n}\to\mathbb{R}$ by publishing
$f(S)+\mathbf{TLap}(\varepsilon,\delta)$. It is well known that this mechanism
is $(\varepsilon,\delta)$-DP [GDGK20].

###  3.1 Better-Than-Median Selection

In this section, we prove Theorem 4, restated below.

Reminder of Theorem 4. For every $\alpha\in(0,\infty)$ and $\beta\in(0,1)$,
for $(\varepsilon,\delta)$-DP $\mathcal{A}$ with $\varepsilon\in(0,1)$ and
$\delta\geq 0$, there is a better-than-median algorithm $\mathcal{A}^{*}$ with
confidence $1-\beta$ that satisfies the following:

  * •

With probability $1$, $\mathcal{A}^{*}$ makes at most $T$ oracle calls to
$\mathcal{A}$, where

$T=\begin{cases}\leavevmode\nobreak\ \leavevmode\nobreak\
\left\lceil\frac{2}{\beta}\right\rceil&\text{if $\alpha=1$}\\\ \left\lceil
5(\frac{2}{\beta})^{1/\alpha}\log(1/\beta)\right\rceil&\text{otherwise}\end{cases}.$

  * •

$\mathcal{A}^{*}$ is $((2+\alpha)\varepsilon,T\delta)$-differentially private.

Furthermore, if $\mathcal{A}$ is $(\varepsilon,\delta)$-DP with $\delta>0$,
then $\mathcal{A}^{*}$ is $(\varepsilon,T\delta)$-DP.

###### Proof.

We design $\mathcal{A}^{*}$ that initializes Algorithm 1 with $\gamma=\alpha$
and calls Selection with arguments $(k=1,\tau=T,M_{1}=\mathcal{A})$ where $T$
given by the theorem statement. If follows from Theorem 1 that
$\mathcal{A}^{*}$ is $((2+\alpha)\varepsilon,\tau\delta)$-DP. As for the
utility, we have shown the utility guarantee for $\alpha=1$. When $\alpha\neq
1$, we argue as follows.

First, with probability at least $1-(\beta/2)$, we have that
$p\geq(2\beta)^{1/\alpha}$. We condition on this event. By our choice of $T$,
we know that $\mathcal{A}$ will be run for at least $t\geq\log(4/\beta)$ times
with probability at least $1-(\beta/4)$. We further condition on this event.
Then, the probability that the $t$ calls of $\mathcal{A}$ fail to yield a
better-than-median solution is at most $1-(\beta/4)$. Overall, the probability
that $\mathcal{A}*$ fails to output a better-than-median solution is at most
$1-\beta$, as desired. ∎

###  3.2 Query Releasing

In this section, we prove Theorem 5, restated below.

Reminder of Theorem 5. There is a constant $C>0$ such that the following is
true. For every $\varepsilon\in(0,1),\delta\in(0,1/2)$ and $k\in\mathbb{N}$,
there is an $(\varepsilon,\delta)$-DP algorithm that answers $k$ given
sensitivity-$1$ queries $f_{1},\dots,f_{k}$, such that

$\Pr_{\tilde{f}}\left[\|f-\tilde{f}\|_{\infty}\leq C\frac{\sqrt{k\log
1/\delta}+\log(1/\delta)}{\varepsilon}\right]=1,$

where $\tilde{f}:=(\tilde{f}_{1},\dots,\tilde{f}_{k})$ denotes the responses
released by the algorithm.

To prove Theorem 5, we need the following theorem due to [GKM21].

######  Theorem 13 ([GKM21]).

There is a constant $C_{1}>0$ such that the following is true. For every
$\varepsilon\in(0,1),\delta\in(0,1/2)$ and $k\in\mathbb{N}$, there is an
$(\varepsilon,\delta)$-DP algorithm that, given $k$ non-adaptive
sensitivity-$1$ queries $f_{1},\dots,f_{k}$, returns a list of answers
$(\tilde{f}_{1},\dots,\tilde{f}_{k})$, such that

$\Pr_{\tilde{f}}\left[\|f-\tilde{f}\|_{\infty}\leq C_{1}\frac{\sqrt{k\log
1/\delta}}{\varepsilon}\right]\geq\frac{1}{2}.$

The following statement follows as a simple corollary of Theorem 13.

######  Corollary 1.

There is a constant $C_{2}>0$ such that the following is true. For every
$\varepsilon\in(0,1),\delta\in(0,1/2)$ and $k\in\mathbb{N}$, there is an
$(\varepsilon,\delta)$-DP algorithm that, given $k$ non-adaptive
sensitivity-$1$ queries $f_{1},\dots,f_{k}$, returns a list of answers
$(\tilde{f}_{1},\dots,\tilde{f}_{k})$ and a real $s\in\mathbb{R}^{+}$
satisfying the following.

  * •

With probability $1$, it holds that $\|f-\tilde{f}\|_{\infty}\leq s$.

  * •

With probability at least $\frac{1}{2}$, it holds that

$s\leq C_{2}\left(\frac{\sqrt{k\log
1/\delta}}{\varepsilon}+\frac{\log(1/\delta)}{\varepsilon}\right).$

###### Proof.

Let $\mathcal{A}_{1}$ be an instantiation of the algorithm from Theorem 13
with privacy parameter set to $(\varepsilon/2,\delta/2)$. Given a list of
queries $(f_{1},\dots,f_{k})$. We first run $\mathcal{A}_{1}$ to produce a
list of responses $(\tilde{f}_{1},\dots,\tilde{f}_{k})$. Let
$g=\|f-\tilde{f}\|_{\infty}$. We compute
$s=g+2\frac{\log(1/\delta)}{\varepsilon}+\mathbf{TLap}(\varepsilon/2,\delta/2)$.
Finally, we release $(\tilde{f}_{1},\dots,\tilde{f}_{k})$ and $s$. It follows
that $s$ is an upper bound for $\|f-\tilde{f}\|_{2}$ with probability $1$.
Moreover, since $\|f-\tilde{f}\|_{\infty}\leq 4C_{1}\frac{\sqrt{k\log
1/\delta}}{\varepsilon}$ happens with probability at least $\frac{1}{2}$, it
follows that $s\leq\max(4C_{1},4)\cdot\left(\frac{\sqrt{k\log
1/\delta}}{\varepsilon}+\frac{\log(1/\delta)}{\varepsilon}\right)$ with
probability at least $\frac{1}{2}$. Since the truncated Laplace mechanism is
$(\varepsilon/2,\delta/2)$-DP, by the basic composition theorem, the whole
algorithm is $(\varepsilon,\delta)$-DP. ∎

Given Corollary 1, Theorem 5 follows by tuning parameters properly.

###### Proof of Theorem 5.

We will combine Corollary 1 with Theorem 4. In particular, given the target
privacy budget $(\varepsilon,\delta)$, let $\mathcal{A}$ be an instantiation
of Corollary 1 with privacy parameters $(\varepsilon/3,\delta^{2}/10)$. Then
we use Theorem 4 on top of $\mathcal{A}$ with $\gamma=1$ and
$\beta=\delta/10$, to select a vector $(\tilde{f}_{1},\dots,\tilde{f}_{k})$
with the smallest associated quality score $s$. Let $C_{2}=\max(4C_{1},4)$. If
$s\leq C_{2}\left(\frac{\sqrt{k\log
1/\delta}}{\varepsilon}+\frac{\log(1/\delta)}{\varepsilon}\right)$, then we
simply output $(\tilde{f}_{1},\dots,\tilde{f}_{k})$. Otherwise, we non-
privately output the original vector $(f_{1},\dots,f_{k})$. Since $s$ is an
upper bound of $\|f-\tilde{f}\|_{\infty}$, the utility guarantee is evident.

It remains to verify that the algorithm is $(\varepsilon,\delta)$-DP. The
vector $(\tilde{f}_{i})_{i\in[k]}$ selected by Theorem 4 is
$(\varepsilon,\delta/5)$-DP with respect to the private input. Moreover, with
probability at least $1-\delta/5$, it holds that

$s\leq C_{2}\left(\frac{\sqrt{k\log
1/\delta}}{\varepsilon}+\frac{\log(1/\delta)}{\varepsilon}\right).$

Therefore, we will do the non-private correction with probability at most
$\delta/5$. Consequently, the whole algorithm $(\varepsilon,\delta)$-DP. ∎

###  3.3 Top-$k$ Selection

In this section, we prove Theorem 6, restated below.

Reminder of Theorem 6. There is an absolute constant $C>0$ such that the
following holds. For every $\varepsilon,\delta,\beta\in(0,1)$, there is an
$(\varepsilon,\delta)$-DP algorithm for top-$k$ selection satisfying the
following. Let $\mathbf{S}$ denote the output of the algorithm. Then

$\Pr\left[\Gap(\mathbf{S})\geq
C\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\cdot\log(m)+C\frac{\log(1/\beta)}{\varepsilon}\right]\leq\beta.$

###### Proof.

We first consider the case that $\beta\geq\delta$. Define a mechanism
$\mathcal{A}$ as follows. Set
$\varepsilon^{\prime}=\frac{\varepsilon}{40\sqrt{k\log(1/\delta)}}$,
$\mathcal{A}$ repeatedly run the exponential mechanism for $k$ rounds, to
select $k$ candidates $\mathbf{S}\subset[m]$. Then $\mathcal{A}$ calculates
$\tilde{q}(S)=\Gap(S)+\mathbf{Lap}(\varepsilon/6)+13\frac{\log(1/\beta)}{\varepsilon}$
and outputs $\mathbf{S}$ and $\tilde{q}(S)$. By the basic and advanced
composition theorems of DP [DRV10], $\mathcal{A}$ is
$(\varepsilon/3,\delta^{2}/10)$-DP.

With probability $1-\beta/2$, all the Laplace noises sampled in the execution
of $\mathcal{A}$ are bounded by $\frac{10\log(1/\beta)}{\varepsilon}$. We
condition on this event. Then, it is easy to see that $\tilde{q}(S)$ provides
an upper bound of $\Gap(\mathbf{S})$. Moreover, by the utility proof of the
exponential mechanism, there is an absolute constant $C>0$ such that

$\P_{\mathbf{S},\tilde{q}}\left[\tilde{q}(\mathbf{S})\leq
C\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\cdot\log(m)+C\frac{\log(1/\beta)}{\varepsilon}\right]\geq\frac{1}{2}.$

We use Theorem 4 on top of $\mathcal{A}$ with $\gamma=1$ and
$\beta=\delta/10$, to select a subset $\mathbf{S}$ with the smallest
associated $\tilde{q}(S)$. The utility property of Theorem 4 shows that with
probability $1-\beta$, we have

$\Gap(\mathbf{S})\leq\tilde{q}(S)\leq
C\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\cdot\log(m)+C\frac{\log(1/\beta)}{\varepsilon}.$

The privacy property of Theorem 4 shows that the result algorithm is
$(\varepsilon,\delta)$-DP, as desired.

For the case $\beta<\delta$, we can first design an
$(\varepsilon,\delta^{\prime})$-DP top-$k$ selection algorithm with confidence
$\beta^{\prime}$, where $\delta^{\prime}=\delta/10$ and
$\beta^{\prime}=\delta^{\prime}$. It follows that with probability at least
$1-\beta^{\prime}$, we have

$\Gap(\mathbf{S})\leq
C^{\prime}\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}\cdot\log(m)+C^{\prime}\frac{\log(1/\beta^{\prime})}{\varepsilon}$

for a constant $C^{\prime}>0$. We can use the non-private correction trick
similar to the proof of Theorem 5 to non-privately correct bad subset
$\mathbf{S}$. This degrades the privacy bound of the algorithm from
$(\varepsilon,\delta/10)$-DP to $(\varepsilon,\delta)$-DP, and gives the
desired confidence bound (in fact, the confidence is improved to with
probability one). ∎

###  3.4 Stable Selection

In this section, we prove the results for stable selection.

##### Choosing Mechanism.

Let $\mathcal{F}$ be a family of $1$-Lipschitz functions. Recall that
$\mathcal{F}$ is $k$-bounded, if for any two neighboring datasets
$D,D^{\prime}$, it holds that $\sum_{f\in\mathcal{F}}|f(D)-f(D^{\prime})|\leq
k$. We now prove Theorem 7, which is restated below.

Reminder of Theorem 7. Suppose $\mathcal{F}$ is a $k$-bounded function family.
Then, there is an $(\varepsilon,\delta)$-DP algorithm $\mathcal{A}$ that
receives a private input $X$ and selects a function $f\in\mathcal{F}$ such
that, with probability at least $1-\beta$,

$f(D)\geq\max_{f^{*}\in\mathcal{F}}\\{f^{*}(D)\\}-O(\frac{1}{\varepsilon}\log(k/\delta\beta)).$

###### Proof.

For each function $f_{i}\in\mathcal{F}$, construct a mechanism
$\mathcal{M}_{i}$ as follows: $\mathcal{M}_{i}$ receives the takes as input
the dataset $D$ and outputs a pair
$(i,f_{i}(D)+\mathbf{TLap}(\varepsilon,\frac{\delta\beta}{5k}))$.

We use the Selection function in Algorithm 1 with parameters $\gamma=1$,
$\tau=\frac{4}{\beta}$ and mechanisms $\\{M_{i}\\}_{f_{i}\in\mathcal{F}}$, and
output the index $i$ returned from the Selection.

To see the privacy, we fix an arbitrary pair of adjacent datasets
$D,D^{\prime}$. It follows that
$\sum_{f\in\mathcal{F}}|f(D)-f(D^{\prime})|\leq k$. Moreover, it is easy to
see that that $i$-th mechanism is
$(\varepsilon,\frac{\delta\beta}{5k}\cdot|f_{i}(D)-f_{i}(D^{\prime})|)$-DP.
Therefore, by Theorem 1, our mechanism is $(3\varepsilon,\delta)$-DP.

To see the utility, fix the dataset $D$ and let $i^{*}$ be the index of the
best candidate. Then, with probability at least $1-\beta$, at least one trial
of $M_{i^{*}}(D)$ returns a pair $(i,s)$ with $s\geq f_{i^{*}}(D)$. We
condition on this event. Let $(j,s^{\prime})$ be the result returned from
Selection. It follows that $f_{j}(D)\geq
s^{\prime}-\frac{5}{\varepsilon}\log(k/\beta\delta)\geq
s-\frac{5}{\varepsilon}\log(k\beta/\delta)\geq
f_{i^{*}}(D)-\frac{5}{\varepsilon}\log(k/\beta\delta)$, as desired. ∎

##### Stable Selection.

Suppose $\mathcal{F}$ is a function family. For any given dataset $D$, sort
functions in $\mathcal{F}$ by decreasing order of $f(D)$. Namely, write
$\mathcal{F}=\\{f_{1},f_{2},\dots,f_{m}\\}$ so that $f_{1}(D)\geq
f_{2}(D)\geq\dots\geq f_{m}(D)$. Recall that we have defined the $k$-th gap of
$D$ on $\mathcal{F}$ as $G_{k}(D,\mathcal{F})=f_{1}(D)-f_{k+1}(D)$. We prove
Theorem 8, restated below.

Reminder of Theorem 8. For any $k\geq 1$ and $\beta\in(0,1)$, there is an
$(\varepsilon,\delta)$-DP algorithm $\mathcal{A}$ that holds a dataset $D$ and
achieves the following. For any $1$-Lipschitz function family $\mathcal{F}$,
suppose $G_{k}(D,\mathcal{F})\geq\frac{10}{\varepsilon}\log(k/\delta\beta)$.
Then, with probability at least $1-\beta$, $\mathcal{A}$ selects a function
$f\in\mathcal{F}$ such that

$f(D)\geq\max_{f^{*}\in\mathcal{F}}\\{f^{*}(D)\\}-O(\frac{1}{\varepsilon}\log(k/\delta\beta)).$

###### Proof.

Let $\varepsilon^{\prime}=\varepsilon/3$. Given
$\mathcal{F}=\\{f_{1},\dots,f_{m}\\}$, $k\geq 1$ and the dataset $D$, let
$Q(D)$ be the $(k+1)$-th largest score $f_{i}(D)$ among
$\\{f_{i}(D)\\}_{i\in[m]}$. We define a list of mechanisms
$M_{1},\dots,M_{m}$, where $M_{i}(D)$ just returns index $i$ with score
$s_{i}=\max(f_{i}(D)-Q(D),0)+\mathbf{TLap}(\varepsilon^{\prime},\frac{\beta\delta}{10k})$.
We initialize Algorithm 1 with $\gamma=1$, and call Selection with
$(k=m,\tau=\lceil\frac{2}{\beta}\rceil,M_{1},\dots,M_{m})$ to select an index
$i^{*}$ with the largest score. Then we output $i^{*}$.

To see the utility, let $j^{*}=\arg\max_{j\in[m]}f_{j}(D)$. If
$G_{k}(D,\mathcal{F})\geq 10\log(k/\delta\beta)$. It follows that
$f_{j}(D)-Q(D)\geq 10\log(k/\delta\beta)$. By our choice of $\tau$, with
probability at least $1-\beta$, $M_{J^{*}}$ produces at least one pair
$(j^{*}s_{j^{*}})$ with $s_{j^{*}}\geq f_{j^{*}}(D)-Q(D)$. We condition on
this event. Let $i^{*}$ be the index of returned by the algorithm. Since
$(j^{*},s_{j^{*}})$ is in the candidate set, it follows that
$\max(f_{i^{*}}(D)-Q(s),0)\geq
f_{j^{*}}(D)-Q(D)-\frac{1}{\varepsilon^{\prime}}\log(k/\delta\beta)>0$.
Therefore, $f_{i^{*}}(D)\geq
f_{j^{*}}(D)-\frac{2}{\varepsilon^{\prime}}\log(k/\delta\beta)$, as desired.

Now we prove the privacy bound. Fix $D,D^{\prime}$ to be two neighboring
inputs. We first observe that $|Q(D)-Q(D^{\prime})|\leq 1$. For every
$i\in[m]$, consider $M_{i}(D)$ and $M_{i}(D^{\prime})$. There three cases:

  * Case $1$.

Both $f_{i}(D)>Q(D)$ and $f_{i}(D^{\prime})>Q(D^{\prime})$. Then it follows
that $|(f_{i}(D)-Q(D))-(f_{i}(D^{\prime})-Q(D^{\prime}))|\leq 2$. Therefore,
$M_{i}(D)$ and $M_{i}(D^{\prime})$ are
$(\varepsilon^{\prime},\frac{\delta\beta}{5k})$-indistinguishable (in the DP
sense).

  * Case $2$.

$f_{i}(D)>Q(D)$ but $f_{i}(D^{\prime})\leq Q(D^{\prime})$. Still, it is true
that
$|(f_{i}(D)-Q(D))-0|\leq|(f_{i}(D)-Q(D))-(f_{i}(D^{\prime})-Q(D^{\prime}))|\leq
2$. Therefore, $M_{i}(D)$ and $M_{i}(D^{\prime})$ are
$(\varepsilon^{\prime},\frac{\delta\beta}{5k})$-indistinguishable. The case
that $f_{i}(D)\leq Q(D)$ but $f_{i}(D^{\prime})>Q(D^{\prime})$ is similar.

  * Case $3$.

Both $f_{i}(D)\leq Q(D)$ and $f_{i}(D^{\prime})\leq Q(D^{\prime})$. Then it
follows that $M_{i}(D)$ and $M_{i}(D^{\prime})$ are
$(\varepsilon^{\prime},0)$-indistinguishable.

By our definition of $Q(D)$, there are at most $2k$ indices $i\in[m]$ that
belong to Cases 1 and 2. Therefore, by Theorem 1, the whole algorithm is
$(3\varepsilon^{\prime},\tau\frac{\delta\beta\cdot 2k}{5k})$-DP. Since
$\tau=2/\beta$ and $\varepsilon^{\prime}=\varepsilon/3$, it follows that the
algorithm is $(\varepsilon,\delta)$-DP. ∎

##### The advantage of non-random search.

Looking into the proof of Theorems 7 and 8, we can find that both of them work
by selecting from a large number of candidates $(M_{1},\dots,M_{m})$. Since
the number of candidates is huge, we need to add truncated Laplace noises to
balance between privacy and utility. Consequently, for each $i\in[m]$, the
best we can say about $M_{i}$ is that it only satisfies
$(\varepsilon,\delta_{i})$-DP with $\delta_{i}>0$. Fortunately, fixing two
neighboring inputs $D,D^{\prime}$, we can compare $M_{i}(D)$ with
$M_{i}(D^{\prime})$ for every $i\in[m]$, and prove that the $\delta_{i}$
parameters add up to at most $O(k)$. Since our private selection considers
each mechanism separately, we can bound the overall probability of privacy
failure (i.e., $\delta$) easily. If one were to use the Liu-Talwar framework
to solve the stable selection problem, then one needs to bound the privacy
failure probability very carefully (perhaps via an advanced concentration
inequality).

##  4 Improved Sparse Vector Technique

In this section, we present our improved sparse vector algorithm, and apply it
to improve the private multiplicative weight update algorithm.

###  4.1 The Repetitive SVT

Before showing the algorithm, we set up some pieces of notation. In SVT, we
want to answer queries of the form
$f_{i}(D)\stackrel{{\scriptstyle?}}{{\leq}}t$, where $f_{i}(D)$ is a function
of sensitivity $\Delta$.

We formulate a private algorithm $U_{\varepsilon}(f_{i},t)$ to test the
hypothesis $f_{i}(D)\lessapprox t$ privately. $U_{\varepsilon}(f_{i},t)$
computes $\hat{f}_{i}(D)=f_{i}(D)+\mathbf{Lap}(\Delta/\varepsilon)$, returns
$\top$ if $\hat{f}_{i}(D)\geq t$, and returns $\perp$ otherwise. It is easy to
see that $U_{\varepsilon}(f_{i},t)$ is $(\varepsilon,0)$-DP for every
sensitivity-$1$ function $f_{i}$. For our purpose, we also need a private
algorithm to test lower bounds of $f_{i}(D)$. Let $d>0$ be a parameter. We
design a private algorithm $V_{d,\varepsilon}(f_{i},t)$ to test
$f_{i}(D)\gtrapprox t-d$. $V_{d,\varepsilon}(f_{i},t)$ computes
$\hat{f}_{i}(D)=f_{i}(D)+\mathbf{Lap}(\Delta/\varepsilon)$, returns $\top$ if
$\hat{f}_{i}(D)\leq t-d$, and returns $\perp$ otherwise.

##### The algorithm.

The following shows our improved SVT algorithm, which we call the Repetitive
SVT. As we have discussed in Section 1.5, it works by alternating the testing
of two hypotheses $U_{\varepsilon}(f_{i},t)$ and $V_{d,\varepsilon}(f_{i},t)$.
Here, $U_{\varepsilon}(f_{i},t)$ tests the truthfulness of
$f_{i}(D)\lessapprox t$. If $U_{\varepsilon}(f_{i},t)$ outputs $\top$, then we
say the test is “failed”, and the hypothesis $f_{i}(D)\lessapprox t$ is
“refuted”, otherwise we say the test passes. Similarly,
$V_{d,\varepsilon}(f_{i},t)$ tests the validity of $f_{i}(D)\gtrapprox t-d$.

Input: Parameters $\varepsilon\in(0,1),\gamma>0,d>0,k,\tau\in\mathbb{N}$.
Private input $D\in{\mathcal{X}}^{n}$.

1 initialize  __:

2 Initialize Algorithm 1 with $\gamma$.

3

4while  _$c <k$_ do

5 Receive a query $(f_{i},t)$ // We want to test whether $f_{i}(D)\lessapprox
t$

6 $D\leftarrow U_{\varepsilon}$ // $D$ will alternate between
$U_{\varepsilon}$ and $V_{d,\varepsilon}$

7 while  _True_ do

8 $\mathsf{success}\leftarrow 1$

9 for  _$i=1,\dots,\tau$_ do // Test $D$ independently for $\tau$ times

10 $\Gamma\leftarrow\textnormal{{Test}}(D(f_{i},t))$ // ‘‘Test’’ is the
procedure in Algorithm 1

11 if  _$\Gamma=\top$_ then

12 $\mathsf{success}\leftarrow 0$

13 break

14

15

16 if  _$\mathsf{success}=1$_ then // Passed all of $\tau$ tests

17 break

18

19 else // Failed one test; switch to test the other direction

20 $c\leftarrow c+1$

21 if  _$c=k$_ then

22 HALT the algorithm

23

24 if  _$D=U_{\varepsilon}$_ then

25 $D\leftarrow V_{d,\varepsilon}$

26

27 else

28 $D\leftarrow U_{\varepsilon}$

29

30

31

32 if  _$D=U_{\varepsilon}$_ then

33 Output $\perp$ // Report $f_{i}(D)\lessapprox t$

34

35 else

36 Output $\top$ // Report $f_{i}(D)\gtrapprox t-d$

37

38

Algorithm 3 The Repetitive SVT

###  4.2 Analysis

In this section, we analyze the privacy and utility properties of Algorithm 3.
The privacy follows as a direct corollary of Theorem 2.

######  Lemma 3.

Algorithm 3 is $((2k+\gamma)\varepsilon,0)$-DP and
$(O(\gamma\varepsilon+\sqrt{k\log(1/\delta)}\varepsilon),\delta)$-DP for all
$\delta>0$.

Next, we show how to tune parameters $\gamma,d,\tau$ properly to get the best
possible utility. Let the target confidence bound by $1-\beta$. We assume
$\beta\in(2^{-m},1/m)$. The upper bound of $\beta$ is natural, as our
improvement is significant only when $\beta\leq m^{-\omega(1)}$. The lower
bound on $\beta$ is a rather mild restriction.

Suppose our final privacy budget is $(O(\varepsilon),O(\delta))$-DP, and we
need to use Algorithm 3 to process at most $m$ queries. Among them, it is
promised that there are at most $k$ “Above-Threshold” queries. Then, we set

$\begin{cases}\gamma=\frac{\log(20/\beta)}{\log(m)},\\\ \tau=5m^{2},\\\
\varepsilon^{\prime}=\frac{\varepsilon}{\gamma+\sqrt{k\log(1/\delta)}},\\\
k^{\prime}=k+7\frac{\log(1/\beta)}{\log(m)},\\\
d=\frac{10\Delta}{\varepsilon^{\prime}}\log(m).\end{cases}$

We run Algorithm 3 with parameters
$\varepsilon^{\prime},\gamma,d,\tau,k^{\prime}$ to process the queries. Lemma
3 implies that Algorithm 3 with the parameters as specified above enjoys
$(\xi,\delta)$-DP, where

$\xi=O\left(\varepsilon^{\prime}\sqrt{k^{\prime}\log(1/\delta)}\right)\leq
O(\varepsilon).$

We prove the following lemma concerning the utility guarantee of Algorithm 3.

######  Lemma 4.

For the parameters as stated above. With probability $1-\beta$, Algorithm 3
achieves the following utility guarantee.

  * •

For every query $(f_{i},t)$ that received a $\perp$ response, it holds that
$f_{i}(D)\leq t$.

  * •

For every query $(f_{i},t)$ that received a $\top$ response, it holds that
$f_{i}(D)\geq t-d$.

  * •

Either Algorithm 3 processes all $m$ queries and halts, or it halts earlier.
In the latter case, Algorithm 3 must has outputted at least $k$ $\top$
responses before halting.

###### Proof.

Let $p$ denote the “pass” probability sampled during the initialization. It
follows that with probability at least $1-\beta/20$, we have
$p\geq\frac{1}{m}$. We condition on this event.

We begin with verifying the first two bullets. Note that if a $\perp$ response
is returned on a query $(f_{i},t)$, it implies that the algorithm passed
$\textnormal{{Test}}(U_{\varepsilon^{\prime}}(f_{i},t))$ for $\tau=5m^{2}$
times. Suppose $f_{i}(D)>t$. Then, the probability that one execution of
$\textnormal{{Test}}(U_{\varepsilon^{\prime}}(f_{i},t))$ passes is at most
$1-p\cdot\frac{1}{2}\leq 1-\frac{1}{2m}$. Therefore, the probability that all
of the $\tau$ independent calls to
$\textnormal{{Test}}(U_{\varepsilon^{\prime}}(f_{i},t))$ pass is at most
$(1-\frac{1}{2m})^{\tau}\leq 2^{-2m}$. If this extremely-unlikely event does
happen, then we say that a fatal error happens. Since the batch test (The
“for” loop starting at Line 9) is run for at most $m+k^{\prime}$ times. The
probability that there exists a fatal error is at most
$2^{-2m}\cdot(m+k^{\prime})\leq\beta/20$. Similarly, we can show that up to
failure probability $\beta/20$, the second bullet holds.

It remains to verify the last bullet. First, note that given a query
$(f_{i},t)$, we know that either $f_{i}(D)\leq t-\frac{d}{2}$ or
$f_{i}(D)>t-\frac{d}{2}$. During the execution of Algorithm 3, we say that a
“mistake” happens, if one of the following events happens.

  * •

$f_{i}(D)\leq t-\frac{d}{2}$, but Algorithm 3 fails a batch of
$\textnormal{{Test}}(U_{\varepsilon^{\prime}}(f_{i},t))$ tests.

  * •

$f_{i}(D)\geq t-\frac{d}{2}$, but Algorithm 3 fails a batch of
$\textnormal{{Test}}(V_{d,\varepsilon^{\prime}}(f_{i},t))$ tests.

We now show that a mistake happens with low probability. We consider the first
type of mistake. The second type can be argued similarly.

Recall that $d=\frac{10\Delta}{\varepsilon^{\prime}}\log(m)$. Given
$f_{i}(D)\geq t-\frac{d}{2}$, we know that one call to
$\textnormal{{Test}}(U_{\varepsilon^{\prime}}(f_{i},t))$ passes with
probability at least $1-\frac{1}{m^{5}}$. Hence, the probability that all the
$\tau$ calls pass is at least $1-\frac{5}{m^{3}}$. Therefore, the probability
that a mistake happens is at most $\frac{5}{m^{3}}$.

Let $R=\lceil\frac{3\log(1/\beta)}{\log(m)}\rceil$. Since Algorithm 3 runs the
batch test for at at most $(k+m)$ times, the probability that the number of
mistakes is larger than $R$ is at most

$(m+k)^{R}\cdot\left(\frac{5}{m^{3}}\right)^{R}\leq\left(\frac{10}{m^{2}}\right)^{R}\leq\beta/10.$

This bound can be verified by union-bounding over all $R$-subsets of $[m+k]$.

We condition on the event that Algorithm 3 makes no more than $R$ mistakes.
Now, suppose that Algorithm 3 halts before processing all the queries. For
each $i\in[m]$, let $c_{i}\geq 1$ be the number of batch tests that Algorithm
3 runs for the $i$-th query. If the algorithm halts before the $i$-th query,
set $c_{i}=1$. Then, it follows that

$\\#\\{\text{mistakes}\\}=\sum_{i=1}^{m}\lfloor\frac{c_{i}-1}{2}\rfloor\leq
R.$

Since Algorithm 3 halts earlier, we have

$k^{\prime}=\sum_{i=1}^{m}(c_{i}-1).$

We observe that

$\displaystyle\\#\\{\text{$\top$ responses}\\}$
$\displaystyle=\sum_{i=1}^{m}\mathbbm{1}\\{c_{i}\bmod 2=0\\}$
$\displaystyle=\sum_{i=1}^{m}(c_{i}-1)-2\lfloor\frac{c_{i}-1}{2}\rfloor$
$\displaystyle=\left(\sum_{i=1}^{m}(c_{i}-1)\right)-2\left(\sum_{i=1}^{m}\lfloor\frac{c_{i}-1}{2}\rfloor\right)$
$\displaystyle\geq k^{\prime}-2R$ $\displaystyle\geq k,$

as desired. ∎

To conclude, we review the confidence-accuracy tradeoff implied by Lemma 4.
Fix the privacy budget to be $(\varepsilon,\delta)$. Suppose that one needs to
identify $k$ significant queries from a total of $m$ queries, and one desires
$(1-\beta)$ confidence bound. Then, the additive error bound that Algorithm 3
can offer is

$d\leq
O\left(\Delta\frac{\sqrt{k\log(1/\delta)}\log(m)+\log(1/\beta)}{\varepsilon}\right).$

######  Remark 2.

If we want to have a pure-DP privacy guarantee, then we can repeat the
analysis above with parameter setup as

$\begin{cases}\gamma=\frac{\log(20/\beta)}{\log(m)},\\\ \tau=5m^{2},\\\
\varepsilon^{\prime}=\frac{\varepsilon}{\gamma+k},\\\
k^{\prime}=k+7\frac{\log(1/\beta)}{\log(m)},\\\
d=\frac{10\Delta}{\varepsilon^{\prime}}\log(m).\end{cases}$

Fixing the privacy parameters $\varepsilon$ and $k,m$, the tradeoff between
error and confidence is

$d\leq O\left(\Delta\frac{k\log(m)+\log(1/\beta)}{\varepsilon}\right).$

###  4.3 Applications

In this section, we apply Algorithm 3 to improve the private multiplicative
weight update algorithm and the sample complexity of adaptive data analysis.

####  4.3.1 Private Multiplicative Weight Update

It is instructive to review how the private multiplicative weight update
algorithm [HR10] works. Roughly speaking, the private MWU algorithm maintains
a publicly-known “approximation” distribution $h:{\mathcal{X}}\to[0,1]$ to the
uniform distribution over the private input $D$. Given a query
$f_{i}:{\mathcal{X}}\to[0,1]$, the algorithm uses $\mathbb{E}_{x\sim
h}[f_{i}(x)]$ as a “guess” for $\mathbb{E}_{x\sim D}[f_{i}(x)]$. Then it
defines a function $g_{i}(D)=\left|\mathbb{E}_{x\sim
D}[f_{i}(x)]-\mathbb{E}_{x\sim h}[f_{i}(x)]\right|$, and uses SVT to privately
check if $g_{i}(D)\lessapprox\alpha$, where $\alpha$ is the desired accuracy
bound. Querying SVT yields two possible outcomes:

  * •

The SVT algorithm returns that $g_{i}(D)\lessapprox\alpha$. In this case, the
algorithm answers this query with $\mathbb{E}_{x\sim h}[f_{i}(x)]$, without
paying the privacy loss.

  * •

The SVT algorithm returns that $g_{i}(D)\gtrapprox\alpha$. Then, the algorithm
answers this query by releasing $\mathbb{E}_{x\sim
D}[f_{i}(x)]+\mathbf{Lap}(1/n\varepsilon^{\prime})$. After that, the algorithm
also updates the current distribution $h$ according to the MWU rule. In this
case, we call the $i$-th round an “update round”.

It is shown in [HR10] that the number of update rounds is no more than
$k=\frac{\log|{\mathcal{X}}|}{\alpha^{2}}$. Therefore, if we desire the final
algorithm to be $(\varepsilon,\delta)$-DP, we can afford to use
$(\varepsilon^{\prime},0)$-DP implementation of the sparse vector technique
and the Laplace mechanism with
$\varepsilon^{\prime}=\frac{\varepsilon}{\sqrt{k\log(1/\delta)}}$. The
standard calculation shows that, the magnitudes of Laplace noises used in the
algorithm are all bounded by $O(\frac{\log(m/\beta)}{\varepsilon^{\prime}n})$
with probability $1-\beta$. Therefore, the best accuracy bound we can hope for
is

$\alpha\approx\Theta\left(\frac{\log(m/\beta)}{\varepsilon^{\prime}n}\right)=\Theta\left(\frac{\sqrt{k\log(1/\delta)}\log(m/\beta)}{\varepsilon
n}\right)=\Theta\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m/\beta)}{\alpha\varepsilon
n}\right).$

This completes the proof sketch for Theorem 9. For reader’s convenience, we
recall the statement below.

Reminder of Theorem 9. For every $\varepsilon,\delta\in(0,1)$, there is an
$(\varepsilon,\delta)$-DP algorithm that answers $m$ adaptively chosen linear
queries with the following utility guarantee. Let $(\tilde{f}_{i})_{i\in[m]}$
denote the outputs of $\mathcal{A}$. For every $\beta\in(0,1)$, with
probability $1-\beta$ we have that
$\max_{i\in[m]}\\{|\tilde{f}_{i}-\mathbb{E}_{j\in[n]}[f_{i}(x_{j})]|\\}\leq\alpha_{\beta}$,
where

${\alpha_{\beta}}^{2}\leq
O\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m/\beta)}{n\varepsilon}\right).$

##### Our improvement.

As we have seen in the last subsection, using our improved SVT (Algorithm 3),
we can improve the confidence-accuracy tradeoff of SVT to

$\alpha\leq
O\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m)}{n\varepsilon\alpha}+\frac{\log(1/\beta)}{n\varepsilon}\right).$

However, to yield the improved private MWU algorithm, there is one remaining
issue. That is, during each update round, we need to use the Laplace mechanism
to come up with an estimation of $\mathbb{E}_{x\sim D}[f_{i}(x)]$. With a
small-but-noticeable probability, the Laplace noise
$\mathbf{Lap}(1/n\varepsilon^{\prime})$ can be very large so that the
estimation given by the Laplace mechanism is erroneous. We can resolve the
issue by utilizing Algorithm 3. Namely, after getting the estimation of
$\mathbb{E}_{x\sim D}[f_{i}(x)]$ from the Laplace mechanism, we ask the
repetitive SVT to test if the estimation is accurate. If it turns out to be
inaccurate, we reject the current estimation and request a new one from the
Laplace mechanism. Although this process consumes privacy budget, we can
nevertheless show that the number of such “rejections” is small with
overwhelmingly high probability, using an argument similar as the proof of
Lemma 4.

Another point worth mentioning is that the privacy analysis for Algorithm 3 is
done for the whole execution. Therefore, when we use it as a subroutine in the
private MWU algorithm, we are _concurrently_ running it with the Laplace
mechanism. To argue the privacy of the algorithm, we need to use the
concurrent composition theorems of DP (see, e.g., [VW21, VZ22, Lyu22]).

To summarize, we have shown how we can arrive at the following improved
private MWU algorithm.

Reminder of Theorem 11. There is an absolute constant $C>0$ such that the
following is true. For every $\varepsilon,\delta\in(0,1)$, $m\in\mathbb{N}$
and $\beta\geq 2^{-m}$, there exists

$\alpha\leq
C\cdot\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m)}{n\varepsilon\cdot\alpha}+\frac{\log(1/\beta)}{n\varepsilon}\right)$

and an $(\varepsilon,\delta)$-DP algorithm that answers $m$ adaptively chosen
linear queries such that, with probability $1-\beta$, we have
$\max_{i\in[m]}\\{|\tilde{f}_{i}-\mathbb{E}_{j\in[n]}[f_{i}(x_{j})]|\\}\leq\alpha$.

####  4.3.2 Adaptive Data Analysis

The generalization property of DP [DFH+15, BNS+16a] provides a connection
between privacy-preserving algorithms and algorithms for adaptive data
analysis. In particular, an $(\varepsilon,\delta)$-DP algorithm that answers
$m$ linear queries with additive error $\alpha$ and confidence $1-\beta$,
implies an $(\alpha^{\prime},\beta^{\prime},m)$-accurate algorithm for
adaptive data analysis with linear queries, where
$\alpha^{\prime}=O(\alpha+\varepsilon)$ and
$\beta^{\prime}=O(\beta+\delta/\varepsilon)$.

Applying this generic connection to Theorem 9 proves Theorem 10. We now apply
the connection with Theorem 11 to prove Theorem 12, restated below.

Reminder of Theorem 12. For every finite universe ${\mathcal{X}}$, every
$m\geq 1$ and $\alpha\in(0,1),\beta\geq 2^{-m}$, there is an
$(\alpha,\beta,m)$-accurate adaptive data analysis algorithm with sample
complexity

$n\leq
O\left(\min\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\beta)}}{\alpha^{3}},\frac{\log|X|}{\alpha^{4}}\right)\log
m+\frac{\log(1/\beta)}{\alpha^{2}}\right).$

Suppose we aim for an $(\alpha,\beta,m)$-accurate algorithm. Letting
$k=\frac{\log|{\mathcal{X}}|}{\alpha^{2}}$, Theorem 11 and the generalization
property imply that this is possible as long as the inequality below is
satisfied

$\alpha\geq
C^{\prime}\cdot\left(\frac{\sqrt{\log|{\mathcal{X}}|\log(1/\delta)}\log(m)}{n\varepsilon\cdot\alpha}+\frac{\log(1/\beta)}{n\varepsilon}\right)$

for some absolute constant $C^{\prime}>0$. Solving for $n$ yields that

$n\geq C^{\prime}\left(\frac{\sqrt{k\log(1/\beta)}}{\alpha^{2}}\log
m+\frac{\log(1/\beta)}{\alpha^{2}}\right).$

Therefore, we can choose $n$ to be as small as

$O\left(\frac{\sqrt{k\log(1/\beta)}}{\alpha^{2}}\log
m+\frac{\log(1/\beta)}{\alpha^{2}}\right).$

In Theorem 12, we also claimed an incomparable bound

$n\leq O\left(\frac{k}{\alpha^{2}}\log
m+\frac{\log(1/\beta)}{\alpha^{2}}\right).$

This can achieved using a pure-DP version of Theorem 11, which can be derived
from the pure-DP version of Algorithm 3 (see Remark 2).

##### Acknowledgements

Edith Cohen is partially supported by Israel Science Foundation (grant no.
1595/19). Uri Stemmer is partially supported by the Israel Science Foundation
(grant 1871/19) and by Len Blavatnik and the Blavatnik Family foundation.

## References

  * [BDRS18] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke.  Composable and versatile privacy via truncated CDP.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 74–86. ACM, 2018.
  * [BKSW21] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu.  Private hypothesis selection.  IEEE Trans. Inf. Theory, 67(3):1981–2000, 2021.
  * [BNS+16a] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman.  Algorithmic stability for adaptive data analysis.  In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 1046–1059. ACM, 2016.
  * [BNS16b] Amos Beimel, Kobbi Nissim, and Uri Stemmer.  Private learning and sanitization: Pure vs. approximate differential privacy.  Theory Comput., 12(1):1–61, 2016.
  * [BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan.  Fingerprinting codes and the price of approximate differential privacy.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 1–10, New York, NY, USA, 2014. Association for Computing Machinery.
  * [DDR20] Jinshuo Dong, David Durfee, and Ryan Rogers.  Optimal differential privacy composition for exponential mechanisms.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2597–2606. PMLR, 13–18 Jul 2020\.
  * [DFH+15] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth.  Preserving statistical validity in adaptive data analysis.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 117–126, 2015.
  * [DK20] Yuval Dagan and Gil Kur.  A bounded-noise mechanism for differential privacy.  CoRR, abs/2012.03817, 2020.
  * [DMNS16] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.  Calibrating noise to sensitivity in private data analysis.  J. Priv. Confidentiality, 7(3):17–51, 2016.
  * [DNR+09] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan.  On the complexity of differentially private data release: Efficient algorithms and hardness results.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 381–390, New York, NY, USA, 2009. Association for Computing Machinery.
  * [DR14] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.
  * [DR19] David Durfee and Ryan M. Rogers.  Practical differentially private top-k selection with pay-what-you-get composition.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3527–3537, 2019.
  * [DRV10] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan.  Boosting and differential privacy.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51–60. IEEE Computer Society, 2010.
  * [GDGK20] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar.  Tight analysis of privacy and utility tradeoff in approximate differential privacy.  In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 89–99. PMLR, 2020.
  * [GKM20] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi.  Differentially private clustering: Tight approximation ratios.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [GKM21] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi.  On avoiding the union bound when answering multiple differentially private queries.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2133–2146. PMLR, 2021.
  * [GLM+10] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar.  Differentially private combinatorial optimization.  In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1106–1125. SIAM, 2010.
  * [GZ21] Arun Ganesh and Jiazheng Zhao.  Privately Answering Counting Queries with Generalized Gaussian Mechanisms.  In Katrina Ligett and Swati Gupta, editors, 2nd Symposium on Foundations of Responsible Computing (FORC 2021), volume 192 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [HR10] Moritz Hardt and Guy N. Rothblum.  A multiplicative weights mechanism for privacy-preserving data analysis.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 61–70. IEEE Computer Society, 2010.
  * [KLM+20] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer.  Privately learning thresholds: Closing the exponential gap.  In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2263–2285. PMLR, 2020.
  * [KMS21] Haim Kaplan, Yishay Mansour, and Uri Stemmer.  The sparse vector technique, revisited.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2747–2776. PMLR, 2021.
  * [LSL17] Min Lyu, Dong Su, and Ninghui Li.  Understanding the sparse vector technique for differential privacy.  Proc. VLDB Endow., 10(6):637–648, 2017.
  * [LT19] Jingcheng Liu and Kunal Talwar.  Private selection from private candidates.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 298–309. ACM, 2019.
  * [Lyu22] Xin Lyu.  Composition theorems for interactive differential privacy, 2022.
  * [Mir17] Ilya Mironov.  Rényi differential privacy.  In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pages 263–275. IEEE Computer Society, 2017.
  * [MS20] Ryan McKenna and Daniel Sheldon.  Permute-and-flip: A new mechanism for differentially private selection.  In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc.
  * [MT07] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 94–103. IEEE Computer Society, 2007.
  * [MV18] Jack Murtagh and Salil P. Vadhan.  The complexity of computing the optimal composition of differential privacy.  Theory Comput., 14(1):1–35, 2018.
  * [OV13] Sewoong Oh and Pramod Viswanath.  The composition theorem for differential privacy.  CoRR, abs/1311.0776, 2013.
  * [PS22] Nicolas Papernot and Thomas Steinke.  Hyperparameter tuning with Rényi differential privacy.  In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
  * [QSZ21] Gang Qiao, Weijie J. Su, and Li Zhang.  Oneshot differentially private top-k selection.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8672–8681. PMLR, 2021.
  * [RR10] Aaron Roth and Tim Roughgarden.  Interactive privacy via the median mechanism.  In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 765–774. ACM, 2010.
  * [SU16] Thomas Steinke and Jonathan R. Ullman.  Between pure and approximate differential privacy.  J. Priv. Confidentiality, 7(2), 2016.
  * [SU17] Thomas Steinke and Jonathan Ullman.  Tight lower bounds for differentially private selection.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 552–563, 2017.
  * [SU20] Thomas Steinke and Jonathan Ullman.  Open problem - avoiding the union bound for multiple queries.  DifferentialPrivacy.org, 10 2020.  https://differentialprivacy.org/open-problem-avoid-union/.
  * [Vad17] Salil P. Vadhan.  The complexity of differential privacy.  In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 347–450. Springer International Publishing, 2017.
  * [vEH14] Tim van Erven and Peter Harremoës.  Rényi divergence and Kullback-Leibler divergence.  IEEE Trans. Inf. Theory, 60(7):3797–3820, 2014.
  * [VW21] Salil Vadhan and Tianhao Wang.  Concurrent composition of differential privacy.  In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography, pages 582–604, Cham, 2021. Springer International Publishing.
  * [VZ22] Salil Vadhan and Wanrong Zhang.  Concurrent composition theorems for differential privacy, 2022.
  * [ZW20] Yuqing Zhu and Yu-Xiang Wang.  Improving sparse vector technique with Renyi differential privacy.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.

##  Appendix A Missing Proofs

###  A.1 Missing Proofs in Section 2

In this section, we show the proof of Lemmas 1 and 2.

####  A.1.1 Preliminaries

Recall we have defined the $\alpha$-order Rényi divergence of $P$ from $Q$ as

$D_{\alpha}(P\|Q):=\frac{1}{\alpha-1}\log\left(\sum_{x\in
X}P(x)\left(\frac{P(x)}{Q(x)}\right)^{\alpha-1}\right).$

The max-divergence is defined as

$D_{\infty}(P\|Q):=\log(\max_{x}\\{P(x)/Q(x)\\}).$

We need a composition property of Rényi divergence. Suppose $P,Q$ are
distributions on $(x,y)\in X\times Y$. For each $x\in X$, let $P_{x}$ denote
the conditional distribution of $y\in(x,y)\sim P$ conditioning on $x$. Also
let $P^{X}$ denote the marginal distribution of $P$ on $X$. Also define
similar pieces of notation for $Q$. Then, we have

$D_{\alpha}(P^{X}\|Q^{X})+\inf_{x\in X}\\{D_{\alpha}(P_{x}\|Q_{x})\\}\leq
D_{\alpha}(P\|Q)\leq D_{\alpha}(P^{X}\|Q^{X})+\sup_{x\in
X}\\{D_{\alpha}(P_{x}\|Q_{x})\\}.$

####  A.1.2 Proofs of Lemmas 1 and 2

We will analyze the $0$-favored coin-flipping mechanism. For readers’
convenience, we restate it below.

Input: An input bit $b\in\\{0,1\\}$, a privacy parameter
$\varepsilon\in(0,1)$, an integer $k\geq 1$.

1 initialize  __:

2 $c\leftarrow 0$

3

4while  _$c <k$_ do

5 Receive a query $(p,q)\in[0,1]^{2}$, promised that $0\leq q\leq p\leq
e^{\varepsilon}q$ and $(1-p)\leq e^{\varepsilon}(1-q)$

6 if  _$b=0$_ then

7 Sample $r\sim\mathbf{Ber}(p)$

8

9 else

10 Sample $r\sim\mathbf{Ber}(q)$

11

12 if  _$r=1$_ then

13 $c\leftarrow c+1$

14

15 Output $r$

16

Algorithm 4 (Restate of Algorithm 2) The $0$-favored coin-flipping mechanism.

Reminder of Lemma 1. Consider Algorithm 4. Fix $\mathcal{A}$ to be an
arbitrary adversary interacting with Algorithm 4. Let $P,Q$ denote the
distributions of the interaction between $\mathcal{A}$ and Algorithm 4 when
the sensitive bit is $0$ or $1$, respectively. Then, for any
$\alpha\in(1,\infty)$, we have $D_{\infty}(P\|Q)\leq k\varepsilon$.

###### Proof.

We first consider the case that $k=1$ and that the adversary is deterministic.
In this case, note that the algorithm always outputs $0$ before a final round,
in which it outputs a $1$ and halts. Therefore, any deterministic adversary
strategy can be described by a list of probability pairs
$(p_{1},q_{1}),(p_{2},q_{2}),\dots$. To interact with the algorithm, the
adversary just keeps sending the next pair in the list, until it gets a
$1$-response from the algorithm.

Hence, the distribution $P$ and $Q$ can be described by two distributions on
positive integers. Where $P=i$ denotes the outcome that the algorithm halts
after the $i$-th round when it holds $b=0$. It is easy to see that

$\Pr[P=i]=\prod_{j<i}(1-p_{j})p_{i},$

Similarly, $Q=i$ denotes the outcome that the algorithm halts after the $i$-th
round when it holds $b=1$. We have

$\Pr[Q=i]=\prod_{j<i}(1-q_{j})q_{i}.$

One can then write

$D_{\infty}(P\|Q)=\log\left(\sup_{i\geq
1}\left\\{\frac{\Pr[P=i]}{\Pr[Q=i]}\right\\}\right).$

For every $i\geq 1$, it is easy to see

$\Pr[P=i]=\sum_{j<i}(1-p_{j})p_{i}\leq\prod_{j<i}(1-q_{j})p_{i}\leq
e^{\varepsilon}\sum_{j<i}(1-q_{j})q_{i}=e^{\varepsilon}\Pr[Q=i].$

This completes the proof for the base case.

For the case that the adversary is randomized, we argue as follows. For any
possible random coins of the adversary $r$, let $P_{r},Q_{r}$ denote the
distributions conditioning on $r$. We have

$D_{\infty}(P_{r}\|Q_{r})\leq\varepsilon,$

because the adversary becomes deterministic conditioning on $r$. Hence, we
have

$D_{\infty}(P\|Q)\leq\sup_{r}\left\\{D_{\infty}(P_{r}\|Q_{r})\right\\}\leq\varepsilon$

as desired.

For the case of $k=c>1$, we can think of the interaction as a concatenation of
at most $c$ executions of the algorithm with $k=1$ each. The proposition
follows from the composition property of max-divergence. ∎

Reminder of Lemma 2. Consider the same setup as in Lemma 1. For any
$\alpha\in(1,\infty)$, we have $D_{\alpha}(P\|Q)\leq 3k\alpha\varepsilon^{2}$.

###### Proof.

We assume that $\alpha\varepsilon<\frac{1}{3}$, as otherwise the conclusion
follows easily from Lemma 1.

Again we start by considering the case that $k=1$ and that the adversary is
deterministic. We inherit the notation $(p_{1},q_{1}),(p_{2},q_{2}),\dots$
from the proof of Lemma 1. Recall

$\Pr[P=i]=\prod_{j<i}p_{j}(1-p_{i}),$

and

$\Pr[Q=i]=\prod_{j<i}q_{j}(1-q_{i}).$

Then, we have

$\displaystyle
e^{(\alpha-1)D_{\alpha}(P\|Q)}=\sum_{i=1}^{\infty}\Pr[P=i]\left(\frac{\Pr[P=i]}{\Pr[Q=i]}\right)^{\alpha-1}.$
(3)

We claim the following.

######  Claim 1.

Assume $\alpha\varepsilon<1/3$. For every $m\geq 1$, it holds that

$\displaystyle\sum_{i=1}^{m}\Pr[P=i]\left(\frac{\Pr[P=i]}{\Pr[Q=i]}\right)^{\alpha-1}+\Pr[P>m]\left(\frac{\Pr[P>m]}{\Pr[Q>m]}\right)^{\alpha-1}\leq
1+3\alpha(\alpha-1)\varepsilon^{2}.$ (4)

We assume Claim 1 for now and quickly finish the proof of Lemma 2. Given Claim
1, take the limit $m\to\infty$ and plug it into (3):

$e^{(\alpha-1)D_{\alpha}(P\|Q)}=\sum_{i=1}^{\infty}\Pr[P=i]\left(\frac{\Pr[P=i]}{\Pr[Q=i]}\right)^{\alpha-1}\leq
1+3\alpha(\alpha-1)\varepsilon^{2}.$

Taking logarithm on both sides and using $\log(1+x)\leq x$ show that
$D_{\alpha}(P\|Q)\leq 3\alpha\varepsilon^{2}$. This completes the proof for
the base case.

For the case that $k=c>1$, we view the interaction as a sequential composition
of $c$ executions of Algorithm 4 with $k=1$ each, and use the composition
property of Rényi divergence. For the case of randomized adversaries,
conditioning on the random coins of the adversary $r$, the conditional
distributions of the interaction satisfy that

$D_{\alpha}(P_{r}\|Q_{r})\leq 3\alpha k\varepsilon^{2}.$

Then, we have

$D_{\alpha}(P\|Q)\leq\sup_{r}\left\\{D_{\alpha}(P\|Q)\right\\}\leq 3\alpha
k\varepsilon^{2},$

completing the proof777We remark that this first inequality will not be true
if we replace the supremum operator over $r$ with expectation, as $D_{\alpha}$
is not necessarily convex (see [vEH14] for a counterexample).. ∎

In the following, we prove Claim 1.

###### Proof of Claim 1.

We use induction on $m$. For the case of $m=1$, we have

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\Pr[P=1]\left(\frac{\Pr[P=1]}{\Pr[Q=1]}\right)^{\alpha-1}+\Pr[P>1]\left(\frac{\Pr[P>1]}{\Pr[Q>1]}\right)^{\alpha-1}$
$\displaystyle=p_{1}\left(\frac{p_{1}}{q_{1}}\right)^{\alpha-1}+(1-p_{1})\left(\frac{1-p_{1}}{1-q_{1}}\right)^{\alpha-1}.$
(5)

We need the following simple fact. (For a proof, see, e.g. [Mir17, Lemma 1].)

######  Fact 1.

Let $0\leq p,q\leq 1$ be such that

$\max(D_{\infty}(\mathbf{Ber}(p)\|\mathbf{Ber}(q)),D_{\infty}(\mathbf{Ber}(q)\|\mathbf{Ber}(p)))\leq\varepsilon.$

Then,

$e^{(\alpha-1)D_{\alpha}(\mathbf{Ber}(p)\|\mathbf{Ber}(q))}\leq
1+2\alpha(\alpha-1)\varepsilon^{2}.$

By Fact 1, we have

$p_{1}\left(\frac{p_{1}}{q_{1}}\right)^{\alpha-1}+(1-p_{1})\left(\frac{1-p_{1}}{1-q_{1}}\right)^{\alpha-1}\leq
1+2(\alpha-1)\alpha\varepsilon^{2}.$

This verifies the base case for $m=1$. Now suppose Claim 1 is true for
$m-1\geq 1$, we prove for the case of $m$. We have

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\sum_{i=1}^{m}\Pr[P=i]\left(\frac{\Pr[P=i]}{\Pr[Q=i]}\right)^{\alpha-1}+\Pr[P>m]\left(\frac{\Pr[P>m]}{\Pr[Q>m]}\right)^{\alpha-1}$
$\displaystyle=\Pr[P=1]\left(\frac{\Pr[P=1]}{\Pr[Q=1]}\right)^{\alpha-1}+\Pr[P>1]\left(\frac{\Pr[P>1]}{\Pr[Q>1]}\right)^{\alpha-1}\times$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\left(\sum_{i=2}^{m}\Pr[P=i|P>1]\left(\frac{\Pr[P=i|P>1]}{\Pr[Q=i|Q>1]}\right)^{\alpha-1}+\Pr[P>m|P>1]\left(\frac{\Pr[P>m|P>1]}{\Pr[Q>m|Q>1]}\right)^{\alpha-1}\right).$
(6)

We look into the bracket on the third line. Conditioning on $P>1$ (and $Q>1$),
the expression inside the bracket describes a $(m-1)$-round interaction
between the adversary and the algorithm, where the probability pairs are given
by $(p_{2},q_{2}),\dots,(p_{m},q_{m})$. Therefore, by induction hypothesis, it
is subject to the bound given by (4), which allows to bound (6) by

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\sum_{i=1}^{m}\Pr[P=i]\left(\frac{\Pr[P=i]}{\Pr[Q=i]}\right)^{\alpha-1}+\Pr[P>m]\left(\frac{\Pr[P>m]}{\Pr[Q>m]}\right)^{\alpha-1}$
$\displaystyle\leq\Pr[P=1]\left(\frac{\Pr[P=1]}{\Pr[Q=1]}\right)^{\alpha-1}+\Pr[P>1]\left(\frac{\Pr[P>1]}{\Pr[Q>1]}\right)^{\alpha-1}\cdot\left(1+3\alpha(\alpha-1)\varepsilon^{2}\right).$
(7)

Now, depending on whether $p_{1}=\Pr[P=1]$ is large or small, we consider two
cases.

Case 1: $p_{1}\geq\frac{2}{3}$. In this case, we use
$\Pr[P>1]=1-p_{1}\leq\frac{1}{3}$, $\Pr[P>1]\leq\Pr[Q>1]$, and Fact 1 to bound
(7) as

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\Pr[P=1]\left(\frac{\Pr[P=1]}{\Pr[Q=1]}\right)^{\alpha-1}+\Pr[P>1]\left(\frac{\Pr[P>1]}{\Pr[Q>1]}\right)^{\alpha-1}\cdot\left(1+3\alpha(\alpha-1)\varepsilon^{2}\right)$
$\displaystyle=p_{1}\left(\frac{p_{1}}{q_{1}}\right)^{\alpha-1}+(1-p_{1})\left(\frac{1-p_{1}}{1-q_{1}}\right)^{\alpha-1}+(1-p_{1})\left(\frac{1-p_{1}}{1-q_{1}}\right)^{\alpha-1}\cdot
3\alpha(\alpha-1)\varepsilon^{2}$ $\displaystyle\leq
1+2\alpha(\alpha-1)\varepsilon^{2}+(1-p_{1})3\alpha(\alpha-1)\varepsilon^{2}$
$\displaystyle\leq 1+3\alpha(\alpha-1)\varepsilon^{2}.$

Case 2: $p_{1}<\frac{2}{3}$. In this case, write
$\lambda=\log(p_{1}/q_{1})\in[0,\varepsilon]$. We bound (7) as

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\Pr[P=1]\left(\frac{\Pr[P=1]}{\Pr[Q=1]}\right)^{\alpha-1}+\Pr[P>1]\left(\frac{\Pr[P>1]}{\Pr[Q>1]}\right)^{\alpha-1}\cdot\left(1+3\alpha(\alpha-1)\varepsilon^{2}\right)$
$\displaystyle\leq
p_{1}e^{\lambda(\alpha-1)}+(1-p_{1})\left(1-\frac{p_{1}-q_{1}}{1-q_{1}}\right)^{\alpha-1}+(1-p_{1})\cdot
3\alpha(\alpha-1)\varepsilon^{2}$ $\displaystyle\leq
p_{1}e^{\lambda(\alpha-1)}+(1-p_{1})e^{-\frac{p_{1}-q_{1}}{1-q_{1}}(\alpha-1)}+(1-p_{1})\cdot
3\alpha(\alpha-1)\varepsilon^{2},$ (8)

where we used $\Pr[P>1]\leq\Pr[Q>1]$ and $(1-x)^{y}\leq e^{-xy}$ in the second
and third line, respectively.

Then we re-write (8) as

$\displaystyle
p_{1}(e^{\lambda(\alpha-1)}-1)+(1-p_{1})(e^{-\frac{p_{1}-q_{1}}{1-q_{1}}(\alpha-1)}-1)+1+(1-p_{1})\cdot
3\alpha(\alpha-1)\varepsilon^{2}.$ (9)

Now, it is clear that to bound (9) by $3\alpha(\alpha-1)\varepsilon^{2}$, it
suffices to show that

$\displaystyle
p_{1}(e^{\lambda(\alpha-1)}-1)+(1-p_{1})(e^{-\frac{p_{1}-q_{1}}{1-q_{1}}(\alpha-1)}-1)\leq
p_{1}\cdot 3\alpha(\alpha-1)\varepsilon^{2}.$ (10)

We use the basic inequality $e^{x}\leq 1+x+x^{2}$, which is valid for
$x\in(-\infty,1.75]$, to bound (10) as

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
p_{1}(e^{\lambda(\alpha-1)}-1)+(1-p_{1})(e^{-\frac{p_{1}-q_{1}}{1-q_{1}}(\alpha-1)}-1)$
$\displaystyle\leq
p_{1}(\lambda(\alpha-1)+\lambda^{2}(\alpha-1)^{2})+(1-p_{1})\left(-\frac{p_{1}-q_{1}}{1-q_{1}}(\alpha-1)+\frac{(p_{1}-q_{1})^{2}}{(1-q_{1})^{2}}(\alpha-1)^{2}\right).$
(11)

Recall $q_{1}=e^{-\lambda}p_{1}$ and $0\leq\lambda\leq\varepsilon\leq 1/3$,
which implies that

$p_{1}-q_{1}=p_{1}(1-e^{-\lambda})\in\big{(}p_{1}(\lambda-\lambda^{2}),p_{1}\lambda\big{)}.$

We proceed to bound (11) as

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
p_{1}(\lambda(\alpha-1)+\lambda^{2}(\alpha-1)^{2})+(1-p_{1})\left(-\frac{p_{1}-q_{1}}{1-q_{1}}(\alpha-1)+\frac{(p_{1}-q_{1})^{2}}{(1-q_{1})^{2}}(\alpha-1)^{2}\right)$
$\displaystyle=p_{1}\lambda(\alpha-1)+p_{1}\lambda^{2}(\alpha-1)^{2}-\frac{1-p_{1}}{1-q_{1}}(p_{1}-q_{1})(\alpha-1)+\frac{(1-p_{1})}{(1-q_{1})^{2}}(p_{1}-q_{1})^{2}(\alpha-1)^{2}.$
(12)

Observe that

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
p_{1}\lambda(\alpha-1)-\frac{1-p_{1}}{1-q_{1}}(p_{1}-q_{1})(\alpha-1)$
$\displaystyle\leq
p_{1}\lambda(\alpha-1)-(1-\frac{p_{1}-q_{1}}{1-q_{1}})(p_{1}-q_{1})(\alpha-1)$
$\displaystyle\leq
p_{1}\lambda(\alpha-1)-(p_{1}-q_{1})(\alpha-1)+\frac{p_{1}-q_{1}}{1-q_{1}}(p_{1}-q_{1})(\alpha-1)$
$\displaystyle\leq\lambda^{2}p_{1}(\alpha-1)+\frac{p_{1}^{2}}{1-q_{1}}\lambda^{2}(\alpha-1)$
($p_{1}-q_{1}\in(p_{1}\lambda-p_{1}\lambda^{2},p_{1}\lambda)$)
$\displaystyle\leq p_{1}\lambda^{2}(\alpha-1)+2p_{1}\lambda^{2}(\alpha-1),$
($\frac{p_{1}}{1-q_{1}}\leq 2$)

and

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
p_{1}\lambda^{2}(\alpha-1)^{2}+\frac{(1-p_{1})}{(1-q_{1})^{2}}(p_{1}-q_{1})^{2}(\alpha-1)^{2}$
$\displaystyle\leq
p_{1}\lambda^{2}(\alpha-1)^{2}+2p_{1}\lambda^{2}(\alpha-1)^{2}.$
($\frac{p_{1}}{1-q_{1}}\leq 2$ and $\frac{1-p_{1}}{1-q_{1}}\leq 1$)

Plug them back in (12). We conclude that

$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
p_{1}\lambda(\alpha-1)+p_{1}\lambda^{2}(\alpha-1)^{2}-\frac{1-p_{1}}{1-q_{1}}(p_{1}-q_{1})(\alpha-1)+\frac{(1-p_{1})}{(1-q_{1})^{2}}(p_{1}-q_{1})^{2}(\alpha-1)^{2}$
$\displaystyle\leq
3p_{1}\lambda^{2}(\alpha-1)+3p_{1}\lambda^{2}(\alpha-1)^{2}$
$\displaystyle\leq 3p_{1}\lambda^{2}(\alpha-1)\alpha.$ (13)

Hence, by a series of deductions ((11), (12), and (13)), we have finally
justified (10), which completes the proof. ∎