concept be chosen a priori, so as to have a well-defined $\mathsf{EX}(c,D)$
oracle. This is closer to the variant of the online learning setting in which
an adversary must fix an instance’s label before the learner makes a
prediction (Littlestone,, 1988).

###  19 Robust Learning with Local Membership Queries

In this section, we study the power of local membership queries in robust
learning. We will focus on whether giving access to a $\lambda$-$\mathsf{LMQ}$
oracle can improve the robustness thresholds from Chapter 5.

We show a negative result: the amount of data needed to $\rho$-robustly learn
conjunctions under the uniform distribution has an exponential dependence on
the adversary’s budget $\rho$ even when the learner has access to the
$\mathsf{LMQ}$ oracle (in addition to the $\mathsf{EX}$ oracle). Here, the
lower bound on the sample drawn from the example oracle is $2^{\rho}$, which
is the same as the lower bound for _monotone_ conjunctions derived in Theorem
4.10, and the local membership query lower bound is $2^{\rho-1}$. The result
relies on showing that there there exists a family of conjunctions that remain
indistinguishable from each other on any sample of size $2^{\rho}$ and any
sequence of $2^{\rho-1}$ LMQs with constant probability.

######  Theorem 6.3.

Fix a monotone increasing robustness function
$\rho:\mathbb{N}\rightarrow\mathbb{N}$ satisfying $2\leq\rho(n)\leq n/4$ for
all $n$. Then, for any query radius $\lambda$, any $\rho(n)$-robust learning
algorithm for the class CONJUNCTIONS with access to the $\mathsf{EX}$ and
$\lambda$-$\mathsf{LMQ}$ oracles has joint sample and query complexity lower
bounds of $2^{\rho}$ and $2^{\rho-1}$ under the uniform distribution.

###### Proof.

Let $D$ be the uniform distribution and, without loss of generality, let
$\rho\geq 2$. Fix two disjoint sets $I_{1}$ and $I_{2}$ of $2\rho$ indices in
$[n]$ (i.e., $|I_{1}|=|I_{2}|=2\rho$), which will be the set of variables
appearing in potential target conjunctions $c_{1}$ and $c_{2}$, respectively
(i.e., their support). We have $2^{4\rho}$ possible pairs of such
conjunctions, as each variable can appear as a positive or negative literal.

Let us consider a randomly drawn sample $S$ of size $2^{\rho}$. We will first
consider what happens when all the examples in $S$ and the queried inputs
$S^{\prime}$ are negatively labelled. Each negative example $x\in S$ allows us
to remove at most $2^{2\rho+1}$ pairs from the possible set of pairs of
conjunctions, as each component $x_{I_{1}}$ and $x_{I_{2}}$ removes at most
one conjunction from the possible targets. By the same reasoning, each LMQ
that returns a negative example can remove at most $2^{2\rho+1}$ pairs of
conjunctions. Note that the parameter $\lambda$ is irrelevant in this setting
as each LMQ can only test one concept pair. Thus, after seeing any random
sample of size $2^{\rho}$ and querying any $2^{\rho-1}$ points, there remains

$\frac{2^{4\rho}-2^{3\rho+1}-2^{3\rho}}{2^{4\rho}}\geq 1/4$ (27)

of the initial conjunction pairs that label all points in $S$ and $S^{\prime}$
negatively. Then, choosing a pair $(c_{1},c_{2})$ of possible target
conjunctions uniformly at random and then choosing $c$ uniformly at random
gives at least a $1/4$ chance that $S$ and $S^{\prime}$ only contain negative
examples (both conjunctions are consistent with this).

Moreover, note that any two conjunctions in a pair will have a robust risk
lower bounded by $15/32$ against each other under the uniform distribution
(see Lemma 4.11). Thus, any learning algorithm $\mathcal{A}$ with LMQ query
budget $m^{\prime}=2^{\rho-1}$ and strategy
$\sigma:(\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\})^{m}\rightarrow(\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\})^{m^{\prime}}$
(note that the queries can be adaptive) can do no better than to guess which
of $c_{1}$ or $c_{2}$ is the target if they are both consistent on the
augmented sample $S\cup\sigma(S)$, giving an expected robust risk lower
bounded by a constant. Letting $\mathcal{E}$ be the event that all points in
both $S$ and $\sigma(S)$ are labelled zero, we get

$\displaystyle\underset{{c,S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(\mathcal{A}(S\cup\sigma(S)),c)\right]$
$\displaystyle\geq\underset{{c,S}}{\Pr}\left(\mathcal{E}\right)\underset{{c,S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(\mathcal{A}(S\cup\sigma(S)),c)\;|\;\mathcal{E}\right]$
(Total Expectation)
$\displaystyle\geq\frac{1}{4}\;\underset{{c,S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(\mathcal{A}(S\cup\sigma(S)),c)\;|\;\mathcal{E}\right]$
(Equation 27)
$\displaystyle=\frac{1}{4}\cdot\frac{1}{2}\;\underset{{S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(\mathcal{A}(S\cup\sigma(S)),c_{1})+\mathsf{R}_{\rho}^{D}(\mathcal{A}(S\cup\sigma(S)),c_{2})\;|\;\mathcal{E}\right]$
(Random choice of $c$)
$\displaystyle\geq\frac{1}{8}\;\underset{{S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(c_{1},c_{2})\;|\;\mathcal{E}\right]$
(Lemma 4.9) $\displaystyle>\frac{1}{8}\cdot\frac{15}{32}$ (Lemma 4.11)
$\displaystyle=\frac{15}{256}\enspace,$

which completes the proof. ∎

Now, since the local membership query lower bound above has an exponential
dependence on $\rho$, any perturbation budget $\omega(\log n)$ will require a
sample and query complexity that is superpolynomial in $n$, giving the
following corollary.

######  Corollary 6.4.

The robustness threshold of the class CONJUNCTIONS under the uniform
distribution with access to $\mathsf{EX}$ and an $\mathsf{LMQ}$ oracle is
$\Theta(\log(n))$.

Observe that the robustness threshold above is the same as when only using the
$\mathsf{EX}$ oracle in Theorem 4.10, and that, as decision lists and
halfspaces both subsume conjunctions, the lower bound of Theorem 6.3 also
holds for these classes. Since we cannot improve the robustness threshold of
conjunctions and superclasses under the uniform distribution with access to
the $\mathsf{LMQ}$ oracle, we will turn our attention to a more powerful
oracle in the next section.

###  20 Robust Learning with Local Equivalence Queries

In this section, we investigate the power of a local equivalence query oracle
in the _distribution-free_ robust learning setting. We start with a negative
result which shows that for a wide variety of concept classes, if
$\lambda<\rho$, then _distribution-free_ robust learnability is impossible in
the $\mathsf{EX}$+$\lambda$-$\mathsf{LEQ}$ model – regardless of how many
queries are allowed. This strengthens the impossibility result presented in
Theorem 4.8. However, the regime $\lambda=\rho$, which implies giving similar
power to the learner as the adversary, enables robust learnability guarantees.
Indeed, Section 20.2 exhibits upper bounds on sample sizes that will guarantee
_robust_ generalization. These bounds are logarithmic in the size of the
hypothesis class (finite case) and linear in the VC dimension of the _robust_
loss of a concept class (infinite case). Section 20.3 draws a comparison
between our framework and the online learning setting, and exhibits robustly
consistent learners. It furthermore studies conjunctions and presents a robust
learning algorithm that is _both_ statistically and computationally efficient.
It concludes by looking at linear classifiers in the discrete and continuous
cases. We adapt the Winnow algorithm in the former setting. In the latter, we
exhibit a sample complexity upper bound while outlining key obstacles to
derive query complexity upper bounds, which will be addressed in Section 21.

####  20.1 Impossibility of Distribution-Free Robust Learning for
$\lambda<\rho$

We start with a negative result, saying that whenever the local query radius
is strictly smaller than the adversary’s budget, monotone conjunctions are not
distribution-free robustly learnable. Note that this result goes beyond
efficiency: no query can distinguish between two potential targets. Choosing
the target uniformly at random lower bounds the expected robust risk, and
hence renders robust learning impossible in this setting.

######  Theorem 6.5.

For locality and robustness parameters $\lambda,\rho\in\mathbb{N}$ with
$\lambda<\rho$, monotone conjunctions (and any superclass) are not
distribution-free $\rho$-robustly learnable with access to a
$\lambda$-$\mathsf{LEQ}$ oracle.

The proof is similar in spirit to the earlier distribution-free impossibility
results from Chapter 4.

###### Proof.

Fix $\lambda,\rho\in\mathbb{N}$ such that $\lambda<\rho$, and consider the
following monotone conjunctions: $c_{1}(x)=\bigwedge_{1\leq i\leq\rho}x_{i}$
and $c_{2}(x)=\bigwedge_{1\leq i\leq\rho+1}x_{i}$. Let $D$ be the distribution
on $\left\\{0,1\right\\}^{n}$ which puts all the mass on $\mathbf{0}$. Then,
the target concept is drawn at random between $c_{1}$ and $c_{2}$. Now,
$c_{1}$ and $c_{2}$ will both give all points in $B_{\lambda}(\mathbf{0})$ the
label 0, so the learner has to choose a hypothesis that is consistent with
both $c_{1}$ and $c_{2}$ (otherwise the robust risk is 1 and we are done).
However, the learner has no way of distinguishing which of $c_{1}$ or $c_{2}$
is the target concept, while these two functions have a $\rho$-robust risk of
1 against each other under $D$. Formally,

$\displaystyle\mathsf{R}_{\rho}^{D}(c_{1},c_{2})$
$\displaystyle=\underset{{x\sim D}}{\Pr}\left(\exists z\in
B_{\rho}(x)\;.\;c_{1}(z)\neq c_{2}(z)\right)$
$\displaystyle=\mathbf{1}[\exists z\in B_{\rho}(\mathbf{0})\;.\;c_{1}(z)\neq
c_{2}(z)]$ $\displaystyle=1\enspace,$ (28)

where such $z=\mathbf{1}_{\rho}\mathbf{0}_{n-\rho}$. To lower bound the
expected robust risk, letting $\mathcal{A}$ be any learning algorithm and
$\mathcal{E}$ be the event that all points in a randomly drawn sample $S$ are
all labeled 0, we have

$\displaystyle\underset{{c,S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(\mathcal{A}(S),c)\right]$
$\displaystyle=\underset{{c,S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(\mathcal{A}(S),c)\;|\;\mathcal{E}\right]$
(By construction of $D$)
$\displaystyle=\frac{1}{2}\;\underset{{S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(\mathcal{A}(S),c_{1})+\mathsf{R}_{\rho}^{D}(\mathcal{A}(S),c_{2})\;|\;\mathcal{E}\right]$
(Random choice of $c$)
$\displaystyle\geq\frac{1}{2}\;\underset{{S}}{\mathbb{E}}\left[\mathsf{R}_{\rho}^{D}(c_{1},c_{2})\;|\;\mathcal{E}\right]$
(Lemma 4.9) $\displaystyle=\frac{1}{2}\enspace.$ (Equation 28)

∎

The result holds for monotone conjunctions and all superclasses (e.g.,
decision lists and halfspaces), but, in fact, we can generalize this reasoning
to any concept class that has a certain form of stability: if we can find
concepts $c_{1}$ and $c_{2}$ in $\mathcal{C}$ and points
$x,x^{\prime}\in\mathcal{X}$ such that $c_{1}$ and $c_{2}$ agree on
$B_{\lambda}(x)$ but disagree on $x^{\prime}$, then if $\lambda<\rho$, the
concept class $\mathcal{C}$ is not distribution-free $\rho$-robustly learnable
with access to a $\lambda$-$\mathsf{LEQ}$ oracle. It suffices to “move” the
center of the ball $x$ until we find a point in the set $B_{\rho}(x)\setminus
B_{\lambda}(x)$ where $c_{1}$ and $c_{2}$ disagree, which is guaranteed to
happen by the existence of $x^{\prime}$. As hinted earlier, this is not
possible for parities, as any two parity functions $f_{I}$ and $f_{J}$ with
index sets $I$ and $J$, respectively, will disagree on $B_{1}(x)$ for any
$x\in\left\\{0,1\right\\}^{n}$, as it suffices to flip a bit in the symmetric
difference $I\Delta J$ to cause them to disagree.

####  20.2 Sample Complexity Upper Bounds

In this section, we show that we can derive sample complexity upper bounds for
_robustly_ consistent learners, i.e., learning algorithms that return a
hypothesis with a _robust_ loss of zero on a training sample. Note that,
crucially, the exact-in-the-ball notion of robustness and its realizability
imply that any robust ERM algorithm will achieve zero empirical robust loss on
a given training sample. As we will see in the next sections, the challenge is
to find a _robustly_ consistent learning algorithm that uses queries to
$\rho$-$\mathsf{LEQ}$. The first bound is for finite classes, where the
dependency is logarithmic in the size of the hypothesis class. The proof is a
simple application of Occam’s razor and is included in Appendix 9.A for
completeness. The argument is similar to Bubeck et al., (2019).

######  Lemma 6.6.

Let $\mathcal{C}$ be a concept class and $\mathcal{H}$ a hypothesis class. Any
$\rho$-robust ERM algorithm using $\mathcal{H}\supseteq\mathcal{C}$ on a
sample of size
$m\geq\frac{1}{\epsilon}\left(\log|\mathcal{H}_{n}|+\log\frac{1}{\delta}\right)$
is a $\rho$-robust learner for $\mathcal{C}$.

For the infinite case, we cannot immediately use the VC dimension as a tool
for bounding the sample complexity of robust learning. To this end, we use the
VC dimension of the robust loss between two concepts, which is the VC
dimension of the class of functions representing the $\rho$-expansion of the
error region between any possible target and hypothesis. This is analogous to
the adversarial VC dimension defined by Cullina et al., (2018) for the
constant-in-the-ball definition of robustness.

######  Definition 6.7 (VC dimension of the exact-in-the-ball robust loss).

Given a target concept class $\mathcal{C}$, a hypothesis class $\mathcal{H}$
and a robustness parameter $\rho$, the VC dimension of the robust loss between
$\mathcal{C}$ and $\mathcal{H}$ is defined as
$\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H}))$, where
$\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H})=\left\\{\ell_{\rho}(c,h):x\mapsto\mathbf{1}[\exists
z\in B_{\rho}(x)\;.\;c(z)\neq
h(z)]\;|\;c\in\mathcal{C},h\in\mathcal{H}\right\\}$. Whenever
$\mathcal{C}=\mathcal{H}$, we simply write
$\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C}))$.

We now show that we can use the VC dimension of the robust loss to upper bound
the sample complexity of robustly-consistent learning algorithms. We will use
this result in Section 20.5 when dealing with an infinite concept class:
halfspaces on $\mathbb{R}^{n}$.

######  Lemma 6.8.

Let $\mathcal{C}$ be a concept class and $\mathcal{H}$ a hypothesis class. Any
$\rho$-robust ERM algorithm using $\mathcal{H}$ on a sample of size
$m\geq\frac{\kappa}{\epsilon}\left(\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H}))\log(1/\epsilon)+\log\frac{1}{\delta}\right)$
for sufficiently large constant $\kappa$ is a $\rho$-robust learner for
$\mathcal{C}$.

###### Proof Sketch of Lemma 6.8..

The proof is very similar to the VC dimension upper bound in PAC learning. The
main distinction is that, instead of looking at the error region of the target
and any function in $\mathcal{H}$, we look at its $\rho$-expansion. Namely,
let the target $c\in\mathcal{C}$ be fixed and, for $h\in\mathcal{H}$, consider
the function $\ell_{\rho}(c,h):x\mapsto\mathbf{1}[\exists z\in
B_{\rho}(x)\;.\;c(z)\neq h(z)]$ and define a new concept class
$\Delta_{c,\rho}(\mathcal{H})=\left\\{\ell_{\rho}(c,h)\;|\;h\in\mathcal{H}\right\\}$.
It is easy to show that
$\mathsf{VC}(\Delta_{c,\rho}(\mathcal{H}))\leq\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H}))$,
as any sign pattern achieved on the LHS can be achieved on the RHS. The rest
of the proof follows from the definition of an $\epsilon$-net and the bound on
the growth function of $\Delta_{c,\rho}(\mathcal{H})$; see Appendix 9.B for
details. ∎

######  Remark 6.9.

Note that, for $\mathcal{X}=\left\\{0,1\right\\}^{n}$ and the Hamming
distance, as $\rho(n)/n$ tends to $1$, we move towards the exact and online
learning settings, and the underlying distribution becomes less important. In
this case, the VC dimension of the robust loss starts to decrease. Indeed, say
if $\rho=n$, then $\mathcal{L}_{\rho}(\mathcal{C})$ only contains the constant
functions $0$ and $1$. We thus only need a single example to query the
$\mathsf{LEQ}$ oracle (which has become the $\mathsf{EQ}$ oracle). However,
this comes at a cost: the _query complexity_ upper bounds presented in the
next sections could be tight.

