#  On the power of adaptivity in statistical adversaries

Guy Blanc
Stanford Jane Lange
MIT Ali Malik
Stanford Li-Yang Tan
Stanford

###### Abstract

We study a fundamental question concerning adversarial noise models in
statistical problems where the algorithm receives i.i.d. draws from a
distribution $\mathcal{D}$. The definitions of these adversaries specify the
type of allowable corruptions (noise model) as well as when these corruptions
can be made (adaptivity); the latter differentiates between oblivious
adversaries that can only corrupt the distribution $\mathcal{D}$ and adaptive
adversaries that can have their corruptions depend on the specific sample $S$
that is drawn from $\mathcal{D}$.

In this work, we investigate whether oblivious adversaries are effectively
equivalent to adaptive adversaries, across all noise models studied in the
literature. Specifically, can the behavior of an algorithm $\mathcal{A}$ in
the presence of oblivious adversaries always be well-approximated by that of
an algorithm $\mathcal{A}^{\prime}$ in the presence of adaptive adversaries?
Our first result shows that this is indeed the case for the broad class of
statistical query algorithms, under all reasonable noise models. We then show
that in the specific case of additive noise, this equivalence holds for all
algorithms. Finally, we map out an approach towards proving this statement in
its fullest generality, for all algorithms and under all reasonable noise
models.

##  1 Introduction

The possibility of noise pervades most problems in statistical estimation and
learning. In this paper we will be concerned with adversarial noise models, as
opposed to the class of more benign random noise models. Adversarial noise
models are the subject of intensive study across statistics [Hub64, Ham71,
Tuk75], learning theory [Val85, Hau92, KL93, KSS94, BEK02], and algorithms
[DKK+19, LRV16, CSV17, DK19]. The definition of each model specifies:

  1. 1.

The type of corruptions allowed. For example, the adversary may be allowed to
add arbitrary points (additive noise [Hub64, Val85]), or in the context of
supervised learning, allowed to change the labels in the data (agnostic noise
[Hau92, KSS94]).

  2. 2.

The adaptivity of the adversary.

The latter is the focus of our work. Consider any statistical problem where
the algorithm is given i.i.d. draws from a distribution $\mathcal{D}$. On one
hand we have oblivious adversaries: such an adversary corrupts $\mathcal{D}$
to a different distribution $\widehat{\mathcal{D}}$, from which the algorithm
then receives a sample. On the other hand we have adaptive adversaries: such
an adversary first draws a sample $\bm{S}$ from $\mathcal{D}$, and upon seeing
the specific outcomes in $\bm{S}$, corrupts it to $\widehat{\bm{S}}$ which is
then passed on to the algorithm. One can further consider adversaries with
intermediate adaptive power, but we think of this as a dichotomy for now.

A coupling argument shows that adaptive adversaries are at least as powerful
as oblivious ones [DKK+19, ZJS19]. In this work we investigate whether they
can be strictly more powerful.

######  Question 1.

Fix the type of corruptions allowed. Is it true that for any algorithm
$\mathcal{A}$, there is an algorithm $\mathcal{A}^{\prime}$ whose behavior in
the presence of adaptive adversaries well-approximates that of $\mathcal{A}$
in the presence of oblivious adversaries?

The distinction between oblivious and adaptive adversaries is frequently
touched upon in works concerning statistical problems. Sometimes this
distinction is brought up in service of emphasizing that the algorithms given
in these works are robust against adaptive adversaries; other times it is
brought up when the algorithms are shown to be robust against oblivious
adversaries, and the viewpoint of an adaptive corruption process is provided
as intuition for the noise model. However, to our knowledge the relative power
of oblivious and adaptive adversaries in the statistical setting has not been
systematically considered in the literature.

###  1.1 Our results

##### Representing the corruption model as a cost function.

To reason generally about 1, we associate every type of allowable corruptions
with a cost function $\rho$ between distributions. An oblivious
$\rho$-adversary therefore corrupts $\mathcal{D}$ to some
$\widehat{\mathcal{D}}$ that is $\eta$-close with respect to $\rho$, meaning
that $\rho(\mathcal{D},\widehat{\mathcal{D}})\leq\eta$. An adaptive
$\rho$-adversary corrupts a sample $S$ drawn from $\mathcal{D}$ to some
$\widehat{S}$ such that the uniform distribution over $\widehat{S}$ is
$\eta$-close with respect to $\rho$ to that over $S$. We elaborate on this
framework in the body of the paper, where we also give examples of the cost
functions that correspond to the standard noise models considered in the
literature.

####  1.1.1 Yes to 1 for all SQ algorithms

Our first result is an affirmative answer to 1 for the broad class of
statistical query (SQ) algorithms. Our proof will require a mild assumption on
this cost function, the precise statement of which we defer to the body of the
paper. For now, we simply refer to cost functions satisfying this assumption
as “reasonable”, and mention that it is easily satisfied by all standard noise
models, and can be seen to be necessary for our result to hold.

######  Theorem 1 (See Theorem 5 for the formal version).

For all reasonable cost functions $\rho$ and SQ algorithms $\mathcal{A}$, the
behavior of $\mathcal{A}$ in the presence of adaptive $\rho$-adversaries well-
approximates that of $\mathcal{A}$ in the presence of oblivious adversaries.

In other words, the SQ framework neutralizes adaptive adversaries into
oblivious ones, and in the context of 1, we can take $\mathcal{A}^{\prime}$ to
be $\mathcal{A}$ itself. Looking ahead to our other results, we remark that
such a statement cannot be true for all algorithms: there are trivial examples
of (non-SQ) algorithms $\mathcal{A}$ for which $\mathcal{A}^{\prime}$ has to
be a modified version of $\mathcal{A}$.111One such example is
$\mathcal{D}=\mathrm{Bernoulli}(\frac{1}{2})$ and
$\mathcal{A}=\mathds{1}[\text{number of $1$'s in the sample is $0$ mod 100}]$.
As the sample size grows, an oblivious adversary can barely change the
acceptance probability of $\mathcal{A}$, whereas an adaptive one can change it
completely.

Theorem 1 adds to the already-deep connections between the SQ framework and
noise tolerance. The SQ framework was originally introduced in learning
theory, where it continues to be influential in the design of learning
algorithms that are resilient to random classification noise [Kea98]. Recent
work of Feldman, Grigorescu, Reyzin, Vempala, and Xiao [FGR+17] generalizes
the framework beyond learning theory to arbitrary computational problems over
distributions, which is also the setting of our work. The SQ framework
encompasses most algorithms in machine learning and optimization, with the
only known exception being Gaussian elimination—we refer the reader to
[FGR+17, FGV17, Rey20] for further discussions of this point. Most relevant to
the topic of this paper, to our knowledge across all noise models, all
existing statistical algorithms that have been shown to be robust to
adversarial noise are captured by the SQ framework.

####  1.1.2 Yes to 1 for additive noise

Our second result is an affirmative answer to 1 for one of the most natural
types of corruptions:

######  Theorem 2 (See Theorem 7 for the formal version).

The answer to 1 is “yes” for additive noise.

In additive noise, an oblivious adversary corrupts $\mathcal{D}$ to
$\widehat{\mathcal{D}}=(1-\eta)\mathcal{D}+\eta\mathcal{E}$ for an arbitrary
distribution $\mathcal{E}$ of their choosing. An adaptive adversary, on the
other hand, gets to inspect the sample $S$ drawn from $\mathcal{D}$, and adds
$\frac{\eta}{1-\eta}|S|$ many arbitrary points of their choosing to $S$. The
oblivious version of additive noise was introduced by Huber [Hub64] and has
become known as Huber’s contamination model; the adaptive version is commonly
called “data poisoning” in the security and machine learning literature.

Additive noise also captures the well-studied malicious noise from learning
theory [Val85] (see also [KL93]). In this model, the sample is thought of as
being generated from $\mathcal{D}$ sequentially: when each point is generated,
with probability $\eta$ an adversary gets to corrupt it to an arbitrary other
point, in a way that depends on all the points that have been generated so
far. This can be seen to be equivalent to an additive noise adversary with
intermediate adaptive power, since their corruptions cannot depend on those
that have not been generated yet.

Theorem 2 therefore shows that Huber’s contamination model, the malicious
noise model, and the adaptive version of additive noise, are in fact all
equivalent. Our proof of Theorem 2 is constructive: we give an explicit
description of how $\mathcal{A}^{\prime}$ can be obtained from $\mathcal{A}$,
and $\mathcal{A}^{\prime}$ preserves the computational and sample efficiency
of $\mathcal{A}$ up to polynomial factors.

####  1.1.3 Yes to 1 in its fullest generality? An approach via subsampling

Our proof of Theorem 2 is actually an instantiation of a broader approach
towards answering 1 affirmatively in its fullest generality: showing that the
answer is “yes” for all (reasonable) types of allowable corruptions and all
algorithms. We introduce the following definition:

######  Definition 1 (Neutralizing filter).

Let $\rho$ be a cost function and $\mathcal{A}$ be an algorithm for a
statistical problem over a domain $\mathcal{X}$. We say that a randomized
function $\Phi:\mathcal{X}^{*}\to\mathcal{X}^{*}$ is a neutralizing filter for
$\mathcal{A}$ with respect to $\rho$ if the following holds. For all
distributions $\mathcal{D}$, with high probability over the draw of $\bm{S}$
from $\mathcal{D}$, the behavior of

$\mathcal{A}$ on $\Phi(\widehat{\bm{S}})$, where $\widehat{\bm{S}}$ is a
corruption of $\bm{S}$ by an adaptive $\rho$-adversary,

well-approximates the behavior of

$\mathcal{A}$ on a sample from $\widehat{\mathcal{D}}$, where
$\widehat{\mathcal{D}}$ is a corruption of $\mathcal{D}$ by an oblivious
$\rho$-adversary.

Perhaps the most natural filter in this context is the subsampling filter. For
an $n$-sample algorithm $\mathcal{A}$, we request for a larger sample of size
$m\geq n$, allow the adaptive adversary to corrupt it, and then run
$\mathcal{A}$ on a size-$n$ subsample of the corrupted size-$m$ sample. We
call this the “$m\to n$ subsampling filter” and denote it as $\Phi_{m\to n}$.
The hope here is for the randomness of the subsampling step to neutralize the
adaptivity of the adversary.

The efficiency of the subsampling filter is measured by the overhead in sample
complexity that it incurs, i.e. how much larger $m$ is relative to $n$.
Subsampling from a sample that is roughly of the size of the domain of course
makes adaptive adversaries equivalent to oblivious ones, but this renders a
sample-efficient algorithm inefficient. We are interested whether the
subsampling filter can be effective while only incurring a mild overhead in
sample complexity.

We propose the following conjecture as a general approach towards answering 1:

######  Conjecture 1.

For all reasonable cost functions $\rho$ and $n$-sample algorithms
$\mathcal{A}$, the subsampling filter $\Phi_{m\to n}$ is a neutralizing filter
for $\mathcal{A}$ with respect to $\rho$ with
$m=\mathrm{poly}(n,\log(|\mathcal{X}|))$.

We obtain Theorem 2 by proving 1 in the case of $\rho$ being additive noise.

While we have not been able to prove 1 for all $\rho$’s and all algorithms, we
can show the following:

######  Theorem 3 (See Theorem 6 for the formal version).

Let $\rho$ be a cost function and $\mathcal{A}$ be an $n$-sample algorithm.
Suppose there is an $m$-sample algorithm $\mathcal{A}^{\prime}$ whose behavior
in the presence of adaptive $\rho$-adversaries well-approximates that of
$\mathcal{A}$ in the presence of oblivious $\rho$-adversaries. Then
$\Phi_{M\to n}$ is a neutralizing filter for $\mathcal{A}$ with respect to
$\rho$ with $M=O(m^{2})$.

Informally, we think of Theorem 3 as saying “If it is possible, subsampling
does it.” We note that in the context of Theorem 3, we do not require
$\mathcal{A}^{\prime}$ to be computationally efficient: as long as
$\mathcal{A}^{\prime}$ is sample efficient, then our resulting algorithm, the
subsampling filter applied to $\mathcal{A}$, inherits the computational
efficiency of $\mathcal{A}$.

Finally, we show that the bound on $m$ in 1 cannot be further strengthened to
be independent of $|\mathcal{X}|$, the size of the domain:

######  Theorem 4 (See Theorem 8 for the formal version).

Let $\rho$ be the cost function for additive noise and $\eta$ be the
corruption budget. There is an $n$-sample algorithm $\mathcal{A}$ such that
for $m\leq O_{\eta}(n\log(|\mathcal{X}|)/\log^{2}n)$, $\Phi_{m\to n}$ is not a
neutralizing filter for $\mathcal{A}$ with respect to $\rho$.

While Theorem 4 shows that some dependence on $|\mathcal{X}|$ is necessary, we
remark that the $\log(|\mathcal{X}|)$ dependence in 1 is fairly mild—this is
the description length of a sample point $x\in\mathcal{X}$. Theorem 4 also
shows that the quantiative bounds that we achieve for Theorem 2 has an optimal
dependence on $|\mathcal{X}|$.

###  1.2 Discussion

##### Implications of our results.

Theorem 1 says that for all reasonable cost functions, all SQ algorithms
(existing and future ones) that are resilient to oblivious adversaries are
“automatically” also resilient to adaptive adversaries. Likewise, lower bounds
against adaptive adversaries immediately yield lower bounds against oblivious
ones. The same remark further applies for all algorithms in the case of
additive noise and malicious noise, by Theorem 2.

As a concrete example, we recall that the agnostic learning framework was
originally defined with respect to oblivious adversaries [Hau92, KSS94]. As in
the PAC model there a concept class $\mathcal{C}$, but the target function $f$
is no longer assumed to lie within $\mathcal{C}$—hence the name of the model.
The learning algorithm is expected to achieve error close to $\mathrm{opt}$,
the distance from $f$ to $\mathcal{C}$. However, many papers on agnostic
learning provide the viewpoint of an adaptive corruption process as intuition
for the model: the data is assumed to be a labeled according to a function
$f\in\mathcal{C}$, but an adversary corrupts an $\mathrm{opt}$ fraction of the
labels given to the learning algorithm. This adaptive version was subsequently
defined as a separate model called nasty classification noise [BEK02] (as a
special case of the nasty sample noise model introduced in that paper).
Theorem 1 therefore shows that the agnostic learning model and the nasty
classification noise model are in fact equivalent when it comes to SQ
algorithms.

##### When can quantifiers be swapped?

The distinction between oblivious and adaptive adversaries can be viewed as a
difference in the order of “for all” and “with high probability” quantifiers
in the performance guarantees of statistical algorithms. An algorithm succeeds
in the presence of oblivious adversaries if for all distributions
$\widehat{\mathcal{D}}$ that are close to $\mathcal{D}$, the algorithm
succeeds with high probability over a sample $\bm{S}$ drawn from
$\widehat{\mathcal{D}}$. On the other hand, an algorithm succeeds in the
presence of adaptive adversaries if with high probability over a sample
$\bm{S}$ drawn from $\mathcal{D}$, the algorithm succeeds for all corruptions
$\widehat{\bm{S}}$ that are close to $\bm{S}$.

Our work formalizes the question of when these quantifiers can be swapped, and
our results provide several answers.

###  1.3 Other related work: the online setting

While the focus of our work is on the statistical setting, the distinction
between adaptive and oblivious adversaries has also been the subject of recent
study in the online setting, albeit with a notably different notion of
adaptivity.

In the online setting, adaptive adversaries can change the input distribution
in response to the previous behavior of the algorithm, while oblivious
adversaries must choose a fixed input distribution before the algorithm runs.
Haghtalab, Roughgarden, and Shetty [HRS21] analyze this distinction in the
setting of smoothed analysis, which forces the adaptive adversary to choose
distributions that are not too concentrated on any small subset of the
support. In this setting, they reduce adaptive adversaries to oblivious ones
via a coupling argument. This results in strong guarantees for online
learning, online discrepancy minimization, and dispersion in online
optimization in the smoothed setting, even in the presence of an adaptive
adversary.

##  2 Preliminaries

We use boldface (e.g. $\bm{x}\sim\mathcal{D}$) to denote random variables.
Throughout this paper $\mathcal{X}$ denotes an arbitrary finite domain, and we
write $S\in\mathcal{X}^{*}$ to represent a multiset of elements in
$\mathcal{X}$, meaning
$S\in\mathcal{X}^{0}\cup\mathcal{X}^{1}\cup\mathcal{X}^{2}\ldots$. We use the
notation $a=b\pm\varepsilon$ to indicate that $|a-b|<\varepsilon$. For any
$m\in\mathds{N}$, the notation $[m]$ indicates the set $\\{1,2,\ldots,m\\}$.

##### Distributions.

For any $S\in\mathcal{X}^{*}$, we use $\mathcal{U}(S)$ to refer to the uniform
distribution over $S$. For simplicity, we enforce that all distributions only
have rational probabilities, meaning
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}[\bm{x}=x]$ is
rational for any distribution $\mathcal{D}$ and element
$x\in\mathcal{X}$.222Alternatively, one could enforce that the cost function
smoothly interpolate to irrational probabilities, which is the case for all
standard noise models. For any distributions $\mathcal{D}_{1},\mathcal{D}_{2}$
and parameter $\theta\in[0,1]$, we use
$\theta\mathcal{D}_{1}+(1-\theta)\mathcal{D}_{2}$ to refer to the mixture
distribution which samples from $\mathcal{D}_{1}$ with probability $\theta$
and from $\mathcal{D}_{2}$ with probability $(1-\theta)$

######  Definition 2 (Total variation distance).

Let $\mathcal{D}$ and $\mathcal{D}^{\prime}$ be any two distributions over the
same domain, $\mathcal{X}$. It is well known that the following are equivalent
definitions for the _total variation distance_ between $\mathcal{D}$ and
$\mathcal{D}^{\prime}$, denoted
$\operatorname{dist}_{\mathrm{TV}}(\mathcal{D},\mathcal{D}^{\prime})$:

  1. 1.

It is characterized by the best test distinguishing the two distributions:

$\displaystyle\operatorname{dist}_{\mathrm{TV}}(\mathcal{D},\mathcal{D}^{\prime})\coloneqq\sup_{T:\mathcal{X}\to[0,1]}\left\\{\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[T(\bm{x})]-\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}^{\prime}}[T(\bm{x}^{\prime})]\right\\}.$

  2. 2.

