#  Subsampling Suffices for Adaptive Data Analysis

Guy Blanc
Stanford University

###### Abstract

Ensuring that analyses performed on a dataset are representative of the entire
population is one of the central problems in statistics. Most classical
techniques assume that the dataset is independent of the analyst’s query and
break down in the common setting where a dataset is reused for multiple,
adaptively chosen, queries. This problem of _adaptive data analysis_ was
formalized in the seminal works of Dwork et al. (STOC, 2015) and Hardt and
Ullman (FOCS, 2014).

We identify a remarkably simple set of assumptions under which the queries
will continue to be representative even when chosen adaptively: The only
requirements are that each query takes as input a random subsample and outputs
few bits. This result shows that the noise inherent in subsampling is
sufficient to guarantee that query responses generalize. The simplicity of
this subsampling-based framework allows it to model a variety of real-world
scenarios not covered by prior work.

In addition to its simplicity, we demonstrate the utility of this framework by
designing mechanisms for two foundational tasks, statistical queries and
median finding. In particular, our mechanism for answering the broadly
applicable class of statistical queries is both extremely simple and state of
the art in many parameter regimes.

##  1 Introduction

Data is a scarce and valuable resource. As a result, data analysts often reuse
the same dataset to answer multiple queries. [DFH+15c, HU14] initiated the
study of _adaptive data analysis_ , which aims to give provable guarantees
that the query answers will have low bias, i.e. be representative of the full
population, even when a data set is reused adaptively. Since then, there have
been a number of works exploring the adaptive reuse of data [DFH+15a, DFH+15b,
SU15b, SU15a, BNS+16, RZ16, RRST16, Smi17, FS17, FS18, FRR20, DK22].

Prior work can be split into two camps. The first focuses on the design of
_mechanisms_ , a layer between the analysts and dataset. In those works,
analysts do not have direct access to the data. Instead, when they wish to ask
a query $\phi$, they pass it to the mechanism. The mechanism uses the dataset
to answer $\phi$ without revealing too much information about the dataset;
e.g. by adding noise to the output of $\phi$ applied to the data set.
[DFH+15a, DFH+15b, DK22, FS18, FS17, SU15a]

The second camp provides ways to quantify the amount of information that has
so far been revealed about the dataset and guarantees that when that quantity
is small, query answers will have low bias. Such measures include those based
on mutual information [FS18, RZ16], max information [RRST16], and differential
privacy [DFH+15c, BNS+16]. Work in this camp is closely intertwined with the
first camp: Generally, these information measures are proposed in conjunction
with a specific mechanism design in mind. In order to prove the mechanism’s
responses have low bias, the first step is prove it reveals little
information, and second step is to prove that revealing little information
implies low bias.

This work is motivated by a simple question,

> _What minimal assumptions can we make about the queries to guarantee that
> the results will have low bias, even without an explicit mechanism?_

The purpose of asking this question is twofold. First, it models a reality in
which data analysts often do not explicitly use mechanisms to obfuscate query
results before looking at them. Second, if these assumptions are sufficiently
easy to explain to an analyst, they can be actionable, as the analyst can keep
the assumptions in mind when deciding how to analyze data.

A first attempt at answering this question is that the query should reveal
little information as quantified by any of the aforementioned measures. We
find this to be an unsatisfactory response. It is often difficult to determine
whether a natural sequence of queries satisfy those measures, so it is not
clear if the measures form a good model of reality. Furthermore, it is not
clear what takeaways an analyst not versed in the intricacies of information
theory is to glean from the idea that they should try to minimize mutual
information or some differential privacy parameters.

Our approach. We show that as long as each query takes as input a random
subsample of the dataset and outputs to a small range, the results will have
low bias. Quantitatively, our results depend on both the size of the subsample
and the number of possible outputs the query has. Unlike previous information
measures, this requirement is completely syntactic and trivial to verify. The
quantities are also intuitive and easy to explain to a data analyst who may be
interested in ensuring their results have low bias.

One interpretation of this framework is that it eliminates the need to design
a noise distribution for each task. Prior works design mechanisms to bound the
bias by adding an appropriate amount of noise to the true result before
returning it (e.g. by adding a mean-$0$ Gaussian). Our work shows that the
noise inherent in subsampling suffices. It also extends to tasks where it is
difficult to design an appropriate noise distribution – for example, when the
output of each query is categorical rather than numerical.

As easy corollaries of this subsampling approach, we give simple mechanisms
for two foundational tasks, statistical queries and median finding,
demonstrating the power of this framework. In particular, our mechanism for
answering the broad and influential class of _statistical queries_ (SQs)
[Kea98, FGR+17] achieves state of the art accuracy in many parameter regimes.
In addition to their broad applicability, statistical queries have been the
standard bearer by which we assess the utility of approaches for adaptive data
analysis since the early works of [DFH+15c, BNS+16]. Our SQ mechanism had
advantages beyond its accuracy: It runs in sublinear time, and its extreme
simplicity renders it broadly applicable in non-standard setting.

###  1.1 Our results

We’ll show that an analyst can ask an adaptive sequence of _subsampling
queries_ without incurring large bias.

######  Definition 1 (Subsampling query).

For any sample $S\in X^{n}$ and query $\phi:X^{w}\to Y$ where $w\leq n$, the
_subsampling query_ $\phi$ is answered by drawing
$\bm{x}_{1},\ldots,\bm{x}_{w}$ uniformly without replacement from $S$, and
then providing the answer $\bm{y}=\phi(\bm{x}_{1},\ldots,\bm{x}_{w})$.

The notation $\phi^{(n)}(S)$ denotes the distribution of $\bm{y}$ defined
above. Similarly, for any distribution $\mathcal{D}$ supported on $X$, the
notation $\phi^{(\mathrm{dist})}(\mathcal{D})$ denote the distribution of
$\bm{y}^{\prime}=\phi(\bm{x}_{1}^{\prime},\ldots,\bm{x}_{w}^{\prime})$ when
$\bm{x}_{1}^{\prime},\ldots,\bm{x}_{w}^{\prime}\overset{\mathrm{iid}}{\sim}\mathcal{D}$.

We allow the analyst to be _adaptive_ : The analyst’s choice for the
$t^{\text{th}}$ query may depend arbitrarily on the responses to the first
$t-1$ queries, as summarized in Figure 1. We first give an informal result
bounding the sample size needed to ensure the results have low bias.

######  Theorem 1 (The subsampling mechanism has low bias).

Suppose an analyst asks an adaptive sequence of $T$ subsampling queries, each
mapping $X^{w}$ to $Y$, to a sample $\bm{S}\sim\mathcal{D}^{n}$. As long as

$n\geq\tilde{\Omega}(w\sqrt{T\cdot|Y|}),$

with high probability, all of the queries will have low bias.

Theorem 1 can be compared to a naive approach which takes a fresh batch of $w$
samples for each query. Subsampling has a quadratically better dependence on
$T$ than that approach which requires $n\geq wT$. The following formal version
of Theorem 1 quantifies the bias of each query.

Input: A sample $S\in X^{n}$ not known to the analyst. For each time step
$t\in[T]$, the analyst 1. Selects a query $\phi_{t}:X^{w_{t}}\to Y_{t}$ which
can depend on the previous responses $\bm{y}_{1},\ldots,\bm{y}_{t-1}$. 2.
Receives the response $\bm{y}_{t}\sim\phi_{t}(S)$. Figure 1: An analyst asking
an adaptive sequence of subsampling queries.

######  Theorem 2 (Formal version of Theorem 1).

For any distribution $\mathcal{D}$ over domain $X$, and analyst making a
series of adaptive queries $\phi_{1},\ldots,\phi_{T}:X^{w}\to Y$ to a sample
$\bm{S}\sim\mathcal{D}^{n}$,

$\mathop{{\mathds{E}}\/}\left[\sup_{t\in[T],y\in
Y}\left(\phi^{(n)}_{t}(\bm{S})(y)-\phi^{(\mathrm{dist})}_{t}(\mathcal{D})(y)\right)^{2}\right]\leq
O\left(w\log n\left(\frac{wT|Y|}{n^{2}}+\frac{1}{n}\right)\right).$

where the expectation is both over the sample $\bm{S}$ and the analysts choice
of queries, and the notation $\mathcal{D}(x)$ denotes
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}[\bm{x}=x]$.

By Markov’s inequality, with probability at least $0.9$, for all $t\in[T]$ and
$y\in Y$