####  20.3 General Query Complexity Upper Bounds

In the previous section, we derived sample complexity upper bounds for
robustly consistent learners. The challenge is thus to create algorithms that
perform robust empirical risk minimization, as we are operating in the
realizable setting. We begin by showing that online learning results can be
used to guarantee robust learnability. We recall the online learning setting
in Section 6.4. We denote by $\mathsf{Lit}(\mathcal{C})$ the Littlestone
dimension of a concept class $\mathcal{C}$, which appears in the query
complexity bound in the theorem below.

######  Theorem 6.10.

A concept class $\mathcal{C}$ is $\rho$-robustly learnable with the Standard
Optimal Algorithm (SOA) (Littlestone,, 1988) using the $\mathsf{EX}$ and
$\rho$-$\mathsf{LEQ}$ oracles with sample complexity
$m(n,\epsilon,\delta)=\frac{1}{\epsilon}\left(\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C}))\log(1/\epsilon)+\log\frac{1}{\delta}\right)$
and query complexity
$r(n,\epsilon,\delta)=m(n,\epsilon,\delta)\cdot\mathsf{Lit}(\mathcal{C})$.
Furthermore, if $\mathcal{C}$ is a finite concept class on
$\left\\{0,1\right\\}^{n}$, then $\mathcal{C}$ is $\rho$-robustly learnable
with sample complexity
$m(n,\epsilon,\delta)=\frac{1}{\epsilon}\left(\log(|\mathcal{C}|)+\log\frac{1}{\delta}\right)$
and query complexity
$r(n,\epsilon,\delta)=m(n,\epsilon,\delta)\cdot\mathsf{Lit}(\mathcal{C})$.

###### Proof.

The sample complexity bounds come from Lemmas 6.6 and 6.8 and the fact that
the Standard Optimal Algorithm (SOA) is a consistent learner, as it will be
given counterexamples in the perturbation region until a robust loss of zero
is achieved.

For each query to $\mathsf{LEQ}$, a counterexample is returned, or the robust
loss is zero. Then, using the mistake upper bound of SOA, which is
$\mathsf{Lit}(\mathcal{C})$, we get the query upper bound. ∎

Of course, some concept classes, e.g., thresholds, have infinite Littlestone
dimension, so Theorem 6.10 is not useful in these settings. In Section 21, we
will study assumptions on the adversary’s precision that give finite query
upper bounds for linear classifiers. But even if the Littlestone dimension is
finite, the SOA can be computationally inefficient, or even untractable.
However, if we have access to an online learning algorithm with a mistake
bound, it is possible to obtain robust learning guarantees. Indeed, the
theorem below exhibits a query upper bound for robustly learning with an
online algorithm $\mathcal{A}$ with a given mistake upper bound $M$. This is
moreover particularly useful in case $\mathcal{A}$ is _computationally_
efficient (which is not the case for the Standard Optimal Algorithm in Theorem
6.10) and $M$ is polynomial in the input dimension.

######  Lemma 6.11.

Let $\mathcal{C}$ be a concept class learnable in the online setting with
mistake bound $M(n)$. Then $\mathcal{C}$ is $\rho$-robustly learnable using
the $\mathsf{EX}$ and $\rho$-$\mathsf{LEQ}$ oracles with sample complexity
$m(n,\epsilon,\delta)=\frac{1}{\epsilon}\left(\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H}))+\log\frac{1}{\delta}\right)$
and query complexity $r(n,\epsilon,\delta)=m(n,\epsilon,\delta)\cdot M(n)$.

We remark that, implicit in the statement of the above lemma is the assumption
that all potential mistakes must be contained in the potential perturbation
region ($B_{\rho}(\text{supp}(D))$, the $\rho$-expansion of the support of the
distribution). We now proceed with the proof of the above lemma.

###### Proof.

The sample complexity bound is obtained from Lemma 6.8 and, for each point in
the sample, a query to $\mathsf{LEQ}$ can either return a robust loss of 0 or
1 and give a counterexample. Since the mistake bound is $M$, we have a query
upper bound of $r=m\cdot M$, as required. ∎

######  Remark 6.12.

In this section, we have assumed that $\lambda=\rho$. In Section 23.2, where
we compare the power of $\mathsf{LEQ}$ and $\mathsf{EQ}$, we will see a robust
learning scenario where $\lambda>\rho$ dramatically increases the query
complexity.

####  20.4 Improved Query Complexity Bounds for Conjunctions

We now show how to improve the query upper bound from the previous section in
the special case of conjunctions. Moreover, the algorithm used to robustly
learn conjunctions is both statistically and _computationally_ efficient,
which is not the case for the Standard Optimal Algorithm.

######  Theorem 6.13.

The class CONJUNCTIONS is efficiently $\rho$-robustly learnable in the
distribution-free setting using the $\mathsf{EX}$ and $\rho$-$\mathsf{LEQ}$
oracles with at most
$O\left(\frac{1}{\epsilon}\left(n+\log\frac{1}{\delta}\right)\right)$ random
examples and
$O\left(\frac{1}{\epsilon}\left(n+\log\frac{1}{\delta}\right)\right)$ queries
to $\rho$-$\mathsf{LEQ}$.

The algorithm achieving the above bounds is a straightforward adaptation of
the online learning algorithm for conjunctions in Section 6.4.

###### Proof.

Let $c$ be the target conjunction and let $D$ be an arbitrary distribution. We
describe an algorithm $\mathcal{A}$ with polynomial sample and query
complexity with access to a $\rho$-$\mathsf{LEQ}$ oracle. By Lemma 6.6, if we
can guarantee that $\mathcal{A}$ returns a hypothesis with zero robust loss on
a i.i.d. sample of size
$m=O\left(\frac{1}{\epsilon}\left(n+\log\frac{1}{\delta}\right)\right)$ with a
polynomial number of queries to the $\rho$-$\mathsf{LEQ}$ oracle, we are done.

The algorithm is similar to the standard PAC learning algorithm, in that it
only learns from positive examples. Indeed, the original hypothesis $h$ is a
conjunction of all $2n$ literals. After seeing a positive example $x$,
$\mathcal{A}$ removes from $h$ the literals $\bar{x_{i}}$ for $i=1,\dots,n$,
as they cannot be in $c$. Note that, by construction, any hypothesis $h$
returned by $\mathcal{A}$ always satisfies $c\subseteq h$.222222We overload
$c,h$ to mean both the functions and the set of literals in the conjunction,
as it will be unambiguous to distinguish them from context. Thus, any counter
example returned by the $\mathsf{LEQ}$ oracle will have that $c(z)=1$ and
$h(z)=0$. This allows us to remove at least one literal from the hypothesis
set for every counterexample. Now, it is easy to see that, for $c\subseteq
h^{\prime}\subseteq h$, if the robust loss $\mathbf{1}[\exists z\in
B_{\lambda}(x)\;.\;c(z)\neq h(z)]$ on $x$ w.r.t. $h$ is zero, so will be the
robust loss on $x$ w.r.t. the updated hypothesis $h^{\prime}$. Hence,
$\mathcal{A}$ makes at most $m+2n$ queries to the $\mathsf{LEQ}$ oracle. ∎

Note that the query upper bound that we get is of the form $m+M$, as opposed
to $m\cdot M$ from Lemma 6.8 (where $m$ is the sample complexity and $M$ the
mistake bound). Indeed, any update to the hypothesis will not affect the
consistency of previously queried points with robust loss of zero. Thus, once
zero robust loss is achieved on a point, it does not need to be queried again.

####  20.5 Bounds for Linear Classifiers

In this section, we first derive sample and query complexity upper bounds for
linear classifiers on $\left\\{0,1\right\\}^{n}$ with bounded weights. We then
derive sample complexity bounds for linear classifiers on $\mathbb{R}^{n}$ and
outline obstacles for query complexity upper bounds. Note that the robustness
threshold of linear classifiers on $\left\\{0,1\right\\}^{n}$ _without_ access
to the $\mathsf{LEQ}$ oracle remains an open problem, as pointed out in
Chapter 5.

Let $\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W}$ be the class of linear
threshold functions on $\left\\{0,1\right\\}^{n}$ with integer weights such
that the sum of the absolute values of the weights and the bias is bounded
above by $W$. We have the following theorem, whose proof relies on bounding
the size of $\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W}$ and using the
mistake bound for Winnow (Littlestone,, 1988).

######  Theorem 6.14.

The class $\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W}$ is $\rho$-robustly
learnable with access to the $\mathsf{EX}$ and $\rho$-$\mathsf{LEQ}$ oracles
using the Winnow algorithm with sample complexity
$m(n,\epsilon,\delta)=O\left(\frac{1}{\epsilon}\left(n+\min\left\\{n,W\right\\}\log(W+n)+\log\frac{1}{\delta}\right)\right)$
and local equivalence query complexity $r(n,\epsilon,\delta)=$
$O(m(n,\epsilon,\delta)\cdot W^{2}\log(n))$.

###### Proof.

The sample complexity bound uses Lemma 6.6. Note the class
$\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W}$ has size
$O(2^{n}(n+W)^{\min\left\\{n,W\right\\}})$. This is a simple application of
the _stars and bars_ identity, where $W$ is the number of stars and $n+1$ the
number of bars (as we are considering the bias term as well): ${n+W\choose
W}=O((n+W)^{min\left\\{n,W\right\\}})$. The $2^{n}$ term comes from the fact
that each weight can be positive or negative. The query complexity uses the
fact that the mistake bound for Winnow for
$\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W}$ is $O(W^{2}\log(n))$ in the case
of positive weights (the full statement can be found in Section 6.4).
Littlestone, (1988) outlines how to use the Winnow algorithm when the linear
classifier’s weights can vary in sign, at the cost of doubling the input
dimension and weight bound (see Theorem 10 and Example 6 therein). ∎

We now turn our attention to linear classifiers
$\mathsf{LTF}_{\mathbb{R}^{n}}$ on $\mathbb{R}^{n}$. We first show that, when
considering an adversary with bounded $\ell_{2}$-norm perturbations, we can
bound the sample complexity of robust learning for this class through a bound
on the VC dimension of the robust loss. However, the query complexity is
infinite in the general case (we will later prove an infinite lower bound in
Corollary 6.34). This is because the Littlestone dimension of thresholds, and
thus halfspaces, is infinite (see Section 6.4 for details). We will address
this issue in Section 21.

######  Theorem 6.15.

Let the adversary’s budget be measured by the $\ell_{2}$ norm. Then any
$\rho$-robust ERM learning algorithm for $\mathsf{LTF}_{\mathbb{R}^{n}}$ on
$\mathbb{R}^{n}$ has sample complexity
$m=O(\frac{1}{\epsilon}(n^{3}+\log(1/\delta)))$.

The proof of this theorem relies on deriving an upper bound on the VC
dimension of the robust loss of halfspaces. This enables us to bound the
sample complexity needed to guarantee robust accuracy. We will need the
following theorem from Goldberg and Jerrum, (1995):

######  Theorem 6.16 (Theorem 2.2 in (Goldberg and Jerrum,, 1995)).

Let $\left\\{\mathcal{C}_{k,n}\right\\}_{k,n\in\mathbb{N}}$ be a family of
concept classes where concepts in $\mathcal{C}_{k,n}$ and instances are
represented by $k$ and $n$ real values, respectively. Suppose that the
membership test for any instance $\alpha$ in any concept $C$ of
$\mathcal{C}_{k,n}$ can be expressed as a boolean formula $\Phi_{k,n}$
containing $s=s(k,n)$ distinct atomic predicates, each predicate being a
polynomial inequality or equality over $k+n$ variables (representing $C$ and
$\alpha$) of degree at most $d=d(k,n)$. Then
$\mathsf{VC}({\mathcal{C}_{k,n}})\leq 2k\log(8eds)$.

We will now translate the $\rho$-expansion of the error region (i.e., the
robust loss function) between two halfspaces as a boolean formula. The
following result from Renegar, (1992), will be instrumental to obtain our
result:

######  Theorem 6.17 (Theorem 1.2 in Renegar, (1992)).

Let $\Psi$ be a formula in the first-order theory of the reals of the form

$(Q_{1}x^{[1]}\in\mathbb{R}^{n_{1}})\dots(Q_{\omega}x^{[\omega]}\in\mathbb{R}^{n_{\omega}})P(x^{[1]},\dots,x^{[n_{\omega}]},y)\enspace,$

with free variables $y=(y_{1},\dots,y_{l})$, quantifiers $Q_{i}$ ($\exists$ or
$\forall$) and quantifier-free Boolean formula
$P(x^{[1]},\dots,x^{[n_{\omega}]},y)$ with $m$ atomic predicates consisting of
polynomial inequalities of degree at most $d$. There exists a procedure that
constructs an equivalent quantifier-free formula $\Phi$ of the form

$\bigvee_{i=1}^{I}\bigwedge_{j=1}^{J_{i}}(h_{ij}(y)\Delta_{ij}0)\enspace,$

where

$\displaystyle I$ $\displaystyle\leq(md)^{2^{O(\omega)}l\prod_{k}n_{k}}$
$\displaystyle J_{i}$ $\displaystyle\leq(md)^{2^{O(\omega)}\prod_{k}n_{k}}$
$\displaystyle\deg(h_{ij})$
$\displaystyle\leq(md)^{2^{O(\omega)}\prod_{k}n_{k}}$
$\displaystyle\Delta_{ij}$
$\displaystyle\in\left\\{\leq,\geq,=,\neq,>,<\right\\}\enspace.$

We are now ready to state the key technical lemma need for the proof of
Theorem 6.15.

######  Lemma 6.18.

Let $a,b\in\mathbb{R}^{n},a_{0},b_{0}\in\mathbb{R}$, and define the map
$\varphi:x\mapsto\mathbf{1}[\exists z\in
B_{\rho}(x)\;.\;\text{sgn}(a^{\top}z+a_{0})\neq\text{sgn}(b^{\top}z+b_{0})]$.
Then $\varphi$ can be represented as a boolean formula $\Phi$ with
$s=10^{Cn^{2}}$ distinct atomic predicates, with each predicate being a
polynomial inequality over $2n+2$ variables of degree at most
$10^{C^{\prime}n}$ for some constants $C,C^{\prime}>0$.

###### Proof.

First note that the predicate
$\text{sgn}(a^{\top}z+a_{0})\neq\text{sgn}(b^{\top}z+b_{0})$ can be
represented as the following formula:

$\left(a^{\top}z+a_{0}\geq 0\wedge
b^{\top}z+b_{0}<0\right)\vee\left(a^{\top}z+a_{0}<0\wedge b^{\top}z+b_{0}\geq
0\right)\enspace,$

which contains $n+(2n+2)$ variables and 4 predicates. Moreover, given a
perturbation $\zeta\in\mathbb{R}^{n}$, the constraint
$\left\|\zeta\right\|_{2}\leq\rho$ on its magnitude is a polynomial inequality
of degree 2:

$\sum_{i}\zeta_{i}^{2}\leq\rho^{2}\enspace.$

Now, consider the following formula:

$\Psi(x)=\exists\zeta\in\mathbb{R}^{n}\;.\;\left(\text{sgn}(a^{\top}(x+\zeta)+a_{0})\neq\text{sgn}(b^{\top}(x+\zeta)+b_{0})\wedge\left\|\zeta\right\|_{2}\leq\rho\right)\enspace.$

This is a formula of first-order logic over the reals. Using the notation of
Theorem 6.17, we have $\omega=1$ quantifier, and thus $\prod_{k}n_{k}=n$, one
Boolean formula with $m=5$ polynomial inequalities of degree $d$ at most $2$,
and $l=n$. Thus, $\Psi(x)$ can be expressed as a quantifier-free formula
$\Phi(x)=\bigvee_{i=1}^{I}\bigwedge_{j=1}^{J_{i}}(h_{ij}(y)\Delta_{ij}0)$ of
size

$I\max_{i}J_{i}\leq(md)^{2^{O(\omega)}l\prod_{k}n_{k}+2^{O(\omega)}\prod_{k}n_{k}}\leq
10^{Cn^{2}}$

for some constant $C$, where the polynomial inequalities are of degree at most
$(md)^{2^{O(\omega)}\prod_{k}n_{k}}\leq 10^{C^{\prime}n}$ for some constant
$C^{\prime}$. ∎

We thus get the following corollary.

######  Corollary 6.19.

The VC dimension of the robust loss of $\mathsf{LTF}_{\mathbb{R}^{n}}$ is
$O(n^{3})$.

###### Proof.

We let $s=10^{Cn^{2}}$, $k=2n+2$ and $d=10^{C^{\prime}n}$ from the proof above
and use Definition 6.7 and Theorem 6.16 to get a VC dimension of the robust
loss upper bound of $O(k\log(sd))=O(n^{3})$.232323Note that Corollary 2.4 in
Goldberg and Jerrum, (1995) uses this reasoning. ∎

Proving Theorem 6.15 is now a straightforward application of the results
above.