It is characterized by the coupling which makes the two random variables
different with the smallest probability.

$\displaystyle\operatorname{dist}_{\mathrm{TV}}(\mathcal{D},\mathcal{D}^{\prime})\coloneqq\inf_{(\bm{x},\bm{x}^{\prime})\text{
a coupling of
}\mathcal{D},\mathcal{D}^{\prime}}\left\\{\mathop{{\operatorname{{Pr}}}\/}[\bm{x}\neq\bm{x}^{\prime}]\right\\}.$

##  3 Adversarial noise models

To reason generally about various noise adversarial models, we represent the
types of allowable corruptions by a budget $\eta$ and cost function $\rho$,
which maps each ordered pair of distributions to some non-negative cost (or
infinity). The cost need not be symmetrical.

######  Definition 3 ($(\rho,\eta)$-oblivious adversary).

Given some cost function $\rho$ and budget $\eta$, an algorithm operating in
oblivious adversary model will receive the following input: If the true data
distribution is $\mathcal{D}$, then the algorithm will receive iid samples
from an adversarial chosen $\widehat{\mathcal{D}}$ satisfying
$\rho(\mathcal{D},\widehat{\mathcal{D}})\leq\eta$.

######  Definition 4 ($(\rho,\eta)$-adaptive adversary).

Given some cost function $\rho$ and budget $\eta$, an $n$-sample algorithm
operating in adaptive adversary model will receive the following input: If the
true data distribution is $\mathcal{D}$, first a clean sample
$\bm{S}\sim\mathcal{D}^{n}$ is generated, and then the algorithm will get an
adversarially chosen $\widehat{\bm{S}}$ satisfying
$\rho(\mathcal{U}(\bm{S}),\mathcal{U}(\widehat{\bm{S}}))\leq\eta$.

Throughout this paper, we use $\widehat{\dbox{\phantom{x}}}$ to denote the
corrupted version of a set or distribution.

We remark that the adaptive adversary as defined in Definition 4 is slightly
stronger than the definitions usually considered, in the sense that there is
usually a bound on the size of $\widehat{S}$ the adversary is allowed to
produce. For example, in the nasty noise model (Definition 7), the adversary
is only allowed to change points in the sample, and so $|\widehat{S}|=|S|$.
All of our results apply regardless of the size of $\widehat{S}$.

###  3.1 Standard noise models from the literature

In this subsection, we list a variety of common adversary models and show how
they are special cases of our framework with an appropriate choice of cost
function.

####  3.1.1 Three generic models

######  Definition 5 (Additive noise).

Given a size-$n$ sample $S\in\mathcal{X}^{n}$ and a corruption budget $\eta$,
the adaptive additive noise adversary is allowed to add $\lfloor
n\cdot\eta/(1-\eta)\rfloor$ points to $S$ arbitrarily.

The additive noise model is captured by the cost function:

$\displaystyle\mathrm{cost}_{\mathrm{add}}(\mathcal{D},\widehat{\mathcal{D}})\coloneqq\inf_{\eta\in\mathds{R}_{\geq
0}}\left\\{\widehat{\mathcal{D}}=(1-\eta)\mathcal{D}+\eta\mathcal{E}\right\\}\quad\text{
for some distribution }\mathcal{E}.$

The oblivious version of additive noise is the well-known Huber contamination
model [Hub64].

######  Definition 6 (Subtractive noise).

Given a size-$n$ sample $S\in\mathcal{X}^{n}$ and a corruption budget $\eta$,
the adaptive subtractive noise adversary is allowed to remove $\lfloor\eta
n\rfloor$ points from $S$ arbitrarily.

The subtractive noise adversary is captured by the cost function:

$\displaystyle\mathrm{cost}_{\mathrm{sub}}(\mathcal{D},\widehat{\mathcal{D}})\coloneqq\mathrm{cost}_{\mathrm{add}}(\widehat{\mathcal{D}},\mathcal{D}).$

######  Definition 7 (Nasty noise).

Given a size-$n$ sample $S\in\mathcal{X}^{n}$ and a corruption budget $\eta$,
the adaptive nasty noise adversary is allowed to change up to $\lfloor\eta
n\rfloor$ of the points in $S$ arbitrarily.

This noise model is also known as strong contamination, and as nasty sample
noise (or simply nasty noise) in the context of supervised learning [BEK02].
It is captured by the cost function $\rho=\operatorname{dist}_{\mathrm{TV}}$.

####  3.1.2 Other standard models

######  Definition 8 (Nasty classification noise [BEK02]).

Let the domain be $\mathcal{X}=X\times Y$. Given a size-$n$ sample
$S\in\mathcal{X}^{n}$ and a corruption budget $\eta$, the adaptive nasty
classification noise adversary is allowed to choose $\lfloor\eta n\rfloor$
points and for each one, change it from $(x,y)$ to $(x,\widehat{y})$ for
arbitrary $\widehat{y}\in Y$.

This model is captured by the cost function:

$\displaystyle\mathrm{cost}_{\mathrm{agn}}(\mathcal{D},\widehat{\mathcal{D}})=\begin{cases}\infty&\text{if
$\mathcal{D}$ and $\mathcal{D}^{\prime}$ do not have the same marginal
distribution over $\mathcal{X}$}\\\
\operatorname{dist}_{\mathrm{TV}}(\mathcal{D},\widehat{\mathcal{D}})&\text{otherwise}\end{cases}$

The $(\mathrm{cost}_{\mathrm{agn}},\eta)$-oblivious adversary corresponds
exactly to the well-studied agnostic learning model [Hau92, KSS94]. Hence,
Theorem 1 implies that nasty classification noise and the agnostic learning
model are identical for SQ algorithms.

The final noise model that we discuss is defined with respect to an adversary
that has intermediate adaptive power:

######  Definition 9 (Malicious noise [Val85]).

In the malicious noise model where the adversary has corruption budget $\eta$,
a sample is generated point-by-point. For each point, independently with
probability $1-\eta$, that point is $\bm{x}\sim\mathcal{D}$. Otherwise, the
adversary is allowed to make that point an arbitrary $x\in\mathcal{X}$ with
knowledge of the previous points sampled but not the future points.

##### On the relationship between malicious noise and additive noise.

The malicious noise adversary does not have full adaptivity, as when they
decide what point to add, they only have knowledge of previous points sampled
and not future ones. We now show how to encode the fully adaptive version of
malicious noise, in which the adversary knows all points in the sample when
deciding corruptions, in our framework.

We first augment the domain to
$\mathcal{X}^{\prime}=\mathcal{X}\cup\\{\varnothing\\}$ where $\varnothing$
will be used to indicate the adversary can change this point arbitrarily. We
then let $\mathcal{D}^{\prime}$ be the distribution satisfying, for each
$x\in\mathcal{X}$:

$\displaystyle\mathcal{D}^{\prime}=(1-\eta)\mathcal{D}+\eta\mathcal{D}_{\varnothing}$

where $\mathcal{D}_{\varnothing}$ is the distribution that always outputs
$\varnothing$. We define the cost function to be

$\displaystyle\mathrm{cost}_{\mathrm{mal}}(\mathcal{D}^{\prime},\widehat{\mathcal{D}}^{\prime})=\begin{cases}\infty&\text{if
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\widehat{\mathcal{D}}^{\prime}}[\bm{x}=\varnothing]>0$}\\\
\infty&\text{if
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\widehat{\mathcal{D}}^{\prime}}[\bm{x}=x]<\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\widehat{\mathcal{D}}}[\bm{x}=x]$
for any $x\in\mathcal{X}$}\\\ 0&\text{otherwise.}\end{cases}$

Note that in order for $\widehat{\mathcal{D}}^{\prime}$ to be a valid
corruption of $\mathcal{D}^{\prime}$ (i.e.
$\mathrm{cost}_{\mathrm{mal}}(\mathcal{D}^{\prime},\widehat{\mathcal{D}}^{\prime})\neq\infty$),
all of the probability mass of $\widehat{\mathcal{D}}^{\prime}$ must be over
$\mathcal{X}$, with none on $\varnothing$. The above provides an encoding of
an adaptive adversary that is at least as powerful as malicious noise. To
further understand the corresponding oblivious adversary, we note that, after
fixing $\eta$,

$\displaystyle\mathrm{cost}_{\mathrm{mal}}(\mathcal{D}^{\prime},\widehat{\mathcal{D}}^{\prime})\neq\infty\quad\text{if
and only
if}\quad\widehat{\mathcal{D}}^{\prime}=(1-\eta)\mathcal{D}+\eta\mathcal{E}\quad\text{for
some distribution $\mathcal{E}$}.$

Hence, the oblivious adversary corresponding to malicious noise is the same as
the oblivious adversary for additive noise. Theorem 2 implies that the
adaptive and oblivious versions of additive noise, as well as malicious noise,
are all equivalent.

###  3.2 Technical remarks

##### Fixed budget vs. random budget.

Consider the nasty noise model (Definition 7), corresponding to
$\rho=\operatorname{dist}_{\mathrm{TV}}$ in our framework. Given a size-$n$
clean sample $\bm{S}$, the adaptive adversary can choose any $\eta$-fraction
of the points to change arbitrarily to create the corrupted sample
$\widehat{\bm{S}}$. Often an alternative definition is used where the
adversary is allowed to arbitrarily change $m$ points in $\bm{S}$, where $m$
can vary based on the specific sample $\bm{S}$, as long as the marginal
distribution of $m$ over samples $\bm{S}\sim\mathcal{D}^{n}$ is
$\mathrm{Bin}(n,\eta)$. This definition is used by [DKK+19, ZJS19] to show
that the adaptive adversary can simulate any oblivious adversary. Technically,
for our definition of an adaptive adversary with fixed budget $\eta$, this
fact is not strictly true.333For example, suppose $\mathcal{X}=\\{0,1\\}$,
$\mathcal{D}$ is the identically $0$ distribution, and $\eta=0.1$. If a
size-$10$ sample is taken, under our adaptive definition, $\widehat{S}$ will
never have more than a single $1$. However, the oblivious adversary can choose
$\widehat{\mathcal{D}}$ that returns $1$ with probability $0.1$ and as a
result is a non-zero chance that two $1$’s appear in a size-$10$ sample.
However, all our results are readily extendable to these slightly stronger
adaptive adversaries with random-budgets. We refer the reader to Section A.1
for details on how we can extend our upper bounds to these random-budget
adaptive adversaries. We also intersperse various inline remarks throughout
the proofs to elaborate on particular details concerning this extension.
Specifically, Remark 2 for changes in the proof needed for Theorem 1 and
Remark 5 for changes needed in Theorems 2 and 3.

##### Finite vs infinite domains.

For our analyses, we assume that the domain, $\mathcal{X}$, is finite. Our
goal is to understand when an algorithm that succeeds in the presence of an
oblivious adversary implies an algorithm that succeeds in the presence of an
adaptive adversary. Any algorithm that succeeds in the presence of an
oblivious adversary can only read finitely many bits of each data point,
effectively discretizing the domain.

That said, Theorem 1 also applies to infinite domains. If the domain is
infinite, a more general definition of closed under mixtures is required in
place of the simpler Definition 15.

######  Definition 10 (Closed under mixtures, infinite domain).

We say that $\rho$ is _closed under mixtures_ if for any distributions
$\mathcal{D},\mathcal{D}^{\prime}$, and coupling of $\bm{x}\sim\mathcal{D}$,
$\bm{x}^{\prime}\sim\mathcal{D}^{\prime}$ and a latent variable $\bm{z}$ (over
any domain),

$\rho(\mathcal{D},\mathcal{D}^{\prime})\leq\sup_{\bm{z}}\left\\{\rho((\bm{x}\mid\bm{z}),(\bm{x}^{\prime}\mid\bm{z}))\right\\}.$

When the domain is finite, Definitions 15 and 10 are equivalent. When it is
infinite, Definition 10 is needed to prove 4.2. The remainder of the proof of
Theorem 1 is identical.

##  4 Proof of Theorem 1: The SQ framework neutralizes adaptive adversaries

In this section we formally state and prove Theorem 1—namely that the
behaviour of a Statistical Query (SQ) algorithm in the presence of adaptive
adversaries is equivalent to its behaviour in the presence of oblivious
adversaries.

##### Basics of the SQ framework.

Let $\mathcal{D}$ be a distribution over some domain $\mathcal{X}$. A
statistical query is a pair $(\phi,\tau)$ where $\phi:\mathcal{X}\to[-1,1]$ is
the query and $\tau>0$ is a tolerance parameter. These queries can be answered
by a statistical query oracle $\textsc{Stat}_{\mathcal{D}}$ which, given an SQ
$(\phi,\tau)$, returns a value $v$ equal to
$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[\phi(\bm{x})]$ up to an
additive error of $\tau$ i.e.
$v\in\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[\phi(\bm{x})]\pm\tau$.

Throughout this section, we will use some convenient shorthand. For a multiset
$S\in\mathcal{X}^{*}$, we write

$\phi(S)\coloneqq\frac{1}{|S|}\sum_{x\in S}\phi(x)$

and for a distribution $\mathcal{D}$, we write

$\phi(\mathcal{D})\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[\phi(\bm{x})].$

We will also use $\mathrm{round}(v,\tau)$ to refer to $v$ rounded to the
nearest integer multiple of $\tau$.

A $k$-query statistical query algorithm, $\mathcal{A}$, is an algorithm that
makes a sequence of statistical queries to the oracle
$\textsc{Stat}_{\mathcal{D}}$ one by one, using the result of the previous
queries to decide which statistical query to make next.

######  Definition 11 ($k$-query SQ Algorithm).