$\left|\operatorname{{Pr}}[\phi^{(n)}_{t}(\bm{S})(y)-\phi^{(\mathrm{dist})}_{t}(\mathcal{D})(y)\right|\leq\tilde{O}\left(\frac{w\sqrt{T|Y|}}{n}+\sqrt{\frac{w}{n}}\right).$

The second term, $\sqrt{\frac{w}{n}}$, quantifies the _inherit_ bias in a
sample: There are111One such example, for
$\mathcal{D}=\mathrm{Unif}(\\{-1,1\\})$, is the query
$\phi(S)=\mathds{1}[\sum_{x\in X}x\geq 0]$. queries $\phi:X^{w}\to\\{0,1\\}$,
for which, even with a fresh sample $\bm{S}$,
$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[|\phi^{(n)}(\bm{S})(1)-\phi^{(\mathrm{dist})}(\mathcal{D})(1)|]=\Theta(\sqrt{\frac{w}{n}})$.

The first term therefore quantifies the extra bias. When
$T|Y|\leq\frac{n}{w}$, that first term is dominated by the inherit bias. The
guarantee than slowly degrades from the inherit bias to vacuous as $T|Y|$
varies between $\frac{n}{w}$ and $\frac{n^{2}}{w^{2}}$. In contrast, naive
sample splitting works well from $T\leq\frac{n}{w}$ but cannot move beyond
that regime.

Our next theorem generalizes Theorem 2 in a number of ways. First, it allows
the analyst to choose a different domain and range size for each query – As a
function of the responses $\bm{y}_{1},\ldots,\bm{y}_{t-1}$, the analyst
chooses $w_{t},Y_{t}$ and a subsampling query $\phi:X^{w_{t}}\to Y_{t}$. The
only requirement is that the analyst not exceed a total _budget_

######  Definition 2 (Budgeted analyst).

For any distribution $\mathcal{D}$, sample size $n$, cost function,
$\mathrm{cost}$, mapping queries to $\mathds{R}_{\geq 0}$ and budget $b\geq
0$, we say an analyst is _$(\mathrm{cost},b)$ -budgeted in expectation_ if

$\mathop{{\mathds{E}}\/}\left[\sum_{t\in[T]}\mathrm{cost}(\phi_{t})\right]\leq
b$

where the expectation is over the analysts choice of queries
$\phi_{1},\ldots,\phi_{T}$ which in turn also depends on the randomness of
$\bm{S}\sim\mathcal{D}^{n}$ and the prior query outputs,
$\bm{y}_{1},\ldots,\bm{y}_{T-1}$ in Figure 1. Similarly, we say that an
analyst is _$(\mathrm{cost},b)$ -budgeted almost surely_ if
$\sum_{t\in[T]}\mathrm{cost}(\phi_{t})\leq b$ holds almost surely.

We further generalize Theorem 2 by disconnecting the test queries from the
first $T$ queries the analyst asks. After receiving the response
$\bm{y}_{1},\ldots,\bm{y}_{T}$, the analyst chooses any set of test queries
$\psi_{1}:X^{v_{1}}\to[0,1],\ldots,\psi_{m}:X^{v_{m}}\to[0,1]$ for which we
bound
$|\mathop{{\mathds{E}}\/}_{\bm{y}\sim\psi^{(n)}(\bm{S})}[\bm{y}]-\mathop{{\mathds{E}}\/}_{\bm{y}\sim\psi^{(\mathrm{dist})}(\mathcal{D})}[\bm{y}]|$.
To recover Theorem 2, we define a test query
$\psi(x_{1},\ldots,x_{w})\coloneqq\mathds{1}[\psi_{t}(x_{1},\ldots,x_{w})=y]$
for each $t\in[T]$ and $y\in Y_{t}$. The following notation will be
convenient.

######  Definition 3 (Expectation of a query).

For a query $\phi:X^{w}\to Y\subseteq\mathds{R}$ and sample $S\in X^{n}$, we
use the notation $\phi(S)$ as shorthand for
$\mathop{{\mathds{E}}\/}_{\bm{y}\sim\phi^{(n)}}[\bm{y}]$. Similarly, for a
distribution $\mathcal{D}$ over domain $X$, we use the notation
$\phi(\mathcal{D})$ as shorthand for
$\mathop{{\mathds{E}}\/}_{\bm{y}\sim\phi^{(\mathrm{dist})}}[\bm{y}]$.

A more technical improvement of Theorem 3 over Theorem 2 is that the error
bound improves when
$\operatorname{{Var}}_{\mathcal{D}}(\psi)\coloneqq\mathop{{\bf
Var}\/}_{\bm{y}\sim\psi^{(\mathrm{dist})}(\mathcal{D})}[\bm{y}]$ is small.
Theorem 2 corresponds to the pessimistic bound of
$\operatorname{{Var}}_{\mathcal{D}}(\psi)\leq 1$. This improvement will be
important to the application of answering statistical queries given in Section
1.1.1. To state Theorem 3, we define the _error_ of a test query.

######  Definition 4 (Error of a query).

For any $\psi:X^{w}\to[0,1]$, distribution $\mathcal{D}$ over $X$ and sample
$S\in X^{n}$, we define

$\mathrm{error}(\psi,S,\mathcal{D})\coloneqq\frac{1}{w}\cdot\min\left(\Delta,\frac{\Delta^{2}}{\operatorname{{Var}}_{\mathcal{D}}(\psi)}\right)\quad\quad\text{where
}\Delta\coloneqq|\psi(S)-\psi(\mathcal{D})|.$

If $\mathrm{error}(\psi,S,\mathcal{D})\leq\varepsilon$, then
$\Delta\leq\max(w\varepsilon,\sqrt{w\varepsilon\operatorname{{Var}}_{\mathcal{D}}(\psi)})$.
When $\operatorname{{Var}}_{\mathcal{D}}(\psi)=1$, the second term, or the
trivial bound of $\Delta\leq 1$, dominates. As
$\operatorname{{Var}}_{\mathcal{D}}(\psi)$ decreases, the bound improves until
it hits a floor of $w\varepsilon$.

######  Theorem 3 (Generalization of Theorem 2).

For sample size $n$, define the cost of a query as

$\mathrm{cost}_{n}(\phi:X^{w}\to Y)\coloneqq\frac{w|Y|\log n}{n-w}.$

For any distribution $\mathcal{D}$ over domain $X$ and adaptive analyst that
is $(\mathrm{cost}_{n},b)$-budgeted in expectation, let $\Psi$, $|\Psi|\leq
m$, be a collection of tests the analyst chooses after receiving query
responses $\bm{y}_{1},\ldots,\bm{y}_{T}$. Then

$\mathop{{\mathds{E}}\/}\left[\sup_{\psi\in\Psi}\mathrm{error}(\psi,\bm{S},\mathcal{D})\right]\leq
O\left(\frac{b+\log m+1}{n}\right)$

where the expectation is both over the sample $\bm{S}\sim\mathcal{D}^{n}$ and
the analyst’s decisions.

While Theorem 3 only guarantees low bias in expectation, we further show that
a high probability guarantee holds when $w_{t}=1$ for all $t\in T$.

######  Theorem 4 (Improved dependence on failure probability).

In the setting of Theorem 3, if the analyst is
$(\mathrm{cost}_{n},b)$-budgeted _almost surely_ , chooses $w_{t}=1$ for all
$t\in[T]$ and, as a function of the responses $\bm{y}_{1},\ldots,\bm{y}_{T}$,
chooses a single test $\psi:X\to[0,1]$, then, for any failure probability
$\delta>0$,

$\operatorname{{Pr}}\left[\mathrm{error}(\psi,\bm{S},\Delta)\geq
O\left(\log(1/\delta)\cdot\left(\frac{b+1}{n}\right)\right)\right]\leq\delta.$

Note that the logarithmic dependence on $\delta$ means that a union bound
suffices to handle the case where the analysts chooses $m$ tests. In that
case, the $\log(1/\delta)$ dependence is instead $\log(m/\delta)$.

The case of $w=1$ is particularly interesting for two reasons.

  1. 1.

It is sufficient for our application of answering statistical queries, a
widely-applicable query class, given in Section 1.1.1. Indeed, one way to
characterize statistical queries are precisely those queries
$\phi:X^{n}\to[0,1]$ for which an unbiased (and bounded) estimator of
$\phi(S)$ can be computed given a single $\bm{x}\sim\mathrm{Unif}(S)$. Our
mechanism for answering statistical queries simply averages many of these
unbiased estimators.

  2. 2.

One way to answer a query with $w\geq 2$ is to cast a sample of $n$ points
from $\mathcal{D}$ as a sample of $\lfloor n/w\rfloor$ points each drawn from
$\mathcal{D}^{w}$. By doing so, each query $\phi:X^{w}\to Y$ can be answered
by looking at one “grouped point,” and so Theorem 4 gives a high probability
guarantee. We conjecture that such grouping is unnecessary and that Theorem 4
would directly hold without the restriction that $w_{t}=1$ for all $t\in[T]$.
That said, the proof breaks in this setting, and so we consider extending it
to be an intriguing open problem.

Lastly, we show it is possible to drop the $\log n$ dependence from Theorems 3
and 4 for queries that are sufficiently _uniform_ , meaning each output of the
query is fairly likely to occur. To define uniform queries, we expand
Definition 1 to allow for subsampling queries that are not deterministic
functions. Rather, given a subsample $x_{1},\ldots,x_{w}$, the output of the
query may still be a random variable. Equivalently, we may think of every
query as accepting as input random bits in addition to the subsample, though
we will suppress those random bits from out notation.

######  Definition 5 ($p$-uniform).

A subsampling query $\phi:X^{w}\to Y$ is said to be $p$-_uniform_ if, for
every $x_{1},\ldots,x_{w}\in X$ and every $y\in Y$,
$\operatorname{{Pr}}[\phi(x_{1},\ldots,x_{w})=y]\geq p$.

######  Theorem 5 (Improved bounds for $p$-uniform queries).

Theorem 3 holds, where for a $p$-uniform query $\phi:X^{w}\to Y$, the improved
cost function

$\mathrm{cost}_{n}(\phi)\coloneqq\frac{w|Y|}{n-w}\cdot\min\left(\log
n,1+\log\left(1+\frac{w}{np}\right)\right)$ (1)

is used. For Theorem 4, the improved cost function also incorporates the
desired failure probability, $\delta$, and is defined

$\mathrm{cost}_{n,\delta}(\phi)\coloneqq\frac{|Y|}{n}\cdot\min\left(\log
n,1+\log\left(1+\frac{\log(1/\delta)}{np}\right)\right)$ (2)

When $p$ is large enough, the cost function in Theorem 5 improves upon that of
Theorems 3 and 4 by a $\log n$ factor. In the applications of Sections 1.1.1
and 1.1.2, we will add a small amount of noise to eliminate that log factor.
Without that noise, the mechanisms would be even simpler, though the sample
size needed would increase by a log factor.

####  1.1.1 A mechanism for statistical queries

Our main application is an extremely simple and accurate mechanism for the
broad class of _statistical queries_. Statistical queries, introduced by
Kearns [Kea98], are parameterized by a function $\phi:X\to[0,1]$. A valid
answer to such a query is any value close to $\phi(\mathcal{D})$. Many natural
analyses can be cast as sequence of statistical queries. This includes most
algorithms for both supervised and unsupervised learning, such as least-
squares regression, gradient-descent, and moment based methods. We refer the
reader to [FGR+17] for a more extensive list.

Input: A sample $S\in X^{n}$ and parameters $\varepsilon,k$. For each time
step $t\in[T]$, 1. Receive a query $\phi_{t}:X\to[0,1]$. 2. Define,
$\phi_{t}^{\prime}(x)\coloneqq\begin{cases}\varepsilon&\text{if
}\phi_{t}(x)\leq\varepsilon,\\\ 1-\varepsilon&\text{if }\phi_{t}(x)\geq
1-\varepsilon,\\\ \phi_{t}(x)&\text{otherwise.}\end{cases}$ 3. Sample
uniformly
$\bm{x}_{1},\ldots,\bm{x}_{k}\overset{\mathrm{iid}}{\sim}\mathrm{Unif}(S)$ and
for each, sample
$\bm{v}_{i}\sim\mathrm{Bernoulli}(\phi_{t}^{\prime}(\bm{x}_{i}))$. 4. Set
$\bm{y}_{t}$ to the mean of $\bm{v}_{1},\ldots,\bm{v}_{k}$ and output
$\bm{y}_{t}$. Figure 2: A mechanism for statistical queries using subsampling.

The mechanism for answering statistical queries is given in Figure 2. Note
that an even simpler mechanism that does not “squash,” taking
$\phi^{\prime}=\phi$, still provides accurate answers to statistical queries.
The difference is just a log-factor on the sample size as such queries are not
guaranteed to be $p$-uniform, and so the improvement of Theorem 5 to Theorem 4
does not hold.

######  Theorem 6 (Accuracy of our mechanism for answering SQs).

For any parameters $\tau,\delta>0$, adaptively chosen sequence of statistical
queries $\phi_{1},\ldots,\phi_{T}:X\to[0,1]$, and sample size

$n\geq\Omega\left(\frac{\sqrt{T\log(T/\delta)\log(1/\delta)}}{\tau^{2}}\right),$
(3)

if the mechanism of Figure 2 is given a sample $\bm{S}\sim\mathcal{D}^{n}$ and
parameters

$\varepsilon\coloneqq
O\left(\frac{\log(1/\delta)}{n}\right)\quad\quad\quad\quad\text{and}\quad\quad\quad\quad
k\coloneqq O\left(\frac{\log(T/\delta)}{\tau^{2}}\right),$

with probability at least $1-\delta$, it answers all queries $t\in[T]$ to
accuracy

$|\bm{y}_{t}-\mathop{{\mathds{E}}\/}[\phi_{t}(\mathcal{D})]|\leq\max(\tau\cdot\operatorname{{std}}(\phi_{t}),\tau^{2})$
(4)

where
$\operatorname{{std}}(\phi)\coloneqq\sqrt{\mathop{{\mathds{E}}\/}[\phi(\mathcal{D})](1-\mathop{{\mathds{E}}\/}[\phi(\mathcal{D})])}\leq
1$.

The proof of Theorem 6 is a simple corollary of Theorems 5 and 4: Each vote
($\bm{v}_{i}$ in Figure 2) is the output of a subsampling query
$\phi:X\to\\{0,1\\}$ and so fits within our framework with $w=1$, and $|Y|=2$.

In many settings, the bound of Theorem 6 is state of the art. When
$\operatorname{{std}}(\phi)=o(1)$, its accuracy improves upon prior state of
the arts, both from Feldman and Steinke.222It’s worth noting that both of
these works use a more strict definition of
$\operatorname{{std}}(\phi)=\sqrt{\operatorname{{Var}}_{\bm{x}\sim\mathcal{D}}[\phi(\bm{x})]}$.
If the range of $\phi$ is $\\{0,1\\}$, their definition and ours coincide.
Otherwise, their definition can be smaller than ours.

  1. 1.

In [FS17], they gave a mechanism with the accuracy guarantees of Theorem 6,
but requiring a larger sample size of

$n\geq\Omega\left(\frac{\sqrt{T\log(1/\delta)}\log(T/\tau\delta)}{\tau^{2}}\right).$

In addition to requiring a larger sample size than Theorem 6, that mechanism
is also more complicated than ours. It splits the dataset into chunks of size
$\frac{1}{\tau^{2}}$. Given a query, it computes the average of that query on
each chunk, and then computes an approximate median of those averages via a
differentially private algorithm. The same mechanism actually solves the
approximate median problem described in Section 1.1.2.

  2. 2.

In [FS18], they gave a mechanism with a slightly worse sample size333Their
sample size is a $\sqrt{\log(T)}$ multiplicative factor worse than ours when
$\delta$ is constant. Theorem 6 when the failure probability, $\delta$, is a
constant. Their mechanism is also simple: For a sample $S$ and query $\phi$,
they compute $\phi(S)+\zeta$ where $\zeta$ is a Gaussian with mean $0$ and
variance that scales with $\operatorname{{std}}(\phi)$. However, their
dependence on $\delta$ is a multiplicative $1/\delta$ factor, exponentially
worse than ours.

The pessimistic setting where all the queries satisfy
$\operatorname{{std}}(\phi)=\Theta(1)$ is more well studied [DFH+15c, BNS+16,
SU15b, SU15a, HU14, DK22]. The state of the art was given recently by Dagan
and Kur [DK22], who showed that a sample of size

$n=O\left(\frac{\sqrt{T\log(1/\tau\delta)}}{\tau^{2}}\right)$

is sufficient whenever $\tau\delta\geq 2^{-\tilde{O}(T)}$. Their mechanism
works by returning $y_{t}=\phi_{t}(S)+\zeta$ where $\zeta$ is drawn from a
very carefully constructed _bounded_ distribution. Our mechanism has a
slightly better dependence on $\tau$ and a better accuracy when
$\operatorname{{std}}(\phi)$ is small, but slightly worse dependencies on $T$
and $\delta$.

##### Advantages of our mechanism.

Our mechanism has advantages beyond the quantitative bound on the sample size
needed for low bias. First, it naturally runs in sublinear time as answering
each query requires only looking at $k=n/\sqrt{T}$ of the points in $S$.

Furthermore, our mechanism easily extends to the setting where the analyst
does not know ahead of time how many samples, the parameter $k$ in Figure 2,
they want for a particular query. Rather, they can sequentially sample
$\bm{v}_{1},\bm{v}_{2},\ldots$ while continually updating an estimate for
$\phi(\mathcal{D})$ and stop at any point. The bounds of Theorem 6 hold as
long as the total number of samples is at most $n\sqrt{T}$. Early stopping can
appear naturally in practice. For example,

  1. 1.

The analyst may only desire accuracy $\pm\tau$, regardless of what
$\operatorname{{std}}(\phi_{t})$ is. If, based on the first $k^{\prime}<k$
samples, the analyst can determine that $\operatorname{{std}}(\phi_{t})$ is
small, they can stop early as a small $\operatorname{{std}}(\phi_{t})$ means
fewer samples are needed to acheive the desired accuracy.

  2. 2.

The analyst may wish to verify whether $\phi(\mathcal{D})\approx c$ for some
value $c$. If after the first $k^{\prime}<k$ samples, the average is far from
$c$, the analyst can already determine that $\phi(\mathcal{D})$ is far from
$c$. This setting has previously been studied in the influential work of
[DFH+15a, DFH+15b] which showed that there exists mechanisms that answer
exponentially many such verification queries, as long as all but a tiny
fraction of the inequalities to verify are true. Our analysis does not extend
to exponentially many queries, but it can easily intertwine standard queries
with verification queries, with the later being cheaper.

####  1.1.2 A mechanism for finding approximate medians

We also consider a generalization of statistical queries, each of which map
$w$ inputs to some set $R\subseteq\mathds{R}$. For such queries, we give a
mechanism for determining an _approximate median_ of the distribution
$\phi^{(\mathrm{dist})}(\mathcal{D})$.

######  Definition 6 (Approximate median).

For a distribution $\mathcal{E}$ with support in $\mathds{R}$, we say a value
$y$ is an _approximate median of $\mathcal{E}$_ if,

$\min\left(\operatorname{{Pr}}_{\bm{x}\sim\mathcal{E}}[\bm{x}<y],\operatorname{{Pr}}_{\bm{x}\sim\mathcal{E}}[\bm{x}>y]\right)\geq
0.4.$

One particular application for approximate median queries is, once again, for
answering statistical queries. Given an SQ $\phi:X\to[0,1]$, we can construct

$\phi^{\prime}(x_{1},\ldots,x_{w})=\mathop{{\mathds{E}}\/}_{\bm{i}\in[w]}[\phi(\bm{x}_{i})].$

Since $\phi^{\prime}$ and $\phi$ have the same mean, and $\phi^{\prime}$ has a
smaller variance, Chebyshev’s inequality implies that any approximate median
of $\phi^{\prime}$ will be within $2/\sqrt{w}$ standard deviations of
$\phi(\mathcal{D})$. As a result, the mechanism of Figure 3 can give similar
accuracy results as guaranteed in Theorem 6. The sample size required is
larger (by log factors), but in exchange, it provides better accuracy when
$\operatorname{{std}}(\phi)$ is smaller than $\tau$. In that setting, the
$\tau^{2}$ term of Equation 4 dominates, but the median-based mechanism does
not incur it.

Input: A sample $S\in X^{n}$ split into $k$ groups $S^{(1)},\ldots,S^{(k)}$
each containing $\geq\lfloor n/k\rfloor$ elements. For each time step
$t\in[T]$, 1. Receive a query $\phi_{t}:X^{w_{t}}\to R_{t}$ where
$R_{t}\subseteq\mathds{R}$. 2. Perform binary search on the mechanism’s output
$\bm{y}_{t}\in R_{t}$ where, to determine whether $\bm{y}_{t}\geq r$, the
following procedure is used. (a) For each group $i\in k$ generate a vote
$\bm{v}_{i}$ by first sampling a random subset
$\bm{S}^{\prime}\sim\binom{S^{(i)}}{w_{t}}$ and then setting
$\bm{v}_{i}=\mathds{1}[\phi_{t}(\bm{S}^{\prime})\geq r]$. (b) Add noise to
each vote $\bm{v}_{i}$ by flipping it with probability
$\frac{w}{|S^{(i)}|}$.555This mechanism still works without the added noise,
though with slightly worse parameters. (c) Determine $\bm{y}_{t}\geq r$ iff at
least half of the votes are $1$. 3. After the $\lceil\log_{2}(R_{t})\rceil$
steps of binary search have finished, a single value $\bm{y}_{t}=r$ will be
determined. Output it. Figure 3: The subsampling mechanism answering
approximate median queries.

######  Theorem 7 (Accuracy of our mechanism for answering approximate median
queries).

For any adaptively chosen sequence of queries $\phi_{1}:X^{w_{1}}\to
R_{1},\ldots,\phi_{T}:X^{w_{T}}\to R_{T}$ and $\delta>0$, if the sample size
satisfies

$n\geq\Omega\left(\log\left(\frac{T\log
R_{\max}}{\delta}\right)\sqrt{w_{\max}\sum_{t\in T}w_{t}}\right)$

where $w_{\max}$ and $R_{\max}$ are upper bounds on $w_{t}$ and $|R_{t}|$
respectively, and $k\coloneqq\log\left(\frac{T\log R_{\max}}{\delta}\right)$,
then with probability at least $1-\delta$, for all $t\in[T]$, the output
$\bm{y}_{t}$ of Figure 3 is an approximate median for
$\phi^{(\mathrm{dist})}_{t}(\mathcal{D})$.

Feldman and Steinke also give a mechanism for answering approximate median
queries [FS17]. Their mechanism needs a sample size of

$n\geq\Omega\left(\log\left(\frac{TR_{\max}}{\delta}\right)\sqrt{\log(1/\delta)Tw_{\max}^{2}}\right).$

Our sample size bound is similar to theirs in the pessimistic settings where
$w_{t}\approx w_{\max}$ for all $t$, with slight improvements on some of the
other dependencies. For example, we have a linear dependence on
$\log(1/\delta)$, whereas they have a $\log(1/\delta)^{3/2}$ dependence.

Most interestingly, our mechanisms and that of [FS17] is fairly similar – both
rely on splitting the dataset and, roughly speaking, computing an approximate
median of the queries’ value on each group – but the analyses are wholly
different. Their analysis is based on differential privacy. In contrast,
Theorem 7 is a simple corollary of Theorem 5. Indeed, it’s not difficult to
show that our mechanism does _not_ satisfy standard $(\varepsilon,\delta)$
differential privacy with strong enough parameters to give a sample size bound
close to that of Theorem 7.

###  1.2 Other related work

Subsampling has been thoroughly explored in the context of privacy
amplification (see e.g. [BBG18, ZW19] or the book chapter [Ste22]): if
$\mathcal{A}$ is a differentially private algorithm, running $\mathcal{A}$ on
a random subset of the data gives an algorithm with even better privacy
parameters. Given the previous applications of differential privacy to
adaptive data analysis, this seems like a natural starting point for our work.
However, such an approach is not sufficient to analyze subsampling queries.
Indeed, subsampling queries do not necessarily satisfy
$(\varepsilon,\delta)$-differential privacy with sufficiently good parameters
to give useful bounds on the bias.

Fish, Reyzin, and Rubinstein explored the use of subsampling to speed up
classical mechanisms for adaptive data analysis [FRR20]. For example, their
mechanism for answering a statistical query $\phi$, computes $\phi$ on a
random subsample of the data _and_ adds Laplacian noise to that result. This
allows them to retain the accuracy guarantees of prior mechanisms that added
Laplacian noise [BNS+16] while also running in sublinear time. In contrast,
our work shows that subsampling alone is sufficient, and achieves sample size
bounds that improve upon prior work.

##  2 Technical Overview

We consider the entire transcript of interaction between the analyst and the
random sample $\bm{S}\sim\mathcal{D}^{n}$. This transcript, denoted $\bm{y}$,
records the history of queries $\phi_{1},\ldots,\phi_{T}$ asked by the
analyst, as well as the responses $\bm{y}_{t}\sim\phi(\bm{S})$ for each
$t\in[T]$. The bulk of the work in proving Theorem 3 and its generalization
given in Theorem 5 is the following mutual information bound.

######  Theorem 8.

In the settings of Theorems 3 and 5, let $\bm{y}$ be the transcript of
interaction between the analyst and sample $\bm{S}$. Then, the mutual
information of $\bm{S}$ and $\bm{y}$ is at most $O(nb)$.

The starting point for Theorem 8 is the work of Feldman and Steinke [FS18].
They introduce the following notion of algorithmic stability.

######  Definition 7 (Average leave-one-out KL stability, [FS18]).

A randomized algorithm $\mathcal{M}:X^{n}\to Y$ is $\varepsilon$-ALKL stable
if there is some randomized algorithm $\mathcal{M}^{\prime}:X^{n-1}\to Y$ such
that, for all samples $S\in X^{n}$,

$\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}(S)}\big{\|}{\mathcal{M}^{\prime}(S_{-\bm{i}})}\big{)}\right]\leq\varepsilon$

where $d_{\mathrm{KL}}\left({\cdot}\middle\|{\cdot}\right)$ is the KL-
divergence and $S_{-i}\in X^{n-1}$ refers to all but the $i^{\text{th}}$ point
of $S$.

Intuitively, a mechanism that is ALKL stable cannot depend too much on any
single point in the sample. Feldman and Steinke show that if a transcript
$\bm{y}$ is produced via the adaptive composition of $T$ queries, each of
which are individually $\varepsilon$-ALKL stable, then the mutual information
between $\bm{y}$ and $\bm{S}$ is at most $nT\varepsilon$. Hence, our proof of
Theorem 8 proceeds by showing that a subsampling query $\phi^{(n)}$ is
$(O(\mathrm{cost}_{n}(\phi)))$-ALKL stable.

The most natural candidate for $\mathcal{M}^{\prime}$ in Definition 7 is
$\phi^{(n-1)}$. Unfortunately, its not hard to construct a query $\phi$,
sample $S\in X^{n}$, and $i\in[n]$ for which
$d_{\mathrm{KL}}\left({\phi^{(n)}(S)}\middle\|{\phi^{(n-1)}(S_{-i})}\right)$
is infinite, and so this candidate does not work. For example, if
$X=\\{0,1\\}$, $\phi:X^{1}\to\\{0,1\\}$ is the identity function, and
$S=\\{1,0,\ldots,0\\}$, the support of $\phi^{(n)}(S)$ is $\\{0,1\\}$ whereas
the support of $\phi^{(n-1)}(S_{-i})$ is only $\\{0\\}$, leading to an
infinite KL-divergence. To get around this, we define the following
alternative notion of stability.

######  Definition 8 (Average leave-one-out $\chi^{2}$ stability).

A randomized algorithm $\mathcal{M}:X^{n}\to Y$ is $\varepsilon$-$\chi^{2}$
stable if there is some randomized algorithm $\mathcal{M}^{\prime}:X^{n-1}\to
Y$ such that, for all samples $S\in X^{n}$,

$\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\chi^{2}}\big{(}{\mathcal{M}(S)}\big{\|}{\mathcal{M}^{\prime}(S_{-\bm{i}})}\big{)}\right]\leq\varepsilon$

where $d_{\chi^{2}}\big{(}{\mathcal{D}}\big{\|}{\mathcal{E}}\big{)}$ is the
reversed $\chi^{2}$ divergence, which is infinite if
$\mathrm{supp}(\mathcal{E})\not\subseteq\mathrm{supp}(\mathcal{D})$ and
otherwise equal to
$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[\frac{(\mathcal{D}(\bm{x})-\mathcal{E}(\bm{x}))^{2}}{\mathcal{D}(\bm{x})^{2}}\right]$.

Whereas $d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)$ is
finite iff $\mathrm{supp}(\mathcal{D})\subseteq\mathrm{supp}(\mathcal{E})$,
$d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)$ is finite iff
$\mathrm{supp}(\mathcal{E})\subseteq\mathrm{supp}(\mathcal{D})$. As a result
$d_{\chi^{2}}\big{(}{\phi^{(n)}(S)}\big{\|}{\phi^{(n-1)}(S_{-i})}\big{)}$ is
guaranteed to be finite. Furthermore, given the quadratic nature of
$\chi^{2}$-divergence, we are able to use the techniques of linear algebra to
give a bound on
$\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\chi^{2}}\big{(}{\phi^{(n)}(S)}\big{\|}{\phi^{(n-1)}(S_{-\bm{i}})}\big{)}\right]$.
That bound is given in Section 5.