###  21 Robust Learning Against Precision-Bounded Adversaries

It is possible to obtain some relatively straightforward robustness guarantees
for classes with infinite Littlestone dimension if there exists a sufficiently
large margin between classes (in which case the exact-in-the-ball and
constant-in-the-ball notions of robustness coincide). However, some of these
results have already been derived in the literature. See, e.g., (Cullina et
al.,, 2018) for the sample complexity of halfspaces in the constant-in-the-
ball realizable setting w.r.t. $\ell_{p}$-norm adversaries, which improves on
the sample complexity bound of Theorem 6.15 by being linear – vs cubic – in
the input dimension; together with a mistake bound for Perceptron, we get
$\mathsf{LEQ}$ bounds.242424In this case, we would need a margin between the
sets $B_{\rho}(\text{supp}(D_{0}))$ and $B_{\rho}(\text{supp}(D_{1}))$, as
these are the sets of potential counterexamples – the condition
$B_{\rho}(\text{supp}(D_{0}))\cap B_{\rho}(\text{supp}(D_{1}))=\emptyset$ is
not sufficient in itself to get guarantees for hypotheses with infinite
Littlestone dimension. See (Montasser et al.,, 2021) for both upper and lower
bounds in this setting.

Instead, in this section, we look at robust learning problems in which the
decision boundary can cross the perturbation region, but where the adversary’s
precision is limited. We use ideas from Ben-David et al., (2009) concerning
hypotheses with margins in the online learning framework. Note, however, that
here the margin does not represent sufficient distance between classes, but
rather a region of the instance space that is too costly for the adversary to
access (e.g., the number of bits needed to express an adversarial example is
too large).

Examining the proof that the Littlestone dimension of thresholds is infinite
(see Section 6.4), the key assumption is that the adversary has _infinite_
precision, which is perhaps not a reasonable assumption to make in practice.
More precisely, in the construction of the Littlestone tree, each
counterexample given requires an additional bit to be described, as the
remainder of the interval $[0,1]$ is split in two at each prediction. Our work
in this section formally and more generally addresses this potential issue.

We now define the meaning of bounding an adversary’s precision in the context
of robust learning, which is depicted in Figure 9.

Figure 9: The dotted line is the hypothesis $h$, and the solid line, the
target $c$. The adversary has precision $\tau$. The shaded regions represent
the set $B_{\tau}(z_{i})$. The counterexample $z_{1}$ is valid as $c$ and $h$
disagree on all of $B_{\tau}(z_{1})$ and both functions are constant in this
region, but $z_{2}$ is not as $c$ and $h$ agree on part of $B_{\tau}(z_{2})$.

######  Definition 6.20 (Precision-Bounded Adversary).

Let $(\mathcal{X},d)$ be a metric space, and let an adversary $\mathbb{A}$
have budget $\rho$. We say that $\mathbb{A}$ is _precision-bounded_ by $\tau$,
if for target $c$, hypothesis $h$, and input $x$, $\mathbb{A}$ can only return
counterexamples $z\in B_{\rho}(x)$ such that $h$ and $c$ are both constant and
disagree on the whole region $B_{\tau}(z)$ and $B_{\tau}(z)\subseteq
B_{\rho}(x)$.

##### Comparison with online learning.

Note that if we set $\rho$ to be large enough so that the perturbation region
is the whole instance space $\mathcal{X}$ for any point $x$ (more generally,
$\mathcal{U}(x)=\mathcal{X}$), we (almost) recover the adversary model in the
online learning setting. The only distinction is that, in online learning, at
a given time $t$ the learner is a point $x_{t}$ to classify (implicitly
classifying the whole region $B_{\tau}(x_{t})$ in our precision-bounded
setting), rather than committing to a hypothesis $h$ on the whole instance
space. The adversary (or “nature” if a target must be chosen a priori) reveals
the true label after a prediction is made.

In the mistake-bound model, the only constraint is that there exists a concept
in $\mathcal{H}$ that is consistent with the labelled sequence
$(x_{1},y_{1},),\dots,(x_{t},y_{t})$ seen so far. When working with a
precision-bounded adversary, we are implicitly asking the adversary to not
give counterexamples too close to the boundary. Then, in the mistake-bound
model, this translates into the adversary giving a point $x_{t}$ to predict
such that there does not exist time steps $t^{\prime},t^{\prime\prime}$ where
$y_{t^{\prime}}\neq y_{t^{\prime\prime}}$ and $B_{\tau}(x_{t^{\prime}})$ and
$B_{\tau}(x_{t^{\prime\prime}})$ both intersect with $B_{\tau}(x_{t})$, hence
a _margin_. Margin-based complexity measures for online learning adapted from
Ben-David et al., (2009) will be used in this section.

A subtle distinction between the definitions we give below and that of Ben-
David et al., (2009) is that the latter defined margin-based Littlestone trees
and Littlestone dimension for margin-based _hypothesis classes_. They require
that the hypothesis class $\mathcal{H}$ satisfies the following: for all
$h\in\mathcal{H}$, $h$ is of the form $\mathcal{X}\rightarrow\mathbb{R}$, and
the prediction rule is

$\phi(h(x))=\frac{\text{sgn}(h(x))+1}{2}\enspace,$ (29)

where the magnitude $\left|h(x)\right|$ is the _confidence_ in the prediction.
The $\mu$-_margin-mistake_ on an example $(x,y)$ is defined as

$\left|h(x)-y\right|_{\mu}=\begin{cases}0&\text{if
}\phi(h(x))=y\wedge\left|h(x)\right|\geq\mu\\\
1&\text{otherwise}\end{cases}\enspace.$ (30)

For us, since it is the _adversary_ that is bounded in its precision, we
instead consider any hypothesis class where the concepts are boolean functions
whose domain is a metric space $(\mathcal{X},d)$. Rather than having the
condition $\left|h(x)\right|\geq\mu$ from Equation 30, we encode a margin
representing the precision $\tau$ by the requirement that hypotheses must be
constant in the $\tau$-expansion around any point in the Littlestone trees.
This difference is not only stylistic, but also concerns the semantics of the
margin. Our definition moreover implies a uniform margin on the instance
space, while the one from Ben-David et al., (2009) can fluctuate in the
instance space based on the classifier’s confidence. However, the tools and
techniques used here don’t differ much in essence from the ones in Ben-David
et al., (2009). The main novelty is the meaning of the notion of margin and
its study in the context of robust learning.

######  Definition 6.21 (Littlestone Trees of Precision $\tau$).

A Littlestone tree of precision $\tau$ for a hypothesis class $\mathcal{H}$ on
metric space $(\mathcal{X},d)$ is a complete binary tree $T$ of depth $d$
whose internal nodes are instances $x\in\mathcal{X}$. Each edge is labelled
with $-$ or $+$ and corresponds to the potential labels of the parent node $x$
and the region $B_{\tau}(x)$. Each path from the root to a leaf must be
consistent with some $h\in\mathcal{H}$, i.e. if $x_{1},\dots,x_{d}$ with
labellings $y_{1},\dots,y_{d}$ is a path in $T$, there must exist
$h\in\mathcal{H}$ such that $h|_{B_{\tau}(x_{i})}=y_{i}$ for all $i$.

While it is possible to have a hypothesis giving different labels to points in
the region $B_{\tau}(x)$ in the standard setting, in the above construction,
one must commit to labelling the whole region $B_{\tau}(x)$ either positively
or negatively.

For the remainder of the text, we will identify each leaf in a Littlestone
tree $T$ with a hypothesis $h\in\mathcal{H}$ that is consistent with the
labellings along the path from the root to this leaf. Note that the choice of
labelling $y$ of $B_{\tau}(x)$ of some $x\in T$ implies that, in contrast to
the standard Littlestone trees, any $h\in\mathcal{H}$ with $h(x)=y$ that is
_not_ constant on $B_{\tau}(x)$ cannot be consistent with any path in $T$. The
set of consistent hypotheses on $T$ thus does _not_ form a partition of
$\mathcal{H}$ in our precision-bounded setting.

We now remark that, by definition, no node in the tree has a $\tau$-expansion
that overlaps with the $\tau$-expansion of any of its ancestors.

######  Proposition 6.22.

Let $T$ be a Littlestone tree of precision $\tau$. Then for any node $x\in T$
and ancestor $x^{\prime}\in T$ of $x$, $B_{\tau}(x)\cap
B_{\tau}(x^{\prime})=\emptyset$.

###### Proof.

Take two paths from the root to two distinct leaves, $h_{0}$ and $h_{1}$,
respectively. Let the paths branch off at $x\in T$, with $h_{y}$ giving label
$y$ to the whole region $B_{\tau}(x)$. Let $x^{\prime}$ be an ancestor of $x$
in $T$, and note that $h_{0}=h_{1}=b$ on $B_{\tau}(x^{\prime})$ for some
$b\in\\{0,1\\}$. Then, since $h_{0}$ and $h_{1}$ must disagree on all of
$B_{\tau}(x)$, it follows that $B_{\tau}(x)\cap
B_{\tau}(x^{\prime})=\emptyset$. ∎

We can now define the following variant of the Littlestone dimension, which is
analogous to the margin-based Littlestone dimension of Ben-David et al.,
(2009).

######  Definition 6.23 (Precision-Bounded Littlestone Dimension).

The Littlestone dimension of precision $\tau$ of a hypothesis class
$\mathcal{H}$ on metric space $(\mathcal{X},d)$, denoted
$\mathsf{Lit}_{\tau}(\mathcal{H})$, is the depth $k$ of the largest
Littlestone tree with bounded precision $\tau$ for $\mathcal{H}$. If no such
$k$ exists then $\mathsf{Lit}(\mathcal{H})=\infty$.

Note that setting $\tau=0$, i.e., there are no constraints on the nodes, we
recover the Littlestone tree and Littlestone dimension definitions. As an
example, let us consider the class of threshold functions, which, when
$\tau=0$, have infinite Littlestone dimension.

######  Proposition 6.24.

Let $\tau>0$. The class $\mathsf{THRESHOLDS}_{B}$ of threshold functions on
$[0,B]$ induce Littlestone trees of precision $\tau$ of depth bounded by
$log\frac{B}{\tau}-1$. Thus
$\mathsf{Lit}_{\tau}(\mathsf{THRESHOLDS}_{B})=\lfloor\log\frac{B}{\tau}-1\rfloor$.

###### Proof.

Let $\tau>0$ be arbitrary. Here, the optimal strategy to construct a
Littlestone tree is to divide the interval $[0,B]$ in two equal parts at each
round. Given $x\in[0,B]$ and $\alpha<\alpha^{\prime}\in\mathbb{R}$, in order
to have two threshold functions $h_{\alpha}(x)=\mathbf{1}[x\geq\alpha]$ and
$h_{\alpha^{\prime}}(x)=\mathbf{1}[x\geq\alpha^{\prime}]$ that disagree on the
whole range $[x-\tau,x+\tau]$, we need both $\alpha<x-\tau$ and
$\alpha^{\prime}\geq x+\tau$. Thus, at depth $d$, we have divided $[0,B]$ into
$2^{d}$ parts we must have $2\tau\geq B2^{-d}$, implying
$\mathsf{Lit}_{\tau}(\mathsf{THRESHOLDS}_{B})=\lfloor\log\frac{B}{\tau}-1\rfloor$.
∎

We now show a lower bound on the number of mistakes of any learner against an
adversary with bounded precision $\tau$. The proof is identical to the regime
$\tau=0$.

######  Theorem 6.25.

Any online learning algorithm for $\mathcal{C}$ has mistake bound
$M\geq\mathsf{Lit}_{\tau}(\mathcal{C})$ against a $\tau$-precision-bounded
adversary.

###### Proof.

Let $\mathcal{A}$ be any online learning algorithm for $\mathcal{C}$. Let $T$
be a Littlestone tree of bounded precision $\tau$ and depth
$\mathsf{Lit}_{\tau}(\mathcal{C})$ for $\mathcal{C}$. Clearly, an adversary
can force $\mathcal{A}$ to make $\mathsf{Lit}_{\tau}(\mathcal{C})$ mistakes by
sequentially and adaptively choosing a path in $T$ in function of
$\mathcal{A}$’s predictions. ∎

Now, let us consider a version of the SOA where the adversary has precision
$\tau$. The algorithm is identical to the SOA (see Algorithm 5 in Chapter 3),
except for the definition of $V^{(b)}_{t}$, which requires that the hypotheses
are constant in the region around the prediction.

Algorithm 6 Precision-Bounded Standard Optimal Algorithm

A hypothesis class $\mathcal{\mathcal{H}}$

for $t=1,2,\dots$ do

$V_{1}\leftarrow\mathcal{H}$

Receive example $x_{t}$

$V^{(b)}_{t}\leftarrow\left\\{h\in V_{t}\;|\;h|_{B_{\tau}(x_{t})}=b\right\\}$

$\hat{y_{t}}=\underset{b}{\arg\max}\;\mathsf{Lit}_{\tau}\left(V^{(b)}_{t}\right)$

Receive true label $y_{t}$

$V_{t+1}\leftarrow V^{(y_{t})}_{t}$

end for

Below, we show that this slight modification of the SOA is also optimal for
cases in which the adversary is constrained by $\tau$. This is analogous to
Theorem 21 in (Ben-David et al.,, 2009), who did not include the proof of
optimality for brevity. We have included it in this thesis for completeness.

######  Theorem 6.26.

The precision-bounded Standard Optimal Algorithm makes at most
$\mathsf{Lit}_{\tau}(\mathcal{C})$ mistakes in the mistake-bound model of
online learning when the adversary has precision $\tau$.

###### Proof.

We will show that, at every mistake, the precision-bounded Littlestone
dimension of the subclass $V_{t}$ decreases by at least 1 after receiving the
true label $y_{t}$.

WLOG, assume that there does not exist $t^{\prime}<t$ such that
$x_{t^{\prime}}\in B_{\tau}(x_{t})$, as otherwise this implies that
$V_{t}^{(y_{t^{\prime}})}=V_{t}$ and $V_{t}^{(\neg
y_{t^{\prime}})}=\emptyset$, and we cannot make a mistake (note in particular
that we cannot have two differently labelled points in $B_{\tau}(x_{t})$ as
otherwise this would not be a valid example for the adversary to give).

Suppose that, at time $t$,
$y_{t}=\arg\min_{b}\mathsf{Lit}_{\tau}(V^{(b)}_{t})$. Note that
$V_{t+1}=V^{(y_{t})}_{t}$. Now, consider any two Littlestone trees $T_{y_{t}}$
and $T_{\hat{y}_{t}}$ of precision $\tau$ and maximal depths for
$V^{(y_{t})}_{t}$ and $V^{(\hat{y})}_{t}$, respectively. By Proposition 6.22
and definition of $V^{(b)}_{t}$, neither tree can contain nodes whose
$\tau$-expansions intersect with $B_{\tau}(x_{t})$. Moreover, all hypotheses
in $V^{(y_{t})}_{t}$ and $V^{(\hat{y})}_{t}$ are constant on
$B_{\tau}(x_{t})$. Hence it is possible to construct a $\tau$-constrained
Littlestone tree $T$ for $V_{t}$ of depth
$\min_{b}\mathsf{Lit}_{\tau}(V^{(b)}_{t})+1$ (recall that $T$ must be
complete). Then
$\mathsf{Lit}_{\tau}(V_{t})\geq\mathsf{Lit}_{\tau}(V^{({y_{t}})}_{t})+1=\mathsf{Lit}_{\tau}(V_{t+1})+1$,
as required.252525Note that the Littlestone dimension does not necessarily
decrease when $y_{t}=\hat{y}_{t}$, as we could have $V_{t}=V_{t}^{(y_{t})}$. ∎

######  Remark 6.27.

When considering threshold functions on $[0,1]$, and given example $x_{t}$ to
predict, the SOA’s strategy is effectively to look at the labelled points in
the history and consider the largest $x^{(0)}\in[0,1]$ with negative label and
the smallest $x^{(1)}\in[0,1]$ with positive label, and predict
$y_{t}=\underset{b}{\arg\min}\left|x_{t}-x^{(b)}\right|$.

We now turn our attention to the robust learning of halfspaces in
$(\mathbb{R}^{n},d_{2})$ against adversaries of precision $\tau$, where
$d_{2}$ is the metric induced by the $\ell_{2}$ norm. As pointed out by Ben-
David et al., (2009), we essentially have the same argument as the Perceptron
algorithm, because, once the hypothesis is sufficiently close to the target,
the adversary cannot return counterexamples near the boundary. Note that this
result can be generalized to $\ell_{p}$ norms. Figure 10 depicts the argument
of the proof of Theorem 6.28.

######  Theorem 6.28.