An (adaptive) $k$-query SQ algorithm $\mathcal{A}$ is a sequence of $k$ SQs

$(\phi^{(1)},\tau^{(1)}),(\phi^{(2)}_{v_{1}},\tau^{(2)}),(\phi^{(3)}_{v_{1},v_{2}},\tau^{(3)}),\ldots,(\phi^{(k)}_{v_{1},\ldots,v_{k-1}},\tau^{(k)})$

to $\textsc{Stat}_{\mathcal{D}}$, where $\mathcal{A}$’s choice of the
$(i+1)$-st SQ can depend on $v_{1},\ldots,v_{i}$ which are the answers of
$\textsc{Stat}_{\mathcal{D}}$ to the previous $i$ SQs. For notational
simplicity, we make the standard assumption that all the $\tau$’s are the
same.

##### Using samples to simulate $\textsc{Stat}_{\mathcal{D}}$.

The SQ framework is a stylized model that cleanly facilitates theoretical
analyses; in actuality statistical algorithms do not have access to the SQ
oracle $\textsc{Stat}_{\mathcal{D}}$. In this section we recall a basic fact
(4.1) that underlies the SQ framework, showing how random samples can be used
to simulate the SQ oracle. Though simple, this helps motivate Theorem 1, which
generalizes 4.1 to the setting of adversarial noise.

######  Definition 12 (Representative w.r.t. a single SQ).

Let $\mathcal{D}$ be a distribution over $\mathcal{X}$, let
$\phi:\mathcal{X}\to[-1,1]$ be a statistical query, and $\tau>0$ be a
tolerance parameter. We say that a sample $S\in\mathcal{X}^{*}$ is
representative of $\mathcal{D}$ with respect to $(\phi,\tau)$ if

$\phi(S)\in\phi(\mathcal{D})\pm\tau.$

By the Chernoff bound, if $\bm{S}$ comprises $n=\Theta(1/\tau^{2})$
independent draws from $\mathcal{D}$, then $\bm{S}$ is representative of
$\mathcal{D}$ with respect to $(\phi,\tau)$ w.h.p. We now generalize
Definition 12 and this fact from a single SQ to general SQ algorithms that
make multiple SQs:

######  Definition 13 (Representative w.r.t. an SQ algorithm).

Let $\mathcal{D}$ be a distribution over $\mathcal{X}$ and $\mathcal{A}$ be a
$k$-query SQ algorithm. We say that a sample $S\in\mathcal{X}^{*}$ is
representative of $\mathcal{D}$ with respect to $\mathcal{A}$ if, roughly
speaking, $S$ can be used to accurately simulate
$\textsc{Stat}_{\mathcal{D}}$’s answers to $\mathcal{A}^{\prime}s$ queries.
More precisely, let

$\displaystyle v_{1}$
$\displaystyle\coloneqq\mathrm{round}(\phi^{(1)}(S),\tau)$ $\displaystyle
v_{i+1}$
$\displaystyle\coloneqq\mathrm{round}(\phi^{(i+1)}_{v_{1},\ldots,v_{i}}(S),\tau)\quad\text{for
}i\in\\{0,1,\ldots,k-1\\},$

where the choice of the $(i+1)$-st SQ can depend on the results
$v_{1},\ldots,v_{i}$ of the previous $i$ SQs. Then, $S$ is representative of
$\mathcal{D}$ with respect to $\mathcal{A}$ if $S$ satisfies:

$v_{i+1}\in\phi^{(i+1)}_{v_{1},\ldots,v_{i}}(\mathcal{D})\pm\tau$

for all $i\in\\{0,1,\ldots,k-1\\}$.

A standard Chernoff bound and union bound over all $O(1/\tau)^{k}$ possible
queries yields the following:

######  Fact 4.1.

Let $\mathcal{D}$ be a distribution and $\mathcal{A}$ be a $k$-query SQ
algorithm. Let $\bm{S}$ be $n$ independent draws from $\mathcal{D}$ where
$n=\Theta(k\log(1/\tau)/\tau^{2})$. Then $\bm{S}$ is representative of
$\mathcal{D}$ with respect to $\mathcal{A}$ w.h.p.

######  Remark 1.

As is standard in the SQ literature, in Definition 13 the $v_{i+1}$’s are
defined with respect to the rounded versions of
$\phi^{(i+1)}_{v_{1},\ldots,v_{i}}(S)$’s. This is essential since otherwise
4.1 would not hold. An alternative solution, proposed by the line of work on
adaptive data analysis [DFH+15, BNS+21], is to add Gaussian or Laplacian noise
to the $\phi^{(i+1)}_{v_{1},\ldots,v_{i}}(S)$’s.

###  4.1 Formal statement of Theorem 1: 4.1 in the presence of adversarial
noise

We introduce the following generalization of Definition 13 for the setting of
adversarial noise:

######  Definition 14 ($\eta$-robustly representative w.r.t an SQ algorithm).

Fix a cost function $\rho$. Let $\mathcal{D}$ be a distribution over
$\mathcal{X}$ and $\mathcal{A}$ be a $k$-query SQ algorithm. We say that a
sample $S\in\mathcal{X}^{*}$ is $\mathbf{\eta}$-robustly representative of
$\mathcal{D}$ with respect to $\mathcal{A}$ if the following holds: for every
$\widehat{S}$ such that $\mathcal{U}(\widehat{S})$ $\eta$-close to
$\mathcal{U}(S)$, there is a distribution $\widehat{\mathcal{D}}$ that is
$\eta$-close to $\mathcal{D}$ such that $\widehat{\mathcal{S}}$ is
representative of $\widehat{\mathcal{D}}$ with respect to $\mathcal{A}$.

Therefore, a sample $S$ that is $\eta$-robustly representative of
$\mathcal{D}$ with respect to $\mathcal{A}$ guarantees the following: if
$\mathcal{A}$ succeeds on every distribution $\widehat{\mathcal{D}}$ that is
$\eta$-close to $\mathcal{D}$ (i.e. $\mathcal{A}$ is resilient to oblivious
adversaries), then $\mathcal{A}$ also succeeds on every $\eta$-corruption
$\widehat{S}$ of $S$ (i.e. $\mathcal{A}$ is also resilient to adaptive
adversaries).

Our proof of Theorem 1 will only assume that the cost function $\rho$ is
“reasonable” in the sense of the following definition; this property is easily
satisfied by all standard cost functions:

######  Definition 15 (Closed under mixtures).

We say that $\rho$ is _closed under mixtures_ if for any distributions
$\mathcal{D}_{1},\mathcal{D}_{2},\widehat{\mathcal{D}}_{1},\widehat{\mathcal{D}}_{2}$
and $\theta\in(0,1)$,

$\displaystyle\rho(\theta\mathcal{D}_{1}+(1-\theta)\mathcal{D}_{2},\theta\widehat{\mathcal{D}}_{1}+(1-\theta)\widehat{\mathcal{D}}_{2})\leq\max(\rho(\mathcal{D}_{1},\widehat{\mathcal{D}}_{1}),\rho(\mathcal{D}_{2},\widehat{\mathcal{D}}_{2})).$

Requiring that $\rho$ is closed under mixtures enforces that the adaptive and
oblivious adversaries “match up” in the sense of making the same types of
changes. This is formalized in the following fact, for which we provide a
short proof in Section A.2.

######  Fact 4.2.

Let $\rho$ be closed under mixtures, $\mathcal{D}$ be a distribution over
$\mathcal{X}$, $\eta$ be a corruption budget, and $n\in\mathds{N}$. Suppose
that for all $S\in\mathcal{X}^{n}$, there is a corresponding $\widehat{S}$
satisfying $\rho(\mathcal{U}(S),\mathcal{U}(\widehat{S}))\leq\eta$. Let
$\widehat{\mathcal{D}}$ be the distribution where
$\bm{x}\sim\widehat{\mathcal{D}}$ is generated by: 1) Drawing
$\bm{S}\sim\mathcal{D}^{n}$ and 2), drawing
$\bm{x}\sim\mathcal{U}(\widehat{\bm{S}})$. Then,
$\rho(\mathcal{D},\widehat{\mathcal{D}})\leq\eta$.

Our quantitative bounds will depend on a parameter that is related to the
types of corruption the adversaries can make. Suppose that the adaptive
adversary is required to keep the size of the corrupted sample the same as the
clean sample ($|\widehat{S}|=|S|$). In this case, we require that if two
samples $S_{1}$ and $S_{2}$ differ in only one point, then for any
$\widehat{S}_{1}$ that is $\eta$-close to $S_{1}$, there is some
$\widehat{S}_{2}$ that is $\eta$-close to $S_{2}$ where $\widehat{S}_{1}$ and
$\widehat{S}_{2}$ differ in only a small number of points. The following
definition generalizes that notion to the case where the adversary can also
change the number of points in the sample.

######  Definition 16 ($\ell$-local).

For any $\ell>0$, a cost function $\rho$ with budget $\eta$ is $\ell$-local if
for any distributions $\mathcal{D},\mathcal{E}$, and $\widehat{\mathcal{D}}$,
there exists some $\widehat{\mathcal{E}}$ satisfying

$\displaystyle\rho(\mathcal{E},\widehat{\mathcal{E}})$
$\displaystyle\leq\rho(\mathcal{D},\widehat{\mathcal{D}}),$
$\displaystyle\operatorname{dist}_{\mathrm{TV}}(\widehat{\mathcal{D}},\widehat{\mathcal{E}})$
$\displaystyle\leq\ell\cdot\operatorname{dist}_{\mathrm{TV}}(\mathcal{D},\mathcal{E}).$

All of the adversary models in Section 3.1 are $1$-local with the exception of
the $\eta$-subtractive noise, which is $\frac{1}{1-\eta}$-local. We encourage
the reader to think of $\ell$ as a constant.

We are now ready to state the formal version of Theorem 1, which generalizes
4.1 to the setting of adversarial noise:

######  Theorem 5 (Formal version of Theorem 1; 4.1 for the noisy setting).

Fix an $\ell$-local cost function and an adversary budget $\eta$. Let
$\mathcal{D}$ be a distribution, $\mathcal{A}$ be a $k$-query SQ algorithm,
$n\in\mathds{N}$ be a sample size. With probability at least

$1-\exp\left(-\frac{\tau^{2}n}{8\ell^{2}}+k\log\left(\frac{2}{\tau}+1\right)\right)$

over the draw of $n$ independent samples $\bm{S}$ from $\mathcal{D}$, we have
that $\bm{S}$ is $\eta$-robustly representative of $\mathcal{D}$ with respect
to $\mathcal{A}$.

Therefore, when $\ell$ is constant, it suffices to set
$n=O(k\log(1/\tau)/\tau^{2})$ to ensure that $\bm{S}$ is $\eta$-robustly
representative of $\mathcal{D}$ with respect to $\mathcal{A}$ with high
probability.

###  4.2 Proof of overview and technical tools

We want to bound the probability that a set $\bm{S}\sim\mathcal{D}^{n}$ fails
to be $\eta$-robustly representative of $\mathcal{D}$ for $\mathcal{A}$. This
occurs when there is a $\widehat{\bm{S}}$ s.t.
$\rho(\mathcal{U}(\bm{S}),\mathcal{U}(\widehat{\bm{S}}))\leq\eta$ with values

$\begin{split}v_{1}&\coloneqq\mathrm{round}(\phi^{(1)}(\widehat{\bm{S}}),\tau)\\\
v_{i+1}&\coloneqq\mathrm{round}(\phi^{(i+1)}_{v_{1},\ldots,v_{i}}(\widehat{\bm{S}}),\tau)\quad\text{for
}i\in\\{0,1,\ldots,k-1\\},\end{split}$ (1)

but, for every $\widehat{\mathcal{D}}$ that is $\eta$-close to $\mathcal{D}$,
there is some $i$ for which
$|v_{i}-\phi^{(i)}_{v_{1},\ldots,v_{i-1}}(\widehat{\mathcal{D}})|>\tau$.

  1. 1.

In Lemma 4.5 we prove Theorem 5 in the special case where $\mathcal{A}$ makes
only one statistical query.

  2. 2.

In Lemma 4.6, we consider any possible set of values $v_{1},\ldots,v_{k}$. We
show that there is a reduction to a one-SQ algorithm $\mathcal{B}$ (so Lemma
4.5 applies), such that, for any sample $S\in\mathcal{X}^{n}$, if both of the
following hold:

    1. (a)

There is an $\widehat{S}$ satisfying Equation 1 such that
$\rho(\mathcal{U}(S),\mathcal{U}(\widehat{S}))\leq\eta$.

    2. (b)

For every $\widehat{\mathcal{D}}$ that is $\eta$-close to $\mathcal{D}$, there
is some $i$ for which
$|v_{i}-\phi^{(i)}_{v_{1},\ldots,v_{i-1}}(\widehat{\mathcal{D}})|>\tau$.

Then, $S$ is not $\eta$-robustly representative of $\mathcal{D}$ for
$\mathcal{B}$. By Lemma 4.5, this can only happen with exponentially small
probability.

  3. 3.

Finally, we complete the proof with a union bound over all $O(1/\tau)^{k}$
possible values $v_{1},\ldots,v_{k}$.

We will use a few standard technical tools:

######  Fact 4.3 (Separating hyperplane theorem).

Let $A,B\in\mathds{R}^{k}$ be disjoint, nonempty, and convex. There exists a
nonzero vector $w\in\mathds{R}^{k}$ and $T\in\mathds{R}$ such that $a\cdot
w\leq T$ and $b\cdot w\geq T$ for all $a\in A$ and $b\in B$.

######  Fact 4.4 (McDiarmid’s inequality).

Suppose that $f:\mathcal{X}^{n}\to\mathds{R}$ satisfies the $c$-bounded
difference property: for any
$(x_{1},\ldots,x_{n}),(x_{1}^{\prime},\ldots,x_{n}^{\prime})\in\mathcal{X}^{n}$
that differ on only on a single coordinate, $f$ satisfies

$\left|f(x_{1},\ldots,x_{n})-f(x_{1}^{\prime},\ldots
x_{n}^{\prime})\right|\leq c.$

Then, for any $\tau>0$ and any distribution $\mathcal{D}$ over $\mathcal{X}$,

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[f(\bm{S})-\mu\geq\tau]\leq\exp\left(-\frac{2\tau^{2}}{c^{2}n}\right)\quad\quad\quad\quad\text{where}\quad\mu\coloneqq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[f(\bm{S})].$

###  4.3 Proof of Theorem 5

Our first step is to prove Lemma 4.5 which is similar to Theorem 5 in the case
where $\mathcal{A}$ makes a single statistical query.444To prove Theorem 5 in
the case of a single statistical query, we could apply Lemma 4.5 twice: Once
to bound how large the adversary can make $\Psi(\widehat{\bm{S}})$ and once to
bound how small it can make $\Psi(\widehat{\bm{S}})$. Instead, we will
directly apply Lemma 4.5 to prove the multi-query case of Theorem 5.

######  Lemma 4.5 (Theorem 5 in the case of a single SQ).

Let $\Psi:\mathcal{X}\to[-1,1]$ be a statistical query, $T\in[-1,1]$, and
suppose:

$\Psi(\widehat{\mathcal{D}})\leq T\quad\quad\text{for all
$\widehat{\mathcal{D}}$ that are $\eta$-close to $\mathcal{D}$}.$

Then, for any $\tau>0$ and sample size $n\in\mathds{N}$, the probability over
$\bm{S}\sim\mathcal{D}^{n}$ that there is some ${{\widehat{\bm{S}}}}$ that is
$\eta$-close to $\bm{S}$ satisfying

$\Psi({{\widehat{\bm{S}}}})\geq T+\frac{\tau}{2}$

is at most $\exp\left(-\frac{\tau^{2}n}{8\ell^{2}}\right)$.

###### Proof.

For any sample $S\in\mathcal{X}^{n}$, define

$\displaystyle f(S)\coloneqq\sup_{{{\widehat{\mathcal{U}(S)}}}\text{ is
$\eta$-close to
}\mathcal{U}(S)}\left\\{\Psi({{\widehat{\mathcal{U}(S)}}})\right\\}.$

