# On the Computability of Robust PAC Learning

Pascale Gourdeau Vector Institute & University of Toronto, Toronto, ON,
Canada<EMAIL_ADDRESS>Tosca Lechner Cheriton School of
Computer Science, University of Waterloo, Waterloo, ON, Canada;
<EMAIL_ADDRESS>and Ruth Urner Lassonde School of Engineering, EECS
Department, York University, Toronto, ON, Canada;
<EMAIL_ADDRESS>order.

###### Abstract

We initiate the study of computability requirements for adversarially robust
learning. Adversarially robust PAC-type learnability is by now an established
field of research. However, the effects of computability requirements in PAC-
type frameworks are only just starting to emerge. We introduce the problem of
robust computable PAC (robust CPAC) learning and provide some simple
sufficient conditions for this. We then show that learnability in this setup
is not implied by the combination of its components: classes that are both
CPAC and robustly PAC learnable are not necessarily robustly CPAC learnable.
Furthermore, we show that the novel framework exhibits some surprising
effects: for robust CPAC learnability it is not required that the robust loss
is computably evaluable! Towards understanding characterizing properties, we
introduce a novel dimension, the computable robust shattering dimension. We
prove that its finiteness is necessary, but not sufficient for robust CPAC
learnability. This might yield novel insights for the corresponding phenomenon
in the context of robust PAC learnability, where insufficiency of the robust
shattering dimension for learnability has been conjectured, but so far a
resolution has remained elusive.

##  1 Introduction

Formal studies of learnability mostly fall into one of two extremes: the focus
is either on purely statistical (or information-theoretic) aspects, where
predictors and learners are treated as functions; or requirements of
computational efficiency, namely runtime that is polynomial in various
parameters, are imposed. Recent work has introduced the study of learnability
under a more basic, yet arguably essential requirement, namely that both
learners and predictors are computable functions (Agarwal et al., 2020), a
framework termed Computable Probably Approximately Correct (CPAC)
learnability. For binary classification, a setting where various versions of
standard learnability (realizable, agnostic, proper, improper, learnable by
any ERM) are well known to be characterized (in the information-theoretic
sense) by finiteness of the VC dimension, the addition of computability
requirements has revealed a somewhat more fine-grained landscape: CPAC
learnability has been shown to be equivalent to a computable version of the VC
dimension, the so called _effective VC dimension_ , while proper CPAC
learnability was proven to be equivalent to the finiteness of the VC dimension
combined with the existence of a computable _approximate_ ERM learner
(Sterkenburg, 2022; Delle Rose et al., 2023).

In this work, we initiate the study of computable PAC learning in the
(adversarially) robust setting. Adversarial robust PAC learning has by now
been extensively studied, e.g., by Montasser et al. (2019, 2021); Gourdeau et
al. (2021); Awasthi et al. (2023); Lechner et al. (2023) and recent work has
provided a characterization of learnability (again, in the purely information-
theoretic sense) by a parameter of the one inclusion graph of the learning
problem (Montasser et al., 2022). We here explore how adding a requirement of
computability adds more subtle aspects to the questions of robust PAC
learnability, and expose some perhaps surprising aspects of this setup.

We start by setting up a formal framework for robust learning under
computability constraints on the learners and hypotheses, and also the
perturbation sets employed. As a warm-up, we provide some simple sufficient
conditions for learnability in our setting, but also show that the question of
robust CPAC learnability is more subtle than the combination of its
components: we prove that there exist classes that are CPAC learnable and
robustly PAC learnable with respect to perturbation types that are decidable,
yet are not robustly CPAC learnable.

We then explore the role of computability of the robust loss for robust CPAC
learnability. Perhaps surprisingly, the robust loss being computably evaluable
is neither a necessary nor a sufficient requirement for robust learnability.
The insufficiency result relies on showing that there are CPAC learnable
classes with computably evaluable robust loss that do not admit a robust
empirical risk minimization (RERM) oracle (Montasser et al., 2019) which would
return a hypothesis with minimal empirical robust risk on any sample) in the
robust agnostic setting. This result is significant as many works assume
access to an RERM oracle. In particular, the standard reduction of agnostic to
realizable learning in the robust learning setting requires such an oracle
(Montasser et al., 2019), and we here demonstrate an example where
learnability in the robust realizable case does not extend to the agnostic
case through this reduction, since RERM is not computable.

Finally, we explore the role of dimensions for computable robust learnability.
We introduce a novel, computable version of the robust shattering dimension.
Finiteness of the robust shattering dimension has been shown to to be
necessary for robust learnability (Montasser et al., 2019), however it has
remained an open question whether it is also a sufficient condition (Montasser
et al., 2022). For the computable version, we prove that the finiteness of our
_computable robust shattering dimension_ is necessary, yet not sufficient, to
ensure robust CPAC learnability. This result might provide novel insights for
the case without computability constraints. Our results involve deriving a new
no free lunch theorem for robust learning, which might also be of independent
interest.

###  1.1 Related Work

#### Computable Learning.

Incorporating aspects of computability into formal learning frameworks is a
very recent field of study, originally motivated by the establishement of
problems whose learnability is independent of set-theory (Ben-David et al.,
2019). The introduction of the notion of computable PAC (CPAC) learning
(Agarwal et al., 2020) provided a framework for standard binary
classification. Follow up works have by now resulted in a full
characterization of CPAC learnability in terms of the so-called effective VC
dimension (Sterkenburg, 2022; Delle Rose et al., 2023). Very recent works have
extended the study of computability in learning to other learning settings
such as continuous domains (Ackerman et al., 2022) and online learning
(Hasrati and Ben-David, 2023).

#### Robust Learning.

There is a rich learning theory literature on adversarial robustness. Earlier
work focused on the existence of adversarial examples for the stability notion
of robustness (Fawzi et al., 2016, 2018a, 2018b; Gilmer et al., 2018; Shafahi
et al., 2019; Tsipras et al., 2019), and for its true-label counterpart
(Diochnos et al., 2018; Mahloujifar et al., 2019). Many of the works in the
former category highlighted the incompatibility between robustness and
accuracy, while Bhattacharjee and Chaudhuri (2021) and Chowdhury and Urner
(2022) later argued that these two objectives should not be in conflict by
proposing notions of adaptive robusteness. Some studies focus on the sample
complexity of robust learning in a PAC setting through a notion called the
adversarial VC dimension (Cullina et al., 2018). Some upper bounds depend on
the number of perturbations allowed for each instance (Attias et al., 2022b),
others on the VC and dual VC dimension of a hypothesis class obtained through
an improper learner (Montasser et al., 2019), thus also covering the case of
infinite perturbation sets. Ashtiani et al. (2020) later gave an upper bound
for _proper_ robust learning in terms of the VC dimensions of the class and
induced margin class. Montasser et al. (2022) exhibited a characterization of
robust learning based on the one-inclusion graph of Haussler et al. (1994)
adapted to robust learning. The sample complexity of robust learning has also
been studied in the semi-supervised setting (Attias et al., 2022a), through
the lens of transformation invariances (Shao et al., 2022), through Rademacher
complexity bounds (Khim et al., 2019; Yin et al., 2019; Awasthi et al., 2020)
and by the use of online learning algorithms (Diakonikolas et al., 2020;
Bhattacharjee et al., 2021). Robust risk relaxations have been studied by
Viallard et al. (2021); Ashtiani et al. (2023); Bhattacharjee et al. (2023);
Raman et al. (2023), while Balcan et al. (2022, 2023) offered reliability
guarantees for robust learning under various notions of robustness. In terms
of the true-label robust risk, sample complexity upper and lower bounds with
access to random examples only have been derived with respect to
distributional assumptions (Diochnos et al., 2020; Gourdeau et al., 2021,
2022b), as this set-up does not allow distribution-free robust learning
(Gourdeau et al., 2021). To circumvent computational or information-theoretic
obstacles of robust learning with random examples only, recent work has
studied robust learning with the help of oracles (Montasser et al., 2021;
Gourdeau et al., 2022a; Lechner et al., 2023), while other work has instead
looked at curtailing the (computational) power of the adversary (Mahloujifar
and Mahmoody, 2019; Garg et al., 2020). Prior works have also analyzed the
role of computational efficiency in robust learnability (Bubeck et al., 2019;
Degwekar et al., 2019; Gourdeau et al., 2021), however we are the first to
exhibit effects of issues arising from the basic, essential requirement of
computability.

##  2 Problem Set-up

#### Notation.

Denote by $\Sigma$ a finite alphabet, with $\Sigma^{*}$ denoting the set of
all finite words, or strings, over $\Sigma$. We use standard notation for sets
and functions, for example, we let $[n]=\\{1,2,\ldots,n\\}\subset\mathbb{N}$
denote the set of the first $n$ natural numbers.

#### Computability.

Throughout this paper, we will assume we fixed a programming language. The
existence of a program or algorithm is then equivalent to the existence of a
Turing machine. We use $(T_{i})_{i\in\mathbb{N}}$ to denote a fixed
enumeration of all Turing machines/programs. We use the notation $T\equiv S$
to indicate that two Turing Machines have the same behavior as functions (not
necessarily the same encoding, thus not necessarily the same index in the
enumeration). Further, for a Turing machine $T$ and input $x$, we write
$T(x)\downarrow$ to indicate that $T$ halts on input $x$ and we write
$T(x)\uparrow$ to indicate that $T$ loops (does not halt) on input $x$.

We say that a function $f:\Sigma^{*}\rightarrow\Sigma^{*}$ is _total
computable_ if there exists a program $P$ that halts on every string
$\sigma\in\Sigma^{*}$ with $P(\sigma)=f(\sigma)$. A set $S\subseteq\Sigma^{*}$
is called _decidable_ (or recursive) if there exists a program $P$ such that
for every $\sigma\in\Sigma^{*}$, $P$ halts on $\sigma$ and outputs whether
$\sigma\in S$. Finally, a set $S\subseteq\Sigma^{*}$ is called _recursively
enumerable_ (or semidecidable) if there exists a program $P$ that enumerates
all strings in $S$, or, equivalently, if there exists a program $P$ that halts
on every input $\sigma\in S$ and, if it halts, correctly indicates whether
$\sigma\in S$.

Moreover, we will fix a language and proof system for first-order logic that
is both sound and complete: a first-order formula has a proof if and only if
it is a tautology. We additionally require that this language has a rich
enough vocabulary (with respect to function and relation symbols) to guarantee
that the set of all its tautologies is undecidable (e.g. Mendelson (2009),
Proposition 3.54 (Church’s Theorem)).

#### Learnability.

Let $\mathcal{X}$ be the input space and $\mathcal{Y}$ the label space. We
will focus on the case $\mathcal{Y}=\\{0,1\\}$, i.e., binary classification,
and countable domains, thus $\mathcal{X}=\mathbb{N}$. We let
$\mathcal{H}\subseteq\\{0,1\\}^{\mathbb{N}}$ denote a _hypothesis class_ on
$\mathcal{X}$. Given a joint distribution $D$ on
$\mathcal{X}\times\mathcal{Y}$ and a hypothesis $h\in\mathcal{H}$, the _risk_
(or error) of $h$ with respect to $D$ is defined as

$\mathsf{R}(h;D)=\underset{{(x,y)\sim D}}{\Pr}\left(h(x)\neq
y\right)\enspace.$

We will also denote by
$\ell:\mathcal{H}\times\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$ the 0-1
loss function $\ell(h,x,y)=\mathbf{1}[h(x)\neq y]$, and we use the notation
$\mathsf{R}(h;S)=\frac{1}{m}\sum_{i=1}^{m}\ell(h,x_{i},y_{i})$ to denote the
_empirical risk_ of $h$ on a sample
$S=\\{(x_{i},y_{i})\\}_{i=1}^{m}\in(\mathcal{X}\times\mathcal{Y})^{m}$. We
operate in the PAC-learning framework of (Valiant, 1984).

######  Definition 1 (Agnostic PAC Learnability).

A hypothesis class $\mathcal{H}$ is _PAC learnable in the agnostic setting_ if
there exists a learner $\mathcal{A}$ and function $m(\cdot,\cdot)$ such that
for all $\epsilon,\delta\in(0,1)$ and for any distribution $D$, if the input
to $\mathcal{A}$ is an i.i.d. sample $S$ from $D$ of size at least
$m(\epsilon,\delta)$, then, with probability at least $(1-\delta)$ over the
samples, the learner outputs a hypothesis $\mathcal{A}(S)$ with
$\mathsf{R}(\mathcal{A}(S);D)\leq\underset{h\in\mathcal{H}}{\inf}\mathsf{R}(h;D)+\epsilon\enspace.$
The class is said to be _PAC learnable in the realizable setting_ if the above
holds under the condition that
$\underset{h\in\mathcal{H}}{\inf}\mathsf{R}(h;D)=0$.

It is well known that a (binary) hypothesis class is PAC learnable if and only
if it has finite _VC dimension_ (Vapnik and Chervonenkis, 1971), which is
defined below.

######  Definition 2 (Shattering and VC dimension (Vapnik and Chervonenkis,
1971)).

Given a class of functions $\mathcal{H}$ from $\mathcal{X}$ to $\\{0,1\\}$, we
say that a set $S\subseteq\mathcal{X}$ is _shattered by $\mathcal{H}$_ if the
restriction of $\mathcal{H}$ to $S$ is the set of all function from $S$ to
$\\{0,1\\}$. The VC dimension of a hypothesis class $\mathcal{H}$, denoted
$\mathsf{VC}(\mathcal{H})$, is the size $d$ of the largest set that can be
shattered by $\mathcal{H}$. If no such $d$ exists then
$\mathsf{VC}(\mathcal{H})=\infty$.

#### Computable learnability.

The above notion of learnability only considers the size of a sample needed to
ensure generalization; there are no computational limitations. _Efficient_ PAC
learnability (Valiant, 1984) requires that the algorithm $\mathcal{A}$ run in
time that is polynomial in the learning parameters, and that its output be
polynomially evaluable. Sitting in the middle of these two viewpoints is
_computable_ PAC (CPAC) learnability (Agarwal et al., 2020), where we do not
require computational efficiency, but rather that the learning algorithm and
its output be computable. We additionally require that the hypothesis class
$\mathcal{H}$ be computably representable (Agarwal et al. (2020), Remark 4).

######  Definition 3 (Computable Representation of a Hypothesis class (Agarwal
et al., 2020)).

A class of functions $\mathcal{H}$ is _decidably representable (DR)_ if there
exists a decidable set of programs $\mathcal{P}$ such that the set of all
functions computed by a program in $\mathcal{P}$ equals $\mathcal{H}$. We call
it _recursively enumerably_ representable (RER) if there exists such a set of
programs that is recursively enumerable.

The following definition incorporates these requirements for the class that a
learner outputs.

######  Definition 4 (CPAC Learnability, (Agarwal et al., 2020)).

We say that a class $\mathcal{H}$ is (agnostic) CPAC learnable, if there is a
computable (agnostic) PAC learner for $\mathcal{H}$ that outputs total
computable functions as predictors and uses a decidable (recursively
enumerable) representation for these.

#### Adversarial robustness.

Let $\mathcal{U}:\mathcal{X}\rightarrow 2^{\mathcal{X}}$ be a _perturbation
type_ , assigning each point $x\in\mathcal{X}$ a region $\mathcal{U}(x)$
accessible to an adversary, with the convention $x\in\mathcal{U}(x)$. We
define the robust risk as:

$\mathsf{R}_{\mathcal{U}}(h;D)=\underset{{(x,y)\sim D}}{\Pr}\left(\exists
z\in\mathcal{U}(x)\;.\;h(z)\neq y\right)\enspace.$