Fix constants $B,\tau>0$. Let the adversary’s budget $\rho$ be measured by the
$\ell_{2}$ norm. Let $\mathsf{LTF}_{\mathbb{R}^{n}}$ be the class of
halfspaces on $\mathbb{R}^{n}$ where the instance space is restricted to
points $x\in\mathbb{R}^{n}$ with $\left\|x\right\|_{2}\leq B-\rho$. Then,
$\mathsf{LTF}_{\mathbb{R}^{n}}$ is distribution-free $\rho$-robustly learnable
against an adversary of precision $\tau$ using the $\mathsf{EX}$ and
$\rho$-$\mathsf{LEQ}$ oracles with sample complexity
$m(n,\epsilon,\delta)=O(\frac{1}{\epsilon}(n^{3}+\log(1/\delta)))$ and query
complexity
$r(n,\epsilon,\delta)=m(n,\epsilon,\delta)\cdot\frac{B^{2}}{\tau^{2}}$. Note
that this is query-efficient if $\frac{B^{2}}{\tau^{2}}=\text{poly}(n)$.

Note that the dependence on $\tau$ in the mistake bound, and thus the
$\mathsf{LEQ}$ upper bound, is $1/\tau^{2}$, in contrast to the dependence of
$\log 1/\tau$ for thresholds.

Figure 10: A visual representation of the proof of Theorem 6.28. The dotted
lines on either side of the target $c$ represent a margin of $\tau/2$. Any
hypothesis within the dotted lines in the (shaded) perturbation region ensures
that an adversary of bounded precision $\tau$ cannot return any
counterexamples. Finally, counterexamples must be labelled according to the
target $c$, and both $h$ and $c$ are not constant on $B_{\rho}(x)$.

###### Proof.

The sample complexity follows from Theorem 6.15. The query upper bound follows
from Lemma 6.11 and the mistake bound for the Perceptron algorithm (see
Theorem 3.16). To see that the bound for Perceptron can be used, note that the
adversary having precision $\tau$ implies that any consistent target function
$c(x)=a^{\top}x+a_{0}$ and any counterexample $z$ will satisfy the conditions
(i) $\left\|z\right\|_{2}\leq B$ and (ii)
$\tau\leq\frac{c(z)(a^{\top}z)}{\left\|z\right\|_{2}}$ from Theorem 3.16. ∎

###  22 Lower Bounds on Robust Learning with $\mathsf{LEQ}$

In this section, we derive lower bounds on the expected number of queries of
robust learning algorithms for various concept classes. We start with general
lower bounds and conclude by looking at specific concept classes.

####  22.1 General Query Complexity Lower Bounds

We start by giving a general lower bound on the query complexity of the
$\mathsf{LEQ}$ oracle that is linear in the _restricted_ Littlestone dimension
of a concept class. This notion, which restricts the region of the instance
space where the nodes in the Littlestone tree can come from, will be defined
below, along with the restricted VC dimension.

We first define the notion of the _restricted_ VC dimension of a concept
class. We note that we can straightforwardly extend the definitions below to
an arbitrary perturbation region $\mathcal{U}:\mathcal{X}\rightarrow
2^{\mathcal{X}}$, and obtain analogous results.

######  Definition 6.29 ($\rho$-restricted VC Dimension).

The $\rho$-restricted VC dimension of a concept class $\mathcal{C}$, denoted
$\mathsf{VC}|_{\rho}(\mathcal{C})$, is the size $d$ of the largest set
$X\subseteq\mathcal{X}$ shattered by $\mathcal{C}$ such that there exists
$x^{*}\in X$ where $x\in B_{\rho}(x^{*})$ for all $x\in X$.

We now introduce the restricted Littlestone dimension.

######  Definition 6.30 ($\rho$-restricted Littlestone Dimension).

The $\rho$-restricted Littlestone dimension of a hypothesis class
$\mathcal{H}$, denoted $\mathsf{Lit}|_{\rho}(\mathcal{H})$, is the depth $d$
of the largest Littlestone tree $T$ for $\mathcal{H}$ with root node $x^{*}$
such that $x\in B_{\rho}(x^{*})$ for all the nodes $x\in T$.

######  Remark 6.31.

It follows from the upper bound on the (standard) VC dimension by the
Littlestone dimension that
$\mathsf{VC}|_{\rho}(\mathcal{C})\leq\mathsf{Lit}|_{\rho}(\mathcal{H})$, as we
can construct a restricted Littlestone tree from a witness set of the
restricted VC dimension.

We are now ready to state the main theorem of this section.

######  Theorem 6.32.

Let $\mathcal{C}$ be a concept class of $\rho$-restricted Littlestone
dimension $\mathsf{Lit}|_{\rho}(\mathcal{C})=d$. Then there exists a
distribution on $\mathcal{X}$ such that any $\rho$-robust learning algorithm
for $\mathcal{C}$ has an expected number of queries $\Omega(d)$ to the
$\rho$-$\mathsf{LEQ}$ oracle.

As a consequence of Remark 6.31, we have the following corollary.

######  Corollary 6.33.

Let $\mathcal{C}$ be a concept class of $\rho$-restricted VC dimension
$\mathsf{VC}|_{\rho}(\mathcal{C})=d$. Then there exists a distribution on
$\mathcal{X}$ such that any $\rho$-robust learning algorithm for $\mathcal{C}$
has an expected number of queries $\Omega(d)$ to the $\rho$-$\mathsf{LEQ}$
oracle.

The proof of Theorem 6.32 is similar to showing that a mistake lower bound in
online learning can be transformed in an expected mistake lower bound when we
instead require the adversary to choose a label _before_ a (potentially
randomized) prediction is made.

In order to prove Theorem 6.32, we will use Yao’s minimax principle, which
will allow us to give lower bounds for randomized algorithms while only
considering deterministic algorithms in our analysis.

We will start with some notation. Let $\text{cost}(A,z)$ represent the real-
valued cost of an algorithm $A$ on an input $z$ for problem $P$ (e.g., running
time, number of queries, etc.). For a distribution $\mathcal{D}$ on the set
$Z$ of potential inputs to $P$, the cost of $A$ on $\mathcal{D}$ is defined as
$\text{cost}(A,\mathcal{D}):=\underset{{z\sim\mathcal{D}}}{\mathbb{E}}\left[\text{
cost}(A,z)\right]$. The _distributional complexity_ of $P$ is
$\underset{\mathcal{D}}{\max}\;\underset{A\in\mathcal{A}}{\min}\text{
cost}(A,\mathcal{D})$ (the cost of the worst distribution on inputs for the
best deterministic algorithm). Now, as we can see a randomized algorithm $R$
as a distribution $\mathcal{R}$ over all the possible deterministic
algorithms, we can define the cost of a randomized algorithm as
cost$(R,x)=\text{
cost}(\mathcal{R},x)=\underset{{A\sim\mathcal{R}}}{\mathbb{E}}\left[\text{
cost}(A,x)\right]$. The _randomized complexity_ of $P$ is defined as
$\underset{\mathcal{R}}{\min}\;\underset{x}{\max}\text{ cost}(R,x)$.

Yao’s minimax principle states that the randomized complexity and
distributional complexity of a problem $P$ are equal, i.e.,

$\underset{\mathcal{R}}{\min}\;\underset{x}{\max}\text{
cost}(\mathcal{R},x)=\underset{\mathcal{D}}{\max}\;\underset{A\in\mathcal{A}}{\min}\text{
cost}(A,\mathcal{D})\enspace.$

For us, the input to the learning problem will be the target concept, and as
such the distribution $\mathcal{D}$ will be over the concept class
$\mathcal{C}$. The cost of an algorithm $A$ on $c$ is the number of queries to
the $\rho$-$\mathsf{LEQ}$ oracle, and we are interested in the expected number
of counterexamples returned.

###### Proof of Theorem 6.32.

The idea behind the proof is to choose a distribution in which all the
elements of the Littlestone tree appear in the perturbation region of its
root. We then derive query lower bounds for deterministic algorithms and a
deterministic $\mathsf{LEQ}$. We finally use Yao’s minimax principle to lower
bound the number of queries of _any_ robust learning algorithm to the
$\mathsf{LEQ}$ oracle.

_Distribution on $\mathcal{X}$._ Let $T$ be a Littlestone tree of depth $d$
with root $x^{*}\in X$ such that all its nodes are contained in
$B_{\rho}(x^{*})$. Let $D$ be a distribution on $\mathcal{X}$ be such that
$D(x^{*})=1$. Hence, any query to $\mathsf{EX}(c,D)$ will return
$(x^{*},c(x^{*}))$. Moreover, any learning algorithm must be exact on
$B_{\rho}(x^{*})$, as otherwise the existence of a point $z$ in
$B_{\rho}(x^{*})$ such that the target and hypothesis disagree results in the
robust risk being 1.

Let $\widetilde{\mathcal{C}}=\left\\{c_{1},\dots,c_{2^{d-1}}\right\\}$ be the
set of concepts appearing as leaves of the subtree $T^{\prime}$ of $T$ that
label ${x^{*}}$ positively. We will pick the target $c$ at random from
$\widetilde{\mathcal{C}}$.

_$\mathsf{LEQ}$ strategy._ Let the $\rho$-$\mathsf{LEQ}$ oracle have access to
$T$ as its internal ordering. Upon being queried with $(x^{*},h)$,
$\mathsf{LEQ}$ returns a counterexample $x^{\prime}$ of least depth. Namely, a
target $c\in\widetilde{\mathcal{C}}$ determines a path from $x^{*}$ to a leaf,
and the $\mathsf{LEQ}$ oracle returns the highest node where $h$ and $c$
disagree.

_Deterministic algorithms._ In order to use Yao’s minimax principle, we first
consider a set of deterministic algorithms. For any fixed distribution
$\mathcal{D}$ on the target concepts, a learning algorithm $A$ achieving
$\underset{A\in\mathcal{A}}{\min}\text{ cost}(A,\mathcal{D})$ must be
consistent with the data seen so far. Otherwise, $\mathsf{LEQ}$ can simply
return a counterexample that has already been returned, increasing the number
of queries to $\mathsf{LEQ}$.

Without loss of generality, we consider the setting where the Littlestone tree
$T$ the $\mathsf{LEQ}$ uses to return counterexamples is known to $A$. This
implies that if $A$ receives $(x_{i},c(x_{i}))$ as a counterexample, then
there exists a unique path from $x^{*}$ to a node containing $x_{i}$ where
parents nodes of $x_{i}$ must have been labelled correctly by the hypothesis.
Any algorithm that does not know this information (or doesn’t use it) is
dominated by an algorithm knowing this information. Then any $A$ achieving
$\underset{A\in\mathcal{A}}{\min}\text{ cost}(A,\mathcal{D})$ in this setting
must be consistent on the counterexamples and (implicitly revealed) correctly
labelled points.

_Executions paths._ Consider a given _deterministic_ algorithm $A$ that is
consistent with the data seen so far. After seeing $(x^{*},+1)$, $A$ returns a
hypothesis $h_{1}$, thus the label $h_{1}(x_{1})$ is fixed (where $x_{1}$ is
the child of $x^{*}$ with a positively labelled edge). Then, one of the edges
coming out of the node $x_{1}$ will be correct, while the other will be
incorrect. Since each concept in $\widetilde{\mathcal{C}}$ defines a path in
$T^{\prime}$ and $A$ is deterministic, for each node $x$ in $T^{\prime}$, one
of its edges is correct and the other, incorrect. Then, for each leaf $c$ in
$T^{\prime}$, the edges from $x_{1}$ to $c$ that are marked as incorrect
represent the counterexamples given to $A$ by $\mathsf{LEQ}$ if $c$ were the
target. It is then easy to see that choosing the target u.a.r. from the leaves
$\widetilde{\mathcal{C}}$ of $T’$, we have an expected number of
counterexamples that is exactly $(d-1)/2$. Thus

$\underset{\mathcal{D}}{\max}\;\underset{A\in\mathcal{A}}{\min}\text{
cost}(A,\mathcal{D})\geq\underset{A\in\mathcal{A}}{\min}\text{
cost}(A,U(\widetilde{\mathcal{C}}))\geq\frac{d-1}{2}\enspace,$

where $U(\widetilde{\mathcal{C}})$ is the uniform distribution on
$\widetilde{\mathcal{C}}$. In fact, we can see that the distribution achieving
the maximum on the LHS is the uniform distribution on
$\widetilde{\mathcal{C}}$.

_Putting it all together._ Now, any learning algorithm in this setting is
either deterministic or randomized. If the algorithm is randomized, it can be
expressed as a distribution on the set of deterministic algorithms. We can
thus apply Yao’s principle and get that there exists a distribution on
$\mathcal{X}$ such that any robust learning algorithm for $\mathcal{C}$ will
have an expected number of queries to $\mathsf{LEQ}$ that is linear in the
restricted Littlestone dimension of $\mathcal{C}$. ∎

####  22.2 Bounds on the Restricted VC and Littlestone Dimensions

In this section, we study bounds on the restricted VC and Littlestone
dimensions of monotone conjunctions, decision lists and linear classifiers.
This enables us to use Theorem 6.32 to get lower bounds on the expected number
of queries to $\mathsf{LEQ}$ for the robust learning of these classes. The VC
dimension bounds are (asymptotically) the same as the standard VC dimension
for these classes. We finish by showing this is not always the case, and
exhibiting an example where the VC dimension is _not_ a lower bound for the
expected number of queries to $\mathsf{LEQ}$, hence justifying the use of
alternative complexity measure in our setting.

We summarize our results on the restricted VC dimension in Table 3. The proofs
of the bounds appear in Appendix 9.C. As corollaries of Theorem 6.32, we get
that the restricted VC dimension lower bounds presented in Table 3 are lower
bounds on the expected number of queries to the $\mathsf{LEQ}$ oracle.

Concept Class |  $\mathsf{VC}$ dimension |  $\rho$-restricted $\mathsf{VC}$ dimension
---|---|---
Conjunctions | $n$ |  $2$ (if $\rho=1$) $n$ (if $\rho\geq 2$)
Linear Threshold Functions | $n+1$ | $n+1$
$k$-Decision Lists | $\widetilde{\Theta}(n^{k})$ |  $\widetilde{\Theta}(n^{k})$ (given $\rho\geq k$)
Table 3: Comparing the VC dimension and the $\rho$-restricted VC dimension for
given concept classes. The $\widetilde{\Theta}$ notation hides the logarithmic
factors. Unless otherwise stated, we assume $\rho\geq 1$.

Now, while linear classifiers in $\mathbb{R}^{n}$ have a (restricted) VC
dimension of $n+1$, their $\rho$-restricted Littlestone dimension is infinite.
Indeed, it suffices to consider the subclass of thresholds (for which the
proof of its Littlestone dimension being infinite can easily be adapted to the
restricted setting) giving the lemma below.

######  Corollary 6.34.

Given $\rho>0$, there exists a distribution on $\mathbb{R}^{n}$ such that any
$\rho$-robust learning algorithm for linear classifiers has an infinite
expected number of queries to $\rho$-$\mathsf{LEQ}$.

We now turn our attention to the relationship between VC dimension and its
restricted counterpart, and their use for $\mathsf{LEQ}$ lower bounds.

##### In general, is
$\mathsf{VC}|_{\rho}(\mathcal{H})=\widetilde{\Theta}(\mathsf{VC}(\mathcal{H}))$?

No: we exhibit a concept class $\mathcal{H}$ where
$\mathsf{VC}(\mathcal{H})=d$ but $\mathsf{VC}|_{\rho}(\mathcal{H})=1$. This
shows that there can be an arbitrary gap between the restricted VC dimension
and its standard counterpart. Let $X=\left\\{x_{1},\dots,x_{d}\right\\}$ be a
set of $d$ points on $\left\\{0,1\right\\}^{n}$ whose balls of radius $\rho$
don’t coincide (choose $\rho$ and $d$ as functions of $n$ such that this is
possible). Define the following concept class $\mathcal{C}=\bigcup_{S\subseteq
X}\left\\{c(x)=\mathbf{1}[x\in S]\right\\}$. Clearly,
$\mathsf{VC}(\mathcal{C})=d$, but $\mathsf{VC}|_{\rho}(\mathcal{C})=1$.

##### Are there better $\mathsf{LEQ}$ lower bounds than $\mathsf{VC}|_{\rho}$?

Yes: we can still show an expected query lower bound of $\Omega(d)$ in the
example above by constructing a uniform distribution on some set
$X^{*}=\left\\{x_{1}^{*},\dots,x_{d}^{*}\right\\}$ such that $X\cap
X^{*}=\emptyset$ and $x_{i}^{*}\in B_{\rho}(x_{i})$ for all $i$, implying that
$c(x_{i})=0$ for all $1\leq i\leq d$ and $c\in\mathcal{C}$. Thus, to get a
hypothesis with robust risk strictly smaller than $1/d$, exact learning is
required. We can show that, by choosing the target at random from
$\mathcal{C}$, the expected number of counterexamples for any algorithm is
lower bounded by a function $\Omega(d)$ with the same reasoning as the proof
of Theorem 6.32.

##### Is the VC dimension a general lower bound for $\mathsf{LEQ}$?

