# Realizable Learning is All You Need

Max Hopkins Department of Computer Science and Engineering, UCSD, California,
CA 92092. Email<EMAIL_ADDRESS>Supported by NSF Award DGE-1650112.
Daniel M. Kane Department of Computer Science and Engineering / Department of
Mathematics, UCSD, California, CA 92092. Email<EMAIL_ADDRESS>Supported
by NSF Award CCF-1553288 (CAREER) and a Sloan Research Fellowship. Shachar
Lovett Department of Computer Science and Engineering, UCSD, California, CA
92092. Email<EMAIL_ADDRESS>Supported by NSF Award CCF-1909634. Gaurav
Mahajan Department of Computer Science and Engineering, UCSD, California, CA
92092. Email<EMAIL_ADDRESS>
###### Abstract

The equivalence of realizable and agnostic learnability is a fundamental
phenomenon in learning theory. With variants ranging from classical settings
like PAC learning and regression to recent trends such as adversarially robust
learning, it’s surprising that we still lack a unified theory; traditional
proofs of the equivalence tend to be disparate, and rely on strong model-
specific assumptions like uniform convergence and sample compression.

In this work, we give the first model-independent framework explaining the
equivalence of realizable and agnostic learnability: a three-line blackbox
reduction that simplifies, unifies, and extends our understanding across a
wide variety of settings. This includes models with no known characterization
of learnability such as learning with arbitrary distributional assumptions and
more general loss functions, as well as a host of other popular settings such
as robust learning, partial learning, fair learning, and the statistical query
model.

More generally, we argue that the equivalence of realizable and agnostic
learning is actually a special case of a broader phenomenon we call property
generalization: any desirable property of a learning algorithm (e.g. noise
tolerance, privacy, stability) that can be satisfied over finite hypothesis
classes extends (possibly in some variation) to any learnable hypothesis
class.

###### Contents

  1. 1 Introduction
  2. 2 Contributions
    1. 2.1 The Base Reduction
    2. 2.2 Beyond Binary Classification
      1. 2.2.1 Generalizing Labels and Loss
      2. 2.2.2 Beyond the PAC Setting
    3. 2.3 Property Generalization
    4. 2.4 Proof Overview: Modification Archetypes
  3. 3 Related Work
    1. 3.1 Beyond Binary Classification
    2. 3.2 Semi-supervised, Active, and Semi-Private Learning
    3. 3.3 Non-Uniform Covering and Probabilistic Representations
  4. 4 Preliminaries
    1. 4.1 PAC-Learning
    2. 4.2 Learning Under Distribution Families
  5. 5 The Core Reduction: Agnostic to Realizable Learning
  6. 6 Four Modification Archetypes
    1. 6.1 Discretization: Infinite Label Classes
    2. 6.2 Sub-sampling: Malicious Noise
    3. 6.3 Replacing ERM: Semi-Private Learning
    4. 6.4 Changing the Base Model: Covariate Shift
  7. A Doubly Bounded Loss
  8. B Robust Learning
  9. C Partial PAC-Learning
  10. D Uniform Stability
  11. E Statistical Query Model
  12. F Fairness
  13. G Notions of Coverability

##  1 Introduction

The equivalence of realizable and agnostic learnability in Valiant’s Probably
Approximately Correct (PAC) model [1] is one of the best known results in
learning theory, and numbers among its most surprising. Given a set $X$ and a
family of binary classifiers $H$, the result states that the ability to learn
a classifier $h\in H$ from examples of the form $(x,h(x))$ is in fact
sufficient for something much stronger: given samples from any distribution
$D$ over $X\times\\{0,1\\}$, it is possible to learn the best approximation to
$D$ in $H$. This surprising equivalence stems from a classical result of
Vapnik and Chervonenkis (VC) [2], and independently Blumer, Ehrenfeucht,
Haussler, and Warmuth (BEHW) [3] and Haussler [4], who equate both the former
model (known as realizable learning) and the latter model (known as agnostic
learning) to a strong property of pairs $(X,H)$ called uniform
convergence.111Uniform convergence promises that a large enough sample gives a
good approximation for loss of every $h\in H$ simultaneously.

VC, BEHW, and Haussler’s result was certainly a breakthrough in its own right,
but its proof technique is too indirect to reveal any deeper connections
between realizable and agnostic learning beyond the PAC setting. Further,
recent years have seen both theory and practice shift away not only from this
original formalization, but more generally from the “uniform convergence
equals learnability” paradigm, often in favor of distributional or data-
dependent assumptions like margin that are more applicable to the real world.
The inability of VC, BEHW, and Haussler’s proof technique to generalize to
such scenarios raises a fundamental question: is the equivalence of realizable
and agnostic learning a fundamental property of learnability, or simply a
happy coincidence derived from the original PAC framework?

In the 30 years since these works, a mountain of evidence has amassed in favor
of the former: almost every reasonable variant of learning shares some sort of
similar equivalence. This includes a long list of popular settings such as
regression [5], distribution-dependent learning [6], multi-class learning [7],
robust learning [8], online learning [9], private learning [10, 11], and
partial learning [12, 13]. What’s more, the uniform convergence paradigm fails
miserably in most of these models. In the distribution-dependent model, for
instance, it is easy to build classes which are trivially learnable (even with
one sample!) but completely fail to satisfy uniform convergence [6]. On the
other hand, models such as private learning give well-known examples where
uniform convergence fails to imply learnability [14]. In spite of this, we are
really no closer today to a general understanding of this phenomenon than we
were in the early 90s. Much like Vapnik and Chervonenkis [2], Blumer,
Ehrenfeucht, Haussler, and Warmuth [3], and Haussler’s [4] proofs, the above
works often use indirect methods and tend to rely on powerful model-dependent
assumptions.

In this work, we aim to offer a generic, unifying theory by way of the first
direct reduction from agnostic to realizable learning. Unlike any previous
work, our reduction is blackbox, relies on no additional assumptions, and,
perhaps most importantly, is incredibly simple. In fact, the basic algorithm
can be stated in three lines.

Input: Realizable PAC-Learner $\mathcal{A}$, Unlabeled Sample Oracle
$\mathcal{O}_{U}$, Labeled Sample Oracle $\mathcal{O}_{L}$

Algorithm:

  1. 1.

Draw an unlabeled sample $S_{U}\sim\mathcal{O}_{U}$, and labeled sample
$S_{L}\sim\mathcal{O}_{L}$.

  2. 2.

Run $\mathcal{A}$ over all possible labelings of $S_{U}$ to get:

$C(S_{U})\coloneqq\\{\mathcal{A}(S_{U},h(S_{U}))\leavevmode\nobreak\
|\leavevmode\nobreak\ h\in H|_{S_{U}}\\}.$

  3. 3.

Return the hypothesis in $C(S_{U})$ with lowest empirical error over $S_{L}$.

Algorithm 1 Agnostic to Realizable Reduction

This basic reduction simplifies and unifies classic results such as VC [2],
BEHW [3], and Haussler’s [4] distribution-free equivalence and Benedek and
Itai’s [6] analogous result in the distribution-dependent setting,222Formally
Benedek and Itai only consider random classification noise, but it is clear
that their analysis extends to the agnostic model. with no loss in sample-
complexity.333In the distribution-free setting, the resulting sample
complexity is optimal up to a log factor, though it was later discovered this
could be removed through a more complicated chaining technique [15]. Moreover,
because Algorithm 1 doesn’t rely on model-dependent properties like uniform
convergence, it extends to learning regimes without known characterizations.
One such example is the notoriously difficult distribution-family model, in
which the adversary is given a restricted family of distributions
$\mathscr{D}$ along with the pair $(X,H)$. While no characterization of
learnability is known in this model, Algorithm 1 can still be used to show
that the realizable and agnostic settings are equivalent.

Unfortunately, while Algorithm 1 does avoid any significant blowup in sample
complexity, it is inherently computationally inefficient. In fact, this is
necessary unless $P=NP$. There are many basic classes (e.g. halfspaces) which
are easy to learn in the realizable model, but NP-hard in the agnostic setting
(see e.g. [16]).444We note this is only known to hold in the proper setting.
This does not lose significant generality since our reduction is inherently
proper, and even an improper reduction would break standard cryptographic
hardness assumptions such as learning parity with noise. As a result, we focus
in this work only on information theoretic considerations, though building
computationally efficient reductions under restricted settings remains a very
interesting avenue of research.

The core of Algorithm 1 lies in an equivalence between PAC learning and a new
form of randomized covering of independent interest we call a non-uniform
cover. In contrast to more classical notions, a non-uniform cover is a
distribution over subsets of hypotheses that covers any fixed hypothesis in
the class with high probability, but may fail to cover all hypotheses
simultaneously. The connection between supervised learning and non-uniform
covering is inherent in Algorithm 1, where Steps 1 and 2 turn the realizable
learner $\mathcal{A}$ into a non-uniform cover $C(S_{U})$, and Step 3 uses the
cover to perform agnostic learning. At a high level, this process works
because the adversary does not see the randomness inherent to Steps 1 and 2,
and therefore cannot detect or exploit which hypotheses in the class will fail
to be well-estimated in the process.

In fact, this connection has many broader implications within the theory of
supervised learning. For one, the method is not inherently restricted to the
agnostic setting. Algorithm 1 achieves agnostic learning for general classes
by applying an agnostic learner for finite classes in Step 3; replacing this
with learners satisfying other properties (e.g. the exponential mechanism for
privacy) leads to other families of reductions to the realizable setting. At a
high level, this can be summarized by the following informal ‘guiding
principle’:

######  Guiding Principle (Property Generalization).

If there is a (sample-efficient) algorithm with property $P$ over finite
classes, then Algorithm 1 gives a (sample-efficient) learner with property $P$
over any ‘learnable’ class.

We stress that the above is a guide, not a theorem, and indeed often requires
modification or weakening of the desired property for a given application. For
instance, when Step 3 is replaced with a private algorithm, the result is a
semi-private learner for general classes, a weakened model allowing the use of
a small amount of public unlabeled data [17, 18].

Algorithm 1 also provides a unified framework for many settings beyond the
PAC-model. This includes basic extensions such as general loss
functions555Over infinite label spaces, we will require some weak assumptions
on the loss. and the distribution-family model, but also more involved
modifications such as partial learning, robust learning, or even the
statistical query model. Moreover, in some of these settings removing reliance
on setting-specific assumptions like uniform convergence actually
quantitatively improves the sample complexity; such is the case for the semi-
private model, where we use this fact to achieve information-theoretically
optimal unlabeled sample complexity for the first time.

Finally, we note there are a few settings where Algorithm 1 runs into issues,
especially discrete infinite settings such as infinite multi-class
classification and properties such as privacy that require more careful data
handling. We leave the extension of our method to these settings as an
intriguing open problem.

##  2 Contributions

In this section we overview our main contributions: Algorithm 1 and its
analysis (including the introduction of non-uniform covers), extensions to
more general label spaces and loss functions, and property generalization
beyond the agnostic setting. Finally, we discuss the main modifications we
make to Algorithm 1 to handle such extensions.

###  2.1 The Base Reduction

Since all of our results are derived from variants of Algorithm 1, it is
instructive to start by considering its basic analysis in our simplest non-
trivial setting: distribution-family classification. This framework captures
learnability with arbitrary distributional assumptions, a well-studied
relaxation of PAC learning in practice where worst-case distributional
assumptions are often too strong, and encompasses both the distribution-free
and distribution-dependent PAC settings. Unlike these models, however, we
cannot assume uniform convergence in the distribution family setting, due to a
classical example of Benedek and Itai [6].

######  Proposition 2.1 (Benedek and Itai [6]).

There exists a PAC-learnable class $(D,X,H)$ over binary labels and
classification loss without the uniform convergence property.

###### Proof.

Let $X=[0,1]$, $D$ be the uniform distribution over $X$, $Y=\\{0,1\\}$, and
$H$ consist of all indicator functions for finite sets $S\subset X$, as well
as for $X$ itself. It is not hard to see that $(D,X,H)$ is realizably PAC-
learnable by the following scheme in only a single sample: if the learner
draws a sample labeled $1$, output the all $1$’s function. Otherwise, output
all $0$s. When the adversary has chosen a finite set, with probability $1$ the
learner draws a sample labeled $0$, and outputs a hypothesis with $0$ error
(since the finite set has measure $0$). If the adversary chooses the all $1$’s
function, the learner will always output the all $1$’s function.

On the other hand, it is clear that when the adversary chooses the all $1$’s
function, no matter how many samples the learner draws, there will exist a
hypothesis in the class that is poorly approximated by the sample. Namely the
hypothesis whose support is given by the support of the sample itself has
empirical measure $1$, but true measure $0$. As a result, this class fails to
have the uniform convergence property despite its learnability. ∎

This simple example rules out many classical techniques in supervised
learning, including uniform convergence based reductions (e.g. [19, 17, 18]).
Furthermore, the distribution-family setting has no known combinatorial
characterization of learnability [20] and, due to its probabilistic nature and
shared characteristics with EMX learnability, it seems likely the model may be
independent of ZFC entirely [21]. This means we also cannot hope to take the
traditional approach [2, 6, 4, 5] of proving equivalence of realizable and
agnostic models by simultaneous characterization.

With this motivation in mind, let’s define distribution-family learning more
formally. Let $X$ be a set (called the instance space), $Y=\\{0,1\\}$ the set
of binary labels, $\mathscr{D}$ a family of distributions over $X$, and
$H=\\{h:X\to Y\\}$ a family of binary classifiers. A tuple $(\mathscr{D},X,H)$
is said to be realizably learnable if there exists an algorithm666Note that
$\mathcal{A}$ could be deterministic or randomized. This distinction has no
effect on any of the arguments in this work. $\mathcal{A}$ and a function
$n(\varepsilon,\delta)$ such that for every $\varepsilon,\delta>0$, every
choice of distribution $D\in\mathscr{D}$, and every hypothesis $h\in H$,
$\mathcal{A}$ outputs a good classifier with high probability on samples of
size $n(\varepsilon,\delta)$:

$\Pr_{S\sim D^{n(\varepsilon,\delta)}}[\text{err}_{D\times
h}(\mathcal{A}(S,h(S)))\leq\varepsilon]\geq 1-\delta,$

where $\text{err}_{D\times h}(\cdot)$ is commonly called the error or risk of
$h$:

$err_{D\times h}(h^{\prime})=\underset{x\sim D}{\Pr}[h^{\prime}(x)\neq h(x)].$

Likewise, a tuple $(\mathscr{D},X,H)$ is said to be agnostically learnable if
there exists an algorithm $\mathcal{A}$ which for every distribution $D$ over
$X\times Y$ whose marginal $D_{X}\in\mathscr{D}$ outputs $h^{\prime}$ close to
the best hypothesis in $H$ with probability $1-\delta$:

$\Pr_{S\sim D^{n(\varepsilon,\delta)}}[\text{err}_{D}(\mathcal{A}(S))\leq
OPT+\varepsilon]\geq 1-\delta,$

where $OPT=\inf_{h\in H}\\{\text{err}_{D}(h)\\}$ is the error of the best
hypothesis in the class777We will assume throughout for simplicity that the
infinum is realized by some element in the class, but this assumption can be
removed with essentially no changes to any arguments. and the risk
$\text{err}_{D}(\cdot)$ is similarly defined:

$\text{err}_{D}(h^{\prime})=\underset{(x,y)\sim D}{\Pr}[h^{\prime}(x)\neq y].$

With this in mind, we can now state the most basic application of Algorithm 1:
the equivalence of agnostic and realizable learning for distribution-family
classification.

######  Theorem 2.2 (Realizable $\to$ Agnostic (Distribution-Family
Classification)).

Let $\mathcal{A}$ be a realizable learner for $(\mathscr{D},X,H)$ using
$n(\varepsilon,\delta)$ samples. Then Algorithm 1 is an agnostic learner for
$(\mathscr{D},X,H)$ using:

$m_{U}(\varepsilon,\delta)\leq n(\varepsilon/2,\delta/2)$

unlabeled samples, and

$m_{L}(\varepsilon,\delta)\leq
O\left(\frac{n(\varepsilon/2,\delta/2)+\log(1/\delta)}{\varepsilon^{2}}\right)$

labeled samples. Moreover if $(X,H)$ has finite VC dimension $d$, Algorithm 1
needs only