Similarly as in the standard setting, we will consider the robust loss
function
$\ell^{\mathcal{U}}:\mathcal{H}\times\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$
defined as $\ell^{\mathcal{U}}(h,x,y)=\mathbf{1}[\exists
z\in\mathcal{U}(x)\;.\;h(x)\neq y]$, and denote the empirical robust risk of
predictor $h$ over a sample $S$ by $\mathsf{R}_{\mathcal{U}}(h;S)$.

We will here work with this _stability_ notion of robustness, while prior work
has also explored other notions of robustness with emphasis on label
correctness (Mahloujifar et al., 2019; Gourdeau et al., 2021; Bhattacharjee
and Chaudhuri, 2021; Chowdhury and Urner, 2022).

######  Definition 5 (Agnostic Robust PAC Learnability (Montasser et al.,
2019)).

A hypothesis class $\mathcal{H}$ is $\mathcal{U}$-robustly PAC learnable in
the agnostic setting if there exists a learner $\mathcal{A}$ and a function
$m(\cdot,\cdot)$ such that for all $\epsilon,\delta\in(0,1)$ and for every
distribution $D$, if the input to $\mathcal{A}$ is an i.i.d. sample $S$ from
$D$ of size at least $m(\epsilon,\delta)$, then, with probability at least
$(1-\delta)$ over the samples, the learner outputs a hypothesis
$\mathcal{A}(S)$ with
$\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);D)\leq\underset{h\in\mathcal{H}}{\inf}\mathsf{R}_{\mathcal{U}}(h;D)+\epsilon\enspace.$
The class is said to be $\mathcal{U}$-robustly PAC learnable in the realizable
setting if the above holds under the condition that
$\underset{h\in\mathcal{H}}{\inf}\mathsf{R}_{\mathcal{U}}(h;D)=0$.

#### Computable robust learnability.

We can straightforwardly adapt the definition of CPAC learnability to its
robust counterpart:

######  Definition 6 (Robust CPAC Learnability).

We say that a class $\mathcal{H}$ is $\mathcal{U}$-robustly (agnostic) CPAC
learnable, if there exists a $\mathcal{U}$-robust PAC learner for
$\mathcal{H}$ that also satisfies the computability requirements of a CPAC
learner.

Similarly to the requirements for $\mathcal{H}$, we can require the
perturbation type $\mathcal{U}$ also be DR or RER:

######  Definition 7 (Representations of Perturbation Types).

Let $\mathcal{U}:\mathcal{X}\rightarrow 2^{\mathcal{X}}$ be a perturbation
type. Then $\mathcal{U}$ is said to be _decidably representable (or
recursively enumerable)_ if the set
$\\{(x,z)\;.\;x\in\mathcal{X},z\in\mathcal{U}(x)\\}$ is decidable (or
recursicely enumerable, repectively).

Asking for perturbation types to be decidably representable is quite a natural
requirement. Indeed, we show in Appendix A.2 an example that uses a
perturbation type $\mathcal{U}$ that is not DR and thus makes the
impossibility of $\mathcal{U}$-robust CPAC learning trivial.

As opposed to the binary loss, which depends only on a simple comparison
between two labels, and can thus always be evaluated for computable
predictors, the robust loss is not always computably evaluable. In Section
4.2, we explore the role of the following notion of loss computability.

######  Definition 8 (Robust loss computably evaluable).

Given a hypothesis class $\mathcal{H}$, and perturbation type $\mathcal{U}$,
we say that the robust loss for $\mathcal{U}$ is _computably evaluable on
$\mathcal{H}$_ if
$\ell^{\mathcal{U}}:\mathcal{H}\times\mathcal{X}\times\\{0,1\\}\to\\{0,1\\}$
is a total computable function.

#### Proper learnability and empirical risk minimization.

For all the above notions of learnability, we call the class $\mathcal{H}$
_properly PAC/ CPAC/ $\mathcal{U}$-robustly PAC/ $\mathcal{U}$-robustly CPAC
learnable_ if there exists a learner that satisfies the corresponding
definition of learnability and always outputs functions from $\mathcal{H}$. A
learner $\mathcal{A}$ is said to _perform empirical risk minimization (ERM)_ ,
or _implement an $\mathsf{ERM}_{\mathcal{H}}$ oracle_, if it always outputs a
predictor from the hypothesis class of minimal empirical risk, that is for all
$m\in\mathbb{N}$ and samples $S\in(\mathcal{X}\times\mathcal{Y})^{m}$,

$\mathcal{A}(S)\in\operatorname*{arg\,min}_{h\in\mathcal{H}}\mathsf{R}(h,S)\enspace.$

Robust empirical risk minimization (RERM) is defined analogously for the
robust risk $\mathsf{R}_{\mathcal{U}}$. We now outline different types of RERM
oracles that we will study throughout this work. A labelled sample $S$ is said
to be _robustly realizable_ if
$\min_{h\in\mathcal{H}}\mathsf{R}_{\mathcal{U}}(h;S)=0$, and _robustly non-
realizable_ otherwise. We will distinguish between three cases:

$\bullet$ weak-realizable $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle:
for any robustly realizable sample $S$, the oracle outputs $h$ with
$\mathsf{R}_{\mathcal{U}}(h;S)=0$. On robustly non-realizable samples such an
oracle is allowed not to halt.

$\bullet$ strong-realizable $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$
oracle: for any robustly realizable sample $S$, the oracle outputs $h$ with
$\mathsf{R}_{\mathcal{U}}(h;S)=0$. For any robustly non-realizable sample, it
halts and outputs “not-robustly-realizable”.

$\bullet$ agnostic $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle: the
oracle performs RERM on both robustly realizable and robustly non-realizable
samples.

Note that, if the robust loss is computably evaluable, then the existence of a
computable strong realizable $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$
oracle is equivalent to the existence of an agnostic
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle. Moreover, a strong-
realizable oracle always implies the existence of an agnostic oracle.

#### Useful facts.

Recall the following sufficient condition for CPAC learnability, which we
later use:

######  Fact 9 (Agarwal et al. (2020); Sterkenburg (2022)).

If $\mathsf{VC}(\mathcal{H})$ is finite and there exists a total computable
function that implements an $\mathsf{ERM}_{\mathcal{H}}$ oracle, then
$\mathcal{H}$ is CPAC learnable.

We now recall the following result by Ashtiani et al. (2020), which outlines
sufficient conditions for the proper robust learnability of a class.
Throughout this text, we will use the notation of Ashtiani et al. (2020),
where the _margin class_
$\mathcal{H}^{\mathcal{U}}_{\text{mar}}:=\left\\{\text{mar}^{\mathcal{U}}_{h}\right\\}_{h\in\mathcal{H}}$
consists of the margin sets
$\text{mar}^{\mathcal{U}}_{h}:=\left\\{x\in\mathcal{X}\;|\;\exists
z\in\mathcal{U}(x)\;.\;h(x)\neq h(z)\right\\}$, i.e., given $\mathcal{H}$ and
$\mathcal{U}$, the instances in $\mathcal{X}$ that incur a robust loss of 1
due to a perturbation that is labeled differently by $h$ (rather than due to
mislabeling).

######  Fact 10 (Theorem 7 in (Ashtiani et al., 2020)).

If both the VC dimension of a class $\mathcal{H}$ and the VC dimension of
$\mathcal{H}^{\mathcal{U}}_{\text{mar}}$ are finite, then $\mathcal{H}$ is
properly (agnostically) $\mathcal{U}$-robustly PAC learnable.

##  3 Warm-up: Simple Sufficient Conditions for Robust CPAC Learnability

We start by exhibiting conditions ensuring (proper) robust CPAC learnability
in the agnostic setting.

######  Fact 11.

Let hypothesis class $\mathcal{H}$ and perturbation type $\mathcal{U}$ be such
that
$\mathsf{VC}(\mathcal{H})+\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})<\infty$
and there exists a total computable function that implements an agnostic
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle. Then $\mathcal{H}$ is
properly $\mathcal{U}$-robustly CPAC learnable. If there exists a computable
function that implements a weak-realizable
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle, then $\mathcal{H}$ is
$\mathcal{U}$-robustly CPAC learnable in the realizable case.

###### Proof.

By Fact 10,
$D:=\mathsf{VC}(\mathcal{H})+\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})<\infty$
implies that a finite sample of size $O\left(\frac{D\log D+\log
1/\delta}{\epsilon^{2}}\right)$ is sufficient to guarantee robust
generalization w.r.t. $\mathcal{U}$, whenever a robust risk minimizer for a
given sample is returned. Since robust ERM is computably implementable, we are
done. ∎

######  Fact 12.

Let hypothesis class $\mathcal{H}$ be RER and perturbation type $\mathcal{U}$
be such that $\ell^{\mathcal{U}}$ is computably evaluable on $\mathcal{H}$.
Then $\mathcal{H}$ admits a weak realizable RERM oracle.

###### Proof.

Let $S$ be a robustly realizable input sample. The following procedure
computes $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$. Since the class is RER,
we can iterate through the class $\mathcal{H}=(h_{i})_{i\in\mathbb{N}}$ and
for each $h_{i}$:
$\bullet$ Compute $\mathsf{R}^{\mathcal{U}}(h_{i},S)$, which is possible since
the robust loss is computably evaluable;
$\bullet$ Check whether $\mathsf{R}^{\mathcal{U}}(h_{i},S)=0$. If so, halt and
output $h_{i}$, otherwise continue.
As we know that there exists $h\in\mathcal{H}$ with $R^{\mathcal{U}}(h,S)=0$,
we know that the algorithm will halt. ∎

######  Remark 13.

Combining Facts 11 and 12 shows that for a RER hypothesis class $\mathcal{H}$
and a perturbation type $\mathcal{U}$, the conditions
$\mathsf{VC}(\mathcal{H})+\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})<\infty$
and $\ell^{\mathcal{U}}$ on $\mathcal{H}$ being computably evaluable are
sufficient to guarantee proper robust CPAC learnability in the robustly
realizable case.

Now, we show that having access to a computable online learner (see Definition
15 in (Hasrati and Ben-David, 2023)) and a counterexample oracle, together
with the margin class having finite VC dimension, is sufficient to guarantee
robust learnability. The counterexample oracle we will use is the Perfect
Attack Oracle (PAO) of (Montasser et al., 2021), which takes as input
$h,x,y\in\mathcal{H}\times\mathcal{X}\times\\{0,1\\}$ and returns
$z\in\mathcal{U}(x)$ such that $h(z)\neq y$, if such a counterexample exists.
The proof is included in Appendix A.1.

######  Proposition 14.

Let $\mathcal{H}$ be computably online learnable, and let $\mathcal{U}$ be
such that $\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})<\infty$. Then
$\mathcal{H}$ is $\mathcal{U}$-robustly CPAC learnable with access to the PAO
in the realizable setting.

##  4 Relating CPAC and Robust CPAC Learning

In this section, we study the relationship between CPAC learnability, robust
CPAC learnability and the computable evaluability of the robust loss. We start
in Section 4.1 with examples where we have CPAC learnability, but not robust
CPAC learnability. The constructions in that section also show that the robust
loss being computably evaluable is not sufficient for robust CPAC
learnability. In Section 4.2, we show that the robust loss being computably
evaluable is in general also not necessary to ensure robust CPAC learning,
which might be unexpected.

###  4.1 Robust CPAC learnability is not implied by Robust PAC + CPAC
learnability

In this section, we first look at two examples of hypothesis classes and
perturbation types where CPAC learnability and robust learnability do not
imply robust CPAC learnability. In both cases, the perturbation types are DR,
in contrast to Example 29. Our first result holds in the robust agnostic case
for general, improper learners, and the second, in the robust realizable case
for proper learners.

######  Theorem 15.

There exists a hypothesis class $\mathcal{H}$ and perturbation type
$\mathcal{U}$ such that (i) $\mathcal{H}$ is properly CPAC learnable, (ii)
$\mathcal{U}$ is decidably representable and (iii) $\mathcal{H}$ is properly
$\mathcal{U}$-robustly PAC learnable, but $\mathcal{H}$ is not (improperly)
$\mathcal{U}$-robustly CPAC learnable in the agnostic setting.

###### Sketch.

Fix a proof system for ﬁrst-order logic over a rich enough vocabulary that is
sound and complete. Let $\left\\{\varphi_{i}\right\\}_{i\in\mathbb{N}}$ and
$\left\\{\pi_{j}\right\\}_{j\in\mathbb{N}}$ be enumerations of all theorems
and proofs, respectively. We define the following hypothesis class on
$\mathbb{N}$:

$\mathcal{H}=\left\\{h_{a}\;:\;\forall
i\in\mathbb{N},\;h_{a}(2i)=\mathbf{1}[i\leq a]\wedge
h_{a}(2i+1)=1\right\\}_{a\in\mathbb{N}\cup\left\\{\infty\right\\}}\enspace.$

Thus, $\mathcal{H}$ is the the concept class where each function defines a
threshold on even integers, and is the constant function 1 on odd integers.

The perturbation sets are defined as follows. For any $i\in\mathbb{N}$ we set:

$\displaystyle\mathcal{U}(6i)=\left\\{6i\right\\}\cup\left\\{2j+1\right\\}_{j\in\mathbb{N}}\enspace,$
$\displaystyle\mathcal{U}(6i+2)=\left\\{6i+2\right\\}\enspace,$
$\displaystyle\mathcal{U}(6i+4)=\left\\{6i+2,6i+4\right\\}\cup\left\\{2j+1\;|\;\pi_{j}\text{
is a proof of theorem }\varphi_{i}\right\\}_{j\in\mathbb{N}}\enspace,$
$\displaystyle\mathcal{U}(2i+1)=\left\\{2i+1\right\\}\enspace.$

The properties (i)-(iii) are fulfilled by this construction, as we will show
in detail in the appendix. Furthermore, we note that the question of whether
$\mathcal{U}(6i)\cap\mathcal{U}(6i+4)$ is empty is equivalent to whether there
exists a proof for theorem $\varphi_{i}$, and thus is undecidable. We now show
that this undecidable problem can be reduced to agnostically robustly CPAC
learning $\mathcal{H}$ with respect to $\mathcal{U}$. To see this define the
distributions $D_{i}$ on $\mathbb{N}\times\\{0,1\\}$ as follows:

$\displaystyle D_{i}((6i,1))=1/2,\qquad D_{i}((6i+2,1))=1/6,\qquad
D_{i}((6i+4,0))=1/3\enspace.$

For a learner to succeed on all the $D_{i}$, it needs to decide whether
$\mathcal{U}(6i)\cap\mathcal{U}(6i+4)=\emptyset$ for all $i$. ∎

For more detail and the full proof we refer the reader to Appendix B.1.

The result above holds in the improper agnostic setting. Next, we look at the
robustly realizable setting, and show an impossibility result in case we
require a _proper_ robust learning algorithm.

######  Theorem 16.

There exists a hypothesis class $\mathcal{H}$ and perturbation type
$\mathcal{U}$ such that (i) $\mathcal{H}$ is properly CPAC learnable, (ii)
$\mathcal{U}$ is decidably representable, and (iii) $\mathcal{H}$ is properly
$\mathcal{U}$-robustly PAC learnable, but not properly $\mathcal{U}$-robustly
CPAC learnable in the realizable setting.

###### Proof.

Let $(T_{i})_{i\in\mathbb{N}}$ be an enumeration of Turing Machines. We define
the hypothesis class on $\mathbb{N}$:

$\mathcal{H}=\\{h_{a,b,c}\;:\;\forall i\;(h_{a,b,c}(2i)=1\text{ iff
}i\in\\{a,b\\})\wedge(h_{a,b,c}(2i+1)=c)\\}_{a,b\in\mathbb{N},\;c\in\\{0,1\\}}\enspace,$