We are further able to show, in Section 4, a surprising connection between
ALKL stability and $\chi^{2}$ stability: If $\mathcal{M}$ is
$\varepsilon$-$\chi^{2}$ stable, it is
$(\varepsilon^{\prime}\coloneqq\varepsilon\log(|Y|/\varepsilon))$-ALKL stable.
Since $d_{\mathrm{KL}}\left({\cdot}\middle\|{\cdot}\right)$ and
$d_{\chi^{2}}\left({\cdot}\middle\|{\cdot}\right)$ are finite in different
regimes, we cannot use the same $\mathcal{M}^{\prime}$ in Definitions 7 and 8.
Instead, we “smooth” the $\mathcal{M}^{\prime}$ of Definition 8 to ensure its
support includes all elements of $Y$.

Sections 4 and 5 together prove Theorem 8. Bounded mutual information is known
to imply various generalization bounds. Our setting is non-standard, so in
Section 6, we connect mutual information to the generalization guarantee of
Theorem 3.

###  2.1 An auto-boosting result

While low mutual information is sufficient to guarantee generalization on
average, it does not imply the sort of high probability guarantee given in
Theorem 4. Instead, we show an “auto-boosting” result in the case where
$w_{t}=1$ at all time steps $t$.

######  Lemma 2.1 (Informal version of Lemma 7.1).

Suppose that the analyst always asks subsampling queries $\phi:X^{w_{t}}\to
Y_{t}$ where $w_{t}=1$ for all $t\in[T]$. Any low-bias guarantee that holds
with constant probability for a sample size of $n$ holds with probability
$1-2^{\Omega(-N/n)}$ given a sample of size $N>n$.

The intuition behind Lemma 2.1 is the following natural way to boost success
probabilities: Start by drawing $k$ disjoint samples
$\bm{S}^{(1)},\ldots,\bm{S}^{(k)}\overset{\mathrm{iid}}{\sim}\mathcal{D}^{n}$.
Then, whenever a query $\phi$ appears, choose a random group $\bm{i}\in[k]$
and output $\phi(\bm{S}^{(\bm{i})})$. The hypothesis of Lemma 2.1 then
guarantees the following: For any test $\psi$ chosen as a function of the
query responses, the probability $\bm{S}^{(i)}$ is biased with respect to
$\psi$ is at most a constant, say $0.1$, for each $i\in[k]$. If these events
were independent, then the probability a large fraction, say $0.2k$, of the
disjoint samples are “biased” is $2^{-\Omega(k)}$.

It turns out there is some subtlety in applying this intuition. Because the
analyst can choose which query to ask a group $S^{(i)}$ as a function of
responses from some other group $S^{(i^{\prime})}$, the events indicating
whether each group is biased need not be independent. To handle this we
generalize a direct product theorem of Shaltiel that was originally applied to
fair decision trees [Sha04]. That generalization, given in Lemma 7.4 shows
that while those events need not be independent, they behave no worse than if
they were.

Furthermore, the above natural way of boosting success probabilities happens
automatically! Given a sample of size $S\in X^{N\coloneqq nk}$, the answer of
a query $\bm{y}=\phi(S)$ where $\phi:X^{1}\to Y$ is completely equivalent to
the answer $\bm{y}^{\prime}=\phi(S^{(\bm{i})})$ where $S^{(1)},\ldots
S^{(k)}\in X^{n}$ are partitions of $S$ and $\bm{i}\sim\mathrm{Unif}([k])$. We
can answer subsampling queries in the most natural way, and they automatically
boost their own success probabilities. Note that this step importantly relies
on $w_{t}=1$ and fails for larger $w$.

Finally, in Section 8, we prove that both of SQ mechanism and median-finding
mechanism both have low bias. Given our framework, these proofs are simple.

##  3 Notation and key definitions

##### Sets and multisets.

For a natural number $n$, we use $[n]$ to denote the set $\\{1,\ldots,n\\}$.
For a multiset $S\in X^{n}$ we use the notation $S_{i}$ to indicate the
$i^{\text{th}}$ element of $S$, and
$S_{-i}\coloneqq(S_{1},\ldots,S_{i-1},S_{i+1},\ldots,S_{n})$ denotes the
remaining $n-1$ elements. For $w\leq n$, we use the notation $\binom{S}{w}$ to
indicate the set of all size-$w$ multisets $S^{\prime}$ that are contained
within $S$.

##### Random variables and distributions.

We use boldfont (e.g. $\bm{x}\sim\mathcal{D}$) to denote random variables, and
generally will use calligraphic font to denote distribution. The notation
$\bm{x}\sim S$ for a (multi)set $S$ is shorthand for
$\bm{x}\sim\mathrm{Unif}(S)$. For a distribution $\mathcal{D}$ over domain $X$
and element $x\in X$, we use $\mathcal{D}(x)$ to denote the probability mass
function of $\mathcal{D}$ evaluated at $x$. Similarly, for a subset
$X^{\prime}\subset X$, the notation $\mathcal{D}(X^{\prime})$ is shorthand for
$\sum_{x\in X^{\prime}}\mathcal{D}(x)$. We use
$\mathrm{supp}(\mathcal{D})\coloneqq\\{x\in X\mid\mathcal{D}(x)>0\\}$ for the
support of $\mathcal{D}$. For convenience, all domains and distributions will
be discrete.

##### Logarithms and exponentials.

We use $\log$ to denote the natural logarithm, $\log_{2}$ to denote logarithms
in base 2, and $\exp$ to denote the function $x\mapsto e^{x}$.

##### Properties of distributions and random variables.

Throughout this paper, we will use the following two notions of “closeness” of
two distributions.

######  Definition 9 (Kullback-Leibler (KL) Divergence).

For distributions $\mathcal{D}$, $\mathcal{E}$ supported on a domain $X$, the
_KL divergence_ between $\mathcal{D}$ and $\mathcal{E}$ is defined as,

$d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[\log\left(\frac{\mathcal{D}(\bm{x})}{\mathcal{E}(\bm{x})}\right)\right].$

######  Definition 10 (Neyman’s $\chi^{2}$ divergence).

For distribution $\mathcal{D}$, $\mathcal{E}$ supported on a domain $X$, we
define the _$\chi^{2}$ divergence_ between $\mathcal{D}$ and $\mathcal{E}$

$d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[\frac{(\mathcal{D}(\bm{x})-\mathcal{E}(\bm{x}))^{2}}{\mathcal{D}(\bm{x})^{2}}\right]=\sum_{x\in
X}\frac{(\mathcal{D}(x)-\mathcal{E}(x))^{2}}{\mathcal{D}(x)}.$

Note that our definition of $\chi^{2}$ divergence reverses the arguments
relative to Pearson’s $\chi^{2}$ divergence.

Furthermore, mutual information will play a critical role in our proofs.

######  Definition 11 (Mutual information).

For random variables $\bm{x},\bm{y}$ jointly distributed according to a
distribution $\mathcal{D}$, let $\mathcal{D}(x)$ and $\mathcal{D}(y)$ be the
marginal distributions of $\bm{x}$ and $\bm{y}$ respectively. The mutual
information between $\bm{x}$ and $\bm{y}$ is defined as

$I(\bm{x};\bm{y})\coloneqq
d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{D}(x)\times\mathcal{D}(y)}\right)=\mathop{{\mathds{E}}\/}_{\bm{y}}\left[d_{\mathrm{KL}}\left({\mathcal{D}(x\mid\bm{y}=y)}\middle\|{\mathcal{D}(y)}\right)\right].$

###  3.1 Formal model of the analyst

Figure 1 summarizes the interaction of the analyst with a sample $S\in X^{n}$.
Formally, we model the analyst $\mathcal{A}$ as a function mapping a time step
$t\in[T]$, previous query responses $y_{1},\ldots,y_{t-1}$, and a source of
randomness $\bm{z}\sim\mathcal{Z}$ to a subsampling query $\phi_{t}$. After
the $T^{\text{th}}$ step, the analyst outputs a series of test queries
$\psi_{1}:X^{v_{1}}\to\\{0,1\\},\psi_{m}:X^{v_{m}}\to\\{0,1\\}$, also as a
function of $y_{1},\ldots,y_{T}$ and $\bm{z}$. With this formal description of
the analyst, we can give the following lengthy but fully explicit description
of Theorem 3.

######  Theorem 9 (Theorem 3 restated with a formal model of the analyst).

For any analyst $\mathcal{A}$ and distributions $\mathcal{D},\mathcal{Z}$,
draw $\bm{S}\sim\mathcal{D}^{n}$ and $\bm{z}\sim\mathcal{Z}$. For each
$t\in[T]$, let $\phi_{t}=\mathcal{A}(t,\bm{y}_{1},\ldots,\bm{y}_{t-1},\bm{z})$
and $\bm{y}_{t}\sim\phi^{(n)}_{t}(\bm{S})$. Then, for
$\psi_{1},\ldots,\psi_{m}=\mathcal{A}(T,\bm{y}_{1},\ldots,\bm{y}_{T},\bm{z})$,

$\mathop{{\mathds{E}}\/}[\sup_{i\in[m]}\mathrm{error}(\psi_{i},\bm{S},\mathcal{D})]\leq
O\left(\mathop{{\mathds{E}}\/}\left[\frac{\sum_{t\in
T}\mathrm{cost}_{n}(\phi_{t})+\log m+1}{n}\right]\right).$ (5)

We will restrict our attention to _deterministic_ analysts, where the analysts
output is a deterministic function of the previous responses. Deterministic
analysts do not take in a source of randomness (previously denoted
$\bm{z}\sim\mathcal{Z}$). Through the following simple argument, this is
without loss of generality.

######  Lemma 3.1 (Deterministic analysts are as powerful as randomized
analysts).

If Theorem 3 holds for deterministic analysts, it also holds for randomized
analysts. The same is true for Theorems 4 and 5.

###### Proof.

Let $\mathcal{A}$ be a randomized analyst. We can think of it as a mixture of
deterministic analysts: $\mathcal{A}$ first draws $\bm{z}\sim\mathcal{Z}$ and
then executes the deterministic strategy
$\mathcal{A}_{\bm{z}}\coloneqq\mathcal{A}(\cdot,\bm{z})$. Then,

$\displaystyle\mathop{{\mathds{E}}\/}[\text{Error with $\mathcal{A}$ as the
analyst}]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{z}}[\mathop{{\mathds{E}}\/}[\text{Error
with $\mathcal{A}_{\bm{z}}$ as the analyst}]]$
$\displaystyle\leq\sup_{z}\mathop{{\mathds{E}}\/}[\text{Error with
$\mathcal{A}_{z}$ as the analyst}]$

The left-hand side of Equation 5 when $\mathcal{A}$ is the analyst is the
expectation of the same quantity when $\mathcal{A}_{\bm{z}}$ is the analyst.
Therefore, if it is small for all deterministic analysts, it is also small for
all randomized analysts. Similar arguments hold for Theorems 4 and 5. ∎

##  4 Bounding ALKL-stability from $\chi^{2}$-stability

The starting point of our analysis is the work of [FS18]. They introduce a
notion of _algorithmic stability_ , measuring how much the output of the
algorithm depends on its input.

######  Definition 12 (Average leave-one-out KL stability, Definition 7
restated, [FS18]).

A randomized algorithm $\mathcal{M}:X^{n}\to Y$ is $\varepsilon$-ALKL stable
with respect to a randomized algorithm $\mathcal{M}^{\prime}:X^{n-1}\to Y$ if,
for all samples $S\in X^{n}$,

$\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}(S)}\big{\|}{\mathcal{M}^{\prime}(S_{-\bm{i}})}\big{)}\right]\leq\varepsilon.$

We simply say that $\mathcal{M}$ is $\varepsilon$-ALKL stable if there exists
some $\mathcal{M}$’ with respect to which it is $\varepsilon$-ALKL stable.

Intuitively, the output of a mechanism that is $\varepsilon$-ALKL cannot
depend too much on individual points in the sample. Feldman and Steinke were
able to formalize this intuition to show that, if each step of an adaptive
mechanism is ALKL stable, it does not reveal too much information about its
input.

######  Fact 4.1 (ALKL stability bounds mutual information [FS18]).

if $\mathcal{M}:X^{n}\to Y$ is $\varepsilon$-ALKL stable, then for
$\bm{S}\sim\mathcal{D}^{n}$ and $\bm{y}\sim\mathcal{M}(\bm{S})$,

$I(\bm{S};\bm{y})\leq n\varepsilon.$

Furthermore, if $\mathcal{M}_{1}:X^{n}\to Y_{1}$ is $\varepsilon_{1}$-ALKL
stable, and for each $y\in Y_{1}$, $\mathcal{M}_{2}^{y_{1}}:X^{n}\to Y_{2}$ is
$\varepsilon_{2}$-ALKL stable, then the randomized algorithm that takes as
input a sample $S$, draws $\bm{y}_{1}\sim\mathcal{M}_{1}(S)$,
$\bm{y}_{2}\sim\mathcal{M}_{2}^{\bm{y}_{1}}(S)$, and outputs
$\bm{y}=(\bm{y}_{1},\bm{y}_{2})$ is $(\varepsilon_{1}+\varepsilon_{2})$-ALKL
stable.

The second component of Fact 4.1 says that ALKL stability composes adaptively:
To bound the ALKL stability of a mechanism, it is sufficient to bound the ALKL
stability of each individual step. Taken together with the first part of Fact
4.1, that ALKL stability upper bounds mutual information, it gives a
convenient way to uppder bound the mutual information of a mechanism
$\mathcal{M}$ and its input.

In this work, we will not directly bound the ALKL stability of subsampling
queries. Instead, we find it easier to first introduce the following
intermediate notion of stability.

######  Definition 13 (Average leave-one-out $\chi^{2}$ stability, Definition
8 restated).

A randomized algorithm $\mathcal{M}:X^{n}\to Y$ is $\varepsilon$-$\chi^{2}$
stable with respect to a randomized algorithm $\mathcal{M}^{\prime}:X^{n-1}\to
Y$ if, for all samples $S\in X^{n}$,

$\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\chi^{2}}\big{(}{\mathcal{M}(S)}\big{\|}{\mathcal{M}^{\prime}(S_{-\bm{i}})}\big{)}\right]\leq\varepsilon.$

We simply say that $\mathcal{M}$ is $\varepsilon$-$\chi^{2}$ stable if there
exists some $\mathcal{M}$’ with respect to which it is
$\varepsilon$-$\chi^{2}$ stable.

The key technical advantage of $\chi^{2}$ stability is its quadratic nature.
This makes it more amenable to the techniques of linear algebra used in
Section 5. Interestingly, $\chi^{2}$ does not appear to directly satisfy the
same notion of adaptive composability satisfied by ALKL stability. However, we
are able to show that it implies ALKL stability, and take advantage of its
adaptive composition properties.

######  Theorem 10 ($\chi^{2}$ to ALKL stability).

If $\mathcal{M}:X^{n}\to Y$ is $\varepsilon$-ALKL stable with respect to
$\mathcal{M}^{\prime}:X^{n-1}\to Y$,

  1. 1.

It is $\varepsilon^{\prime}$-ALKL stable for

$\varepsilon^{\prime}\coloneqq\varepsilon\cdot(3+2\log(|Y|/\varepsilon)).$

Note that this is with respect to a _different_ randomized algorithm than
$\mathcal{M}^{\prime}$.666Indeed, without further assumptions, there may not
exist any finite $\varepsilon^{\prime}$ for which $\mathcal{M}$ is
$\varepsilon^{\prime}$-ALKL stable with respect to $\mathcal{M}^{\prime}$.

  2. 2.

If for some $\tau\in(0,1]$, all $S\in X^{n}$, $i\in[n]$, and $y\in Y$,
$\mathcal{M}^{\prime}(S_{-i})(y)\geq\tau\cdot\mathcal{M}(S)(y)$, then
$\mathcal{M}$ is $\varepsilon^{\prime}$-ALKL stable with respect to
$\mathcal{M}^{\prime}$ for

$\varepsilon^{\prime}\coloneqq\varepsilon\cdot\left(1+\log(1/\tau)\right).$
(6)

The proof of Theorem 10 uses the following two technical propositions relating
KL and $\chi^{2}$-divergences.

######  Proposition 4.2.

For any distributions $\mathcal{D}$, $\mathcal{E}$ supported on $Y$, if for
any $\tau\in(0,1]$ and all $y\in Y$,
$\mathcal{E}(y)\geq\tau\cdot\mathcal{D}(y)$, then

$d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)\leq(1+\log(1/\tau))\cdot
d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right).$

###### Proof.

Let $\bm{y}$ be drawn $\bm{y}\sim\mathcal{D}$ and $\bm{t}$ be the random
variable $\bm{t}\coloneqq\frac{\mathcal{E}(\bm{y})}{\mathcal{D}(\bm{y})}$.
Then, we can write KL-divergence and $\chi^{2}$-divergence as

$d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)\coloneqq\mathop{{\mathds{E}}\/}\left[-\log\bm{t}\right]\quad\quad\quad\text{and}\quad\quad\quad
d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)\coloneqq\mathop{{\mathds{E}}\/}\left[(\bm{t}-1)^{2}\right].$

Note that

$\mathop{{\mathds{E}}\/}[\bm{t}]=\sum_{y\in
Y}\mathcal{D}(y)\frac{\mathcal{E}(\bm{y})}{\mathcal{D}(\bm{y})}=\sum_{y\in
Y}\mathcal{E}(\bm{y})=1.$

Therefore, we can equivalently write KL-divergence in the following form

$d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)=\mathop{{\mathds{E}}\/}\left[-\log\bm{t}+(\bm{t}-1)\right].$

We claim that for all $t>0$,

$-\log t+(t-1)\leq\begin{cases}\frac{1}{2}(t-1)^{2}&\text{if }t\geq 1\\\
(1-\log t)\cdot(t-1)^{2}&\text{if }0<t<1.\end{cases}$ (7)

For $t\geq 1$, consider the function
$f(t)\coloneqq\frac{1}{2}(t-1)^{2}-\left(-\log t+(t-1)\right)$. It satisfies
$f(1)=0$ and $f^{\prime}(t)=(t-1)^{2}/t$, which is nonnegative for $t\geq 0$.
Therefore, $f(t)>0$ for all $t\geq 1$, which is sufficient for the first case
in Equation 7.

For the second case of $t\in(0,1)$, consider the function
$g(t)\coloneqq(1-\log t)\cdot(t-1)^{2}-\left(-\log t+(t-1)\right)$. It
satisfies $g(1)=0$ and $g^{\prime}(t)=(t-1)(1-2\log t)$. That derivative is
nonpositive for $t\in(0,1)$, so $g(t)\geq 0$ for all $t\in(0,1)$, proving the
second case of Equation 7.