We will show that $f$ satisfies the $c\coloneqq\frac{2\ell}{n}$-bounded
difference property. Consider any samples $S,S^{\prime}\in\mathcal{X}^{n}$
that differ in only a single point. We will show that for every point in the
set

$\\{\Psi({{\widehat{\mathcal{U}(S)}}})\mid{{\widehat{\mathcal{U}(S)}}}\text{
is $\eta$-close to }\mathcal{U}(S)\\},$

there is some point in the set

$\\{\Psi({{\widehat{\mathcal{U}(S^{\prime})}}})\mid{{\widehat{\mathcal{U}(S^{\prime})}}}\text{
is $\eta$-close to }\mathcal{U}(S^{\prime})\\}$

that differs from it by at most $\pm\frac{2\ell}{n}$, and vice versa. This
implies that $f$ satisfies the $c\coloneqq\frac{2\ell}{n}$-bounded difference
property.

As $S$ and $S^{\prime}$ only differ in a single piont,

$\displaystyle\operatorname{dist}_{\mathrm{TV}}(\mathcal{U}(S),\mathcal{U}(S^{\prime}))\leq\frac{1}{n}.$

Furthermore by Definition 16, for any ${{\widehat{\mathcal{U}(S)}}}$ that is
$\eta$-close to $\mathcal{U}(S)$, there is some
${{\widehat{\mathcal{U}(S^{\prime})}}}$ that is $\eta$-close to
$\mathcal{U}(S^{\prime})$ satisfying

$\displaystyle\operatorname{dist}_{\mathrm{TV}}({{\widehat{\mathcal{U}(S)}}},{{\widehat{\mathcal{U}(S^{\prime})}}})\leq\frac{\ell}{n}.$

Using the Definition 2 and the fact that the range of $\Psi$ is a length-$2$
interval, the above implies that

$\displaystyle\left|\Psi({{\widehat{\mathcal{U}(S)}}})-\Psi({{\widehat{\mathcal{U}(S^{\prime})}}})\right|\leq\frac{2\ell}{n}$

proving that $f$ satisfies the $\frac{2\ell}{n}$-bounded difference property.
By McDiarmid’s inequality, $f(\bm{S})$ concentrates around its mean. Lastly,
we show that

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[f(\bm{S})]\leq
T.$ (2)

Suppose for the sake of contradiction that
$\mathop{{\mathds{E}}\/}[f(\bm{S})]>T-\varepsilon$ for some $\varepsilon>0$.
For each $S\in\mathcal{X}^{n}$, let ${{\widehat{\mathcal{U}(S)}}}$ be
$\eta$-close of $\mathcal{U}(S)$ satisfy
$\Psi({{\widehat{\mathcal{U}(S)}}})\geq f(S)-\varepsilon$ (which exists by the
definition of $f$). We can define $\widehat{\mathcal{D}}$ as the distribution
where, to sample $\bm{x}\sim\widehat{\mathcal{D}}$, we

  1. 1.

Draw an i.i.d. sample $\bm{S}\sim\mathcal{D}^{n}$.

  2. 2.

Draw $\bm{x}\sim{{\widehat{\mathcal{U}(\bm{S})}}}$ uniformly.

By 4.2, $\widehat{\mathcal{D}}$ is $\eta$-close to $\mathcal{D}$. Then,

$T\geq\Psi(\widehat{\mathcal{D}})=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\Psi({{\widehat{\mathcal{U}(\bm{S})}}})]\geq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\Psi(f(\bm{S}))-\varepsilon]=\mathop{{\mathds{E}}\/}[f(\bm{S})]-\varepsilon>T.$

This is a contradiction, so Equation 2 holds. Lemma 4.5 follows from
McDiarmid’s inequality applied to $f$. ∎

######  Lemma 4.6 ($k$-query SQ algorithm to a single SQ).

Fix any $k$ statistical queries
$\phi^{(1)},\ldots,\phi^{(k)}:\mathcal{X}\to[-1,1]$ and $k$ values
$v_{1},\ldots,v_{k}$. Suppose that there is no $\widehat{\mathcal{D}}$ that is
$\eta$-close to $\mathcal{D}$ satisfying

$\displaystyle\phi^{(i)}(\widehat{\mathcal{D}})\in
v_{i}\pm\tau\quad\quad\text{for every }i\in[k].$

Then there exists a single statistical query $\Psi:\mathcal{X}\to[-1,1]$ and
threshold $T$ with the following properties.

  1. 1.

$\Psi(\widehat{\mathcal{D}})\leq T$ for every $\widehat{\mathcal{D}}$ that is
$\eta$-close to $\mathcal{D}$.

  2. 2.

For any distribution $\mathcal{E}$ satisfying $\phi_{i}(\mathcal{E})\in
v_{i}\pm\frac{\tau}{2}$ for each $i\in[k]$, it is also true that
$\Psi(\mathcal{E})\geq T+\frac{\tau}{2}$.

###### Proof.

We define $A\in\mathds{R}^{d}$ to be

$\displaystyle
A\coloneqq\left\\{\left(\phi^{(1)}(\widehat{\mathcal{D}}),\ldots,\phi^{(k)}(\widehat{\mathcal{D}})\right)\mid\widehat{\mathcal{D}}\text{
is $\eta$-close to }\mathcal{D}\right\\},$

which is convex since the cost function is closed under mixtures (Definition
15). We define $B$ to be

$\displaystyle B\coloneqq\left\\{b\in\mathds{R}^{k}\mid b_{i}\in
v_{i}\pm\tau\text{ for all }i\in[k]\right\\},$

which is convex since it is the intersection of halfspaces. By the assumptions
of Lemma 4.6, $A$ and $B$ are disjoint. Let $w\in\mathds{R}^{k}$ and $T\in R$
be the vector and threshold respectively guaranteed to exist by the separating
hyperplane theorem, normalized so that $\|w\|_{1}=1$. We define

$\displaystyle\Psi(x)\coloneqq\sum_{i\in[k]}w_{i}\cdot\phi^{(i)}(x).$

As $\|w\|_{1}=1$ and the range of each $\phi^{(i)}(x)\in[-1,1]$ for each
$x\in\mathcal{X}$, it is also true that $\Psi(x)\in[-1,1]$. We show that
$\Psi,T$ meet the two criteria of Lemma 4.6. The first criteria holds by the
separating hyperplane theorem. The second criteria is equivalent to showing
that any $b\in B_{\mathrm{inner}}$ satisfies $b\cdot w\geq
T+\textstyle\frac{\tau}{2}$ where

$\displaystyle B_{\mathrm{inner}}\coloneqq\left\\{b\in\mathds{R}^{k}\mid
b_{i}\in v_{i}\pm\textstyle\frac{\tau}{2}\text{ for all }i\in[k]\right\\}.$

There must be a minimal point for $b\cdot w$ at a “corner” of $B$. Let
$b^{\star}$ be such a minimal point (i.e.
$(b^{\star})_{i}=v_{i}+c_{i}\cdot\tau$ for $c_{i}\in\\{\pm 1\\}$). For any
$b\in B_{\mathrm{inner}}$

$\displaystyle b\cdot w$ $\displaystyle=b^{\star}\cdot
w+\sum_{i\in[k]}w_{i}(b_{i}-b^{\star}_{i})$ $\displaystyle=b^{\star}\cdot
w+\sum_{i\in[k]}|w_{i}|\cdot|b_{i}-b^{\star}_{i}|$ ($b^{\star}$ minimal for
$b\cdot w$ over $b\in B$) $\displaystyle\geq b^{\star}\cdot
w+\sum_{i\in[k]}|w_{i}|\cdot\textstyle\frac{\tau}{2}$
($|b_{i}-b^{\star}_{i}|\geq\tau/2$ for $b\in B_{\mathrm{inner}}$)
$\displaystyle\geq T+\textstyle\frac{\tau}{2}.$ (Separating hyperplane
theorem, $\|w\|_{1}=1$)

This implies the second criteria of Lemma 4.6. ∎

We now complete the proof of Theorem 5:

###### Proof of Theorem 5.

Fix an $S\in\mathcal{X}^{n}$ that is not $\eta$-robustly representative of
$\mathcal{D}$ with respect to $\mathcal{A}$. This means that there exists an
$\widehat{S}$ such that $\mathcal{U}(\widehat{S})$ is $\eta$-close to
$\mathcal{U}(S)$ and $\widehat{S}$ is not representative of
$\widehat{\mathcal{D}}$ with respect to $\mathcal{A}$ for any
$\widehat{\mathcal{D}}$ that is $\eta$-close to $\mathcal{D}$. Therefore, if
we define:

$\displaystyle v_{1}$
$\displaystyle=\mathrm{round}(\phi^{(1)}(\widehat{S}),\tau)$ $\displaystyle
v_{i+1}$
$\displaystyle=\mathrm{round}(\phi^{(i+1)}_{v_{1},\ldots,v_{i}}(\widehat{S}),\tau)\quad\text{for
$i\in\\{0,1,\ldots,k-1\\}$},$

there is no $\widehat{\mathcal{D}}$ that is $\eta$-close to $\mathcal{D}$
satisfying:

$\phi^{(i+1)}_{v_{1},\ldots,v_{i}}({{\widehat{\mathcal{D}}}})\in
v_{i}\pm\tau\quad\text{for all $i\in[k]$.}$

By Lemmas 4.5 and 4.6, for any fixed choice of $v_{1},\ldots,v_{k}$,555Note
that once $v_{1},\ldots,v_{k}$ are fixed, this also fixes the $k$ statistical
queries $\phi^{(1)},\ldots,\phi^{(k)}$ and so Lemma 4.6 applies. this occurs
with probability at most $\exp\left(-\frac{\tau^{2}n}{8\ell^{2}}\right)$.
Since each $v_{i}\in[-1,1]$ is an integer multiple $\tau$, there are at most
$(\frac{2}{\tau}+1)^{k}$ many choices for $(v_{1},\ldots,v_{k})$. A union
bound over all these choices completes the proof of Theorem 5. ∎

######  Remark 2.

Theorem 5 also holds with strong adaptive adversaries (Definition 21 in
Section A.1) rather than just adaptive adversaries, with the appropriate
changes in constants. The proof only differs in Lemma 4.5. We then wish to
bound the probability that the adversary can make
$\Psi(\widehat{\bm{S}}^{\prime})\geq T+\tau/2$, where $\widehat{\bm{S}}$ and
$\widehat{\bm{S}}^{\prime}$ are as in Definition 21. For constant $\ell$,

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}[\Psi(\widehat{\bm{S}}^{\prime})\geq
T+\tau/2]$
$\displaystyle\leq\mathop{{\operatorname{{Pr}}}\/}_{\widehat{\bm{S}},\widehat{\bm{S}}^{\prime}}\left[|\Psi(\widehat{\bm{S}})-\Psi(\widehat{\bm{S}}^{\prime})|\geq\tau/4\right]+\mathop{{\operatorname{{Pr}}}\/}_{\widehat{\bm{S}}}[\Psi(\widehat{\bm{S}})\geq
T+\tau/4]$
$\displaystyle\leq\mathop{{\operatorname{{Pr}}}\/}_{\widehat{\bm{S}},\widehat{\bm{S}}^{\prime}}\left[\operatorname{dist}_{\mathrm{TV}}(\mathcal{U}(\widehat{\bm{S}}),\mathcal{U}(\widehat{\bm{S}}^{\prime}))\geq\tau/8\right]+\exp(-O(\tau^{2}n))$
(Lemma 4.5) $\displaystyle\leq\exp(-O(\tau^{2}n)).$ (Definition 21)

Once Lemma 4.5 is modified to handle strong adaptive adversaries, the
remainder of the proof of Theorem 5 applies unchanged.

##  5 Proof of Theorem 3: If adaptivity can be neutralized, subsampling does
it

Towards tackling 1 for all algorithms, we define the subsampling filter, a
natural “wrapper algorithm” that operates only on samples and can be applied
to any existing algorithm:

######  Definition 17 (Subsampling Filter).

Define the subsampling filter $\Phi_{m\to
n}:\mathcal{X}^{m}\to\mathcal{X}^{n}$ that, given a set $S\in\mathcal{X}^{m}$,
subsamples $n$ elements $\bm{S}^{\prime}\sim\mathcal{U}(S)^{n}$ and returns
them. We will also write $\Phi_{*\to n}$ when the size of $S$ is variable.

Intuitively, by requesting a large number of points $m$ and randomly
subsampling points for the original algorithm, the filter should able to
neutralise some of the power of the adaptive adversary, since the adversary
cannot know which subsample the algorithm will receive. In this section we
will prove Theorem 3 which, informally speaking, states that if the noise
model is such that adaptivity can be neutralised, then subsampling does it. In
the next section, we carry out this proof strategy for the specific case of
additive noise and establish Theorem 2.

###  5.1 Definitions and the formal statement of Theorem 3

We begin by formalizing what it means for the behavior of an algorithm
$\mathcal{A}$ in the presence of an oblivious adversary to be equivalent to
that of an algorithm $\mathcal{A}^{\prime}$ in the presence of an adaptive
adversary. Roughly speaking, that corresponds to the range of acceptance
probabilities $\mathcal{A}$ can have with all possible oblivious adversaries
being close to the range of acceptance probabilities that
$\mathcal{A}^{\prime}$ can have with all possible adaptive adversaries.

######  Definition 18.

Fix a cost function $\rho$, budget $\eta\geq 0$, and distribution
$\mathcal{D}$ over $\mathcal{X}$. For an algorithm
$\mathcal{A}:\mathcal{X}^{*}\to\\{0,1\\}$, we define:

$\displaystyle\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\coloneqq\sup_{\rho(\mathcal{D},\widehat{\mathcal{D}})\leq\eta}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]\right\\},$
$\displaystyle\mathrm{Oblivious\text{-}Min}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\coloneqq\inf_{\rho(\mathcal{D},\widehat{\mathcal{D}})\leq\eta}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]\right\\},$

the maximum and minimum acceptance probabilities of $\mathcal{A}$ given an
obliviously corrupted $\mathcal{D}$. We similarly define the adaptive
versions:

$\displaystyle\mathrm{Adaptive\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},m)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{m}}\Bigg{[}\sup_{\rho(\mathcal{U}(\bm{S}),\mathcal{U}(\widehat{\bm{S}}))\leq\eta}\left\\{\mathcal{A}(\widehat{\bm{S}})\right\\}\Bigg{]},$
$\displaystyle\mathrm{Adaptive\text{-}Min}_{\rho,\eta}(\mathcal{A},\mathcal{D},m)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{m}}\Bigg{[}\inf_{\rho(\mathcal{U}(\bm{S}),\mathcal{U}(\widehat{\bm{S}}))\leq\eta}\left\\{\mathcal{A}(\widehat{\bm{S}})\right\\}\Bigg{]}.$

######  Definition 19 ($\varepsilon$-equivalent).

Fix a cost function $\rho$ and a budget $\eta\geq 0$. Let
$\mathcal{A},\mathcal{A}^{\prime}:\mathcal{X}^{*}\to\\{0,1\\}$ be two
algorithms. We say that $\mathcal{A}$ in the presence of
$(\rho,\eta)$-oblivious adversaries is $(n,m,\varepsilon)$-equivalent to
$\mathcal{A}^{\prime}$ in the presence of $(\rho,\eta)$-adaptive adversaries
if the following holds for all distributions $\mathcal{D}$ over $\mathcal{X}$:

$\mathrm{Adaptive\text{-}Max}_{\rho,\eta}(\mathcal{A}^{\prime},\mathcal{D},m)=\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\pm\varepsilon,$

and likewise for $\mathrm{Min}$ instead of $\mathrm{Max}$. If the algorithms
$\mathcal{A}$ or $\mathcal{A}^{\prime}$ are randomized, then these
expectations are also over the randomness of the algorithms.

We now state the formal version of Theorem 3:

######  Theorem 6 (Formal version of Theorem 3: If it is possible, subsampling
does it).

Fix a cost function $\rho$ and budget $\eta\geq 0$. Suppose that $\mathcal{A}$
and $\mathcal{A}^{\prime}$ are algorithms where $\mathcal{A}$ in the presence
of $(\rho,\eta)$-oblivious adversaries is $(n,m,\varepsilon)$-equivalent to
$\mathcal{A}^{\prime}$ in the presence of $(\rho,\eta)$-adaptive adversaries.

Consider the subsampling algorithm
$\mathcal{A}_{\mathrm{sub}}\coloneqq\mathcal{A}\circ\Phi_{*\to n}$ which,
given a sample $S\in\mathcal{X}^{*}$, subsamples $n$ elements
$\bm{S}^{\prime}\sim\mathcal{U}(S)^{n}$ and returns
$\mathcal{A}(\bm{S}^{\prime})$. For

$M\coloneqq
O\left(\frac{m^{2}\log(1/\varepsilon)^{2}}{\varepsilon^{5}}\right),$

we have that $\mathcal{A}$ in the presence of $(\rho,\eta)$-oblivious
adversaries is $(n,M,9\varepsilon)$-equivalent to $\mathcal{A}_{\mathrm{sub}}$
in the presence of $(\rho,\eta)$-adaptive adversaries.

######  Remark 3 (Search to decision reduction).

In both Theorems 2 and 3, we focus on decision algorithms that output a single
bit $\\{0,1\\}$, rather than the more general setting of search algorithms
that output an answer from some set $\mathcal{Y}$. This is without loss of
generality. Given a search algorithm
$\mathcal{A}:\mathcal{X}^{*}\to\mathcal{Y}$, and any set of “good outputs”
$Y\subseteq\mathcal{Y}$, we could define an algorithm
$\mathcal{B}\coloneqq\mathds{1}_{Y}\circ\mathcal{A}$ where $\mathcal{B}(S)=1$
iff $\mathcal{A}(S)\in Y$. Then, we can directly apply Theorems 2 and 3 to
$\mathcal{B}$. Hence, Theorems 2 and 3 hold for search algorithms with the
appropriate definition of “equivalence” for search algorithms: We say
$\mathcal{A}:\mathcal{X}^{\star}\to\mathcal{Y}$ and
$\mathcal{A}^{\prime}:\mathcal{X}^{\star}\to\mathcal{Y}$ are
$\varepsilon$-equivalent if for every $Y\subseteq\mathcal{Y}$,
$\mathds{1}_{Y}\circ\mathcal{A}$ and $\mathds{1}_{Y}\circ\mathcal{A}^{\prime}$
are $\varepsilon$-equivalent (according to Definition 19).

###  5.2 Proof of Theorem 6

Our proof of Theorem 6 relies on the following simple lemma. Roughly speaking,
it states that sampling with replacement and sampling without replacement are
nearly indistinguishable when the population is a quadratic factor larger than
the number of samples.

######  Lemma 5.1.

For any distribution $\mathcal{D}$ and integers $m,M\in\mathds{N}$, let
$\Phi_{M\to m}\circ\mathcal{D}^{M}$ be the distribution with the following
generative process: first draw a size-$M$ sample $\bm{S}\sim\mathcal{D}^{M}$,
and then subsample, with replacement, $m$ points from $\bm{S}$. Then

$\operatorname{dist}_{\mathrm{TV}}(\mathcal{D}^{m},\Phi_{M\to
m}\circ\mathcal{D}^{M})\leq\frac{\binom{m}{2}}{M}.$

###### Proof.

We describe a coupling of $\bm{S}\sim\mathcal{D}^{m}$ and
$\bm{S}^{\prime}\sim\Phi_{M\to m}\circ\mathcal{D}^{M}$ such that
$\operatorname{{Pr}}[\bm{S}\neq\bm{S}^{\prime}]\leq\binom{m}{2}/M$.

  1. 1.

Initialize $S$ and $S^{\prime}$ to be empty sets, and $y_{1},\ldots,x_{M}$ to
be unset variables.

  2. 2.

Repeat $m$ times:

    1. (a)

Draw $\bm{i}\sim[M]$ uniformly.

    2. (b)

If $y_{\bm{i}}$ is unset, draw $\bm{x}\sim\mathcal{D}$ and set
$y_{\bm{i}}\leftarrow\bm{x}$. Then, add $\bm{x}$ to both $\bm{S}$ and
$\bm{S}^{\prime}$.

    3. (c)

Otherwise, add $y_{\bm{i}}$ to $\bm{S}^{\prime}$ and sample
$\bm{x}\sim\mathcal{D}$ to add to $\bm{S}$.

It is straightforward to verify that the above generative process leads to the
distribution of $\bm{S}$ and $\bm{S}^{\prime}$ being that of $\mathcal{D}^{m}$
and $\Phi_{M\to m}\circ\mathcal{D}^{M}$ respectively. Furthermore, if
$\bm{S}\neq\bm{S}^{\prime}$, that means there is some index $i\in[M]$ that was
sampled at least twice. If we fix $j_{1}\neq j_{2}\in[m]$ and some $i\in[M]$,
the probability $i$ is the index chosen at steps $j_{1}$ and $j_{2}$ is
$1/M^{2}$. Union bounding over the $M$ choices for $i$ and $\binom{m}{2}$ for
$j_{1},j_{2}$ gives that

$\operatorname{{Pr}}[\bm{S}\neq\bm{S}^{\prime}]\leq\frac{\binom{m}{2}}{M}.$

The desired result follows from the definition of total variation cost,
Definition 2. ∎

Lemma 5.1 will be used in conjunction with the following fact:

######  Fact 5.2.

Suppose there exists a test which, given $c$ samples from a distribution
$\mathcal{E}$ that is either $\mathcal{D}_{0}$ or $\mathcal{D}_{1}$, returns
$0$ if $\mathcal{E}=\mathcal{D}_{0}$ with probability at least $\frac{3}{4}$,
and returns $1$ if $\mathcal{E}=\mathcal{D}_{1}$ with probability at least
$\frac{3}{4}$. Then,

$\operatorname{dist}_{\mathrm{TV}}(\mathcal{D}_{1},\mathcal{D}_{2})\geq\frac{1}{2c}.$

Together, Lemma 5.1 and 5.2 imply that for appropriately chosen $m$ and $M$,
there is no sample-efficient test distinguishing $\mathcal{D}^{m}$ from
$\Phi_{M\to m}\circ\mathcal{D}_{M}$ with high probability. We will use this to
prove Theorem 6 by contradiction. Using the assumption that
$\mathcal{A}^{\prime}$ is equivalent to $\mathcal{A}$, we will design a
sample-efficient test that approximates
$\mathrm{Oblivious\text{-}Max}_{\rho,\eta}$ and
$\mathrm{Oblivious\text{-}Min}_{\rho,\eta}$ for $\mathcal{A}$ with respect to
both $\mathcal{D}^{m}$ and $\Phi_{M\to m}\circ\mathcal{D}^{M}$. We then show
that if $\mathcal{A}_{\mathrm{sub}}\coloneqq\Phi_{*\to n}\circ\mathcal{A}$ is
not equivalent to $\mathcal{A}$, then these values will distinguish the two
distributions.

The following lemma carries out the first part of this plan:

######  Lemma 5.3.

Let $\mathcal{A}$ and $\mathcal{A}^{\prime}$ be as in Theorem 6. There is an
estimator $\mathrm{Est\text{-}Max}_{\rho,\eta}$ that uses

$m^{\prime}\coloneqq\frac{m\log(2/\varepsilon)}{2\varepsilon^{2}}$

samples from a distribution $\mathcal{D}$ and returns an estimate of
$\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)$ that is
accurate to $\pm 2\varepsilon$ with probability at least $1-\varepsilon$, and
likewise an estimator $\mathrm{Est\text{-}Min}_{\rho,\eta}$ for
$\mathrm{Oblivious\text{-}Min}_{\rho,\eta}$. Formally, for all distributions
$\mathcal{D}$ over $\mathcal{X}$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{m^{\prime}}}\Big{[}\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})=\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\pm
2\varepsilon\Big{]}\geq 1-\varepsilon,$

and likewise for $\mathrm{Est\text{-}Min}_{\rho,\eta}$ and
$\mathrm{Oblivious\text{-}Min}_{\rho,\eta}$.

###### Proof.

We will prove the lemma for $\mathrm{Est\text{-}Max}_{\rho,\eta}$ and
$\mathrm{Oblivious\text{-}Max}_{\rho,\eta}$; the proof for Min instead of Max
is identical. $\mathrm{Est\text{-}Max}_{\rho,\eta}$ computes an estimate
satisfying:

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{m^{\prime}}}\Big{[}\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})=\mathrm{Adaptive\text{-}Max}_{\rho,\eta}(\mathcal{A^{\prime}},\mathcal{D},m)\pm\varepsilon\Big{]}\leq\varepsilon.$
(3)

This is sufficient to guarantee that $\mathrm{Est\text{-}Max}_{\rho,\eta}$’s
estimate is within $\pm 2\varepsilon$ of
$\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)$ by our
assumption that $\mathcal{A}$ is $(n,m,\varepsilon)$-equivalent to
$\mathcal{A}^{\prime}$. To provide such an estimate,
$\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})$ draws
$\log(2/\varepsilon)/(2\varepsilon^{2})$ many size-$m$ samples
$\bm{S}^{\prime}\sim\mathcal{D}^{m}$. For each, it computes:

$\sup_{\rho(\widehat{\bm{S}^{\prime}},\bm{S}^{\prime})\leq\eta}\big{\\{}\mathcal{A}^{\prime}(\widehat{\bm{S}^{\prime}})\big{\\}}$
(4)

and returns the average of these supremums. By the Chernoff bound, this
average satisfies Equation 3. ∎

######  Remark 4.

We are only concerned with the sample efficiency of these estimators, not
their time efficiency or even whether they are computable. Indeed, as stated,
an algorithm computing the estimators would need to loop or infinitely many
$\widehat{\bm{S}^{\prime}}\in\mathcal{X}^{*}$ to compute Equation 4. For us
they are just an analytical tool used to prove Theorem 6, the conclusion of
which gives an algorithm
$\mathcal{A}_{\mathrm{sub}}\coloneqq\mathcal{A}\circ\Phi_{*\to n}$ that
inherits the time efficiency of $\mathcal{A}$.

The next lemma notes that the $\mathrm{Adaptive\text{-}Max}_{\rho,\eta}$ of
$\mathcal{A}_{\mathrm{sub}}\coloneqq\mathcal{A}\circ\Phi_{*\to n}$ can be
expressed in terms of the $\mathrm{Oblivious\text{-}Max}_{\rho,\eta}$ of
$\mathcal{A}$. Formally:

######  Lemma 5.4.

$\displaystyle\mathrm{Adaptive\text{-}Max}_{\rho,\eta}(\mathcal{A}_{\mathrm{sub}},\mathcal{D},M)=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]},$
and likewise for $\mathrm{Min}$ instead of $\mathrm{Max}$.

###### Proof.

The lemma follows from this series of identities:

$\displaystyle\mathrm{Adaptive\text{-}Max}_{\rho,\eta}(\mathcal{A}_{\mathrm{sub}},\mathcal{D},M)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\Bigg{[}\sup_{\rho(\mathcal{U}(\bm{S}),\mathcal{U}(\widehat{\bm{S}}))\leq\eta}\left\\{\mathcal{A}_{\mathrm{sub}}(\widehat{\bm{S}})\right\\}\Bigg{]}$
(Definition of $\mathrm{Adaptive\text{-}Max}_{\rho,\eta}$)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\Bigg{[}\sup_{\rho(\mathcal{U}(\bm{S}),\mathcal{U}(\widehat{\bm{S}}))\leq\eta}\left\\{(\mathcal{A}\circ\Phi_{*\to
n})(\widehat{\bm{S}})\right\\}\Bigg{]}$ (Definition of
$\mathcal{A}_{\mathrm{sub}}$)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\Bigg{[}\sup_{\rho(\mathcal{U}(\bm{S}),\mathcal{E})\leq\eta}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}^{\prime}\sim\mathcal{E}^{n}}[\mathcal{A}(\bm{S}^{\prime})]\right\\}\Bigg{]}$
(Definition of the subsampling filter $\Phi_{*\to n}$)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]},$
(Definition of $\mathrm{Oblivious\text{-}Max}_{\rho,\eta}$)

where the penultimate identity also uses our convention that distributions
have rational weights, and therefore can expressed as the uniform distribution
over a sufficiently large multiset of elements. ∎

The following lemma completes the proof of Theorem 6.

######  Lemma 5.5.

Let $m^{\prime}$ be as in Lemma 5.3 and define $M\coloneqq
14(m^{\prime})^{2}/\varepsilon$. Then

$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]}=\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\pm
9\varepsilon,$

and likewise for $\mathrm{Min}$ instead of $\mathrm{Max}$.

###### Proof.

Our proof proceed by contradiction: assuming that
$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]}$
is more than $9\varepsilon$ far from
$\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)$, we
will prove that

$\displaystyle\operatorname{dist}_{\mathrm{TV}}(\mathcal{D}^{m^{\prime}},\Phi_{M\to
m^{\prime}}\circ\mathcal{D}^{M})\geq\frac{\varepsilon}{14}.$ (5)

From Lemma 5.1, we know that

$\operatorname{dist}_{\mathrm{TV}}(\mathcal{D}^{m^{\prime}},\Phi_{M\to
m^{\prime}}\circ\mathcal{D}^{M})<\frac{(m^{\prime})^{2}}{M}=\frac{\varepsilon}{14},$

which yields the desired contradiction. To establish Equation 5, we design an
algorithm that given
$\lceil\frac{6}{\varepsilon}\rceil\leq\frac{7}{\varepsilon}$ samples from
either $\mathcal{D}^{m^{\prime}}$ from $\Phi_{M\to
m^{\prime}}\circ\mathcal{D}^{M}$ is able to distinguish them with probability
$\frac{3}{4}$. Once we do, the desired result follows from 5.2.

Let
$\mu\coloneqq\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)$.
First, we define

$\displaystyle\delta\coloneqq\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}|\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)-\mu|>4\varepsilon\big{]}$

and we bound

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]}\leq(1-\delta)\cdot(\mu+4\varepsilon)+\delta\cdot
1\leq\mu+4\varepsilon+\delta.$

Similarly,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]}$
$\displaystyle\geq(1-\delta)\cdot(\mu-4\varepsilon)+\delta\cdot 0$
$\displaystyle\geq\mu-4\varepsilon-\delta.$ ($\mu-4\varepsilon\leq 1$)

Hence by our assumption that

$\displaystyle\left|\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]}-\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\right|>9\varepsilon,$

we can conclude that $\delta>5\varepsilon$.

Now let $\mathcal{E}$ be either $\mathcal{D}^{m^{\prime}}$ or $\Phi_{M\to
m^{\prime}}\circ\mathcal{D}^{M}$. Our test to determine which $\mathcal{E}$ is
will do the following: draw $\lceil\frac{6}{\varepsilon}\rceil$ samples from
$\mathcal{E}$, $\bm{S}\sim\mathcal{E}$, and run
$\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})$ on each. If less than a
$2\varepsilon$ fraction of the estimates returned by
$\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})$ differ from $\mu$ in more than
$\pm 2\varepsilon$, return that $\mathcal{E}=\mathcal{D}^{m^{\prime}}$.
Otherwise, return that $\mathcal{E}=\Phi_{M\to
m^{\prime}}\circ\mathcal{D}^{M}$. We will prove this test succeeds with
probability at least $1-e^{-2}\geq\frac{3}{4}$. We consider the two possible
cases:

  1. 1.