i.e., $\mathcal{H}$ is the class of functions that only maps at most two even
numbers to 1 and are constant on the odd numbers. First note that
$\mathsf{VC}(\mathcal{H})=3$, as for any shattered set $X\subseteq\mathbb{N}$,
we can have at most one odd integer in $X$, and at most two even ones. It is
straightforward to show that any set of the form $\left\\{2i,2j,2k+1\right\\}$
for $i,j,k\in\mathbb{N}$ can be shattered. This implies, by Theorem 6 in
(Montasser et al., 2019), that $\mathcal{H}$ is (improperly) robustly
learnable for any perturbation type $\mathcal{U}$. We will argue below that,
for the perturbation type we employ, $\mathcal{H}$ is in fact properly
$\mathcal{U}$-robustly CPAC learnable. Second, as ERM is easily implementable
for $\mathcal{H}$, we have that $\mathcal{H}$ is properly CPAC learnable.

We define the perturbation sets as follows:

$\displaystyle\mathcal{U}(2i)=\\{2i\\}\cup\\{2j+1:T_{i}(i)\text{ halts within
}j\text{ steps }\\}\enspace,$
$\displaystyle\mathcal{U}(2i+1)=\left\\{2i+1\right\\}\enspace.$

Note that $\mathcal{U}$ is decidably representable, as for any two points
$x_{1},x_{2}$, the program outlined in Appendix B.2 decides whether
$x_{2}\in\mathcal{U}(x_{1})$.

We now show that for this $\mathcal{U}$, $\mathcal{H}$ is _properly_
$\mathcal{U}$-robustly learnable. To see this, we again use the terminology of
Ashtiani et al. (2020), and consider the margin class
$\mathcal{H}^{\mathcal{U}}_{\text{mar}}$, where each $h_{a,b,c}\in\mathcal{H}$
fixes a set $\text{mar}_{h_{a,b,c}}^{\mathcal{U}}$, which we will denote by
$\text{mar}_{a,b,c}$ for brevity. Note that, from the property
$k\subseteq\mathcal{U}(k)$ that holds for all $k\in\mathbb{N}$, only even
integers can belong in some set $\text{mar}_{a,b,c}$. Recall that $h_{a,b,c}$
maps at most two even numbers $a$ and $b$ to $1$ and all odd numbers to
$c\in\\{0,1\\}$.

We distinguish two cases:

  * •

$c=0$: then $\text{mar}_{a,b,0}=\left\\{2a\;|\;T_{a}(a)\text{
halts}\right\\}\cup\left\\{2b\;|\;T_{b}(b)\text{ halts}\right\\}$,

  * •

$c=1$: then $\text{mar}_{a,b,1}=\left\\{2i\;|\;T_{i}(i)\text{
halts}\right\\}\setminus\left\\{2a,2b\right\\}$.

From this, we can see that shattered sets must only contain even integers $k$
such that $T_{k/2}(k/2)$ halts. We now argue that
$\mathsf{VC}(\mathcal{H}^{\mathcal{U}}_{\text{mar}})=5$. Consider a set
$X=\left\\{k_{1},\dots,k_{6}\right\\}$ of size 6 such that $k_{i}$ is even and
$T_{k_{i}/2}(k_{i}/2)$ halts for all $i=1,\dots,6$. Then the subset
$\left\\{k_{1},k_{2},k_{3}\right\\}$ cannot be part of the projection of
$\mathcal{H}^{\mathcal{U}}_{\text{mar}}$ onto $X$, and thus
$\left\\{k_{1},\dots,k_{6}\right\\}$ cannot be shattered. Indeed, note that
for $c=0$, the margin set $\text{mar}_{a,b,0}$ has size $2$ only for any
$a,b\in\mathbb{N}$. Thus
$\left\\{k_{1},k_{2},k_{3}\right\\}\in\text{mar}_{a,b,c}$ would imply that
there exists $a,b\in\mathbb{N}$ such that
$k_{1},k_{2},k_{3}\in\text{mar}_{a,b,1}$. However then, by definition, there
are at most two of $k_{4},k_{5},k_{6}$ that are not in $\text{mar}_{a,b,1}$, a
contradiction. Finally, consider a set $X=\left\\{k_{1},\dots,k_{5}\right\\}$
of size 5 such that $k_{i}$ is even and $T_{k_{i}/2}(k_{i}/2)$ halts for all
$i=1,\dots,5$. Any subset $X^{\prime}\subseteq X$ is contained in the
projection of $\mathcal{H}^{\mathcal{U}}_{\text{mar}}$ onto $X$: if
$|X^{\prime}|\geq 3$ there exists $a,b\in\mathbb{N}$ such that
$X^{\prime}\in\text{mar}_{a,b,1}$, and otherwise if $|X^{\prime}|\leq 2$ there
exists $a,b\in\mathbb{N}$ such that $X^{\prime}\in\text{mar}_{a,b,0}$, and
thus $X$ is shattered.

Now, for any $i,k\in\mathbb{N}$, with $i\neq k$, we define a distribution
$D_{i,k}$ on $\mathbb{N}\times\\{0,1\\}$ as follows:

$\displaystyle D_{i,k}(2i,1)=D_{i,k}(2k,0)=1/2\enspace.$

We will now show that $\mathcal{H}$ is not properly $\mathcal{U}$-robustly
CPAC learnable with respect to the set of distributions
$\left\\{D_{i,k}\right\\}_{i,k\in\mathbb{N}}$ in the realizable case. Note
that robustly realizability here implies that at most one of the sets
$\mathcal{U}(2i)$ or $\mathcal{U}(2k)$ is not a singleton. Indeed, if
$\mathcal{U}(2i)=\left\\{2i\right\\}$ then $T_{i}(i)$ does not halt, whereas
if $\left\\{2i\right\\}\subset\mathcal{U}(2i)$ (strict inequality) then
$T_{i}(i)$ halts, and similarly for $2k$. Hence, since we have
$D_{i,k}(2i,1)=D_{i,k}(2k,0)=1/2$, to choose between $h_{i,i^{\prime},0}$ and
$h_{i,i^{\prime},1}$ for some fixed $i^{\prime}\in\mathbb{N}$ with
$i^{\prime}\neq k$ and $i^{\prime}\neq i$ we need to know whether either of
$\mathcal{U}(2i)$ or $\mathcal{U}(2k)$ is a singleton.

Now consider the following decision problem, which we term $\mathsf{TwoHalt}$.
Given two Turing machines $T_{i}$ and $T_{j}$, the task is to correctly
predict which run out of $T_{i}(i)$ and $T_{j}(j)$ halts if only one of them
does. If both runs loop, the solver should still halt and produce an output;
in case both halt the decider may run indefinitely or halt and produce some
output. That is, we only require a correct decision if exactly one of
$T_{i}(i)$ and $T_{j}(j)$ halts, and require the program to halt if both loop.
We show below (see Lemma 30) that no algorithm can satisfy these requirements.

We now argue that a $\mathcal{U}$-robust proper CPAC learner can be used to
solve $\mathsf{TwoHalt}$, and thus, by invoking Lemma 30, which is stated and
proved in Appendix B.3, conclude that no such learner exists. If a
$\mathcal{U}$-robust proper CPAC learner for $\mathcal{H}$ existed, there is a
sample size $M$ that suffices for robust loss at most $\epsilon=1/3$ with
probability $1-\delta=2/3$ over all $M$ size samples from $D_{i,k}$. We then
solve $\mathsf{TwoHalt}$ by running the learner on all $M$-length sequences
over the points $(2i,1)$ and $(2k,0)$, and taking the majority for the label
that the resulting predictor gives on the odd numbers.

∎

###  4.2 Robust CPAC learnability and its relationship to the computability of
$\ell^{\mathcal{U}}$ and RERM

One of the obstacles with robust CPAC learning is that, even if a class
consists of computable functions, the robust loss might not be pointwise
computable. This is in contrast to the CPAC setting for which the binary loss
is always computable for computable functions. It is then natural to ask what
relationship exists between the computability of the robust loss and the
robust CPAC learnability of a class. The following result demonstrates that
the computability of the pointwise robust loss for all hypotheses in the class
is not a necessary criterion for robust CPAC learnability.

######  Theorem 17.

There exist $\mathcal{H}$ and $\mathcal{U}$ such that (i) $\mathcal{H}$ is
properly CPAC learnable, (ii) $\mathcal{U}$ is decidably representable, and
(iii) $\mathcal{H}$ is properly $\mathcal{U}$-robustly CPAC learnable in the
agnostic setting and admits a computable agnostic
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle, but the function
$\ell^{\mathcal{U}}$ is not computably evaluable on $\mathcal{H}$.

###### Sketch.

This theorem is proven with the following construction. Let $\mathcal{X}$,
$(\varphi_{i})_{i\in\mathbb{N}}$ and $(\pi_{i})_{i\in\mathbb{N}}$ be defined
as in the construction for Theorem 15. Let $(i,0)$, represent the $i$-th
formula and for any $i,j$ let $(i,j)$ represent the $j$-th proof
(independently of $i$). Let
$\mathcal{H}=\\{h_{a,b}\\}_{a,b\in\mathbb{N}\cup\\{0,\infty\\}}$, where

$h_{a,b}(i,j)=\begin{cases}1&\text{ if }i<a\text{ or }(i=a\text{ and }j\leq
b)\\\ 0&\text{ otherwise }\end{cases}\enspace.$

It is clear that $\mathsf{VC}(\mathcal{H})=1$ and that ERM is computably
implementable, so $\mathcal{H}$ is properly CPAC learnable. We define the
perturbation regions as follows:

$\displaystyle\mathcal{U}(i,0)=\\{(i,0)\\}\cup\\{(i,j):\pi_{j}\text{ proves
}\varphi_{i}\\}\enspace,$
$\displaystyle\mathcal{U}(i,j)=\\{(i,0),(i,j)\\}\enspace.$

It is also easy to verify that this perturbation type is DR. In the full
proof, we show that in general there is no algorithm that evaluates the loss
of each hypotheses $h_{a,b}$ on every point. However, there is an RER subclass
$\mathcal{H}^{\prime}=\\{h_{a,\infty}:a\in\mathbb{N}\\}\subset\mathcal{H}$
such that every hypothesis in $\mathcal{H}^{\prime}$ is computably evaluable
and such that on any distribution, $\mathcal{H}^{\prime}$ contains an optimal
(with respect to $\mathcal{H}$) hypothesis. It is thus possible to robustly
CPAC learn $\mathcal{H}$ by performing RERM over $\mathcal{H}^{\prime}$. ∎

The full proof is included in Appendix C.1. We next show that, even if the
robust loss is computably evaluable on $\mathcal{H}$, and the class
$\mathcal{H}$ is properly CPAC learnable and properly robustly PAC learnable,
neither the existence of a robust ERM oracle nor robust CPAC learnability are
implied.

######  Theorem 18.

There exist a DR hypothesis class $\mathcal{H}$ and a DR perturbation type
$\mathcal{U}$ such that (i) $\mathcal{H}$ is properly CPAC learnable, (ii)
$\mathcal{H}$ is properly $\mathcal{U}$-robustly PAC learnable, and (iii) the
robust loss is computably evaluable, but there is no strong realizable
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$-oracle and $\mathcal{H}$ is not
properly agnostically $\mathcal{U}$-robustly CPAC learnable.

###### Sketch.

We prove this theorem with the following construction. Let the instance space
be $\mathcal{X}=\mathbb{N}\times\mathbb{N}$. Let the hypothesis class be
$\mathcal{H}=\\{h_{i,j}:i,j\in\mathbb{N}\\}$, where

$h_{i,j}(x)=\begin{cases}1&\text{ if }x=(i,k)\text{ with }k\leq j\\\ 0&\text{
otherwise }\end{cases}\enspace,$

i.e., $\mathcal{H}$ is the class of initial segments on
$\\{(i,j)\\}_{j\in\mathbb{N}}$ for all $i\in\mathbb{N}$. We set the
perturbation types to:

$\displaystyle\mathcal{U}((i,0))$
$\displaystyle=\\{(i,0)\\}\cup\\{(i,k):T_{i}\text{ does not halt after
}k\text{ steps on the empty input }\\}\enspace,$
$\displaystyle\mathcal{U}((i,j))$
$\displaystyle=\begin{cases}\\{(i,j),(i,0)\\}&T_{i}\text{ does not halt after
}j\text{ steps on the empty input}\\\ \\{(i,j)\\}&\text{ otherwise.
}\end{cases}\enspace$

The proof of the impossibility of agnostic robust CPAC learning and of the
non-existence of a strong realizable RERM oracle relies on reductions from the
Halting problem. ∎

The detailed proof shows that the construction in the sketch above fulfills
all the requirements for proving the theorem and is included in Appendix C.2.
Recall from Fact 12 that the class being RER (a weaker assumption than being
DR) and the robust loss being computably evaluable imply the existence of a
weak realizable $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$-oracle. We
therefore demonstrated a separation between the existence of RERM oracles in
the robust realizable versus the agnostic case. Our proof also shows that the
existence of weak realizable RERM oracles does not imply the existence of
agnostic RERM orcalce. Furthermore, note that the existence of a strong
realizable RERM oracle implies computable evaluablility of robust loss. Thus,
the result of Theorem 17 shows that the existence of a agnostic RERM oracle
does not imply the existence of a strong realizable RERM oracle.

In the non-robust setting, proper _strong_ CPAC (SCPAC) learnability (which is
CPAC learnability with the additional requirement that the sample complexity
function $m(\cdot,\cdot,\cdot)$ be computable) implies the existence of an
$\mathsf{ERM}_{\mathcal{H}}$ oracle (Sterkenburg (2022), Theorem 8). We finish
this section by showing that a similar result holds in robust learning if the
robust loss is computably evaluable. The proof of Proposition 19 below is
included in Appendix C.3.

######  Proposition 19.

Let $\mathcal{H}$ be a hypothesis class and $\mathcal{U}$ a perturbation type
such that $\ell^{\mathcal{U}}$ is computably evaluable. Then, if $\mathcal{H}$
is properly $\mathcal{U}$-robustly SCPAC learnable in the agnostic setting,
$\mathcal{H}$ admits a computable agnostic
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle; and if $\mathcal{H}$ is
properly $\mathcal{U}$-robustly SCPAC learnable in the realizable setting,
then $\mathcal{H}$ admits a computable weak realizable
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle.

##  5 Necessary Conditions for Robust CPAC Learning

In this section, we define a complexity measure, denoted by
$c$-$\dim_{\mathcal{U}}$, and prove its finiteness is implied by robust CPAC
learnability for RER perturbation types. We later study its relationship with
the VC dimension, and show that it cannot characterize robust CPAC
learnability.

###  5.1 No-Free-Lunch Theorems

Prior work has shown that standard CPAC learnability is equivalent to the
hypothesis class having finite _effective VC dimension_ , which can be thought
of as a computable version of the VC dimension (Sterkenburg, 2022; Delle Rose
et al., 2023). The effective VC dimension of $\mathcal{H}$ is the smallest
$k$, such that there exists a computable function
$w:\mathbb{N}^{k+1}\rightarrow\\{0,1\\}^{k+1}$ that, when given a set of
domain points of size $k+1$, outputs a labelling that cannot be achieved by
any $h\in\mathcal{H}$. The function $w$ is called a _witness function_. The
complexity measure $c$-$\dim_{\mathcal{U}}(\mathcal{H})$ that we introduce in
this section is a computable version of the robust shattering dimension
$\dim_{\mathcal{U}}(\mathcal{H})$ which has been shown to lowerbound the
robust sample complexity (Montasser et al., 2019).

######  Definition 20 ($\mathcal{U}$-robust shattering dimension Montasser et
al. (2019)).