$m_{L}(\varepsilon,\delta)\leq
O\left(\frac{d\log\left(1/\varepsilon\right)+\log(1/\delta)}{\varepsilon^{2}}\right)$

labeled samples.

Along with its novelty in the distribution-family setting (where no such
equivalence was known), it is worth noting that in the distribution-free
setting, Theorem 2.2 actually recovers the same sample complexity bound as
standard analysis of uniform convergence.888Though it should be noted that the
additional $\log(1/\varepsilon)$ factor can be removed by a more complicated
chaining argument [15]. We also note that while unlabeled sample complexity is
not usually considered separately from labeled complexity in the PAC setting,
this will become a useful distinction in semi-supervised extensions considered
later in the work. As such, it is instructive to keep the complexities
separate for the time being.

With this out of the way, let’s prove Theorem 2.2. The analysis breaks
naturally into two parts, corresponding respectively to Step 2 and Step 3 of
Algorithm 1. In the first part, we’ll show that $C(S_{U})$, the set of outputs
corresponding to running the realizable learner $\mathcal{A}$ across all
possible labelings of the unlabeled sample $S_{U}$, is in some sense a “good
approximation” of the class $H$. More formally, the crucial observation is
that for any choice of the adversary’s distribution, $C(S_{U})$ will (almost)
always contain a hypothesis close to the optimal solution.

######  Claim 2.3.

For any distribution $D$ over $X\times Y$ whose marginal
$D_{X}\in\mathscr{D}$, with probability $1-\delta/2$, there exists
$h^{\prime}\in C(S_{U})$ which is within $\varepsilon/2$ of the optimal risk:

$err_{D}(h^{\prime})\leq OPT+\varepsilon/2.$

Once we have this claim, the second step is to show that Step 3, an empirical
risk minimization process on $C(S_{U})$, gives the desired agnostic learner.
This actually follows from standard arguments. In particular, given a
hypothesis $h\in C(S_{U})$, let

$err_{S_{L}}(h)=\Pr_{(x,y)\sim S_{L}}[h(x)\neq y]$

denote its empirical risk with respect to $S_{L}$. Since $C(S_{U})$ is finite,
a standard Chernoff+Union bound gives that with probability at least
$1-\delta/2$, the empirical risk of every hypothesis in $C(S_{U})$ with
respect to $S_{L}$ is close to its true risk. Then as long as $S_{L}$ is
sufficiently large, empirical risk minimization returns a solution with at
most $OPT+\varepsilon$ error with high probability (we’ll formalize this in a
moment).

It remains to prove 2.3. The key observation lies in an equivalence between
realizable PAC-learning and a weak type of randomized covering: for any fixed
$h\in H$, $C(S_{U})$ contains a hypothesis close to $h$ with high probability.

######  Lemma 2.4.

For any distribution $D$ over $X\times Y$ with marginal $D_{X}\in\mathscr{D}$
and any $h\in H$, with probability $1-\delta/2$, there exists $h^{\prime}\in
C(S_{U})$ which is within $\varepsilon/2$ of $h$ in classification distance:

$\Pr_{x\sim D_{X}}[h^{\prime}(x)\neq h(x)]\leq\varepsilon/2.$

###### Proof.

The proof is essentially immediate from the definition of realizable PAC-
learning. $\mathcal{A}$ promises that for any $h\in H$ and $D\in\mathscr{D}$,
a $1-\delta/2$ fraction of labeled samples $(S,h(S))\sim
D^{n(\varepsilon/2,\delta/2)}$ satisfy

$\text{err}_{D\times
h}[\mathcal{A}(S,h(S))]=\underset{D}{\Pr}[h^{\prime}(x)\neq
h(x)]\leq\varepsilon/2,$

where $h^{\prime}=\mathcal{A}(S,h(S))$. Since $C(S_{U})$ contains
$\mathcal{A}(S_{U},h(S_{U}))$ for every $h\in H$ by definition, the result
follows. ∎

More generally, we call such objects non-uniform covers.

######  Definition 2.5 (Non-uniform Cover (Informal Definition 5.1)).

Let $(X,H)$ be a class over label space $Y$, $D$ a marginal distribution over
$X$, and $C$ a random variable over the power set $P(H)$. We call $C$ a non-
uniform $(\varepsilon,\delta)$-cover of $H$ with respect to $D$ if for every
$h\in H$:

$\Pr_{C}\left[\exists h^{\prime}\in C:\Pr_{x\sim D}[h^{\prime}(x)\neq
h(x)]\leq\varepsilon\right]\geq 1-\delta.$

Note that Lemma 2.4 (and in general non-uniform covering) does not imply that
$C(S_{U})$ contains hypotheses close to every $h\in H$ simultaneously. This
stronger object is called a uniform cover and takes provably more samples to
construct (see Appendix G). In our case, a non-uniform cover is sufficient.
Since the guarantee holds for every fixed $h\in H$, it must hold in particular
for the optimal hypothesis $h_{OPT}$, so $C(S_{U})$ contains some $h^{\prime}$
within $\varepsilon/2$ of optimal. Let’s now formalize these ideas and put
everything together to prove Theorem 2.2.

###### Proof of Theorem 2.2.

Let $D$ be the adversary’s distribution over $X\times Y$, and let $h_{OPT}\in
H$ be a hypothesis achieving the optimal error. By Lemma 2.4, with probability
$1-\delta/2$, $C(S_{U})$ contains a hypothesis $h^{\prime}$ such that:

$\Pr_{x\sim D_{X}}[h^{\prime}(x)\neq h_{OPT}(x)]\leq\varepsilon/2.$

This implies 2.3 (that $C(S_{U})$ contains a hypothesis with error at most
$OPT+\varepsilon/2$) since

$\displaystyle err_{D}(h^{\prime})$ $\displaystyle=\underset{(x,y)\sim
D}{\Pr}[h^{\prime}(x)\neq y]$ $\displaystyle\leq\underset{(x,y)\sim
D}{\Pr}[h_{OPT}(x)\neq y]+\underset{(x,y)\sim D}{\Pr}[h_{OPT}(x)\neq
h^{\prime}(x)]$ $\displaystyle\leq OPT+\varepsilon/2.$

We can now use standard empirical risk minimization bounds on $C(S_{U})$ to
find a hypothesis with error at most $OPT+\varepsilon$. Chernoff and union
bounds imply that with probability at least $1-\delta/2$, the empirical risk
of every hypothesis in $C(S_{U})$ on a sample of size
$O\left(\frac{\log(|C(S_{U})|/\delta)}{\varepsilon^{2}}\right)$ is at most
$\varepsilon/4$ away from its true error. Since $h^{\prime}$ has error at most
$OPT+\varepsilon/2$, its empirical risk is at most $OPT+3\varepsilon/4$, and
by the above guarantee any hypothesis in $C(S_{U})$ with empirical risk at
most $OPT+3\varepsilon/4$ has true error at most $OPT+\varepsilon$.

Putting everything together, we have that with probability $1-\delta$ over the
entire process, the empirical risk minimizer of $C(S_{U})$ has error at most
$OPT+\varepsilon$ as desired. The sample complexity bounds follow from noting
that $|C(S_{U})|$ is at most $2^{n(\varepsilon/2,\delta/2)}$, and at most
$\left(\frac{e\cdot n(\varepsilon/2,\delta/2)}{d}\right)^{d}$ if the class has
VC dimension $d$. The sample complexity bound for the latter case then follows
by plugging in the standard bound for distribution-free classification:
$n(\varepsilon/2,\delta/2)\leq
O\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right)$. ∎

###  2.2 Beyond Binary Classification

While simplifying and generalizing classic results on distribution-free [3, 4]
and distribution-dependent [6] learning is nice in and of itself, the real
benefit of Algorithm 1 lies in its ability to adapt across a huge range of
models. In this section, we’ll give a high-level overview of some extensions
to popular learning settings beyond the PAC model. Detailed discussion and
proofs of these results are given in the main body and appendices.

####  2.2.1 Generalizing Labels and Loss

We’ll start by considering one of the most basic and important modifications
in practice: generalized label spaces and loss functions beyond binary
classification. This encompasses classic settings such as multi-class
classification, regression, and more. Formally, the setup remains mostly the
same. Let $X$ be the instance space, and $\mathscr{D}$ a family of
distributions over $X$. Instead of just working over $\\{0,1\\}$, we will now
consider classifiers over a generic label space $Y$, and loss function
$\ell:Y\times Y\to\mathbb{R}_{\geq 0}$. For simplicity, we will always assume
that $\ell(y,y)=0$, and will say that $\ell$ satisfies the identity of
indiscernibles if $\ell(y_{1},y_{2})=0$ iff $y_{1}=y_{2}$. Given a family of
classifiers $H=\\{h:X\to Y\\}$ and a distribution $D$ over $X\times Y$, the
error or risk of a hypothesis $h\in H$ is its expected loss:

$err_{D,\ell}(h)=\underset{(x,y)\sim D}{\mathbb{E}}[\ell(h(x),y)].$

Learnability of a class $(\mathscr{D},X,H,\ell)$ in the distribution-family
model is then defined exactly as before, where the only difference lies in
replacing classification error with the above.

Unfortunately, it is fairly clear that a naive application of Algorithm 1 will
fail in this general model. If $Y$ is infinite, the unlabeled sample $S_{U}$
may have infinitely many possible labelings, causing $C(S_{U})$ to be infinite
in turn. Since we are not in the domain where uniform convergence is
equivalent to learnability, empirical risk minimization is no longer
guaranteed to work, and Algorithm 1 may therefore fail. In fact, this is not
just an issue with our algorithm: it is an inherent barrier. Realizable and
agnostic learning simply aren’t equivalent for most reasonable losses over
infinite label classes.

######  Proposition 2.6 (Proposition 6.1).

Let $\ell$ be any loss function over $\mathbb{R}$ satisfying the identity of
indiscernibles that is continuous in the first variable. Then there exists a
class $(\mathscr{D},X,H,\ell)$ which is realizably learnable but not
agnostically learnable.

It is worth mentioning that $\mathscr{D}$ can be taken to be the set of all
distributions over $X$ in this construction, so the lower bound holds in the
distribution-free setting as well.

The construction in Proposition 2.6 uses the infinite label space to exactly
encode each hypothesis (i.e. a single labeled example always uniquely
determines the corresponding hypothesis). In the realizable case this is
clearly learnable in a single sample, but a small amount of noise can
completely erase this information so the class can’t be agnostically learned.
On the positive side, we use a simple modification of Algorithm 1 to show this
is essentially the only barrier to agnostic learnability. Somewhat more
formally, we call a class _discretely learnable_ if for every $\varepsilon>0$,
there exists an $\varepsilon$-discretization999A discretization is a class
$H^{\prime}$ over a finite (or probably finite) label space such that every
$h\in H$ is close to some $h^{\prime}\in H^{\prime}$. See Section 6.1 for
details. of $(\mathscr{D},X,H,\ell)$ that is learnable up to $O(\varepsilon)$
error. Discrete learnability can informally be thought of as a very weak type
of noise tolerance that essentially acts only to rule out the above
construction.

We prove that discrete learnability is equivalent to agnostic learnability
over two broad classes of loss functions. The first is a basic generalization
of loss functions over finite label classes we call doubly bounded loss.

######  Theorem 2.7 (Informal Theorem A.2: Realizable $\to$ Agnostic (Doubly
Bounded Loss)).

Let $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$ be a loss function such that
$\forall y_{1}\neq y_{2}\in Y$:

$\ell(y_{1},y_{2})\in[\alpha,\beta]$

for some $\beta>\alpha>0$. Then for any class $(\mathscr{D},X,H,\ell)$, the
following are equivalent:

  1. 1.

$(X,H,\mathscr{D},\ell)$ is (properly) discretely-learnable.

  2. 2.

$(X,H,\mathscr{D},\ell)$ is (properly) agnostically-learnable.

This result also implies that realizable and agnostic learning are equivalent
over any loss function satisfying the identity of indiscernibles over finite
$Y$, since realizable and discrete learnability are equivalent in this case
and every such loss function is doubly bounded. We complement this with a
lower bound showing a separation between realizable and agnostic learning for
general loss over finite $Y$ by exploiting a simple ternary loss function that
fails the identity of indiscernibles (see Proposition 5.4).

While many reasonable loss functions on infinite label classes (e.g.
$\ell_{p}$-loss) aren’t bounded away from $0$, they do tend to come with other
structure we can utilize. We’ll prove a similar result to the above under the
weak assumption that our loss satisfies an approximate triangle inequality.
Such loss functions, which we call approximate pseudometrics, can informally
be thought of as generalizing any sort of distance-based loss.

######  Theorem 2.8 (Informal Theorem 6.5: Realizable $\to$ Agnostic
(Approximate Pseudometrics)).

Let $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$ be an (upper) bounded101010By this
we mean the range of $\ell$ is $[0,B]$ for some $B\in\mathbb{R}_{\geq 0}$. We
note that this condition can be replaced with the weaker assumption that
$(\mathscr{D},X,C,\ell)$ is agnostically learnable for every finite subset
$C\subseteq H$. loss function satisfying a $c$-approximate triangle
inequality:

$\forall y_{1},y_{2},y_{3}\in Y:\ell(y_{1},y_{3})\leq
c(\ell(y_{1},y_{2})+\ell(y_{2},y_{3})).$

Then for any class $(\mathscr{D},X,H,\ell)$, the following are equivalent:

  1. 1.

$(\mathscr{D},X,H,\ell)$ is (properly) discretely-learnable.

  2. 2.

$(\mathscr{D},X,H,\ell)$ is (properly) $c$-agnostically learnable.

where “$c$-agnostic” learnability only requires error $c\cdot OPT+\varepsilon$
rather than $OPT+\varepsilon$.

While $c$-agnostic learnability is a weaker guarantee than we get for doubly
bounded loss, it is actually necessary for approximate pseudometrics. In
particular, there exist simple discretely-learnable classes over
$c$-approximate pseudometrics which are not $c^{\prime}$-agnostically
learnable for any $c^{\prime}<c$ (see Proposition 6.6). It is also worth
noting that the sample complexity blowup in both Theorem 2.7 and Theorem 2.8
remains polynomial in $\varepsilon^{-1}$ (indeed nearly-quadratic) in most
reasonable scenarios.111111More formally, the blowup is at worst
$\frac{\log(|Y_{\varepsilon}|)}{\varepsilon^{2}}$, where $|Y_{\varepsilon}|$
is the size of the $\varepsilon$-discretized label space. Finally we remark
that along with being novel in the distribution-family setting, to our
knowledge these results are actually new to the distribution-free setting as
well, where such an equivalence was only known for bounded Lipschitz [5, 22]
or binary-valued [23, 7] loss functions.

####  2.2.2 Beyond the PAC Setting

While allowing distributional assumptions through the distribution-family
model is a good step towards practice, recent trends have starting branching
even further away from the PAC setting. In this section, we’ll discuss a
prototypical example of applying Algorithm 1 to an extended model: adversarial
robustness. In the appendix, we cover similar extensions to Partial Learning
(Appendix C), SQ-learning (Appendix E), and Fair Learning (Appendix F).

Robust learning is an extension of the PAC model introduced to handle
adversarial perturbations at test time. Practically, this is meant to ensure
that an integrated prediction system (e.g. in a self-driving car) cannot be
tricked by possibly imperceptible adversarial changes to the outside world.
This can be formalized by modifying the way we compute error. Given a
perturbation function mapping $X$ to its power set, $\mathcal{U}:X\to P(X)$
(think of $\mathcal{U}$ as specifying a neighbor set or set of possible
corruptions for each $x\in X$), the robust risk of a labeling $h:X\to Y$ with
respect to a distribution $D$ over $X\times Y$ is:

$\text{R-err}_{\mathcal{U},D}(h)=\underset{(x,y)\sim
D}{\mathbb{E}}\left[\max_{x^{\prime}\in\mathcal{U}(x)}\ell(h(x^{\prime}),y)\right].$

Realizable and agnostic robust learning are then defined analogously to the
PAC-model where the standard error is replaced with robust error (though the
distribution-family model does require a slight twist, see Appendix B for
details). We show that a basic modification to Algorithm 1 again implies the
two models are equivalent.

######  Theorem 2.9 (Informal Theorem B.5: Realizable $\to$ Agnostic (Robust
Classification)).