Finally, we use the fact that for all $t$ in the support of $\bm{t}$,
$t\geq\tau$ where $\tau\in(0,1]$. This gives

$\displaystyle
d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)$
$\displaystyle=\mathop{{\mathds{E}}\/}\left[-\log\bm{t}+(\bm{t}-1)\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}\left[(1-\log\tau)\cdot(\bm{t}-1)^{2}\right]$
$\displaystyle=(1+\log(1/\tau))\cdot
d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right).\qed$

######  Proposition 4.3.

For any distributions $\mathcal{D}$, $\mathcal{E}$ supported on $Y$ and
$\tau\in(0,1]$, let $\mathcal{E}^{\prime}$ be the mixture distribution
$\mathcal{E}^{\prime}=(1-\tau)\cdot\mathcal{E}+\tau\cdot\mathrm{Unif}(Y)$.
Then,

$d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}^{\prime}}\right)\leq(1+\log(|Y|/\tau))\cdot(d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)+\tau)+\tau.$

###### Proof.

As in the proof of Proposition 4.2 let $\bm{y}$ be drawn
$\bm{y}\sim\mathcal{D}$ and $\bm{t}$ be the random variable
$\bm{t}\coloneqq\frac{\mathcal{E}(\bm{y})}{\mathcal{D}(\bm{y})}$. We also
define

$\bm{t}^{\prime}\coloneqq\frac{\mathcal{E}^{\prime}(\bm{y})}{\mathcal{D}(\bm{y})}=\frac{(1-\tau)\cdot\mathcal{E}(\bm{y})+\frac{\tau}{|Y}|}{\mathcal{D}(\bm{y})}=(1-\tau)\cdot\bm{t}+\frac{\tau}{|Y|\cdot\mathcal{D}(\bm{y})}.$

Let $f(t)\coloneqq-\log t+t-1$. We claim that, for all $t,\Delta>0$,

$f(t+\Delta)\leq(1-\log\min(1,\Delta))\cdot(t-1)^{2}+\Delta.$ (8)

The proof of Equation 8 is separated into three cases.

  1. Case 1:

$t\geq 1$. Here, we use that $f^{\prime}(t)\leq 1$ which means that
$f(t+\Delta)\leq f(t)+\Delta$. The desired bound follows from Equation 7 and
$(1-\log\min(1,\Delta))\geq\frac{1}{2}$.

  2. Case 2:

$t<1$ and $t+\Delta\geq 1$. Once again using $f^{\prime}(t)\leq 1$, we have
that $f(t+\Delta)\leq f(1)+(t+\Delta-1)$. The desired bound follows from
$f(1)=0$ and $(t+\Delta-1)\leq\Delta$.

  3. Case 3:

$t+\Delta<1$. Then,

$\displaystyle f(t+\Delta)$
$\displaystyle\leq(1-\log(t+\Delta))\cdot(t+\Delta-1)^{2}$ (Equation 7)
$\displaystyle\leq(1-\log(t+\Delta))\cdot(t-1)^{2}$ ($t+\Delta<1$)
$\displaystyle\leq(1-\log\Delta)(t-1)^{2}.$

Applying Equation 8 and using the fact that $\mathcal{D}(\bm{y})\leq 1$,

$f(\bm{t}^{\prime})=f\left((1-\tau)\cdot\bm{t}+\frac{\tau}{|Y|\cdot\mathcal{D}(\bm{y})}\right)\leq\left(1-\log\left(\frac{\tau}{|Y|}\right)\right)\cdot((1-\tau)\cdot\bm{t}-1)^{2}+\frac{\tau}{|Y|\cdot\mathcal{D}(\bm{y})}.$

For any $c\in[0,1]$ and $t\in R$,

$(ct-1)^{2}-(t-1)^{2}=(c^{2}-1)\left(t-\frac{1}{c+1}\right)^{2}+\frac{c-1}{c+1}\leq\frac{1-c}{1+c}\leq
1-c.$ (9)

Finally, we bound,

$\displaystyle
d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}^{\prime}}\right)$
$\displaystyle=\mathop{{\mathds{E}}\/}[f(\bm{t}^{\prime})]\leq\mathop{{\mathds{E}}\/}\left[\left(1-\log\left(\frac{\tau}{|Y|}\right)\right)\cdot((1-\tau)\cdot\bm{t}-1)^{2}+\frac{\tau}{|Y|\cdot\mathcal{D}(\bm{y})}\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}\left[\left(1-\log\left(\frac{\tau}{|Y|}\right)\right)\cdot((\bm{t}-1)^{2}+\tau)+\frac{\tau}{|Y|\cdot\mathcal{D}(\bm{y})}\right]$
(Equation 9)
$\displaystyle=\left(1+\log\left(\frac{|Y|}{\tau}\right)\right)\cdot\left(\tau+d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)\right)+\sum_{y\in
Y}\mathcal{D}(y)\cdot\frac{\tau}{|Y|\cdot\mathcal{D}(y)}$
$\displaystyle=\left(1+\log\left(\frac{|Y|}{\tau}\right)\right)\cdot\left(\tau+d_{\chi^{2}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)\right)+\tau.\qed$

We conclude this section with a proof of Theorem 10.

###### Proof.

We begin with the first case, aiming to prove that there is a mechanism
$\mathcal{M}^{\prime\prime}$ with respect to which $\mathcal{M}$ is
$\varepsilon^{\prime}$-ALKL stable for
$\varepsilon^{\prime}\coloneqq\varepsilon\cdot(3+2\log(|Y|/\varepsilon))$.
Given a sample $S_{-i}\in X^{n-1}$, $\mathcal{M}^{\prime\prime}$ runs
$\bm{y}\sim\mathcal{M}^{\prime}(S_{-i})$. With probability $(1-\varepsilon)$,
it outputs $\bm{y}$. Otherwise, with probability $\varepsilon$, it output a
draw from $\mathrm{Unif}(Y)$. Then, for any $S\in X^{n}$,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}$
$\displaystyle\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}(S)}\big{\|}{\mathcal{M}^{\prime\prime}(S_{-\bm{i}})}\big{)}\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}(S)}\big{\|}{(1-\varepsilon)\cdot\mathcal{M}^{\prime}(S_{-\bm{i}})+\varepsilon\cdot\mathrm{Unif}(Y)}\big{)}\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[(1+\log(|Y|/\varepsilon))\cdot(d_{\chi^{2}}\left({\mathcal{M}(S)}\middle\|{\mathcal{M}^{\prime}(S_{-\bm{i}})}\right)+\varepsilon)+\varepsilon\right]$
(Proposition 4.3)
$\displaystyle=(1+\log(|Y|/\varepsilon))\cdot\left(\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\chi^{2}}\left({\mathcal{M}(S)}\middle\|{\mathcal{M}^{\prime}(S_{-\bm{i}})}\right)\right]+\varepsilon\right)+\varepsilon$
(Linearity of expectation)
$\displaystyle\leq(1+\log(|Y|/\varepsilon))\cdot\left(\varepsilon+\varepsilon\right)+\varepsilon$
($\mathcal{M}$ is $\varepsilon$-$\chi^{2}$ stable w.r.t.
$\mathcal{M}^{\prime}$)
$\displaystyle=\varepsilon\cdot(3+2\log(|Y|/\varepsilon))=\varepsilon^{\prime}.$

The second case is similar, but we apply Proposition 4.2 instead of
Proposition 4.3. Letting $\tau$ be as defined in the statement of Theorem 10,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}$
$\displaystyle\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}(S)}\big{\|}{\mathcal{M}^{\prime\prime}(S_{-\bm{i}})}\big{)}\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[(1+\log(1/\tau))\cdot
d_{\chi^{2}}\left({\mathcal{M}(S)}\middle\|{\mathcal{M}^{\prime}(S_{-\bm{i}})}\right)\right]$
(Proposition 4.2)
$\displaystyle=(1+\log(1/\tau))\cdot\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\chi^{2}}\left({\mathcal{M}(S)}\middle\|{\mathcal{M}^{\prime}(S_{-\bm{i}})}\right)\right]$
(Linearity of expectation) $\displaystyle\leq(1+\log(1/\tau))\cdot\varepsilon$
($\mathcal{M}$ is $\varepsilon$-$\chi^{2}$ stable w.r.t.
$\mathcal{M}^{\prime}$) $\displaystyle=\varepsilon^{\prime}.$

∎

##  5 Bounding the mutual information

In this section, we’ll use $\chi^{2}$ stability to bound the mutual
information between the sample $\bm{S}$ and the sequence of responses of the
analyst $\bm{y}_{1},\ldots,\bm{y}_{T}$. Explicitly, we’ll prove the following.

######  Theorem 11 (Formal version of Theorem 8).

For any deterministic analyst $\mathcal{A}$, distribution $\mathcal{D}$, and
sample size $n\geq 2$, draw $\bm{S}\sim\mathcal{D}^{n}$. For each $t\in[T]$,
let $\phi_{t}=\mathcal{A}(t,\bm{y}_{1},\ldots,\bm{y}_{t-1})$ and
$\bm{y}_{t}\sim\phi^{(n)}_{t}(\bm{S})$, then

$I(\bm{S};(\bm{y}_{1},\ldots,\bm{y}_{T}))\leq
n\cdot\mathop{{\mathds{E}}\/}\left[\sum_{t\in{T}}\mathrm{cost}(\phi_{t})\right]$

where the cost of a $p$-uniform query $\phi:X^{w}\to Y$ is

$\mathrm{cost}(\phi)\coloneqq\frac{w(|Y|-1)}{(n-1)(n-w)}\cdot\min\left(5+4\log
n,1+\log\left(1+\frac{w}{np}\right)\right).$

Before proving Theorem 11, we’ll be explicit about all sources of randomness.
The strategy of the analyst, mapping previous query responses to each new
query, is assumed to be deterministic. This is without loss of generality (see
Lemma 3.1) and to simplify notation. Recall, from Definition 5, for
$\phi:X^{w}\to Y$, it must be the case that for every $S^{\prime}\in X^{w}$
and $y\in Y$, $\operatorname{{Pr}}[\phi(S^{\prime})=y]\geq p$. For any $p>0$,
this requires that the query $\phi$ have a random output. Therefore, the
explicit sampling process is:

  1. 1.

A sample $\bm{S}\sim\mathcal{D}^{n}$ is sampled.

  2. 2.

At each time step $t\in[T]$, as a _deterministic_ function of previous
responses $\bm{y}_{1},\ldots,\bm{y}_{t-1}$, the analyst chooses a query
$\phi_{t}:X^{w}\to Y$. This query is answered by first subsampling
$\bm{S}^{\prime}\sim\binom{\bm{S}}{w}$ and then drawing a response
$\bm{y}_{t}\sim\phi_{t}(\bm{S}^{\prime})$.

The main technical ingredient of Theorem 11 is the following bound on the
$\chi^{2}$-stability of a single (possibly randomized) subsampling query.

######  Lemma 5.1.

For any query $\phi:X^{w}\to Y$, $\phi^{(n)}$ is $\varepsilon$-$\chi^{2}$
stable with respect to $\phi^{(n-1)}$ for

$\varepsilon\coloneqq\frac{w(|Y|-1)}{(n-1)(n-w)}.$

Lemma 5.1 is an easy corollary of the following, slightly more general, lemma.

######  Lemma 5.2.

For any nonnegative integers $w\leq n-1$, and $f:\binom{[n]}{w}\to\mathds{R}$,

$\mathop{{\bf
Var}\/}_{\bm{i}\sim[n]}\left[\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[f({\bm{T}})\mid
i\notin{\bm{T}}]\right]\leq\frac{w}{(n-1)(n-w)}\mathop{{\bf
Var}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[f({\bm{T}})].$ (10)

###### Proof of Lemma 5.1 from Lemma 5.2.

Fix a sample $S\in X^{n}$. For each $y\in Y$, we define,
$f_{y}:\binom{[n]}{w}\to\mathds{R}$ which, upon receiving
$i_{1},\ldots,i_{w}\in[n]$, outputs
$\operatorname{{Pr}}[\phi(S_{i_{1}},\ldots,S_{i_{w}})=y]$. Then,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}$
$\displaystyle\left[d_{\chi^{2}}\big{(}{\phi^{(n)}(S)}\big{\|}{\phi^{(n-1)}(S_{-\bm{i}})}\big{)}\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[\sum_{y\in
Y}\frac{\left(\phi^{(n)}(S)(y)-\phi^{(n-1)}(S_{-\bm{i}})(y)\right)^{2}}{\phi^{(n)}(S)(y)}\right]$
$\displaystyle=\sum_{y\in Y}\frac{\mathop{{\bf
Var}\/}_{\bm{i}\sim[n]}[\phi^{(n-1)}(S_{-\bm{i}})(y)]}{\phi^{(n)}(S)(y)}$
($\phi^{(n)}(S)(y)=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}[\phi^{(n-1)}(S_{-\bm{i}})(y)$)
$\displaystyle=\sum_{y\in Y}\frac{\mathop{{\bf
Var}\/}_{\bm{i}\sim[n]}[\phi^{(n-1)}(S_{-\bm{i}})(y)]}{\phi^{(n)}(S)(y)(1-\phi^{(n)}(S)(y))}\cdot(1-\phi^{(n)}(S)(y))$

Note that for any random variable $\bm{x}$ bounded within $[0,1]$ with mean
$\mu$, $\mathop{{\mathds{E}}\/}[\bm{x}^{2}]\leq\mu$ and so $\mathop{{\bf
Var}\/}[\bm{x}]\leq\mu(1-\mu)$. Applying this to the random variable
$f_{y}({\bm{T}})$ gives a lower bound on the denominator in the above
expression, and so,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\chi^{2}}\big{(}{\phi^{(n)}(S)}\big{\|}{\phi^{(n-1)}(S_{-\bm{i}})}\big{)}\right]$
$\displaystyle\leq\sum_{y\in Y}\frac{\mathop{{\bf
Var}\/}_{\bm{i}\sim[n]}\left[\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[f_{y}({\bm{T}})\mid
i\notin{\bm{T}}]\right]}{\mathop{{\bf
Var}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[f_{y}({\bm{T}})]}\cdot(1-\phi^{(n)}(S)(y))$
$\displaystyle\leq\sum_{y\in Y}\frac{w}{(n-1)(n-w)}\cdot(1-\phi^{(n)}(S)(y))$
(Lemma 5.2) $\displaystyle=\frac{w}{(n-1)(n-w)}\cdot\left(|Y|-\sum_{y\in
Y}\phi^{(n)}(S)(y)\right)$
$\displaystyle=\frac{w(|Y|-1)}{(n-1)(n-w)}=\varepsilon.$

Since this holds for any $S\in X^{n}$, $\phi^{(n)}$ is
$\varepsilon$-$\chi^{2}$ stable w.r.t. $\phi^{(n-1)}$. ∎

###### Proof of Lemma 5.2.

In order to prove Lemma 5.2, it is sufficient to restrict ourselves to
mean-$0$ functions $f$, as both sides of Equation 10 are invariant to
translations. We’ll consider the vector space of all such functions

$\mathcal{V}\coloneqq\left\\{f:\binom{[n]}{w}\to\mathds{R}\,\bigg{|}\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[f({\bm{T}})]=0\right\\},$

endowed with the inner product

$\langle
f,g\rangle\coloneqq\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[f({\bm{T}})g({\bm{T}})].$

With this choice of inner product, for any $f\in\mathcal{V}$, $\mathop{{\bf
Var}\/}[f]=\langle f,f\rangle=\|f\|^{2}$. Defining
$\phi:\mathcal{V}\times\mathcal{V}\to\mathds{R}$,

$\phi(f,g)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[f({\bm{T}})\mid\bm{i}\notin
T]\cdot\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\binom{[n]}{w}}[g({\bm{T}})\mid\bm{i}\notin
T]\right].$

we have that for any mean-zero $f$, the left hand side of Equation 10 is equal
to $\phi(f,f)$. Clearly $\phi$ is bilinear, symmetric, and positive semi-
definite. Our goal is to find the maximum $\phi(f,f)$ among $f$ with
$\|f\|\leq 1$, which is just the maximum eigenvalue of the linear map
corresponding to $\phi$. We’ll show that this maximum occurs for a _linear_
$f$, where linear functions are defined as

$\mathcal{L}\coloneqq\left\\{T\mapsto\sum_{i\in
T}\alpha_{i}\bigg{|}\,\alpha\in\mathds{R}^{n}\right\\}\subseteq\mathds{R}^{\binom{[n]}{w}}.$
(11)

Consider any $f\in\mathcal{V}$ that is orthogonal to every linear function.
Since the function $T\mapsto\mathds{1}[i\notin T]$ is linear777This function
is formed by setting $\alpha_{j}=\frac{1}{w}-\mathds{1}[j=i]$ in Equation 11.,
for any $i\in[n]$, we have that $\mathop{{\mathds{E}}\/}[f({\bm{T}})\mid
i\notin{\bm{T}}]=0$. Therefore, for any $g\in\mathcal{V}$,

$\phi(f,g)=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[0\cdot\mathop{{\mathds{E}}\/}[g({\bm{T}})\mid\bm{i}\notin
T]\right]=0.$

As a result, all $f$ in $\mathcal{L}^{\perp}$ are in the kernel of the linear
map corresponding to $\phi$. Hence, to find the maximum of $\phi(f,f)$ among
$\|f\|\leq 1$, it is sufficient to just consider linear functions. Pick an
arbitrary mean-zero $\alpha\in\mathds{R}^{n}$ and set $f=T\mapsto\sum_{i\in
T}\alpha_{i}$. We compute the variance of $f$:

$\displaystyle\|f\|^{2}$
$\displaystyle=\mathop{{\mathds{E}}\/}[f({\bm{T}})^{2}]$
$\displaystyle=\mathop{{\mathds{E}}\/}\left[\left(\sum_{i\in{\bm{T}}}\alpha_{i}\right)^{2}\right]$
$\displaystyle=\sum_{i\in[n]}\operatorname{{Pr}}[i\in{\bm{T}}]\alpha_{i}^{2}+\sum_{i\neq
j}\operatorname{{Pr}}[i,j\in{\bm{T}}]\alpha_{i}\alpha_{j}$ (Linearity of
expectation)
$\displaystyle=\frac{w}{n}\sum_{i\in[n]}\alpha_{i}^{2}+\frac{w(w-1)}{n(n-1)}\sum_{i\neq
j}\alpha_{i}\alpha_{j}$
$\displaystyle=\frac{w}{n}\left(\sum_{i\in[n]}\alpha_{i}\cdot\left(\alpha_{i}+\frac{w-1}{n-1}\sum_{j\neq
i}\alpha_{j}\right)\right)$
$\displaystyle=\frac{w}{n}\left(\sum_{i\in[n]}\alpha_{i}\cdot\left(\frac{n-w}{n-1}\alpha_{i}+\frac{w-1}{n-1}\sum_{j\in[n]}\alpha_{j}\right)\right)$
$\displaystyle=\frac{w}{n}\left(\sum_{i\in[n]}\alpha_{i}\cdot\left(\frac{n-w}{n-1}\alpha_{i}\right)\right)$
($f$ is mean-zero)
$\displaystyle=\frac{w(n-w)}{n(n-1)}\sum_{i\in[n]}\alpha_{i}^{2}.$