Case 1: $\mathcal{E}=\mathcal{D}^{m^{\prime}}$. In this case, given a sample
from $\mathcal{E}$, $\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})$ returns an
estimate that is within $\pm 2\varepsilon$ of $\mu$ with probability at least
$1-\varepsilon$. By the Chernoff bound, given $\frac{6}{\varepsilon}$ such
samples, the probability more than $2\varepsilon$ fraction deviate from $\mu$
by more than $\pm\varepsilon$ is at most
$\exp(-\frac{1}{3}\cdot\frac{6}{\varepsilon}\cdot\varepsilon)=e^{-2}$.
Therefore, the test succeeds with probability at least $1-e^{-2}$.

  2. 2.

Case 2: $\mathcal{E}=\Phi_{M\to m^{\prime}}\circ\mathcal{D}^{M}$. We showed
above that with probability at least $5\varepsilon$ over a sample
$\bm{S}\sim\mathcal{D}^{M}$ we have
$\left|\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)-\mu\right|>4\varepsilon$.
When that’s the case, $\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})$ returns an
estimate that is further than $\pm 2\varepsilon$ from $\mu$ with probability
at least $1-\varepsilon$. Therefore, on a single sample, the probability that
the estimate of $\mathcal{A}$ deviates from $\mu$ by more than $\pm
2\varepsilon$ is at least $5\varepsilon(1-\varepsilon)\geq 4\varepsilon$. By
the Chernoff bound, given $\frac{6}{\varepsilon}$ samples, the probability
that at most $2\varepsilon$ fraction deviate $\mu$ by at most $\pm
2\varepsilon$ is at most $\exp(-\frac{1}{8}\cdot\frac{6}{\varepsilon}\cdot
4\varepsilon)=e^{-3}$. Therefore, the test succeeds with probability at least
$1-e^{-2}$.

Hence, given $\lceil\frac{6}{\varepsilon}\rceil$ samples, it is possible to
distinguish $\mathcal{D}^{m^{\prime}}$ from $\Phi_{M\to
m^{\prime}}\circ\mathcal{D}^{M}$ with a success probability of at least
$\frac{3}{4}$. Equation 5 follows from 5.2, completing the proof by
contradiction. ∎

######  Remark 5 (Strong adaptive adversaries).

If $\mathcal{A}:\mathcal{X}^{n}\to\\{0,1\\}$ in the presence of oblivious
adversaries is $(n,M,\varepsilon)$-equivalent to
$\mathcal{A}_{\mathrm{sub}}\coloneqq\mathcal{A}\circ\Phi_{*\to n}$ in the
presence of adaptive adversaries, then it is also
$(n,M,2\varepsilon)$-equivalent to $\mathcal{A}_{\mathrm{sub}}$ in the
presence of _strong adaptive adversaries_ (Definition 21 in Section A.1) as
long as $M=\Omega(n^{2}/\varepsilon^{2})$. This applies to both Theorem 6 in
this section and Theorem 7 in the next.

Let $\widehat{\bm{S}}$ and $\widehat{\bm{S}}^{\prime}$ be defined as in
Definition 21. Then, for any strong adaptive adversary supplying the sample
$\widehat{\bm{S}}^{\prime}$, there is some adaptive adversary supplying the
sample $\widehat{\bm{S}}$, so we wish to compare
$\mathop{{\mathds{E}}\/}[\mathcal{A}_{\mathrm{sub}}(\widehat{\bm{S}}^{\prime})]$
to $\mathop{{\mathds{E}}\/}[\mathcal{A}_{\mathrm{sub}}(\widehat{\bm{S}})]$.
Recall that $\mathcal{A}_{\mathrm{sub}}$ first subsamples to $n$ points, so

$\displaystyle\left|\mathop{{\mathds{E}}\/}[\mathcal{A}_{\mathrm{sub}}(\widehat{\bm{S}}^{\prime})]-\mathop{{\mathds{E}}\/}[\mathcal{A}_{\mathrm{sub}}(\widehat{\bm{S}})]\right|$
$\displaystyle\leq
n\mathop{{\mathds{E}}\/}_{\widehat{\bm{S}},\widehat{\bm{S}}^{\prime}}[\operatorname{dist}_{\mathrm{TV}}(\mathcal{U}(\widehat{\bm{S}}),\mathcal{U}(\widehat{\bm{S}}^{\prime}))]$
$\displaystyle\leq O(n/\sqrt{M})=\varepsilon.$ (by Equation 13)

##  6 Proof of Theorem 2: The subsampling filter neutralizes adaptive additive
noise

In this section, we prove the following theorem:

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

Fix a budget $\eta\geq 0$, distribution $\mathcal{D}$ over $\mathcal{X}$, and
algorithm $\mathcal{A}:\mathcal{X}^{n}\to\\{0,1\\}$. Consider the subsampling
algorithm $\mathcal{A}_{\mathrm{sub}}\coloneqq\mathcal{A}\circ\Phi_{*\to n}$
which, given a sample $S\in\mathcal{X}^{*}$, subsamples $n$ elements
$\bm{S}^{\prime}\sim\mathcal{U}(S)^{n}$ and returns
$\mathcal{A}(\bm{S}^{\prime})$. For

$M\coloneqq O\left(\frac{n^{4}\log(|\mathcal{X}|)}{\varepsilon^{2}}\right),$

we have that $\mathcal{A}$ in the presence of
$(\mathrm{cost}_{\mathrm{add}},\eta)$-oblivious adversaries is
$(n,M,\varepsilon)$-equivalent to $\mathcal{A}_{\mathrm{sub}}$ in the presence
of $(\mathrm{cost}_{\mathrm{add}},\eta)$-adaptive adversaries.

Implicit in the proof of Theorem 6, we proved the following.

######  Lemma 6.1.

Fix a cost function $\rho$, budget $\eta\geq 0$, and $\varepsilon>0$. Suppose
that for an algorithm $\mathcal{A}:\mathcal{X}^{n}\to\\{0,1\\}$, there are
estimators
$\mathrm{Est\text{-}Max}_{\rho,\eta},\mathrm{Est\text{-}Min}_{\rho,\eta}:\mathcal{X}^{m}\to\\{0,1\\}$
that use $m$ samples from a distribution $\mathcal{D}$ and returns estimates
satisfying

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{m^{\prime}}}\Big{[}\mathrm{Est\text{-}Max}_{\rho,\eta}(\bm{S})=\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\pm
2\varepsilon\Big{]}\geq 1-\varepsilon,$

and likewise for $\mathrm{Min}$ instead of $\mathrm{Max}$. Then, for

$\displaystyle M=\frac{14m^{2}}{\varepsilon},$

we have that $\mathcal{A}$ in the presence of $(\rho,\eta)$-oblivious
adversaries is $(n,M,9\varepsilon)$-equivalent to
$\mathcal{A}_{\mathrm{sub}}\coloneqq\mathcal{A}\circ\Phi_{*\to n}$ in the
presence of $(\rho,\eta)$-adaptive adversaries.

In order to prove Theorem 7, we’ll construct the estimator
$\mathrm{Est\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}$ (and likewise
for Min). The goal is to estimate

$\displaystyle\mathrm{Oblivious\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}(\mathcal{A},\mathcal{D},n)\coloneqq\sup_{\widehat{\mathcal{D}}=(1-\eta)\cdot\mathcal{D}+\eta\cdot\mathcal{E}}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]\right\\}.$

The key insight is rather than trying all possible distributions
$\mathcal{E}$, to compute a $\pm\varepsilon$ approximation, it suffices to
consider those $\mathcal{E}$ that are equal to $\mathcal{U}(T)$ for some
$T\in\mathcal{X}^{n^{2}/\varepsilon}$. Our final result will have a
logarithmic dependence on the number of $\mathcal{E}$ we need to try, which
results in just a logarithmic dependence on $|\mathcal{X}|$.

The following definition and accompany fact will be useful.

######  Definition 20 (Stochastic function).

For any sets $\mathcal{X},\mathcal{Y}$, a stochastic function
${\bm{f}}:\mathcal{X}\to\mathcal{Y}$ is a collection of distributions
$\\{\mathcal{D}_{x}\mid x\in\mathcal{X}\\}$ each supported on $\mathcal{Y}$
where the notation ${\bm{f}}(x)$ indicates an independent draw from
$\mathcal{D}_{x}.$

######  Fact 6.2.

For any distribution $\mathcal{D}_{1},\mathcal{D}_{2}$ supported on a domain
$\mathcal{X}$, and any stochastic function
${\bm{f}}:\mathcal{X}\to\mathcal{Y}$, let ${\bm{f}}\circ\mathcal{D}_{i}$ be
the distribution where to sample $\bm{y}\sim{\bm{f}}\circ\mathcal{D}_{i}$, we
first sample $\bm{x}\sim\mathcal{D}_{i}$ and then sample
$\bm{y}={\bm{f}}(\bm{x})$. Then,

$\displaystyle\operatorname{dist}_{\mathrm{TV}}({\bm{f}}\circ\mathcal{D}_{1},{\bm{f}}\circ\mathcal{D}_{2})\leq\operatorname{dist}_{\mathrm{TV}}(\mathcal{D}_{1},\mathcal{D}_{2}).$

###### Proof.

Given a coupling of $\bm{x}_{1}\sim\mathcal{D}_{1}$ and
$\bm{x}_{2}\sim\mathcal{D}_{2}$, consider the coupling of
$\bm{y}_{1}\sim{\bm{f}}\circ\mathcal{D}_{1}$ and
$\bm{y}_{2}\sim{\bm{f}}\circ\mathcal{D}_{2}$ where if $\bm{x}_{1}=\bm{x}_{2}$
then $\bm{y}_{1}=\bm{y}_{2}={\bm{f}}(\bm{x}_{1})$ and otherwise
$\bm{y}_{1}={\bm{f}}(\bm{x}_{1})$ and $\bm{y}_{2}={\bm{f}}(\bm{x}_{2})$
independently. Then,

$\operatorname{{Pr}}[\bm{y}_{1}\neq\bm{y}_{2}]\leq\operatorname{{Pr}}[\bm{x}_{1}\neq\bm{x}_{2}],$

implying the desired result by Definition 2. ∎

To prove Theorem 7, we will design the estimators
$\mathrm{Est\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}$ and
$\mathrm{Est\text{-}Min}_{\mathrm{cost}_{\mathrm{add}},\eta}$. Plugging the
sample complexity of those estimators into Lemma 6.1 would be sufficient for
Theorem 7 with the slightly worse
$M=n^{6}\log(|\mathcal{X}|)^{2}/\varepsilon^{7}$. To get the optimal
$\log(|\mathcal{X}|)$ dependence on the domain size (and an improved
dependence on $n$ and $\varepsilon$), we need a more refined version of Lemma
6.1 that takes advantage of the structure of the particular estimators we
derive. The following Lemma applies for any cost function $\rho$, but we will
then design $\mathcal{F}$ satisfying Equation 6 specifically for
$\rho=\mathrm{cost}_{\mathrm{add}}$ in Lemma 6.4.

######  Lemma 6.3.

Fix a cost function $\rho$, budget $\eta\geq 0$, $\varepsilon\in(0,1]$, and
algorithm $\mathcal{A}:\mathcal{X}^{n}\to\\{0,1\\}$. Suppose there is a set of
stochastic functions $\mathcal{F}$ each $\mathcal{X}\to\mathcal{X}$, that
satisfy, for any distribution $\mathcal{D}$ over $\mathcal{X}$,

$\displaystyle\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}(\bm{S}))]\right\\}=\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\pm\varepsilon,$
(6)

and likewise for $\mathrm{Min}$ instead of $\mathrm{Max}$, where ${\bm{f}}(S)$
is shorthand for applying ${\bm{f}}$ element wise and independently to $S$.
Then:

  1. 1.

There are estimators
$\mathrm{Est\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}$ and
$\mathrm{Est\text{-}Min}_{\mathrm{cost}_{\mathrm{add}},\eta}$ meeting the
requirements of Lemma 6.1 for

$m^{\prime}=O\left(\frac{n\log(|\mathcal{F}|/\varepsilon)}{\varepsilon^{2}}\right).$

In particular, this implies that for

$M=O\left(\frac{n^{2}\log(|\mathcal{F}|/\varepsilon)^{2}}{\varepsilon^{5}}\right),$

we have that $\mathcal{A}$ in the presence of $(\rho,\eta)$-oblivious
adversaries is $(n,M,9\varepsilon)$-equivalent to $\mathcal{A}_{\mathrm{sub}}$
in the presence of $(\rho,\eta)$-adaptive adversaries.

  2. 2.

More directly, for

$\displaystyle
M=O\left(\frac{n^{2}\log(|\mathcal{F}|/\varepsilon)}{\varepsilon}\right)$ (7)

we have that $\mathcal{A}$ in the presence of $(\rho,\eta)$-oblivious
adversaries is $(n,M,5\varepsilon)$-equivalent to $\mathcal{A}_{\mathrm{sub}}$
in the presence of $(\rho,\eta)$-adaptive adversaries.

###### Proof.

We first give $\mathrm{Est\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}$
satisfying the first item. For $r\coloneqq
O(\frac{\log(|\mathcal{F}|/\varepsilon)}{\varepsilon^{2}})$, let

$\mathrm{Est\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}=\max_{{\bm{f}}\in\mathcal{F}}\Bigg{\\{}\underbrace{\mathop{{\mathds{E}}\/}_{\mathrm{trial}\in[r]}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}\left[\mathcal{A}({\bm{f}}(\bm{S}))\right]\right]}_{\coloneqq\mathrm{Est}^{({\bm{f}})}}\Bigg{\\}}.$

We note that as long as the samples are reused across different
${\bm{f}}\in\mathcal{F}$ that $m^{\prime}=rn$ samples from $\mathcal{D}$
suffices to compute the above expression. By Hoeffding’s inequality, for any
fixed ${\bm{f}}\in\mathcal{F}$, with probability at least
$1-\frac{\varepsilon}{T}$

$\mathrm{Est}^{({\bm{f}})}=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}(\bm{S}))]\pm\varepsilon.$

By union bound, with probability at least $1-\varepsilon$, the above holds for
every ${\bm{f}}\in\mathcal{F}$. If so,
$\mathrm{Est\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}$ has the desired
accuracy by Equation 6.

Next, we prove the $M$ from Equation 7 suffices. By Lemma 5.4, it suffices to
prove that

$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\big{[}\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{U}(\bm{S}),n)\big{]}=\mathrm{Oblivious\text{-}Max}_{\rho,\eta}(\mathcal{A},\mathcal{D},n)\pm
5\varepsilon,$

and likewise for $\mathrm{Min}$ instead of $\mathrm{Max}$. Applying Equation 6
to both sides of the above equation, it is sufficient to prove that

$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\bigg{[}\max_{{\bm{f}}\in\mathcal{F}}\bigg{\\{}\underbrace{\mathop{{\mathds{E}}\/}_{\bm{S}_{n}\sim\mathcal{U}(\bm{S})^{n}}[\mathcal{A}({\bm{f}}(\bm{S}_{n}))]}_{\coloneqq
g^{({\bm{f}})}(\bm{S})}\bigg{\\}}\bigg{]}=\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}(\bm{S}))]\right\\}\pm
3\varepsilon.$ (8)

Fix a single ${\bm{f}}\in\mathcal{F}$. We’ll use McDiarmid’s inequality (4.4)
to say that $g^{({\bm{f}})}(\bm{S})$ concentrates around its mean. Take any
$S\in\mathcal{X}^{M}$ and suppose we change one point in it to create
$S^{\prime}$. Then $|g^{({\bm{f}})}(S)-g^{({\bm{f}})}(S^{\prime})|$ is at most
the probability that the changed point appears in $\bm{S}_{n}$, which is at
most $\frac{n}{M}$. Applying McDiarmid’s inequality,

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{m}}\left[g^{({\bm{f}})}(\bm{S})=\mu^{({\bm{f}})}\pm\varepsilon\right]$
$\displaystyle\geq 1-2\exp\left(-\frac{2\varepsilon^{2}}{(n/M)^{2}M}\right)$
where
$\mu^{({\bm{f}})}\coloneqq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\left[g^{({\bm{f}})}(\bm{S})\right]$
$\displaystyle\geq 1-\frac{\varepsilon}{|\mathcal{F}|}.$ (using
$M=O\left(\frac{n^{2}\log(|\mathcal{F}|/\varepsilon)}{\varepsilon}\right)$)