If $(\mathscr{D},X,H)$ is robustly PAC-learnable in the realizable setting
with sample complexity $n(\varepsilon,\delta)$, then (a modification of)
Algorithm 1 robustly learns $(\mathscr{D},X,H)$ in the agnostic setting in:

$m_{U}(\varepsilon,\delta)\leq
O\left(\max_{\mu\in[0,1-\varepsilon]}\left\\{\frac{n(\varepsilon/(2(1-\mu)),\delta/3)}{1-\mu}\right\\}\right)$

unlabeled samples and

$m_{L}(\varepsilon,\delta)\leq
O\left(\frac{m_{U}(\varepsilon,\delta)+\log(1/\delta)}{\varepsilon^{2}}\right)$

labeled samples.

We note that this result can also be combined with our analysis for more
general loss functions, albeit with a slightly worse $c$-agnostic parameter.
In the classification setting, Theorem 2.9 generalizes recent work giving such
an equivalence in the distribution-free model [8, 24], though the sample
complexity of our algorithm suffers an extra factor of $\varepsilon^{-1}$ in
this special case.

###  2.3 Property Generalization

So far we have only considered using Algorithm 1 to reduce from agnostic to
realizable learning, albeit in a number of extended settings beyond the PAC
model. On the other hand, we claimed in the introduction that Algorithm 1 can
be used to build a learner satisfying any “finitely-satisfiable” property. In
this section, we’ll discuss two such examples: privacy, and malicious noise.
In Appendix D we cover a similar application to uniform stability. Note that
since we are only modifying the learning _property_ in this section, the base
(realizable) learner remains the same and does not require any additional
constraints.

We’ll start with Kearns and Li’s malicious noise [25]. In this model, the
learner has access to a faulty sample oracle $\mathcal{O}_{M}(\cdot)$ which
returns a labeled sample from the adversary’s true distribution with
probability $1-\eta$, and otherwise receives an adversarially chosen pair
$(x,y)$. A realizable or agnostic learner is said to be tolerant to malicious
noise if it achieves the standard PAC guarantees while drawing from the
malicious oracle instead of the standard sample oracle. Like agnostic
learning, tolerance to malicious noise is easy to achieve on finite hypothesis
classes. As a result, a basic modification of Algorithm 1 gives a blackbox
reduction from agnostic learning with malicious noise to realizable learning.

######  Theorem 2.10 (Informal Theorem 6.8: Realizable $\to$ Malicious).

If $(\mathscr{D},X,H)$ is realizably PAC-learnable with sample complexity
$n(\varepsilon,\delta)$, then for any
$\eta<\frac{\varepsilon}{1+\varepsilon}$, (a modification of) Algorithm 1
gives an agnostic learner for $(\mathscr{D},X,H)$ tolerant to $\eta$ malicious
noise. Furthermore letting $\Delta=\frac{\varepsilon}{1+\varepsilon}-\eta$,
the sample complexity is at most
$\text{poly}(\Delta^{-1},\log(1/\delta),n(\Delta,\delta))$.

This extends the original result of [25] to the distribution-family setting,
and is tight in the sense that $\frac{\varepsilon}{1+\varepsilon}$ is the best
possible error tolerance in the malicious model [25]. As before, the result
can be combined with our discretization techniques to give a similar
equivalence for approximate pseudometric loss that is new in both the
distribution-family and distribution-free settings.

While malicious noise is certainly distinct from the agnostic model, both are
examples of noise-tolerance properties. We’ll finish this informal discussion
of our results with a learning property of a different flavor: privacy.
Informally, an algorithm is said to be $\alpha$-differentially private if its
output is not susceptible to small changes in the underlying sample (see
Section 6.3 for exact definitions). Privacy is a very strong condition, even
relaxed notions such as $(\alpha,\delta)$-differential privacy (which
essentially allows for a $\delta$ probability of privacy failure) require
finite Littlestone dimension in the distribution-free setting [14], which
rules out any sort of reduction directly from realizable learning.

On the other hand, our reduction actually is able to recover a different
relaxation known as semi-private learning [17]. In this generalization of the
well-studied ‘label privacy’ [26] setting, the learning algorithm has access
not only to a private database of labeled samples, but also to a smaller
public database of unlabeled data. This models a common practical scenario: a
small portion of “opt-in” users are willing to release their participation,
but still wish to hide any sensitive label data. By replacing the empirical
risk minimization (ERM) process in Step 3 of Algorithm 1 with a popular
private algorithm known as the exponential mechanism [27], we give a direct
reduction from semi-private to realizable learning in the distribution-family
setting.

######  Theorem 2.11 (Informal Theorem 6.15: Semi-Private $\to$ Realizable).

If $(\mathscr{D},X,H)$ is realizably learnable with sample complexity
$n(\varepsilon,\delta)$, then (a modification of) Algorithm 1 gives an
$\alpha$-semi-private, agnostic learner using

$m_{\text{pub}}(\alpha,\varepsilon,\delta)\leq n(\varepsilon/2,\delta/2)$

unlabeled (public) samples, and

$m_{\text{pri}}(\alpha,\varepsilon,\delta)\leq
O\left(\frac{n(\varepsilon/2,\delta/2)+\log(1/\delta)}{\varepsilon\cdot\min\\{\varepsilon,\alpha\\}}\right)$

labeled (private) samples.

This generalizes Beimel, Nissim, and Stemmer’s [17] original equivalence of
realizable and semi-private learning in the distribution-free setting to the
distribution-family model, and also extends to the general loss functions
covered in Section 2.2.1. In fact, in this case our algorithm actually gives a
quantitative improvement over previous work [17, 18] in the distribution-free
case.

######  Corollary 2.12 (Informal Corollary 6.16: Realizable $\to$ Semi-Private
(Distribution-Free Classification)).

Let $(X,H)$ be a class with VC-dimension $d$. Then $(X,H)$ is $\alpha$-semi-
private, agnostically learnable in

$m_{\text{pub}}(\varepsilon,\delta,\alpha)\leq
O\left(\frac{d+\log(1/\delta)}{\varepsilon}\right)$

unlabeled samples,121212We note that this algorithm is improper. A proper
algorithm may need an additional $\log(1/\varepsilon)$ unlabeled samples for
some classes. and

$m_{\text{pri}}(\varepsilon,\delta,\alpha)\leq
O\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon\cdot\min\\{\varepsilon,\alpha\\}}\right)$

labeled samples.

For fixed $d$ and $\delta$, Corollary 2.12 resolves the unlabeled sample
complexity of semi-private learning, improving over the recent best of Alon,
Bassily, and Moran [18], who additionally showed that any class which is not
privately learnable requires at least $\Omega(\frac{1}{\varepsilon})$ public
samples to (semi)-privately learn. The private sample complexity, on the other
hand, remains off by a logarithmic factor from known lower bounds [28].
Resolving the latter requires improving the standard application of the
exponential mechanism, and remains an interesting open problem.

It is also worth noting that Theorem 2.11 and Corollary 2.12 are robust to
some amount of shift in distribution between the public and private databases.
This problem, often called covariate shift in other contexts, is a commonly
observed issue in machine learning practice, and is especially of concern in
privacy where a distribution over “opt-in” public users could easily differ
from the overall distribution of private data. We discuss covariate shift in
the semi-private setting in more depth in Section 6.4.

###  2.4 Proof Overview: Modification Archetypes

We’ve already seen how Algorithm 1 works in the basic case of binary
classification, but covering the extended regimes above require some
modifications. In this section, we’ll overview the four generic types of
modification we use to extend Algorithm 1 across the aforementioned settings.

##### Discretization.

We’ll start by discussing our main technique to extend Algorithm 1 to infinite
label spaces. The basic idea is simple: since we cannot afford to run our
learner over all possible labelings of $S_{U}$, we instead run the learner
over labelings coming from some discretization of the class. As long as we
have access to a learner for the discretization, we can then use the same
arguments covered in Section 2 to prove various occurrences of property
generalization. We formalize these notions more generally in Section 6.1,
where we use the technique to prove Theorem 2.8 (Theorem 2.7 is proved in
Appendix A). Discretization can also be used to handle learning models such as
the statistical query setting which output real-valued query responses (see
Appendix E).

##### Subsampling.

Another core limitation to Algorithm 1 is access to clean unlabeled data.
Algorithm 1 works by running a realizable learner over a representative set of
unlabeled data, but, in practice, such data may often be corrupted, and data-
dependent assumptions such as margin might mean that the optimal hypothesis
isn’t even well-defined on this set. We handle cases like these by a simple
sub-sampling procedure: instead of running our realizable learner over
labelings of $S_{U}$, we run the learner over all labelings of all subsets of
$S_{U}$. As long as $S_{U}$ contains some amount of uncorrupted data, this
subsampling procedure will find it and we can maintain the guarantees
discussed in Section 2. We use this technique to prove property generalization
for models such as robust learning (see Theorem 2.9 and Appendix B), partial
learning (see Appendix C), and malicious noise (see Theorem 2.10 and Section
6.2).

##### Replacing the Finite Learner.

In the introduction, we proposed a general paradigm (guiding principle) called
property generalization: that a variant of any learning property which holds
for finite classes should in fact hold for any “learnable” class in the base
model. The main idea relies on replacing Step 3 of Algorithm 1 (which, as
stated, is an empirical risk minimization process) with a generic learner for
finite classes with the desired property. For noise-tolerance properties such
as agnostic and malicious noise, empirical risk minimization works. Properties
such as privacy or stability, however, require a different finite learner. To
prove Theorem 2.11, for example, we replace the ERM process in Algorithm 1
with the exponential mechanism [27]. We use a similar strategy in Appendix D
to prove an analogous result for uniform stability.

##### Replacing the Base Learner.

Finally we note a very basic modification of Algorithm 1 that allows us to
extend property generalization beyond the PAC setting: simply replace the
input realizable PAC learner with a realizable learner in the desired model.
This is usually combined with one of the techniques above depending on the
specific application, e.g. to prove property generalization for robust
learning and the statistical query model. The same idea can also be used to
analyze semi-private learning with covariate shift (see Section 6.4) and
property generalization for fair learning (see Appendix F).

##  3 Related Work

Agnostic learning is a very widely studied model across learning theory, and
works across many different sub-areas have noted model specific equivalences
with realizable learning. Here we’ll survey a few representative examples, and
discuss how they relate and differ from our approach.

###  3.1 Beyond Binary Classification

##### Uniform Convergence and Multiclass Classification.

It is well known that the uniform convergence equals learnability paradigm
continues to hold for $0/1$-valued loss functions over constant-size label
spaces [3, 23, 29, 30], and that agnostic and realizable learning are
equivalent as a result. On the other hand, Daniely, Sabato, Ben-Devid, and
Shalev-Shwartz [31] showed this is no longer the case as the number of labels
grows large. In this regime, even basic multi-class learning is no longer
equivalent to uniform convergence, so the connection between realizable and
agnostic learning becomes non-trivial. A few years later, David, Moran, and
Yehuyadoff (DMY) [7] proved the equivalence nevertheless holds in the infinite
multi-class setting through the weaker sample compression equals learnability
paradigm. While more general than the uniform convergence paradigm, their
proof remains model-specific and fails in many of the settings we consider,
e.g. partial learning [13].

##### Discretization and General Loss Functions.

Basic forms of discretization were also considered back in the mid 90s in work
on characterizing the learnability of real-valued functions. In a seminal
work, Bartlett, Long, and Williamson (BLW) [5] proved that a scale-sensitive
measure introduced by Kearns and Schapire [32] called fat-shattering dimension
characterizes learnability under bounded Lipschitz loss functions.131313Though
the original work only considers $\ell 1$ loss, their techniques generalize to
Lipschitz loss, see for instance [22]. BLW use a basic form of discrete
learning (called quantization) to prove that fat-shattering dimension is a
necessary condition, and use uniform convergence to prove sufficiency. We give
a similar argument as BLW in the necessary direction, but show that uniform
convergence is not necessary for the equivalence to hold, and instead use
Algorithm 1 to appeal directly to discrete learnability. This allows us to
extend BLW’s result across a much more general set of loss functions and
scenarios without strong model-specific assumptions.

###  3.2 Semi-supervised, Active, and Semi-Private Learning

Our reduction hinges on combining a realizable learner with unlabeled data to
cut down the number of potential hypotheses in our class. The use of unlabeled
samples to this effect is one of the core ideas in the field of semi-
supervised learning [19, 33]. Here, it is usually additionally assumed that
the function to be learnt has some relation (or ‘compatibility’) to the
underlying data distribution, for example it might have large margin on
unlabelled data as in Transductive SVM [34] or redundant sufficient
information as in Co-training [35, 36]. In their seminal work on the topic,
Balcan and Blum [19] employed a similar strategy to Algorithm 1 in which they
draw an unlabeled sample $S_{U}$ and select hypotheses consistent with each
possible labeling based upon compatibility. They argue via uniform convergence
that this results in a uniform cover, and then use empirical risk minimization
to select a good hypothesis in the cover. It is worth noting that around the
same time a similar strategy independently found use in the online learning
literature in work of Ben-David, Pal, and Shalev-Schwarz [9] who simulated the
so-called ‘standard optimal algorithm’ (SOA) over a sequence of examples and
applied weighted majority [37] over the resulting set of hypotheses to obtain
an agnostic online learner.

Similar strategies have also found use in the related active learning
literature. Hanneke and Yang [38] use the same technique to build a cover from
unlabeled samples (adding one hypothesis consistent with each possible
labeling), and then apply active (adaptive) query algorithms to learn the best
hypothesis in the cover in as few labeled samples as possible. This
generalized earlier work of Dasgupta [39], who assumed a priori that the cover
was known to the learner ahead of time. Most recently, the approach has seen
use in the study of semi-private learning. In their original work on the
model, Beimel, Nissim, and Stemmer [17] again apply the same trick for
building a uniform cover, but then find the best hypothesis privately via the
exponential mechanism (similar to our proof of Theorem 2.11). The analysis of
this strategy was later improved by Alon, Bassily, and Moran (ABM) [18].

The above works differ from ours in two crucial senses. First, each work
focuses solely on developing an algorithm for their specific framework (rather
than working to understand a more general equivalence or reduction between
settings). In this sense, one can view each of these prior results as a
specific instance of our general framework where the “base learner” in our
reduction is restricted to be an empirical risk minimizer (or SOA in the
online setting), and a problem-specific learner for the relevant property
(online, agnostic, active, or private) is then applied over the resulting
cover. Second, and perhaps most importantly, these previous works all rely
fundamentally on uniform convergence.141414The online setting is the only
exception, but this model diverges much more substantially from the PAC-type
learning we consider in this work than previous uniform convergence based
methods. This means that their algorithms break down as soon as one moves away
from the original PAC model (even to say the basic distribution-dependent
setting), and can also lead to sub-optimal sample complexity bounds. In the
analysis of semi-private learning, for instance, we show that avoiding uniform
convergence leads to asymptotically better bounds, actually resolving the
public sample complexity of the model altogether. Indeed, one can show that
building a uniform cover requires asymptotically more unlabeled samples than a
non-uniform one, and therefore cannot result in optimal semi-supervised
algorithms.151515Formally we only prove this for the distribution-family
model, though we conjecture it holds in the distribution-free setting too.

###  3.3 Non-Uniform Covering and Probabilistic Representations

Covering techniques have long been used in learning theory, and while almost
all prior works focus on uniform notions (where all hypotheses are covered
simultaneously), there is one notable exception. In 2013, Beimel, Nissim, and
Stemmer (BNS) [40] introduced probabilistic representations, a strong
randomized form of covering used to characterize pure differentially private
learning. In the language of our work, given a class $(X,H)$, a probabilistic
representation is a distribution over subsets of $H$ which is a non-uniform
cover simultaneously over all distributions of $X$. BNS prove that private
learning is equivalent to the existence of a probabilistic representations for
the class. Equivalently, this can be thought of as the ability to build a non-
uniform cover without access to the underlying distribution at all. On the
other hand, we are interested in the much weaker setting where a non-uniform
cover can be built from a bounded number of samples from the distribution (and
crucially argue that this is equivalent to realizable learning). Thus in a
sense, our core connection between realizable learning and non-uniform
covering can be thought of as an analog of BNS’ characterization of private
learning by probabilistic representations.