Finally, we bound $\phi(f,f)$. In order to do so, we first compute, for any
$i\in[n]$

$\displaystyle\mathop{{\mathds{E}}\/}[f({\bm{T}})\mid i\notin{\bm{T}}]$
$\displaystyle=\sum_{j\neq i}\operatorname{{Pr}}[j\in{\bm{T}}\mid
i\notin{\bm{T}}]\cdot\alpha_{j}$ $\displaystyle=\sum_{j\neq
i}\frac{w}{n-1}\cdot\alpha_{j}$
$\displaystyle=\frac{w}{n-1}\left(\sum_{j\in[n]}\alpha_{j}\right)-\frac{w}{n-1}\alpha_{i}$
$\displaystyle=-\frac{w}{n-1}\alpha_{i}$ ($f$ is mean-zero.)

This allows us to compute,

$\displaystyle\phi(f,f)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[\mathop{{\mathds{E}}\/}[f({\bm{T}})\mid\bm{i}\notin
T]^{2}\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[\left(-\frac{w}{n-1}\alpha_{i}\right)^{2}\right]$
$\displaystyle=\frac{w^{2}}{n(n-1)^{2}}\sum_{i\in[n]}\alpha_{i}^{2}.$

Comparing the expressions for $\phi(f,f)$ and $\|f\|^{2}$, we conclude that
for any linear $f$, Equation 10 holds with equality. Since the maximum of
$\phi(f,f)$ among $f$ with $\|f\|^{2}\leq 1$ occurs for a linear function, we
are done. ∎

The next step in the proof of Theorem 11 is to convert the
$\varepsilon$-$\chi^{2}$ stability of each subsampling query to
$\varepsilon^{\prime}$-ALKL stability for appropriately chosen
$\varepsilon^{\prime}$.

######  Corollary 5.3.

For any $p$-uniform query $\phi:X^{w}\to Y$, $\phi^{(n)}$ is
$\varepsilon^{\prime}$-ALKL stable for

$\varepsilon^{\prime}\coloneqq\frac{w(|Y|-1)}{(n-1)(n-w)}\cdot\min\left(5+4\log
n,1+\log\left(1+\frac{w}{np}\right)\right).$

###### Proof.

First note that if $|Y|=1$, the query is trivially $0$-ALKL stable as its
output cannot depend on its input. Therefore, we may assume that $|Y|\geq 2$.
By Lemma 5.1, $\phi^{(n)}$ is $\varepsilon$-$\chi^{2}$ with respect to
$\phi^{(n-1)}$ for $\varepsilon=\frac{w(|Y|-1)}{(n-1)(n-w)}$. By the first
guarantee of Theorem 10, $\phi^{(n)}$ is $\varepsilon^{\prime}$-ALKL stable
for

$\displaystyle\varepsilon^{\prime}$
$\displaystyle\coloneqq\varepsilon\cdot(3+2\log(|Y|/\varepsilon))$
$\displaystyle=\varepsilon\cdot\left(3+2\log\left(\frac{|Y|}{\frac{w(|Y|-1)}{(n-1)(n-w)}}\right)\right)$
$\displaystyle=\varepsilon\cdot\left(3+2\log\left(\frac{|Y|}{|Y|-1}\cdot{\frac{(n-1)(n-w)}{w}}\right)\right)$
$\displaystyle\leq\varepsilon\cdot\left(3+2\log\left(2n^{2}\right)\right)$
($|Y|\geq 2,w\geq 1$) $\displaystyle=\varepsilon\cdot\left(3+2\log 2+4\log
n\right)\leq\varepsilon\cdot(5+4\log n).$

This gives the first of the two desired bounds. For the other bound, we take
advantage of the $p$-uniformity of $\phi$. Consider any $S\in X^{n}$, $y\in
Y$, and $i\in[n]$. We can write,

$\displaystyle\phi^{(n)}(S)(y)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}^{\prime}\sim\binom{S}{w}}[\operatorname{{Pr}}[\phi(\bm{S}^{\prime})=y]]$
$\displaystyle=\operatorname{{Pr}}[i\in\bm{S}^{\prime}]\mathop{{\mathds{E}}\/}_{\bm{S}^{\prime}\sim\binom{S}{w}}[\operatorname{{Pr}}[\phi(\bm{S}^{\prime})=y]\mid
i\in\bm{S}^{\prime}]+\operatorname{{Pr}}[i\notin\bm{S}^{\prime}]\mathop{{\mathds{E}}\/}_{\bm{S}^{\prime}\sim\binom{S}{w}}[\operatorname{{Pr}}[\phi(\bm{S}^{\prime})=y]\mid
i\notin\bm{S}^{\prime}]$
$\displaystyle=\frac{w}{n}\mathop{{\mathds{E}}\/}_{\bm{S}^{\prime}\sim\binom{S}{w}}[\operatorname{{Pr}}[\phi(\bm{S}^{\prime})=y]+(1-\frac{w}{n})\cdot\phi^{(n-1)}(S_{-i})(y)$
$\displaystyle\leq\frac{w}{n}+(1-\frac{w}{n})\cdot\phi^{(n-1)}(S_{-i})(y)$
$\displaystyle\leq\frac{w}{np}\cdot\phi^{(n-1)}(S_{-i})(y)+(1-\frac{w}{n})\cdot\phi^{(n-1)}(S_{-i})(y)$
($\phi^{(n-1)}(S_{-i})(y)\geq p$)
$\displaystyle\leq\left(\frac{w}{np}+1\right)\cdot\phi^{(n-1)}(S_{-i})(y).$

Therefore, setting $\tau=(1+\frac{w}{np})^{-1}$, we have that
$\phi^{(n-1)}(S_{-i})(y)\geq\tau\cdot\phi^{(n)}(S)(y)$. Applying the second
guarantee of Theorem 10, $\phi^{(n)}$ is $\varepsilon^{\prime}$-ALKL stable
for

$\varepsilon^{\prime}\coloneqq\varepsilon\cdot(1+\log(1/\tau))=\varepsilon\cdot\left(1+\log\left(1+\frac{w}{np}\right)\right).$

The desired result follows from taking whichever of the two ALKL stability
bounds is better. ∎

Given the above ALKL stability bound, the proof of Theorem 11 is _almost_
completed by Fact 4.1 from [FS18] which connects ALKL stability to mutual
information. However, to directly apply Fact 4.1, we would need an _a priori_
bound on the ALKL stability of each query. Instead, we allow the analyst to
choose its query as a function of the previous responses and only require the
total cost be bounded in expectation. Specifically, we want to show an
adaptive composition of ALKL stability even when the stability parameters of
later queries are a function of prior queries responses. This has recently
been shown to hold in [FZ21]. However, their setting is slightly different,
focusing on analysts that are budgeted almost surely rather than in
expectation, so we cannot use their results black box. Instead, we prove the
following.

######  Lemma 5.4 (Generalization of Fact 4.1).

Draw $\bm{S}\sim\mathcal{D}^{n}$. Then, for each $t\in[T]$, let an analyst
choose a randomized algorithm $\mathcal{M}_{t}:X^{n}\to Y$ as a function of
$\bm{y}_{1},\ldots,\bm{y}_{t-1}$ and draw an output
$\bm{y}_{t}\sim\mathcal{M}_{t}(\bm{S})$. If $\mathcal{M}_{t}$ is
$\bm{\varepsilon}_{t}$-ALKL stable, then,

$I(\bm{S};(\bm{y}_{1},\ldots,\bm{y}_{T}))\leq
n\cdot\mathop{{\mathds{E}}\/}\left[\sum_{t\in[T]}\bm{\varepsilon}_{t}\right]$

where the expectation is taken over the analysts choices for the queries,
which in turn depends on the randomness of $\bm{S}$ and
$\bm{y}_{1},\ldots,\bm{y}_{T}$.

Theorem 11 is a direct consequence of Lemma 5.4 and Corollary 5.3. The proof
of Lemma 5.4 is mostly a matter of looking through [FS18]’s proof of Fact 4.1
and confirming that everything still holds in this more general setting.

The first statement of Fact 4.1 is a special case of the following more
general fact, implicit in [FS18]’s proof.

######  Fact 5.5 (Implicit in [FS18]’s proof of Fact 4.1).

For any randomized algorithm $\mathcal{M}:X^{n}\to Y$ and
$\bm{S}\sim\mathcal{D}^{n}$, if $\bm{y}\sim\mathcal{M}(\bm{S})$ then for any
randomized algorithm $\mathcal{M}^{\prime}:X^{n-1}\to Y$

$I(\bm{S};\bm{y})\leq
n\cdot\mathop{{\mathds{E}}\/}_{\bm{S}}\left[\mathop{{\mathds{E}}\/}_{\bm{i}\sim[n]}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}(\bm{S})}\big{\|}{\mathcal{M}^{\prime}(\bm{S}_{-\bm{i}})}\big{)}\right]\right].$

To take advantage of Fact 5.5, we’ll define the ALKL stability with respect to
a distribution. Note that if a randomized algorithm is $\varepsilon$-ALKL
stable, it is $\varepsilon$-ALKL stable with respect to all distributions.

######  Definition 14 (ALKL stability with respect to a distribution).

A randomized algorithm $\mathcal{M}:X^{n}\to Y$ is $\varepsilon$-ALKL stable
with respect to a (not necessarily product) distribution $\mathcal{D}$ over
$X^{n}$ if there is a randomized algorithm $\mathcal{M}^{\prime}:X^{n-1}\to Y$
for which

$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D},\bm{i}\sim[n]}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}(S)}\big{\|}{\mathcal{M}^{\prime}(S_{-\bm{i}})}\big{)}\right]\leq\varepsilon.$

Then, we generalize [FS18]’s adaptive composition of ALKL stability.

######  Proposition 5.6 (Adaptive composition of ALKL stability with respect
to a distribution).

For any $\mathcal{M}_{1}:X^{n}\to Y_{1}$, $\mathcal{M}_{2}:Y_{1}\times
X^{n}\to Y_{2}$, and distribution $\mathcal{D}$ over $X^{n}$ satisfying

  1. 1.

$\mathcal{M}_{1}:X^{n}\to Y_{1}$ is $\varepsilon_{1}$-ALKL stable with respect
to $\mathcal{D}$.

  2. 2.

For $\bm{S}\sim\mathcal{D}$ and any $y_{1}\in Y_{1}$,
$\mathcal{M}_{2}(y_{1},\cdot)$ is $(\varepsilon_{2}^{(y_{1})})$-ALKL stable
with respect to $(\mathcal{D}\mid\mathcal{M}_{1}(\bm{S})=y_{1})$.

The randomized algorithm mapping $S$ to
$\mathcal{M}_{2}(\mathcal{M}_{1}(S),S)$ is $\varepsilon^{\prime}$-ALKL stable
with respect to $\mathcal{D}$ for

$\varepsilon^{\prime}\coloneqq\varepsilon_{1}+\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D},\bm{y}_{1}\sim\mathcal{M}_{1}(\bm{S})}[\varepsilon_{2}^{(\bm{y}_{1})}].$

###### Proof.

This proof uses the well-known chain rule of KL divergence. For any
distributions $\mathcal{D}$ and $\mathcal{E}$ over domain $X\times Y$,

$d_{\mathrm{KL}}\left({\mathcal{D}}\middle\|{\mathcal{E}}\right)=d_{\mathrm{KL}}\left({\mathcal{D}(x)}\middle\|{\mathcal{E}(x)}\right)+\mathop{{\mathds{E}}\/}_{\bm{x}^{\prime}\sim\mathcal{D}(x)}\left[d_{\mathrm{KL}}\big{(}{\mathcal{D}(y\mid
x=x^{\prime})}\big{\|}{\mathcal{E}(y\mid x=x^{\prime})}\big{)}\right]$

where $\mathcal{D}(x)$ denotes the marginal distribution of $\mathcal{D}$ over
$X$ and $\mathcal{D}(y\mid x=x^{\prime})$ its conditional distribution over
$Y$. Then, we bound

$\displaystyle\varepsilon^{\prime}$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D},\bm{i}\sim[n]}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}_{2}(\mathcal{M}_{1}(\bm{S}),\bm{S})}\big{\|}{\mathcal{M}_{2}^{\prime}(\mathcal{M}_{1}^{\prime}(\bm{S}_{-\bm{i}}),\bm{S}_{-\bm{i}})}\big{)}\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D},\bm{i}\sim[n]}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}_{1}(\bm{S})}\big{\|}{\mathcal{M}_{1}^{\prime}(\bm{S})}\big{)}\right]+\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D},\bm{i}\sim[n],\bm{y}_{1}}\left[d_{\mathrm{KL}}\big{(}{\mathcal{M}_{2}(\bm{y}_{1},\bm{S})}\big{\|}{\mathcal{M}_{2}^{\prime}(\bm{y}_{1},\bm{S})}\big{)}\right]$
$\displaystyle=\varepsilon_{1}+\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D},\bm{y}_{1}\sim\mathcal{M}_{1}(\bm{S})}[\varepsilon_{2}^{(\bm{y}_{1})}].\qed$

###### Proof of Lemma 5.4.

By repeatedly applying Proposition 5.6, the mechanism that takes as input
$\bm{S}$ and outputs $\bm{y}=(\bm{y}_{1},\ldots,\bm{y}_{t})$ is
$\left(\mathop{{\mathds{E}}\/}\left[\sum_{t\in[T]}\bm{\varepsilon}_{t}\right]\right)$-ALKL
stable w.r.t. $\mathcal{D}^{n}$. The desired result follows from Fact 5.5. ∎

##  6 From small mutual information to small bias

In this section, we connect a mutual information bound to generalization
error, completing the proof of Theorem 3 and its generalization in Theorem 5.
Recall our definition of _error_ for a test query.

######  Definition 15 (Definition 4, restated).

For any $\psi:X^{w}\to[0,1]$ and distribution $\mathcal{D}$ over $X$, we
define

$\mathrm{error}(\psi,S,\mathcal{D})\coloneqq\frac{1}{w}\cdot\min\left(\Delta,\frac{\Delta^{2}}{\sigma^{2}}\right)$

where

$\Delta\coloneqq|\psi(S)-\psi(\mathcal{D})|\quad\quad\text{and}\quad\quad\sigma^{2}\coloneqq\mathop{{\bf
Var}\/}_{\bm{S}\sim\mathcal{D}^{w}}[\psi(\bm{S})].$

Note that if a query has error $\varepsilon$, this corresponds to
$\Delta=O(w\varepsilon+\sqrt{w\varepsilon\sigma^{2}})$.

######  Theorem 12 (Mutual information bounds bias).

For any $\bm{S}\sim\mathcal{D}^{n}$ and $\bm{y}\in Y$, as well as
$\Psi^{(\bm{y})}$ a set of test queries each mapping $X^{*}\to[0,1]$ chosen as
a function of $\bm{y}$,

$\mathop{{\mathds{E}}\/}_{\bm{S},\bm{y}}\left[\sup_{\psi\in\Psi^{(\bm{y})}}\mathrm{error}(\psi,\bm{S},\mathcal{D})\right]\leq\frac{8I(\bm{S};\bm{y})+4\mathop{{\mathds{E}}\/}_{\bm{y}}\left[\log\left|\Psi^{(\bm{y})}\right|\right]+12\log
2}{n}.$

Our proof will use the following fact.

######  Fact 6.1 ([FS18]).

For any random variables $\bm{S}\in X$ and
${\bm{\psi}}:X\to\mathds{R}\in\Psi$, as well as $\lambda>0$,

$\mathop{{\mathds{E}}\/}_{\bm{S},\bm{y}}\left[{\bm{\psi}}(\bm{S})\right]\leq\frac{1}{\lambda}\left(I(\bm{S};{\bm{\psi}})+\sup_{\psi\in\Psi}\log\left(\mathop{{\mathds{E}}\/}_{\bm{S}}\left[\exp\left(\lambda\psi(\bm{S})\right)\right]\right)\right).$

######  Corollary 6.2.

For any random variables $\bm{x}\in X$ and ${\bm{f}}:X\to\mathds{R}\in F$
satisfying, for all $t\geq 0$ and $f\in F$,
$\operatorname{{Pr}}_{\bm{x}}[f(\bm{x})\geq t]\leq e^{-t}$,

$\mathop{{\mathds{E}}\/}[{\bm{f}}(\bm{x})]\leq 2(I(\bm{x};{\bm{f}})+\log 2).$

###### Proof.

Fix an arbitrary $f\in F$. We first bound the moment generating function of
$f(\bm{x})$.

$\displaystyle\mathop{{\mathds{E}}\/}[\exp(f(\bm{x})/2)]$
$\displaystyle=\int_{0}^{\infty}\operatorname{{Pr}}[\exp(f(\bm{x})/2)\geq
t]dt$ $\displaystyle=1+\int_{1}^{\infty}\operatorname{{Pr}}[f(\bm{x})\geq
2\log t]dt$ $\displaystyle\leq 1+\int_{1}^{\infty}t^{-1/2}dt=2.$

The desired result follows from Fact 6.1 with $\lambda=1/2$. ∎

_Bernstein’s inequality_ will give the sorts high probability bounds needed to
apply Corollary 6.2.

######  Fact 6.3 (Bernstein’s inequality).

For any iid mean-zero random variables $\bm{a}_{1},\ldots,\bm{a}_{n}$
satisfying $|\bm{a}_{i}|\leq 1$ almost surely and with variance $\sigma^{2}$,
let $\bm{A}=\frac{1}{n}\cdot\sum_{i\in[n]}\bm{a}_{i}$

$\operatorname{{Pr}}\left[|\bm{A}|\geq\Delta\right]\leq
2\exp\left(-\frac{\Delta^{2}n}{2(\sigma^{2}+\frac{\Delta}{3})}\right).$ (12)

For our setting, a black-box application of Bernstein’s inequality is not
sufficient. We wish to prove concentration of a random variable that is _not_
necessarily the sum of iid random variables. Fortunately, the proof of
Bernstein’s inequality only uses a bound on the moment generating function of
$\bm{A}$: It proceeds by applying Markov’s inequality to the random variable
$e^{\lambda\bm{A}}$ for an appropriate choice of $\lambda\in\mathds{R}$. As a
result, the following also holds.

######  Fact 6.4 (Generalization of Bernstein’s inequality).

Let $\bm{B}$ be any random variable satisfying, for all
$\lambda\in\mathds{R}$,

$\mathop{{\mathds{E}}\/}[e^{\lambda\bm{B}}]\leq\mathop{{\mathds{E}}\/}[e^{\lambda\bm{A}}],$