A set $X=\\{x_{i}\\}_{i=1}^{m}$ is $\mathcal{U}$-robustly shattered by
$\mathcal{H}$ if there exists a set
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{m}$ with
$x_{i}\in\mathcal{U}(z_{i}^{0})\cap\mathcal{U}(z_{i}^{1})$ for all
$i=1,\dots,m$ such that for all $y_{1}\dots,y_{m}\in\\{0,1\\}$ there exists
$h\in\mathcal{H}$ such that for all $i=1,\dots,m$ and
$z^{\prime}\in\mathcal{U}(z_{i}^{y_{i}})$ we have that $h(z^{\prime})=y_{i}$.
The _robust shattering dimension of $\mathcal{H}$_, denoted
$\dim_{\mathcal{U}}(\mathcal{H})$, is the largest integer $k$ such that there
exists a set of size $k$ that is $\mathcal{U}$-robustly shattered. If
arbitrarily large $\mathcal{U}$-robustly shattered sets exist, then
$\dim_{\mathcal{U}}(\mathcal{H})=\infty$.

Note that, for $X$ to be robustly shattered, for all $i\neq j$ the regions
$\mathcal{U}(z_{i}^{1})$ and $\mathcal{U}(z_{j}^{0})$ must be disjoint. Now,
contrary to the standard notion of shattering, there are two factors at play
in a set being robustly shattered. The first one is whether a set is robustly
_“shatterable”_ , namely whether, by definition of $\mathcal{U}$–and without
considering $\mathcal{H}$–the set $X$ _could_ be robustly shattered by an
arbitrary set of functions (which holds trivially in the standard case). The
second factor, if robust shatterability holds, is as in the standard case:
whether there does in fact exists a set of hypotheses from $\mathcal{H}$ that
can realize the robust shattering. To highlight this distinction, we introduce
the following property:

######  Definition 21 (Robust shatterability).

A set $X=\left\\{x_{1},\dots,x_{m}\right\\}\subseteq\mathcal{X}$ is called
_$\mathcal{U}$ -robustly shatterable_ if there exists a set
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{m}\subseteq\mathcal{X}$ with
$x_{i}\in\mathcal{U}(z_{i}^{0})\cap\mathcal{U}(z_{i}^{1})$ and for all $i\neq
j$ the regions $\mathcal{U}(z_{i}^{1})$ and $\mathcal{U}(z_{j}^{0})$ are
disjoint. In this case, $Z$ is said to _admit a $\mathcal{U}$-robustly
shatterable set_.

We now define the computable version of Definition 20, which also uses the
notion of a witness function. If $\dim_{\mathcal{U}}(\mathcal{H})<k$ then for
all $m\geq k$, for all $X=\\{x_{i}\\}_{i=1}^{m}$ and for all
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{m}$ with
$x_{i}\in\mathcal{U}(z_{i}^{0})\cap\mathcal{U}(z_{i}^{1})$ there exists a
labelling that is _not_ $\mathcal{U}$-robustly realizable by $\mathcal{H}$.
Thus:

######  Definition 22 (Computable robust shattering dimension).

A _$k$ -witness of $\mathcal{U}$-robust shattering dimension_ for
$\mathcal{H}$ is a function $w:\mathbb{N}^{2(k+1)}\rightarrow\\{0,1\\}^{k+1}$
such that when given a set $Z=\\{(z_{i}^{0},z_{i}^{1})\\}_{i=1}^{k+1}$ that
admits a robustly shatterable set, it outputs $y_{1}\dots,y_{k+1}\in\\{0,1\\}$
such that for all $h\in\mathcal{H}$ there exist $i=1,\dots,m$ and
$z^{\prime}\in\mathcal{U}(z_{i}^{y_{i}})$ with $h(z^{\prime})\neq y_{i}$. The
_computable robust shattering dimension of $\mathcal{H}$_, denoted
$\text{c-}\dim_{\mathcal{U}}(\mathcal{H})$, is the smallest integer $k$ such
that there exists a _computable_ $k$-witness of robust shattering dimension.
If no such $k$ exists, $\text{c-}\dim_{\mathcal{U}}(\mathcal{H})=\infty$.

We note that, by definition, if $\mathcal{U}$ does not admit a shatterable set
of size $k$, then any function is a $k$-witness. Towards showing that
finiteness of the computable robust shattering dimension is a necessary
condition for $\mathcal{U}$-robust CPAC learnability, we first formulate a No-
Free-Lunch theorem for robust learnability, leaving aside computability
considerations for the time being.

######  Lemma 23 (Robust No-Free-Lunch Theorem).

Let $\mathcal{X}$ be the domain and $\mathcal{U}:\mathcal{X}\rightarrow
2^{\mathcal{X}}$ a perturbation type. Let $\mathcal{A}$ be any computable
learner. Let $m$ be a number smaller than $|\mathcal{X}|/4$ representing the
training set size, with the property that there exist $4m$ points
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$ such that $Z$ admits a
$\mathcal{U}$-robustly shatterable set. Then there exists a distribution $D$
over $\mathcal{X}\times\\{0,1\\}$ such that (i) there exists a function
$f:\mathcal{X}\rightarrow\\{0,1\\}$ such that
$\mathsf{R}_{\mathcal{U}}(f;D)=0$; and (ii) with probability at least $1/7$
over $S\sim D^{m}$, $\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);D)\geq 1/8$.

The proof of Lemma 23 is included in Appendix D.1. We comment on the robust
shatterability in the impossibility results from Section 4 in Appendix E.

######  Remark 24.

First note that we work with $\mathcal{X}=\mathbb{N}$, so the condition
$m\leq|\mathcal{X}|/4$ is immediately satisfied for any $m$. Second, note that
the robust shatterability condition in the theorem, which depends on the
perturbation type $\mathcal{U}$, is satisfied if the regions $\mathcal{U}(x)$
are, e.g., balls of finite radii.

We are now ready to state the computable version of Lemma 23, which involves
not only the existence of a distribution and function that are robustly
realizable on which the learner performs poorly, but also the ability to
computably find such a pair:

######  Lemma 25 (Computable Robust No-Free-Lunch Theorem).

Fix instance space $\mathcal{X}$ and perturbation type
$\mathcal{U}:\mathcal{X}\rightarrow 2^{\mathcal{X}}$. Let $\mathcal{A}$ be any
computable learner and furthermore suppose that the perturbation type
$\mathcal{U}$ is recursively enumerably representable (RER). Then for any
$m\in\mathbb{N}$, any domain $\mathcal{X}$ of size at least $4m$ and any
subset $Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$ that admits a
$\mathcal{U}$-robustly shatterable set, we can computably find a function
$f:\mathcal{X}\rightarrow\\{0,1\\}$ that is computable on $Z$ such that

$\underset{{S\sim
D^{m}}}{\mathbb{E}}\left[R_{\mathcal{U}}(\mathcal{A}(S);D)\right]\geq
1/4\qquad\text{and}\qquad\underset{{S\sim
D^{m}}}{\Pr}\left(R_{\mathcal{U}}(\mathcal{A}(S);D)\geq 1/8\right)\geq
1/7\enspace,$ (1)

where $D$ is the uniform distribution on
$\left\\{(z_{i}^{y_{i}},y_{i})\right\\}_{i=1}^{2m}$ for some
$y\in\\{0,1\\}^{2m}$ such that for all $i=1,\dots,2m$ and for all
$z^{\prime}\in\mathcal{U}(z_{i}^{y_{i}})$ we have that $f(z^{\prime})=y_{i}$ .

The proof of Lemma 25 follows a similar argument as the proof of the
computable No-Free-Lunch Theorem shown in Agarwal et al. (2020), but the
computation of the robust loss differs:

###### Proof.

We first computably find a shatterable set $X=\\{x_{1},x_{2},\dots,x_{2m}\\}$
corresponding to the set of pairs
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$. That is
$x_{i}\in\mathcal{U}(z_{i}^{0})\cap\mathcal{U}(z_{i}^{1})$ for all $i\in[2m]$.
Since the sets $\mathcal{U}(z_{i}^{0})$ and $\mathcal{U}(z_{i}^{1})$ are
recursively enumerable, we can computably find such an $x_{i}$ in their
intersection for each $i$. We simply enumerate the instances from
$\mathcal{U}(z_{i}^{0})$ and $\mathcal{U}(z_{i}^{1})$ by alternating between
the two sets until we find an instance that belongs to both enumerations.
Because we are guaranteed that $Z$ admits a $\mathcal{U}$-robustly shatterable
set, this process is guaranteed to halt.

The existence of a function $f$ and distribution $D$ satisfying Equation 1
follows directly from Lemma 23, so it remains to show that, using
$\mathcal{A}$ we can computably find such an $f$ and $D$. Note that the
construction of the pairs $(f_{j},D_{j})$ in Lemma 23 corresponds to pairs of
$\mathcal{U}$-robustly realizable distributions. There are $T=2^{2m}$ such
pairs, as putting mass on $z_{i}^{y_{i}}$ implies not putting mass on
$z_{i}^{\neg y_{i}}$. Second, for a given $(f_{j},D_{j})$ and a fixed sample
size $m$, there are $k=(2m)^{m}$ sequences $\\{S_{l}^{j}\\}_{l=1}^{k}$ of $m$
instances drawn from $D_{j}$, each equally likely as $D_{j}$ is uniform on its
support. We now run $\mathcal{A}$ on all these sequences, and compute a lower
bound on the expected robust loss of $\mathcal{A}$ on $(f_{j},D_{j})$ by
employing the labels of the learner’s output on the shatterable set $X$:

$\displaystyle\underset{{S\sim
D_{j}^{m}}}{\mathbb{E}}\left[\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);D_{j})\right]=\frac{1}{k}\sum_{l=1}^{k}\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S^{j}_{l});D_{j})$
$\displaystyle=\frac{1}{k}\sum_{l=1}^{k}\frac{1}{2m}\sum_{i=1}^{2m}\ell^{\mathcal{U}}\left(\mathcal{A}(S^{j}_{l}),z_{i}^{(j)},y_{i}^{(j)}\right)$
$\displaystyle\geq\frac{1}{k}\sum_{l=1}^{k}\frac{1}{2m}\sum_{i=1}^{2m}\mathbbm{1}\left[{\mathcal{A}(S^{j}_{l})(x_{i})\neq
y_{i}^{(j)}}\right]\enspace.$

As argued in the proof of Lemma 23, there exist $f_{j},D_{j}$ such that

$\frac{1}{k}\sum_{l=1}^{k}\frac{1}{2m}\sum_{i=1}^{2m}\mathbbm{1}\left[{\mathcal{A}(S^{j}_{l})(x_{i})\neq
y_{i}^{(j)}}\right]\geq 1/8\enspace.$

Furthermore, we note that the for every $j$, the set of sequences
$\\{S_{l}^{j}\\}_{j=1}^{k}$ can be computably generated and that the
expression
$\frac{1}{k}\sum_{l=1}^{k}\frac{1}{2m}\sum_{i=1}^{2m}\mathbbm{1}\left[{\mathcal{A}(S^{j}_{l})(x_{i})\neq
y_{i}^{(j)}}\right]$ can be computably evaluated. Thus by iterating through
$j=1,\dots,T$ until finding $j$ that satisfies
$\frac{1}{k}\sum_{l=1}^{k}\frac{1}{2m}\sum_{i=1}^{2m}\mathbbm{1}\left[{\mathcal{A}(S^{j}_{l})(x_{i})\neq
y_{i}^{(j)}}\right]\geq 1/8$, we can computably find $(f_{j},D_{j})$ with
$\underset{{S\sim
D_{j}^{m}}}{\mathbb{E}}\left[\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);(D_{j})\right]\geq
1/8$. We further note that the corresponding labelling $f_{j}$ can be
computably evaluated on all elements of $Z$ as required. ∎

Note that if the perturbation sets are DR, then the function $f$ above is
total computable on $\mathcal{X}$. We now state the main result of this
section:

######  Theorem 26.

Let $\mathcal{H}$ be (improperly) $\mathcal{U}$-robustly CPAC learnable and
suppose the perturbation type $\mathcal{U}$ is RER. Then the computable
$\mathcal{U}$-robust shattering dimension
$\text{c-}\dim_{\mathcal{U}}(\mathcal{H})$ of $\mathcal{H}$ is finite, i.e.,
$\mathcal{H}$ admits a computable $k$-witness of $\mathcal{U}$-robust
shattering dimension for some $k\in\mathbb{N}$.

The proof, included in Appendix D.2, follows the reasoning of Lemma 9 in
Sterkenburg (2022).

###  5.2 Relationship between the effective VC dimension and
$c\text{-}\dim_{\mathcal{U}}$

It has been shown that the dimension $\dim_{\mathcal{U}}(\mathcal{H})$ yields
a lower bound on the sample complexity for $\mathcal{U}$-robust learning
(Montasser et al., 2019). However, it has remained an open question whether
this dimension also provides an upper bound on the sample complexity, thus
whether it actually characterizes $\mathcal{U}$-robust learnability. Here we
show that a corresponding conjecture in the CPAC setting is not true. We first
relate the effective VC dimension, which we will identify as
$c\text{-}\mathsf{VC}$ to denote computability, to the computable robust
shattering dimension.

######  Lemma 27.

For any class $\mathcal{H}$ and perturbation type $\mathcal{U}$ admitting a
recursively enumerable representation, we have
$c\text{-}\dim_{\mathcal{U}}(\mathcal{H})\leq
c\text{-}\mathsf{VC}(\mathcal{H})$.

###### Proof.

Let $\mathcal{H}$ have finite effective VC dimension $k$. Then there exist a
computable function $w:\mathbb{N}^{k+1}\rightarrow\\{0,1\\}^{k+1}$ such that
$w$ is a $k$-witness of VC dimension for $\mathcal{H}$. Now, let
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{k+1}$ admit a robustly
shatterable set. Because $\mathcal{U}$ is RER, we can find a robustly
shatterable set $X$ of size $k+1$ for $Z$. It suffices to output the labelling
$w(X)$, which is not achievable by any $h\in\mathcal{H}$, and thus not
robustly achievable by any $h\in\mathcal{H}$ as well, and so
$c\text{-}\dim_{\mathcal{U}}(\mathcal{H})\leq k$, as required. ∎

We know that CPAC learnability of a class $\mathcal{H}$ implies
$c\text{-}\mathsf{VC}(\mathcal{H})<\infty$ (Sterkenburg, 2022), and thus, by
the above lemma, CPAC learnability implies
$c\text{-}\dim_{\mathcal{U}}(\mathcal{H})\leq
c\text{-}\mathsf{VC}(\mathcal{H})<\infty$. On the other hand, we have shown in
this work that there exist $\mathcal{H}$, $\mathcal{U}$ such that CPAC
learnability does not imply $\mathcal{U}$-robust CPAC learnability (see
Theorem 15). Thus there are classes that are not $\mathcal{U}$-robust CPAC
learnable while having finite effective robust shattering dimension, meaning
that this dimension does not characterize robust CPAC learnability:

######  Corollary 28.

The dimension $c\text{-}\dim_{\mathcal{U}}(\mathcal{H})$ does not characterize
$\mathcal{U}$-robust CPAC learnability.

##  6 Conclusion

We have initiated the study of robust computable PAC learning, and provided a
formal framework for its analysis. We showed sufficient conditions that enable
robust CPAC learnability, as well as showed that CPAC learnability and robust
learnability are not in themselves sufficient to guarantee robust CPAC
lernability. We also exhibited a counterintuitive relationship between the
computability of the robust loss and robust CPAC learnability. This is of
particular interest, as the evaluability of the robust loss has often
implicitly been used in the literature on the theory of robust learning, or
potential issues on the evaluability of the robust loss have been circumvented
by the use of oracles. We finished by studying the role of the computable
robust shattering dimension in robust CPAC learnability, showing that its
finiteness is a necessary but not sufficient condition.

## Acknowledgements

Pascale Gourdeau has been supported by a Vector Postdoctoral Fellowship and an
NSERC Postdoctoral Fellowship. Tosca Lechner has been supported by a Vector
Research Grant and a Waterloo Apple PhD Fellowship. Ruth Urner is also an
Affiliate Faculty Member at Toronto’s Vector Institute, and acknowldeges
funding through an NSERC Discovery grant.