No: consider the problem defined above, but with the perturbation region being
the identity function for each $x\in X$. Clearly, it is not possible to
construct the distribution in the previous example. In fact, a random sample
of size $\Theta(d)$ is sufficient to guarantee generalization, without the use
of queries.

###  23 Further Comparing the Local Query Models

We finish this chapter by drawing a more nuanced picture of the local
membership and equivalence query frameworks, in how they compare with each
other (Section 23.1) and to other active learning set-ups (Section 23.2).

####  23.1 Local Membership and Equivalence Queries

We start by showing two results on the efficient robust learnability of
singletons. The first result is a negative one: singletons are not efficiently
robustly learnable in the distribution-free setting in the
$\mathsf{EX}$+$\mathsf{LMQ}$ model. However, the second result shows that it
is possible to do so in the $\mathsf{EX}$+$\mathsf{LEQ}$ model when the
perturbation budget $\rho$ and the locality radius $\lambda$ are equal. While
simple, together these results highlight the relevance of the $\mathsf{LEQ}$
oracle in robust learning. Indeed, they show that, unlike in the standard PAC
model, membership queries cannot, in general, simulate equivalence queries in
the robust learning setting.262626See Theorem 3.20 for details. In robust
learning, because of the existence of the existential quantifier in the robust
loss, $\mathbf{1}[\exists z\in B_{\rho}(x)\;.\;c(z)\neq h(z)]$, polynomially-
many (local) membership queries cannot in general suffice to estimate the
robust loss, as illustrated below. We finish by looking at parities, a concept
class for which local membership and equivalence queries are equally powerful.

We first start by showing that having access to local membership queries does
not ensure the robust learnability of singletons in the distribution-free
setting _regardless of the query radius_.

######  Proposition 6.35.

If $\rho$ is $\omega(1)$, the class of singletons is not efficiently
$\rho$-robustly learnable in the distribution-free setting when the learner
has access to a $\lambda$-$\mathsf{LMQ}$ oracle for any $\lambda$.

###### Proof.

Fix $x\in\mathcal{X}$ and consider the distribution $D$ on $\mathcal{X}$ such
that $D(x)=1$. We distinguish two cases. If $\lambda<\rho$, it suffices to
choose two singletons in $B_{\rho}(x)\setminus B_{\lambda}(x)$ and draw the
target concept uniformly at random between them (the learner cannot query a
positive label, and cannot do better than choosing the right target at
random). The second case is $\lambda\geq\rho$. Note that
$\left|B_{\rho}(x)\right|\geq(n/\rho)^{\rho}$, which is superpolynomial in $n$
for any budget $\rho=\omega(1)$ (as $\rho\leq n$). Now, for any LMQ strategy
with a polynomial query upper bound $r(n)$, there exists a sufficiently large
input dimension $N$ such that, after $r(N)$ queries, at least half the points
in $B_{\rho}(x)$ have yet to be queried. Choosing a target uniformly at random
in $B_{\rho}(x)\setminus\left\\{x\right\\}$, using Lemma 4.9, and noting that
any two singletons in $B_{\rho}(x)$ have robust risk of 1 against each other,
suffices to lower bound the expected risk of any hypothesis over the choice of
the target concept by a constant. ∎

We now show that, in contrast, having access to a local equivalence query
oracle enables the robust learnability of singletons in the distribution-free
setting.

######  Proposition 6.36.

Singletons are efficiently distribution-free $\rho$-robustly learnable given a
$\rho$-$\mathsf{LEQ}$ oracle.

###### Proof.

Draw a sufficiently large sample $S\sim D^{m}$ to ensure robust
generalization, as in Lemma 6.6 ($\left|S\right|$ is polynomial in the input
dimension $n$ and learning parameters). If there exists a positively labelled
point $x\in S$, we have learned the target singleton. Otherwise, query the
$\mathsf{LEQ}$ oracle with the constant function 0 on the points in $S$ until
we receive a counterexample (the target singleton) or until it is confirmed
that all points have robust loss of 0. In either case, we have queried at most
$m$ points and the hypothesis is robustly consistent with the training sample,
and we are done. ∎

Note that this is in contrast with the fact that, if a concept class is
exactly learnable with access to the $\mathsf{MQ}$ and $\mathsf{EQ}$ oracles,
then it is PAC learnable with random examples and access to $\mathsf{MQ}$ (see
Section 6.5 for details). Fundamentally, the existential quantifier in the
robust risk definition renders simulating the $\mathsf{LEQ}$ oracle with the
$\mathsf{LMQ}$ oracle impossible.

##### Learning parities with $\mathsf{LMQ}$ and $\mathsf{LEQ}$.

There are cases where the $\mathsf{EX}$+$\mathsf{LMQ}$ and
$\mathsf{EX}$+$\mathsf{LEQ}$ models are equally powerful. Indeed, it is easy
to see that access to the 1-$\mathsf{LMQ}$ or 1-$\mathsf{LEQ}$ oracle is
sufficient to exactly learn parities with one query to $\mathsf{EX}$. For the
former case, it suffices to flip each bit $i$ of an instance $x$ drawn from
$\mathsf{EX}$ and give $x\oplus e_{i}$ to the $\mathsf{LMQ}$ oracle to observe
whether $i$ is in the target parity. For the latter, note that each
counterexample $(x,y)$ is linearly independent from the set of data points
already collected, so there must be at most $n$ counterexamples in $B_{1}(x)$,
thus exactly identifying the target parity.

####  23.2 A Two-Way Separation between $\mathsf{LEQ}$ and $\mathsf{EQ}$

In this section, we compare local and “global” query oracles. We show that,
when considering robust learning, the $\mathsf{EX}$+$\mathsf{LEQ}$ and
$\mathsf{EX}$+$\mathsf{EQ}$ models are in general incomparable. This is in
contrast with $\mathsf{LMQ}$ and $\mathsf{MQ}$, where a learning algorithm
with access to $\mathsf{LMQ}$ can straightforwardly be simulated by an
algorithm with access to $\mathsf{MQ}$.

We first show the existence of a robust learning problem on
$\left\\{0,1\right\\}^{n}$ such that the $\mathsf{EX}$+$\mathsf{LEQ}$ model
requires one sample point from $\mathsf{EX}$ and one query to $\mathsf{LEQ}$,
while it requires $\log n$ calls to $\mathsf{EQ}$ in the
$\mathsf{EX}$+$\mathsf{EQ}$ model. We then show the existence of a robust
learning problem on $\left\\{0,1\right\\}^{n}$ such that the
$\mathsf{EX}$+$\mathsf{LEQ}$ model requires $O(1/\epsilon)$ sample points from
$\mathsf{EX}$ and a total of $1/\epsilon$ queries to $\mathsf{LEQ}$ in order
to have a robust error bounded by $\epsilon$, while it only requires a single
call to $\mathsf{EQ}$ in the $\mathsf{EX}$+$\mathsf{EQ}$ model.272727We note
that the query complexity of learning with $\mathsf{MQ}$, $\mathsf{EQ}$ and
partial queries has been vastly studied, notably by Angluin, (1988) and Maass
and Turán, (1992). In these works however, the learning algorithm is required
to be _proper_ and the learning _exact_. In contrast, we look at the robust
learning framework and allow improper learning.

We now formally state the result showing that (perhaps counter-intuitively)
1-$\mathsf{LEQ}$ can sometimes be more powerful than $\mathsf{EQ}$. The idea
is to create a learning problem such that any counterexample in a ball of
radius one around a point reveals full information about the target, but when
the oracle is free to choose any point in the input space, it can
(adversarially) reveal partial information. To simplify our analysis, we will
assume that the oracle does not have to commit to any target, as long as the
target is defined on the support of the distribution (in order to have a well-
defined example oracle). The target is not necessarily defined on the rest of
the input space, only restricting the oracle to output a sequence of
counterexamples for which there always exists a consistent concept. As
mentioned earlier in this chapter, choosing a target a priori (i.e., similarly
to the online stochastic setting) simply results in expected bounds of the
same order as if the oracle does not have to commit to a target (i.e., the
mistake-bound online setting).

######  Theorem 6.37.

Let $\mathcal{C}=\left\\{x\mapsto x_{i}\;|\;i\in[n]\right\\}$ be the class of
_monotone_ dictators. There exists a distribution $D$ on
$\left\\{0,1\right\\}^{n}$ and target concept $c\in\mathcal{C}$ such that
1-robustly learning $(c,D)$ requires at most one query to 1-$\mathsf{LEQ}$,
but, for any learning algorithm, at least $\log n$ queries to $\mathsf{EQ}$.

###### Proof.

Let $D$ be such that $D(\mathbf{0})=1$, and note that robustly learning
$\mathcal{C}$ against an adversary with budget 1 requires exact learning.
Moreover, the labelled instance $(\mathbf{0},0)$ gives no information about
the target concept.

For the $\mathsf{LEQ}$ model, the learner samples the point $\mathbf{0}$ from
$\mathsf{EX}$, and gives the constant hypothesis $0$ to $\mathsf{LEQ}$. Since
the oracle must return $x\in B_{1}(\mathbf{0})$ such that $c(x)=1$, it must
return $e_{i}$ such that $c(x)=x_{i}$.282828Note that this is an improper
learner, but we can simply consider the case
$\mathcal{C}^{\prime}=\mathcal{C}\cup\left\\{c(x)=0\right\\}$ to get an
example with proper learning.

For the $\mathsf{EQ}$ model, the idea is that, for any hypothesis $h$ the
learner gives to $\mathsf{EQ}$, the oracle can always find a counterexample
that removes at most half of the potential targets. Let
$I_{t}=\left\\{i\in[n]\;|\;x_{i}\text{ is consistent with the
history}\right\\}$ be the set of indices (and thus concepts) that are
consistent with the sequence of counterexamples given up until query $t$, and
note that $I_{1}=[n]$. Let $h\in 2^{\left\\{0,1\right\\}^{n}}$ be an arbitrary
hypothesis and define the following function

$\\#1:(x,I)\mapsto\sum_{i\in I}x_{i}$

that returns the number of 1’s at the indices of $I\subseteq[n]$ in an
instance $x\in\left\\{0,1\right\\}^{n}$. Define the following instances:

$\displaystyle x_{*}:=\underset{x:h(x)=1}{\arg\min}\;\\#1(x,I_{t})\enspace,$
$\displaystyle x^{*}:=\underset{x:h(x)=0}{\arg\max}\;\\#1(x,I_{t})\enspace.$

We now argue that one of $x_{*}$ or $x^{*}$ will decrease $I_{t}$ by at most
half. Recall that the oracle’s goal is to reveal as little information as
possible to the learner at every query. Note that, given
$x\in\left\\{0,1\right\\}^{n}$, if $h(x)\neq c(x)$, then all the bits with
value $c(x)$ are still viable target functions for that counterexample.

Now, if $x^{*}$ is a counterexample, then $c(x^{*})=1$, and there are
$\\#1(x,I_{t})$ concepts that are still consistent with the counterexample
history. Likewise, if if $x_{*}$ is a counterexample, then $c(x^{*})=0$, and
there are $\left|I_{t}\right|-\\#1(x,I_{t})$ concepts that are still
consistent with the counterexample history. Thus, if the oracle chooses the
counterexample maximizing the number of consistent concepts with the history,
we have that