where $\bm{A}$ is as in Fact 6.3. Then, the bound of Equation 12 also holds
with $\bm{B}$ in place of $\bm{A}$.

We’ll use the following to produce a bound in our setting.

######  Proposition 6.5.

For any $\psi:X^{w}\to\mathds{R}$, distribution $\mathcal{D}$ over $X$, and
convex function $f:\mathds{R}\to\mathds{R}$, set $m=\lfloor n/w\rfloor$. Then,

$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}\left[f\left(\psi(\bm{S})\right)\right]\leq\mathop{{\mathds{E}}\/}_{\bm{S}^{(1)},\ldots,\bm{S}^{(m)}\overset{\mathrm{iid}}{\sim}\mathcal{D}^{w}}\left[f\left(\mathop{{\mathds{E}}\/}_{\bm{i}\sim[m]}\left[\psi(\bm{S}^{(i)})]\right]\right)\right].$

###### Proof.

Given $S\in X^{n}$, G, let $\mathcal{G}(S)$ be the uniform distribution over
all disjoint groupings, $\bm{S}^{(1)},\ldots,\bm{S}^{(m)}\in X^{w}$, of $S$.
In particular, $\bm{S}^{(1)}\sim\binom{S}{w}$,
$\bm{S}^{(2)}\sim\binom{S\setminus\bm{S}^{(1)}}{w}$, and so on. Note that each
$\bm{S}^{(i)}$ has a marginal distribution equal to that of a sample from
$\binom{S}{w}$. Since $mw\leq n$, all the groups are disjoint. Then,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}$
$\displaystyle\left[f\left(\psi(\bm{S})\right)\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}\left[f\left(\mathop{{\mathds{E}}\/}_{\bm{S}^{\prime}\sim\binom{\bm{S}}{w}}[\psi(\bm{S}^{\prime})]\right)\right]$
(Definition 4)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}\left[f\left(\mathop{{\mathds{E}}\/}_{\bm{i}\sim[m]}\left[\mathop{{\mathds{E}}\/}_{\bm{S}^{(1)},\ldots,\bm{S}^{(m)}\overset{\mathrm{iid}}{\sim}\binom{\bm{S}}{w}}\left[\psi(\bm{S}^{(\bm{i})})\right]\right]\right)\right]$
($\mathop{{\mathds{E}}\/}[c]=c$)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}\left[f\left(\mathop{{\mathds{E}}\/}_{\bm{S}^{(1)},\ldots,\bm{S}^{(m)}\sim\mathcal{G}(\bm{S})}\left[\mathop{{\mathds{E}}\/}_{\bm{i}\sim[m]}\left[\psi(\bm{S}^{(\bm{i})})\right]\right]\right)\right]$
($\bm{S}^{(i)}$ marginally from $\binom{\bm{S}}{w}$)
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}^{(1)},\ldots,\bm{S}^{(m)}\sim\mathcal{G}(\bm{S})}\left[f\left(\mathop{{\mathds{E}}\/}_{\bm{i}\sim[m]}\left[\psi(\bm{S}^{(i)})]\right]\right)\right]\right]$
(Jensen’s inequality)

For $\bm{S}\sim\mathcal{D}^{n}$ and
$\bm{S}^{(1)},\ldots,\bm{S}^{(m)}\sim\mathcal{G}(\bm{S})$, since the groups
are disjoint, they are each iid draws from $\mathcal{D}^{w}$. Therefore,

$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}\left[f\left(\psi(\bm{S})\right)\right]\leq\mathop{{\mathds{E}}\/}_{\bm{S}^{(1)},\ldots,\bm{S}^{(m)}\overset{\mathrm{iid}}{\sim}\mathcal{D}^{w}}\left[f\left(\mathop{{\mathds{E}}\/}_{\bm{i}\sim[m]}\left[\psi(\bm{S}^{(i)})]\right]\right)\right]\qed$

Since $x\to\exp{\lambda x}$ is convex, we arrive at the following corollary.

######  Corollary 6.6.

For any $\psi:X^{w}\to[-1,1]$ and distribution $\mathcal{D}$ over $X$ such
that $\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{w}}[\psi(\bm{S})]=0$ and
$\mathop{{\bf Var}\/}_{\bm{S}\sim\mathcal{D}^{w}}[\phi(\bm{S})]=\sigma^{2}$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[|\psi(\bm{S})|\geq\Delta]\leq
2\exp\left(-\frac{\Delta^{2}m}{2(\sigma^{2}+\frac{\Delta}{3})}\right)\leq
2\exp\left(-\frac{m}{2}\min(\Delta,\Delta^{2}/\sigma^{2})\right)$

where $m\coloneqq\left\lfloor\frac{n}{w}\right\rfloor$.

Finally, we complete the proof of Theorem 12.

###### Proof of Theorem 12.

For each $y\in Y$, we define $f^{(y)}:X^{n}\to\mathds{R}$ as

$f^{(y)}(S)\coloneqq\sup_{\psi\in\Psi^{(y)}}\frac{n\cdot\mathrm{error}(\psi,S,\mathcal{D})}{4}-\log(2|\Psi^{(y)}|).$

We claim that for all $y\in Y$ and $t>0$,
$\operatorname{{Pr}}[f^{(y)}(\bm{S})\geq t]\leq e^{-t}$. First, consider a
single test function $\psi:X^{w}\to[0,1]$. By Corollary 6.6 applied to the
centered query $\psi^{\prime}\coloneqq\psi-\psi(\mathcal{D})$, as well as the
bound $n/(2w)\leq m$ when $m\coloneqq\lfloor n/w\rfloor$

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathrm{error}(\psi,\bm{S},\mathcal{D})\cdot
n/4\geq\varepsilon]\leq 2\exp(-\varepsilon)$

By the union bound,

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}}[f^{(y)}(\bm{S})\geq
t]$ $\displaystyle\leq
2\sum_{\psi\in\Psi^{(y)}}\operatorname{{Pr}}\left[\frac{n\cdot\mathrm{error}(\psi,\bm{S},\mathcal{D})}{4}-\log(2|\Psi^{(y)}|)\geq
t\right]$ $\displaystyle\leq 2|\Psi^{(y)}|\cdot e^{-t-2|\Psi^{(y)}|}=e^{-t}.$

Therefore, by Corollary 6.2,

$\mathop{{\mathds{E}}\/}_{\bm{S},\bm{y}}\left[\sup_{\psi\in\Psi^{(\bm{y})}}\frac{n\cdot\mathrm{error}(\psi,\bm{S},\mathcal{D})}{4}-\log(2|\Psi^{(\bm{y})}|)\right]\leq
2(I(\bm{S};\bm{y})+\log 2).$

Rearranging yields,

$\mathop{{\mathds{E}}\/}_{\bm{S},\bm{y}}\left[\sup_{\psi\in\Psi^{(\bm{y})}}\mathrm{error}(\psi,\bm{S},\mathcal{D})\right]\leq\frac{8I(\bm{S};\bm{y})+4\mathop{{\mathds{E}}\/}_{\bm{y}}\left[\log\left|\Psi^{(\bm{y})}\right|\right]+12\log
2}{n}.\qed$

We’ve now assembled all the ingredients to prove Theorem 3 and the first part
of Theorem 5.

###### Proof.

Theorem 3 is a special case of the first part of Theorem 5, so we only prove
the later. Since the error of a query is trivially upper bounded by $1$,
Theorem 5 is vacuous if $n=1$. Therefore, without loss of generality, we may
assume that $n\geq 2$.

Let $\bm{y}\coloneqq\bm{y}_{1},\ldots,\bm{y}_{T}$ be the queries responses. If
the $t^{\text{th}}$ query is $p_{t}$-uniform and maps $X^{w_{t}}$ to $Y_{t}$,
by Theorem 11

$\displaystyle I(\bm{S};\bm{y})$ $\displaystyle\leq
n\cdot\mathop{{\mathds{E}}\/}\left[\sum_{t\in
T}\frac{w_{t}(|Y_{t}|-1)}{(n-1)(n-w_{t})}\cdot\min\left(5+4\log
n,1+\log\left(1+\frac{w_{t}}{np_{t}}\right)\right)\right]$ $\displaystyle\leq
10\cdot\mathop{{\mathds{E}}\/}\left[\sum_{t\in
T}\frac{w_{t}Y_{t}}{(n-w_{t})}\cdot\min\left(1+\log
n,1+\log\left(1+\frac{w_{t}}{np_{t}}\right)\right)\right]$ ($\frac{n}{n-1}\leq
2$)

The desired result then follows from Theorem 12. ∎

For completeness, we further show that Theorem 2 is an easy consequence of
Theorem 3.

###### Proof of Theorem 2 from Theorem 3.

First note that if $w>n/2$, the guarantee of Theorem 2 is vacuous. Therefore,
we may assume that $w\leq n/2$. Clearly, the analyst in Theorem 2 is
$(\mathrm{cost}_{n},b)$-budgeted for

$b\coloneqq\frac{tw|Y|\log n}{n-w}\leq\frac{2tw|Y|\log n}{n}.$

The analyst can choose, for each query $\phi_{t}$ and outcome $y\in Y$, a test
function $\psi_{t,y}(S)\coloneqq\mathds{1}[\phi_{t}(S)=y]$. The total number
of test functions is $m\coloneqq t|Y|$. If $m>n^{2}$, then, once again, the
guarantee of Theorem 2 is vacuous, so we assume $m\leq n^{2}$. Applying
Theorem 3 as well as the inequality
$\left(\psi(S)-\psi(\mathcal{D})\right)^{2}\leq
w\cdot\mathrm{error}(\psi,S,\mathcal{D})$ gives

$\mathop{{\mathds{E}}\/}\left[\sup_{t\in[T],y\in
Y}\left(\phi^{(n)}_{t}(\bm{S})(y)-\phi^{(\mathrm{dist})}_{T}(\mathcal{D})(y)\right)^{2}\right]\leq
O\left(w\frac{b+\log(n^{2})+1}{n}\right)\leq O\left(w\log
n\cdot\left(\frac{tw|Y|}{n^{2}}+\frac{1}{n}\right)\right)$

as desired. ∎

##  7 Boosting the success probability

Theorem 3 proves that, with constant success probability, the analyst cannot
find a test on which the sample is biased. In this section, we prove Theorem 4
showing that, when all of the analysts queries $\phi:X^{w}\to Y$ satisfy
$w=1$, that guarantee holds with high probability. We do this via a reduction
from small failure probability to constant failure probability.

Notation Throughout this section, we will only consider analysts who make
queries of the form $\phi:X\to Y$ and tests of the form $\psi:X\to[0,1]$
(corresponding to $w=1$), and analysts that only output a single test. Given
an analyst $\mathcal{A}$ and sample $S\in X^{n}$, we’ll use the notation
$\mathcal{A}(S)$ as shorthand for the distribution of tests $\mathcal{A}$ asks
on the sample $S$. I.e., ${\bm{\psi}}\sim\mathcal{A}(S)$ is shorthand for, at
each $t\in[T]$, setting $\phi_{t}=\mathcal{A}(\bm{y}_{1},\ldots,\bm{y}_{t-1})$
and $\bm{y}_{t}\sim\phi^{(n)}_{t}(S)$, and then setting
${\bm{\psi}}=\mathcal{A}(\bm{y}_{1},\ldots,\bm{y}_{T})$.

######  Lemma 7.1 (Boosting from constant to small failure probability).

For any distribution $\mathcal{D}$ over $X$, sample size $n$, budget $b$, cost
function $\mathrm{cost}$, and threshold $\tau_{\psi}\in[0,1]$ for each
$\psi:X\to[0,1]$, suppose that for all analysts $\mathcal{A}$ that are
$(\mathrm{cost},b)$-budgeted almost surely,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n},{\bm{\psi}}\sim\mathcal{A}(\bm{S})}[\psi(\bm{S})\geq\tau_{\psi}]\leq\frac{1}{100}.$

Then, for any sample size $N\geq n$, $k=\lfloor N/n\rfloor$, and all analysts
$\mathcal{A}^{\prime}$ that are $(\mathrm{cost},B\coloneqq bk/100)$-budgeted
almost surely,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{N},{\bm{\psi}}\sim\mathcal{A}^{\prime}(\bm{S})}\left[\psi(\bm{S})\geq\tau_{\psi}+1/n\right]\leq\exp(-\Omega(k)).$

At a high level, the proof of Lemma 7.1 exploits a classic and well-known
technique for boosting success probabilities: Given an algorithm that fails
with constant probability, if we run $k$ independent copies, with probability
$1-2^{-\Omega(k)}$, a large fraction of those copies will succeed. Typically,
this technique gives a framework for modifying existing algorithms – for
example, by taking the majority of multiple independent runs – in order to
produce a new algorithm with a small failure probability.

Interestingly, in our setting, no modification to the algorithm is necessary.
If we answer subsampling queries in the most natural way, they “automatically”
boost their own success probability. The key insight is a single large sample
$\bm{S}\sim\mathcal{D}^{N\coloneqq nk}$ can be cast as $k$ groups of samples
$\bm{S}^{(1)},\ldots,\bm{S}^{(k)}\overset{\mathrm{iid}}{\sim}\mathcal{D}^{n}$
and the output of a query $\bm{y}\sim\phi^{(N)}(\bm{S})$ is the same as that
of $\bm{y}^{\prime}\sim\phi^{(n)}(\bm{S}^{(\bm{i})})$ where $\bm{i}\sim[k]$ is
a random group. Using this insight, we are able to prove the following Lemma.

######  Lemma 7.2 (It is exponentially unlikely many groups have high error).

In the setting of Lemma 7.1, let $\bm{S}^{(1)}$ be the first $n$ elements of
$\bm{S}$, $\bm{S}^{(2)}$ the next $n$, and so on. Then,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{N},{\bm{\psi}}\sim\mathcal{A}^{\prime}(\bm{S})}\left[\sum_{i\in[k]}\mathds{1}[{\bm{\psi}}(\bm{S}^{(i)})\geq\tau_{{\bm{\psi}}}]\geq
0.03k\right]\leq e^{-k/300}.$

The hypothesis of Lemma 7.1 roughly corresponds to
$\operatorname{{Pr}}[{\bm{\psi}}(\bm{S}^{(i)})\geq\tau_{{\bm{\psi}}}]\leq
1/100$. If these events were independent for each $i\in[k]$, then the
conclusion of Lemma 7.2 would follow from a standard Chernoff. Unfortunately,
they are not necessarily independent. To get around that, in Lemma 7.4 we
extend a direct product theorem of Shaltiel’s showing, roughly speaking, those
events are no worse than independent.

We combine Lemma 7.2 with the following Lemma.

######  Lemma 7.3.

For $N\geq nk$, let $\bm{S}\in X^{N}$ be drawn from any permutation invariant
distribution, meaning
$\operatorname{{Pr}}[\bm{S}=S]=\operatorname{{Pr}}[\bm{S}=\sigma(S)]$ for any
$\sigma$ a permutation of the indices. Let $\bm{S}^{(1)}$ be the first $n$
elements of $\bm{S}$, $\bm{S}^{(2)}$ the next $n$, and so on. For any query
$\psi:X\to Y$ and threshold $\tau$, let $\bm{b}$ be the random variable
counting the number of $i\in[k]$ for which $\psi(\bm{S}^{(i)})\geq\tau$. Then,

$\operatorname{{Pr}}[\psi(\bm{S})\geq\tau+1/n]\leq
200\operatorname{{Pr}}[\bm{b}\geq 0.03k].$

Lemma 7.1 is a straightforward consequence of the above two Lemma.

###### Proof of Lemma 7.1 assuming Lemmas 7.2 and 7.3.

The analyst chooses a query $\psi^{(\bm{y})}$ as a function of the responses
$\bm{y}\coloneqq\bm{y}_{1}\sim\phi_{1}(\bm{S}),\ldots,\bm{y}_{T}\sim\phi_{T}(\bm{S})$.
Our goal is to show that
$\operatorname{{Pr}}[\psi^{(\bm{y})}(\bm{S})\geq\tau_{\psi^{(\bm{y})}}+1/n]\leq
200\exp(-k/300)$.

Conditioned on any possible sequence of response $\bm{y}=y$, the distribution
of $\bm{S}$ is permutation invariant. Therefore,

$\displaystyle\operatorname{{Pr}}[\psi^{(\bm{y})}(\bm{S})\geq\tau_{\psi^{(\bm{y})}}]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\mid\bm{y}}\left[\psi^{(\bm{y})}(\bm{S})\geq\tau_{\psi^{(\bm{y})}}+1/n\right]\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{y}}\left[200\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}}\left[\sum_{i\in[k]}\mathds{1}[\psi^{(\bm{y})}(\bm{S}^{(i)})\geq\tau_{\psi^{(\bm{y})}}]\geq
0.03k\right]\right]$ (Lemma 7.3)
$\displaystyle=200\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{N},{\bm{\psi}}\sim\mathcal{A}^{\prime}(\bm{S})}\left[\sum_{i\in[k]}\mathds{1}[{\bm{\psi}}(\bm{S}^{(i)})\geq\tau_{{\bm{\psi}}}]\geq
0.03k\right]$ $\displaystyle\leq 200e^{-k/300}.$ (Lemma 7.2)

∎

###  7.1 Proof of Lemma 7.2

In order to prove Lemma 7.2, in Figure 4 we will define an “analyst game”
formalizing the setting in which an analyst has multiple distinct samples each
of which they can ask queries to. We then prove a direct product theorem
analogous to to Shaltiel’s direct product theorem for fair decision trees
[Sha04].

Parameters: A product distribution
$\mathcal{D}\coloneqq\mathcal{D}_{1}\times\cdots\times\mathcal{D}_{k}$ over
domain $X$, budgets $b\in\mathds{R}^{k}$, a class of queries $\Phi$ each
mapping $X$ to a distribution of possible responses, function
$\mathrm{cost}:\Phi\to\mathds{R}_{\geq 0}$, and class of tests $\Psi$ each
mapping $X$ to $\\{0,1\\}$. Setup: Samples
$\bm{x}_{1},\ldots,\bm{x}_{k}\sim\mathcal{D}$ are drawn and _not_ revealed to
the analyst. Execution: The analyst repeats as many times as desired: 1. The
analyst chooses a query $\phi\in\Phi$ and index $i\in[k]$ 2. The analyst
receives the response $\bm{y}\sim\phi(\bm{x}_{i})$. 3. The budget is
decremented: $b_{i}\leftarrow b_{i}-\mathrm{cost}(\phi)$. Afterwards, the
analyst chooses tests $\psi_{1},\ldots,\psi_{k}$. The analyst wins if
$b_{i}\geq 0$ and $\psi_{i}(\bm{x}_{i})=1$ for all $i\in[k]$. Figure 4: An
analyst game.

######  Lemma 7.4 (Direct product theorem for analyst games).