### Paper Organization

The remainder of this paper is split into two portions, the main body and the
appendix. The main body covers our base reduction for finite label classes
along with four archetypes of modification, and is meant to be read as
written. On the other hand, the Appendix covers various applications of these
archetypes to a variety of learning models and properties. These sections are
all self-contained, and are meant more as a reference text in the sense that
the reader interested in some particular model or property should simply skip
to the section covering that application.

The main body is organized as follows: we cover preliminary definitions in
Section 4, our base reduction from agnostic to realizable learning for finite
label classes in Section 5, and discuss the four modification archetypes along
with a representative application in Sections 6.1, 6.2, 6.3 and 6.4. In more
detail, these sections respectively cover: extensions to infinite label
classes via discretization, malicious noise via sub-sampling, agnostic semi-
private learning via replacing ERM, and covariate shift via replacing the base
learner.

In the Appendix we cover applications to doubly-bounded loss (Appendix A),
robust learning (Appendix B), partial learning (Appendix C), uniformly-stable
learning (Appendix D), the statistical query model (Appendix E), and fair
learning (Appendix F), and discuss further connections of non-uniform covers
to previous notions of covering (Appendix G).

##  4 Preliminaries

Before moving to a more formal discussion of our results, we’ll cover the most
basic learning models discussed in this work: standard (distribution-free)
PAC-learning and distribution-family PAC-learning. Extended models we consider
beyond these (e.g. malicious noise, robust learning, partial learning, etc.)
will instead be introduced in their respective sections.

###  4.1 PAC-Learning

We’ll start by reviewing the seminal PAC-learning model of Valiant [1] and
Vapnik and Chervonenkis [2]. We start with a few core definitions for the
setting of general loss. Let $X$ be an arbitrary set called the _instance
space_ (e.g. $\mathbb{R}^{d}$), $Y$ a set called the _label space_ (e.g.
$\\{0,1\\}$), and $H$ a family of labelings of $X$ by $Y$ (that is a family of
functions of the form $h:X\to Y$). Given a class $(X,H)$, it will often be
useful to consider its growth function $\Pi_{H}(n)$ which measures the maximum
size of $H$ when restricted to a sample of size $n$:

$\Pi_{H}(n)=\max_{h\in H,S\in X^{n}}(\left|H|_{S}\right|)).$

We note that the growth function is trivially bounded by $|Y|^{n}$, but one
can often give stronger bounds when $(X,H)$ satisfies some finite
combinatorial dimension (e.g. VC-dimension for the binary case).

While PAC-learning is sometimes used to refer only to classification, we will
study the model under general loss functions. With that in mind, we call a
function $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$ a _loss function_ if
$\ell(y,y)=0$ for all $y\in Y$. We say a loss $\ell$ satisfies the _identity
of indiscernibles_ if $\ell(y_{1},y_{2})=0$ iff $y_{1}=y_{2}$. Given any
distribution $D$ over $X\times Y$ and loss $\ell$, the _risk_ of a labeling
$h:X\to Y$ with respect to $D$ and $\ell$ is its expected loss:

$\text{err}_{D,\ell}(h)=\underset{(x,y)\sim D}{\mathbb{E}}[\ell(h(x),y)].$

The goal of learning is generally to find a classifier $h\in H$ that minimizes
risk. More formally, there are two commonly studied variants of this problem.
The original formulation, now called _realizable_ learning, assumes the
existence of a hypothesis in $H$ with no loss.

######  Definition 4.1 ((Realizable) PAC-learning).

We say $(X,H,\ell)$ is realizable PAC-learnable if there exists an algorithm
$\mathcal{A}$ and function $n(\varepsilon,\delta)$ such that for all
$\varepsilon,\delta>0$ and distributions $D$ over $X\times Y$ such that
$\min_{h\in H}{\text{err}_{D,\ell}(h)}=0$:

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{err}_{D,\ell}(\mathcal{A}(S))>\varepsilon]\leq\delta.$

$\mathcal{A}$ is called proper if it outputs only labels in $H$.

Perhaps a more realistic variant of PAC-learning is to drop this restriction
on the adversary, and let them choose an arbitrary distribution over $X\times
Y$. This model, introduced by Haussler [4] and Kearns, Schapire, and Sellie
[25], is known as _agnostic_ learning.

######  Definition 4.2 ((Agnostic) PAC-learning).

We say $(X,H,\ell)$ is agnostic PAC-learnable if there exists an algorithm
$\mathcal{A}$ and function $n(\varepsilon,\delta)$ such that for all
$\varepsilon,\delta>0$ and distributions $D$ over $X\times Y$:

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{err}_{D,\ell}(\mathcal{A}(S))>OPT+\varepsilon]\leq\delta,$

where $OPT=\min_{h\in H}\\{\text{err}_{D,\ell}(h)\\}$.

For some settings covered in this work, it will turn out that reaching
$OPT+\varepsilon$ error is too stringent of a condition. However, we will show
in these cases that it is sometimes possible to maintain a weaker guarantee
and learn up to $c\cdot OPT+\varepsilon$ error for some constant $c>1$. We
call such classes _$c$ -agnostic learnable_.

Finally, we note that for simplicity when $\ell$ is the standard
“classification error:”

$\ell(y_{1},y_{2})=\begin{cases}0&\text{if }y_{1}=y_{2}\\\
1&\text{else},\end{cases}$

we’ll simply write $(X,H)$ to mean $(X,H,\ell)$. Realizable and Agnostic
Learning are well studied under many basic loss functions including binary
classification, where both models are known to be characterized by a
combinatorial parameter called VC-dimension.

###  4.2 Learning Under Distribution Families

The standard PAC-models described above are often called _distribution-free_
due to the fact that no assumptions are made on the marginal distribution over
$X$. In practice, however, this is usually too worst-case an assumption. We
often expect distributions in nature to be “nice” in some way, or at least
somewhat restricted. This is reflected in the fact that popular machine
learning algorithms usually significantly outperform the PAC-model’s worst-
case generalization bounds. Indeed such niceness assumptions have long been
popular in learning theory as well, where conditions such as tail bounds or
anti-concentration are frequently used to build efficient algorithms.

These ideas are captured more generally by a simple (but notoriously
difficult) extension to the PAC framework originally proposed by Benedek and
Itai [6], where the adversary is restricted to picking from a fixed, known set
of distributions.

######  Definition 4.3 ((Realizable) Distribution-Family PAC-learning).

Let $X$ be an instance space and $\mathscr{D}$ a family of distributions over
$X$. We say $(\mathscr{D},X,H,\ell)$ is realizable PAC-learnable if there
exists an algorithm $\mathcal{A}$ and function $n(\varepsilon,\delta)$ such
that for all $\varepsilon,\delta>0$ and distributions $D$ over $X\times Y$
satisfying:

  1. 1.

The marginal $D_{X}\in\mathscr{D}$,

  2. 2.

$\min_{h\in H}\text{err}_{D,\ell}(h)=0$,

we have

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{err}_{D,\ell}(\mathcal{A}(S))>\varepsilon]\leq\delta.$

Agnostic learning is defined similarly. The adversary must still choose a
marginal distribution in $\mathscr{D}$, but the conditional labeling can be
arbitrary.

######  Definition 4.4 (Agnostic Distribution-Family PAC-learning).

We say $(\mathscr{D},X,H,\ell)$ is agnostic PAC-learnable if there exists an
algorithm $\mathcal{A}$ and function $n(\varepsilon,\delta)$ such that for all
$\varepsilon,\delta>0$ and distributions $D$ over $X\times Y$ satisfying:

  1. 1.

The marginal $D_{X}\in\mathscr{D}$,

$\mathcal{A}$ outputs a good hypothesis with high probability:

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{err}_{D,\ell}(\mathcal{A}(S))>OPT+\varepsilon]\leq\delta$

where $OPT=\min_{h\in H}\\{\text{err}_{D,\ell}(h)\\}$.

The weaker $c$-agnostic learning is defined analogously with $OPT$ replaced by
$c\cdot OPT$. Unlike the standard model, very little is known about
distribution-family learnability. While a number of works have made some
progress on this front [6, 20, 41, 42], a characterization of learnability
remains elusive despite some 30 years of effort.

##  5 The Core Reduction: Agnostic to Realizable Learning

In this section, we give a more detailed exposition of our main reduction as
covered in Section 2, including the more general setting of arbitrary loss on
constant size label spaces (in the distribution-family model), matching lower
bounds, and additional discussion of non-uniform covers. As mentioned
previously, since there is no known combinatorial characterization of
learnability in the distribution-family model, standard techniques [3, 23, 29,
30] cannot be used, and it is plausible that no combinatorial characterization
of learnability exists for this model at all [21].

Before jumping into our reduction proper, it is worth re-iterating why we
can’t simply take the approach of prior works and rely on uniform convergence,
a strong condition which promises that on a large enough sample, the empirical
error of every hypothesis will be close to its true error. While uniform
convergence was a very popular technique in the early years of learning,
practitioners have since moved away from the paradigm which fails to capture
learning rates seen in practice [43, 44]. Indeed it soon became clear that the
technique failed to capture even basic theoretical models such as the
distribution-dependent setting (as discussed in Proposition 2.1). In later
sections, we will even see distribution-free models where uniform convergence
fails, such as the Partial PAC model [12, 13] which captures realistic
scenarios such as learning with margin. Since even the most basic
modifications of PAC-learning fail to satisfy uniform convergence, it is clear
we need to move beyond the condition to gain a more general understanding of
the common phenomenon of equivalence between learning models.

Instead of relying on uniform convergence, our core observation is an
equivalence between learning and sample access to a combinatorial object we
call a non-uniform cover.

######  Definition 5.1 (Non-uniform Cover).

Let $(X,H)$ be a class over label space $Y$ and $L_{X,Y}$ denote the family of
all labelings from $X$ to $Y$. If $C$ is a random variable over the power set
$P(L_{X,Y})$ and $d:L_{X,Y}\times L_{X,Y}\to\mathbb{R}_{\geq 0}$ is a
“distance” function between labelings, we call $C$ a non-uniform
$(\varepsilon,\delta)$-cover of $H$ with respect to $d$ if for all $h\in H$:

$\Pr_{T\sim C}\left[\exists h^{\prime}\in
T:d(h^{\prime},h)\leq\varepsilon\right]\geq 1-\delta.$

We call $C$ bounded if its support lies entirely on subsets of size at most
some $k\in\mathbb{N}$, and we call the smallest such $k$ its size.

Non-uniform covers share a close connection to several notions of covering
used throughout the learning literature such as uniform covers [18] and
fractional covers [45]. We discuss these connections in more detail in
Appendix G. For the moment, we note only that previous works using the
strictly stronger notion of uniform covering necessarily lose factors in the
sample complexity as a result. We discuss this further in Section 6.3 as well.

In Section 2, we argued (at least implicitly) that once we have sampling
access to a bounded non-uniform cover, agnostic learnability follows from
standard arguments. Namely since a sample $T$ has bounded size and is
guaranteed to contain a concept “close” to optimal, it suffices to run
empirical risk minimization over about $\log(|T|/\delta)/\varepsilon^{2}$
samples. The key to our reduction therefore boils down to turning blackbox
access to a realizable PAC-learner into sampling access to some relevant non-
uniform cover. This is given by Step 2 of Algorithm 1, which we rewrite here
as a subroutine called LearningToCover.

Input: Hypothesis Class $H$, Realizable PAC-Learner $\mathcal{A}$, Unlabeled
Sample size $S_{U}$.

Algorithm:

  1. 1.

Run $\mathcal{A}$ over all possible labelings of $S_{U}$ by $H$.

  2. 2.

Return the set of responses $C(S_{U})$:

$C(S_{U})\coloneqq\\{\mathcal{A}(S_{U},h(S_{U}))\leavevmode\nobreak\
|\leavevmode\nobreak\ h\in H|_{S_{U}}\\}.$

Algorithm 2 LearningToCover($H$, $\mathcal{A}$, $S_{U}$)

In fact, we already argued in Section 2 that LearningToCover gives sampling
access to a non-uniform cover, but we will re-write the result here in this
formulation for convenience.

######  Lemma 5.2 (Core Lemma: Realizable Learning Implies Non-Uniform
Covering).

Let $\mathcal{A}$ be an algorithm that $(\varepsilon,\delta)$-PAC learns a
class $(\mathscr{D},X,H,\ell)$ in $n=n(\varepsilon,\delta)$ samples. Then for
any $D\in\mathscr{D}$, running LearningToCover on $S_{U}\sim D^{n}$ returns a
sample from a size $\Pi_{H}(n)$, non-uniform $(\varepsilon,\delta)$-cover with
respect to the standard distance between hypotheses:

$d(h,h^{\prime})=\underset{D}{\mathbb{E}}[\ell(h^{\prime}(x),h(x))].$

###### Proof.

The proof is essentially immediate from the definition of realizable PAC-
learning. $\mathcal{A}$ promises that for any $h\in H$ and $D\in\mathscr{D}$,
a $1-\delta$ fraction of labeled samples $(S_{U},h(S_{U}))\sim
D^{n(\varepsilon,\delta)}$ satisfy

$\text{err}_{D\times
h,\ell}(\mathcal{A}(S_{U},h(S_{U})))=\underset{D}{\mathbb{E}}[\ell(h^{\prime}(x),h(x))]\leq\varepsilon,$

where $h^{\prime}=\mathcal{A}(S_{U},h(S_{U}))$. Since $C(S_{U})$ contains
$\mathcal{A}(S_{U},h(S_{U}))$ for every $h$ by definition, the result follows.
∎

This means that as long as we have blackbox access to a realizable PAC-learner
and unlabeled samples from the adversary’s distribution, we can simulate
access to a non-uniform cover. Let’s now formalize our previous intuition that
this is sufficient to turn a realizable learner into an agnostic one for any
finite label class. We will generalize this result to doubly-bounded loss in
Appendix A, but it is instructive to consider the setting of finite $Y$ first.

######  Theorem 5.3 (Realizable $\to$ Agnostic (Finite Label Classes)).

Let $(\mathscr{D},X,H,\ell)$ be any class on a finite label space $Y$ with
loss function $\ell:Y\to Y$ satisfying the identity of indiscernibles. Then
Algorithm 1 is an agnostic learner with sample complexity:

$m(\varepsilon,\delta)\leq
n(\eta_{\ell}\varepsilon,\delta/2)+O\left(\frac{\log\left(\frac{\Pi_{H}(n(\eta_{\ell}\varepsilon,\delta/2))}{\delta}\right)}{\varepsilon^{2}}\right)$

where $\eta_{\ell}\geq\Omega\left(\frac{\min_{a\neq b}(\ell(a,b))}{\max_{a\neq
b}(\ell(a,b))}\right)$ is a constant depending only on $\ell$.

###### Proof.

Let $\mathcal{A}$ be the promised realizable learner for
$(X,H,\mathscr{D},\ell)$ with sample complexity $n(\varepsilon,\delta)$. Run
LearningToCover with parameters $\varepsilon^{\prime}=\eta_{\ell}\varepsilon$
and $\delta^{\prime}=\delta/2$. We argue that the output contains some
$h^{\prime}$ such that $\text{err}_{D,\ell}(h^{\prime})\leq
OPT+\varepsilon/2$. Since $C(S_{U})$ is finite and $\ell$ is upper bounded, a
standard Chernoff bound gives that choosing an empirical risk minimizer from
$C(S_{U})$ based on
$O\left(\frac{\log\left(\frac{|C(S_{U})|}{{\delta}}\right)}{\varepsilon^{2}}\right)$
additional samples gives the desired learner. The sample complexity then
follows immediately from the definition of $C(S_{U})$.

To see why $C(S_{U})$ has this property, recall that for any $h\in H$, Lemma
5.2 states that $C(S_{U})$ contains some $h^{\prime}$ such that:

$\mathbb{E}_{x\sim
D_{X}}[\ell(h^{\prime}(x),h(x))]\leq\eta_{\ell}\varepsilon.$

Because we assume that $\ell(a,b)=0$ iff $a=b$, this actually implies a
stronger relation—$h$ and $h^{\prime}$ must be close in classification error:

$\Pr_{x\sim D_{X}}[h(x)\neq
h^{\prime}(x)]\leq\frac{\eta_{\ell}\varepsilon}{\min_{a\neq b}(\ell(a,b))}.$