$\left|I_{t+1}\right|=\max\left\\{\left|I_{t}\right|-\\#1(x_{*},I_{t}),\\#1(x^{*},I_{t})\right\\}\geq\lfloor\left|I_{t}\right|/2\rfloor\enspace,$

which concludes the proof. ∎

######  Remark 6.38.

As a corollary of Theorem 6.37, we get that there exists a robust learning
problem for which distribution-free efficient robust learning is still
possible when $\lambda>\rho$, but where the query complexity is much larger
than if $\lambda=\rho$ (set $\rho=1$ in the problem above).

Now, we formally show that, for some learning problems, an $\mathsf{EQ}$
oracle is more powerful than an $\mathsf{LEQ}$ oracle.

######  Theorem 6.39.

Let
$\mathcal{C}=\left\\{x\mapsto\mathbf{1}[x=x^{\prime}]\;|\;x^{\prime}\in\left\\{0,1\right\\}^{n}\right\\}$
be the class of singletons. Then there exists a distribution $D$ on
$\left\\{0,1\right\\}^{n}$ and target concept $c\in\mathcal{C}$ such that
robustly learning $(c,D)$ requires at most one query to $\mathsf{EQ}$, but,
for any learning algorithm, at least $1/\epsilon$ queries to
$\lambda$-$\mathsf{LEQ}$ for robust accuracy $\epsilon$.

###### Proof.

Let $k=\lfloor 1/\epsilon\rfloor$. Let $X=\left\\{x_{1},\dots,x_{k}\right\\}$
be instances in $\left\\{0,1\right\\}^{n}$ whose $\lambda$-expansions don’t
intersect (let $n$ be sufficiently large and choose $\lambda$ as a function of
$n$ and $\epsilon$ so that this is possible). Let $c(x_{i})=0$ for all
instances $x_{i}$, and let $D$ be the uniform distribution on $X$. Note that,
if the target singleton is in any of the perturbation regions
$B_{\rho}(x_{i})$, then a $\rho$-robust learning algorithm given robust
accuracy parameter $\epsilon$ must identify the target exactly. Without loss
of generality, we let $\rho=\lambda$.

For the $\mathsf{EQ}$ bound, the learner can clearly query $\mathsf{EQ}$ with
the constant function $0$, and get the singleton target as a counterexample,
without any call to $\mathsf{EX}$.

For the $\lambda$-$\mathsf{LEQ}$ bound, the oracle’s strategy is simply to
(adaptively) return that $c=0$ on all queries
$(x_{i_{1}},h_{1}),\dots,(x_{i_{k-1}},h_{k-1})$ until the last query
$x_{i_{k}}$, which reveals the target singleton. This yields a lower bound of
$k$ queries to $\lambda$-$\mathsf{LEQ}$ (the optimal strategy is to not repeat
an instance in the queries and always choose $h_{i}=0$) ∎

######  Remark 6.40.

As the mistake-bound of singletons in online learning is 1, the theorem above
also shows that $\rho$-robust learning with a $\rho$-$\mathsf{LEQ}$ can result
in query complexity lower bounds that are strictly greater than mistake bounds
in online learning. Note though that the optimal algorithm still only makes
one mistake, it simply has to query the $\mathsf{LEQ}$ a certain number of
times before making it.

###  24 Summary and Open Problems

In this chapter, we have thoroughly studied the powers and limitations of both
local membership and equivalence queries in the context of robust learning. In
particular, we have outlined when access to either oracle is necessary to
enable robustness guarantees, as well as obtained lower bounds on the local
query complexity of various robust learning problems.

####  24.1 Final Remarks on Local Query Oracles

We discuss the implementation of local query oracles, as well as how the
$\mathsf{LMQ}$ and $\mathsf{LEQ}$ oracles differ when considering the
constant-in-the-ball notion of robustness.

##### Implementing $\mathsf{LEQ}$ oracle.

In practice, one always has to find a way to approximately implement oracles
studied in theory. A possible way to generate counterexamples with respect to
the exact-in-the-ball notion of robustness is as follows. Suppose that there
is an adversary that can generate points $z\in B_{\rho}(x)$ such that
$h(z)\neq c(z)$. Provided such an adversary can be simulated, there is a way
to (imperfectly) implement the $\mathsf{LEQ}$ oracle in practice. Thus, the
use of these oracles can be viewed as a form of adversarial training.

##### Local query analogues for the constant-in-the-ball risk.

Both the $\mathsf{LMQ}$ and $\mathsf{LEQ}$ models are particularly well-suited
for the standard and exact-in-the-ball risks, as they address _information-
theoretic_ limitations of learning with random examples only. On the other
hand, while information-theoretic limitations of robust learning with respect
to the _constant-in-the-ball_ notion of robustness arise when the perturbation
function $\mathcal{U}$ is unknown to the learner, _computational_ obstacles
can also occur even when the definition of $\mathcal{U}$ is available. Indeed,
determining whether the hypothesis changes label in the perturbation region
could be intractable. In these cases, the Perfect Attack Oracle (PAO) of
Montasser et al., (2021) can be used to remedy these limitations for robust
learning with respect to the constant-in-the-ball robust risk. Crucially, in
their setting, counterexamples could have a different label to the ground
truth: a counterexample $z\in\mathcal{U}(x)$ for $x$ is such that $h(z)\neq
c(x)$, not necessarily $h(z)\neq c(z)$. A striking example of this is when
$\mathcal{U}(x)=\mathcal{X}$. In this case, we only want to know if the
hypothesis is constant on the whole input space. This could compromise the
standard accuracy of the hypothesis (see e.g., Tsipras et al., (2019) for a
learning problem where robustness and accuracy are at odds). Finally, an
$\mathsf{LMQ}$ analogue for the constant-in-the-ball risk is not needed: the
only information we need for a perturbed point $z\in B_{\rho}(x)$ is the label
of $x$ (given by the example oracle) and $h(z)$. Given that one of the
requirements of PAC learning is that the hypothesis is efficiently
evaluatable, we can easily compute $h(z)$.

##### Comparison with (Montasser et al.,, 2021).

Closest to our work in this chapter is that of Montasser et al., (2021), who
derive sample and PAO query bounds for the realizable constant-in-the-ball
setting. They use the algorithm from (Montasser et al.,, 2019) to get a sample
complexity of
$\tilde{O}\left(\frac{\mathsf{VC}(\mathcal{H}){\mathsf{VC}^{*}}^{2}(\mathcal{H})+\log(1/\delta)}{\epsilon}\right)$
and derive a query complexity of
$\tilde{O}(2^{\mathsf{VC}(\mathcal{H})^{2}\mathsf{VC}^{*}(\mathcal{H})^{2}\log^{2}(\mathsf{VC}^{*}(\mathcal{H}))}\mathsf{Lit}(\mathcal{H}))$,
where $\mathsf{VC}^{*}(\mathcal{H})$ is the dual VC dimension of a hypothesis
class. They also derive query lower bounds: their general PAO query complexity
lower bound is $\Omega(\log(\text{Tdim}(\mathcal{H})))$, where
$\text{Tdim}(\mathcal{H})$ is the _threshold dimension_ of a hypothesis class.
The threshold dimension is bounded below by the logarithm of the Littlestone
dimension, hence giving a general query lower bound of
$\Omega(\log\log(\mathsf{Lit}(\mathcal{H})))$. Since threshold functions have
a threshold dimension exponential in the Littlestone dimension, Montasser et
al., (2021) get a PAO query lower bound of $\Omega(\mathsf{Lit}(\mathcal{H}))$
in that special cases. In contrast, we get an $\mathsf{LEQ}$ query lower bound
linear in the restricted Littlestone dimension (which coincides with the
Littlestone dimension for a wide variety of common concept classes) for any
concept class.

####  24.2 Future Work

We finally outline various avenues for future research.

##### Local membership query lower bounds.

The $\mathsf{LMQ}$ lower bound from Section 19 was derived for conjunctions.
The technique does not work for monotone conjunctions, as, for a given set of
indices $I$, there exists only one monotone conjunction using all indices in
$I$. Can we get a similar $\mathsf{LMQ}$ lower bound where the dependence on
$\rho$ is exponential for monotone conjunctions, or it is possible to robustly
learn them with $o(2^{\rho})$ local membership queries?

##### Limiting the power of the adversary.

In Section 21, we studied robust learning against a bounded-precision
adversary, requiring that it return a point around which the hypothesis and
target disagree _everywhere_. We could relax this requirement and instead let
the adversary choose a distribution $D_{x}$ on the perturbation region
$\mathcal{U}(x)$, with constraints on $D_{x}$ that prevent a Dirac delta
distribution on a single adversarial example $z\in\mathcal{U}(x)$. A promising
avenue is to consider the smoothed adversaries of the work of Haghtalab et
al., 2022a ; Haghtalab et al., 2022b  in online learning, which have density
functions bounded by $1/\sigma$ that of the uniform density. Note that a
probabilistic approach of robustness has been considered in (Viallard et al.,,
2021; Robey et al.,, 2022) with respect to the constant-in-the-ball notion of
robustness.

##### Sample and query complexity bounds with $\mathsf{LEQ}$.

In Section 20.2, we derived sample complexity upper bounds as a function of
the VC dimension of the robust loss. As noted in Remark 6.9, this quantity is
1 when the adversarial budget $\rho=n$ (in $\left\\{0,1\right\\}^{n}$) due to
the fact that we are essentially working in the online setting and the
underlying distribution has become irrelevant. However, our upper bound for
linear classifiers is $O(n^{3})$, implying that it is quite loose, especially
as $\rho$ increases. Understanding the behaviour of the VC dimension of the
robust loss as a function of $\rho$ to get concrete sample complexity bounds
is a natural avenue for future work. In Appendix 10.A, we take a closer look
at this question and show that, in the particular case of $\rho=n-1$, the VC
dimension of the robust loss between linear classifiers is exactly 2.

Another natural direction for future work is to obtain sample complexity
_lower_ bounds. We first note in Appendix 10.B that it is unlikely that the VC
dimension of the robust loss is a good candidate for this complexity measure.
Indeed, we explain why the proof that the VC dimension is a lower bound in the
standard setting does not carry through when considering the robust loss. We
are currently investigating whether the complexity measure based on the one-
inclusion graph developed by Montasser et al., (2022) for the constant-in-the-
ball notion of robustness can be adapted to the exact-in-the-ball setting and
thus get a _characterization_ of robust learnability.

Finally, it would be interesting to give a more fine-grained picture of the
sample and query complexity tradeoff outlined in Remark 6.9, perhaps through
joint sample and query complexity lower bounds.

##  Chapter 7 Conclusion

This thesis studied the robustness of learning algorithms to evasion attacks
from a learning theory perspective. Our focus was on the _existence_ of
misclassified perturbed instances, with respect to the exact-in-the-ball
notion of robust risk. Our main consideration was the sample and query
complexity of learning problems, with a particular focus on _efficiency_ , in
an information-theoretic sense. We identified assumptions on learning problems
that either enable or prevent robustness guarantees. In particular, we looked
at how the distribution that generates the data as well as the way in which
the data is acquired influence the amount of data needed to ensure robustness
to evasion attacks.

We started with a more passive setting in which the learner was restrained to
a randomly drawn sample labelled according to the target concept, which
required distributional assumptions to get reasonable sample complexity
bounds. We outlined a series of combinatorial arguments to show that the
$\log(n)$-expansion of error regions for certain concept classes on the
boolean hypercube is not too large compared to the original set representing
the error region.

In order to obtain distribution-free guarantees, we progressively considered
more active and powerful learners which have access to _local_ queries –
showing in the process that local membership queries were, in general, not
going to improve our previously obtained robustness thresholds. We have
furthermore delimited the frontier of distribution-free robust learning for a
wide variety of concept classes. This happens to be when the learner’s query
region and the adversary’s perturbation region exactly coincide. We provided a
nuanced discussion of these results and complemented them with lower bounds to
the local equivalence query oracle.

To conclude, one of the overarching themes of this thesis is the
identification of fundamental _trade-offs_ between the robustness of a
learning algorithm and its training sample size. As outlined below, the notion
of tradeoff also informs future research directions and presents itself as a
compelling framework to study guarantees or lack thereof in learning problems
with non-standard objectives.

###  25 Future Work

As hinted throughout this thesis, we are far from having a full picture of
robust learnability with respect to the exact-in-the-ball notion of
robustness. Indeed, concrete open problems abound, including the following
questions posed in previous chapters. What is the robustness threshold of
linear classifiers (and, more generally, concept classes of polynomially-
bounded VC dimension) under log-Lipschitz distributions? Can we derive tighter
sample complexity bounds with access to random examples only? Is there a
complexity measure characterizing the robust learnability of robust ERM
algorithms under the exact-in-the-ball notion of robustness?

Broader research questions have also arisen following the work presented in
this thesis. Below we outline more general and perhaps more speculative
avenues for future work.

##### Agnostic setting.

In standard PAC learning, the agnostic setting allows for a joint distribution
on the instance and label spaces. The aim is to output a hypothesis whose
error is as close as possible to the optimal hypothesis in the class. Observe
that the constant-in-the-ball notion of robustness naturally extends to the
agnostic setting: the label of a perturbed instance is compared to the label
of its unperturbed counterpart. In fact, Montasser et al., (2019) exhibit an
elegant reduction from the agnostic to the realizable setting for the
constant-in-the-ball notion of robustness. Hopkins et al., (2022) even show a
quite general reduction for a family of general loss functions, which
generalizes the one from (Montasser et al.,, 2019), at the cost of a
$1/\epsilon$ factor in the sample complexity. However, given the presence of a
target concept in the exact-in-the-ball case, it is not obvious how to extend
this definition to the agnostic setting. The robustness definition of Pang et
al., (2022), mentioned in the literature review, could be a candidate for
this. In any case, developing a theory of agnostic robust learnability in our
setting, and determining whether the methods of Hopkins et al., (2022) apply,
is an exciting future research direction.

##### Probabilistic Lipschitzness.

In this thesis, when looking at robust learning with random examples only, we
have considered learning problems as arbitrary concept and distribution pairs
$(c,D)$ that come from a fixed concept class and distribution family. However,
it would be natural to consider learning problems in which there is a
relationship between the target and the distribution on the data. The
probabilistic Lipschitzness property, proposed by Urner and Ben-David, (2013),
offers an interesting possible research direction: while a Lipschitzness
condition on a deterministic target function imposes a margin between classes,
its probabilistic counterpart allows the margins to “smoothen out” near the
boundary. Allowing for target functions that satisfy Probabilistic Lipschitz
(perhaps in addition to log-Lipschitzness) has the potential to result in
better sample complexity bounds while still ensuring sufficient probability
mass near the boundary in order to justify the use of the exact-in-the-ball
notion of robustness.

##### Poisoning and evasion attacks.

We have so far focused on the study of evasion attacks. As pointed out in the
literature review, there has also been a considerable body of work focusing on
various poisoning attack models. Whether it is possible to draw connexions
between the two settings (e.g., is a learning algorithm that is robust to
evasion attacks also robust to poisoning attacks, and vice-versa, and, if so,
under which conditions?) is an interesting research direction that could
bridge different views of robustness, especially considering the _clean-label
attack model_ , where new training data modified by the adversary must still
be consistent with the target concept.

##### Multi-objective trustworthy machine learning.

One can expand the requirements of a learning algorithm for classification
beyond its predictive accuracy, and in ways other than robustness, in the
general goal of _trustworthiness_. For example, in interpretability and
explainable machine learning, we have an additional need for a model to be
able to explain _why_ a certain label has been chosen for a new unseen
example, or more generally how a model uses a specific subset of features in
its predictions, usually by attributing importance to certain features of the
data. Another important consideration is the fairness of learning algorithms.
While there exist many different notions of fairness (Kleinberg et al.,,
2017), the overarching goal is usually to avoid discrimination against a
particular subgroup of the data. Finally, there are a variety of ways in which
privacy can be specified. For example, one may wish to be resilient against
membership inference attacks, where the aim is to infer whether an individual
was part of the training set. It is apparent that such formal guarantees are
warranted for any safe learning algorithm that is deployed in practice.
Drawing connections between how these requirements relate to robustness is one
of many possible research avenues in trustworthy machine learning. Indeed, it
is possible that these requirements be at odds with each other, naturally
resulting in multi-objective formulations, or, conversely, that they can in
fact align with each other. While there exists work on this topic in the
literature, see, e.g., (Lecuyer et al.,, 2019; Pawelczyk et al.,, 2022;
Konstantinov,, 2022), knowledge gaps remain, especially considering the myriad
of ways in which robustness, fairness, interpretability and privacy have been
defined.

To conclude, while we have focused on the trade-off between robustness and
sample complexity in this work, the nature of trade-offs in learning problems
can vary: between sample complexity and other learning objectives, between a
learning objective and computational complexity, between learning objectives
themselves, etc. Exploring trade-offs through the lens of learning theory
could refine our understanding of fundamental limitations as well as
possibilities of learning with safer and more realistic objectives.

## References

  * Aden-Ali et al., (2023) Aden-Ali, I., Cherapanamjeri, Y., Shetty, A., and Zhivotovskiy, N. (2023).  The one-inclusion graph algorithm is not always optimal.
  * Angluin, (1987) Angluin, D. (1987).  Learning regular sets from queries and counterexamples.  Information and computation, 75(2):87–106.
  * Angluin, (1988) Angluin, D. (1988).  Queries and concept learning.  Machine learning, 2(4):319–342.
  * Angluin, (1990) Angluin, D. (1990).  Negative results for equivalence queries.  Machine Learning, 5(2):121–150.
  * Angluin and Kharitonov, (1995) Angluin, D. and Kharitonov, M. (1995).  When won’t membership queries help?  Journal of Computer and System Sciences, 50(2):336–355.
  * Ashtiani et al., (2020) Ashtiani, H., Pathak, V., and Urner, R. (2020).  Black-box certification and learning under adversarial perturbations.  In International Conference on Machine Learning, pages 388–398. PMLR.
  * Ashtiani et al., (2023) Ashtiani, H., Pathak, V., and Urner, R. (2023).  Adversarially robust learning with tolerance.  In International Conference on Algorithmic Learning Theory, pages 115–135. PMLR.
  * Attias et al., (2022) Attias, I., Hanneke, S., and Mansour, Y. (2022).  A characterization of semi-supervised adversarially-robust pac learnability.  arXiv preprint arXiv:2202.05420.
  * Attias et al., (2019) Attias, I., Kontorovich, A., and Mansour, Y. (2019).  Improved generalization bounds for robust learning.  In Algorithmic Learning Theory, pages 162–183. PMLR.
  * Awasthi et al., (2019) Awasthi, P., Dutta, A., and Vijayaraghavan, A. (2019).  On robustness to adversarial examples and polynomial optimization.  Advances in Neural Information Processing Systems, 32.
  * Awasthi et al., (2013) Awasthi, P., Feldman, V., and Kanade, V. (2013).  Learning using local membership queries.  In Conference on Learning Theory, pages 398–431. PMLR.
  * Awasthi et al., (2020) Awasthi, P., Frank, N., and Mohri, M. (2020).  Adversarial learning guarantees for linear hypotheses and neural networks.  In International Conference on Machine Learning, pages 431–441. PMLR.
  * Barreno et al., (2006) Barreno, M., Nelson, B., Sears, R., Joseph, A. D., and Tygar, J. D. (2006).  Can machine learning be secure?  In Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pages 16–25.
  * Bary-Weisberg et al., (2020) Bary-Weisberg, G., Daniely, A., and Shalev-Shwartz, S. (2020).  Distribution free learning with local queries.  In Algorithmic Learning Theory, pages 133–147. PMLR.
  * Baum and Lang, (1992) Baum, E. B. and Lang, K. (1992).  Query learning can work poorly when a human oracle is used.  In International joint conference on neural networks, volume 8, page 8. Beijing China.
  * Ben-David et al., (2009) Ben-David, S., Pál, D., and Shalev-Shwartz, S. (2009).  Agnostic online learning.  In Conference on Learning Theory, volume 3, page 1.
  * Bhagoji et al., (2019) Bhagoji, A. N., Cullina, D., and Mittal, P. (2019).  Lower bounds on adversarial robustness from optimal transport.  Advances in Neural Information Processing Systems, 32.
  * Bhattacharjee et al., (2023) Bhattacharjee, R., Hopkins, M., Kumar, A., Yu, H., and Chaudhuri, K. (2023).  Robust empirical risk minimization with tolerance.  In International Conference on Algorithmic Learning Theory, pages 182–203. PMLR.
  * Biggio et al., (2013) Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šrndić, N., Laskov, P., Giacinto, G., and Roli, F. (2013).  Evasion attacks against machine learning at test time.  In Joint European conference on machine learning and knowledge discovery in databases, pages 387–402. Springer.
  * Biggio et al., (2012) Biggio, B., Nelson, B., and Laskov, P. (2012).  Poisoning attacks against support vector machines.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1467–1474.
  * Biggio and Roli, (2018) Biggio, B. and Roli, F. (2018).  Wild patterns: Ten years after the rise of adversarial machine learning.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 2154–2156.
  * Block, (1962) Block, H.-D. (1962).  The perceptron: A model for brain functioning. i.  Reviews of Modern Physics, 34(1):123.
  * Blum et al., (2021) Blum, A., Hanneke, S., Qian, J., and Shao, H. (2021).  Robust learning under clean-label attack.  In Conference on Learning Theory, pages 591–634. PMLR.
  * Blumer et al., (1987) Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. (1987).  Occam’s razor.  Information processing letters, 24(6):377–380.
  * Blumer et al., (1989) Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. (1989).  Learnability and the vapnik-chervonenkis dimension.  Journal of the ACM (JACM), 36(4):929–965.
  * Bshouty, (1993) Bshouty, N. H. (1993).  Exact learning via the monotone theory.  In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 302–311. IEEE.
  * Bubeck et al., (2018) Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. (2018).  Adversarial examples from cryptographic pseudo-random generators.  arXiv preprint arXiv:1811.06418.
  * Bubeck et al., (2019) Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. (2019).  Adversarial examples from computational constraints.  In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 831–840, Long Beach, California, USA. PMLR.
  * Camacho and McIlraith, (2019) Camacho, A. and McIlraith, S. A. (2019).  Learning interpretable models expressed in linear temporal logic.  In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, pages 621–630.
  * Cesa-Bianchi and Lugosi, (2006) Cesa-Bianchi, N. and Lugosi, G. (2006).  Prediction, learning, and games.  Cambridge university press.
  * Chernoff, (1952) Chernoff, H. (1952).  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, pages 493–507.
  * Chowdhury and Urner, (2022) Chowdhury, S. and Urner, R. (2022).  Robustness should not be at odds with accuracy.  In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Cullina et al., (2018) Cullina, D., Bhagoji, A. N., and Mittal, P. (2018).  PAC-learning in the presence of evasion adversaries.  Advances in Neural Information Processing Systems.
  * Dalvi et al., (2004) Dalvi, N., Domingos, P., Sanghai, S., and Verma, D. (2004).  Adversarial classification.  In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 99–108. ACM.
  * Degwekar et al., (2019) Degwekar, A., Nakkiran, P., and Vaikuntanathan, V. (2019).  Computational limitations in robust classification and win-win results.  In Conference on Learning Theory, pages 994–1028. PMLR.
  * Diakonikolas et al., (2019) Diakonikolas, I., Kane, D., and Manurangsi, P. (2019).  Nearly tight bounds for robust proper learning of halfspaces with a margin.  Advances in Neural Information Processing Systems, 32.
  * Diakonikolas et al., (2020) Diakonikolas, I., Kane, D. M., and Manurangsi, P. (2020).  The complexity of adversarially robust proper learning of halfspaces with agnostic noise.  Advances in Neural Information Processing Systems, 33:20449–20461.
  * Diochnos et al., (2018) Diochnos, D., Mahloujifar, S., and Mahmoody, M. (2018).  Adversarial risk and robustness: General definitions and implications for the uniform distribution.  In Advances in Neural Information Processing Systems.
  * Diochnos et al., (2020) Diochnos, D. I., Mahloujifar, S., and Mahmoody, M. (2020).  Lower bounds for adversarially robust PAC learning under evasion and hybrid attacks.  In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 717–722.
  * Dobriban et al., (2020) Dobriban, E., Hassani, H., Hong, D., and Robey, A. (2020).  Provable tradeoffs in adversarially robust classification.  arXiv preprint arXiv:2006.05161.
  * Doshi-Velez and Kim, (2017) Doshi-Velez, F. and Kim, B. (2017).  Towards a rigorous science of interpretable machine learning.  arXiv preprint arXiv:1702.08608.
  * Dreossi et al., (2019) Dreossi, T., Ghosh, S., Sangiovanni-Vincentelli, A., and Seshia, S. A. (2019).  A formalization of robustness for deep neural networks.  arXiv preprint arXiv:1903.10033.
  * Dwork, (2008) Dwork, C. (2008).  Differential privacy: A survey of results.  In International conference on theory and applications of models of computation, pages 1–19. Springer.
  * Ehrenfeucht et al., (1989) Ehrenfeucht, A., Haussler, D., Kearns, M., and Valiant, L. (1989).  A general lower bound on the number of examples needed for learning.  Information and Computation, 82(3):247–261.
  * Etesami et al., (2020) Etesami, O., Mahloujifar, S., and Mahmoody, M. (2020).  Computational concentration of measure: Optimal bounds, reductions, and more.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 345–363. SIAM.
  * Fang et al., (2022) Fang, Z., Li, Y., Lu, J., Dong, J., Han, B., and Liu, F. (2022).  Is out-of-distribution detection learnable?  In Advances in Neural Information Processing Systems.
  * (47) Fawzi, A., Fawzi, H., and Fawzi, O. (2018a).  Adversarial vulnerability for any classifier.  Advances in neural information processing systems, 31.
  * (48) Fawzi, A., Fawzi, O., and Frossard, P. (2018b).  Analysis of classifiers? robustness to adversarial perturbations.  Machine Learning, 107(3):481–508.
  * Fawzi et al., (2016) Fawzi, A., Moosavi-Dezfooli, S.-M., and Frossard, P. (2016).  Robustness of classifiers: from adversarial to random noise.  In Advances in Neural Information Processing Systems, pages 1632–1640.
  * Feige et al., (2015) Feige, U., Mansour, Y., and Schapire, R. (2015).  Learning and inference in the presence of corrupted inputs.  In Conference on Learning Theory, pages 637–657.
  * Feldman and Schulman, (2012) Feldman, D. and Schulman, L. J. (2012).  Data reduction for weighted and outlier-resistant clustering.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1343–1354. Society for Industrial and Applied Mathematics.
  * Füredi, (1988) Füredi, Z. (1988).  Matchings and covers in hypergraphs.  Graphs and Combinatorics, 4(1):115–206.
  * Garg et al., (2020) Garg, S., Jha, S., Mahloujifar, S., and Mohammad, M. (2020).  Adversarially robust learning could leverage computational hardness.  In Algorithmic Learning Theory, pages 364–385. PMLR.
  * Gilmer et al., (2018) Gilmer, J., Metz, L., Faghri, F., Schoenholz, S. S., Raghu, M., Wattenberg, M., and Goodfellow, I. (2018).  Adversarial spheres.  arXiv preprint arXiv:1801.02774.
  * Goldberg, (2006) Goldberg, P. W. (2006).  Some discriminant-based pac algorithms.  Journal of Machine Learning Research, 7(Feb):283–306.
  * Goldberg and Jerrum, (1995) Goldberg, P. W. and Jerrum, M. R. (1995).  Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers.  Machine Learning, 18(2-3):131–148.
  * Goldblum et al., (2022) Goldblum, M., Tsipras, D., Xie, C., Chen, X., Schwarzschild, A., Song, D., Madry, A., Li, B., and Goldstein, T. (2022).  Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2):1563–1580.
  * Goodfellow et al., (2015) Goodfellow, I. J., Shlens, J., and Szegedy, C. (2015).  Explaining and harnessing adversarial examples.  In Bengio, Y. and LeCun, Y., editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
  * Gourdeau et al., (2019) Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2019).  On the hardness of robust classification.  In Advances in Neural Information Processing Systems, pages 7444–7453.
  * Gourdeau et al., (2021) Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2021).  On the hardness of robust classification.  Journal of Machine Learning Research, 22.
  * (61) Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2022a).  Sample complexity bounds for robustly learning decision lists against evasion attacks.  In International Joint Conference in Artificial Intelligence.
  * (62) Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2022b).  When are local queries useful?  In Advances in Neural Information Processing Systems.
  * (63) Haghtalab, N., Han, Y., Shetty, A., and Yang, K. (2022a).  Oracle-efficient online learning for beyond worst-case adversaries.  arXiv preprint arXiv:2202.08549.
  * (64) Haghtalab, N., Roughgarden, T., and Shetty, A. (2022b).  Smoothed analysis with adaptive adversaries.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 942–953. IEEE.
  * Hanneke, (2016) Hanneke, S. (2016).  The optimal sample complexity of pac learning.  The Journal of Machine Learning Research, 17(1):1319–1333.
  * Haussler, (1992) Haussler, D. (1992).  Decision theoretic generalizations of the pac model for neural net and other learning applications.  Information and computation, 100(1):78–150.
  * Haussler et al., (1994) Haussler, D., Littlestone, N., and Warmuth, M. K. (1994).  Predicting $\\{$0, 1$\\}$-functions on randomly drawn points.  Information and Computation, 115(2):248–292.
  * Helmbold et al., (1992) Helmbold, D., Sloan, R., and Warmuth, M. K. (1992).  Learning integer lattices.  SIAM Journal on Computing, 21(2):240–266.
  * Hoeffding, (1963) Hoeffding, W. (1963).  Probability inequalities for sums of bounded random variables.  Journal of the American statistical association, 58(301):13–30.
  * Hopkins et al., (2022) Hopkins, M., Kane, D. M., Lovett, S., and Mahajan, G. (2022).  Realizable learning is all you need.  In Conference on Learning Theory, pages 3015–3069. PMLR.
  * Jackson, (1997) Jackson, J. C. (1997).  An efficient membership-query algorithm for learning DNF with respect to the uniform distribution.  Journal of Computer and System Sciences, 55(3):414–440.
  * Kearns and Li, (1988) Kearns, M. and Li, M. (1988).  Learning in the presence of malicious errors.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 267–280.
  * Kearns et al., (1994) Kearns, M. J., Schapire, R. E., and Sellie, L. M. (1994).  Toward efficient agnostic learning.  Machine Learning, 17:115–141.
  * Khim et al., (2019) Khim, J., Jog, V., and Loh, P.-L. (2019).  Adversarial influence maximization.  In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1–5. IEEE.
  * Kleinberg et al., (2017) Kleinberg, J., Mullainathan, S., and Raghavan, M. (2017).  Inherent trade-offs in the fair determination of risk scores.  In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * Koltun and Papadimitriou, (2007) Koltun, V. and Papadimitriou, C. H. (2007).  Approximately dominating representatives.  Theoretical Computer Science, 371(3):148–154.
  * Konstantinov, (2022) Konstantinov, N. H. (2022).  Robustness and fairness in machine learning.  PhD thesis.
  * Krizhevsky and Hinton, (2009) Krizhevsky, A. and Hinton, G. (2009).  Learning multiple layers of features from tiny images.  Technical report, Citeseer.
  * LeCun, (1998) LeCun, Y. (1998).  The mnist database of handwritten digits.  http://yann. lecun. com/exdb/mnist/.
  * Lecuyer et al., (2019) Lecuyer, M., Atlidakis, V., Geambasu, R., Hsu, D., and Jana, S. (2019).  Certified robustness to adversarial examples with differential privacy.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 656–672. IEEE.
  * Linial et al., (1993) Linial, N., Mansour, Y., and Nisan, N. (1993).  Constant depth circuits, fourier transform, and learnability.  Journal of the ACM (JACM), 40(3):607–620.
  * Littlestone, (1988) Littlestone, N. (1988).  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  Machine learning, 2(4):285–318.
  * (83) Lowd, D. and Meek, C. (2005a).  Adversarial learning.  In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 641–647. ACM.
  * (84) Lowd, D. and Meek, C. (2005b).  Good word attacks on statistical spam filters.  In Fifth Conference on Email and Anti-Spam (CEAS), volume 2005.
  * Maass, (1991) Maass, W. (1991).  On-line learning with an oblivious environment and the power of randomization.
  * Maass and Turán, (1992) Maass, W. and Turán, G. (1992).  Lower bound methods and separation results for on-line learning models.  Machine Learning, 9:107–145.
  * Madry et al., (2018) Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2018).  Towards deep learning models resistant to adversarial attacks.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net.
  * Mahloujifar et al., (2018) Mahloujifar, S., Diochnos, D. I., and Mahmoody, M. (2018).  Learning under $p$-tampering attacks.  In Algorithmic Learning Theory, pages 572–596. PMLR.
  * Mahloujifar et al., (2019) Mahloujifar, S., Diochnos, D. I., and Mahmoody, M. (2019).  The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure.  AAAI Conference on Artificial Intelligence.
  * Mahloujifar and Mahmoody, (2017) Mahloujifar, S. and Mahmoody, M. (2017).  Blockwise p-tampering attacks on cryptographic primitives, extractors, and learners.  In Theory of Cryptography: 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part II 15, pages 245–279. Springer.
  * Mahloujifar and Mahmoody, (2019) Mahloujifar, S. and Mahmoody, M. (2019).  Can adversarially robust learning leveragecomputational hardness?  In Algorithmic Learning Theory, pages 581–609. PMLR.
  * Mohri et al., (2012) Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2012).  Foundations of machine learning.  MIT press.
  * Montasser et al., (2019) Montasser, O., Hanneke, S., and Srebro, N. (2019).  VC classes are adversarially robustly learnable, but only improperly.  In Conference on Learning Theory, pages 2512–2530. PMLR.
  * Montasser et al., (2020) Montasser, O., Hanneke, S., and Srebro, N. (2020).  Reducing adversarially robust learning to non-robust pac learning.  Advances in Neural Information Processing Systems, 33:14626–14637.
  * Montasser et al., (2021) Montasser, O., Hanneke, S., and Srebro, N. (2021).  Adversarially robust learning with unknown perturbation sets.  In Conference on Learning Theory, pages 3452–3482. PMLR.
  * Montasser et al., (2022) Montasser, O., Hanneke, S., and Srebro, N. (2022).  Adversarially robust learning: A generic minimax optimal learner and characterization.  Neural Information Processing Systems.
  * Natschläger and Schmitt, (1996) Natschläger, T. and Schmitt, M. (1996).  Exact vc-dimension of boolean monomials.  Information Processing Letters, 59(1):19–20.
  * Novikoff, (1963) Novikoff, A. B. (1963).  On convergence proofs for perceptrons.  Technical report, STANFORD RESEARCH INST MENLO PARK CA.
  * O’Donnell, (2014) O’Donnell, R. (2014).  Analysis of boolean functions.  Cambridge University Press.
  * O’Donnell and Servedio, (2007) O’Donnell, R. and Servedio, R. A. (2007).  Learning monotone decision trees in polynomial time.  SIAM Journal on Computing, 37(3):827–844.
  * Okudono et al., (2020) Okudono, T., Waga, M., Sekiyama, T., and Hasuo, I. (2020).  Weighted automata extraction from recurrent neural networks via regression on state spaces.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5306–5314.
  * Pang et al., (2022) Pang, T., Lin, M., Yang, X., Zhu, J., and Yan, S. (2022).  Robustness and accuracy could be reconcilable by (proper) definition.  In International Conference on Machine Learning, pages 17258–17277. PMLR.
  * Papernot et al., (2016) Papernot, N., McDaniel, P., Sinha, A., and Wellman, M. (2016).  Towards the science of security and privacy in machine learning.  arXiv preprint arXiv:1611.03814.
  * Pawelczyk et al., (2022) Pawelczyk, M., Agarwal, C., Joshi, S., Upadhyay, S., and Lakkaraju, H. (2022).  Exploring counterfactual explanations through the lens of adversarial examples: A theoretical and empirical analysis.  In International Conference on Artificial Intelligence and Statistics, pages 4574–4594. PMLR.
  * Pydi and Jog, (2021) Pydi, M. S. and Jog, V. (2021).  The many faces of adversarial risk.  Advances in Neural Information Processing Systems, 34.
  * Quinonero-Candela et al., (2008) Quinonero-Candela, J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. D. (2008).  Dataset shift in machine learning.  Mit Press.
  * Renegar, (1992) Renegar, J. (1992).  On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals.  Journal of symbolic computation, 13(3):255–299.
  * Rivest, (1987) Rivest, R. L. (1987).  Learning decision lists.  Machine learning, 2(3):229–246.
  * Robbins, (1955) Robbins, H. (1955).  A remark on stirling’s formula.  The American mathematical monthly, 62(1):26–29.
  * Robey et al., (2022) Robey, A., Chamon, L., Pappas, G. J., and Hassani, H. (2022).  Probabilistically robust learning: Balancing average and worst-case performance.  In International Conference on Machine Learning, pages 18667–18686. PMLR.
  * Rosenblatt, (1958) Rosenblatt, F. (1958).  The perceptron: a probabilistic model for information storage and organization in the brain.  Psychological review, 65(6):386.
  * Shafahi et al., (2018) Shafahi, A., Huang, W. R., Najibi, M., Suciu, O., Studer, C., Dumitras, T., and Goldstein, T. (2018).  Poison frogs! targeted clean-label poisoning attacks on neural networks.  Advances in neural information processing systems, 31.
  * Shafahi et al., (2019) Shafahi, A., Huang, W. R., Studer, C., Feizi, S., and Goldstein, T. (2019).  Are adversarial examples inevitable?  In 7th International Conference on Learning Representations (ICLR 2019).
  * Shalev-Shwartz and Ben-David, (2014) Shalev-Shwartz, S. and Ben-David, S. (2014).  Understanding machine learning: From theory to algorithms.  Cambridge university press.
  * Shao et al., (2022) Shao, H., Montasser, O., and Blum, A. (2022).  A theory of pac learnability under transformation invariances.  Advances in Neural Information Processing Systems, 35:13989–14001.
  * Shih et al., (2019) Shih, A., Darwiche, A., and Choi, A. (2019).  Verifying binarized neural networks by angluin-style learning.  In International Conference on Theory and Applications of Satisfiability Testing, pages 354–370. Springer.
  * Simon, (2015) Simon, H. U. (2015).  An almost optimal pac algorithm.  In Conference on Learning Theory, pages 1552–1563. PMLR.
  * Steinhardt et al., (2017) Steinhardt, J., Koh, P. W. W., and Liang, P. S. (2017).  Certified defenses for data poisoning attacks.  Advances in neural information processing systems, 30.
  * Suggala et al., (2019) Suggala, A. S., Prasad, A., Nagarajan, V., and Ravikumar, P. (2019).  Revisiting adversarial risk.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2331–2339. PMLR.
  * Szegedy et al., (2013) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2013).  Intriguing properties of neural networks.  In International Conference on Learning Representations.
  * Tsipras et al., (2019) Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. (2019).  Robustness may be at odds with accuracy.  In International Conference on Learning Representations.
  * Urner and Ben-David, (2013) Urner, R. and Ben-David, S. (2013).  Probabilistic lipschitzness a niceness assumption for deterministic labels.  In Learning Faster from Easy Data-Workshop@ NIPS, volume 2, page 1.
  * Valiant, (1984) Valiant, L. G. (1984).  A theory of the learnable.  In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 436–445. ACM.
  * Vapnik, (1982) Vapnik, V. (1982).  Estimation of dependences based on empirical data: Springer series in statistics (springer series in statistics).
  * Vapnik and Chervonenkis, (1971) Vapnik, V. and Chervonenkis, A. (1971).  On the uniform convergence of relative frequencies of events to their probabilities.  In Theory of Probability and Its Applications.
  * Viallard et al., (2021) Viallard, P., VIDOT, E. G., Habrard, A., and Morvant, E. (2021).  A pac-bayes analysis of adversarial robustness.  Advances in Neural Information Processing Systems, 34.
  * Warmuth, (2004) Warmuth, M. K. (2004).  The optimal pac algorithm.  In Learning Theory: 17th Annual Conference on Learning Theory, Conference on Learning Theory 2004, Banff, Canada, July 1-4, 2004. Proceedings 17, pages 641–642. Springer.
  * Weiss et al., (2018) Weiss, G., Goldberg, Y., and Yahav, E. (2018).  Extracting automata from recurrent neural networks using queries and counterexamples.  In International Conference on Machine Learning, pages 5247–5256. PMLR.
  * Weiss et al., (2019) Weiss, G., Goldberg, Y., and Yahav, E. (2019).  Learning deterministic weighted automata with queries and counterexamples.  Advances in Neural Information Processing Systems, 32.
  * Wiles et al., (2022) Wiles, O., Gowal, S., Stimberg, F., Rebuffi, S.-A., Ktena, I., Dvijotham, K. D., and Cemgil, A. T. (2022).  A fine-grained analysis on distribution shift.  In International Conference on Learning Representations.
  * Yin et al., (2019) Yin, D., Kannan, R., and Bartlett, P. (2019).  Rademacher complexity for adversarially robust generalization.  In International conference on machine learning, pages 7085–7094. PMLR.
  * Zhang et al., (2019) Zhang, H., Yu, Y., Jiao, J., Xing, E., El Ghaoui, L., and Jordan, M. (2019).  Theoretically principled trade-off between robustness and accuracy.  In International conference on machine learning, pages 7472–7482. PMLR.