In Figure 4, fix the domain $X$, query class $\Phi$, test class $\Psi$ and
cost function $\mathrm{cost}$ for which
$\inf_{\phi\in\Phi}(\mathrm{cost}(\phi))>0$. For any distributions
$\mathcal{D}\coloneqq\mathcal{D}_{1}\times\cdots\mathcal{D}_{k}$ and budgets
$b\in\mathds{R}^{k}$, let $\mathrm{AG}(\mathcal{D},b)$ be the maximum
probability an analyst wins the game described in Figure 4. Then,

$\mathrm{AG}(\mathcal{D},b)\leq\prod_{i\in[k]}\mathrm{AG}(\mathcal{D}_{i},b_{i}).$
(13)

It’s straightforward to see that the $(\geq)$ direction of Equation 13 also
holds, but we will not need that direction in this paper.

###### Proof.

First note that if, for any $i\in[k]$, $b_{i}<0$, then both sides of Equation
13 are equal to $0$. We may therefore assume, without loss of generality that
$b_{i}\geq 0$ for all $i\in[k]$.

Consider an arbitrary analyst, $\mathcal{A}$, for distribution $\mathcal{D}$
and budget $b$. We will prove that the probability $\mathcal{A}$ wins is at
most $\prod_{i\in[k]}\mathrm{AG}(\mathcal{D}_{I},b_{i})$ by induction on the
number of iterations of the loop in Figure 4 that $\mathcal{A}$
executes.888Note that since $\inf_{\phi\in\Phi}(\mathrm{cost}(\phi))>0$, the
number of loop executions is finite. In the base case, $\mathcal{A}$ executes
the loop zero times and directly chooses tests. Then, $\mathcal{A}$’s
probability of winning is upper bounded by

$\displaystyle\sup_{\phi_{1},\ldots,\phi_{k}\in\Psi}\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[\prod_{i\in[k]}\psi_{i}(\bm{x}_{i})\right]$
$\displaystyle=\sup_{\phi_{1},\ldots,\phi_{k}\in\Psi}\prod_{i\in[k]}\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[\psi_{i}(\bm{x}_{i})\right]$
($\mathcal{D}$ is product)
$\displaystyle=\prod_{i\in[k]}\sup_{\phi_{i}\in\Psi}\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}_{i}\sim\mathcal{D}_{i}}\left[\psi_{i}(\bm{x}_{i})\right]\leq\mathrm{AG}(\mathcal{D}_{i},b_{i}).$

In the case where $\mathcal{A}$ executes the loop $\geq 1$ times, let
$\phi\in\Phi$ and $i\in[k]$ be the query and group respectively that
$\mathcal{A}$ chooses in the first iteration of the loop. Using
$b^{\prime}\in\mathds{R}^{k}$ as the vector satisfying
$b^{\prime}_{i}=b_{i}-\mathrm{cost}(\phi)$ and $b^{\prime}_{j}=b_{j}$ for all
$j\neq i$, the success probability of $\mathcal{A}$ is upper bounded by

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D},\bm{y}\sim\phi(\bm{x}_{i})}$
$\displaystyle\left[\mathrm{AG}(\mathcal{D}\mid\phi(\bm{x}_{i})=\bm{y},b^{\prime})\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D},\bm{y}\sim\phi(\bm{x}_{i})}\left[\prod_{j\in[k]}\mathrm{AG}((\mathcal{D}\mid\phi(\bm{x}_{i})=\bm{y})_{j},b^{\prime}_{j})\right]$
(inductive hypothesis)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D},\bm{y}\sim\phi(\bm{x}_{i})}\left[\mathrm{AG}((\mathcal{D}\mid\phi(\bm{x}_{i})=\bm{y})_{i},b_{i}-\mathrm{cost}(\phi))\cdot\prod_{j\neq
i}\mathrm{AG}(\mathcal{D}_{j},b_{j})\right]$ $\displaystyle=\prod_{j\neq
i}\mathrm{AG}(\mathcal{D}_{j},b_{j})\cdot\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D},\bm{y}\sim\phi(\bm{x}_{i})}\left[\mathrm{AG}((\mathcal{D}\mid\phi(\bm{x}_{i})=\bm{y})_{i},b_{i}-\mathrm{cost}(\phi)\right].$

The quantity
$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D},\bm{y}\sim\phi(\bm{x}_{i})}\left[\mathrm{AG}((\mathcal{D}\mid\phi(\bm{x}_{i})=\bm{y})_{i},b_{i}-\mathrm{cost}(\phi)\right]$
is exactly the win probability on $\mathcal{D}_{i},b_{i}$ of the analyst whose
first query is $\phi$, and remaining strategy is optimal. Therefore, it is
upper bounded by $\mathrm{AG}(\mathcal{D}_{i},b_{i})$ and so the win
probability of $\mathcal{A}$ is upper bounded by
$\prod_{i\in[k]}\mathrm{AG}(\mathcal{D}_{i},b_{i})$, as desired. ∎

We’ll also use the following version of the classic Chernoff bound.

######  Fact 7.5 (Chernoff bound).

Let $\bm{x}_{1},\ldots,\bm{x}_{k}$ be random variables each taking on values
in $\\{0,1\\}$ and satisfying, for some $p<1$ and all $S\subseteq[k]$,

$\operatorname{{Pr}}\left[\bigcap_{i\in S}\bm{x}_{i}\right]\leq p^{|S|}.$

Then, for any $\delta>0$,

$\operatorname{{Pr}}\left[\sum_{i\in[k]}\bm{x}_{i}\geq(1+\delta)pk\right]\leq\exp\left(-\frac{\delta^{2}pk}{2+\delta}\right).$

###### Proof of Lemma 7.2.

Let $\bm{S}^{(k+1)}$ be the remaining $N-nk$ elements not in
$\bm{S}^{(1)},\ldots,\bm{S}^{(k)}$. At each time step $t\in[T]$, the analyst
asks a query $\phi_{t}:X\to Y_{t}$ and receives the response
$\bm{y}_{t}=\phi_{t}(\bm{x}_{t})$. We can think of $\bm{x}_{t}$ as being
chosen via a two tiered process: First, a group $\bm{i}_{t}\in[k+1]$ is
chosen, and then $\bm{x}_{t}$ is chosen uniform from $\bm{S}^{(\bm{i})}$. We
will show that Lemma 7.2 holds even if the analyst gets to choose $\bm{i}_{t}$
at each step.

For each group $i\in[k]$, let $\bm{a}_{i}$ be the indicator that the total
cost of queries to $\bm{S}^{(i)}$ is at most $b$ and
$\psi(\bm{S}^{(i)})\geq\tau_{\psi}$. Since there is a total of $B=bk/100$
budget, regardless of the analyst partitions the queries to groups, at most
$\frac{k}{100}$ groups will receive queries with total cost $\geq b$. It is
therefore sufficient to bound the probability that
$\sum_{i\in[k]}\bm{a}_{i}\geq 0.02k$. Applying Lemma 7.4 and the hypothesis of
Lemma 7.1, for any set of groups $G\subseteq[k]$,

$\operatorname{{Pr}}\left[\bigcap_{i\in
G}\bm{a}_{i}\right]\leq\left(\frac{1}{100}\right)^{|G|}.$

Applying the Chernoff bound in Fact 7.5,

$\operatorname{{Pr}}\left[\sum_{i\in[k]}\bm{a}_{i}\geq
0.02k\right]\leq\exp\left(-\frac{k}{300}\right).\qed$

###  7.2 Proof of Lemma 7.3

We begin by proving the following technical Lemma.

######  Lemma 7.6.

For any $S\in[0,1]^{N}$ and $n<N$, let $\bm{x}$ be sampled by taking the sum
of $n$ elements from $S$ chosen uniformly without replacement. Then, if
$\operatorname{{Var}}[\bm{x}]$ is nonzero,

$\operatorname{{Pr}}[\bm{x}>\mathop{{\mathds{E}}\/}[\bm{x}]]\geq\frac{2\sqrt{3}-3}{12+\frac{4}{\operatorname{{Var}}[\bm{x}]}}$

Lemma 7.6 implies that one of two things must be true: Either
$\operatorname{{Var}}[\bm{x}]\leq 1$, in which case standard techniques give
that the median of $\bm{x}$ is within $1$ of the mean. Otherwise, $\bm{x}$
exceeds its mean with a constant probability. To prove Lemma 7.6, we use the
following inequality connecting the moments of $\bm{x}$ to the probability it
exceeds its mean.

######  Fact 7.7 ([Ver08]).

For any mean-$0$ random variable $\bm{x}$ with nonzero variance,

$\operatorname{{Pr}}[\bm{x}>0]\geq\frac{2\sqrt{3}-3}{\frac{\mathop{{\mathds{E}}\/}[\bm{x}^{4}]}{\mathop{{\mathds{E}}\/}[\bm{x}^{2}]^{2}}}.$

Hence, to prove Lemma 7.6, it suffices to estimate the moments of $\bm{x}$.
The moments of $\bm{x}$ can be explicitly computed as a function of the
elements in $S$, but this results in a rather large number of terms. To make
the arithmetic simpler, we instead compare to the scenario where the sample
was performed _with replacement_.

######  Fact 7.8 ([Hoe94]).

For some set $S\in R^{N}$ and $n\leq N$, let $\bm{x}$ be the sum of $n$
elements sampled uniformly _without replacement_ from $S$, and $\bm{y}$ be the
sum of $n$ elements sampled _with replacement_ from $S$. Then, for any convex
$f$,

$\mathop{{\mathds{E}}\/}[f(\bm{x})]\leq\mathop{{\mathds{E}}\/}[f(\bm{y})].$

######  Corollary 7.9.

For any set $S\in R^{N}$ whose elements sum to $0$, let $\bm{x}$ and $\bm{y}$
be as in Fact 7.8. Then,

$\frac{\mathop{{\mathds{E}}\/}[\bm{x}^{4}]}{\mathop{{\mathds{E}}\/}[\bm{x}^{2}]^{2}}\leq\left(\frac{N-1}{N-n}\right)^{2}\cdot\frac{\mathop{{\mathds{E}}\/}[\bm{y}^{4}]}{\mathop{{\mathds{E}}\/}[\bm{y}^{2}]^{2}}.$

###### Proof.

By Fact 7.8,
$\mathop{{\mathds{E}}\/}[\bm{x}^{4}]\leq\mathop{{\mathds{E}}\/}[\bm{y}^{4}]$.
Therefore it suffices to show that
$\mathop{{\mathds{E}}\/}[\bm{x}^{2}]=\mathop{{\mathds{E}}\/}[\bm{y}^{2}]\cdot\frac{N-n}{N-1}$.

Let $\bm{x}_{1},\ldots,\bm{x}_{n}$ and $\bm{y}_{1},\ldots,\bm{y}_{n}$ be the
$n$ elements of $S$ chosen without replacement and with replacement
respectively. Then, since the $\bm{y}_{i}$ are mean-$0$ and independent, for
$i\neq j\in[n]$, $\mathop{{\mathds{E}}\/}[\bm{y}_{i}\bm{y}_{j}]=0$. Meanwhile,
using the fact that the sum of elements in $S$ is $0$,

$\mathop{{\mathds{E}}\/}[\bm{x}_{i}\bm{x}_{j}]=\frac{1}{N(N-1)}\sum_{a\in[N]}\sum_{b\in[N]\setminus\\{a\\}}S_{a}S_{b}=\frac{1}{N(N-1)}\sum_{a\in[N]}S_{a}\left(\sum_{b\in[N]}S_{b}-S_{a}\right)=-\frac{1}{N(N-1)}\sum_{a\in[N]}S_{a}^{2}.$

Furthermore, we have for any $i\in[n]$, that

$\mathop{{\mathds{E}}\/}[\bm{x}_{i}^{2}]=\mathop{{\mathds{E}}\/}[\bm{y}_{i}^{2}]=\frac{1}{N}\sum_{a\in[N]}S_{a}^{2}.$

Next, we can compute the second moment of $\bm{y}$,

$\mathop{{\mathds{E}}\/}[\bm{y}^{2}]=\sum_{i\in[n]}\mathop{{\mathds{E}}\/}[\bm{y}_{i}^{2}]=\frac{n}{N}\sum_{a\in[N]}S_{a}^{2}.$

For $\bm{x}$,

$\mathop{{\mathds{E}}\/}[\bm{x}^{2}]=\sum_{i\in[n]}\mathop{{\mathds{E}}\/}[\bm{x}_{i}^{2}]+\sum_{i\neq
j}\mathop{{\mathds{E}}\/}[\bm{x}_{i}\bm{x}_{j}]=\frac{n}{N}\sum_{a\in[N]}S_{a}^{2}-\frac{n(n-1)}{N(N-1)}\sum_{a\in[N]}S_{a}^{2}=\frac{n}{N}\left(1-\frac{n-1}{N-1}\right)\sum_{a\in[N]}S_{a}^{2}.$

Comparing the above gives the desired bound. ∎

Next, we bound the desired moment ratio in the setting where the elements are
sampled _with_ replacement.

######  Proposition 7.10.

Let $\bm{y}_{1},\ldots,\bm{y}_{n}$ be iid mean-$0$ variables each bounded on
$[-1,1]$. Then, for $\bm{y}\coloneqq\sum_{i\in[n]}\bm{y}_{i}$

$\frac{\mathop{{\mathds{E}}\/}[\bm{y}^{4}]}{\mathop{{\mathds{E}}\/}[\bm{y}^{2}]^{2}}\leq
3+\frac{1}{\operatorname{{Var}}[\bm{y}]}$

###### Proof.

We’ll denote $\sigma^{2}\coloneqq\mathop{{\mathds{E}}\/}[\bm{y}_{i}^{2}]$.
Since $\bm{y}_{i}$ is bounded, we further have that
$\mathop{{\mathds{E}}\/}[\bm{y}_{i}^{4}]\leq\sigma^{2}$. Then,

$\mathop{{\mathds{E}}\/}[\bm{y}^{2}]=n\sigma^{2}.$

Expanding $\mathop{{\mathds{E}}\/}[\bm{y}^{4}]$ gives many terms. Luckily,
since the $\bm{y}_{i}$ are each independent and mean-$0$, most of those terms
cancel. We are left with,

$\mathop{{\mathds{E}}\/}[\bm{y}^{4}]=n\mathop{{\mathds{E}}\/}[\bm{y}_{i}^{4}]+3n(n-1)(\sigma^{2})^{2}\leq
n\sigma^{2}+3n^{2}\sigma^{4}.$

This gives

$\frac{\mathop{{\mathds{E}}\/}[\bm{y}^{4}]}{\mathop{{\mathds{E}}\/}[\bm{y}^{2}]^{2}}\leq\frac{n\sigma^{2}+3n^{2}\sigma^{4}}{n^{2}\sigma^{4}}=3+\frac{1}{n\sigma^{2}}.$

The desired result follows from $\operatorname{{Var}}[\bm{y}]=n\sigma^{2}$. ∎

Finally, we complete the proof of Lemma 7.6

###### Proof.

Let $\mu\coloneqq\frac{1}{N}\sum_{x\in S}x$, and $S^{\prime}$ be a copy of $S$
with each element shifted by $-\mu$. Clearly, each element of $S^{\prime}$ is
bounded on $[-1,1]$ and they sum to $0$. It suffices to bound
$\operatorname{{Pr}}[\bm{x}^{\prime}>0]$ for $\bm{x}^{\prime}$ being the sum
of $n$ uniform elements chosen without replacement from $S^{\prime}$.
Furthermore, without loss of generality, we may assume that $n\leq\frac{N}{2}$
as, if $n>N/2$, we may instead consider the sum of the elements _not_ sampled.
$\bm{x}^{\prime}>0$ iff the sum of the elements not sampled is negative.

Let $\bm{y}^{\prime}$ be the sum of $n$ elements chosen uniformly without
replacement from $S^{\prime}$. Then,

$\displaystyle\operatorname{{Pr}}[\bm{x}>\mathop{{\mathds{E}}\/}[\bm{x}]]$
$\displaystyle=\operatorname{{Pr}}[\bm{x}^{\prime}>0]$
$\displaystyle\geq\frac{2\sqrt{3}-3}{\frac{\mathop{{\mathds{E}}\/}[\bm{x}^{\prime
4}]}{\mathop{{\mathds{E}}\/}[\bm{x}^{\prime 2}]^{2}}}$ (Fact 7.7)
$\displaystyle\geq\frac{2\sqrt{3}-3}{\left(\frac{N-1}{N-n}\right)^{2}\frac{\mathop{{\mathds{E}}\/}[\bm{y}^{\prime
4}]}{\mathop{{\mathds{E}}\/}[\bm{y}^{\prime 2}]^{2}}}$ (Corollary 7.9)
$\displaystyle\geq\frac{2\sqrt{3}-3}{4\frac{\mathop{{\mathds{E}}\/}[\bm{y}^{\prime
4}]}{\mathop{{\mathds{E}}\/}[\bm{y}^{\prime 2}]^{2}}}$ ($n\leq N/2$)
$\displaystyle\geq\frac{2\sqrt{3}-3}{4\left(3+\frac{1}{\operatorname{{Var}}[\bm{y}^{\prime}]}\right)}$
(Proposition 7.10)
$\displaystyle\geq\frac{2\sqrt{3}-3}{4\left(3+\frac{1}{\operatorname{{Var}}[\bm{x}]}\right)}$
(Fact 7.8)

∎

We’ll use the following one-sided variant of Chebyshev’s inequality

######  Fact 7.11 (Cantelli’s inequality).

Let $\bm{x}$ be a random variable with variance $\sigma^{2}$. Then,

$\operatorname{{Pr}}[\bm{x}-\mathop{{\mathds{E}}\/}[\bm{x}]\geq\varepsilon\sigma]\leq\frac{1}{1+\varepsilon}.$

As an easy consequence of the above two results, we obtain the following.

######  Corollary 7.12.

For $\bm{x}$ as in Lemma 7.6,

$\operatorname{{Pr}}[\bm{x}>E[\bm{x}]-1]\geq\frac{2\sqrt{3}-3}{13}>0.0357.$

###### Proof.

If $\operatorname{{Var}}[\bm{x}]\geq 4$, the desired result follows from Lemma
7.6. Otherwise, it follows from Fact 7.11. ∎

###### Proof of Lemma 7.3.

We’ll use $\bm{a}$ as shorthand for
$\mathds{1}[\psi(\bm{S}^{(i)})\geq\tau+1/n]$. Since
$\operatorname{{Pr}}[\bm{b}\geq 0.03k]\geq\operatorname{{Pr}}[\bm{b}\geq
0.03k\mid\bm{a}]\cdot\operatorname{{Pr}}[\bm{a}]$,

$\operatorname{{Pr}}[\bm{a}]\leq\frac{\operatorname{{Pr}}[\bm{b}\geq
0.03k]}{\operatorname{{Pr}}[\bm{b}\geq 0.03k\mid\bm{a}]}.$

Therefore, it suffices to show that $\operatorname{{Pr}}[\bm{b}\geq
0.03k\mid\bm{a}]\geq\frac{1}{200}$. By Corollary 7.12, for any $i\in[k]$

$\operatorname{{Pr}}[\psi(\bm{S}^{(i)})\geq\tau\mid\bm{a}]>0.0357.$

Using linearity of expectation,

$\mathop{{\mathds{E}}\/}[\bm{b}\mid\bm{a}]>0.0357k.$

The random variable $k-\bm{b}$ is nonnegative and satisfies

$\mathop{{\mathds{E}}\/}[k-\bm{b}\mid\bm{a}]<k-0.0357k=0.9643k.$

Therefore, by Markov’s inequality

$\operatorname{{Pr}}[k-\bm{b}\geq
0.97k\mid\bm{a}]\leq\frac{0.9643k}{0.97k}<0.995.$

Equivalently, $\bm{b}\geq 0.03k$ with probability at least $0.005$ conditioned
on $\psi(\bm{S})\geq\tau+1/n$, which is exactly what we wished to show. ∎

###  7.3 Proof of Theorem 4 and the second part of Theorem 5

###### Proof.

We’ll prove the second part of Theorem 5, as Theorem 4 follows from it. Let
$k=O(\log(1/\delta))$. First, we note that if $\mathcal{A}$ is
$(\mathrm{cost}_{n,\delta},b)$-budgeted almost surely (according to Equation
2), then it is $(\mathrm{cost}_{n/k},O(bk))$-budgeted almost surely (according
to Equation 1). For each test function $\psi:X^{1}\to[0,1]$, define the
threshold to be

$\tau_{\psi}\coloneqq\psi(\mathcal{D})+O\left(\max\left(\frac{k(b+1)}{n},\sqrt{\frac{k(b+1)}{n}\cdot\operatorname{{Var}}_{\mathcal{D}}(\psi)}\right)\right).$

By the first part of Theorem 5 and Markov’s inequality, for any analyst
$\mathcal{A}$ that is $(\mathrm{cost}_{n/k},O(b))$-budgeted,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n},{\bm{\psi}}\sim\mathcal{A}(\bm{S})}[\psi(\bm{S})\geq\tau_{\psi}]\leq\frac{1}{100}.$