Let $h_{OPT}\in H$ be an optimal hypothesis, and let $h^{\prime}_{OPT}$ denote
the corresponding output of LearningToCover. Then by the above, we have that:

$\displaystyle\text{err}_{D,\ell}(h^{\prime}_{OPT})$
$\displaystyle=\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h^{\prime}_{OPT}(x),y)]$
$\displaystyle=\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h^{\prime}_{OPT}(x),y)-\ell(h_{OPT}(x),y)+\ell(h_{OPT}(x),y)]$
$\displaystyle=OPT+\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h^{\prime}_{OPT}(x),y)-\ell(h_{OPT}(x),y)]$
$\displaystyle\leq OPT+Pr_{D}[h_{OPT}(x)\neq h^{\prime}_{OPT}(x)]\max_{a\neq
b}(\ell(a,b))$ $\displaystyle\leq OPT+\varepsilon/2$

where we have used the assumption that we set $\eta_{\ell}=c\frac{\min_{a\neq
b}(\ell(a,b))}{\max_{a\neq b}(\ell(a,b))}$ for some universal $c>0$. ∎

It’s worth spending a moment discussing our only assumption on the loss
function $\ell$, that it satisfies the identity of indiscernibles. This is not
only a natural assumption for most cases in practice (that mislabeling has
non-zero error), it is theoretically justified as well: realizable and
agnostic learning aren’t necessarily equivalent for $\ell$ without this
property, even in the distribution-free setting.

######  Proposition 5.4 (Identity of Indiscernibles Lower Bound).

There exists a realizably learnable class $(X,H,\ell)$ over a finite label
space $Y$ which is not agnostically learnable.

###### Proof.

Let the instance space $X=\mathbb{N}$ be the set of natural numbers, the label
space $Y=\\{0,1\\}^{2}$. We consider the hypothesis class $H$ with all
functions which output the first bit as $0$, that is:

$\displaystyle H=\\{h:h(x)=(0,\cdot)\leavevmode\nobreak\ \forall x\in X\\}.$

Furthermore, we define the loss function $\ell:Y\times Y\to\\{0,1,c\\}$ as

$\displaystyle\ell((b_{1},r_{1}),(b_{2},r_{2}))=\begin{cases}0&b_{1}=b_{2}\\\
1&b_{1}\neq b_{2}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
r_{1}=r_{2}\\\ c&\leavevmode\nobreak\ \text{otherwise.}\end{cases}$

Note that $(X,H,\ell)$ is trivially learnable in the realizable setting simply
by returning any $h\in H$. On the other hand, we will show it is only
$O(c)$-agnostically learnable. First, notice that for any labelling $f:X\to
Y$, there exists a hypothesis $h\in H$ which matches $f$ on the second bit,
and therefore for any marginal $D$ over $X$:

$OPT\leq err_{D,f}(h)\leq 1.$

As a result, it suffices to show that for every $m\in\mathbb{N}$ and
(randomized) algorithm $\mathcal{A}$ using $m$ samples there exists a labeling
$f:X\to Y$ and marginal distribution $D_{X}$ such that

$\displaystyle\mathbb{E}_{S\sim D^{m}_{X}}\mathbb{E}_{x\sim
D_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x))]\geq c/12.$ (1)

As long as this holds Markov’s inequality gives that every algorithm must have
error at least $\Omega(c)$ with constant probability.

For simplicity, we will restrict our attention in the rest of the proof to the
marginal distribution $D_{X}$ which is uniform over the set $[k]$ for some
natural number $k$ we will fix later. To prove Equation 1, by Yao’s minimax
principle it is enough to prove there is a distribution $\mu$ over functions
$f:[k]\to Y$ such that any _deterministic_ algorithm $\mathcal{A}$ has
expected loss at least $c/12$ over $\mu$:

$\displaystyle\mathbb{E}_{f\sim\mu}\mathbb{E}_{S\sim
D^{m}_{X}}\mathbb{E}_{x\sim D_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x))]>c/12.$

We now show that the above holds for $\mu$ being uniform over all functions
from $[k]$ to $Y$ for any $k>2m$. Here, we have that

$\displaystyle\mathbb{E}_{x\sim D_{X}}\mathbb{E}_{f\sim\mu}\mathbb{E}_{S\sim
D^{m}_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x)))]\geq\mathbb{E}_{x\sim
D_{X}}\Big{[}\Pr_{S\sim D^{m}_{X}}[x\notin S]\cdot c/4\Big{]},$

where the last step follows from noting that for any value $(a,b)$ that
$\mathcal{A}(S,f(S))$ assigns to $x\notin S$, $f(x)$ will be $(1-a,1-b)$ with
probability $1/4$ incurring a loss of $c$. The result then follows by noting
that for every $x\in[k]$:

$\displaystyle\Pr_{S\sim D^{m}_{X}}[x\notin
S]=\Big{(}1-\frac{1}{k}\Big{)}^{m}\geq 1/e$

since $1-x\geq\exp\\{-x/(1-x)\\}$ and $k>2m$. Therefore, we get that

$\displaystyle\mathbb{E}_{x\sim D_{X}}\mathbb{E}_{f\sim\mu}\mathbb{E}_{S\sim
D^{m}_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x))]\geq c/4e,$

which completes the proof. ∎

Note that this bound holds even if $\mathcal{A}$ is allowed to be improper. It
is worth noting that if we are willing to increase the size of $Y$, the
learner’s error in this bound can actually be increased all the way to $c$,
the maximum possible (see Proposition 6.1). This is in fact tight, as we will
show that any loss function like the above satisfying a $c$-approximate
triangle inequality can be $c$-agnostically learned (that is learned to within
$c\cdot OPT+\varepsilon$ error).

##  6 Four Modification Archetypes

###  6.1 Discretization: Infinite Label Classes

In the previous section, we showed that our base reduction characterizes the
equivalence of realizable and agnostic learning for loss functions satisfying
the identity of indiscernibles for all finite label classes. In this section,
we discuss a technique called discretization that allows our reduction to
extend this result to infinite label classes. Normally, it’s clear that when
$Y$ is infinite our standard reduction will fail: since the total number of
possible labelings of a finite sample may be infinite, LearningToCover may
output an infinite set. In fact, this is more than a technical barrier:
realizable and agnostic learning simply aren’t equivalent for infinite label
classes.

######  Proposition 6.1.

Let $\ell$ be any continuous loss function (in the first variable) over
$\mathbb{R}$ satisfying the identity of indiscernibles. Then there exists a
class $(\mathscr{D},X,H,\ell)$ which is realizably learnable but not
agnostically learnable.

###### Proof.

Let $X=\mathbb{N}$ and $Y=[0,2]$. To construct our class, we first consider
the set of all boolean functions over $X$ with finite support. Each function
$f$ in this class may equivalently be thought of as a binary string in
$\\{0,1\\}^{*}$. Denote the corresponding decimal value of this string in
$[0,1]$ by $s_{f}$. To construct $H$, for every boolean function
$f:\mathbb{N}\to\\{0,1\\}$ with finite support, include in $H$ the function
$h_{f}(x)=f(x)+s_{f}$. Note that $(X,H)$ is clearly realizably learnable under
any distribution family $\mathscr{D}$ and any loss function, since a single
sample always uniquely determines $h_{f}$. On the other hand, adding even the
smallest amount of noise erases this unique identification, making the class
impossible to learn.

More formally, let $\mathscr{D}$ be the family of all distributions. By the
continuity of $\ell$ and the fact that $\ell(0,0)=\ell(1,1)=0$, for all
$\varepsilon>0$ notice that there exists $\gamma=\gamma(\varepsilon)>0$ such
that
$\max_{0\leq\gamma^{\prime}\leq\gamma}\\{\ell(\gamma^{\prime},0),\ell(1+\gamma^{\prime},1)\\}<\varepsilon$.
Let $n_{\gamma}\in\mathbb{N}$ be the index of the first non-zero digit in the
binary representation of $\gamma$. The idea is to note that beyond these first
$n_{\gamma}$ coordinates, our class if within $\varepsilon$ of an arbitrary
boolean function. More formally, notice that for any distribution $D$ and
boolean function $f$ which is $0$ on $[n_{\gamma}]$, we have that
$\text{OPT}_{H}(f)\coloneqq\min_{h\in H}\\{\text{err}_{D\times
f,\ell}(h)\\}\leq\varepsilon$. The bound then follows from the fact that such
arbitrary functions are not learnable.

In more detail, Yao’s minimax principle states that it is sufficient to show
that for any potential sample complexity $m(\varepsilon,\delta)$, there exists
a randomized strategy for the adversary such that no deterministic learner can
achieve $OPT+c$ accuracy with constant probability for some constant $c>0$. To
this end, consider the following strategy: the adversary chooses the uniform
distribution over $[n_{\gamma},n_{\gamma}+2m(\varepsilon,\delta)]$, and a
binary function on that interval uniformly at random (recall $OPT$ is at most
$\varepsilon$ for every such function). Since the learner can only see $1/2$
of the mass, any strategy must be incorrect on half of the remaining points in
expectation. In particular conditioned on any sample, the expected loss of any
predicted labeling of an unseen point is at least $\ell_{\text{min-
err}}=\underset{y\in[0,2]}{\min}\\{\frac{\ell(y,0)+\ell(y,1)}{2}\\}$ (since
each unseen label appears with $1/2$ probability conditioned on the learner’s
sample). The total expected loss of any strategy is then at least
$\ell_{\text{min-err}}/2$, which is bounded away from $0$. Setting
$\varepsilon$ and $c$ sufficiently small then gives the desired result. ∎

Proposition 6.1 relies crucially on the fact that the adversary can erase a
significant amount of information with a very small label perturbation. In the
rest of this section, we’ll discuss a technique for modifying our reduction
that shows this is essentially the only barrier between realizable and
agnostic learning (at least for a broad class of loss functions). The key is
to require a slightly stronger notion of learnability based upon
discretization.

######  Definition 6.2 (Discretization).

We say $(\mathscr{D},X,H^{\prime},\ell)$ is an $\varepsilon$-discretization of
$(\mathscr{D},X,H,\ell)$ if the following three conditions hold:

  1. 1.

$H^{\prime}$ is probably bounded. That is for all $n\in\mathbb{N}$,
$\delta>0$, and $D\in\mathscr{D}$ there exists a bound
$m(n,\delta)\in\mathbb{N}$ such that:

$\Pr_{S\sim D^{n}}[|Im(H^{\prime}|_{S})|\leq m(n,\delta)]\geq 1-\delta.$

  2. 2.

$H^{\prime}$ point-wise161616We note that in most cases this condition can
generally be weakened to the expected guarantee $\mathbb{E}_{x\sim
D_{X}}[\ell(h^{\prime}(x),h(x))]\leq\varepsilon$, but the stronger notion is
needed for some applications such as adversarial robustness.
$\varepsilon$-covers $H$ with respect to $\ell$. That is for all for all $h\in
H$, there exists $h^{\prime}\in H^{\prime}$ satisfying:

$\forall x\in X:\ell(h^{\prime}(x),h(x))\leq\varepsilon.$

  3. 3.

$H^{\prime}$ is always useful. That is for all $h^{\prime}\in H^{\prime}$,
there exists $h\in H$ such that:

$\forall x\in X:\ell(h^{\prime}(x),h(x))\leq\varepsilon.$

Note that most realistic settings have reasonable discretizations (e.g. it is
enough to have some Lipshitz-like condition and a weak tail-bound on the
loss). We now define a basic notion of learnability based on discretization
which essentially serves to rule out adversarial constructions in the vein of
Proposition 6.1.

######  Definition 6.3 (Discretely-learnable).

We say $(\mathscr{D},X,H,\ell)$ is discretely-learnable with sample complexity
$n(\varepsilon,\delta)$ if there is some constant $c_{1}>0$ such that for all
$\varepsilon,\delta>0$ there exists an $\varepsilon$-discretization
$H_{\varepsilon}$ which is $(c_{1}\varepsilon,\delta)$-PAC-learnable in at
most $n(\varepsilon,\delta)$ samples. We call the learner proper if it outputs
hypotheses in $H$.

We’ll prove that discrete and agnostic learnability are equivalent as long as
the loss satisfies an approximate triangle inequality.

######  Definition 6.4 (Approximate pseudometric).

We call a loss function $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$ a
$c$-approximate pseudometric if for all triples $y_{1},y_{2},y_{3}\in Y$:

$\ell(y_{1},y_{3})\leq c(\ell(y_{1},y_{2})+\ell(y_{2},y_{3})).$

Approximate pseudometrics are natural choices for loss functions in practice
and capture a broad set of scenarios including finite-range losses and
standard setups such as $\ell_{p}$-regression, and have seen some previous
study in the literature [46]. By modifying the first step of our reduction to
take discretization into account and leveraging the approximate triangle
inequality in the second, we prove that discrete learnability and $c$-agnostic
learnability are equivalent under $c$-approximate pseudometrics.

######  Theorem 6.5.

Let $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$ be a bounded $c$-approximate
pseudometric. Then the following are equivalent for all
$(\mathscr{D},X,H,\ell)$:

  1. 1.

$(\mathscr{D},X,H,\ell)$ is discretely-learnable.

  2. 2.

$(\mathscr{D},X,H,\ell)$ is $c$-agnostically learnable.

###### Proof.

The proof is similar to Theorem 5.3. We first show the forward direction.
Assume $(\mathscr{D},X,H,\ell)$ is discretely-learnable. Fix
$\varepsilon^{\prime}=\frac{\varepsilon}{4c^{2}c_{1}}$ (where $c_{1}$ is the
constant from Definition 6.3), and let $H_{\varepsilon^{\prime}}$ be a
learnable $\varepsilon^{\prime}$-discretization of $H$. We argue that running
LearningToCover on $H_{\varepsilon^{\prime}}$ gives the desired agnostic
learner. Since $\ell$ is bounded, it is sufficient to prove that $C(S_{U})$
contains a hypothesis $h^{\prime}$ such that
$\text{err}_{D,\ell}(h^{\prime})\leq c\cdot OPT+\varepsilon/2$. Empirical risk
minimization then works as in the finite case.

Let $h_{OPT}\in H$ be an optimal hypothesis. Since $H_{\varepsilon^{\prime}}$
is a discretization of $H$, there exists $h^{\varepsilon^{\prime}}_{OPT}\in
H_{\varepsilon^{\prime}}$ such that:

$\forall x\in
X:\ell(h_{OPT}(x),h^{\varepsilon^{\prime}}_{OPT}(x))<\varepsilon^{\prime}.$

Further, by the guarantees of discrete learnability, with probability at least
$1-\delta/2$ there exists $h^{\prime}\in C(S_{U})$ such that close to
$h^{\varepsilon^{\prime}}_{OPT}$ in the following sense:

$\underset{x\sim
D_{X}}{\mathbb{E}}[\ell(h^{\prime}(x),h^{\varepsilon^{\prime}}_{OPT}(x))]\leq
c_{1}\varepsilon^{\prime}=\frac{\varepsilon}{4c^{2}}$

Plugging in the previous observation and applying our approximate triangle
inequality, we get that $h^{\prime}$ is close to $h_{OPT}$ in the following
sense:

$\displaystyle\underset{x\sim
D_{X}}{\mathbb{E}}[\ell(h^{\prime}(x),h_{OPT}(x))]$ $\displaystyle\leq
c\left(\underset{x\sim
D_{X}}{\mathbb{E}}[\ell(h^{\prime}(x),h^{\varepsilon^{\prime}}_{OPT}(x))]+\underset{x\sim
D_{X}}{\mathbb{E}}[\ell(h^{\varepsilon^{\prime}}_{OPT}(x),h_{OPT}(x))]\right)$
$\displaystyle\leq\frac{\varepsilon}{2c}$

The final step is to transfer from the marginal $D_{X}$ to the full joint
distribution of the adversary, which follows immediately from a similar
application of the approximate triangle inequality. This is the only step that
loses a factor in the OPT term:

$\displaystyle\text{err}_{D,\ell}(h^{\prime})$
$\displaystyle=\underset{(x,y)\sim D}{\mathbb{E}}[\ell(h^{\prime}(x),y)]$
$\displaystyle\leq c\left(\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h^{\prime}(x),h_{OPT}(x))]+\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h_{OPT}(x),y)]\right)$ $\displaystyle\leq c\cdot
OPT+\varepsilon/2$