## References

  * Ackerman et al. (2022) Nathanael Ackerman, Julian Asilis, Jieqi Di, Cameron Freer, and Jean-Baptiste Tristan.  Computable pac learning of continuous features.  In _Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science_ , pages 1–12, 2022.
  * Agarwal et al. (2020) Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, and Ruth Urner.  On learnability wih computable learners.  In _Algorithmic Learning Theory_ , pages 48–60. PMLR, 2020.
  * Ashtiani et al. (2020) Hassan Ashtiani, Vinayak Pathak, and Ruth Urner.  Black-box certification and learning under adversarial perturbations.  In _International Conference on Machine Learning_ , pages 388–398. PMLR, 2020.
  * Ashtiani et al. (2023) Hassan Ashtiani, Vinayak Pathak, and Ruth Urner.  Adversarially robust learning with tolerance.  In _International Conference on Algorithmic Learning Theory_ , pages 115–135. PMLR, 2023.
  * Attias et al. (2022a) Idan Attias, Steve Hanneke, and Yishay Mansour.  A characterization of semi-supervised adversarially robust pac learnability.  _Advances in Neural Information Processing Systems_ , 35:23646–23659, 2022a.
  * Attias et al. (2022b) Idan Attias, Aryeh Kontorovich, and Yishay Mansour.  Improved generalization bounds for adversarially robust learning.  _Journal of Machine Learning Research_ , 23(175):1–31, 2022b.
  * Awasthi et al. (2020) Pranjal Awasthi, Natalie Frank, and Mehryar Mohri.  Adversarial learning guarantees for linear hypotheses and neural networks.  In _International Conference on Machine Learning_ , pages 431–441. PMLR, 2020.
  * Awasthi et al. (2023) Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong.  Theoretically grounded loss functions and algorithms for adversarial robustness.  In _International Conference on Artificial Intelligence and Statistics_ , pages 10077–10094. PMLR, 2023.
  * Balcan et al. (2022) Maria-Florina Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma.  Robustly-reliable learners under poisoning attacks.  In _Conference on Learning Theory_ , pages 4498–4534. PMLR, 2022\.
  * Balcan et al. (2023) Maria-Florina F Balcan, Steve Hanneke, Rattana Pukdee, and Dravyansh Sharma.  Reliable learning in challenging environments.  _Advances in Neural Information Processing Systems_ , 36, 2023.
  * Ben-David et al. (2019) Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff.  Learnability can be undecidable.  _Nat. Mach. Intell._ , 1(1):44–48, 2019.
  * Bhattacharjee and Chaudhuri (2021) Robi Bhattacharjee and Kamalika Chaudhuri.  Consistent non-parametric methods for maximizing robustness.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 9036–9048, 2021.
  * Bhattacharjee et al. (2021) Robi Bhattacharjee, Somesh Jha, and Kamalika Chaudhuri.  Sample complexity of robust linear classification on separated data.  In _International Conference on Machine Learning_ , pages 884–893. PMLR, 2021.
  * Bhattacharjee et al. (2023) Robi Bhattacharjee, Max Hopkins, Akash Kumar, Hantao Yu, and Kamalika Chaudhuri.  Robust empirical risk minimization with tolerance.  In _International Conference on Algorithmic Learning Theory_ , pages 182–203. PMLR, 2023.
  * Bubeck et al. (2019) Sebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn.  Adversarial examples from computational constraints.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97, pages 831–840. PMLR, 2019.
  * Chowdhury and Urner (2022) Sadia Chowdhury and Ruth Urner.  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, 2022.
  * Cullina et al. (2018) Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal.  PAC-learning in the presence of evasion adversaries.  _Advances in Neural Information Processing Systems_ , 2018.
  * Degwekar et al. (2019) Akshay Degwekar, Preetum Nakkiran, and Vinod Vaikuntanathan.  Computational limitations in robust classification and win-win results.  In _Conference on Learning Theory, COLT_ , volume 99, pages 994–1028. PMLR, 2019.
  * Delle Rose et al. (2023) Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, and Tomasz Steifer.  Find a witness or shatter: the landscape of computable pac learning.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pages 511–524. PMLR, 2023.
  * Diakonikolas et al. (2020) Ilias Diakonikolas, Daniel M Kane, and Pasin Manurangsi.  The complexity of adversarially robust proper learning of halfspaces with agnostic noise.  _Advances in Neural Information Processing Systems_ , 33:20449–20461, 2020.
  * Diochnos et al. (2018) Dimitrios Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody.  Adversarial risk and robustness: General definitions and implications for the uniform distribution.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Diochnos et al. (2020) Dimitrios I. Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody.  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, 2020.
  * Fawzi et al. (2016) Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard.  Robustness of classifiers: from adversarial to random noise.  In _Advances in Neural Information Processing Systems_ , pages 1632–1640, 2016.
  * Fawzi et al. (2018a) Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi.  Adversarial vulnerability for any classifier.  _Advances in neural information processing systems_ , 31, 2018a.
  * Fawzi et al. (2018b) Alhussein Fawzi, Omar Fawzi, and Pascal Frossard.  Analysis of classifiers robustness to adversarial perturbations.  _Machine Learning_ , 107(3):481–508, 2018b.
  * Garg et al. (2020) Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mahmoody Mohammad.  Adversarially robust learning could leverage computational hardness.  In _Algorithmic Learning Theory_ , pages 364–385. PMLR, 2020.
  * Gilmer et al. (2018) Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian J. Goodfellow.  Adversarial spheres.  In _6th International Conference on Learning Representations, ICLR Workshop Track Proceedings_. OpenReview.net, 2018.
  * Gourdeau et al. (2021) Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell.  On the hardness of robust classification.  _The Journal of Machine Learning Research_ , 22(1):12521–12549, 2021.
  * Gourdeau et al. (2022a) Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell.  When are local queries useful for robust learning?  _Advances in Neural Information Processing Systems_ , 35:33920–33933, 2022a.
  * Gourdeau et al. (2022b) Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell.  Sample complexity bounds for robustly learning decision lists against evasion attacks.  In _International Joint Conference in Artificial Intelligence_ , 2022b.
  * Hasrati and Ben-David (2023) Niki Hasrati and Shai Ben-David.  On computable online learning.  In _International Conference on Algorithmic Learning Theory_ , pages 707–725. PMLR, 2023.
  * Haussler et al. (1994) David Haussler, Nick Littlestone, and Manfred K Warmuth.  Predicting $\\{$0, 1$\\}$-functions on randomly drawn points.  _Information and Computation_ , 115(2):248–292, 1994.
  * Khim et al. (2019) Justin Khim, Varun Jog, and Po-Ling Loh.  Adversarial influence maximization.  In _2019 IEEE International Symposium on Information Theory (ISIT)_ , pages 1–5. IEEE, 2019.
  * Lechner et al. (2023) Tosca Lechner, Vinayak Pathak, and Ruth Urner.  Adversarially robust learning with uncertain perturbation sets.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Mahloujifar and Mahmoody (2019) Saeed Mahloujifar and Mohammad Mahmoody.  Can adversarially robust learning leverage computational hardness?  In _Algorithmic Learning Theory_ , pages 581–609. PMLR, 2019.
  * Mahloujifar et al. (2019) Saeed Mahloujifar, Dimitrios I Diochnos, and Mohammad Mahmoody.  The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure.  _AAAI Conference on Artificial Intelligence_ , 2019.
  * Mendelson (2009) Elliott Mendelson.  _Introduction to mathematical logic (5. ed.)_.  Chapman and Hall, 2009.
  * Montasser et al. (2019) Omar Montasser, Steve Hanneke, and Nathan Srebro.  VC classes are adversarially robustly learnable, but only improperly.  In _Conference on Learning Theory_ , pages 2512–2530. PMLR, 2019\.
  * Montasser et al. (2021) Omar Montasser, Steve Hanneke, and Nathan Srebro.  Adversarially robust learning with unknown perturbation sets.  In _Conference on Learning Theory_ , pages 3452–3482. PMLR, 2021\.
  * Montasser et al. (2022) Omar Montasser, Steve Hanneke, and Nati Srebro.  Adversarially robust learning: A generic minimax optimal learner and characterization.  _Advances in Neural Information Processing Systems_ , 35:37458–37470, 2022.
  * Raman et al. (2023) Vinod Raman, Unique Subedi, and Ambuj Tewari.  On proper learnability between average-and worst-case robustness.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Shafahi et al. (2019) Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein.  Are adversarial examples inevitable?  In _7th International Conference on Learning Representations (ICLR 2019)_ , 2019.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning - From Theory to Algorithms_.  Cambridge University Press, 2014.
  * Shao et al. (2022) Han Shao, Omar Montasser, and Avrim Blum.  A theory of pac learnability under transformation invariances.  _Advances in Neural Information Processing Systems_ , 35:13989–14001, 2022.
  * Sterkenburg (2022) Tom F Sterkenburg.  On characterizations of learnability with computable learners.  In _Conference on Learning Theory_ , pages 3365–3379. PMLR, 2022\.
  * Tsipras et al. (2019) Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry.  Robustness may be at odds with accuracy.  In _International Conference on Learning Representations_ , 2019.
  * Valiant (1984) Leslie G Valiant.  A theory of the learnable.  _Communications of the ACM_ , 27(11):1134–1142, 1984.
  * Vapnik and Chervonenkis (1971) Vladimir Vapnik and Alexey Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In _Theory of Probability and Its Applications_. 1971.
  * Viallard et al. (2021) Paul Viallard, Eric Guillaume VIDOT, Amaury Habrard, and Emilie Morvant.  A pac-bayes analysis of adversarial robustness.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Yin et al. (2019) Dong Yin, Ramchandran Kannan, and Peter Bartlett.  Rademacher complexity for adversarially robust generalization.  In _International conference on machine learning_ , pages 7085–7094. PMLR, 2019.

##  Appendix A Proofs and Remarks from Section 3

###  A.1 Proof of Theorem 14

###### Proof.

We will use the computable online algorithm $\mathcal{A}$ as a black-box. Let
$D:=\mathsf{VC}(\mathcal{H})+\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})$
and note that online learnability implies that
$\mathsf{VC}(\mathcal{H})\leq\mathsf{Lit}(\mathcal{H})<\infty$, and so
$D<\infty$.

Let $S=\left\\{(x_{i},y_{i})\right\\}_{i=1}^{m}$ be drawn i.i.d. from an
arbitrary robustly-realizable distribution $D$ on
$\mathcal{X}\times\\{0,1\\}$. We outline below a robust CPAC algorithm, which
is essentially the $\mathsf{CycleRobust}$ algorithm of (Montasser et al.,
2021) with the online algorithm $\mathcal{A}$ being used, implements robust
ERM on $S$:

Input: $S=\left\\{(x_{i},y_{i})\right\\}_{i=1}^{m}$, computable online
algorithm $\mathcal{A}$ for $\mathcal{H}$

Output: $h\in\mathcal{H}$ such that $h$ achieves zero robust loss on $S$

$K\leftarrow 0$, $h\leftarrow\mathcal{A}(\emptyset)$;

while  _$K\leq\mathsf{Lit}(\mathcal{H})$_ do

for  _$i=1,\dots,m$_ do

if  _$(z,y)\leftarrow\mathsf{PAO}(h,x_{i},y_{i})$_ then $\triangleright$
robust loss is 1, get counterexample

$K++$ ;

$\triangleright$ Update mistake count

$h\leftarrow\mathcal{A}((z,y))$ $\triangleright$ Update hypothesis

Break $\triangleright$ Exit for-loop

else if  _$i=m$_ then

return $h$ $\triangleright$ $h$ is robustly consistent on $S$

$\triangleright$ No counterexample $\Rightarrow$ go to next index

end for

end while

return $h$

Algorithm 1 $\mathcal{U}$-robust CPAC algorithm

Note that, because of robust realizability, we are guaranteed that
$\mathcal{A}$ makes at most $\mathsf{Lit}(\mathcal{H})$ mistakes, after which
$h$ will be $\mathcal{U}$-robustly consistent on $S$. The program above makes
a finite number of calls to $\mathcal{A}$, and thus is computable by the fact
that $\mathcal{A}$ is itself a computatble online learner. By Fact 11, we are
done. ∎

###  A.2 Decidable Representation of Perturbation Types

######  Example 29.

We exhibit $\mathcal{H}$, $\mathcal{U}$ such that $\mathcal{H}$ is CPAC
learnable and $\mathcal{U}$-robustly PAC learnable but $\mathcal{H}$ is not
(improperly) $\mathcal{U}$-robustly CPAC learnable. In this example,
$\mathcal{U}$ is not DR. The hypothesis class is as follows:

$\mathcal{H}:=\left\\{h_{a,b}(i)=\mathbf{1}[i\in\left\\{a,b\right\\}]\right\\}\enspace.$

Clearly $\mathsf{VC}(\mathcal{H})=2$ and ERM is computably implementable, so
by Fact 9, $\mathcal{H}$ is CPAC learnable. Moreover, $\mathcal{H}$ having
finite VC dimension implies that it is $\mathcal{U}$-robustly PAC learnable
(Montasser et al., 2019).

We now define the perturbation type:

$\mathcal{U}(2i)=\\{2i\\}\cup\\{2i+1\;|\;T_{i}\text{ halts on the empty
word}\\}\enspace,$ $\mathcal{U}(2i+1)=\\{2i+1\\}\cup\\{2i\;|\;T_{i}\text{
halts on the empty word}\\}\enspace.$

We now define distributions $D_{i}$:

$D_{i}(2i,1)=D_{i}(2i+1,0)=1/2\enspace.$

Clearly, the labelling $l(2_{i})=1$ and $l(2i+1)=0$ is optimal (and gives zero
robust risk) if and only if $T_{i}$ does not halt on the empty word.
Otherwise, if $T_{i}$ halts, $l$ incurs a robust risk of 1, and any function
satisfying $h(2i)=h(2i+1)$ is a robust risk minimizer incurring a robust risk
of $1/2$.

If $\mathcal{H}$ were (improperly) $\mathcal{U}$-robustly CPAC learnable,
there would be a robust learning algorithm $\mathcal{A}$ for $\mathcal{H}$
with sample complexity $m(\epsilon,\delta)$. Letting $M\in\mathbb{N}$ being an
upper bound on $m(1/3,1/2)$, then with probability at least $2/3$,
$\mathcal{A}$ returns a hypothesis with robust risk within $1/3<1/2$ of the
robust risk minimizer in $\mathcal{H}$ when run on a sample of size $M$. Then,
running $\mathcal{A}$ on all $2^{M}$ sequences of length $M$ with elements in
$\\{2i,2i+1\\}$ (which are equally probable), we end up with optimal
hypotheses on two thirds of the runs. Checking, for each hypothesis $h$,
whether $h(2i)=h(2i+1)$ and taking the majority vote over all sequences, we
get a decider for whether $T_{i}$ halts on the empty word. And so
$\mathcal{H}$ is not (improperly) $\mathcal{U}$-robustly CPAC learnable. Note
here that if we had a way to know whether $k\in\mathcal{U}(2i)$, i.e., if
$\mathcal{U}$ was DR, we would immediately be able to implement robust ERM for
samples from the distributions defined above. Not requiring perturbation
regions to be DR thus makes deriving impossibility results for robust CPAC
learning relatively trivial.

##  Appendix B Proofs and Algorithms from Section 4.1

###  B.1 Proof of Theorem 15

###### Proof.

Fix a proof system for ﬁrst-order logic over a rich enough vocabulary that is
sound and complete. Let $\left\\{\varphi_{i}\right\\}_{i\in\mathbb{N}}$ and
$\left\\{\pi_{j}\right\\}_{j\in\mathbb{N}}$ be enumerations of all theorems
and proofs, respectively. We define the following hypothesis class on
$\mathbb{N}$:

$\mathcal{H}=\left\\{h_{a}\;:\;\forall
i\in\mathbb{N},\;h_{a}(2i)=\mathbf{1}[i\leq a]\wedge
h_{a}(2i+1)=1\right\\}_{a\in\mathbb{N}\cup\left\\{\infty\right\\}}\enspace.$

Thus, $\mathcal{H}$ is the the concept class where each function defines a
threshold on even integers, and is the constant function 1 on odd integers.

First, to show (i), note that $\mathsf{VC}(\mathcal{H})=1$, as for any set $X$
of two even integers, the labelling $h(x)=0$, $h(z)=1$ cannot be realized on
two even integers $x<z$, and odd integers can only have labelling 1, and thus
cannot be in a shattered set. As ERM is easily implementable for
$\mathcal{H}$, we have that $\mathcal{H}$ is properly CPAC learnable by Fact
9.

Now, we define the perturbation sets as follows. For any $i\in\mathbb{N}$ we
set:

$\displaystyle\mathcal{U}(6i)=\left\\{6i\right\\}\cup\left\\{2j+1\right\\}_{j\in\mathbb{N}}\enspace,$
$\displaystyle\mathcal{U}(6i+2)=\left\\{6i+2\right\\}\enspace,$
$\displaystyle\mathcal{U}(6i+4)=\left\\{6i+2,6i+4\right\\}\cup\left\\{2j+1\;|\;\pi_{j}\text{
is a proof of theorem }\varphi_{i}\right\\}_{j\in\mathbb{N}}\enspace,$
$\displaystyle\mathcal{U}(2i+1)=\left\\{2i+1\right\\}\enspace.$

Note that the question of whether $\mathcal{U}(6i)\cap\mathcal{U}(6i+4)$ is
empty is equivalent to whether there exists a proof for theorem $\varphi_{i}$,
and thus is undecidable.

It is straightforward to show (ii), as for every integer $i\in\mathbb{N}$, we
can represent $\mathcal{U}(6i+4)$ with the program $P_{6i+4}$, which we have
included below.

Input: $x,i\in\mathbb{N}$

Output: Whether $x\in\mathcal{U}(6i+1)$

if  _$x\in\left\\{6i+2,6i+4\right\\}$_ then

output yes

else if  _$x$ is even_ then

output no

else

$j\leftarrow\frac{x-1}{2}$;

if  _$\pi_{j}$ proves $\varphi_{i}$_ then

output yes

else

output no

end if

end if

Algorithm 2 Program $P_{6i+4}$ to decide whether $x\in\mathcal{U}(6i+4)$

Now, for all other $k$, deciding whether $x\in\mathcal{U}(k)$ is also easily
representable as a program $P_{k}$ (we can just assume
$\mathcal{U}(x)=\left\\{x\right\\}$ if there does not exists $i\in\mathbb{N}$
such that $k\in\left\\{6i,6i+2,6i+4\right\\}$, in order for $\mathcal{U}$ to
be well-defined).

To show (iii), we follow the notation of (Ashtiani et al., 2020) and show that
$\mathsf{VC}(\mathcal{H}^{\mathcal{U}}_{\text{mar}})=1$, which implies proper
robust learnability by Fact 11 (also Fact 10). Recall that the class
$\mathcal{H}^{\mathcal{U}}_{\text{mar}}$ consists of the sets
$\text{mar}^{\mathcal{U}}_{h}:=\left\\{x\in\mathcal{X}\;|\;\exists
z\in\mathcal{U}(x)\;.\;h(x)\neq h(z)\right\\}$, defined for each
$h\in\mathcal{H}$. Now, fix $a\in\mathbb{N}$, which induces the function
$h_{a}$ and the set $\text{mar}_{h_{a}}^{\mathcal{U}}$, which we will denote
by $\text{mar}_{a}$ for simplicity. Because of the condition $h(x)\neq h(z)$
in the definition of $\text{mar}_{a}$ and the property that
$\left\\{k\right\\}\subseteq\mathcal{U}(k)$, the only integers
$k\in\mathbb{N}$ that can belong to $\text{mar}_{a}$ are those for which
$\left\\{k\right\\}$ is a proper subset of $\mathcal{U}(k)$, i.e., those for
which there exists $i\in\mathbb{N}$ such that $k=6i$ or $k=6i+4$. We can see
that

$\displaystyle\text{mar}_{a}=$
$\displaystyle\left\\{6i\;|\;6i>2a\right\\}_{i\in\mathbb{N}}\cup\left\\{6i+4\;|\;\varphi_{i}\text{
is a tautology}\wedge 6i+4>2a\right\\}_{i\in\mathbb{N}}$
$\displaystyle\cup\left\\{6i+4\;|\;\varphi_{i}\text{ not a tautology}\wedge
6i+2=2a\right\\}_{i\in\mathbb{N}}\enspace,$

as these are precisely the instances which incur a robust loss of 1 with
respect to $h_{a}$:

  * •

If $k=6i$ then since
$\mathcal{U}(6i)=\left\\{6i\right\\}\cup\left\\{2j+1\right\\}_{j\in\mathbb{N}}$,
we have that $k\in\text{mar}_{a}$ iff $h_{a}(k)=0$,

  * •

If $k=6i+4$ and $\varphi_{i}$ is a tautology, then since

$\mathcal{U}(6i+4)=\left\\{6i+2,6i+4\right\\}\cup\left\\{2j+1\;|\;\pi_{j}\text{
is a proof of theorem }\varphi_{i}\right\\}_{j\in\mathbb{N}}\enspace,$

we have that $k\in\text{mar}_{a}$ iff $h_{a}(k)=0$ (we cannot have
$h_{a}(6i+4)=1$ while $h_{a}(6i+2)=0$),

  * •

Else, if $k=6i+4$ and $\varphi_{i}$ is not a tautology,
$\mathcal{U}(6i+4)=\left\\{6i+2,6i+4\right\\}$, and $k\in\text{mar}_{a}$ iff
$h(6i+2)\neq h(6i+4)$ iff $6i+2=2a$.

Now, it suffices to consider the subsets of
$X=\left\\{6i,6i+4\right\\}_{i\in\mathbb{N}}$ to find the largest shattered
set, as these are the only instances that can belong to some set
$\text{mar}_{a}$. We partition $X$ into two parts $P_{1}$ and $P_{2}$, where
$P_{1}=\left\\{6i\right\\}_{i\in\mathbb{N}}\cup\left\\{6i+4\;|\;\varphi_{i}\text{
is a tautology}\right\\}_{i\in\mathbb{N}}$ and
$P_{2}=\left\\{6i+4\;|\;\varphi_{i}\text{ is not a
tautology}\right\\}_{i\in\mathbb{N}}$. On the one hand,
$\left\\{\text{mar}_{a}\right\\}_{a\in\mathbb{N}}$ restricted to $P_{1}$ is
simply thresholds on $P_{1}$, and so at most one element from $P_{1}$ can be
in a shattered set. On the other hand,
$\left\\{\text{mar}_{a}\right\\}_{a\in\mathbb{N}}$ restricted to $P_{2}$ is
the class of singletons, so again at most one element from $P_{2}$ can be in a
shattered set. Thus, we have established that
$\mathsf{VC}(\mathcal{H}^{\mathcal{U}}_{\text{mar}})\leq 2$. To see that
$\mathsf{VC}(\mathcal{H}^{\mathcal{U}}_{\text{mar}})=1$ consider arbitrary
$k_{1}\in P_{1}$ and $k_{2}=6i+4\in P_{2}$ for some
$i,i^{\prime}\in\mathbb{N}$. It is easy to see that
$\left\\{k_{1},k_{2}\right\\}$ or $\left\\{k_{2}\right\\}$ won’t be in the
projection of $\mathcal{H}^{\mathcal{U}}_{\text{mar}}$ onto
$\left\\{k_{1},k_{2}\right\\}$. Indeed, $k_{2}$ being in a set in the
projection implies that there is a unique $\text{mar}_{a}$ such that
$k_{2}\in\text{mar}_{a}$, and $k_{1}$ is either in $\text{mar}_{a}$ or not.

Finally, to show that $\mathcal{H}$ not (improperly) $\mathcal{U}$-robustly
CPAC learnable in the agnostic setting we define a set of distributions for
which no computable learner for $\mathcal{H}$ succeeds. For each
$i\in\mathbb{N}$ we define a distribution $D_{i}$ on
$\mathbb{N}\times\\{0,1\\}$ as follows:

$\displaystyle D_{i}((6i,1))=1/2\enspace,$ $\displaystyle
D_{i}((6i+2,1))=1/6\enspace,$ $\displaystyle D_{i}((6i+4,0))=1/3\enspace.$

To determine optimal predictors on these distributions, we distinguish two
cases:

  1. 1.

$\mathcal{U}(6i)\cap\mathcal{U}(6i+4)=\emptyset$ : this implies that
$\mathcal{U}(6i+4)=\left\\{6i+2,6i+4\right\\}$. Since
$\mathcal{U}(6i+2)\cap\mathcal{U}(6i+4)\neq\emptyset$ and these points have
different labels under distribution $D_{i}$, no predictor can achieve robust
loss $0$ on both points simultaneously. Thus no predictor can achieve robust
risk less than $1/6$. Note that $h_{3i,\infty}$ has robust risk $1/6$ on
$D_{i}$, and is therefore an optimal predictor on $D_{i}$. Furthermore, note
that any optimal predictor $h$ on $D_{i}$ must satisfy $h(6i+2)=h(6i+4)=0$.

  2. 2.

$\mathcal{U}(6i)\cap\mathcal{U}(6i+4)\neq\emptyset$ : in this case, since $6i$
and $6i+4$ have different labels under distribution $D_{i}$ and intersecting
perturbation sets, no predictor can achieve robust loss $0$ on both points and
thus no predictor can achieve robust loss less than $1/3$ on $D_{i}$. Note
that $h_{\infty,\infty}$ (the constant function 1) has robust risk $1/3$ on
$D_{i}$ and is thus a robust risk minimizer in this case. Furthermore, any
optimal predictor $h$ on $D_{i}$ must satisfy $h(6i)=h(6i+2)=1$, to not incur
additional robust loss.

We thus established that we have $h(6i+2)=1$ for an optimal predictor on
$D_{i}$ (and any predictor that has robust loss less than $1/6$ more than the
optimal) if and only if $\mathcal{U}(6i)\cap\mathcal{U}(6i+4)\neq\emptyset$
and thus if and only if $\varphi_{i}$ has a proof.

We now argue that for any $i\in\mathbb{N}$, a $\mathcal{U}$-robust CPAC
learner $\mathcal{A}$ for $\mathcal{H}$, proper or not, can be used to
determine whether $\mathcal{U}(6i)\cap\mathcal{U}(6i+4)=\emptyset$, and thus
can be used to decide if $\varphi_{i}$ is a tautology or not: we let
$\mathcal{A}$ be a robust computable learner for $\mathcal{H}$ and let
$M\in\mathbb{N}$ be an upper bound for learning $\mathcal{H}$ with
$\epsilon=1/7<1/6$ and $\delta=1/3$. Running $\mathcal{A}$ on all sequences of
length $M$ over the set $\left\\{(6i,1),(6i+2,1),(6i+4,0)\right\\}$ and
evaluating the resulting predictors has to yield a $1/7$-close to optimal
hypothesis on two thirds of the sample. Thus taking the majority vote over the
predictions on $(6i+2)$ is a decider for whether $\varphi_{i}$ is a tautology
or not. ∎

###  B.2 Algorithm for the Decidable Representation in Theorem 16

Input: $x_{1},x_{2}\in\mathbb{N}$

Output: Whether $x_{2}\in\mathcal{U}(x_{1})$

if  _$x_{1}$ is odd_ then

if  _$x_{2}=x_{1}$_ then

output $x_{2}\in\mathcal{U}(x_{1})$

else

output $x_{2}\notin\mathcal{U}(x_{1})$

end if

else $\triangleright$ $x_{1}$ is even

if  _$x_{2}$ is odd_ then

run $T_{x_{1}}(x_{1})$ for at most $\frac{x_{2}-1}{2}$ steps

if  _$T_{x_{1}}(x_{1})$ halted_ then

output $x_{2}\in\mathcal{U}(x_{1})$

else $\triangleright$ $T_{x_{1}}(x_{1})$ is still running after
$\frac{x_{2}-1}{2}$ steps

output $x_{2}\notin\mathcal{U}(x_{1})$

end if

else $\triangleright$ $x_{2}$ is even

if  _$x_{2}=x_{1}$_ then

output $x_{2}\in\mathcal{U}(x_{1})$

else

output $x_{2}\notin\mathcal{U}(x_{1})$

end if

end if

end if

Algorithm 3 Program to decide whether $x_{2}\in\mathcal{U}(x_{1})$

###  B.3 Useful Lemmas for Theorem 16

######  Lemma 30.

There is no program that solves the problem $\mathsf{TwoHalt}$, that is, no
program with the following behavior: given a pair of indices of Turing
Machines $(i,j)$ as input:

  * •

if $T_{i}(i)$ halts and $T_{j}(j)$ loops, output $1$

  * •

if $T_{i}(i)$ loops and $T_{j}(j)$ halts, output $2$

  * •

if both $T_{i}(i)$ and $T_{j}(j)$ loop, halt and output $1$ or output $2$

  * •

if both $T_{i}(i)$ and $T_{j}(j)$ halt, output $1$ or output $2$ or loop

Before proving Lemma 30, let us state and prove the following result, which
will be used in the proof of Lemma 30.

######  Lemma 31.

For any two 2-place total computable functions $f_{1}$, $f_{2}$ there are
indices $c_{1},c_{2}$, such that $T_{c_{1}}\equiv T_{f_{1}(c_{1},c_{2})}$ and
$T_{c_{2}}\equiv T_{f_{2}(c_{1},c_{2})}$

###### Proof.

We start by defining the following Turing Machines:

$T_{a}(x_{1},x_{2},y_{1},y_{2})=\begin{cases}T_{T_{x_{1}}(x_{1},x_{2})}(y_{1},y_{2})&\text{
if }T_{x_{1}}(x_{1},x_{2})\text{ halts }\\\
\uparrow&\text{otherwise.}\end{cases}$

and

$T_{{b}}(x_{1},x_{2},y_{1},y_{2})=\begin{cases}T_{T_{x_{2}}(x_{1},x_{2})}(y_{1},y_{2})&\text{
if }T_{x_{2}}(x_{1},x_{2})\text{ halts }\\\
\uparrow&\text{otherwise.}\end{cases}$

By the $S^{n}_{m}$-Theorem, there exist total computable functions $h_{1}$ and
$h_{2}$, such that
$T_{a}(x_{1},x_{2},y_{1},y_{2})=T_{h_{1}(x_{1},x_{2})}(y_{1},y_{2})$ and
$T_{b}(x_{1},x_{2},y_{1},y_{2})=T_{h_{2}(x_{1},x_{2})}(y_{1},y_{2})$ hold for
all $x_{1},x_{2},y_{1},y_{2}$. Now let $e_{1}$ be the index of the Turing
machine that computes the function

$g_{1}(x_{1},x_{2})=f_{1}(h_{1}(x_{1},x_{2}),h_{2}(x_{1},x_{2}))\enspace,$

and $e_{2}$ be the index of the Turing machine that computes the function

$g_{2}(x_{1},x_{2})=f_{2}(h_{1}(x_{1},x_{2}),h_{2}(x_{1},x_{2}))\enspace.$