##  Chapter 8 Proofs from Chapter 5

##  Appendix 8.A Proof of Lemma 5.12

Lemma 5.12. _Let $D$ be an $\alpha$-$\log$-Lipschitz distribution on the
$n$-dimensional boolean hypercube and let $\varphi$ be a conjunction of $d$
literals. Set $\eta=\frac{1}{1+\alpha}$. Then for all $0<\varepsilon<1/2$, if
$d\geq\max\left\\{\frac{4}{\eta^{2}}\log\left(\frac{1}{\varepsilon}\right),\frac{2\rho}{\eta}\right\\}$,
then $\underset{{x\sim D}}{\Pr}\left(\left(\exists y\in B_{\rho}(x)\cdot
y\models\varphi\right)\right)\leq\varepsilon$. _

###### Proof.

Write $\varphi=\ell_{1}\wedge\cdots\wedge\ell_{d}$. Draw a point $x\sim D$
from distribution $D$. Let $X_{1},\dots,X_{d}\in\\{0,1\\}$ be indicator random
variables, respectively denoting whether $x$ satisfies literals
$\ell_{1},\dots,\ell_{d}$. Note that we do not assume the $X_{i}$’s to be
independent from each other. Writing $Y:=\sum_{i=1}^{d}X_{i}$, our goal is to
show that $\underset{{x\sim D}}{\Pr}\left(Y+\rho\geq
d\right)\leq~{}\varepsilon$.