By union bound, with probability at least $1-\varepsilon$, for every
${\bm{f}}\in\mathcal{F}$ we have that
$g^{({\bm{f}})}(\bm{S})=\mu^{({\bm{f}})}\pm\varepsilon$ allowing us to bound
the left hand side of Equation 8,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{M}}\left[\max_{{\bm{f}}\in\mathcal{F}}\left\\{g^{({\bm{f}})}(\bm{S})\right\\}\right]$
$\displaystyle=\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mu^{({\bm{f}})}\right\\}\pm\varepsilon\pm\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{m}}\left[g^{({\bm{f}})}(\bm{S})\neq\mu^{({\bm{f}})}\pm\varepsilon\text{
for some ${\bm{f}}\in\mathcal{F}$}\right]$
$\displaystyle=\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mu^{({\bm{f}})}\right\\}\pm
2\varepsilon.$

Lastly, we want to compare the above to the right hand side of Equation 8 to
$\max_{{\bm{f}}\in\mathcal{F}}\mu^{({\bm{f}})}$. Fix any
${\bm{f}}\in\mathcal{F}$. Using the notation of Lemma 5.1,

$\mu^{({\bm{f}})}=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\Phi_{M\to
n}\circ\mathcal{D}^{M}}\left[\mathcal{A}({\bm{f}}(\bm{S}))\right].$

Therefore,

$\displaystyle\left|\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mu^{({\bm{f}})}\right\\}-\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}(\bm{S}))]\right\\}\right|$
$\displaystyle\leq\max_{{\bm{f}}\in[\mathcal{F}]}\left|\mu^{({\bm{f}})}-\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}(\bm{S}))]\right|$
$\displaystyle\leq\operatorname{dist}_{\mathrm{TV}}(\mathcal{D}^{n},\Phi_{M\to
n}\circ\mathcal{D}^{M})$ (Definition 2)
$\displaystyle\leq\frac{\binom{n}{2}}{M}\leq\varepsilon.$ (Lemma 5.1)

Therefore, the left hand term of Equation 8 is within $\pm 2\varepsilon$ of
$\max_{{\bm{f}}\in\mathcal{F}}\mu^{({\bm{f}})}$ and the right hand term is
within $\pm\varepsilon$ of $\max_{{\bm{f}}\in\mathcal{F}}\mu^{({\bm{f}})}$.
Hence, Equation 8 holds, completing this proof. ∎

In order to use Lemma 6.3, we need to design $\mathcal{F}$ and prove that it
satisfies Equation 6 when $\rho=\mathrm{cost}_{\mathrm{add}}$. The below lemma
completes the proof of Theorem 7.

######  Lemma 6.4.

Fix a budget $\eta\geq 0$, $\varepsilon\in(0,1]$, and algorithm
$\mathcal{A}:\mathcal{X}^{n}\to\\{0,1\\}$. Let $\mathcal{F}$ be the set of
$|\mathcal{X}|^{n^{2}/\varepsilon}$ stochastic functions defined below.

$\displaystyle\mathcal{F}\coloneqq\\{{\bm{f}}^{(T)}\mid
T\in\mathcal{X}^{n^{2}/\varepsilon}\\}\quad\quad\text{where}\quad{\bm{f}}^{(T)}(x)\coloneqq\begin{cases}x&\text{with
probability $1-\eta$}\\\ \bm{y}\text{ where
$\bm{y}\sim\mathcal{U}(T)$}&\text{with probability $\eta$.}\end{cases}$

Then for any $\mathcal{D}$ over $\mathcal{X}$,

$\displaystyle\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}(\bm{S}))]\right\\}$
$\displaystyle=\mathrm{Oblivious\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}(\mathcal{A},\mathcal{D},n)\pm\varepsilon$
$\displaystyle=\sup_{\widehat{\mathcal{D}}=(1-\eta)\cdot\mathcal{D}+\eta\cdot\mathcal{E}}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]\right\\}\pm\varepsilon,$

and likewise for $\mathrm{Min}$ instead of $\mathrm{Max}$.

###### Proof.

Fix any distribution $\mathcal{D}$. First, we note that the distribution of
${\bm{f}}^{(T)}(\bm{x})$ where $\bm{x}\sim\mathcal{D}$ is simply that of
$(1-\eta)\cdot\mathcal{D}+\eta\cdot\mathcal{U}(T)$. Therefore, one direction
of the desired result is easy:

$\displaystyle\max_{{\bm{f}}\in\mathcal{F}}\left\\{\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}(\bm{S}))]\right\\}\leq\mathrm{Oblivious\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}(\mathcal{A},\mathcal{D},n).$

The remainder of this proof is devoted to proving the left hand side of the
above equation is at most $\varepsilon$ smaller than the right hand side. Fix
any distribution $\mathcal{E}$ and consider
$\widehat{\mathcal{D}}=(1-\eta)\cdot\mathcal{D}+\eta\cdot\mathcal{E}$. We’ll
show that

$\displaystyle\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\mathcal{E}^{n^{2}/\varepsilon}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}^{{\bm{T}}}(\bm{S}))]\right]\geq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]-\varepsilon.$
(9)

In particular, the above implies there is a single choice for $T$ that is
within $\varepsilon$ of
$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]$.
As this holds for all corruptions $\widehat{\mathcal{D}}$, it implies the
desired result.

To sample from $\widehat{\mathcal{D}}^{n}$ where
$\widehat{\mathcal{D}}=(1-\eta)\cdot\mathcal{D}+\eta\cdot\mathcal{E}$ we can
first draw $\bm{S}\sim\mathcal{E}^{n}$ and then return $\bm{h}(\bm{S})$,
applied element wise, where:

$\displaystyle\bm{h}(x)\coloneqq\begin{cases}\text{$\bm{y}$ where
$\bm{y}\sim\mathcal{D}$}&\text{with probability $1-\eta$}\\\
\text{$x$}&\text{with probability $\eta$.}\end{cases}$

Therefore, the distribution of ${\bm{f}}^{{\bm{T}}}(\bm{S})$ on the left hand
side of Equation 9 is $\bm{h}\circ\Phi_{n^{2}/\varepsilon\to
n}\circ\mathcal{E}^{n^{2}/\varepsilon}$ (using the notation of Lemma 5.1 and
6.2). Finally, we prove Equation 9 (recalling that
$\widehat{\mathcal{D}}=(1-\eta)\cdot\mathcal{D}+\eta\cdot\mathcal{E}$)

$\displaystyle\left|\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\mathcal{E}^{n^{2}/\varepsilon}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{A}({\bm{f}}^{{\bm{T}}}(\bm{S}))]\right]-\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]\right|$
$\displaystyle\leq\operatorname{dist}_{\mathrm{TV}}(\bm{h}\circ\Phi_{n^{2}/\varepsilon\to
n}\circ\mathcal{E}^{n^{2}/\varepsilon},\bm{h}\circ\mathcal{E}^{n})$
(Definition 2)
$\displaystyle\leq\operatorname{dist}_{\mathrm{TV}}(\Phi_{n^{2}/\varepsilon\to
n}\circ\mathcal{E}^{n^{2}/\varepsilon},\mathcal{E}^{n})$ (6.2)
$\displaystyle\leq\varepsilon.$ (Lemma 5.1 )

∎

##  7 Proof of Theorem 4: Lower bounds against the subsampling filter

In this section, we show a lower bound on $m$ needed for the subsampling
filter to work. Our lower bound holds in the setting of additive noise and
therefore also shows that the dependence on $|\mathcal{X}|$ in Theorem 7 is
optimal.

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

For any sample size $n$, domain $\mathcal{X}$ with $|\mathcal{X}|=2^{d}$ for
an integer $d$, adversary budget $\eta$, and $\varepsilon>0$, there exists an
algorithm $\mathcal{A}:\mathcal{X}^{n}\to\\{0,1\\}$ and corresponding
subsampled algorithm
$\mathcal{A}_{\mathrm{sub}}\coloneqq\mathcal{A}\circ\Phi_{*\to n}$ for which
$\mathcal{A}$ in the presence of
$(\mathrm{cost}_{\mathrm{add}},\eta)$-oblivious adversaries is _not_
$(n,m,1-\varepsilon)$-equivalent to $\mathcal{A}_{\mathrm{sub}}$ in the
presence of $(\mathrm{cost}_{\mathrm{add}},\eta)$-adaptive adversaries for any
$m=O_{\eta}(n\log|\mathcal{X}|/\log^{2}n)$.

##### Proof overview

Without loss of generality, we can consider the domain to be the Boolean
hypercube, $\mathcal{X}=\\{\pm 1\\}^{d}$. Otherwise, we could map the domain
to the hypercube. For an appropriate threshold $t$, we’ll define

$\displaystyle\mathcal{A}(x_{1},\ldots,x_{n})=\begin{cases}1&\text{if for
every $x_{i}$, there is an $x_{j}$ with $j\neq i$ s.t. $\langle
x_{i},x_{j}\rangle\geq t$,}\\\ 0&\text{otherwise.}\end{cases}$

Let $\mathcal{D}$ be uniform over $\mathcal{X}$. For any $\varepsilon>0$, $n$,
and $d$, we’ll show that there is a choice of $t$ such that:

  1. 1.

Lemma 7.1:
$\mathrm{Oblivious\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}(\mathcal{A},\mathcal{D},n)\leq{{\varepsilon/2}}$,
meaning, for any $\widehat{\mathcal{D}}=(1-\eta)\mathcal{D}+\eta\mathcal{E}$,
it is the case that
$\operatorname{{\mathds{E}}}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]\leq\varepsilon/2$.

  2. 2.

Lemma 7.2:
$\mathrm{Adaptive\text{-}Max}_{\mathrm{cost}_{\mathrm{add}},\eta}(\mathcal{A},\mathcal{D},m)\geq
1-\frac{\varepsilon}{2}$ whenever $m=O_{\eta}(n\log|\mathcal{X}|/\log^{2}n)$,
meaning that for $\bm{S}\sim\mathcal{D}^{m}$, the adaptive adversary can
choose $\lfloor m\cdot\eta/(1-\eta)\rfloor$ points ${\bm{T}}$ to add to the
sample for which

$\displaystyle\operatorname{{\mathds{E}}}[\mathcal{A}_{\mathrm{sub}}(\widehat{\bm{S}})]\geq
1-\textstyle\frac{\varepsilon}{2}\quad\text{where
}\widehat{\bm{S}}=\bm{S}\cup{\bm{T}}.$

Together, these prove that $\mathcal{A}$ in the presence of
$(\mathrm{cost}_{\mathrm{add}},\eta)$-oblivious adversaries is not
$(n,m,1-\varepsilon)$-equivalent to $\mathcal{A}_{\mathrm{sub}}$ in the
presence of $(\mathrm{cost}_{\mathrm{add}},\eta)$-adaptive adversaries.

######  Lemma 7.1.

For any distribution $\mathcal{E}$ and
$\widehat{\mathcal{D}}=(1-\eta)\mathcal{D}+\eta\mathcal{E}$,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]<\varepsilon/2.$

###### Proof.

First, we note that for any $x^{\prime}\in\mathcal{X}$ and a clean sample
$\bm{x}\sim\mathcal{D}$, the probability that
$\langle\bm{x},x^{\prime}\rangle\geq t$ is small: by Hoeffding’s inequality,
$\operatorname{{Pr}}_{\bm{x}\sim\mathcal{D}}[\langle\bm{x},x^{\prime}\rangle\geq
t]\leq\exp(-t^{2}/2d)$. Combining this with a simple union bound, we can show
that the probability of even a single clean point forming a correlated pair in
the sample is small:

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})]$
$\displaystyle\leq\eta^{n}+\mathop{{\mathds{E}}\/}_{\bm{S}\sim\widehat{\mathcal{D}}^{n}}[\mathcal{A}(\bm{S})\mid\text{at
least one clean point in $\bm{S}$}]$
$\displaystyle=\eta^{n}+\mathop{{\mathds{E}}\/}_{\begin{subarray}{c}\bm{x}\sim\mathcal{D}\\\
\bm{S}\sim\widehat{\mathcal{D}}^{n-1}\end{subarray}}[\mathcal{A}(\bm{S}\cup\\{\bm{x}\\})]$
$\displaystyle\leq\eta^{n}+\mathop{{\operatorname{{Pr}}}\/}_{\begin{subarray}{c}\bm{x}\sim\mathcal{D}\\\
\bm{S}\sim\widehat{\mathcal{D}}^{n-1}\end{subarray}}[\text{$\exists\bm{x}^{\prime}\in\bm{S}$
with $\langle\bm{x},\bm{x}^{\prime}\rangle\geq t$}]$ (weaken to just one clean
point)
$\displaystyle\leq\eta^{n}+(n-1)\mathop{{\operatorname{{Pr}}}\/}_{\begin{subarray}{c}\bm{x}\sim\mathcal{D}\\\
\bm{x}^{\prime}\sim\widehat{\mathcal{D}}\end{subarray}}[\langle\bm{x},\bm{x}^{\prime}\rangle\geq
t]$ (union bound over $S$)
$\displaystyle\leq\eta^{n}+n\exp\left({-\frac{t^{2}}{2d}}\right).$
(Hoeffding’s, over the randomness of $\bm{x}$)

This will be vanishingly small for the particular choice of $t$ determined in
Lemma 7.2. ∎

######  Lemma 7.2.

For any $m=O_{\eta}(nd/\log^{2}n)$, there exists an adversarial strategy that,
given $\bm{S}\in\mathcal{D}^{m}$, chooses $\lfloor m\cdot\eta/(1-\eta)\rfloor$
points ${\bm{T}}$ to add to the sample for which

$\displaystyle\operatorname{{\mathds{E}}}[\mathcal{A}_{\mathrm{sub}}(\widehat{\bm{S}})]\geq
1-\varepsilon/2\quad\text{where }\widehat{\bm{S}}=\bm{S}\cup{\bm{T}}$

###### Proof.

Let $C={{\lfloor m\cdot\eta/(1-\eta)\rfloor}}$ be the number of points the
adversary can add and denote the sample
$\bm{S}=\\{\bm{x}^{(1)},\ldots\bm{x}^{(m)}\\}$. The adversary constructs
${\bm{T}}=\\{\bm{y}^{(1)},\ldots,\bm{y}^{(C)}\\}$ by setting each
$\bm{y}^{(j)}$ to be the elementwise majority of $k$ chosen points from
$\bm{S}$ (where $k$ will be determined later). The idea is that $\bm{y}^{(j)}$
is a cluster center that will form a correlated pair with every one of these
$k$ points, with high probability.

More formally, for each $j=1,\ldots,C$, define
$\bm{S}^{(j)}=\\{x^{(1+(j-1)k\pmod{|\bm{S}|})},\ldots,x^{(jk\pmod{|\bm{S}|})}\\}$
to be the $j$-th chunk of $k$ points from $\bm{S}$, with the indices wrapping
around to the start of $\bm{S}$ as necessary. We take $\bm{y}^{(j)}$ to be the
elementwise majority666We can assume $k$ is odd for simplicity. of the points
in $\bm{S}^{(j)}$:

$\bm{y}^{(j)}_{\ell}\coloneqq\underset{\bm{x}\in
S^{(j)}}{\text{Maj}}\\{\bm{x}_{\ell}\\}\qquad\text{for $\ell=1,\ldots,d$.}$
(10)