as desired.

We now prove the reverse direction, which is essentially immediate. Assume the
existence of a $c$-agnostic learner for $(\mathscr{D},X,H,\ell)$. Given a
discretization $H_{\varepsilon}$, we want to show
$(\mathscr{D},X,H_{\varepsilon},\ell)$ is learnable to within
$c_{1}\varepsilon$ error for some $c_{1}>0$. This is achieved simply by
running the agnostic learner on $(\mathscr{D},X,H_{\varepsilon},\ell)$. Since
$H_{\varepsilon}$ is “always useful”, every $h\in H_{\varepsilon}$ is
$\varepsilon$-close to some $h^{\prime}\in H$ in the sense that:

$\forall x\in X:\ell(h^{\prime}(x),h(x))\leq\varepsilon.$

In particular, this means that for any choice of $h$ by the adversary there
exists $h^{\prime}\in H$ with low error:

$\text{err}_{D,\ell}(h^{\prime})=\mathbb{E}[\ell(h^{\prime}(x),h(x))]\leq\varepsilon.$

As a result, running the $c$-agnostic learner for $(\mathscr{D},X,H,\ell)$
returns a hypothesis of at most $(c+1)\varepsilon$ error with high
probability. ∎

It is worth noting that bounded loss is not really necessary for Theorem 6.5.
More generally we can require that $(\mathscr{D},X,H,\ell)$ is “finitely
learnable” in the sense that for all finite subsets $H^{\prime}\subset H$,
$(\mathscr{D},X,H^{\prime},\ell)$ is agnostically learnable. When $\ell$ is
bounded, this is true for any finite class by empirical risk minimization.

It is also worth noting that various modifications to the definition of loss
(e.g. defining loss between hypotheses rather than on $Y$ directly) will
continue to work with the above. Similarly, there are various cases when one
can get better than $c\cdot OPT$ accuracy for a $c$-approximate pseudometric,
generally by instead optimizing over some surrogate loss function. For
instance, if a simple transformation of the loss gives a
$c^{\prime}$-approximate pseudometric for $c^{\prime}<c$, then one can
generally learn up to $c^{\prime}\cdot OPT$.171717This does require that $OPT$
is bounded. As an example, note that while square loss
$\ell_{2}(x,y)=(x-y)^{2}$ is a 2-approximate pseudometric, taking
$\sqrt{\text{err}_{D,\ell_{2}}}$ gives a true metric between hypotheses. As a
result, as long as $OPT$ is bounded, we can get truly agnostic learning by
optimizing $\sqrt{\text{err}_{D,\ell_{2}}}$ instead. This strategy works for
any polynomial loss, such as $\ell_{p}(x,y)=|x-y|^{p}$.

On the other hand, outside of these special cases, Theorem 6.5 is tight: there
exist $c$-approximate pseudometric loss functions which cannot be
$c^{\prime}$-agnostically learned for any $c^{\prime}<c$. The argument is
similar to Proposition 6.1, but requires a bit more care.

######  Proposition 6.6.

There exists a discretely-learnable class over a $c$-approximate pseudometric
that is not $c^{\prime}$-agnostically learnable for any $c^{\prime}<c$.

###### Proof.

The proof is similar to Proposition 5.4. We consider the same instance space
$X=\mathbb{N}$ and hypothesis class $H$:

$\displaystyle H=\\{h:h(x)=(0,\cdot)\leavevmode\nobreak\
\forall\leavevmode\nobreak\ x\in X\\}.$

The loss function $\ell:Y\times Y\to\\{0,1,c\\}$ is also the same, but
extended to the larger domain $Y=\mathbb{N}^{2}$:

$\displaystyle\ell((b_{1},r_{1}),(b_{2},r_{2}))=\begin{cases}0&b_{1}=b_{2}\\\
1&b_{1}\neq b_{2}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
r_{1}=r_{2}\\\ c&\leavevmode\nobreak\ \text{otherwise}.\end{cases}$

As before, note that $(X,H,\ell)$ is trivially realizably learnable by always
returning any $h\in H$, $\ell$ is a $c$-psuedometric by definition, and for
any labeling $f:X\to Y$ there exists $h\in H$ such that for all distributions
$D$:

$OPT\leq err_{D,f}(h)\leq 1.$

We now show that the class $(X,H,\ell)$ is only $c$-agnostically learnable.
Since $OPT\leq 1$, it suffices to show that for every $m\in\mathbb{N}$, large
enough $n\in\mathbb{N}$, and randomized algorithm $\mathcal{A}$ on $m$
samples, there exists a labeling $f:X\to Y$ and a marginal distribution
$D_{X}$ such that:

$\displaystyle\mathbb{E}_{S\sim D^{m}_{X}}\mathbb{E}_{x\sim
D_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x))]\geq\Big{(}1-\frac{1}{n}\Big{)}^{3}c.$
(2)

For $n\geq\frac{1}{1-(1-(c-c^{\prime})/c)^{1/3}}$, applying Markov’s
inequality to Equation 2 implies that $\mathcal{A}$ has error at least
$c^{\prime}$ with constant probability.

For simplicity, we now restrict our attention to the marginal $D_{X}$ which is
uniform over the set $[k]$ for some $k\in\mathbb{N}$ to be fixed. By Yao’s
minimax principle, its enough to prove that there exists a _distribution_
$\mu$ _over functions_ $f:[k]\to[n]^{2}$ such that any _deterministic_
algorithm $\mathcal{A}$ the following holds

$\displaystyle\mathbb{E}_{f\sim\mu}\mathbb{E}_{S\sim
D^{m}_{X}}\mathbb{E}_{x\sim
D_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x))]\geq\Big{(}1-\frac{1}{n}\Big{)}^{3}c.$

We now show that the above holds for $\mu$ being uniform over all functions
from $[k]$ to $[n]^{2}$ when $k>\frac{2m}{\ln(n/(n-1))}$. Similar to
Proposition 5.4, we have that

$\displaystyle\mathbb{E}_{x\sim D_{X}}\mathbb{E}_{f\sim\mu}\mathbb{E}_{S\sim
D^{m}_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x))]\geq\mathbb{E}_{x\sim
D_{X}}\Big{[}\Pr_{S\sim D^{m}_{X}}[x\notin
S]\cdot\Big{(}1-\frac{1}{n}\Big{)}^{2}\cdot c\Big{]},$

since no matter the assignment $\mathcal{A}$ gives to $x\notin S$, it will be
wrong on both coordinates with probability $(1-1/n)^{2}$ over the randomness
of $\mu$. The result follows by noting that for every $x\in[k]$

$\displaystyle\Pr_{S\sim D^{m}_{X\times f(X)}}[(x,\cdot)\notin
S]=\Big{(}1-\frac{1}{k}\Big{)}^{m}\geq 1-\frac{1}{n}$

since $1-x\geq\exp\\{-x/(1-x)\\}$, and we have assumed
$k>\frac{2m}{\ln(n/(n-1))}$ and $n>1$. Therefore, we get that

$\displaystyle\mathbb{E}_{x\sim D_{X}}\mathbb{E}_{f\sim\mu}\mathbb{E}_{S\sim
D^{m}_{X}}[\ell(\mathcal{A}(S,f(S))(x),f(x))]\geq\Big{(}1-\frac{1}{n}\Big{)}^{3}c$

which completes the proof. ∎

###  6.2 Sub-sampling: Malicious Noise

Now that we’ve seen how to handle practical problems like regression over
infinite label spaces, we’ll discuss a technique that helps handle data
corruption and data-dependent assumptions: sub-sampling. The main idea is as
follows. Say that the original unlabeled sample we draw is, in some sense,
partially corrupted: perhaps an adversary has changed some fraction of
examples (malicious noise), or some portion of the sample is un-realizable for
a concept in the class (robust and partial learning). In either case, there
generally exists a core subset of “clean” samples that we can use to recover
the guarantees of LearningToCover. Since we cannot necessarily identify these,
the idea is to run LearningToCover over enough subsets of the unlabeled sample
that we find a clean subsample with high probability. In this section we’ll
discuss the application of this technique in detail to Kearns and Li’s [25]
well-studied malicious noise model. In the appendix, we discuss applications
to recently popular adversarially robust (Appendix B) and partial learning
(Appendix C) models.

To start, let’s recall the standard malicious noise model. In this variant of
PAC learning, instead of having access to the standard sample oracle from the
adversary’s distribution $D$ over $X\times Y$, we have access to a malicious
oracle $\mathcal{O}_{M}(\cdot)$ which, with probability $\eta$, outputs an
adversarially chosen pair $(x,y)$, and otherwise samples from $D$ as usual.

######  Definition 6.7 (PAC-learning with Malicious Noise).

We call $(X,H,\mathscr{D},\ell)$ (agnostically)
$(\varepsilon,\delta)$-learnable with malicious noise at rate
$\eta=\eta(\varepsilon)$ if there exists an algorithm $\mathcal{A}$ and
function $m=m_{\text{mal}}(\varepsilon,\delta)$ such that for all
$\varepsilon,\delta>0,$ and distributions $D$ over $X\times Y$ satisfying:

  1. 1.

The marginal $D_{X}\in\mathscr{D}$,

$\mathcal{A}$ outputs a good hypothesis with high probability over samples
drawn from the malicious oracle of size $n(\varepsilon,\delta)$:

$\Pr_{S\sim\mathcal{O}_{M}(\cdot)^{m}}[\text{err}_{D,\ell}(\mathcal{A}(S))>OPT+\varepsilon]\leq\delta.$

where $OPT=\min_{h\in H}\\{\text{err}_{D,\ell}(h)\\}$.

In other words, malicious noise essentially gives a worst-case formalization
of the idea that an $\eta$-fraction of the learner’s data is (adversarial)
garbage.

Let’s now formalize the argument above: modifying LearningToCover to run over
subsamples gives a sample-efficient algorithm for learning with malicious
noise. For readability, we’ll (somewhat informally) restate the algorithm with
this change.

Input: Realizable PAC-Learner $\mathcal{A}$, Accuracy Parameter
$\varepsilon<1/2$, Noise Parameter $\eta<\frac{\varepsilon}{1+\varepsilon}$,
Unlabeled Sample Oracle $\mathcal{O}_{U}$, Labeled Sample Oracle
$\mathcal{O}_{L}$

Algorithm:

  1. 1.

Draw an unlabeled sample $S_{U}\sim\mathcal{O}_{U}$, and labeled sample
$S_{L}\sim\mathcal{O}_{L}$.

  2. 2.

Run LearningToCover over all
$S\in(S_{U})_{\eta^{\prime}}\coloneqq\\{S\subseteq
S_{U}:|S|=\lfloor\left(1-\eta^{\prime}\right)|S_{U}|\rfloor\\}$, where:

$\eta^{\prime}=\frac{3\eta+\varepsilon/(1-\varepsilon)}{4}.$

  3. 3.

Return the hypothesis in
$C(S_{U})\coloneqq\underset{S\in(S_{U})_{\eta^{\prime}}}{\bigcup}C(S)$ with
lowest empirical error over $S_{L}$.

Algorithm 3 Malicious to Realizable Reduction

We now prove that Algorithm 3 gives an (agnostic) learner that is tolerant to
malicious noise.

######  Theorem 6.8.

Let $(\mathscr{D},X,H)$ be realizably PAC-learnable with sample complexity
$n(\varepsilon,\delta)$. Then for any
$\eta<\frac{\varepsilon}{1+\varepsilon}$, Algorithm 3 is an agnostic learner
for $(\mathscr{D},X,H)$ tolerant to $\eta$ malicious noise. Furthermore
letting $\Delta=\frac{\varepsilon}{1+\varepsilon}-\eta$ and
$\beta=\left(1+\frac{\eta}{\Delta}\right)\log\left(\frac{1}{\eta}\right)$, its
sample complexity is at most:

$m_{\text{mal}}(\varepsilon,\delta)\leq
O\left(\beta\frac{n(\Delta/4,\delta/4)}{\Delta}+\frac{\log\left(\Pi_{H}\left(O\left(n(\Delta/2,\delta/2)+\frac{\eta^{2}\log(1/\delta)}{\Delta^{2}}\right)\right)\right)+\log(1/\delta)}{\Delta^{2}}+\beta\frac{\eta^{2}\log(1/\delta)}{\Delta^{3}}\right)$

where we’ve assumed $\varepsilon<1/2$ for simplicity.

###### Proof.

To start, we’ll review for completeness a fairly standard analysis of
empirical risk minimization under malicious noise. Assume for the moment that
the output of LearningToCover, $C(S_{U})$, contains a hypothesis $h^{\prime}$
satisfying $err(h^{\prime})\leq OPT+\beta_{1}$. Say we draw $M$ labeled
samples for the ERM step, and an $\eta^{\prime}=\eta+\beta_{2}$ fraction are
corrupted by the adversary. For large enough $M$, we can assume by a Chernoff
and union bound that the empirical loss of every hypothesis returned by
LearningToCover is at most some $\beta_{3}$ away from its true loss on the un-
corrupted portion of $M$ (we will make all these assumptions formal in a
moment). Given these facts, notice that the empirical loss of $h^{\prime}$ on
$M$ is at most:

$err_{M}(h^{\prime})\leq(1-\eta^{\prime})(OPT+\beta_{1}+\beta_{3})+\eta^{\prime}.$

On the other hand, the empirical error of any $h_{\varepsilon}\in H$ whose
true error is greater than $OPT+\varepsilon$ is at least:

$err_{M}(h)>(1-\eta^{\prime})(OPT+\varepsilon-\beta_{3}).$

To ensure that our ERM works, it is enough to show that for any such $h$,
$err_{M}(h)>err_{M}(h^{\prime})$. A simple calculation shows that this is
satisfied as long as $\beta_{1}+2\beta_{3}\leq\varepsilon$ and
$\beta_{1}+\beta_{2}+2\beta_{3}\leq\Delta$. Setting
$\beta_{1}=\beta_{2}=\beta_{3}=\Delta/4$ gives the desired result.

It is left to argue that our assumptions above hold with high probability.
First, note that by a Chernoff bound, the probability that
$\eta^{\prime}\geq\eta+\Delta/4$ on a set of $M$ samples is at most
$e^{-c\left(\frac{\Delta}{\eta}\right)^{2}M}$ for some $c>0$, so this occurs
with high probability as long as
$M\geq\Omega(\log(1/\delta)\eta^{2}/\Delta^{2})$. Similarly, the empirical
error of every hypothesis in $C(S_{U})$ on the remaining clean samples will be
within $\Delta/4$ of its true error as long as
$M\geq\Omega(\log(|C(S_{U})|/\delta)\eta^{2}/\Delta^{2})$.

It is then left to show that $C(S_{U})$ contains a hypothesis of error at most
$OPT+\Delta/4$. To show this, it is enough to ensure that we run
LearningToCover over a clean subsample of size at least $n(\Delta/4,\delta/4)$
with high probability. If we draw
$|S_{U}|=O\left(\frac{n(\Delta/4,\delta/4)}{1-\eta^{\prime}}+\log(1/\delta)\frac{\eta^{2}}{\Delta^{2}}\right)$
unlabeled samples, a similar Chernoff bound to the above promises that at most
an $\eta^{\prime}$ fraction are corrupted with high probability, and therefore
that at least $n(\Delta/4,\delta/4)$ remain un-corrupted. Running
LearningToCover over all subsets of size $(1-\eta^{\prime})|S_{u}|$ then gives
the desired result. The sample complexity bound follows from choosing $M$
large enough to satisfy the above conditions along with the fact that
$|C(S_{U})|\leq{n\choose(1-\eta^{\prime})n}\Pi_{H}(n)$. ∎

It’s worth noting that the error tolerance of Theorem 6.8 is tight. In their
original introduction of malicious noise, Kearns and Li [25] proved that for
most non-trivial concept classes, no PAC-learner can be tolerate
$\frac{\varepsilon}{1+\varepsilon}$ malicious noise. Theorem 6.8 also extends
to other scenarios we’ve seen so far such as arbitrary loss over finite label
classes and approximate pseudometrics. The proof remains mostly the same,
though the optimal error tolerance may differ.