By Lemma 7.1, for any analyst $\mathcal{A}^{\prime}$ that is
$(\mathrm{cost}_{n/k},O(bk))$-budgeted almost surely, or equivalently, is
$(\mathrm{cost}_{n,\delta},b)$-budgeted almost surely

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n},{\bm{\psi}}\sim\mathcal{A}^{\prime}(\bm{S})}\left[\psi(\bm{S})\geq\tau_{\psi}+k/n\right]\leq\exp(-\Omega(k))\leq\delta/2.$

Therefore, by a union bound applied to both $\psi$ and $-\psi$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n},{\bm{\psi}}\sim\mathcal{A}^{\prime}(\bm{S})}\left[|\psi(\bm{S})-\psi(\mathcal{D})|>O\left(\max\left(\frac{k(b+1)}{n},\sqrt{\frac{k(b+1)}{n}\cdot\operatorname{{Var}}_{\mathcal{D}}(\psi)}\right)\right)+k/n\right]\leq\delta.$

Equivalently, substituting in the definition of error in Definition 4 and
$k\coloneqq O(\log(1/\delta))$

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n},{\bm{\psi}}\sim\mathcal{A}^{\prime}(\bm{S})}\left[\mathrm{error}(\psi,\bm{S},\Delta)\geq
O\left(\log(1/\delta)\cdot\left(\frac{b+1}{n}\right)\right)\right]\leq\delta.\qed$

##  8 Applications

###  8.1 The statistical-query mechanism: Proof of Theorem 6

The proof of Theorem 6 combines two bounds: We’ll proof that, with high
probability, all statistical queries asked have low bias, meaning
$\phi(\bm{S})$ and $\phi(\mathcal{D})$ are close. We’ll further show that,
with high probability, the answer the mechanism gives when receiving a
statistical query $\phi$ is close to $\phi(\bm{S})$. These two results are
combined with the following proposition.

######  Proposition 8.1 (Triangle-like inequality).

For any $\tau>0$ and $a,b,c\in[0,1]$ satisfying

$|b-a|\leq\max(\tau^{2},\tau\sqrt{a(1-a)})\quad\quad\quad\quad|c-b|\leq\max(\tau^{2},\tau\sqrt{b(1-b)})$

it also holds that

$|c-a|\leq 3\max(\tau^{2},\tau\sqrt{a(1-a)}).$

###### Proof.

First, consider the case where $|c-b|\leq\tau^{2}$. Then,

$|c-a|\leq|a-b|+|c-b|\leq\max(\tau^{2},\tau\sqrt{a(1-a)})+\tau^{2}\leq
2\max(\tau^{2},\tau\sqrt{a(1-a)}).$

In the other case,

$\displaystyle|c-b|$ $\displaystyle\leq\tau\sqrt{b(1-b)}$
$\displaystyle=\tau\sqrt{(a+(b-a))(1-a-(b-a))}$
$\displaystyle=\tau\sqrt{a(1-a)+(b-a)(1-2a)-(b-a)^{2}}$
$\displaystyle\leq\tau\sqrt{a(1-a)+(b-a)}$
$\displaystyle\leq\tau\sqrt{a(1-a)}+\tau\sqrt{b-a}$
$\displaystyle\leq\tau\sqrt{a(1-a)}+\tau\sqrt{\max(\tau^{2},\tau\sqrt{a(1-a)}}$
$\displaystyle=\tau\sqrt{a(1-a)}+\max(\tau^{2},\sqrt{\tau^{2}\cdot\tau\sqrt{a(1-a)}})$
$\displaystyle\leq 2\max(\tau^{2},\tau\sqrt{a(1-a)}).$

The desired result follows from the standard triangle inequality. ∎

Next, we give a short proof that the answer’s of the mechanism are all close
to $\phi(\bm{S})$ with high probability.

######  Proposition 8.2.

In the setting of Theorem 6, with probability at least $1-\delta$, for all
$t\in[T]$,

$|\phi_{t}(\bm{S})-\bm{y}_{t}|\leq
3\max\left(\tau^{2},\tau\sqrt{\phi_{t}(\bm{S})(1-\phi_{t}(\bm{S}))}\right).$

###### Proof.

The distribution of $\bm{y}_{t}$ is the sum of $k$ independent $\\{0,1\\}$
bits each with mean within $\pm\varepsilon$ of $\phi_{t}(\bm{S})$. A standard
application of Chernoff bounds and a union bound over the $T$ queries gives
that, since $k\coloneqq O\left(\frac{\log(T/\delta)}{\tau^{2}}\right)$, with
probability at least $1-\delta$, for all $t\in[T]$

$|\bm{y}_{t}-\mathop{{\mathds{E}}\/}[\bm{y}_{t}]|\leq\max\left(\tau^{2},\tau\sqrt{\mathop{{\mathds{E}}\/}[\bm{y}_{t}](1-\mathop{{\mathds{E}}\/}[\bm{y}_{t})}\right).$

Based on the parameters in Theorem 6,

$|\mathop{{\mathds{E}}\/}[\bm{y}_{t}]-\phi_{t}(\bm{S})|\leq\varepsilon\leq\frac{\tau^{2}}{\sqrt{T}}\leq\tau^{2}.$

The desired result follows from Proposition 8.1. ∎

Finally, we prove the main result of this subsection.

###### Proof of Theorem 6.

We’ll apply the “monitor” technique of Bassily et al. [BNS+16], setting the
test query $\psi$ to the SQ with the “worst” response. Specifically, after
receiving responses $\bm{y}_{1},\ldots,\bm{y}_{T}$ to SQs
$\phi_{1},\ldots,\phi_{T}$, the analyst sets the test query to

$\psi\coloneqq\phi_{t^{\star}}\quad\text{where}\quad
t^{\star}\coloneqq\operatorname*{arg\,max}_{t\in[T]}\frac{|\bm{y}_{t}-\phi_{t}(\mathcal{D})|}{\max(\tau^{2},\tau\sqrt{\phi_{t}(\mathcal{D})(1-\phi_{t}(\mathcal{D}))}}.$

It is sufficient to show that Equation 4 holds for $t=t^{\star}$ as, based on
how we defined $t^{\star}$, it then holds for all $t\in[T]$.

The mechanism for answering statistical queries in Figure 2 makes a total of
$Tk$ subsampling queries each with $w=1$ and a range $|Y|=|\\{0,1\\}|=2$. Each
query is $(\varepsilon\coloneqq\frac{\log(1/\delta)}{n})$-uniform. Applying
the improved cost function in Theorem 5 to Theorem 4, the budget is
$b=O(Tk/n)$, and so, with probability at least $1-\delta$,

$\mathrm{error}(\psi,\bm{S},\mathcal{D})\leq
O\left(\log(1/\delta)\cdot\frac{Tk+n}{n^{2}}\right)\leq\tau^{2}.$

As
$\operatorname{{Var}}_{\mathcal{D}}(\psi)\leq\sqrt{\mathcal{D}(\psi)(1-\mathcal{D}(\psi))}$,
this implies that

$|\psi(\bm{S})-\psi(\mathcal{D})|\leq\max\left(\tau^{2},\tau\sqrt{\mathcal{D}(\psi)(1-\mathcal{D}(\psi))}\right).$

Furthermore, by Proposition 8.2, with probability at least $1-\delta$, for all
$t\in[T]$

$|\phi_{t}(\bm{S})-\bm{y}_{t}|\leq
3\max\left(\tau^{2},\tau\sqrt{\phi_{t}(\bm{S})(1-\phi_{t}(\bm{S}))}\right).$

In particular, the above holds for $\phi_{t^{\star}}$. We union bound over
both of the above equations and apply Proposition 8.1: With probability at
least $1-2\delta$ Equation 4 holds for $t=t^{\star}$ up to a constant factor.
As $t^{\star}$ is worst-case, it therefore applies for all $t\in[T]$.

The desired result follows by renaming $\delta^{\prime}\coloneqq\delta/2$ and
$\tau^{\prime}\coloneqq\tau/c$ for appropriate constant $c$. ∎

###  8.2 The median-finding mechanism: Proof of Theorem 7

In this section, we prove Theorem 7. We begin with the following definition.

######  Definition 16 (Bad sample).

For a query $\phi:X^{w}\to R\subseteq\mathds{R}$, and threshold $r\in R$ that
is not an approximate median of $\phi(\mathcal{D})$, we say a sample $S\in
X^{n}$ is $(\phi,r)$-bad if, with probability at least $0.45$ over
$\bm{S}^{\prime}\sim\binom{S}{w}$,

$\mathds{1}[\phi(\bm{S}^{\prime})\geq
r]\neq\mathds{1}[\mathrm{median}(\phi(\mathcal{D}))\geq r].$

Intuitively, the proof of Theorem 7 is separated into two pieces: We show
that, with high probability, for all queries $\phi$ and thresholds $r$ used in
Figure 3, only a small fraction $(\leq 0.02k)$ of the groups are “bad samples.
Then, we show that as long as this is true, with high probability, all answers
output by the mechanism are approximate medians.

###### Proof of Theorem 7.

For each $t\in[T]$ and threshold $r\in R_{t}$ considered the mechanism, let
$p(t,r)$ as follows: If $r$ is an approximate median of
$\phi_{t}(\mathcal{D})$, we define $p(t,r)=0$. If $r$ is smaller than all
approximate medians of $\phi_{t}(\mathcal{D})$, then we define $p(t,r)$ to be
the fraction of votes $\bm{v}_{1},\ldots,\bm{v}_{k}$ that were set to $0$ when
determining whether $\bm{y}_{t}\geq r$. If $r$ is larger than all approximate
medians of $\phi_{t}(\mathcal{D})$, then we define $p(t,r)$ to be the fraction
of such votes that were set to $1$.

If, for all choices of $t,r$, $p(t,r)<0.5$, then all $\bm{y}_{t}$ output by
the median mechanism must be an approximate median. Let $t^{\star},r^{\star}$
be the choices maximizing $p(t^{\star},r^{\star})$. Then, it is sufficient to
prove that with probability at least $1-\delta$, $p(t^{\star},r^{\star})<0.5$.
We define the test query $\psi:X^{w_{t^{\star}}}\to\\{0,1\\}$,

$\psi(S)\coloneqq\mathds{1}[\phi_{t^{\star}}(S)\geq r_{\star}].$

Here, we apply the improved cost function of Theorem 5 to Theorem 3. Each
group $\bm{S}^{(i)}$ is a random sample from $\mathcal{D}^{n^{\prime}}$ where
$n^{\prime}\geq\lfloor n/k\rfloor$. Then the total budget of queries asked to
that group is

$b\coloneqq\sum_{t\in T}\frac{w_{t}\cdot 2}{n^{\prime}-w_{t}}\cdot(1+\log
2)\leq O\left(\frac{\sum_{t\in T}w_{t}}{n^{\prime}}\right)$

where the inequality uses that $n^{\prime}\gg w_{\max}$. Applying Markov’s
inequality to the conclusion of Theorem 3, as well as $n^{\prime}\geq\lfloor
n/k\rfloor$,

$\operatorname{{Pr}}[\mathrm{error}(\psi,\bm{S}^{(i)},\mathcal{D})\geq
0.05]\leq O\left(\frac{b+1}{n^{\prime}}\right)=O\left(\frac{k^{2}\sum_{t\in
T}w_{t}}{n^{2}}+\frac{k}{n}\right)$

Based on how we set $n$ in Theorem 7, the above probability is at most $0.01$.
Furthermore if $\mathrm{error}(\psi,\bm{S}^{(i)},\mathcal{D})<0.05$, then
$\bm{S}^{(i)}$ cannot be $(\phi_{t^{\star}},r^{\star})$-bad. Therefore, for
each group $i\in[k]$, the probability that $\bm{S}^{(i)}$ is
$(\phi_{t^{\star}},r^{\star})$-bad is at most $0.01$. Applying Lemma 7.4 and
the Chernoff bound of Fact 7.5, with probability at least $1-\exp(-k/300)$, at
most $0.02k$ groups $i\in[k]$ are $(\phi_{t^{\star}},r^{\star})$-bad.

Next, we note that for any single choice of $\phi_{t}$ and $r\in R_{t}$, if at
most $0.02k$ groups are $(\phi_{t},r_{t})$-bad, then the expected value of
$p(t,r)$ is at most $0.47$ and, by a Chernoff bound, the probability
$p(t,r)\geq 0.5$ is at most $\exp(-\Omega(k))$. We chose $k$ large enough to
union bound over all $T\cdot\log_{2}(R_{\max})$ choices of $t\in[T]$ and $r\in
R_{t}$. Specifically, with probability at least $1-\delta$, for each $t\in[T]$
and $r_{t}\in R$ for which at most $0.02k$ groups are bad, $p(t,r)<0.5$. In
particular, this includes $p(t^{\star},r^{\star})$, proving the desired
result. ∎

##  9 Acknowledgments

The author thanks Li-Yang Tan and Jonathan Ullman for their helpful
discussions and feedback. He furthermore thanks the STOC reviewers for their
helpful feedback.

Guy is supported by NSF awards 1942123, 2211237, and 2224246.

## References

  * [BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi.  Privacy amplification by subsampling: Tight analyses via couplings and divergences.  Advances in Neural Information Processing Systems, 31, 2018.
  * [BNS+16] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman.  Algorithmic stability for adaptive data analysis.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1046–1059, 2016.
  * [DFH+15a] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toni Pitassi, Omer Reingold, and Aaron Roth.  Generalization in adaptive data analysis and holdout reuse.  Advances in Neural Information Processing Systems, 28, 2015.
  * [DFH+15b] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth.  The reusable holdout: Preserving validity in adaptive data analysis.  Science, 349(6248):636–638, 2015.
  * [DFH+15c] 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, pages 117–126, 2015.
  * [DK22] Yuval Dagan and Gil Kur.  A bounded-noise mechanism for differential privacy.  In Conference on Learning Theory, pages 625–661. PMLR, 2022.
  * [FGR+17] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao.  Statistical algorithms and a lower bound for detecting planted cliques.  Journal of the ACM (JACM), 64(2):1–37, 2017.
  * [FRR20] Benjamin Fish, Lev Reyzin, and Benjamin IP Rubinstein.  Sampling without compromising accuracy in adaptive data analysis.  In Algorithmic Learning Theory, pages 297–318. PMLR, 2020.
  * [FS17] Vitaly Feldman and Thomas Steinke.  Generalization for adaptively-chosen estimators via stable median.  In Conference on Learning Theory, pages 728–757. PMLR, 2017.
  * [FS18] Vitaly Feldman and Thomas Steinke.  Calibrating noise to variance in adaptive data analysis.  In Conference On Learning Theory, pages 535–544. PMLR, 2018.
  * [FZ21] Vitaly Feldman and Tijana Zrnic.  Individual privacy accounting via a renyi filter.  Advances in Neural Information Processing Systems, 34:28080–28091, 2021.
  * [Hoe94] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In The collected works of Wassily Hoeffding, pages 409–426. Springer, 1994.
  * [HU14] Moritz Hardt and Jonathan Ullman.  Preventing false discovery in interactive data analysis is hard.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 454–463. IEEE, 2014.
  * [Kea98] Michael Kearns.  Efficient noise-tolerant learning from statistical queries.  Journal of the ACM (JACM), 45(6):983–1006, 1998.
  * [RRST16] Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar.  Max-information, differential privacy, and post-selection hypothesis testing.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 487–494. IEEE, 2016.
  * [RZ16] Daniel Russo and James Zou.  Controlling bias in adaptive data analysis using information theory.  In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 1232–1240, Cadiz, Spain, 09–11 May 2016. PMLR.
  * [Sha04] Ronen Shaltiel.  Towards proving strong direct product theorems.  Computational Complexity, 12(1/2):1–22, 2004.
  * [Smi17] Adam Smith.  Information, privacy and stability in adaptive data analysis.  arXiv preprint arXiv:1706.00820, 2017.
  * [Ste22] Thomas Steinke.  Composition of differential privacy & privacy amplification by subsampling.  arXiv preprint arXiv:2210.00597, 2022.
  * [SU15a] Thomas Steinke and Jonathan Ullman.  Between pure and approximate differential privacy.  arXiv preprint arXiv:1501.06095, 2015.
  * [SU15b] Thomas Steinke and Jonathan Ullman.  Interactive fingerprinting codes and the hardness of preventing false discovery.  In Conference on learning theory, pages 1588–1628. PMLR, 2015.
  * [Ver08] Mark Veraar.  A note on optimal probability lower bounds for centered random variables.  arXiv preprint arXiv:0803.0727, 2008.
  * [ZW19] Yuqing Zhu and Yu-Xiang Wang.  Poission subsampled rényi differential privacy.  In International Conference on Machine Learning, pages 7634–7642. PMLR, 2019.