Since $g_{1}$ is a total computable function, we have
$T_{h_{1}(e_{1},e_{2})}{\equiv}T_{T_{e_{1}}(e_{1},e_{2})}$. By definition, we
have that $T_{e_{1}}(e_{1},e_{2})$ computes
$f_{1}(h_{1}(e_{1},e_{2}),h_{2}(e_{1},e_{2}))$. Thus
$T_{h_{1}(e_{1},e_{2})}{\equiv}T_{f_{1}(h_{1}(e_{1},e_{2}),h_{2}(e_{1},e_{2}))}$.
Furthermore, by the same argument, we have that
$T_{h_{2}(e_{1},e_{2})}{\equiv}T_{T_{e_{2}}(e_{1},e_{2})}{\equiv}T_{f_{2}(h_{1}(e_{1},e_{2}),h_{2}(e_{1},e_{2}))}$.
Thus if we choose $c_{1}=h_{1}(e_{1},e_{2})$ and $c_{2}=h_{2}(e_{1},e_{2})$,
we get $T_{c_{1}}\equiv T_{f_{1}(c_{1},c_{2})}$ and $T_{c_{2}}\equiv
T_{f_{2}(c_{1},c_{2})}$, as required. ∎

We are now ready to prove Lemma 30, which completes the result of this
section.

###### of Lemma 30.

By way of contradiction, let’s assume that there existed a program/Turing
Machine $T^{\mathsf{TwoHalt}}$ that solved the $\mathsf{TwoHalt}$ problem.
Recall that we had fixed an enumeration $(T_{i})_{i\in\mathbb{N}}$ of all
Turing Machines (or programs), and that we use the notaion $T(i)\downarrow$ to
indicate that a Turing Machine $T$ halts on input $i$ and $T(i)\uparrow$ to
indicate that $T$ loops on input $i$. We can now define two natural numbers
$l_{1}$ and $l_{2}$ as being the indices of Turing Machines $T_{l_{1}}$ and
$T_{l_{2}}$ which have the following behavior:

$T_{l_{1}}(i,j,z)=\begin{cases}1&\text{ if }z=0\\\ \uparrow&\text{ if
}z=i>0\text{ and }T^{\mathsf{TwoHalt}}(i,j)=1\\\ 1&\text{ if }z=j>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=1\\\ \uparrow&\text{ if }z=j>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ 2&\text{ if }z=i>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ \uparrow&\text{ otherwise }\end{cases}$

$T_{l_{2}}(i,j,z)=\begin{cases}2&\text{if }z=0\\\ \uparrow&\text{ if
}z=i>0\text{ and }T^{\mathsf{TwoHalt}}(i,j)=1\\\ 1&\text{ if }z=j>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=1\\\ \uparrow&\text{ if }z=j>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ 2&\text{ if }z=i>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ \uparrow&\text{ otherwise }\end{cases}$

Now by $S^{n}_{m}$-Theorem, there are total computable functions $f_{1}$ and
$f_{2}$ such that

$T_{f_{1}(i,j)}(z)=\begin{cases}1&\text{if }z=0\\\ \uparrow&\text{ if
}z=i>0\text{ and }T^{\mathsf{TwoHalt}}(i,j)=1\\\ 1&\text{ if }z=j>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=1\\\ \uparrow&\text{ if }z=j>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ 2&\text{ if }z=i>0\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ \uparrow&\text{ otherwise }\end{cases}$

and

$T_{f_{2}(i,j)}(z)=\begin{cases}2&\text{if }z=0\\\ \uparrow&\text{ if
}z=i\text{ and }T^{\mathsf{TwoHalt}}(i,j)=1\\\ 1&\text{ if }z=j\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=1\\\ \uparrow&\text{ if }z=j\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ 2&\text{ if }z=i\text{ and
}T^{\mathsf{TwoHalt}}(i,j)=2\\\ \uparrow&\text{ otherwise }\end{cases}$

Now, by Lemma 31, there are $c_{1},c_{2}>0$, such that
$T_{f_{1}(c_{1},c_{2})}\equiv T_{c_{1}}$ and $T_{f_{2}(c_{1},c_{2})}\equiv
T_{c_{2}}$. Recall that we use $T\equiv S$ to indicate that two Turing
Machines have the same behavior as functions.

Now let us look at $T^{\mathsf{TwoHalt}}({c_{1}},{c_{2}})$. There are three
options:

  * •

$T^{\mathsf{TwoHalt}}({c_{1}},{c_{2}})=1$. Then by definition
$T_{c_{1}}(c_{1})=T_{f_{1}(c_{1},c_{2})}(c_{1})\uparrow$ and
$T_{c_{2}}(c_{2})=T_{f_{2}(c_{1},c_{2})}(c_{2})\downarrow$. Thus
$T^{\mathsf{TwoHalt}}$ would output $1$, the wrong answer in a case where $2$,
the correct answer, was required.

  * •

$T^{\mathsf{TwoHalt}}({c_{1}},{c_{2}})=2$. Then by definition
$T_{c_{1}}(c_{1})=T_{f_{1}(c_{1},c_{2})}(c_{1})\downarrow$ and
$T_{c_{2}}(c_{2})=T_{f_{2}(c_{1},c_{2})}(c_{2})\uparrow$. Thus
$T^{\mathsf{TwoHalt}}$ would output $2$, the wrong answer in a case where $1$,
the correct answer, was required.

  * •

$T^{\mathsf{TwoHalt}}({c_{1}},{c_{2}})\uparrow$. Note that, by definition, the
Turing Machines $T_{f_{1}(c_{1},c_{2})}$ and $T_{f_{2}(c_{1},c_{2})}$ only
halt and produce an output if either their input was $0$ or the call to
$T^{\mathsf{TwoHalt}}$ inside their definition halts and produces an output.
Thus, for this case, we get
$T_{c_{1}}(c_{1})=T_{f_{1}(c_{1},c_{2})}(c_{1})\uparrow$ and
$T_{c_{2}}(c_{2})=T_{f_{2}(c_{1},c_{2})}(c_{2})\uparrow$. However, if both
$T_{c_{1}}(c_{1})$ and $T_{c_{2}}(c_{2})$ don’t halt, $T^{\mathsf{TwoHalt}}$
was supposed to halt. Thus $T^{\mathsf{TwoHalt}}$ also has the wrong behaviour
in this case.

In summary, the assumption that $T^{\mathsf{TwoHalt}}$ existed lead to a
contradiction in all cases and thus the problem $\mathsf{TwoHalt}$ does not
admit a solution. ∎

##  Appendix C Proofs from Section 4.2

###  C.1 Proof of Theorem 17

###### Proof.

Let the instance space be
$\mathcal{X}=(\mathbb{N}\times(\\{0\\}\cup\mathbb{N})$. Let
$(\varphi_{i})_{i\in\mathbb{N}}$ be an enumeration of formulas and
$(\pi_{j})_{j\in\mathbb{N}}$ be an enumeration of proofs. Let $(i,0)$,
represent the $i$-th formula and for any $i,j$ let $(i,j)$ represent the
$j$-th proof (independently of $i$). Let
$\mathcal{H}=\\{h_{a,b}\\}_{a,b\in\mathbb{N}\cup\\{0\\}}$, where

$h_{a,b}(i,j)=\begin{cases}1&\text{ if }i<a\text{ or }(i=a\text{ and }j\leq
b)\\\ 0&\text{ otherwise }\end{cases}\enspace.$

It is clear that $\mathsf{VC}(\mathcal{H})=1$ and that ERM is computably
implementable, so $\mathcal{H}$ is properly CPAC learnable.

We define the perturbation region as follows:

$\displaystyle\mathcal{U}(i,0)=\\{(i,0)\\}\cup\\{(i,j):\pi_{j}\text{ proves
}\varphi_{i}\\}\enspace,$
$\displaystyle\mathcal{U}(i,j)=\\{(i,0),(i,j)\\}\enspace,$

which is clearly DR, as to check whether $(i,j)\in\mathcal{U}((i,0))$ we can
check whether $\pi_{j}$ proves $\varphi_{i}$.

It is immediate to see that $\ell^{\mathcal{U}}$ is not computable for all
hypotheses in $\mathcal{H}$. Indeed, for every $i\in\mathbb{N}$, deciding
whether for the formula $\varphi_{i}$ is a tautology reduces to deciding
whether

$\ell^{\mathcal{U}}(h_{i,0},(i,0),1)=0\enspace.$

Now, it remains to show that $\mathcal{H}$ is properly $\mathcal{U}$-robustly
CPAC learnable. To this end, we will first show that
$\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})$ is finite, and second,
show that robust ERM is computable in the agnostic setting. By Fact 11, we
will have robust CPAC learnability.

To show $\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})<\infty$, we
consider the sets $\text{mar}^{\mathcal{U}}_{h_{a,b}}$, which we will denote
by $\text{mar}_{a,b}$ for brevity. First note that either $a=\infty$ or
$b=\infty$ implies that $\text{mar}_{a,b}=\emptyset$. Let $a,b\in\mathbb{N}$
and observe that only instances of the form $(a,j)$ can belong to
$\text{mar}_{a,b}$, and thus a shattered set cannot contain both $(a,j)$ and
$(a^{\prime},j^{\prime})$ where $a\neq a^{\prime}$. We distinguish two cases:

  * •

$\varphi_{a}$ is not a tautology: then $\text{mar}_{a,b}=\\{(a,0)\\}$,

  * •

$\varphi_{a}$ is a tautology: then
$\text{mar}_{a,b}=\\{(a,0)\\}\cup\\{(a,j)\;|\;j>b\wedge\pi_{j}\text{ proves
}\varphi_{a}\\}$.

From this, it is clear that
$\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})=1$.

Now, to show that robust ERM is computable, let
$S\subseteq\mathcal{X}\times\\{0,1\\}$ be an arbitrary labelled sample of size
$m$. For a fixed $i\in\mathbb{N}$ and $y\in\\{0,1\\}$, consider the subset
$S_{i}^{y}$ of $S$, consisting of “$i$-instances” with label $y$, i.e.,
$S_{i}^{y}:=\left\\{((i,j),y)\;|\;((i,j),y)\in S\right\\}$, and let
$S_{i}=S_{i}^{0}\cup S_{i}^{1}$. We can see that $h_{i,\infty}$ incurs robust
loss 1 on all the instances in $S_{i}^{0}$ and robust loss 0 on all the
instances in $S_{i}^{1}$. Furthermore, while every $h_{i,b}$ incurs robust
loss 1 on all $S_{i}^{0}$, it might also incur loss 1 on some instances
$S_{i}^{1}$. Finally, for $b\in\mathbb{N}$, on every instance in $S\setminus
S_{i}$, the hypotheses $h_{i,b}$ and $h_{i,\infty}$ incur the same robust
loss. Thus $h_{i,\infty}$ always “dominates” $h_{i,b}$ in the sense that
$\mathsf{R}_{\mathcal{U}}(h_{i,\infty};S)\leq\mathsf{R}_{\mathcal{U}}(h_{i,b};S)$.
We furthermore note that for every $i$, the loss of the function
$h_{i,\infty}$ can be evaluated on every point. Thus, performing RERM boils
down to comparing all candidate hypotheses of the form $h_{i,\infty}$, which
can be done computably. ∎

######  Remark 32.

In the above proof, let $\mathcal{H}^{\prime}\subset\mathcal{H}$ be the set of
all hypotheses in $\mathcal{H}$ with $b=\infty$, i.e.,
$\mathcal{H}^{\prime}=\left\\{h_{a,b}\in\mathcal{H}\;|\;b=\infty\right\\}$.
Then it is clear that, in the robust case, because of the definition of
$\mathcal{U}$, we can get away with only outputting hypotheses from
$\mathcal{H}^{\prime}$, no matter what the underlying distribution is, and
that for all hypotheses in $\mathcal{H}^{\prime}$ the robust loss is
computable. In general, for some hypothesis class $\mathcal{H}$, let
$\mathcal{H}^{\prime}$ be a class, such that (i) for every $h\in\mathcal{H}$,
there is $h^{\prime}\in\mathcal{H}^{\prime}$, such that for all
$(x,y)\in\mathcal{X}\times\mathcal{Y}$:
$\ell^{\mathcal{U}}(h^{\prime},x,y)\leq\ell^{\mathcal{U}}(h,x,y)$, (ii) the
robust loss of every $h^{\prime}\in\mathcal{H}^{\prime}$ is computably
evaluable. Then if $\mathcal{H}^{\prime}$ is realizable/agnostic robustly CPAC
learnable, so is $\mathcal{H}$. Furthermore, if
$\mathcal{H}^{\prime}\subset\mathcal{H}$ and $\mathcal{H}^{\prime}$ is
_proper_ realizable/agnostic robustly learnable, so is $\mathcal{H}$.

###  C.2 Proof of Theorem 18

###### Proof.

Let the instance space be $\mathcal{X}=\mathbb{N}\times\mathbb{N}$. Let the
hypothesis class be $\mathcal{H}=\\{h_{i,j}:i,j\in\mathbb{N}\\}$, where

$h_{i,j}(x)=\begin{cases}1&\text{ if }x=(i,k)\text{ with }k\leq j\\\ 0&\text{
otherwise }\end{cases}\enspace,$

i.e., $\mathcal{H}$ is the class which defines initial segments on the sets
$\\{(i,j)\\}_{j\in\mathbb{N}}$ for all $i\in\mathbb{N}$.

We define the perturbation types as follows.

$\displaystyle\mathcal{U}((i,0))$
$\displaystyle=\\{(i,0)\\}~{}\cup~{}\\{(i,k):T_{i}\text{ does not halt after
}k\text{ steps on the empty input }\\}\enspace,$
$\displaystyle\mathcal{U}((i,j))$
$\displaystyle=\begin{cases}\\{(i,j),(i,0)\\}&T_{i}\text{ does not halt after
}j\text{ steps on the empty input}\\\ \\{(i,j)\\}&\text{ otherwise.
}\end{cases}\enspace,$

We now prove properties (i)-(iii) from the theorem statement.

To prove (i), i.e., that $\mathcal{H}$ is properly CPAC learnable, it suffices
to observe that $\mathsf{VC}(\mathcal{H})=1$ and that ERM is easily
implementable (in both the agnostic and the realizable cases). In order to
verify $\mathsf{VC}(\mathcal{H})=1$, let us take to arbitrary distinct points
$(i_{1},j_{1})$ and $(i_{2},j_{2})$. If $i_{1}\neq i_{2}$, then the labelling
$((i_{1},j_{1}),1),((i_{2},j_{2}),1)$ cannot be achieved by $\mathcal{H}$. If
$i_{1}=i_{2}$, then $j_{1}\neq j_{2}$. Let us assume without loss of
generality that $j_{1}<j_{2}$. Then the labelling
$((i_{1},j_{1}),0),((i_{2},j_{2}),1)$ cannot be achieved. For computably
realizing ERM, we note that for any sample $S$ it is sufficient to do search
over the finite class $\mathcal{H}_{S}=\\{h_{i,j}:((i,j),1)\in
S\\}\cup\\{h_{0}^{S}\\}$, where $h_{0}^{S}=h_{i,0}$, with $i$ being the
smallest index for which there is no $((i,j),1)\in S$. Searching over these
finitely many candidate hypotheses can be done computably.

To prove (ii), i.e., that $\mathcal{H}$ is properly $\mathcal{U}$-robustly
learnable, we show that the VC dimension
$\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})$ of the margin class is
finite. To this end, we identify the sets
$\text{mar}^{\mathcal{U}}_{\mathcal{H}}$ and distinguish two cases:

  * •

$T_{i}$ does not halt after $j$ steps on the empty input: then

$\text{mar}_{h_{i,j}}^{\mathcal{U}}=\\{(i,0)\\}\cup\\{(i,k):k>j\text{ and
}T_{i}\text{ does not halt after }k\text{ steps}\\}\enspace,$

  * •

$T_{i}$ halts on the empty input after $j$ steps: then
$\text{mar}_{h_{i,j}}^{\mathcal{U}}=\emptyset$.