Let $D_{i}$ be the marginal distribution of $X_{i}$ conditioned on
$X_{1},\dots,X_{i-1}$. This distribution is also $\alpha$-$\log$-Lipschitz by
Lemma 3.23, and hence,

$\underset{{X_{i}\sim D_{i}}}{\Pr}\left(X_{i}=1\right)\leq 1-\eta\enspace.$
(31)

Since we are interested in the random variable $Y$ representing the number of
1’s in $X_{1},\dots,X_{d}$, we define the random variables $Z_{1},\dots,Z_{d}$
as follows:

$Z_{k}=\left(\sum_{i=1}^{k}X_{i}\right)-k(1-\eta)\enspace,$

with the convention that $Z_{0}=0$. The sequence $Z_{1},\dots,Z_{d}$ is a
supermartingale with respect to $X_{1},\dots,X_{d}$:

$\displaystyle\underset{{}}{\mathbb{E}}\left[Z_{k+1}\;|\;X_{1},\dots,X_{k}\right]$
$\displaystyle=\underset{{}}{\mathbb{E}}\left[Z_{k}+X_{k+1}-(1-\eta)\;|\;X_{1},\dots,X_{k}\right]$
$\displaystyle=Z_{k}+\underset{{}}{\Pr}\left(X_{k+1}^{\prime}=1\;|\;X_{1},\dots,X_{k}\right)-(1-\eta)$
$\displaystyle\leq Z_{k}\enspace.$ (by (31))

Now, note that all $Z_{k}$’s satisfy $|Z_{k+1}-Z_{k}|\leq 1$, and that
$Z_{d}=Y-d(1-\eta)$. We can thus apply the Azuma-Hoeffding (A.H.) Inequality
to get

$\displaystyle\underset{{}}{\Pr}\left(Y\geq d-\rho\right)$
$\displaystyle\leq\underset{{}}{\Pr}\left(Y\geq
d(1-\eta)+\sqrt{2\log(2/\varepsilon)d}\right)$
$\displaystyle=\underset{{}}{\Pr}\left(Z_{d}-Z_{0}\geq\sqrt{2\log(2/\varepsilon)d}\right)$
$\displaystyle\leq\exp\left(-\frac{\sqrt{2\log(1/\varepsilon)d}^{2}}{2d}\right)$
(A.H.) $\displaystyle=\varepsilon\enspace,$

where the first inequality holds from the given bounds on $d$ and $\rho$:

$\displaystyle d-\rho$ $\displaystyle=(1-\eta)d+\frac{\eta d}{2}+\frac{\eta
d}{2}-\rho$ $\displaystyle\geq(1-\eta)d+\frac{\eta d}{2}$ (since
$\rho\leq\frac{\eta d}{2}$)
$\displaystyle\geq(1-\eta)d+\sqrt{2\log(1/\varepsilon)d}\enspace.$ (since
$d\geq\frac{8}{\eta^{2}}\log(\frac{1}{\varepsilon})$)

∎

##  Appendix 8.B Proof of Corollary 5.24

Corollary 5.24. _The class of $k$-decision lists is efficiently
$\log(n)$-robustly learnable under log-Lipschitz distributions._

###### Proof of Corollary 5.24.

Let $\mathcal{A}$ be the (proper) PAC-learning algorithm for k-DL as in
Rivest, (1987), with sample complexity $\text{poly}(\cdot)$. Fix the input
dimension $n$, target concept $c$ and distribution $D\in\mathcal{D}_{n}$, and
let $\rho=\log n$. Fix the accuracy parameter $0<\varepsilon<1/2$ and
confidence parameter $0<\delta<1/2$ and let $\eta=1/(1+\alpha)^{k}$. Set

$\varepsilon_{0}=C_{1}\left(\frac{16\varepsilon}{e^{4}n^{2k+2}}\right)^{C_{2}}\min\left\\{\left(\frac{16\varepsilon}{e^{4}n^{2k+2}}\right)^{C_{3}},n^{-C_{4}}\right\\}\enspace,$

where the constants are the ones derived in Theorem 5.23.

Let $m=\lceil\text{poly}(n,1/\delta,1/\varepsilon_{0})\rceil$, and note that
$m$ is polynomial in $n$, $1/\delta$ and $1/\varepsilon$.

Let $S\sim D^{m}$ and $h=\mathcal{A}(S)$. Let the target and hypothesis be
defined as the following decision lists:
$c=((K_{1},v_{1}),\ldots,(K_{r},v_{r}))$ and
$h=((K^{\prime}_{1},v^{\prime}_{1}),\ldots,(K^{\prime}_{s},v^{\prime}_{s}))$,
where the clauses $K_{i}$ are conjunctions of $k$ literals. Given
$i\in\\{1,\ldots,r\\}$ and $j\in\\{1,\ldots,s\\}$, define a $k$-CNF formula
$\varphi^{(c,h)}_{i,j}$ by writing

$\varphi^{(c,h)}_{i,j}=\neg K_{1}\wedge\cdots\wedge\neg K_{i-1}\wedge
K_{i}\wedge\neg K^{\prime}_{1}\wedge\cdots\wedge\neg K^{\prime}_{j-1}\wedge
K^{\prime}_{j}\,.$

Notice that the formula $\varphi^{(c,h)}_{i,j}$ represents the set of inputs
$x\in\mathcal{X}$ that respectively activate vertex $i$ in $c$ and vertex $j$
in $h$.

Since $\underset{{x\sim D}}{\Pr}\left(h(x)\neq c(x)\right)<\varepsilon_{0}$
with probability at least $1-\delta$, any $\varphi^{(c,h)}_{i,j}$ that leads
to a misclassification must have
$\mathsf{SAT}_{0}(\varphi^{(c,h)}_{i,j})<\varepsilon_{0}$. But by Theorem
5.23,
$\mathsf{SAT}_{\log(n)}(\varphi^{(c,h)}_{i,j})<\frac{16\varepsilon}{e^{4}n^{2k+2}}$
for all $\varphi^{(c,h)}_{i,j}$ with probability at least $1-\delta$.

Hence the probability that a $\rho$-bounded adversary can make
$\varphi^{(c,d)}_{i,j}$ true is at most $\frac{16\varepsilon}{e^{4}n^{2k+2}}$.
Taking a union bound over all possible choices of $i$ and $j$ (there are
$\sum_{i=1}^{k}{n\choose k}\leq k\left(\frac{en}{k}\right)^{k}$ possible
clauses in $k$-decision lists, which gives us a crude estimate of
$k^{2}\left(\frac{en}{k}\right)^{2k}\leq\frac{e^{4}n^{2k+2}}{16}$ choices of
$i$ and $j$) we conclude that $\mathsf{R}^{E}_{\log}(h,c)<\varepsilon$.

∎

##  Chapter 9 Proofs from Chapter 6

##  Appendix 9.A Proof of Lemma 6.6

Lemma 6.6. _Let $\mathcal{C}$ be a concept class and $\mathcal{H}$ a
hypothesis class. Any $\rho$-robust ERM algorithm using $\mathcal{H}$ on a
sample of size
$m\geq\frac{1}{\epsilon}\left(\log|\mathcal{H}_{n}|+\log\frac{1}{\delta}\right)$
is a $\rho$-robust learner for $\mathcal{C}$._

###### Proof.

Fix a target concept $c\in\mathcal{C}$ and the target distribution $D$ over
$\mathcal{X}$. Define a hypothesis $h$ to be “bad” if
$R_{\rho}^{D}(c,h)\geq\epsilon$. Note that any robust ERM algorithm will be
robustly consistent on the training sample by the realizability assumption.
Let $\mathcal{E}_{h}$ be the event that $m$ independent examples drawn from
$\mathsf{EX}(c,D)$ are all robustly consistent with $h$. Then, if $h$ is bad,
we have that
$\underset{{}}{\Pr}\left(\mathcal{E}_{h}\right)\leq(1-\epsilon)^{m}\leq
e^{-\epsilon m}$. Now consider the event
$\mathcal{E}=\bigcup_{h\in\mathcal{H}}\mathcal{E}_{h}$. By the union bound, we
have

$\underset{{}}{\Pr}\left(\mathcal{E}\right)\leq\sum_{h\in\mathcal{H}}\underset{{}}{\Pr}\left(\mathcal{E}_{h}\right)\leq\left|\mathcal{H}\right|e^{-\epsilon
m}\enspace.$

Then, bounding the RHS by $\delta$, we have that whenever
$m\geq\frac{1}{\epsilon}\left(\log|\mathcal{H}_{n}|+\log\frac{1}{\delta}\right)$,
no bad hypothesis is _robustly_ consistent with $m$ random examples drawn from
$\mathsf{EX}(c,D)$. If a hypothesis is not bad, it has robust risk bounded
above by $\epsilon$, as required. ∎

##  Appendix 9.B Proof of Lemma 6.8

Lemma 6.8. _Let $\mathcal{C}$ be a concept class and $\mathcal{H}$ a
hypothesis class. Any $\rho$-robust ERM algorithm using $\mathcal{H}$ on a
sample of size
$m\geq\frac{1}{\epsilon}\left(\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H}))\log(1/\epsilon)+\log\frac{1}{\delta}\right)$
is a $\rho$-robust learner for $\mathcal{C}$. _

###### Proof.

The proof is very similar to the VC dimension upper bound in PAC learning. The
main distinction is that instead of looking at the error region of the target
and any function in $\mathcal{H}$, we must look at its $\rho$-expansion.
Namely, we let the target $c\in\mathcal{C}$ be fixed and, for
$h\in\mathcal{H}$, we consider the function $(c\oplus
h)_{\rho}:x\mapsto\mathbf{1}[\exists z\in B_{\rho}(x)\;.\;c(z)\neq h(z)]$ and
define a new concept class $\Delta_{c,\rho}(\mathcal{H})=\left\\{(c\oplus
h)_{\rho}\;|\;h\in\mathcal{H}\right\\}$. It is easy to show that
$\mathsf{VC}(\Delta_{c,\rho}(\mathcal{H}))\leq\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C}))_{\rho}(\mathcal{C},\mathcal{H})$,
as any sign pattern achieved on the LHS can be achieved on the RHS.

The rest of the proof follows from the definition of an $\epsilon$-net and the
bound on the growth function of $\Delta_{c,\rho}(\mathcal{H})$.

First, define the class $\Delta_{c,\rho,\epsilon}(\mathcal{H})$ as
$\left\\{\tilde{c}\in\Delta_{c,\rho}(\mathcal{H})\;|\;\underset{{x\sim
D}}{\Pr}\left(\tilde{c}(x)=1\right)\geq\epsilon\right\\}$, i.e., the set of
functions in $\Delta_{c,\rho}(\mathcal{H})$ which have a robust risk greater
than $\epsilon$. Recall that a set $S$ is an $\epsilon$-net for
$\Delta_{c,\rho}(\mathcal{H})$ if for every
$\tilde{c}\in\Delta_{c,\rho,\epsilon}(\mathcal{H})$, there exists $x\in S$
such that $\tilde{c}(x)=1$. We want to bound the probability that a sample
$S\sim D^{m}$ fails to be an $\epsilon$-net for the class
$\Delta_{c,\rho}(\mathcal{H})$, as if $S$ is an $\epsilon$-net, then any
robustly consistent $h\in\mathcal{H}$ on $S$ will have robust risk bounded
above by $\epsilon$. As with the standard VC dimension, a sample $S$ will be
drawn in two phases. First draw a sample $S_{1}\sim D^{m}$ and let
$\mathcal{E}_{1}$ be the event that $S_{1}$ is not an $\epsilon$-net for
$\Delta_{c,\rho}(\mathcal{H})$. Now, suppose $\mathcal{E}_{1}$ occurs. This
means there exists $\tilde{c}\in\Delta_{c,\rho,\epsilon}(\mathcal{H})$ such
that $\tilde{c}(x)=0$ for all the points $x\in S_{1}$. Fix such a $\tilde{c}$
and draw a second sample $S_{2}\sim D^{m}$. Then, letting $X$ be the random
variable representing the number of points in $S_{2}$ that are such that
$\tilde{c}(x)=1$, we can use Chernoff bound to show that

$\underset{{}}{\Pr}\left(X<\epsilon m/2\right)\leq 2\exp\left(-\frac{\epsilon
m}{12}\right)\enspace,$ (32)

ensuring that whenever $\epsilon m\geq 24$, the probability that at least
$\epsilon m/2$ points in $S_{2}$ satisfy $\tilde{c}(x)=1$ is bounded below by
$1/2$.

Now, consider the event $\mathcal{E}_{2}$ where a sample $S=S_{1}\cup S_{2}$
of size $2m$ such that $|S_{1}|=|S_{2}|=m$ is drawn from $\mathsf{EX}(c,D)$
and there exists a concept
$\tilde{c}\in\Pi_{\Delta_{c,\rho,\epsilon}(\mathcal{H})}(S)$ such that
$|\left\\{x\in S\;|\;\tilde{c}(x)=1|\geq\epsilon m/2\right\\}$ and
$\tilde{c}(x)=0$ for all $x\in S_{1}$, where
$\Pi_{\Delta_{c,\rho,\epsilon}(\mathcal{H})}(S)$ is the set all possible
dichotomies on $S$ induced by $\Delta_{c,\rho,\epsilon}(\mathcal{H})$. Then
$\underset{{}}{\Pr}\left(\mathcal{E}_{2}\right)\geq\frac{1}{2}\underset{{}}{\Pr}\left(\mathcal{E}_{1}\right)$