Since our agnostic model restricts the adversary to choosing a distribution
whose marginal lies in the original family, Theorem 6.8 provides the first
insight on robustness against an adversary who can corrupt the underlying data
as well as the labels. One might wonder whether this result can be pushed
further: is it possible to be robust against an adversary who can corrupt the
marginal over $X$ in some stronger sense? Unfortunately, the answer is no:
malicious noise is necessarily the most distributional corruption we can
handle. Let’s look at two basic lower bounds to see why. First, we’ll consider
an adversary who can remove a portion of the learner’s sample.

######  Proposition 6.9.

For any $\delta>0$, there exists a class $(\mathscr{D},X,H)$ which is
realizably PAC-learnable, but not learnable under an adversary who can remove
a $\delta$ fraction of the learner’s sample.

###### Proof.

This follows from a result of Dudley, Kulkarni, Richardson, and Zeitouni [20]
that there exists an unlearnable class $(\mathscr{D},X,H)$ such that for some
$n(\varepsilon,\delta)$, $(D,X,H)$ is learnable in $n(\varepsilon,\delta)$
samples for every $D\in\mathscr{D}$. The lower bound then follows simply from
adding an extra unique identifying point $x_{D}$ to $X$ for every distribution
$D$, and modifying each $D\in\mathscr{D}$ to have $\Theta(\delta)$ support on
$x_{D}$. This modified class is clearly learnable, since after drawing
$O(1/\delta)$ samples, the learner will draw $x_{D}$ and identify the
distribution $D$ with good probability. However, the class is not learnable
under an adversary who removes points, since with high probability the
adversary can completely remove any mention of $x_{D}$ from the learner’s
sample, reducing to the original unlearnable class $(\mathscr{D},X,H)$. ∎

An adversary who can add samples is similarly powerful. Consider a model in
which the adversary, after choosing a marginal distribution and labeling, sees
the learner’s sample ahead of time and may add an additional $\gamma$ fraction
of correctly labeled elements.181818For simplicity, we’ll assume the adversary
is restricted to picking a marginal distribution and labeling rather than any
joint distribution over $X\times Y$. While the realizable setting is largely
unaffected by such an adversary (as any non-optimal hypothesis will still see
some bad example), even near-trivial concept classes cannot be agnostically
learned.

######  Proposition 6.10.

There exists a class $(X,H)$ which for any $\gamma>0$ is realizably but not
agnostically learnable under an adversary who can add a $\gamma$ fraction of
correctly labeled points to the learner’s sample.

###### Proof.

Let $X=\\{x,x_{1},x_{2}\\}$ and $H=\\{h_{1},h_{2}\\}$ be any class such that
$h_{1}(x)=h_{2}(x)$, but $h_{1}(x_{i})\neq h_{2}(x_{i})$ for $i=1,2$. In the
realizable setting, note that a single labeled example on $x_{1}$ or $x_{2}$
exactly determines the hypothesis. As long as there is less than
$1-\varepsilon$ mass on $x$, the learner will draw such a sample after
$O(1/\varepsilon)$ samples with good probability. Further, if the mass on $x$
is at least $1-\varepsilon$, then $h_{1}$ and $h_{2}$ are both valid outputs.
As a result, any ERM is a valid PAC-learner. Since adding correctly labeled
examples can only help this learner, the class remains realizably learnable
under an adversary who can add an arbitrary number of clean samples.

In the agnostic setting, consider an adversary who chooses a labeling $f$ such
that $f(x)=h_{1}(x)=h_{2}(x)$, $f(x_{1})=h_{1}(x_{1})$, and
$f(x_{2})=h_{2}(x_{2})$. The optimal hypothesis $h_{OPT}$ is then decided by
the amount of mass on $x_{1}$ and $x_{2}$ in the marginal distribution. Namely
if the adversary chooses a distribution $D$ over $\\{x,x_{1},x_{2}\\}$, the
optimal error is $\min\\{D(x_{1}),D(x_{2})\\}$. The idea is then to note that
for $\gamma^{\prime}\leq\gamma/4$, the learner cannot distinguish between the
two following distributions:

$D_{1}(x_{1})=c_{1}\gamma^{\prime},D_{1}(x_{2})=(1-c_{1})\gamma^{\prime}$

and

$D_{2}(x_{1})=(1-c_{1})\gamma^{\prime},D_{2}(x_{2})=c_{1}\gamma^{\prime}$

where $1/2>c_{1}>0$ is some small constant. Informally, if the two
distributions are indistinguishable, any learner will always incur error of
around $\frac{(1-c_{1})\gamma^{\prime}}{2}$, whereas OPT is
$c_{1}\gamma^{\prime}$ for both distributions.

Let’s now give the formal argument. By Yao’s Minimax Principle it is enough to
prove there is a strategy over distributions such that any deterministic
learner has high error. In particular, if we can prove that the expected error
is at least $3\cdot OPT$, then $\Pr[\text{error}\geq 2\cdot OPT]\geq OPT$.
Since OPT is just some constant $c_{1}\gamma^{\prime}$ (dependent only on
$\gamma$), this is sufficient to prove the result. Moving on, consider the
strategy in which the adversary chooses the labeling described above, and
chooses each marginal ($D_{1}$ or $D_{2}$) with probability $1/2$. We’ll break
our analysis into two cases dependent on the sample complexity of the learner.
If the learner uses $O(1/\gamma^{\prime})$ examples, then there is a constant
probability of drawing a sample only consisting of the point $x$. Let
$f^{\prime}$ be the hypothesis returned by the deterministic learner on this
sample. By construction, $f^{\prime}$ must disagree with either $h_{1}$ or
$h_{2}$ on $x_{1}$ or $x_{2}$. Assume $f^{\prime}$ differs on $h_{1}(x_{1})$
(the other cases will follow similarly). When the distribution is $D_{2}$,
$f^{\prime}$ has error at least $(1-c_{1})\gamma^{\prime}$. Since this occurs
with constant probability _independent_ of the choice of $c_{1}$, choosing
$c_{1}$ sufficiently small leads to an expected error of at least
$3c_{1}\gamma^{\prime}$ as desired.

On the other hand, when there are $n=\Omega(1/\gamma^{\prime})$ samples, we
claim that the adversary can force the following sample to occur with constant
probability: $2\gamma^{\prime}n$ instances of $x_{1}$ and $x_{2}$, and
$(1+\gamma)n-4\gamma^{\prime}n$ instances of $x$. This follows from the fact
that for the appropriate choice of constant for $n$, a Chernoff bound gives
that both $x_{1}$ and $x_{2}$ occur at most $2\gamma^{\prime}n$ times with
constant probability. Since the adversary is allowed to add $\gamma n\geq
4\gamma^{\prime}n$ arbitrary examples, they can add instances of $x_{1}$,
$x_{2}$, and $x$ until the above sample is achieved. The remainder of the
argument is then the same as the previous case, as any learner response on
this sample will incur similarly high expected error. ∎

It is also reasonable to consider distributional corruption in the semi-
supervised setting, where the unlabeled and labeled data-sets might have
different underlying distributions. We discuss this model in Section 6.4.

###  6.3 Replacing ERM: Semi-Private Learning

So far we have focused on property generalization for two forms of noise-
tolerance—agnostic learning and learning with malicious noise. In this
section, we’ll show how to use Algorithm 1 to generalize a broader spectrum of
finitely-satisfiable properties through replacing the ERM process with a
generic finite learner with the desired property. Our prototypical example
will be privacy, which is well known to be finitely-satisfiable via McSherry
and Talwar’s [27] exponential mechanism. To start, we’ll cover a few basic
privacy definitions.

######  Definition 6.11 (Differential Privacy).

A learning algorithm $\mathcal{A}$ is said to be $\alpha$-differentially
private if for all neighboring inputs $S,S^{\prime}$ which differ on a single
example:

$\Pr[\mathcal{A}(S)\in T]\leq e^{\alpha}\Pr[\mathcal{A}(S^{\prime})\in T],$

for all measurable events $T$ in the range of $\mathcal{A}$.

The exponential mechanism is one of the most widely used techniques in
privacy. Informally, the algorithm allows for differentially private selection
of a “good” choice from a finite set of objects (potential hypotheses in our
case). More formally, let $s:(X\times Y)^{*}\times H\to\mathbb{R}$ be a
“score” function, and define “sensitivity” $\Delta_{s}$ to be

$\Delta_{s}=\max_{h\in H}\max_{S,S^{\prime}}|s(S,h)-s(S^{\prime},h)|$

where $S,S^{\prime}$ are two neighbouring datasets. The exponential mechanism
selects an item with a good score with high probability, while maintaining
privacy.

######  Definition 6.12 (Exponential Mechanism [27]).

The exponential mechanism $M_{E}$ on inputs $S,H,s$ with privacy parameter
$\alpha$ selects and outputs $h\in H$ with probability

$\frac{\exp(\frac{\alpha s(S,h)}{2\Delta})}{\sum_{h^{\prime}\in
H}\exp(\frac{\alpha s(S,h^{\prime})}{2\Delta})}.$

It is well known that the exponential mechanism leads to a private learner for
finite hypothesis classes under bounded loss.

######  Theorem 6.13 (Theorem 3.4 [47]).

Let $(\mathscr{D},X,H,\ell)$ be a finite class with a bounded loss function.
Then the sample complexity of $\alpha$-differentially private learning
$(\mathscr{D},X,H,\ell)$ is at most:

$n_{pri}(\alpha,\varepsilon,\delta)\leq
O\left(\log\left(\frac{|H|}{\delta}\right)\max\\{\varepsilon^{-2},\varepsilon^{-1}\alpha^{-1}\\}\right).$

We note that [47, Theorem 3.4] only considers classification loss, but the
extension to bounded loss is immediate. Unfortunately, even with the power of
the exponential mechanism, privacy is a very restrictive condition in the
general PAC framework, since we’re most often interested in infinite
hypothesis sets. Indeed even improper private learning requires finiteness of
a highly restrictive measure known as representation dimension [40], which can
be infinite for classes of VC dimension $1$. As a result, the past decade has
seen the introduction of a number of weaker, more practical definitions of
privacy. In this section we’ll focus on a model introduced in 2013 by Beimel,
Nissim, and Stemmer [17] called semi-private learning.

######  Definition 6.14 (Semi-Private Learning).

We call a class $(\mathscr{D},X,H,\ell)$ semi-private PAC-Learnable if there
exists an algorithm $\mathcal{A}$ and two functions
$n_{\text{pub}}=n_{\text{pub}}(\varepsilon,\delta,\alpha)$ and
$n_{\text{pri}}=n_{\text{pri}}(\varepsilon,\delta,\alpha)$ such that for all
$\varepsilon,\delta>0$ and distributions $D$ over $X\times Y$ whose marginal
$D_{X}$ is in $\mathscr{D}$, $\mathcal{A}$ satisfies the following:

  1. 1.

$\mathcal{A}$ outputs a good hypothesis with high probability:

$\Pr_{S_{U}\sim D_{X}^{n_{\text{pub}}},S_{L}\sim
D^{n_{\text{pri}}}}[\text{err}_{D,\ell}(\mathcal{A}(S_{U},S_{L}))>OPT+\varepsilon]\leq\delta.$

  2. 2.

$\mathcal{A}$ is semi-private. That is for all $S_{U}\in X^{n_{\text{pub}}}$:

$\mathcal{A}(S_{U},\cdot)\text{ is }\alpha\text{-differentially private}.$

In other words, semi-private learning offers a model for applications where
labeled data is sensitive, but some (perhaps opt-in) users might not care
about their participation itself being released. Unlike standard private
learning, distribution-free semi-private classification is known to be
characterized by VC dimension, just like realizable PAC-learning [17]. The
best sample complexity bounds are due to Alon, Bassily, and Moran (ABM) [18],
who use uniform convergence to build a uniform cover for $H$ from unlabeled
data, and then apply the exponential mechanism to the resulting cover.

Due to their reliance on uniform convergence, ABM’s techniques fail in the
more general settings we consider. Further, their use of uniform covers
results in sub-optimal public sample complexity even for distribution-free
classification. We prove in Appendix G that these objects require
asymptotically more samples than non-uniform covers (at least in the
distribution-family model), and therefore cannot be used to achieve optimal
semi-private learning. We circumvent both of these issues by appealing
directly to a realizable learner to build a weaker non-uniform cover. For
readability, we first restate the algorithm here.

Input: Realizable PAC-Learner $\mathcal{A}$, Unlabeled Sample Oracle
$\mathcal{O}_{U}$, Labeled Sample Oracle $\mathcal{O}_{L}$

Algorithm:

  1. 1.

Draw an unlabeled sample $S_{U}\sim\mathcal{O}_{U}$, and labeled sample
$S_{L}\sim\mathcal{O}_{L}$.

  2. 2.

Run LearningToCover over $S_{U}$ to get $C(S_{U})$.

  3. 3.

Return the hypothesis in $C(S_{U})$ given by applying the exponential
mechanism with respect to $S_{L}$.

Algorithm 4 Semi-Private to Realizable Reduction

We prove that Algorithm 4 gives a semi-private agnostic learner in the
distribution-family setting.

######  Theorem 6.15 (PAC-learning implies Semi-Private Learning).

Let $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$ be a bounded $c$-approximate
pseudometric. Then the following are equivalent for all triples
$(\mathscr{D},X,H,\ell)$:

  1. 1.

$(\mathscr{D},X,H,\ell)$ is discretely-learnable

  2. 2.

$(\mathscr{D},X,H,\ell)$ is $c$-agnostically, semi-private learnable.

###### Proof.

The proof is essentially the same as Theorem 6.5. The only difference in the
argument is to replace the generic ERM learner over the output of
LearningToCover with the exponential mechanism [47]. ∎

Let’s now take a look at what Theorem 6.15 implies about the special case of
distribution-free classification.

######  Corollary 6.16.

Let $(X,H)$ be a class of VC-dimension $d$ with sample complexity
$n(\varepsilon,\delta)$. The sample complexity of (agnostic) semi-private
learning $(X,H)$ is at most:

$n_{\text{pub}}(\varepsilon,\delta,\alpha)\leq n(\varepsilon/2,\delta/2)$

and

$n_{\text{pri}}(\varepsilon,\delta,\alpha)\leq
O\left(\left(d\log\left(\frac{n(\varepsilon/2,\delta/2)}{d}\right)+\log\left(\frac{1}{\delta}\right)\right)\max\\{\varepsilon^{-2},\varepsilon^{-1}\alpha^{-1}\\}\right).$

Further, the sample complexity of improperly (agnostic) semi-private learning
$(X,H)$ is

$n_{\text{pub}}(\varepsilon,\delta,\alpha)\leq
O\left(\frac{d+\log(1/\delta)}{\varepsilon}\right)$

and

$n_{\text{pri}}(\varepsilon,\delta,\alpha)\leq
O\left(\left(d\log\left(\frac{1}{\varepsilon}\right)+\log\left(\frac{1}{\delta}\right)\right)\max\\{\varepsilon^{-2},\varepsilon^{-1}\alpha^{-1}\\}\right).$

###### Proof.

LearningToCover uses $n(\varepsilon/2,\delta/2)$ samples by definition. In the
improper case, Hanneke showed that $n(\varepsilon/2,\delta/2)\leq
O\left(\frac{d+\log(1/\delta)}{\varepsilon}\right).$ Since the class has VC
dimension $d$, the size of the resulting cover is at most $(e\cdot
n(\varepsilon/2,\delta/2)/d)^{d}$, and the private sample complexity bound
then follows from Theorem 6.13. ∎

This improves over the recent upper bound of ABM who showed that

$n_{\text{pub}}(\varepsilon,\delta,\alpha)\leq
O\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right).$

In fact, for constant $d$ and $\delta$, Corollary 6.16 completely resolves the
unlabeled sample complexity of semi-private learning, as ABM [18] prove a
matching lower bound.

######  Theorem 6.17 (Public Lower Bound [18]).

Every class that is not privately learnable requires at least
$\Omega(1/\varepsilon)$ unlabeled samples to learn in the semi-private model
under classification error.

On the other hand, we note that the private sample complexity remains off by a
log factor from the best known lower bounds of Chaudhari and Hsu [28].

######  Theorem 6.18 (Private Lower Bound [28]).

There exist classes of VC dimension $O(1)$ which require at least:

$n_{\text{pri}}(\varepsilon,\delta,\alpha)\geq\Omega\left(\max\\{\varepsilon^{-2},\varepsilon^{-1}\alpha^{-1}\\}\right)$

private samples to learn.

While we have now resolved the public sample complexity of improper learning,
it remains an interesting open problem for the proper regime where certain
adversarial examples are known to require an extra $\log(1/\varepsilon)$
factor in the standard PAC sample complexity [48, 49]. We conjecture that
Theorem 6.15 should still be tight in this setting: namely that the unlabeled
semi-private sample complexity should always be at least the realizable PAC
sample complexity.

######  Conjecture 6.19.

Let $(X,H)$ be a hypothesis class which is not privately learnable. Then the
realizable sample complexity of $(X,H)$ lower bounds the unlabeled sample
complexity of proper semi-private learning:

$n_{\text{pub}}(\varepsilon,1/2)\geq\Omega(n(\varepsilon,1/2)).$

###  6.4 Changing the Base Model: Covariate Shift

One issue with semi-supervised models like semi-private learning is that, in
practice, the distribution over unlabeled data probably won’t match the
labeled data exactly. In this section, we’ll talk about a final modification
to our reduction to tackle such scenarios and more generally to extend
property generalization beyond the realizable PAC setting: replacing the base
learner. In fact, we already saw this strategy used to a lesser extent in
Section 6.1, where we replaced our standard realizable base learner with a
discrete learner. Here we’ll look at an application in which we assume our
initial learner is robust to _covariate shift_ [50], meaning that even if the
distribution underlying the data shifts between train and test time, the
algorithm will continue to perform well. This stronger assumption will allow
us to build semi-private learners that can handle corruption between the
public and private databases. To start, let’s formalize covariate shift in the
distribution-family model.

######  Definition 6.20 (Covariate Shift).

Let $(\mathscr{D},X,H,\ell)$ be any class, and for every $\varepsilon>0$ let
$C_{\varepsilon}$ be a “covariate-shift” function that maps every
$D\in\mathscr{D}$ to some family of distributions over $X$. Given any
distribution $D\in\mathscr{D}$ and any $h\in H$, let the error of a potential
labeling be given by its worst-case error over $C_{\varepsilon}(D)$, that is:

$\text{CS-err}_{D\times h,\ell,\varepsilon}(c)=\max_{D^{\prime}\in
C_{\varepsilon}(D)}\left\\{\underset{{x\sim
D^{\prime}}}{\mathbb{E}}[\ell(c(x),h(x))]\right\\}.$

We say that $(\mathscr{D},X,H,\ell)$ is realizably learnable under covariate
shift $C=\\{C_{\varepsilon}\\}$ if there exists an algorithm $\mathcal{A}$ and
function $n=n(\varepsilon,\delta)$ such that for all $\varepsilon,\delta>0$,
$D\in\mathscr{D}$, and $h\in H$:

$\Pr_{S\sim D^{n}}\left[\text{CS-err}_{D\times
h,\ell,\varepsilon}(\mathcal{A}(S,h(S)))>\varepsilon\right]\leq\delta.$

We call such a learner robust to covariate shift.

We emphasize that in the above definition, the covariate shift family _scales
with the error parameter $\varepsilon$_. This is a bit different than
Shimodaira’s original definition [50], but is a natural choice in our context
since we consider algorithms which only use access to the original source
distribution (sometimes called “conservative domain adaptation” [51]). In this
setting, we’d expect that as we demand higher accuracy, the amount of
covariate shift we can tolerate will decrease. Indeed in the agnostic model,
it’s clear this scaling is necessary by a similar argument to Proposition
6.10.

The key observation to apply learning under covariate shift in our reduction
is simply to notice that the non-uniform cover output by LearningtoCover must
contain a hypothesis close to optimal under any shifted distribution in
$C_{\varepsilon}(D)$. This can then be used to analyze any semi-supervised
model where the marginal of the labeled distribution may be corrupted from $D$
to any distribution in $C_{\varepsilon}(D)$. In this section, we’ll again
focus on the setting of semi-private learning. First, let’s formalize what it
means to be semi-private learnable under covariate shift.

######  Definition 6.21 (Semi-Private Learning under Covariate Shift).

We call a class $(\mathscr{D},X,H,\ell)$ semi-private (agnostically) PAC-
Learnable under covariate shift $C=\\{C_{\varepsilon}\\}$ if there exists an
algorithm $\mathcal{A}$ and two functions
$n_{\text{pub}}=n_{\text{pub}}(\varepsilon,\delta,\alpha)$ and
$n_{\text{pri}}=n_{\text{pri}}(\varepsilon,\delta,\alpha)$ such that for all
$\varepsilon,\delta>0$ and distributions $D_{X}\in\mathscr{D}$ and
$D^{\prime}$ over $X\times Y$ whose marginal $D^{\prime}_{X}\in
C_{\varepsilon}(D_{X})$, $\mathcal{A}$ satisfies the following:

  1. 1.

$\mathcal{A}$ outputs a good hypothesis over $D^{\prime}$ with high
probability:

$\Pr_{S_{U}\sim D_{X}^{n_{\text{pub}}},S_{p}\sim D^{\prime
n_{\text{pri}}}}[\text{err}_{D^{\prime},\ell}(\mathcal{A}(S_{U},S_{p}))>OPT^{\prime}+\varepsilon]\leq\delta,$

where $OPT^{\prime}=\min_{h\in H}[\text{err}_{D^{\prime},\ell}(h)]$ is the
minimum error over the shifted distribution.

  2. 2.

$\mathcal{A}$ is semi-private. That is for all $S_{U}\in X^{n_{\text{pub}}}$:

$\mathcal{A}(S_{U},\cdot)\text{ is }\alpha\text{-differentially private}$

In other words, we’d like to recover a near-optimal hypothesis even when the
marginal distribution over private data is shifted from the public data. This
is a realistic scenario in practice, since the distribution of “opt-in” users
is likely different from the marginal over the total population. We’ll show
that this issue is solvable in the semi-private setting as long as the
analogous issue in the non-private setting (distribution shift between train
and test time) can be resolved.

######  Theorem 6.22.

Let $(\mathscr{D},X,H,\ell)$ be any class of a finite label space with loss
function satisfying the identity of indiscernibles which is realizably
learnable under covariate shift $C=\\{C_{\varepsilon}\\}$. Then
$(\mathscr{D},X,H,\ell)$ is semi-private, agnostically learnable under
covariate shift $C$ with sample complexity:

$m(\varepsilon,\delta)\leq
n(\eta_{\ell}\varepsilon,\delta/2)+O\left(\frac{\log\left(\frac{\Pi_{H}(n(\eta_{\ell}\varepsilon,\delta/2))}{\delta}\right)}{\varepsilon^{2}}\right)$

where we recall $\eta_{\ell}\geq\Omega\left(\frac{\min_{a\neq
b}(\ell(a,b))}{\max_{a\neq b}(\ell(a,b))}\right)$ is a constant depending only
on $\ell$.

###### Proof.

The proof is essentially the same as Theorem 5.3. The only difference is to
note that for all marginal distributions $D_{X}\in\mathscr{D}$ and choices of
shift $D^{\prime}_{X}\in C_{\varepsilon}(D_{X})$, the output of
LearningToCover has some $h^{\prime}$ satisfying

$\underset{x\sim
D^{\prime}_{X}}{\mathbb{E}}[\ell(h^{\prime}(x),h_{OPT^{\prime}}(x))]\leq\eta_{\ell}\varepsilon,$

where $h_{OPT^{\prime}}$ is some optimal hypothesis over the shifted
distribution $D^{\prime}$. As in the standard analysis, this is guaranteed by
including the output of the realizable learner on $h_{OPT^{\prime}}$
(robustness to covariate shift promises this output is close under
$D^{\prime}_{X}$ with high probability). The remainder of the argument is
exactly as in Theorem 6.5, with the exception of working over the shifted
distribution $D^{\prime}_{X}$ instead of $D_{X}$. ∎

We note that this result can also be extended to the more general loss
functions discussed in Section 6.1 without too much difficulty with the
appropriate definition of discrete learnability under covariate shift.

Since Theorem 6.22 is a bit abstract, let’s take a look at one concrete
application. Given a class $(X,H)$, the class-dependent total variation
distance is a metric on distributions measuring the worst case distance across
elements of $H\Delta H\coloneqq\\{h\Delta h^{\prime}:h,h^{\prime}\in H\\}$:

$TV_{H\Delta H}(D,D^{\prime})\coloneqq\max_{h\in H\Delta
H}\\{\left|D(h)-D^{\prime}(h)\right|\\}.$

It is not hard to see that any realizable learner is robust to
$O(\varepsilon)$ covariate shift in $TV_{H\Delta H}$ distance. We can then
apply Theorem 6.22 to build a robust semi-private learner.

######  Corollary 6.23.

Let $(X,H)$ be a class of VC-dimension $d$, and for every $\varepsilon>0$ and
distribution $D$ over $X$, define a coviarate shift function:

$C_{\varepsilon}(D)\coloneqq\left\\{D^{\prime}:TV_{H\Delta
H}(D,D^{\prime})\leq\varepsilon/2\right\\}.$

Then $(X,H)$ is semi-private learnable under covariate shift
$C=\\{C_{\varepsilon}\\}$ in only

$n_{\text{pub}}(\varepsilon,\delta,\alpha)\leq
O\left(\frac{d+\log(1/\delta)}{\varepsilon}\right)$

unlabeled samples and

$n_{\text{pri}}(\varepsilon,\delta,\alpha)\leq
O\left(\left(d\log\left(\frac{1}{\varepsilon}\right)+\log\left(\frac{1}{\delta}\right)\right)\max\\{\varepsilon^{-2},\varepsilon^{-1}\alpha^{-1}\\}\right)$

labeled samples.

Finally, we note again that our original learner in these results is robust to
covariate shift despite having no access to samples from the new distribution.
Unfortunately, this model does come with fairly strong lower bounds regarding
the type of covariate shifts to which it is possible to be robust [51]. One
solution to this problem is to consider a relaxed variant called (non-
conservative) domain adaptation, where the learner additionally has access to
a small number of unlabeled samples from the test-time distribution. It is
certainly possible to define an analog in the semi-private setting, but
naively the use of unlabeled data from the private distribution breaks our
reduction since privacy won’t be preserved. We leave as an open question
whether any sort of PAC-learner in the non-conservative model could imply
semi-private learners with stronger robustness to covariate shift. Some
progress has been made in this direction recently by Bassily, Moran, and Nandi
[52] for distribution-free classification of halfspaces.

## Acknowledgements

The authors would like to thank Shay Moran, Russell Impagliazzo, Omar
Montasser, and Avrim Blum for enlightening discussions. We also thank
anonymous referees for constructive feedback, and especially for pointing out
the notion of probabilistic representations and that prior work discussed in
Section 3 falls under the general framework of our reduction.

## References

  * Valiant [1984] Leslie G Valiant.  A theory of the learnable.  In _Proceedings of the sixteenth annual ACM symposium on Theory of computing_ , pages 436–445. ACM, 1984.
  * Vapnik and Chervonenkis [1974] Vladimir Vapnik and Alexey Chervonenkis.  Theory of pattern recognition, 1974.
  * Blumer et al. [1989] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the vapnik-chervonenkis dimension.  _Journal of the ACM (JACM)_ , 36(4):929–965, 1989\.
  * Haussler [1992] David Haussler.  Decision theoretic generalizations of the PAC model for neural net and other learning applications.  _Information and computation_ , 100(1):78–150, 1992.
  * Bartlett et al. [1996] Peter L Bartlett, Philip M Long, and Robert C Williamson.  Fat-shattering and the learnability of real-valued functions.  _journal of computer and system sciences_ , 52(3):434–452, 1996.
  * Benedek and Itai [1991] Gyora M Benedek and Alon Itai.  Learnability with respect to fixed distributions.  _Theoretical Computer Science_ , 86(2):377–389, 1991.
  * David et al. [2016] Ofir David, Shay Moran, and Amir Yehudayoff.  Supervised learning through the lens of compression.  _Advances in Neural Information Processing Systems_ , 29:2784–2792, 2016.
  * 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\.
  * Ben-David et al. [2009] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz.  Agnostic online learning.  In _COLT_ , volume 3, page 1, 2009.
  * Beimel et al. [2014] Amos Beimel, Kobbi Nissim, and Uri Stemmer.  Learning privately with labeled and unlabeled examples.  In _Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms_ , pages 461–477. SIAM, 2014.
  * Alon et al. [2020] Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer.  Closure properties for private classification and online prediction.  In _Conference on Learning Theory_ , pages 119–152. PMLR, 2020.
  * Long [2001] Philip M Long.  On agnostic learning with $\\{$0,*, 1$\\}$-valued and real-valued hypotheses.  In _International Conference on Computational Learning Theory_ , pages 289–302. Springer, 2001.
  * Alon et al. [2021a] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran.  A theory of PAC learnability of partial concept classes, 2021a.
  * Alon et al. [2019a] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran.  Private PAC learning implies finite littlestone dimension.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 852–860, 2019a.
  * Li et al. [2001] Yi Li, Philip M Long, and Aravind Srinivasan.  Improved bounds on the sample complexity of learning.  _Journal of Computer and System Sciences_ , 62(3):516–527, 2001.
  * Feldman et al. [2009] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami.  On agnostic learning of parities, monomials, and halfspaces.  _SIAM Journal on Computing_ , 39(2):606–645, 2009\.
  * Beimel et al. [2013a] Amos Beimel, Kobbi Nissim, and Uri Stemmer.  Private learning and sanitization: Pure vs. approximate differential privacy.  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_ , pages 363–378. Springer, 2013a.
  * Alon et al. [2019b] Noga Alon, Raef Bassily, and Shay Moran.  Limits of private learning with access to public data.  _arXiv preprint arXiv:1910.11519_ , 2019b.
  * Balcan and Blum [2010] Maria-Florina Balcan and Avrim Blum.  A discriminative model for semi-supervised learning.  _Journal of the ACM (JACM)_ , 57(3):1–46, 2010\.
  * Dudley et al. [1994] Richard M Dudley, Sanjeev R Kulkarni, T Richardson, and Ofer Zeitouni.  A metric entropy bound is not sufficient for learnability.  _IEEE Transactions on Information Theory_ , 40(3):883–885, 1994.
  * Ben-David et al. [2017] Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff.  A learning problem that is independent of the set theory zfc axioms.  _arXiv preprint arXiv:1711.05195_ , 2017.
  * Wolf [2018] Michael M Wolf.  Mathematical foundations of supervised learning, 2018.
  * Bendavid et al. [1995] S. Bendavid, N. Cesabianchi, D. Haussler, and P.M. Long.  Characterizations of learnability for classes of $\\{0,\ldots,n\\}$-valued functions.  _Journal of Computer and System Sciences_ , 50(1):74–86, 1995.
  * Montasser et al. [2021] Omar Montasser, Steve Hanneke, and Nathan Srebro.  Adversarially robust learning with unknown perturbation sets.  _arXiv preprint arXiv:2102.02145_ , 2021.
  * Kearns and Li [1993] Michael Kearns and Ming Li.  Learning in the presence of malicious errors.  _SIAM Journal on Computing_ , 22(4):807–837, 1993\.
  * Chaudhuri et al. [2006] K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar.  Learning concept classes with privacy.  _Manuscript_ , 2006.
  * McSherry and Talwar [2007] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In _48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07)_ , pages 94–103. IEEE, 2007.
  * Chaudhuri and Hsu [2011] Kamalika Chaudhuri and Daniel Hsu.  Sample complexity bounds for differentially private learning.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pages 155–186. JMLR Workshop and Conference Proceedings, 2011.
  * Vapnik and Chervonenkis [1971] V.N. Vapnik and A.Ya. Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  _Theory of Probability and Its Applications_ , 1971.
  * Natarajan [1989] B. K. Natarajan.  On learning sets and functions.  _Machine Learning_ , 4(1):67–97, 1989.
  * Daniely et al. [2015] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the ERM principle.  _Journal of Machine Learning Research_ , 16:2377–2404, 2015.
  * Kearns and Schapire [1990] Michael J. Kearns and Robert E. Schapire.  Efficient distribution-free learning of probabilistic concepts.  In _31st Annual Symposium on the Foundations of Computer Science,_ , 1990.