We now argue that $\mathsf{VC}(\mathcal{H}_{\text{mar}}^{\mathcal{U}})=1$. To
this end, let $x_{1}=(i_{1},j_{1})$ and $x_{2}=(i_{2},j_{2})$ be two distinct
domain points, and note that, to be shattered, we need $i_{1}=i_{2}$, as
otherwise there is no
$\text{mar}_{h}^{\mathcal{U}}\in\mathcal{H}_{\text{mar}}^{\mathcal{U}}$ with
$x_{1},x_{2}\in\text{mar}_{h}^{\mathcal{U}}$. Now, without loss of generality,
let $j_{1}<j_{2}$. There are three cases:

  * •

If $T_{i_{1}}$ halts after $j_{2}$ steps or less, then there is no
$\text{mar}_{h}^{\mathcal{U}}\in\mathcal{H}_{\text{mar}}^{\mathcal{U}}$ with
$x_{2}\in\text{mar}_{h}^{\mathcal{U}}$.

  * •

If $T_{i_{1}}$ does not halt after $j_{2}$ and $j_{1}\neq 0$, then there is no
$\text{mar}_{h}^{\mathcal{U}}\in\mathcal{H}_{\text{mar}}^{\mathcal{U}}$ with
$x_{1}\in\text{mar}_{h}^{\mathcal{U}}$ and
$x_{2}\notin\text{mar}_{h}^{\mathcal{U}}$.

  * •

If $T_{i_{1}}$ does not halt after $j_{2}$ steps and $j_{1}=0$, then there is
no $\text{mar}_{h}^{\mathcal{U}}\in\mathcal{H}_{\text{mar}}^{\mathcal{U}}$
with $x_{2}\in\text{mar}_{h}^{\mathcal{U}}$ and
$x_{1}\notin\text{mar}_{h}^{\mathcal{U}}$.

To prove (iii), i.e., that the pointwise robust loss is computably evaluable,
let $h_{i,j}\in\mathcal{H}$, $x\in\mathcal{X}$, $y\in\mathcal{Y}$ be
arbitrary, and consider the following procedure:

  * •

If $x=(i,0)$ and $y=1$, we have that $\ell^{\mathcal{U}}(h_{i,j},x,y)=1$ if
and only if $(i,j+1)\in\mathcal{U}((i,0))$, which can be determined by running
$T_{i}$ for $j+1$ steps and checking whether it halts.

  * •

If $x=(i,0)$ and $y=0$, then $\ell^{\mathcal{U}}(h_{i,j},x,y)=1$.

  * •

If $x=(i,k)$ with $k>0$ and $y=1$, check whether $k\leq j$. If so,
$\ell^{\mathcal{U}}(h_{i,j},x,y)=0$, otherwise
$\ell^{\mathcal{U}}(h_{i,j},x,y)=1$.

  * •

If $x=(i,k)$ with $k>0$ and $y=0$, check whether $k\leq j$. If so,
$\ell^{\mathcal{U}}(h_{i,j},x,y)=1$. Otherwise
$\ell^{\mathcal{U}}(h_{i,j},x,y)=0$ if and only if
$(i,0)\notin\mathcal{U}((i,j))$, which can be checked by running $T_{i}$ for
$k$ many steps and checking whether it halts.

  * •

If $x=(i^{\prime},k)$ with $i^{\prime}\neq i$, then
$\ell^{\mathcal{U}}(h_{i,j},x,y)=y$.

Finally, we show that there is no strong realizable
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$-oracle and that $\mathcal{H}$ is
not properly agnostically $\mathcal{U}$-robustly CPAC learnable. We first show
the non-existence of a computable strong realizable
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$-oracle or agnostic
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$-oracle We prove this with a
reduction from the Halting problem: for all $i\in\mathbb{N}$, a strongly
realizable $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$ oracle (or agnostic
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$-oracle) ran on the single labelled
instance $((i,0),1)$ outputs a hypothesis $h$ with robust loss
$\ell^{\mathcal{U}}(h,(i,0),1)=0$ if and only if the Turing Machine $T_{i}$
halts on the empty input. As a side note, we observe that a weak realizable
$\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$-oracle does exist for this
construction.

We show that $\mathcal{H}$ is not agnostically properly $\mathcal{U}$-robustly
CPAC learnable in a similar way. Assume there was an agnostically properly
$\mathcal{U}$-robustly CPAC learner $\mathcal{A}$ with sample complexity
function $m$. For all $i\in\mathbb{N}$, define $D_{i}$ as $D_{i}((i,0),1)=1$.
Let $m=m(1/8,1/8)$. By the learning guarantee of $\mathcal{A}$, we have that
$\mathcal{A}(S)=h\in\mathcal{H}$ with
$\mathcal{L}_{D_{i}}(h)\leq\underset{h\in\mathcal{H}}{\inf}\mathsf{R}(h;D_{i})~{}+~{}\frac{1}{8}$
with probablility $7/8$ over $S\sim D_{i}^{m}$. Observe that
$\underset{h\in\mathcal{H}}{\inf}\mathsf{R}(h;D_{i})=0$ if and only if $T_{i}$
halts on the empty input, and otherwise
$\underset{h\in\mathcal{H}}{\inf}\mathsf{R}(h;D_{i})=1$. We note that
$S^{\prime}=(((i,0),1),\dots,((i,0),1))$, where $|S^{\prime}|=m$ is the only
possible sample drawn from $D_{i}$. Thus we have
$\mathcal{A}(S^{\prime})=h^{\prime}\in\mathcal{H}$ with
$\mathcal{L}_{D_{i}}(h^{\prime})\leq 1/8$ if and only if $T_{i}$ halts on the
empty input. Furthermore,
$\mathcal{L}_{D_{i}}(h^{\prime})=\ell^{\mathcal{U}}(h^{\prime},(i,0),1)\in\\{0,1\\}$
for all $h^{\prime}\in\mathcal{H}$. Thus we have
$\mathcal{L}_{D_{i}}(\mathcal{A}(S^{\prime}),(i,0),1)=\ell^{\mathcal{U}}(\mathcal{A}(S^{\prime}),(i,0),1)=0$
if and only if $T_{i}$ halts on the empty input. As established above, the
robust loss $\ell^{\mathcal{U}}$ can be computably evaluated on any
$h\in\mathcal{H}$. Thus a proper agnostic learner $\mathcal{A}$ yields a
computable procedure for solving the Halting problem, which is a contradiction
to the computable undedicability of the Halting problem. Thus $\mathcal{H}$ is
not agnostically properly $\mathcal{U}$-robustly CPAC learnable. ∎

###  C.3 Proof of Proposition 19

###### Proof.

Let $S=((x_{1},y_{1}),\dots,(x_{k},y_{k}))$ be an input sample for
$\mathsf{RERM}^{\mathcal{U}}_{\mathcal{H}}$, and let $\mathcal{A}$ be the
robust SCPAC learning algorithm with computable sample complexity function
$m_{\mathcal{H},\mathcal{U}}$. Consider the uniform distribution $D_{S}$ over
$S$. Let $m\geq m_{\mathcal{H},\mathcal{U}}(\frac{1}{k+1},1/7)$, which is
computable by the SCPAC guarantee. There are exactly $k^{m}$ different
possible samples $S_{1},\dots S_{k^{m}}$ of size $m$ that can be drawn from
$D_{S}$, all of which being equally likely. Using the proper learner
$\mathcal{A}$ on all samples $S_{i}$, we can generate the class
$\hat{\mathcal{H}}=\\{\mathcal{A}(S_{i}):i\in[k^{m}]\\}$. By the robust
learning guarantee, we know that at least 7/8 of the hypotheses in
$\hat{\mathcal{H}}$ are successful hypotheses, i.e., hypotheses within robust
risk $1/(k+1)$ of the optimal one. Furthermore, since
$\epsilon=\frac{1}{k+1}$, any successful hypothesis must have optimal loss on
$S$ (as any error on a sample point would incur loss $\frac{1}{k}$). It now
suffices to use $\ell^{\mathcal{U}}$ on $\hat{\mathcal{H}}$ and return any one
of the hypotheses with minimal empirical robust risk on $S$. Note that, for
the robust realizable setting (the second case in the theorem statement), we
only get a weak realizable oracle $\mathsf{RERM}_{\mathcal{H}}^{\mathcal{U}}$,
as if the sample is not robustly realizable, we don’t have any guarantees on
$\mathcal{A}$’s behaviour. ∎

##  Appendix D Proofs from Section 5

###  D.1 Proof of Lemma 23

###### Proof.

The idea is similar to the standard No-Free-Lunch Theorem. We let $m$ and
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$ as in the theorem
statement, meaning that for all $i$,
$\mathcal{U}(z_{i}^{0})\cap\mathcal{U}(z_{i}^{1})\neq\emptyset$ and for all
$i\neq j$ the regions $\mathcal{U}(z_{i}^{1})$ and $\mathcal{U}(z_{j}^{0})$
are disjoint. We now look at a robust labelling $y\in\\{0,1\\}^{2m}$. There
are $T=2^{2m}$ such labellings, and for each $j\in[T]$ associated with
labelling $y^{(j)}\in\\{0,1\\}^{2m}$, there exists a function $f_{j}$ such
that for all $i\in[2m]$, for all
$z^{\prime}\in\mathcal{U}(z_{i}^{y_{i}^{(j)}})$ we have that
$f_{j}(z^{\prime})=y_{i}^{(j)}$. Namely, for $i\in[2m]$, the label
$y_{i}^{(j)}$ dictates which of $z_{i}^{0}$ or $z_{i}^{1}$ will have its
perturbation region constantly (and thus robustly) labelled. For each function
$f_{j}$ and its robust labelling $y^{(j)}$, we define the distribution $D_{j}$
as follows:

$D_{j}((z,y))=\begin{cases}1/2m&\text{if $y=y_{i}^{(j)}$ and $z=z_{i}^{y}$ for
some $i\in[2m]$}\\\ 0&\text{otherwise}\end{cases}\enspace.$

It is easy to check that $\mathsf{R}_{\mathcal{U}}(f_{j};D_{j})=0$.

Let $X=\\{x_{i}\\}_{i=1}^{m}$ be some $\mathcal{U}$-robustly shatterable set
corresponding to the set of pairs
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$, that is
$x_{i}\in\mathcal{U}(z_{i}^{0})\cap\mathcal{U}(z_{i}^{1})$ for each
$i\in[2m]$. Now note any hypothesis $h:\mathcal{X}\to\\{0,1\\}$ (that the
learner may output) has to assign labels to the the points in the shatterable
set $X$ and $h(x_{i})=1$ implies $\ell^{\mathcal{U}}(h,z_{i}^{0})=1$ while
$h(x_{i})=0$ implies $\ell^{\mathcal{U}}(h,z_{i}^{1})=1$. Thus each hypothesis
incurs robust loss on at least one of the members $\\{z_{i}^{0},z_{i}^{1}\\}$
of each pair, and such a member can be deduced from observing $h(x_{i})$. Now
the remaining argument to show that there exist $f_{j},D_{j}$ such that the
conditions of the theorem statement are met is exactly as in the proof of the
standard No-Free-Lunch theorem (see, e.g., Theorem 5.1 in Shalev-Shwartz and
Ben-David (2014) for details). We note that the argument there implies that
the high expected loss of the learner’s output is witnessed by its behaviours
on the shatterable set $X$. Namely, there exists $f_{j},D_{j}$ such that

$\displaystyle\underset{{S\sim
D_{j}^{m}}}{\mathbb{E}}\left[\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);D_{j})\right]=\frac{1}{k}\sum_{l=1}^{k}\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S^{j}_{l});D_{j})$
$\displaystyle=\frac{1}{k}\sum_{l=1}^{k}\frac{1}{2m}\sum_{i=1}^{2m}\ell^{\mathcal{U}}\left(\mathcal{A}(S^{j}_{l}),z_{i}^{(j)},y_{i}^{(j)}\right)\enspace,$
$\displaystyle\geq\frac{1}{k}\sum_{l=1}^{k}\frac{1}{2m}\sum_{i=1}^{2m}\mathbbm{1}\left[{\mathcal{A}(S^{j}_{l})(x_{i})\neq
y_{i}^{(j)}}\right]\geq 1/8$

where $k=(2m)^{m}$ is the number of possible sequences of length $m$ drawn
from
$\text{supp}(D_{j}):=\left\\{(z_{i}^{(j)},y_{i}^{(j)})\right\\}_{i=1}^{2m}$,
and where we have denoted by $S^{j}_{l}$ the $l$-th such sequence. ∎

###  D.2 Proof of Theorem 26

###### Proof.

First note that, if the perturbation type $\mathcal{U}$ is such that there is
an upper bound $M$ on the maximal number of pairs
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$ admitting a robustly
shatterable set, then the computable robust shattering dimension is vacuously
finite for any hypothesis class $\mathcal{H}$. Otherwise, let $\mathcal{A}$ be
a $\mathcal{U}$-robust CPAC learner for $\mathcal{H}$ with sample complexity
function $m(\epsilon,\delta)$. Then, fixing $\epsilon=1/8$ and $\delta=1/7$,
we have that for all distributions on $\mathcal{X}\times\\{0,1\\}$, for any
sample of size $m:=m(1/8,1/7)$

$\underset{{S\sim
D^{m}}}{\Pr}\left(\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);D)\geq\underset{h\in\mathcal{H}}{\min}\;\mathsf{R}_{\mathcal{U}}(h;D)+1/8\right)<1/7\enspace.$
(2)

Now, let $Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$ admit a
robustly shatterable set $X$, and note that, as explained in the proof of
Lemma 25, we can computably find such a set $X$. Note that $\mathcal{H}$ and
$\mathcal{U}$ satisfying the conditions of the theorem statement imply, by
Lemma 25, that we can find a distribution $D$ on $Z\times\\{0,1\\}$ such that

$\underset{{S\sim
D^{m}}}{\Pr}\left(\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);D)\geq
1/8\right)\geq 1/7\enspace,$ (3)

and whose support is on some $\left\\{z_{i}^{y_{i}}\right\\}_{i=1}^{2m}$ for
$y\in\\{0,1\\}^{2m}$. This support induces a labelling $y$ on $X$ that is not
robustly achievable with respect to $Z$ by any $h\in\mathcal{H}$, as we would
otherwise have $\underset{h\in\mathcal{H}}{\min}\;L_{D}^{\mathcal{U}}(h)=0$,
implying that Equation 3 and $\underset{{S\sim
D^{m}}}{\Pr}\left(\mathsf{R}_{\mathcal{U}}(\mathcal{A}(S);D)\geq
1/8\right)<1/7$ must hold simultaneously, a contradiction. ∎

##  Appendix E Remarks on the robust shatterability in the impossibility
results from Section 4

We now comment on the robust shatterability in the impossibility results from
Section 4. On the one hand, the perturbation type in Theorem 16 does not allow
for sets of arbitrary size to admit a robustly shatterable set. Indeed, any
sequence of halting Turing machines (which are associated with the only
instances in $\mathbb{N}$ that have a strict inequality
$k\subset\mathcal{U}(k)$) will have an ordering such that their perturbation
regions form an ascending chain, which makes the condition $i\neq
j\implies\mathcal{U}(z_{i}^{1})\cap\mathcal{U}(z_{j}^{0})=\emptyset$
unsatisfiable for any candidate set
$Z=\left\\{(z_{i}^{0},z_{i}^{1})\right\\}_{i=1}^{2m}$. On the other hand, the
perturbation type in Theorem 15 satisfies the robust shatterability
requirement. Indeed, we will add the mild assumption that each proof proves at
most one formula. This implies that for each $i\neq i^{\prime}$,
$\mathcal{U}(6i+4)$ and $\mathcal{U}(6i^{\prime}+4)$ are disjoint, thus,
letting $T=(\varphi_{i_{k}})_{k\in\mathbb{N}}$ be an enumeration of the
tautologies, the set $Z=\\{(6i_{k}+2,6i_{k}+4)\\}_{k\in\mathbb{N}}$ admits the
robustly shatterable set $X=\\{6i_{k}+2\\}_{k\in\mathbb{N}}$, while the sets
$\mathcal{U}(6i+4)$ may be infinite.