First, we note that for a given $\bm{y}^{(j)}$, with high probability, any
point in $\bm{x}\in\bm{S}^{(j)}$ will have a large dot product with
$\bm{y}^{(j)}$:

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{S}^{(j)}\sim\mathcal{D}^{k}}[\langle\bm{x},\bm{y}^{(j)}\rangle]$
$\displaystyle=\sum_{\ell=1}^{d}\mathop{{\mathds{E}}\/}_{\bm{S}^{(j)}\sim\mathcal{D}^{k}}\left[\bm{x}_{\ell}\bm{y}^{(j)}_{\ell}\right]$
$\displaystyle={{\sum_{\ell=1}^{d}\left({\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}^{(j)}\sim\mathcal{D}^{k}}\left[\bm{x}_{\ell}=\bm{y}^{(j)}_{\ell}\right]-\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}^{(j)}\sim\mathcal{D}^{k}}\left[\bm{x}_{\ell}\neq\bm{y}^{(j)}_{\ell}\right]}\right)}}$
$\displaystyle={{\sum_{\ell=1}^{d}\left({\mathop{{\operatorname{{Pr}}}\/}_{\bm{u}\sim\text{Bin}(k-1,\frac{1}{2})}\left[\bm{u}\geq\frac{(k-1)}{2}\right]-\mathop{{\operatorname{{Pr}}}\/}_{\bm{u}\sim\text{Bin}(k-1,\frac{1}{2})}\left[\bm{u}<\frac{(k-1)}{2}\right]}\right)}}$
$\displaystyle={{d\mathop{{\operatorname{{Pr}}}\/}_{\bm{u}\sim\text{Bin}(k-1,\frac{1}{2})}\left[\bm{u}=\frac{(k-1)}{2}\right]}}$
$\displaystyle=\sqrt{\frac{2}{\pi}}{\frac{d}{\sqrt{k}}}(1\pm o(1)).$

Define $\mu\coloneqq(\sqrt{2/\pi})(d/\sqrt{k})$. We will take $t=\mu/2$ as the
threshold for $\mathcal{A}$, both here and in Lemma 7.1 as well. For
$\bm{S}^{(j)}\sim\mathcal{D}^{k}$, with $\bm{y}^{(j)}$ the elementwise
majority of $\bm{S}^{(j)}$, and any $\bm{x}\in S^{(j)}$, this gives:

$\displaystyle.\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}^{(j)}\sim\mathcal{D}^{k}}\left[\langle\bm{x},\bm{y}^{(j)}\rangle<t\right]$
$\displaystyle=\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}^{(j)}\sim\mathcal{D}^{k}}\left[\langle\bm{x},\bm{y}^{(j)}\rangle<\frac{\mu}{2}\right]$
$\displaystyle\leq\exp\left[-\Theta\left({\frac{\mu^{2}}{d}}\right)\right]$
(Hoeffding’s inequality)
$\displaystyle=\exp\left[-\Theta\left({\frac{d}{k}}\right)\right].$ (11)

The subsampling filter $\Phi_{*\to n}$ takes a random subsample of size $n$
from $\widehat{\bm{S}}=\bm{S}\cup{\bm{T}}$ (with replacement). We want to
show, with high probability over size $n$ subsamples
$\bm{S}^{\prime}\sim\mathcal{U}(\widehat{\bm{S}})^{n}$, that
$\mathcal{A}(\bm{S}^{\prime})=1$. For any point $\bm{x}\in\bm{S}$, we say
$\bm{y}^{(j)}\in{\bm{T}}$ is “good” for $\bm{x}$ if $\bm{x}$ was in the
cluster used to compute $\bm{y}^{(j)}$, meaning $\bm{x}\in\bm{S}^{(j)}$.
Similarly, for any $\bm{y}^{(j)}\in{\bm{T}}$, we say that $\bm{x}\in\bm{S}$ is
“good” for $\bm{y}^{(j)}$ is $\bm{x}\in\bm{S}^{(j)}$. By construction, a given
$\bm{x}\in\bm{S}$ participates in the computation of at least $\lfloor
Ck/m\rfloor=\Theta_{{{\eta}}}(k)$ many cluster centers $\bm{y}^{(j)}$’s, and
so for each $\bm{x}\in\bm{S}$, there are $\Theta_{{{\eta}}}(k)$ good
$\bm{y}\text{'s}\in T$. Similarly, there are exactly $k$ good
$\bm{x}\text{'s}\in S$ for each $\bm{y}\in T$. As $\widehat{\bm{S}}$ has size
$\Theta_{\eta}(m)$, for any $\bm{x}\in\bm{S}^{\prime}$, using
$\bm{c}_{\bm{x}}$ to denote the number of good points for $\bm{x}$ that show
up in $\bm{S}^{\prime}$, we have that $\bm{c}_{\bm{x}}$ is distributed as
$\text{Bin}(n,\Omega_{\eta}(k/m))$. This gives:

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}^{\prime}\sim\mathcal{U}(\widehat{\bm{S}})^{n}}[\mathcal{A}(\bm{S}^{\prime})=0]$
$\displaystyle=\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}^{\prime}\sim\mathcal{U}(\widehat{\bm{S}})^{n}}[\text{$\exists\bm{x}\in\bm{S}^{\prime}$
s.t.
$\forall\bm{x}^{\prime}\in\bm{S}^{\prime},\langle\bm{x},\bm{x}^{\prime}\rangle<t$}]$
$\displaystyle\leq
n\mathop{{\operatorname{{Pr}}}\/}_{\bm{x},\bm{S}^{\prime}\sim\mathcal{U}(\widehat{\bm{S}})^{n}}[\text{$\forall\bm{x}^{\prime}\in\bm{S}^{\prime},\langle\bm{x},\bm{x}^{\prime}\rangle<t$}]$
(union bound) $\displaystyle\leq
n\left[\operatorname{{Pr}}[\bm{c}_{\bm{x}}=0]+\mathop{{\operatorname{{Pr}}}\/}_{\bm{x},\bm{S}^{\prime}\sim\mathcal{U}(\widehat{\bm{S}})^{n}}[\text{$\forall\bm{x}^{\prime}\in\bm{S}^{\prime},\langle\bm{x},\bm{x}^{\prime}\rangle<t$}\mid\bm{c}_{\bm{x}}\geq
1]\right]$ $\displaystyle\leq
n\left[\operatorname{{Pr}}[\bm{c}_{\bm{x}}=0]+\mathop{{\operatorname{{Pr}}}\/}_{\bm{x},\bm{S}^{\prime}\sim\mathcal{U}(\widehat{\bm{S}})^{n}}[\text{$\langle\bm{x},\bm{y}_{\bm{x}}\rangle<t$]}\right]$
(weaken to good point) $\displaystyle\leq
n\left({1-\Theta_{\eta}\left({\frac{k}{m}}\right)}\right)^{n}+n\exp\left[-\Theta_{\eta}\left({\frac{d}{k}}\right)\right].$
(from Equation 11)

∎

##### Setting of parameters.

To complete the proof of Theorem 8, we need to choose $m$ and $k$ so that, all
the terms in Lemma 7.1 and Lemma 7.2 are vanishingly small. In particular, we
need $n\left({1-\Theta_{\eta}\left({{k}/{m}}\right)}\right)^{n}\to 0$ and
$n\exp\left({-\Theta_{\eta}\left({{d}/{k}}\right)}\right)\to 0$ as
$n\to\infty$. If $k=\Omega_{\eta}(m\log n/n)$ and $d=\Omega_{\eta}(k\log
n)=\Omega_{\eta}(m\log^{2}n/n)$ with sufficiently large constant factors, we
get the desired result. In other words, as long as $m\leq
O_{\eta}(nd/\log^{2}n)$, the adaptive adversary is stronger than the oblivious
adversary.

##  8 Conclusion

Through this work we hope to initiate the systematic study of the power of
adaptivity in statistical adversaries. A concrete direction for future work is
to answer 1 for other broad classes of algorithms and natural noise models,
either via the subsampling filter (1) or otherwise. Here we highlight the
specific case of subtractive noise: having resolved the case of additive noise
in this work, doing so for subtractive noise as well would be a significant
step towards resolving 1 for all three generic noise models described in
Section 3.1.1.

More speculatively, we suggest that there may be interesting connections
between our work and adaptive data analysis [DFH+15, HU14, SU15, BNS+21]. The
focus of our work is on the adaptivity of the adversary, whereas the focus of
this line of work is on the adaptivity of the algorithm. Does our result for
statistical queries (Theorem 5) also hold for the more general notions of low-
sensitivity and optimization queries studied in this literature? Can
techniques from this literature be used to improve the dependence on $k$ in
Theorem 5?

## Acknowledgements

We thank Adam Klivans and Greg Valiant for helpful conversations. We are
grateful to Greg for allowing us to include Theorem 4 which was proved jointly
with him.

Guy and Li-Yang are supported by NSF CAREER Award 1942123. Jane is supported
by NSF Award CCF-2006664. Ali is supported by a graduate fellowship award from
Knight-Hennessy Scholars at Stanford University.

## References

  * [BEK02] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz.  PAC learning with nasty noise.  Theoretical Computer Science, 288(2):255–275, 2002.
  * [BNS+21] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman.  Algorithmic stability for adaptive data analysis.  SIAM Journal on Computing, 2021.
  * [CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant.  Learning from untrusted data.  In Proceedings of the 49th Annual Symposium on Theory of Computing (STOC), pages 47–60, 2017.
  * [DFH+15] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth.  Preserving statistical validity in adaptive data analysis.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117–126, 2015.
  * [DK19] Ilias Diakonikolas and Daniel M Kane.  Recent advances in algorithmic high-dimensional robust statistics.  arXiv preprint arXiv:1911.05911, 2019.
  * [DKK+19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robust estimators in high-dimensions without the computational intractability.  SIAM Journal on Computing, 48(2):742–864, 2019.
  * [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.
  * [FGV17] Vitaly Feldman, Cristobal Guzmán, and Santosh Vempala.  Statistical query algorithms for mean vector estimation and stochastic convex optimization.  In Proceedings of the 28th Annual Symposium on Discrete Algorithms (SODA), pages 1265–1277, 2017.
  * [Ham71] Frank R. Hampel.  A General Qualitative Definition of Robustness.  The Annals of Mathematical Statistics, 42(6):1887 – 1896, 1971\.
  * [Hau92] David Haussler.  Decision theoretic generalizations of the pac model for neural net and other learning applications.  Information and Computation, 100(1):78–150, 1992.
  * [HRS21] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis with adaptive adversaries.  In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021.
  * [HU14] Moritz Hardt and Jonathan Ullman.  Preventing false discovery in interactive data analysis is hard.  In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 454–463, 2014.
  * [Hub64] Peter Huber.  Robust estimation of a location parameter.  The Annals of Mathematical Statistics, 35(1), 1964.
  * [Kea98] Michael Kearns.  Efficient noise-tolerant learning from statistical queries.  Journal of the ACM (JACM), 45(6):983–1006, 1998.
  * [KL93] Michael Kearns and Ming Li.  Learning in the presence of malicious errors.  SIAM Journal on Computing, 22(4):807–837, 1993.
  * [KSS94] Michael Kearns, Robert Schapire, and Linda Sellie.  Toward efficient agnostic learning.  Machine Learning, 17(2/3):115–141, 1994.
  * [LRV16] Kevin A Lai, Anup B Rao, and Santosh Vempala.  Agnostic estimation of mean and covariance.  In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665–674, 2016.
  * [Rey20] Lev Reyzin.  Statistical queries and statistical algorithms: Foundations and applications.  arXiv preprint arXiv:2004.00557, 2020.
  * [SU15] Thomas Steinke and Jonathan Ullman.  Interactive fingerprinting codes and the hardness of preventing false discovery.  In Proceedings of the 28th Conference on Learning Theory (COLT), pages 1588–1628, 2015.
  * [Tuk75] John W Tukey.  Mathematics and the picturing of data.  In Proceedings of the International Congress of Mathematicians, Vancouver, volume 2, pages 523–531, 1975.
  * [Val85] Leslie G. Valiant.  Learning disjunction of conjunctions.  In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI), pages 560–566, 1985.
  * [ZJS19] Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt.  Generalized resilience and robust statistics.  arXiv, abs/1909.08755, 2019.

##  Appendix A Appendix

###  A.1 Fixed vs random budgets

Recall in Section 3.2, with high probability, the number of changes the
random-budget adversary makes concentrates sharply around $\eta n$. Given an
adversarial strategy that involves modifying $\mathrm{Bin}(n,\eta)$ points, we
can turn it into one that modifies exactly $\lfloor n\eta\rfloor$ points by
changing at most $\tilde{O}(\sqrt{n})$ points and agrees with the original
strategy with high probability.

To make this more concrete, we define a stronger version of our
$(\rho,\eta)$-adaptive adversary. For all reasonable noise models, the
corresponding “randomized budgets” adversary fits within this stronger model
and all our proofs are readily extendable to it.

######  Definition 21 (Strong $(\rho,\eta)$-adaptive adversary).

Given a cost function $\rho$ and budget $\eta$, an $n$-sample algorithm
operating in the _strong_ $(\rho,\eta)$-adaptive adversary model will receive
as input the sample $\widehat{\bm{S}}^{\prime}$ where

  1. 1.

If the true data distribution is $\mathcal{D}$, first a clean sample
$\bm{S}\sim\mathcal{D}^{n}$ is generated.

  2. 2.

The adversary chooses a $\widehat{\bm{S}}$ satisfying
$\rho(\mathcal{U}(\bm{S}),\mathcal{U}(\widehat{\bm{S}}))\leq\eta$.

  3. 3.

The adversary chooses some $\widehat{\bm{S}}^{\prime}$ where, over the
randomness of the original sample and the adversaries decisions, the following
holds.

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\widehat{\bm{S}},\widehat{\bm{S}}^{\prime}}\left[\operatorname{dist}_{\mathrm{TV}}(\mathcal{U}(\widehat{\bm{S}}),\mathcal{U}(\widehat{\bm{S}}^{\prime}))\geq
t\right]$ $\displaystyle\leq\exp(-O(nt^{2}))\quad\quad\text{for all
$t\in(0,1)$}.$ (12)

All of our upper bounds on the strength of adaptive adversaries also apply to
the strong adaptive adversary. See Remark 2 for changes in the proof needed
for Theorem 1. For Theorems 2 and 3, we can use an even weaker restriction on
the adversary and only require that

$\displaystyle\mathop{{\mathds{E}}\/}_{\widehat{\bm{S}},\widehat{\bm{S}}^{\prime}}\left[\operatorname{dist}_{\mathrm{TV}}(\mathcal{U}(\widehat{\bm{S}}),\mathcal{U}(\widehat{\bm{S}}^{\prime}))\right]$
$\displaystyle=O(1/\sqrt{n})$ (13)

in place of Equation 12. See Remark 5 for how Equation 13 can be used to make
Theorems 2 and 3 work with strong adaptive adversaries.

###  A.2 Proof of 4.2

###### Proof.

By a standard inductive argument, Definition 15 implies that for any
$m\in\mathds{N}$, weights $\theta_{1},\ldots,\theta_{m}\geq 0$ summing to $1$
and distributions
$\mathcal{D}_{1},\ldots,\mathcal{D}_{m},\widehat{\mathcal{D}}_{1},\ldots,\widehat{\mathcal{D}}_{m}$,
that

$\displaystyle\rho\left(\sum_{i\in[m]}\theta_{i}\mathcal{D}_{i},\sum_{i\in[m]}\theta_{i}\widehat{\mathcal{D}}_{i}\right)\leq\max_{i\in[m]}\left\\{\rho\left(\mathcal{D}_{i},\widehat{\mathcal{D}}_{i}\right)\right\\}.$

The distribution $\mathcal{D}$ and $\widehat{\mathcal{D}}$ can be written as
the mixtures

$\displaystyle\mathcal{D}$
$\displaystyle=\sum_{S\in\mathcal{X}^{n}}\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\bm{S}=S]\mathcal{U}(S),$
$\displaystyle\widehat{\mathcal{D}}$
$\displaystyle=\sum_{S\in\mathcal{X}^{n}}\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{D}^{n}}[\bm{S}=S]\mathcal{U}(\widehat{S}).$

Since $\rho(\mathcal{U}(S),\mathcal{U}(\widehat{S}))\leq\eta$ for every
$S\in\mathcal{X}^{n}$, we can conclude
$\rho(\mathcal{D},\widehat{\mathcal{D}})\leq\eta$. ∎