# Is Efficient PAC Learning Possible with an
Oracle That Responds “Yes” or “No”?

Constantinos Daskalakis
MIT CSAIL & Archimedes AI
<EMAIL_ADDRESS>Noah Golowich
MIT CSAIL
<EMAIL_ADDRESS>
(June 17, 2024)

###### Abstract

The _empirical risk minimization (ERM)_ principle has been highly impactful in
machine learning, leading both to near-optimal theoretical guarantees for ERM-
based learning algorithms as well as driving many of the recent empirical
successes in deep learning. In this paper, we investigate the question of
whether the ability to perform ERM, which computes a hypothesis minimizing
empirical risk on a given dataset, is necessary for efficient learning: in
particular, is there a weaker oracle than ERM which can nevertheless enable
learnability? We answer this question affirmatively, showing that in the
realizable setting of PAC learning for binary classification, a concept class
can be learned using an oracle which only returns a _single bit_ indicating
whether a given dataset is realizable by some concept in the class. The sample
complexity and oracle complexity of our algorithm depend polynomially on the
VC dimension of the hypothesis class, thus showing that there is only a
polynomial price to pay for use of our weaker oracle. Our results extend to
the agnostic learning setting with a slight strengthening of the oracle, as
well as to the partial concept, multiclass and real-valued learning settings.
In the setting of partial concept classes, prior to our work no oracle-
efficient algorithms were known, even with a standard ERM oracle. Thus, our
results address a question of [AHHM21] who asked whether there are algorithmic
principles which enable efficient learnability in this setting.

##  1 Introduction

Many of the successful techniques in modern machine learning proceed by
specifying a large function class $\mathcal{H}$, such as a class of neural
networks, and optimizing over $\mathcal{H}$ to find a minimizer of a loss
function on a finite dataset. This approach, known as _empirical risk
minimization_ (ERM), has long been known to lead to near-optimal PAC learning
guarantees in fundamental settings such as binary classification and
regression [VC68, VC74, BEHW89, BL98, ABDCBH97]. Due to the ability of
heuristics such as gradient descent to approximately implement ERM for neural
network function classes, the ERM principle also lies behind numerous
empirical successes in supervised learning [KSH12]. Inspired by these
successes, various works have also investigated to what extent an _oracle_
which can implement ERM for a given function class is useful for learning
problems beyond the PAC setting, including online learning [BDGR22, HHSY22,
AAD+23], bandits [SLX22], and reinforcement learning [AKKS20, MFR23].

In this paper, we return to the basics and ask: is ERM necessary? Or can we
efficiently perform learning tasks with a _weaker_ oracle than an ERM oracle?
For the foundational problem of realizable PAC learning, it is known that a
_consistency oracle_ , which returns a hypothesis $\hat{h}$ in the class
$\mathcal{H}$ which is consistent with a given dataset (and fails if one does
not exist), is still sufficient for efficient learning. Perhaps the most
drastic way to further weaken such a consistency oracle is as follows: suppose
that the oracle does not return $\hat{h}$, and only returns a _single bit_
indicating whether such a $\hat{h}\in\mathcal{H}$ exists which fits the data.
We refer to such an oracle as a _weak consistency oracle_. Is there a PAC
learning algorithm which learns efficiently with respect to this oracle?
Perhaps surprisingly, we find that the answer is _yes_. Moreover, this
positive answer extends to the agnostic PAC setting, if we slightly generalize
the weak consistency oracle to return the _value_ of the empirical risk
minimizer $\hat{h}$ on the dataset, but not $\hat{h}$ itself; we call such an
oracle a _weak ERM oracle_.

#### Motivation.

We discuss several possible sources of motivation behind a weakening of an ERM
(or consistency) oracle. First, note that a weak consistency oracle, which
only returns a single bit indicating whether a consistent hypothesis exists,
corresponds to a _decision problem_ on $\mathcal{H}$, whereas a standard
consistency oracle corresponds to a _search problem_. For many natural classes
of problems (e.g., see [AKS04, RV03, KV91]), the decision variant is known to
be computationally cheaper than the search variant.111More generally, such
separations can emerge for non-self-reducible problems in NP. Based off of
such a separation, in Proposition I.1, we provide a concrete example of a
class for which implementing a weak consistency oracle is possible in
polynomial time but implementing a standard consistency oracle is not, under
standard computational assumptions. Thus, in such a case, our approach, via a
weak consistency oracle, will lead to improved computational guarantees over
the standard approach which calls a consistency oracle.

From a more theoretical perspective, the use of weak consistency and weak ERM
oracles yields PAC learning bounds that do not rely on uniform convergence, in
contrast to some prior analyses of ERM. A notable setting where PAC learning
is known to be statistically feasible but uniform convergence fails is that of
learning with _partial concept classes_ [AHHM21, Lon01], which in turn has
numerous applications including to regression [Lon01, BL98], learning with
fairness constraints such as multicalibration [HP23], adversarially robust
learning [AHM22], and others (see Section 4). Our results provide the first
(ERM) oracle-efficient learning algorithm for partial concept classes, which
addresses a question asked in [AHHM21]. We emphasize that even with a
_standard_ ERM oracle, no efficient algorithm was known, whereas our
guarantees for partial concept classes hold with a _weak_ ERM oracle.

###  1.1 Overview of results

First, we consider the setting of PAC learning of _partial concept classes_
[AHHM21, Lon01], which are classes
$\mathcal{H}\subset\\{0,1,*\\}^{\mathcal{X}}$ for some domain space
$\mathcal{X}$. Hypotheses $h\in\mathcal{H}$ should be thought of as undefined
at points $x\in\mathcal{X}$ for which $h(x)=*$ (see Section 2 for a formal
definition).222The unfamiliar reader can simply consider the special case of
those $\mathcal{H}$ whose hypotheses never take the value $*$, which
corresponds to standard binary classification. Our main results for this
setting are as follows:

  * •

In the realizable setting of PAC learning, any partial concept class
$\mathcal{H}$ of VC dimension at most $d_{\mathsf{VC}}$ can be learned by an
algorithm that makes polynomially many calls to a _weak consistency oracle_
$\mathcal{O}^{\mathsf{con,w}}$, which receives as input a dataset
$S=\\{(x_{i},y_{i})\\}_{i\in[n]}$ and returns $\mathsf{True}$ if there is
$h\in\mathcal{H}$ satisfying $h(x_{i})=y_{i}\in\\{0,1\\}$ for all $i$, and
$\mathsf{False}$ otherwise. The sample complexity scales as
$\tilde{O}(d_{\mathsf{VC}}^{3})$ (see first part of Theorem 3.1).

  * •

In the agnostic setting of PAC learning, the same guarantee holds, except with
respect to a _weak ERM oracle_ $\mathcal{O}^{\mathsf{erm,w}}$ which receives
as input $S=\\{(x_{i},y_{i})\\}_{i\in[n]}$ and returns the value
$\min_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{{h(x_{i})\neq
y_{i}\vee h(x_{i})=*}\\}\in\\{0,1/n,\ldots,1\\}$ (see second part of Theorem
3.1).

We proceed to generalize our upper bounds beyond the binary setting, namely
the multiclass and real-valued (regression) settings:

  * •

For $K\in\mathbb{N}$, any multiclass concept class
$\mathcal{H}\subset[K]^{\mathcal{X}}$ of Natarajan dimension at most
$d_{\mathsf{N}}$ can be PAC learned by an algorithm that uses
$n=\tilde{O}(d_{\mathsf{N}}^{3}\log^{4}K)$ samples and makes
$K\cdot\operatorname{poly}(n)$ calls to a weak consistency oracle (or to a
weak ERM oracle in the agnostic setting); see Theorem 4.1.

  * •

Any real-valued class $\mathcal{H}\subset[0,1]^{\mathcal{X}}$ whose fat-
shattering dimension at scales $\gamma\in(0,1)$ is at most
$d_{\mathsf{fat},{\gamma}}$ can be agnostically PAC learned by an algorithm
that uses $n$ samples as long as $n\gtrsim d_{\mathsf{fat},{\gamma}}^{3}$ for
an appropriate chocie of $\gamma$, using $\operatorname{poly}(n)$ calls to a
weak ERM oracle. Moreover, a similar guarantee holds for the realizable
setting; see Theorem 4.2.

In the setting of partial concept classes as well as the _agnostic_ setting of
regression, VC dimension and fat-shattering dimension, respectively, are known
to characterize learnability. Thus, our results above show that there is at
most a polynomial price to pay in terms of sample complexity if we require
efficiency with respect to a weak ERM oracle. In contrast, in the multiclass
and realizable regression settings, the optimal sample complexity is
characterized by the _Daniely-Schwartz dimension_ [DSS14, BCD+22] and the
_one-inclusion graph dimension_ [AHK+23], respectively. These quantities can
be arbitrarily smaller than our corresponding sample complexities above,
namely $d_{\mathsf{N}}\log K$ and $d_{\mathsf{fat},{\gamma}}$, respectively.

Can our bounds for the multiclass and realizable regression settings be
improved to get near-optimal sample complexity while retaining oracle
efficiency? Our final results show a negative answer to this question, even
when the algorithm is given a standard ERM oracle:

  * •

Multiclass concept classes of Daniely-Schwartz dimension 1 are not PAC
learnable with any finite number of ERM oracle queries; see Theorem H.2.

  * •

In the realizable setting of regression, real-valued classes with one-
inclusion graph dimension 1 are not PAC learnable with any finite number of
ERM oracle queries; see Theorem H.3.

#### Techniques.

Our results rest on a new technique to efficiently implement a randomized
variant of the _one-inclusion graph algorithm_ , formalized in Theorem 3.2
(see also Definition 2.8). In particular, we show first that we can obtain a
weak learner by constructing a random orientation of the one-inclusion graph
with bounded out-degree, as follows. For each edge we wish to orient, we take
a random walk starting from each of its endpoints and inspect the distribution
of hitting times of the complement of the one-inclusion graph. The vertex
whose random walk reaches the complement of the one-inclusion graph sooner
should have the edge directed away from it. We then use standard boosting
techniques to improve the weak learner to a strong learner. A detailed proof
overview may be found in Section 3.1.

#### Open questions.

Taken together, our results represent a comprehensive treatment of the weak
oracle efficiency of PAC learning in the standard settings of partial,
multiclass, and real-valued learning. One intruiging question that remains is
closing the gap between our $\tilde{O}(d_{\mathsf{VC}}^{3})$ sample complexity
in the binary setting and the fact that only $O(d_{\mathsf{VC}})$ samples are
required when one is allowed access to a standard ERM oracle. In particular,
is there a (polynomial-sized) cost in sample complexity to pay for using a
weak oracle? Analogous questions can be asked in the multiclass and real-
valued settings. Along different lines, it would be interesting to investigate
the use of weaker notions of ERM oracles in more complex learning situations
such as contextual bandits, online learning, and reinforcement learning.

###  1.2 Broader perspectives

Broadly speaking, our work connects to an extensive body of literature, both
in empirical and theoretical communities, on query-efficient learning. Spurred
by the increasing prevelance of proprietary models and the availability of
APIs to query inputs to these models at a small cost, recent empirical
research has studied to what extent such API calls, which typically each
reveal a small amount of information, can be used to reconstruct information
such as the model’s training data or an approximation to the model itself. For
instance, [TZJ+16] showed that several types of models, including decision
trees, SVMs, and neural networks can be reconstructed to high fidelity using a
relatively small number of queries to evaluate the model at chosen inputs.
Similar results have been shown for various specific domains, including
sentence classification [KTP+20], machine translation [WSS20], and sentence
embedding encoders [DBJ+23].333See also [DB15, MZC+23] and references within
for work on the related problem of inverting trained models. These papers on
“model stealing” roughly parallel an old line of work in learning theory on
learning from queries [Ang88], in which one can make several types of queries
to the ground-truth hypothesis $h^{\star}$, such as a _membership query_ where
one specifies $x$ and receives $h^{\star}(x)$. [Ang88] and many follow-up
works study the question of how many such queries are sufficient for learning
$h^{\star}$.

The high-level implications of the works mentioned above parallel our own in
that one often arrives at the conclusion that a surprisingly large amount of
information be gleaned from a relatively small number of queries, each of
which returns a relatively small number of bits. At a technical level, the
above papers differ from our own in that the queries performed by the learning
algorithm depend explicitly on the ground-truth hypothesis $h^{\star}$,
whereas the oracle queries we consider are queries to the _hypothesis class_
$\mathcal{H}$ without any mention of $h^{\star}$. Nevertheless, with the
advent of methods such as in-context learning [BMR+20], which allows a fully
trained large language model to simulate learning algorithms such as gradient
descent, the distinction between these two settings is somewhat blurred. In
particular, one could imagine a setting where a proprietary large language
model itself serves as an ERM oracle for simpler classes, and thus our results
demonstrating that queries which return only a few bits of information still
permit learning could be informative. We leave it to future work to elucidate
the question of whether the success of such weak oracles ultimately amounts to
a feature (allowing learning without giving too much away) or a bug (giving
enough away to allow reconstruction attacks).

##  2 Preliminaries

Consider a domain $\mathcal{X}$, a label set $\mathcal{Y}$, and a _concept
class_ $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$. Elements
$h\in\mathcal{H}$ are known as _concepts_ (or _hypotheses_). In this paper, we
consider the following different label sets $\mathcal{Y}$:

  * •

If $\mathcal{Y}=\\{0,1,*\\}$, then we say that $\mathcal{H}$ is a _partial
(binary) concept class_ [AHHM21]. A hypothesis which outputs a label of $*$ on
some $x\in\mathcal{X}$ should be interpreted as being undefined at $x$. In the
special case that no hypothesis ever outputs $*$, a partial binary concept
class is known as a _total_ binary concept class. We define the binary loss
function $\ell^{\mathsf{bin}}(y,y^{\prime}):=\mathbbm{1}\\{{y\neq
y^{\prime}\vee y=*\vee y^{\prime}=*}\\},$ for $y,y^{\prime}\in\\{0,1,*\\}$. In
words, we suffer a loss for true label $y$ when predicting $y^{\prime}$ if we
predict the wrong label _or_ either $y,y^{\prime}$ is $*$.

  * •

If $\mathcal{Y}=[K]$, then $\mathcal{H}$ is said to be a _multiclass concept
class_. We define the _multiclass loss function_
$\ell^{\mathsf{mc}}(y,y^{\prime}):=\mathbbm{1}\\{{y\neq y^{\prime}}\\}$, for
$y,y^{\prime}\in[K]$.

  * •

If $\mathcal{Y}=[0,1]$, then $\mathcal{H}$ is said to be a _real-valued
concept class_. We define the _absolute loss function_
$\ell^{\mathsf{abs}}(y,y^{\prime}):=|y-y^{\prime}|$, for
$y,y^{\prime}\in[0,1]$.

Throughout the paper, all concept classes
$\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$ will be understood as being
either partial, multiclass, or real-valued concept classes.

###  2.1 PAC learning

Given a distribution $P\in\Delta(\mathcal{X}\times\mathcal{Y})$, a loss
function $\ell:\mathcal{Y}\times\mathcal{Y}\to[0,1]$, and a hypothesis
$h:\mathcal{X}\to\mathcal{Y}$, we define
$\mathrm{er}_{P,\ell}(h):=\mathbb{E}_{(x,y)\sim P}[\ell(h(x),y)]$. Given a
sequence $S\in(\mathcal{X}\times\mathcal{Y})^{n}$, which we refer to as a
_sample_ , a loss function $\ell:\mathcal{Y}\times\mathcal{Y}\to[0,1]$, and
$h:\mathcal{X}\to\mathcal{Y}$, we define
$\widehat{\mathrm{er}}_{S,\ell}(h):=\frac{1}{n}\sum_{(x,y)\in
S}\mathbbm{1}\\{{h(x)\neq y}\\}$. When working with partial, multiclass, or
real-valued concept classes, we will typically take $\ell$ to be the
corresponding respective loss function among
$\ell^{\mathsf{bin}},\ell^{\mathsf{mc}},\ell^{\mathsf{abs}}$. Thus, unless
otherwise stated, in such situations we will write $\mathrm{er}_{P}(\cdot)$ in
place of $\mathrm{er}_{P,\ell}(\cdot)$ and $\widehat{\mathrm{er}}_{S}(\cdot)$
in place of $\widehat{\mathrm{er}}_{S,\ell}(\cdot)$, where
$\ell\in\\{\ell^{\mathsf{bin}},\ell^{\mathsf{mc}},\ell^{\mathsf{abs}}\\}$ is
understood to be the appropriate choice. We denote samples using curly braces,
but emphasize that samples should be interpreted as sequences of $n$ examples
(in particular, examples can be repeated).

Given a concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$, a
_sample_
$S=\\{(x_{i},y_{i})\\}_{i\in[n]}\subset(\mathcal{X}\times\mathcal{Y})^{n}$ is
said to be _$\mathcal{H}$ -realizable_ if there is $h\in\mathcal{H}$ so that
$h(x_{i})=y_{i}\neq*$ for each $i\in[n]$. Moreover, a distribution
$P\in\Delta(\mathcal{X}\times\mathcal{Y})$ is defined to be _$\mathcal{H}$
-realizable_ if the following holds: in the case that $\mathcal{H}$ is a
partial concept class, for any $n\in\mathbb{N}$, then a sample $S\sim P^{n}$
is $\mathcal{H}$-realizable with probability 1; in the case that $\mathcal{H}$
is a multiclass or real-valued concept class, then
$\inf_{h\in\mathcal{H}}\mathrm{er}_{P}(h)=0$. We remark that these two
conditions coincide if $P$ has finite or countable support (see [AHHM21, Lemma
33]).

#### Realizable oracle-efficient PAC learning.

In the problem of _realizable PAC learning_ (or simply _PAC learning_), for a
concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$ and a
$\mathcal{H}$-realizable distribution $P$, an algorithm $\mathsf{Alg}$
receives a sample $S\sim P^{n}$ and outputs a hypothesis
$H:\mathcal{X}\to\mathcal{Y}$. While often it is assumed that $\mathsf{Alg}$
has full knowledge of the class $\mathcal{H}$, we are concerned with the
setting in which $\mathsf{Alg}$’s only access to $\mathcal{H}$ comes in the
form of an oracle
$\mathcal{O}:(\mathcal{X}\times\mathcal{Y})^{\star}\times\\{0,1\\}^{\star}\to\\{0,1\\}^{\star}$,
which takes as input a sequence of examples
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ as well as a string of bits, and
outputs a string of bits. While much prior work in the literature has focused
on oracles, such as a (strong) ERM oracle (Definition 2.6), which can return
_elements of $\mathcal{H}$_, the oracles we consider are weaker in the sense
that their only outputs are strings of bits, which will be quite short.444Of
course, elements of $\mathcal{H}$ can be represented with $\log|\mathcal{H}|$
bits, but our oracles will always return strings of length
$\operatorname{poly}(\log d,\log 1/\epsilon,\log\log 1/\delta)$, which can be
infinitely smaller than $\log|\mathcal{H}|$. Here $d$ denotes a dimension
quantity (e.g., VC dimension) and $\epsilon,\delta$ are accuracy parameters.
For an input
$(S,z)\in(\mathcal{X}\times\mathcal{Y})^{\star}\times\\{0,1\\}^{\star}$ to an
oracle $\mathcal{O}$, we let the _size_ of $(S,z)$ be $|S|+|z|$, namely the
sum of the number of examples in $S$ and the number of bits in $z$. We say
that an algorithm $\mathsf{Alg}$ has _cumulative query cost $q$_ if the sum of
the sizes of the inputs for all oracle calls that $\mathsf{Alg}$ makes to
$\mathcal{O}$ is at most $q$. Note that the number of oracle calls made by
$\mathsf{Alg}$ is bounded above by $q$.

######  Definition 2.1 (Oracle-efficient PAC learning).

Let domain and label spaces $\mathcal{X},\mathcal{Y}$ be given. Given
$n\in\mathbb{N}$, let $\mathsf{Alg}$ be an algorithm which takes as input a
dataset $S\in(\mathcal{X}\times\mathcal{Y})^{n}$, $x\in\mathcal{X}$, and a
string of uniformly random bits $R\in\\{0,1\\}^{\star}$, has cumulative query
cost $q$ to an oracle
$\mathcal{O}:(\mathcal{X}\times\mathcal{Y})^{\star}\times\\{0,1\\}^{\star}\to\\{0,1\\}^{\star}$,
and outputs some value $\mathsf{Alg}_{R}(S,x)\in\mathcal{Y}$, which is a
deterministic function of $R,S,x$, and the results of the oracle calls.

Let $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$ be a hypothesis class and
$\mathcal{O}$ be an oracle as above. Given $\epsilon,\delta\in(0,1)$, we say
that the class $\mathcal{H}$ is _$(\mathcal{O};\epsilon,\delta)$ -PAC
learnable_ by $\mathsf{Alg}$ with _sample complexity $n$_ and _oracle
complexity $q$_ if the following holds. Letting
$H_{S,R}(x):=\mathsf{Alg}_{R}(S,x)$, we have

$\displaystyle\operatorname{Pr}_{S\sim
P^{n},R}\left(\mathrm{er}_{P}(H_{S,R})\leq\epsilon\right)\geq 1-\delta.$

We emphasize that in the above definition $\mathsf{Alg}$ has no knowledge of
$\mathcal{H}$ (apart from its calls to $\mathcal{O}$); of course, the oracle
$\mathcal{O}$ will depend on $\mathcal{H}$. Often we will slightly abuse
terminology by stating that $\mathsf{Alg}$ “outputs” the hypothesis $H_{S,R}$.

#### Agnostic oracle-efficient PAC learning.

The setting of _agnostic PAC learning_ is similar to the setting of realizable
PAC learning, except that the distribution
$P\in\Delta(\mathcal{X}\times\mathcal{Y})$ is no longer required to be
realizable. As such, we measure the performance of the output hypothesis of an
algorithm by comparing to the best hypothesis in the class $\mathcal{H}$. In
the case that $\mathcal{H}$ is a multiclass or real-valued class, the error of
the best-performing concept in $\mathcal{H}$ on $P$ is defined as
$\mathrm{er}_{P}(\mathcal{H}):=\inf_{h\in\mathcal{H}}\mathrm{er}_{P}(h)$. In
the case that $\mathcal{H}$ is a concept class, we instead define
$\mathrm{er}_{P}(\mathcal{H}):=\lim_{n\to\infty}\mathbb{E}_{S\sim
P^{n}}\left[\min_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{S}(h)\right]$.
[AHHM21, Lemma 39] shows that the limit exists, and that when $\mathcal{H}$ is
a total class, the two notions of $\mathrm{er}_{P}(\mathcal{H})$
coincide.555See Footnote 12 of [AHHM21] for discussion on why the particular
choice of $\mathrm{er}_{P}(\mathcal{H})$ is made.

######  Definition 2.2 (Oracle-efficient agnostic PAC learning).

Using the setup and terminology of Definition 2.1, the class $\mathcal{H}$ is
said to be _$(\mathcal{O};\epsilon,\delta)$_ -agnostically PAC learnable by
$\mathsf{Alg}$ with sample complexity $n$ and oracle complexity $q$ if, for
$H_{S,R}(x):=\mathsf{Alg}_{R}(S,x)$, we have

$\displaystyle\operatorname{Pr}_{S\sim
P^{n},R}\left(\mathrm{er}_{P}(H_{S,R})\leq\mathrm{er}_{P}(\mathcal{H})+\epsilon\right)\geq
1-\delta.$

###  2.2 Oracles

In this section, we formally introduce the oracles that our algorithms will
use. We begin with a _weak consistency oracle_ , which will be used by our
realizable PAC learning algorithms for partial and multiclass concept classes.

######  Definition 2.3 (Weak consistency oracle).

Given a concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$, a _(weak)
consistency oracle_ $\mathcal{O}^{\mathsf{con,w}}$ for $\mathcal{H}$ is
defined as follows: it takes as input a sample
$S\in(\mathcal{X}\times\mathcal{Y})^{n}$, and
$\mathcal{O}^{\mathsf{con,w}}(S)$ outputs $\mathsf{True}$ if $S$ is
$\mathcal{H}$-realizable and $\mathsf{False}$ otherwise.

For real-valued learning, a weak consistency oracle is not sufficient for
learning, due to the fact that labels in $\mathcal{Y}=[0,1]$ can take
infinitely many values. Therefore, for realizable PAC learning in the real-
valued setting, we make use of a _range consistency oracle_ , which is a
natural generalization of a weak consistency oracle when one allows some
margin of error in label space:

######  Definition 2.4 (Range consistency oracle).

Given a real-valued concept class $\mathcal{H}\subset[0,1]^{\mathcal{X}}$, a
_range consistency oracle_ $\mathcal{O}^{\mathsf{range}}$ for $\mathcal{H}$ is
defined as follows: it takes as input a sample
$S=\\{(x_{i},\ell_{i},u_{i})\\}_{i\in[n]}\in(\mathcal{X}\times[0,1]^{2})^{n}$,
and outputs $\mathsf{True}$ if there is some $h\in\mathcal{H}$ so that
$\ell_{i}\leq h(x_{i})\leq u_{i}$ for all $i\in[n]$, and $\mathsf{False}$
otherwise.

The consistency oracles defined above are not sufficient for oracle-efficient
agnostic PAC learning: the challenge is that even approximating the _value_ of
the empirical risk minimizer
$\min_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{S}(h)\in[0,1]$ on a sample
$S\in(\mathcal{X}\times\\{0,1\\})^{n}$ can require many weak consistency
queries to $\mathcal{H}$. Rather surprisingly, it turns out that an oracle
which returns only the value of the empirical risk minimizer on a sample, as
defined formally below, is sufficient for efficient agnostic PAC learnability.

######  Definition 2.5 (Weak ERM oracle).

Consider a concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$, and a
real-valued loss function $\ell:\mathcal{Y}\times\mathcal{Y}\to[0,1]$. A _weak
ERM oracle_ $\mathcal{O}^{\mathsf{erm,w}}$ is a mapping which takes as input a
dataset $S\in(\mathcal{X}\times\mathcal{Y})^{n}$ and outputs the value
$\min_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{S,\ell}(h)\in[0,1]$.666When
$\ell\in\\{\ell^{\mathsf{bin}},\ell^{\mathsf{mc}}\\}$ is binary-valued,
$\min_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{S,\ell}(h)\in\\{0,1/n,\ldots,1\\}$
can be represented with $O(\log n)$ bits. In the real-valued setting, while
this is no longer the case, one can assume that $\mathcal{O}^{\mathsf{erm,w}}$
returns only the $\log(1/\epsilon)$ most significant bits of the empirical
risk, at the cost of an $O(\epsilon)$ error that propagates through the PAC
bounds. For simplicity, we ignore such considerations relating to arithmetic
precision.

Finally, for reference, we introduce the standard notion of ERM oracle, which
returns a hypothesis that minimizes the empirical risk on a sample; to
contrast with a weak ERM oracle, we call such an oracle a strong ERM oracle.

######  Definition 2.6 (Strong ERM oracle).

Consider a concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$ and a
real-valued loss function $\ell:\mathcal{Y}\times\mathcal{Y}\to[0,1]$. A
_strong ERM oracle_ $\mathcal{O}^{\mathsf{erm,s}}$ is a mapping which takes as
input a dataset $S\in(\mathcal{X}\times\mathcal{Y})^{n}$ and outputs some
concept in
$\operatorname*{arg\,min}_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{S,\ell}(h)\in\mathcal{H}$.

###  2.3 Sample compression schemes

Our techniques will involve the use of sample compression schemes, which we
proceed to define.

######  Definition 2.7 (Sample compression scheme; [LW03, DMY16]).

Fix a domain $\mathcal{X}$ and a label set $\mathcal{Y}$. A _compression
scheme_ for the tuple $(\mathcal{X},\mathcal{Y})$ is a pair $(\kappa,\rho)$,
consisting of a compression function
$\kappa:(\mathcal{X}\times\mathcal{Y})^{\star}\to(\mathcal{X}\times\mathcal{Y})^{\star}\times\\{0,1\\}^{\star}$
and a _reconstruction function_
$\rho:(\mathcal{X}\times\mathcal{Y})^{\star}\times\\{0,1\\}^{\star}\to\mathcal{Y}^{\mathcal{X}}$,
satisfying the following property. For any sequence
$S\in(\mathcal{X}\times\mathcal{Y})^{\star}$, $\kappa(S)$ evaluates to some
tuple
$(S^{\prime},B)\in(\mathcal{X}\times\mathcal{Y})^{\star}\times\\{0,1\\}^{\star}$,
where $S^{\prime}$ is a sequence of elements of $S$.

For $S\in(\mathcal{X}\times\mathcal{Y})^{m}$, writing
$(S^{\prime},B):=\kappa(S)$, define $|\kappa(S)|:=|S^{\prime}|+|B|$, i.e., to
denote the sum of the number of samples in $S^{\prime}$ and the length of $B$.
The _size_ of the compression scheme $(\kappa,\rho)$ for _$m$ -sample
datasets_ is $|\kappa|:=\max_{S\in(\mathcal{X}\times\mathcal{Y})^{\leq
m}}|\kappa(S)|$.

For a (partial, multiclass, or real-valued) concept class $\mathcal{H}$, a
_sample compression scheme for $\mathcal{H}$_ is a compression scheme
$(\kappa,\rho)$, so that for every $\mathcal{H}$-realizable sequence
$S\in(\mathcal{X}\times\mathcal{Y})^{m}$, $\rho(\kappa(S))$ correctly
classifies every point in $S$, i.e., $\frac{1}{n}\sum_{(x,y)\in
S}\ell(\rho(\kappa(S)),y)=0$, where
$\ell\in\\{\ell^{\mathsf{bin}},\ell^{\mathsf{mc}},\ell^{\mathsf{abs}}\\}$ is
the appropriate loss function corresponding to $\mathcal{H}$.

Lemma 2.1 below shows that compression schemes of bounded size generalize.

######  Lemma 2.1 (Generalization-by-compression; Theorem 2.1 of [DMY16]).

There is a constant $C>0$ so that the following holds. Consider any domain
$\mathcal{X}$ and label set $\mathcal{Y}$, together with a loss function
$\ell:\mathcal{Y}\times\mathcal{Y}\to[0,1]$. For any compression scheme
$(\kappa,\rho)$, for any $n\in\mathbb{N}$, and $\delta\in(0,1)$, for any
distribution $P\in\Delta(\mathcal{X}\times\\{0,1\\})$, the following holds
with probability $1-\delta$ over $S\sim P^{n}$:

$\displaystyle|\mathrm{er}_{P,\ell}(\rho(\kappa(S)))-\widehat{\mathrm{er}}_{S,\ell}(\rho(\kappa(S)))|$
$\displaystyle\leq$ $\displaystyle
C\sqrt{\widehat{\mathrm{er}}_{S,\ell}(\rho(\kappa(S)))\cdot\frac{1}{n}\left(|\kappa(S)|\log(n)+\log\frac{1}{\delta}\right)}+C\cdot\frac{1}{n}\left(|\kappa(S)|\log(n)+\log\frac{1}{\delta}\right).$

In particular, if $\widehat{\mathrm{er}}_{S,\ell}(\rho(\kappa(S)))=0$, then

$\displaystyle\mathrm{er}_{P,\ell}(\rho(\kappa(S)))\leq$ $\displaystyle
C\cdot\frac{1}{n}\left(|\kappa(S)|\log(n)+\log\frac{1}{\delta}\right).$

###  2.4 The one-inclusion graph

In this section, we introduce the one-inclusion graph [HLW88], which plays a
fundamental role in many PAC learning results. For a (partial, multiclass, or
real-valued) concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$ and
$X=(x_{1},\ldots,x_{m})\in\mathcal{X}^{m}$, we define
$\mathcal{H}|_{X}:=\\{y\in(\mathcal{Y}\backslash\\{*\\})^{m}\ :\ \exists
h\in\mathcal{H}\mbox{ s.t. }h(x_{i})=y_{i}\ \forall i\in[m]\\}$. Note that, in
the special case of partial concept classes,
$\mathcal{H}|_{X}\subset\\{0,1\\}^{m}$ and in particular does _not_ include
the $*$ symbol. For a partial binary concept class $\mathcal{H}$, its _VC
dimension_ , denoted $d_{\mathsf{VC}}(\mathcal{H})$, is the largest positive
integer $d$ so that there is some $X=(x_{1},\ldots,x_{d})\in\mathcal{X}^{d}$
so that $\mathcal{H}|_{X}=\\{0,1\\}^{d}$. It is known that the VC dimension
tightly characterizes statistical learnability of (partial) concept classes
[AHHM21].

For $v\in\\{0,1\\}^{n}$ and $i\in[n]$, we write $v^{\oplus i}$ to denote $v$
with coordinate $i$ flipped, i.e., $v^{\oplus i}_{j}=v_{j}$ for all $j\neq i$
and $v^{\oplus i}_{i}=1-v_{i}$. For $n\in\mathbb{N}$, let
$G_{n}=(V_{n},E_{n})$ be the $n$-dimensional hypercube graph, so that
$V_{n}=\\{0,1\\}^{n}$ and $E_{n}=\\{((v_{-i},0),(v_{-i},1))\ :\
i\in[n],v_{-i}\in\\{0,1\\}^{n-1}\\}$.

######  Definition 2.8 (One-inclusion graph).

Consider a set $\mathcal{W}\subset\\{0,1\\}^{n}$. The _one-inclusion graph_
$G(\mathcal{W})=(V,E)$ induced by $\mathcal{W}$ is defined as the following
graph. The vertex set $V$ is equal to $\mathcal{W}$. The edge set $E$ is the
subgraph of $G_{n}$ induced by $\mathcal{W}$, namely:

$\displaystyle E:=\\{(v,v^{\oplus i})\ :\ i\in[n],\ v,v^{\oplus
i}\in\mathcal{W}\\}.$

For any $i\in[n]$ and $h\in\\{0,1\\}^{n}$, we will occassionally write
$e_{i,h}$ to refer to the edge $(h,h^{\oplus i})$. For a partial concept class
$\mathcal{H}\subset\\{0,1,*\\}^{\mathcal{X}}$ and $X\in\mathcal{X}^{n}$, we
refer to the the one-inclusion graph induced by
$\mathcal{H}|_{X}\subset\\{0,1\\}^{n}$ as the one-inclusion graph of
$\mathcal{H}$ induced by $X$.

For a set $\mathcal{W}\subset\\{0,1\\}^{n}$, $\mathcal{W}^{\mathrm{c}}$
denotes its complement in $\\{0,1\\}^{n}$.

#### Orientations.

Given a graph $G=(V,E)$, a _random orientation_ of $G$ is a mapping
$\sigma:E\to\Delta(V)$, where, for all $e\in E$,
$\operatorname{supp}(\sigma(e))\subseteq e$ (i.e., $\sigma(e)$ is supported on
the 2 vertices of $e$). $\sigma$ is called an _orientation_ if $\sigma(e)$ is
supported on a single vertex $v$, in which case we will write $v=\sigma(e)$.
Given a function $F:V\to[0,1]$ and $\lambda\in[0,1]$, we consider a random
orientation $\sigma_{F,\lambda}$ _induced by $F$_, defined as follows: for an
edge $e=(v,v^{\prime})$, we set

$\displaystyle\sigma_{F,\lambda}(e)(v)=\frac{1+\lambda\cdot(F(v^{\prime})-F(v))}{2},\qquad\sigma_{F}(e)(v^{\prime})=\frac{1+\lambda\cdot(F(v)-F(v^{\prime}))}{2}.$
(1)

Given a random orientation $\sigma$ and a vertex $v\in V$, we define the _out-
degree_ of $\sigma$ at $v$ to be

$\displaystyle\mathsf{outdeg}(v;\sigma):=\sum_{e\ni
v}\left(1-\sigma(e)(v)\right),$

and the out-degree of $\sigma$ is $\mathsf{outdeg}(\sigma):=\max_{v\in
V}\mathsf{outdeg}(v;\sigma)$.

##  3 Learning partial concept classes with a weak oracle

In this section, we give an algorithm for realizable PAC learning with low
oracle complexity for a weak consistency oracle, and an algorithm for agnostic
PAC learning with low oracle complexity for a weak ERM oracle.

######  Theorem 3.1 (Oracle-efficient partial concept class learning).

For any $\epsilon,\delta\in(0,1)$ and $d_{\mathsf{VC}}\in\mathbb{N}$, the
following statements hold:

  1. 1.

There is an algorithm $\mathsf{Alg}^{\mathsf{R}}$ so that for any class
$\mathcal{H}\subset\\{0,1,*\\}^{\mathcal{X}}$ satisfying
$d_{\mathsf{VC}}(\mathcal{H})\leq d_{\mathsf{VC}}$ and any weak consistency
oracle $\mathcal{O}^{\mathsf{con,w}}$ for $\mathcal{H}$, the class
$\mathcal{H}$ is $(\mathcal{O}^{\mathsf{con,w}};\epsilon,\delta)$-PAC
learnable by $\mathsf{Alg}^{\mathsf{R}}$ with sample complexity
$n=\tilde{O}\left(\frac{d_{\mathsf{VC}}^{3}\log(1/\delta)}{\epsilon}\right)$
and oracle complexity $\operatorname{poly}(n)$.

  2. 2.

There is an algorithm $\mathsf{Alg}^{\mathsf{A}}$ so that for any class
$\mathcal{H}\subset\\{0,1,*\\}^{\mathcal{X}}$ satisfying
$d_{\mathsf{VC}}(\mathcal{H})\leq d_{\mathsf{VC}}$ and any weak ERM oracle
$\mathcal{O}^{\mathsf{erm,w}}$ for $\mathcal{H}$, the class $\mathcal{H}$ is
$(\mathcal{O}^{\mathsf{erm,w}};\epsilon,\delta)$-PAC learnable by
$\mathsf{Alg}^{\mathsf{A}}$ with sample complexity
$n=\tilde{O}\left(\frac{d_{\mathsf{VC}}^{3}\log(1/\delta)}{\epsilon^{2}}\right)$
and oracle complexity $\operatorname{poly}(n)$.

In the theorem statement above, $\tilde{O}(\cdot)$ hides factors which are
polynomial in $\log(d_{\mathsf{VC}}),\log(1/\epsilon),\log\log(1/\delta)$. The
proof of the realizable case of Theorem 3.1 proceeds by first constructing an
algorithm (WeakRealizable; Algorithm 1) which is a _weak learner_ for any
class of VC dimension at most $d_{\mathsf{VC}}$ in the realizable setting and
makes polynomially many oracle calls to $\mathcal{O}^{\mathsf{con,w}}$. We
then use a standard boosting algorithm (namely, Adaboost; Algorithm 5) to
boost the performance of the weak learner so as to obtain a learner which has
error at most $\epsilon$ with high probability. To analyze the generalization
error of this approach, we use a technique involving sample compression
schemes [DMY16, SF12]. Finally, to handle the agnostic case of Theorem 3.1, we
reduce to the realizable setting by showing that a weak ERM oracle can be used
in an efficient manner to determine, given any sample
$S\in(\mathcal{X}\times\\{0,1\\})^{n}$, a subsample of maximum size which is
$\mathcal{H}$-realizable (Lemma B.1). In the remainder of the section, we
introduce our weak learner; the remaining ingredients are (mostly) standard
and are presented in Appendices D and E.

###  3.1 An oracle-efficient weak learner

Our goal is to construct an oracle-efficient weak learner, namely one that
improves upon random guessing in expectation over its dataset by a small
margin $\eta>0$:

######  Definition 3.1 (Weak learner).

For $m\in\mathbb{N}$ and $\eta\in(0,1)$, a randomized learning algorithm
$\mathscr{A}:(\mathcal{X}\times\\{0,1\\})^{m}\times\mathcal{X}\to\\{0,1\\}$ is
defined to be a _$m$ -sample weak learner with margin $\eta$_ for the concept
class $\mathcal{H}$ if the following holds. For any $\mathcal{H}$-realizable
distribution $P\in\Delta(\mathcal{X}\times\\{0,1\\})$, $\mathscr{A}$ takes as
input an i.i.d. sample $S\sim P^{m}$ and $x\in\mathcal{X}$ and outputs a
(random) bit $\mathscr{A}(S,x)$, so that

$\displaystyle\mathbb{E}_{S\sim P^{m}}\mathbb{E}_{(x,y)\sim
P}\mathbb{E}_{\mathscr{A}}\left[\ell^{\mathsf{bin}}(\mathscr{A}(S,x),y)\right]\leq\frac{1}{2}-\eta.$
(2)

We construct an oracle-efficient weak learner using polynomially many calls to
a weak consistency oracle $\mathcal{O}^{\mathsf{con,w}}$ by simulating a
random walk on the one-inclusion graph of $\mathcal{H}|_{X}$ for an
appropriate choice of $X\in\mathcal{X}^{m}$. This procedure is formalized in
the WeakRealizable algorithm (Algorithm 1), whose main guarantee is shown
below:

######  Theorem 3.2 (Weak learning guarantee).

There are constants $C_{1},C_{2}$ so that the following holds. Consider a
partial concept class $\mathcal{H}$ of VC dimension $d$, $\delta\in(0,1)$, and
suppose $m\geq C_{1}d\log d$. For an $\mathcal{H}$-realizable sample
$S\in(\mathcal{X}\times\\{0,1\\})^{m-1}$ and $x\in\mathcal{X}$, let
$\mathscr{A}(S,x)\in\\{0,1\\}$ be the output of
$\texttt{WeakRealizable}(S,x,1-\frac{1}{C_{1}m\log
m},1,C_{1}m^{2}\log^{3}m,\mathcal{O}^{\mathsf{con,w}})$ (Algorithm 1), which
is a random variable. Then for any $\mathcal{H}$-realizable sample
$S=\\{(x_{i},y_{i})\\}_{i\in[m]}\in(\mathcal{X}\times\\{0,1\\})^{m}$, it holds
that

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}\left[\ell^{\mathsf{bin}}(\mathscr{A}(S_{-i},x_{i}),y_{i})\right]\leq\frac{1}{2}-\frac{1}{C_{2}m\log
m}$ (3)

where the expectation is taken over the randomness in the runs of
$\mathscr{A}(S_{-i},x_{i})$. Moreover, WeakRealizable makes at most
$\tilde{O}(m^{3})$ calls to $\mathcal{O}^{\mathsf{con,w}}$, each with a
dataset of size $m-1$.

Algorithm 1 Weak oracle-efficient OIG learner

1:A partial concept class $\mathcal{H}$, an $\mathcal{H}$-realizable sample
$S=\\{(x_{i},y_{i})\\}_{i\in[m-1]}\in(\mathcal{X}\times\\{0,1\\})^{m-1}$,
query point $x\in\mathcal{X}$, consistency oracle
$\mathcal{O}^{\mathsf{con,w}}$, parameters $\lambda,\gamma\in(0,1)$,
$U\in\mathbb{N}$.

2:function WeakRealizable($S,x,\gamma,\lambda,U,\mathcal{O}^{\mathsf{con,w}}$)

3: Set $X\leftarrow(x_{1},\ldots,x_{m-1},x)\in\mathcal{X}^{m}$.

4: Set $y^{0}\leftarrow(y_{1},\ldots,y_{m-1},0)\in\\{0,1\\}^{m}$ and
$y^{1}\leftarrow(y_{1},\ldots,y_{m-1},1)\in\\{0,1\\}^{m}$.

5: if
$\mathcal{O}^{\mathsf{con,w}}(\\{(X_{j},y^{b}_{j})\\}_{j\in[m]})=\mathsf{False}$
for some $b\in\\{0,1\\}$ then

6: return $1-b$.

7: For $b\in\\{0,1\\}$, set
$\hat{F}(y^{b})\leftarrow\texttt{EstimatePotential}(X,y^{b},K,\gamma,\mathcal{O}^{\mathsf{con,w}})$.

8: return a sample from $\mathrm{Ber}(\hat{\sigma})$, where
$\hat{\sigma}:=\frac{1+\lambda\cdot(\hat{F}(y^{0})-\hat{F}(y^{1}))}{2}$.

9:$U,\gamma,\mathcal{O}^{\mathsf{con,w}}$ as above, and
$X\in\mathcal{X}^{m},y\in\\{0,1\\}^{m}$.

10:function EstimatePotential($X$, $y,U,\gamma,\mathcal{O}^{\mathsf{con,w}}$)
$\triangleright$ _$y$ represents a vertex of the OIG induced by
$\mathcal{H}|_{X}$, and $U$ is the number of trials_

11: for $1\leq u\leq U$ do

12: Set $Y^{(0)}\leftarrow y$ and
$T_{u}\leftarrow\frac{\log(32e/(1-\gamma))}{\log(1/\gamma)}$.

13: for $0\leq t\leq\frac{\log(32e/(1-\gamma))}{\log(1/\gamma)}$ do

14: if
$\mathcal{O}^{\mathsf{con,w}}(\\{(X_{j},(Y^{(t)})_{j})\\}_{j\in[m]})=\mathsf{False}$
then

15: Set $T_{u}\leftarrow t$, and break (out of the inner for loop).

16: else

17: Choose $i\sim\operatorname{Unif}([m])$, and set
$Y^{(t+1)}\leftarrow(Y^{(t)})^{\oplus i}$.

18: return the quantity $\frac{1}{U}\sum_{u=1}^{U}\gamma^{T_{u}}$.

The guarantee Eq. 3, in which an arbitrary realizable dataset $S$ is fixed and
the algorithm’s performance is measured on all leave-one-out configurations of
$S$, is known as a _transductive learning_ guarantee. A standard
exchangeability argument (see Lemma C.4) shows that Eq. 3 implies an in-
expectation error guarantee under any realizable distribution
$P\in\Delta(\mathcal{X}\times\\{0,1\\})$, and thus Theorem 3.2 implies that
WeakRealizable is an $m$-sample weak learner with margin $\eta=\Theta(1/(m\log
m))$ for $\mathcal{H}$. In the remainder of the section we focus on the proof
of Theorem 3.2.

#### Analyzing WeakRealizable.

Given a dataset $S=\\{(x_{i},y_{i})\\}_{i\in[m-1]}$ together with a “query
point” $x\in\mathcal{X}$, WeakRealizable considers the two vertices
$y^{0}=(y_{1},\ldots,y_{m-1},0),y^{1}=(y_{1},\ldots,y_{m-1},1)$ of the one-
inclusion graph $G(\mathcal{H}|_{X})$ induced by $\mathcal{H}$ on the sequence
$X=(x_{1},\ldots,x_{m-1},x)$. (If $y^{b}$ is not a vertex of
$G(\mathcal{H}|_{X})$ for some $b\in\\{0,1\\}$, then, by realizability, the
correct prediction on $x$ must be $1-b$ – see 6 of Algorithm 1.)
WeakRealizable then calls EstimatePotential on each of the vertices
$y^{0},y^{1}$, which returns estimates $\hat{F}(y^{0}),\hat{F}(y^{1})$ of a
certain potential function on vertices of $G$. These potentials are used to
randomly return an output bit in 8.

The proof that WeakRealizable satisfies Eq. 3 proceeds by considering the
following perspective: the value
$\hat{\sigma}=\frac{1+\lambda(\hat{F}(y^{0})-\hat{F}(y^{1}))}{2}$ computed in
8 can be viewed as a decision to randomly orient the edge $(y^{0},y^{1})$ of
the one-inclusion graph $G(\mathcal{H}|_{X})$ by putting mass $\hat{\sigma}$
on $y^{1}$ and mass $1-\hat{\sigma}$ on $y^{0}$ (see Section 2.4). To minimize
loss, we hope that this orientation puts as much mass as possible on whichever
of $y^{0},y^{1}$ corresponds to the ground-truth hypothesis, i.e., we want the
edge $(y^{0},y^{1})$ to not contribute much to the out-degree of the ground-
truth.

Translated into this language of orientations, the transductive error
guarantee Eq. 3 of Theorem 3.2 is therefore equivalent to the following
statement: fix $m\in\mathbb{N}$, consider any $\mathcal{H}$-realizable dataset
$S=\\{(x_{i},y_{i})\\}_{i\in[m]}$, and let $X=(x_{1},\ldots,x_{m})$. Then the
random orientations of the $m$ edges adjacent to $y\in G(\mathcal{H}|_{X})$
induced by running WeakRealizable with inputs $(S_{-i},x_{i})$, for each
$i\in[m]$, lead the _out-degree_ of $y$ to be bounded above by
$m\cdot\left(1/2-\Omega(1/(m\log m))\right)$. As a sanity check, it is trivial
to achieve out-degree $m/2$ by orienting each edge to each of its vertices
with probability $1/2$; thus, the quantity of interest is the decrease of
$-m\cdot\Omega(1/(m\log m))$ in the out-degree.

To explain how we achieve such an out-degree bound, consider the
$m$-dimensional hypercube graph $G_{m}=(V_{m},E_{m})$. Note that the one-
inclusion graph $G(\mathcal{H}|_{X})$ is the subgraph of $G_{m}$ induced by
$\mathcal{H}|_{X}$. Given $v\in V_{m}$, we consider the (lazy) random walk on
$G_{m}$ started at $v$. In particular, it is the sequence
$Z_{v}^{(0)},Z_{v}^{(1)},Z_{v}^{(2)},\ldots\in V_{m}$ of random variables with
$Z_{v}^{(0)}=v$, and with $Z_{v}^{(t)}$ defined as follows, for $t\geq 0$:
given $Z_{v}^{(t)}\in V_{m}$, the value of $Z_{v}^{(t+1)}$ is defined by
selecting uniformly at random an edge $e$ of $G_{m}$ containing $Z_{v}^{(t)}$,
and then letting $Z_{v}^{(t+1)}$ to be a uniformly random vertex of $e$. Given
a subset $\mathcal{S}\subset V_{m}$ and a vertex $v\in V_{m}$, the _hitting
time_ for $\mathcal{S}$ starting at $v$ is the random variable

$\displaystyle\tau_{\mathcal{S},v}:=\min\left\\{t\geq 0\ :\
Z_{v}^{(t)}\in\mathcal{S}\right\\}.$ (4)

Moreover, the generating function $M_{\mathcal{S},v}(\gamma)$, for
$\gamma\in(0,1)$, is defined for $v\in V_{m}$ by
$M_{\mathcal{S},v}(\gamma):=\mathbb{E}[\gamma^{\tau_{\mathcal{S},v}}]$.777For
$v\in\mathcal{S}$, we have $\tau_{\mathcal{S},v}=0$ and hence
$M_{\mathcal{S},v}(\gamma)=1$. The definition of the random walk yields the
following recursive formula for $M_{\mathcal{S},v}(\gamma)$ (see Lemma C.1 for
a formal statement): for all $v\in\mathcal{S}^{\mathrm{c}}$,

$\displaystyle
M_{\mathcal{S},v}(\gamma)=\frac{\gamma}{(2-\gamma)m}\sum_{i\in[m]}M_{\mathcal{S},v^{\oplus
i}}(\gamma).$ (5)

Given $\mathcal{H}$ and $X\in\mathcal{X}^{m}$ as above, we now choose
$\mathcal{S}:=(\mathcal{H}|_{X})^{\mathrm{c}}$, $\gamma:=1-\Theta(1/(m\log
m))$, and define $F(v)=M_{\mathcal{S},v}(\gamma)$. We may consider the
orientation $\sigma_{F,1}$ induced by $F$ (see Eq. 1). It is a simple
consequence of Eq. 5 (see Lemma C.2 that

$\displaystyle\mathsf{outdeg}(\sigma_{F,1})\leq\frac{m}{2}-(1-\gamma)m\cdot\min_{v\in
V_{m}}F(v).$ (6)

Finally, we can show (in Lemma C.3) that as long as $m\geq\Omega(d\log d)$
(where $d$ is an upper bound on $d_{\mathsf{VC}}(\mathcal{H})$), we have
$\min_{v\in V_{m}}F(v)\geq\Omega(1)$. This statement is a consequence of the
Sauer-Shelah lemma, which bounds
$|\mathcal{S}^{\mathrm{c}}|=|\mathcal{H}|_{X}|\leq(em)^{d}$. In particular,
since $\mathcal{S}^{\mathrm{c}}$ is relatively “small”, the hitting time
$\tau_{\mathcal{S},v}$ cannot get too large for any vertex $v$, meaning that
$\gamma^{\tau_{\mathcal{S},v}}$ cannot become too small. To summarize, we thus
obtain from Eq. 6 that $\mathsf{outdeg}(\sigma_{F,1})\leq
m\cdot\left(\frac{1}{2}-\Omega(1-\gamma)\right)=m\cdot\left(\frac{1}{2}-\Omega\left(\frac{1}{m\log
m}\right)\right)$.

Since the generating function $F(v)$ is not known exactly, WeakRealizable
cannot compute the orientation $\sigma_{F,1}$ exactly. Instead, it computes
estimates $\hat{F}(y^{0}),\hat{F}(y^{1})$ of $F(y^{0}),F(y^{1})$ respectively
(using EstimatePotential), via random rollouts. Crucially, doing so is
possible using only a weak consistency oracle $\mathcal{O}^{\mathsf{con,w}}$:
we only need to be able to check, at each step, whether the random walk has
hit $\mathcal{S}=(\mathcal{H}|_{X})^{\mathrm{c}}$, which is exactly what is
accomplished by $\mathcal{O}^{\mathsf{con,w}}$. By standard concentration
arguments, we can show that the induced orientation $\sigma_{\hat{F},1}$ is
sufficiently close to $\sigma_{F,1}$ to enjoy the same outdegree bounds, thus
establishing Theorem 3.2. The full details of the proof of Theorem 3.2 may be
found in Appendix C.

##  4 Extensions to multiclass and real-valued classes

We next extend the guarantee of Theorem 3.1 to the settings of _multiclass
classification_ and _regression_. The proofs for both of these settings
proceed via a reduction to the case of partial concept classes.

###  4.1 Multiclass concept classes

Our upper bounds for the multiclass setting are phrased in terms of _Natarajan
dimension_ : for a multiclass concept class
$\mathcal{H}\subset[K]^{\mathcal{X}}$, its _Natarajan dimension_ , denoted
$d_{\mathsf{N}}(\mathcal{H})$, is the smallest $d\in\mathbb{N}$ so that there
is some $X=(x_{1},\ldots,x_{d})\in\mathcal{X}^{d}$ together with vectors
$a,b\in[K]^{d}$ with $a_{i}\neq b_{i}$ for all $i\in[d]$ so that
$\mathcal{H}|_{X}\supseteq\\{a_{1},b_{1}\\}\times\cdots\times\\{a_{d},b_{d}\\}$.
It is known that the algorithm the algorithm which returns an empirical risk
minimizer of $\mathcal{H}$ on an i.i.d. sample, which requires access to a
_strong_ ERM oracle $\mathcal{O}^{\mathsf{erm,s}}$, enjoys sample complexity
for PAC learning of $\tilde{O}(d_{\mathsf{N}}(\mathcal{H})\log(K)/\epsilon)$
in the realizable setting and of
$\tilde{O}(d_{\mathsf{N}}(\mathcal{H})\log(K)/\epsilon^{2})$ in the agnostic
setting [DSBDSS11]. Theorem 4.1 shows that we can extend this result to the
setting where we only have a _weak_ ERM oracle, as long as the oracle
complexity is allowed to grow linearly with $K$.

######  Theorem 4.1 (Oracle-efficient multiclass learning).

For any $\epsilon,\delta\in(0,1)$ and $d_{\mathsf{N}}\in\mathbb{N}$, the
following statements hold:

  1. 1.

There is an algorithm $\mathsf{Alg}^{\mathsf{R}}$ so that for any class
$\mathcal{H}\subset[K]^{\mathcal{X}}$ satisfying
$d_{\mathsf{N}}(\mathcal{H})\leq d_{\mathsf{N}}$ and any weak consistency
oracle $\mathcal{O}^{\mathsf{con,w}}$ for $\mathcal{H}$, the class
$\mathcal{H}$ is $(\mathcal{O}^{\mathsf{con,w}};\epsilon,\delta)$-PAC
learnable by $\mathsf{Alg}^{\mathsf{R}}$ with sample complexity
$n=\tilde{O}\left(\frac{d_{\mathsf{N}}^{3}\log^{4}(K/\delta)}{\epsilon}\right)$
and oracle complexity $K\cdot\operatorname{poly}(n)$.

  2. 2.

There is an algorithm $\mathsf{Alg}^{\mathsf{A}}$ so that for any class
$\mathcal{H}\subset[K]^{\mathcal{X}}$ satisfying
$d_{\mathsf{N}}(\mathcal{H})\leq d_{\mathsf{N}}$ and any weak ERM oracle
$\mathcal{O}^{\mathsf{erm,w}}$ for $\mathcal{H}$, the class $\mathcal{H}$ is
$(\mathcal{O}^{\mathsf{erm,w}};\epsilon,\delta)$-agnostically PAC learnable
with sample complexity
$n=\tilde{O}\left(\frac{d_{\mathsf{N}}^{3}\log^{4}(K/\delta)}{\epsilon^{2}}\right)$
and oracle complexity $K\cdot\operatorname{poly}(n)$.

The $\tilde{O}(\cdot)$ above hides factors that are polynomial in
$\log(1/\epsilon),\log(d_{\mathsf{N}}),\log(K/\delta)$. It is straightforward
to show that oracle complexity growing linearly in $K$ is necessary if one
only uses a weak ERM or consistency oracle, by considering the case where
$\mathcal{H}$ is a class that consists of a single unknown hypothesis on a
large domain $\mathcal{X}$, and where the covariates are uniformly distributed
on $\mathcal{X}$.

It is known that for any class $\mathcal{H}\subset[K]^{\mathcal{X}}$, the
sample complexity of PAC learning $\mathcal{H}$ is always within a polynomial
factor of the DS dimension of $\mathcal{H}$, denoted
$d_{\mathsf{DS}}(\mathcal{H})$ [BCD+22], and is in particular bounded below by
$\Omega(d_{\mathsf{DS}}(\mathcal{H}))$ (see Section H.1 for a definition of
the DS dimension). Moreover, we always have $d_{\mathsf{N}}(\mathcal{H})\leq
d_{\mathsf{DS}}(\mathcal{H})\leq O(d_{\mathsf{N}}(\mathcal{H})\cdot\log K)$.
Thus, the sample complexity obtained by the oracle-efficient algorithms
$\mathsf{Alg}^{\mathsf{R}},\mathsf{Alg}^{\mathsf{A}}$ of Theorem 4.1 comes
within a $\operatorname{poly}\log K$ factor of the optimal sample complexity.
While the $\log K$ factor is unlikely to be large in many applications, it is
nevertheless of theoretical interest to wonder if there is an oracle-efficient
algorithm with sample complexity
$\operatorname{poly}(d_{\mathsf{DS}}(\mathcal{H}))$, even if one allows a
_strong_ ERM oracle. We show in Theorem H.2 (Appendix H) that no such
algorithm exists, even if we restrict $d_{\mathsf{DS}}(\mathcal{H})=1$.

###  4.2 Real-valued concept classes

Our bounds for the regression setting are phrased in terms of _fat-shattering
dimension_ : for a real-valued concept class
$\mathcal{H}\subset[0,1]^{\mathcal{X}}$ and $\gamma\in(0,1)$, its _fat-
shattering dimension at scale $\gamma$_, denoted
$d_{\mathsf{fat},{\gamma}}(\mathcal{H})$, is the largest positive integer $d$
so that there exist $x_{1},\ldots,x_{d}\in\mathcal{X}$ and
$s_{1},\ldots,s_{d}\in[0,1]$ so that, for all $b\in\\{0,1\\}^{d}$, there is
some $h\in\mathcal{H}$ so that $h(x_{i})\geq s_{i}+\gamma$ if $b_{i}=1$ and
$h(x_{i})\leq s_{i}-\gamma$ if $b_{i}=0$. It is known that finiteness of the
fat-shattering dimension at all scales $\gamma$ is a sufficient condition for
learnability in both the realizable and agnostic settings, and that a sample
complexity scaling nearly linearly with the fat-shattering dimension at an
appropriate scale can be obtained by outputting an empirical risk minimizer of
$\mathcal{H}$ on an i.i.d. sample (which requires access to a strong ERM
oracle) [Lon01, BL98, ABDCBH97]. Theorem 4.2 shows that we can extend this
result to the setting where we only have a weak ERM oracle, with a polynomial
cost in the sample complexity.

######  Theorem 4.2 (Oracle-efficient regression).

For any $\delta\in(0,1)$, $n\in\mathbb{N}$, and function $\gamma\mapsto
d_{\mathsf{fat},{\gamma}}\in\mathbb{N}$ (for $\gamma\in(0,1)$), the following
statements hold:

  1. 1.

There is an algorithm $\mathsf{Alg}^{\mathsf{R}}$ so that for any class
$\mathcal{H}\subset[0,1]^{\mathcal{X}}$ satisfying
$d_{\mathsf{fat},{\gamma}}(\mathcal{H})\leq d_{\mathsf{fat},{\gamma}}$ for all
$\gamma$ and any weak range oracle $\mathcal{O}^{\mathsf{range}}$ for
$\mathcal{H}$, the class $\mathcal{H}$ is
$(\mathcal{O}^{\mathsf{range}};\epsilon,\delta)$-PAC learnable with sample
complexity $n$ and oracle complexity $\operatorname{poly}(n)$, for
$\epsilon=\inf_{\gamma\in[0,1]}\left\\{O(\gamma)+\tilde{O}\left(\frac{d_{\mathsf{fat},{\gamma}}^{3}\cdot\log(1/\delta)}{n}\right)\right\\}$.

  2. 2.

There is an algorithm $\mathsf{Alg}^{\mathsf{A}}$ so that for any class
$\mathcal{H}\subset[0,1]^{\mathcal{X}}$ satisfying
$d_{\mathsf{fat},{\gamma}}(\mathcal{H})\leq d_{\mathsf{fat},{\gamma}}$ for all
$\gamma$ and any weak ERM oracle $\mathcal{O}^{\mathsf{erm,w}}$ for
$\mathcal{H}$, the class $\mathcal{H}$ is
$(\mathcal{O}^{\mathsf{erm,w}};\epsilon,\delta)$-agnostically PAC learnable
with sample complexity $n$ and oracle complexity $\operatorname{poly}(n)$, for
$\epsilon=\inf_{\gamma\in[0,1]}\left\\{O(\gamma)+\tilde{O}\left(\sqrt{\frac{d_{\mathsf{fat},{\gamma}}^{3}\cdot\log(1/\delta)}{n}}\right)\right\\}.$

The $\tilde{O}(\cdot)$ above hides factors that are polynomial in
$\log(n),\log(d_{\mathsf{fat},{\gamma}}),\log\log(1/\delta)$. In the agnostic
setting the fat-shattering dimension is known to characterize PAC
learnability, and thus Theorem 4.2 shows that the price to pay for oracle-
efficiency with respect to $\mathcal{O}^{\mathsf{erm,w}}$ is only a polynomial
(assuming reasonable growth of $d_{\mathsf{fat},{\gamma}}$). In contrast, in
the realizable setting, the sample complexity is characterized by a different
quantity known as _the one-inclusion graph (OIG) dimension_ [AHK+23], which
can be smaller than the fat-shattering dimension by an arbitrarily large
factor. We show in Theorem H.3 (Section H.2) that, even with a strong ERM
oracle, it is impossible to obtain an oracle-efficient algorithm even for
classes whose OIG dimension is a constant.

## Acknowledgements

CD is supported by NSF Awards CCF-1901292, DMS-2022448, and DMS2134108, a
Simons Investigator Award, and the Simons Collaboration on the Theory of
Algorithmic Fairness. NG is supported by a Fannie & John Hertz Foundation
Fellowship and an NSF Graduate Fellowship.

## References

  * [AACSZ23] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy.  Optimal pac bounds without uniform convergence, 2023.
  * [AAD+23] Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, and Maxwell K. Fishelson.  Online learning and solving infinite games with an erm oracle.  In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 274–324. PMLR, 12–15 Jul 2023.
  * [ABDCBH97] Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler.  Scale-sensitive dimensions, uniform convergence, and learnability.  J. ACM, 44(4):615–631, jul 1997.
  * [AHHM21] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran.  A theory of pac learnability of partial concept classes.  2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671, 2021.
  * [AHK+23] Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, and Grigoris Velegkas.  Optimal learners for realizable regression: Pac learning and online learning, 2023.
  * [AHM22] Idan Attias, Steve Hanneke, and Yishay Mansour.  A characterization of semi-supervised adversarially robust PAC learnability.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [AKKS20] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun.  Flambe: Structural complexity and representation learning of low rank mdps.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20095–20107. Curran Associates, Inc., 2020.
  * [AKS04] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  Primes is in p.  Annals of Mathematics, 160:781–793, 2004.
  * [Ang88] Dana Angluin.  Queries and concept learning.  Mach. Learn., 2(4):319–342, apr 1988.
  * [BCD+22] N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff.  A characterization of multiclass learnability.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943–955, Los Alamitos, CA, USA, nov 2022. IEEE Computer Society.
  * [BDGR22] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin.  Smoothed online learning is as easy as statistical learning.  In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1716–1786. PMLR, 02–05 Jul 2022.
  * [BDMM23] Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran.  Multiclass boosting: Simple and intuitive weak learning criteria.  In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
  * [BEHW89] Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth.  Learnability and the vapnik-chervonenkis dimension.  J. ACM, 36(4):929–965, oct 1989.
  * [BHM+21] Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E Schapire.  Multiclass boosting and the cost of weak learning.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 3057–3067. Curran Associates, Inc., 2021.
  * [BHM23] Nataly Brukhim, Steve Hanneke, and Shay Moran.  Improper multiclass boosting.  In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5433–5452. PMLR, 12–15 Jul 2023.
  * [BL98] Peter L. Bartlett and Philip M. Long.  Prediction, learning, uniform convergence, and scale-sensitive dimensions.  Journal of Computer and System Sciences, 56(2):174–190, 1998.
  * [BMR+20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877–1901. Curran Associates, Inc., 2020.
  * [DB15] Alexey Dosovitskiy and Thomas Brox.  Inverting visual representations with convolutional networks.  2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4829–4837, 2015.
  * [DBJ+23] Adam Dziedzic, Franziska Boenisch, Mingjian Jiang, Haonan Duan, and Nicolas Papernot.  Sentence embedding encoders are easy to steal but hard to defend.  In ICLR 2023 Workshop on Pitfalls of limited data and computation for Trustworthy ML, 2023.
  * [DMY16] Ofir David, Shay Moran, and Amir Yehudayoff.  Supervised learning through the lens of compression.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * [DSBDSS11] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the erm principle.  In Sham M. Kakade and Ulrike von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 207–232, Budapest, Hungary, 09–11 Jun 2011. PMLR.
  * [DSS14] Amit Daniely and Shai Shalev-Shwartz.  Optimal learners for multiclass problems.  In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 287–316, Barcelona, Spain, 13–15 Jun 2014. PMLR.
  * [FKQR21] Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making, 2021.
  * [HHSY22] Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang.  Oracle-efficient online learning for smoothed adversaries.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [HL95] David Haussler and Philip M Long.  A generalization of sauer’s lemma.  Journal of Combinatorial Theory, Series A, 71(2):219–240, 1995\.
  * [HLW88] D. Haussler, N. Littlestone, and M.K. Warmuth.  Predicting (0, 1)-functions on randomly drawn points.  In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 100–109, 1988.
  * [HP23] Lunjia Hu and Charlotte Peale.  Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1–72:30, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [KSH12] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
  * [KTP+20] Kalpesh Krishna, Gaurav Singh Tomar, Ankur P. Parikh, Nicolas Papernot, and Mohit Iyyer.  Thieves on sesame street! model extraction of bert-based apis.  In International Conference on Learning Representations, 2020.
  * [KV91] Samir Khuller and Vijay V. Vazirani.  Planar graph coloring is not self-reducible, assuming p not np.  Theoretical Computer Science, 88(1):183–189, 1991.
  * [Len11] Arjen K. Lenstra.  Integer Factoring, pages 611–618.  Springer US, Boston, MA, 2011.
  * [Lon01] Philip M. Long.  On agnostic learning with {0, *, 1}-valued and real-valued hypotheses.  In COLT/EuroCOLT, 2001.
  * [LPW06] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.  Markov chains and mixing times.  American Mathematical Society, 2006.
  * [LW03] Nick Littlestone and Manfred K. Warmuth.  Relating data compression and learnability.  2003\.
  * [MFR23] Zakaria Mhammedi, Dylan J. Foster, and Alexander Rakhlin.  Representation learning with multi-step inverse kinematics: an efficient and optimal approach to rich-observation rl.  In Proceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org, 2023.
  * [MS13] Indraneel Mukherjee and Robert E. Schapire.  A theory of multiclass boosting.  J. Mach. Learn. Res., 14(1):437–497, feb 2013.
  * [MZC+23] John X. Morris, Wenting Zhao, Justin T. Chiu, Vitaly Shmatikov, and Alexander M. Rush.  Language model inversion, 2023.
  * [RV03] Steffen Reith and Heribert Vollmer.  Optimal satisfiability for propositional calculi and constraint satisfaction problems.  Inf. Comput., 186(1):1–19, oct 2003.
  * [SF12] Robert E. Schapire and Yoav Freund.  Boosting: Foundations and Algorithms.  The MIT Press, 2012.
  * [SLX22] David Simchi-Levi and Yunzong Xu.  Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.  Math. Oper. Res., 47(3):1904–1931, aug 2022.
  * [SS98] Robert E. Schapire and Yoram Singer.  Improved boosting algorithms using confidence-rated predictions.  In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT’ 98, page 80–91, New York, NY, USA, 1998\. Association for Computing Machinery.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning: From Theory to Algorithms.  Cambridge University Press, USA, 2014.
  * [TZJ+16] Florian Tramèr, Fan Zhang, Ari Juels, Michael K. Reiter, and Thomas Ristenpart.  Stealing machine learning models via prediction apis.  In Proceedings of the 25th USENIX Conference on Security Symposium, SEC’16, page 601–618, USA, 2016. USENIX Association.
  * [VC68] Vladimir Vapnik and A Ya Chervonenkis.  Algorithms with complete memory and recurrent algorithms in the problem of learning pattern recognition.  Avtomat. i Telemekh, 4:95–106, 1968.
  * [VC74] V. Vapnik and A. Chervonenkis.  Theory of Pattern Recognition [in Russian].  Nauka, Moscow, 1974.  (German Translation: W. Wapnik & A. Tscherwonenkis, Theorie der Zeichenerkennung, Akademie–Verlag, Berlin, 1979).
  * [WSS20] Eric Wallace, Mitchell Stern, and Dawn Song.  Imitation attacks and defenses for black-box machine translation systems.  In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5531–5546, Online, November 2020. Association for Computational Linguistics.

##  Appendix A Helpful lemmas

In this section we collect various probabilistic lemmas which are used
throughout the proofs. Fix $n\in\mathbb{N}$, and consider the hypercube
$V_{n}=\\{0,1\\}^{n}$. For some $v\in V$, we consider the lazy random walk on
$V_{n}$, denoted $Z_{v}^{(0)},Z_{v}^{(1)},\ldots$, where $Z_{v}^{(0)}$, and
$Z_{v}^{(t)}$ is generated from $Z_{v}^{(t-1)}$ by picking $i\in[n]$ uniformly
at random and flipping the $i$th coordinate of $Z_{v}^{(t-1)}$ with
probability $1/2$.

######  Lemma A.1 (Mixing time of the hypercube; [LPW06]).

Consider $n\in\mathbb{N}$, $v\in V_{n}$, and let
$Z_{v}^{(0)},Z_{v}^{(1)},\ldots$ denote the lazy random walk on the hypercube
$V_{n}$. Let $U$ be a uniformly distributed random variable on $V_{n}$. Then
for any $\epsilon\in(0,1)$ and $t\geq n\log n+n\log(1/\epsilon)$, it holds
that $D_{\mathsf{TV}}({Z_{v}^{(t)}},{U})\leq\epsilon.$

######  Lemma A.2 (Sauer-Shelah; [SSBD14]).

If $\mathcal{H}\subset\\{0,1,*\\}^{\mathcal{X}}$ is a partial concept class
with VC dimension $d$ and $X\in\mathcal{X}^{m}$, then
$|\mathcal{H}|_{X}|\leq(em/d)^{d}$.

The following result is a corollary of Freedman’s inequality.

######  Lemma A.3 (Lemma A.3 of [FKQR21]).

Let $(X_{t})_{t\in[T]}$ be a sequence of random variables adapted to a
filtration $(\mathcal{F}_{t})_{t\in[T]}$. If $0\leq X_{t}\leq R$ almost surely
for all $t\in[T]$, then with probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}\mathbb{E}[X_{t}\mid\mathcal{F}_{t-1}]\leq
2\sum_{t=1}^{T}X_{t}+8R\log(2/\delta).$

##  Appendix B Manipulating a weak ERM oracle

In this section, we prove some lemmas showing that a weak ERM oracle can be
used to implement a slightly stronger oracle which, given a dataset
$S=\\{(x_{i},y_{i})\\}_{i\in[n]}\in(\mathcal{X}\times\mathcal{Y})^{n}$, gives
the values of $h^{\star}(x_{i})$ for $i\in[n]$, where $h^{\star}$ is a risk-
minimizing element of $\mathcal{H}$.

###  B.1 Weak ERM oracle: binary-valued labels

Algorithm 2 Finding the ERM minimizer on a sample from a weak ERM oracle

1:Concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$, weak ERM oracle
$\mathcal{O}^{\mathsf{erm,w}}$, binary-valued loss function
$\ell:\mathcal{Y}\times\mathcal{Y}\to\\{0,1\\}$, sample
$S=\\{(x_{i},y_{i})\\}_{i=1}^{n}\in(\mathcal{X}\times\mathcal{Y})^{n}$.

2:function SampleERM.Binary($S,\ell,\mathcal{O}^{\mathsf{erm,w}}$)

3: Set $\mathcal{I}\leftarrow[n]$.

4: while There is $i\in\mathcal{I}$ so that
$\mathcal{O}^{\mathsf{erm,w}}(\\{x_{j},y_{j}^{\prime})\\}_{j\in\mathcal{I}}>\mathcal{O}^{\mathsf{erm,w}}(\\{(x_{j},y_{j}^{\prime})\\}_{j\in\mathcal{I}\backslash\\{i\\}})$
do

5: Remove such $i$ from $\mathcal{I}$.

6: For each $i\in[n]$, set
$z_{i}\leftarrow\mathbbm{1}\\{{i\not\in\mathcal{I}}\\}$.

7: Return $(z_{1},\ldots,z_{n})$.

We begin with the case of binary-valued loss functions.

######  Lemma B.1.

Consider a concept class $\mathcal{H}\subset\mathcal{Y}^{\mathcal{X}}$ and a
binary-valued loss function $\ell:\mathcal{Y}\times\mathcal{Y}\to\\{0,1\\}$.
Let $\mathcal{O}^{\mathsf{erm,w}}$ be a weak ERM oracle for the class
$\mathcal{H}$ and loss function $\ell$ (Definition 2.5). Then for any dataset
$S=\\{(x_{i},y_{i})\\}_{i\in[n]}\in(\mathcal{X}\times\mathcal{Y})^{n}$, the
algorithm $\texttt{SampleERM.Binary}(S,\ell,\mathcal{O}^{\mathsf{erm,w}})$
(Algorithm 2) makes $O(n^{2})$ calls to $\mathcal{O}^{\mathsf{erm,w}}$ and
outputs a vector $(z_{1},\ldots,z_{n})\in\\{0,1\\}^{n}$ so that, for some
empirical minimizer
$h^{\star}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\sum_{i=1}^{n}\ell(h(x_{i}),y_{i})$,
we have $z_{i}=\ell(h^{\star}(x_{i}),y_{i})$ for all $i\in[n]$.

###### Proof.

Fix $\mathcal{H},\ell,\mathcal{O}^{\mathsf{erm,w}}$, and $S$. Let the number
of iterations of the while loop be denoted $N$. For $0\leq t\leq N$, let
$\mathcal{I}_{t}$ denote the value of the set $\mathcal{I}$ in
$\texttt{SampleERM.Binary}(S,\ell,\mathcal{O}^{\mathsf{erm,w}})$ directly
after round $t$ (so that, in particular, $\mathcal{I}_{0}=[n]$). Note that
each iteration of the while loop, $\mathcal{I}$ decreases in size by 1.
Moreover, on round $t$ of the while loop, letting $i_{t}$ denote the chosen
$i\in\mathcal{I}_{t-1}$, we have

$\displaystyle\min_{h\in\mathcal{H}}\sum_{j\in\mathcal{I}_{t-1}}\ell(h(x_{j}),y_{j})>\min_{h\in\mathcal{H}}\sum_{j\in\mathcal{I}_{t-1}\backslash
i_{t}}\ell(h(x_{j}),y_{j})=\min_{h\in\mathcal{H}}\sum_{j\in\mathcal{I}_{t}}\ell(h(x_{j}),y_{j})\geq\min_{h\in\mathcal{H}}\sum_{j\in\mathcal{I}_{t-1}}\ell(h(x_{j}),y_{j})-1.$

It follows that for $1\leq t\leq N$,
$\min_{h\in\mathcal{H}}\sum_{j\in\mathcal{I}_{t}}\ell(h(x_{j}),y_{j})=\min_{h\in\mathcal{H}}\sum_{j\in[n]}\ell(h(x_{j}),y_{j})-t$.

Note also that we must have
$\min_{h\in\mathcal{H}}\sum_{j\in\mathcal{I}_{N}}\ell(h(x_{j}),y_{j})=0$, as
otherwise we could remove some $i$ from $\mathcal{I}_{N}$ and decrease the
empirical loss. Thus,
$N=\min_{h\in\mathcal{H}}\sum_{j\in[n]}\ell(h(x_{j}),y_{j})$. Moreover, there
is some $h^{\star}\in\mathcal{H}$ so that $\ell(h(x_{j}),y_{j})=0$ for each
$j\in\mathcal{I}_{N}$.

If any $i\in[n]\backslash\mathcal{I}_{N}$ satisfies
$\ell(h^{\star}(x_{i}),y_{i})=0$, then we would have
$\sum_{j\in[n]}\ell(h(x_{j}),y_{j})<n-|\mathcal{I}_{N}|=N$, which is a
contradiction. Thus,
$\ell(h^{\star}(x_{i}),y_{i})=\mathbbm{1}\\{{i\not\in\mathcal{I}_{N}}\\}$ for
all $i\in[n]$, as desired.

The total number of oracle calls made in Algorithm 2 is at most $2n^{2}$: we
certainly have $N\leq n$, and each round of the while loop requires at most
$|\mathcal{I}|+1\leq 2n$ calls to $\mathcal{O}^{\mathsf{erm,w}}$. ∎

###  B.2 Weak ERM oracle: real-valued labels

Next, we prove an analogue of Lemma B.1 for real-valued loss functions; to
keep the oracle complexity bounded, we need to tolerate some approximation
error.

######  Lemma B.2.

Consider a concept class $\mathcal{H}\subset[0,1]^{\mathcal{X}}$. Let
$\mathcal{O}^{\mathsf{erm,w}}$ be a weak ERM oracle for the class
$\mathcal{H}$ and absolute loss function $\ell^{\mathsf{abs}}$ (Definition
2.5). Then for any dataset
$S=\\{(x_{i},y_{i})\\}_{i\in[n]}\in(\mathcal{X}\times[0,1])^{n}$ and
$\gamma\in(0,1)$, the algorithm
$\texttt{SampleERM.Real}(S,\ell,\mathcal{O}^{\mathsf{erm,w}},\gamma)$
(Algorithm 3) makes $O(n/\gamma)$ calls to $\mathcal{O}^{\mathsf{erm,w}}$ of
length $O(n)$ and outputs a vector $(z_{1},\ldots,z_{n})\in[0,1]^{n}$ so that,
for some $h^{\star}\in\mathcal{H}$ satisfying
$\sum_{i=1}^{n}\ell^{\mathsf{abs}}(h^{\star}(x_{i}),y_{i})\leq\inf_{h\in\mathcal{H}}\sum_{i=1}^{n}\ell^{\mathsf{abs}}(h(x_{i}),y_{i})$,
we have $|z_{i}-\ell(h^{\star}(x_{i}),y_{i})|\leq\gamma$ for all $i\in[n]$.

###### Proof.

Fix $\mathcal{H},\mathcal{O}^{\mathsf{erm,w}},S,\gamma$. For $0\leq i\leq n$,
let $\tilde{S}^{(i)}$ denote the value of $\tilde{S}$ directly after round
$i$, so that, in particular, $\tilde{S}^{(0)}=\emptyset$, and
$\tilde{S}^{(i)}$ consists of $n\cdot\lceil 1/\gamma\rceil$ copies of
$(x_{j},y_{j}^{\prime})$, for each $j\in[i]$. For $1\leq i\leq n$, let
$\Delta^{(i)}$ denote the value of $\Delta$ defined on round $i$. We show the
following claim:

######  Lemma B.3.

For each $0\leq i\leq n$, the following properties hold for any empirical risk
minimizer $h^{(i)}\in\operatorname*{arg\,min}_{h\in\mathcal{H}}\sum_{(x,y)\in
S^{(i)}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}}\ell^{\mathsf{abs}}(h(x),y)$:

  1. 1.

For each $j\leq i$, $h^{(i)}(x_{j})\in[y_{j}^{\prime},y_{j}^{\prime}+\gamma]$.

  2. 2.

$h^{(i)}$ is an empirical risk minimizer for
$S^{(i-1)}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}$.

###### Proof of Lemma B.3.

We prove the claim by induction on $i$, noting that there is nothing else to
establish for the base case $i=0$. To establish the inductive step, suppose
that both claims hold at steps $j<i$, for some $i\in[n]$. Let us write
$V_{i-1}:=\sum_{(x,y)\in\tilde{S}^{(i-1)}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}}\ell^{\mathsf{abs}}(h^{(i-1)}(x),y)$.
Taking $\ell=\lfloor h^{(i-1)}(x_{i})/\gamma\rfloor$ yields

$\displaystyle
V_{i,\ell}\leq\sum_{(x,y)\in\tilde{S}^{(i-1)}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}\cup\\{(x_{i},\gamma\ell),(x_{i},\gamma(\ell+1))\\}}\ell^{\mathsf{abs}}(h^{(i-1)}(x),y)\leq
V_{i-1}+\gamma,$

which yields that $V_{i,\ell_{i}^{\star}}\leq V_{i-1}+\gamma$. On the other
hand, since any function $h$ satisfies
$\sum_{(x,y)\in\\{(x_{i},\gamma\ell),(x_{i},\gamma(\ell+1))\\}}\ell^{\mathsf{abs}}(h(x),y)\geq\gamma$,
we must have that $V_{i,\ell}\geq V_{i-1}+\gamma$ for each $\ell$. It follows
that $V_{i}=V_{i,\ell_{i}^{\star}}=V_{i-1}+\gamma$, and that any empirical
risk minimizer $h^{(i)}$ for
$\tilde{S}^{(i)}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}$ satisfies the following two
properties:

  * •

$h^{(i)}(x_{i})\in[\gamma\ell_{i}^{\star},\gamma(\ell_{i}^{\star}+1)]=[y_{i}^{\prime},y_{i}^{\prime}+\gamma]$.

  * •

$h^{(i)}$ is an empirical risk minimizer on
$\tilde{S}^{(i-1)}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}$.

Thus the second claim of the lemma statement holds at step $i$. Moreover,
using the inductive hypothesis together with the first item above, we see that
$h^{(i)}(x_{j})\in[y_{j}^{\prime},y_{j}^{\prime}+\gamma]$ for all $j<i$. ∎

By Lemma B.3, any empirical risk minimizer $h^{(n)}$ for
$S^{(n)}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}$ satisfies
$h^{(n)}(x_{i})\in[y_{i}^{\prime},y_{i}^{\prime}+\gamma]$ for each $i\in[n]$
and moreover is also an empirical risk minimizer for $S$. This establishes the
claim of Lemma B.2. ∎

Algorithm 3 Finding the ERM minimizer on a sample from a weak ERM oracle

1:Concept class $\mathcal{H}\subset[0,1]^{\mathcal{X}}$, weak ERM oracle
$\mathcal{O}^{\mathsf{erm,w}}$, sample
$S=\\{(x_{i},y_{i})\\}_{i=1}^{n}\in(\mathcal{X}\times[0,1])^{n}$, accuracy
parameter $\gamma$ so that $1/\gamma\in\mathbb{N}$.

2:function SampleERM.Real($S,\gamma,\mathcal{O}^{\mathsf{erm,w}}$)

3: Initialize $\tilde{S}\leftarrow\emptyset$.

4: for $1\leq i\leq n$ do

5: for $0\leq\ell\leq 1/\alpha-1$ do

6: Set
$V_{i,\ell}\leftarrow\mathcal{O}^{\mathsf{erm,w}}(\tilde{S}\cup\\{(x_{j},y_{j})\\}_{j\in[n]}\cup\\{(x_{i},\alpha\ell),(x_{i},\alpha(\ell+1))\\})$.

7: Define $\ell_{i}^{\star}:=\operatorname*{arg\,min}_{0\leq\ell\leq
1/\alpha-1l}\\{V_{i,\ell}\\}$, and
$y_{i}^{\prime}:=\alpha\cdot\ell_{i}^{\star}$.

8: Add $(x_{i},y_{i}^{\prime})$ and $(y_{i}^{\prime}+\alpha)$ to $\tilde{S}$.

9: return the vector $(y_{1}^{\prime},\ldots,y_{n}^{\prime})$.

Algorithm 4 Implementing a real-valued consistency oracle with range queries

1:Concept class $\mathcal{H}\subset[0,1]^{\mathcal{X}}$, weak ERM oracle
$\mathcal{O}^{\mathsf{erm,w}}$, sample
$S=\\{(x_{i},\ell_{i},u_{i})\\}_{i\in[n]}\in(\mathcal{X}\times[0,1]^{2})^{n}$,
$i\in[n]$.

2:function SampleCon.Real($(S,\mathcal{O}^{\mathsf{erm,w}})$)

3: Set $S^{\prime}:=\bigcup_{i\in[n]}\\{(x_{i},\ell_{i}),(x_{i},u_{i})\\}$.

4: Set $V\leftarrow\mathcal{O}^{\mathsf{erm,w}}(S^{\prime})$.

5: return $\mathsf{True}$ if $V\leq\sum_{i=1}^{n}(u_{i}-\ell_{i})$, else
$\mathsf{False}$.

######  Lemma B.4.

Consider a concept class $\mathcal{H}\subset[0,1]^{\mathcal{X}}$ equipped with
a weak ERM oracle $\mathcal{O}^{\mathsf{erm,w}}$. Then for any
$S=\\{(x_{i},\ell_{i},u_{i})\\}_{i\in[n]}\in(\mathcal{X}\times[0,1]^{2})^{n}$
with $\ell_{i}\leq u_{i}$ for all $i$, the algorithm
$\texttt{SampleCon.Real}(S,\mathcal{O}^{\mathsf{erm,w}})$ (Algorithm 4)
outputs $\mathsf{True}$ if and only if there is some $h\in\mathcal{H}$
satisfying $\ell_{i}\leq h(x)\leq u_{i}$ for all $i\in[n]$.

###### Proof.

The lemma statement is immediate from the fact that there is $h\in\mathcal{H}$
satisfying $\ell_{i}\leq h(x)\leq u_{i}$ if and only if

$\displaystyle\inf_{h\in\mathcal{H}}\sum_{i=1}^{n}|h(x_{i})-\ell_{i}|+|h(x_{i})-u_{i}|=\sum_{i=1}^{n}(u_{i}-\ell_{i}).$

∎

##  Appendix C Proof of Theorem 3.2

###  C.1 Properties of the generating function

Given $m,\mathcal{S}\subset V_{m}=\\{0,1\\}^{m}$, and $v\in V_{m}$, recall the
definition of the hitting time $\tau_{\mathcal{S},v}$ in Eq. 4. We begin by
proving the following basic recursive property of the generating function
$M_{\mathcal{S},v}(\gamma)$ of the random walk on the hypercube graph $G_{m}$
defined in Section 3.1.

######  Lemma C.1.

Suppose $\mathcal{W}\subset\\{0,1\\}^{m}$ is given, and consider the
$m$-dimensional hypercube graph $G_{m}=(V,E)$. Then the following holds for
all $v\in\mathcal{W}$:

$\displaystyle
M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)=\frac{\gamma}{(2-\gamma)m}\sum_{i\in[m]}M_{\mathcal{W}^{\mathrm{c}},v^{\oplus
i}}(\gamma).$

###### Proof.

For any $v\in\mathcal{W}$ and $t>0$, we have

$\displaystyle\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v}=t)=\frac{1}{2}\cdot\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v}=t-1)+\frac{1}{2}\sum_{i=1}^{m}\frac{1}{m}\cdot\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v^{\oplus
i}}=t-1),$

where we have used the fact that for $v\in\mathcal{W}$, each of the $m$ edges
containing $v$, indexed by $i\in[m]$ has two vertices, namely $v$ and
$v^{\oplus i}$. Moreover, for $v\in\mathcal{W}$, we have that
$\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v}=0)=0$. Thus, for
$\gamma\in(0,1)$, we have

$\displaystyle M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)=$
$\displaystyle\sum_{t\geq
1}\gamma^{t}\cdot\left(\frac{1}{2}\cdot\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v}=t-1)+\frac{1}{2}\sum_{i=1}^{m}\frac{1}{m}\cdot\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v^{\oplus
i}}=t-1)\right)$ $\displaystyle=$ $\displaystyle\frac{\gamma}{2}\cdot
M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)+\frac{\gamma}{2m}\sum_{i=1}^{m}\sum_{t\geq
1}\gamma^{t-1}\cdot\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v^{\oplus
i}}=t-1)$ $\displaystyle=$ $\displaystyle\frac{\gamma}{2}\cdot
M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)+\frac{\gamma}{2m}\sum_{i=1}^{m}M_{\mathcal{W}^{\mathrm{c}},v^{\oplus
i}}(\gamma).$

Rearranging, we see that

$\displaystyle
M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)=\frac{\gamma}{(2-\gamma)m}\sum_{i\in[m]}M_{\mathcal{W}^{\mathrm{c}},v^{\oplus
i}}(\gamma),$

as desired. ∎

Lemma C.2 establishes an upper bound on the outdegree of the orientation
$\sigma_{F,\lambda}$ (defined in Eq. 1) induced by the function
$F(v):=M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)$.

######  Lemma C.2.

Given $m\in\mathbb{N}$, $\gamma\in(0,1)$, $\lambda\in[0,1]$, and
$\mathcal{W}\subset\\{0,1\\}^{m}$, write
$F(v):=M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)$ for $v\in\\{0,1\\}^{m}$. Then
the induced orientation $\sigma_{F,\lambda}$ satisfies

$\displaystyle\mathsf{outdeg}(\sigma_{F,\lambda})\leq\frac{m}{2}-(1-\gamma)\lambda
m\cdot\min_{v\in V}F(v).$

###### Proof.

Consider any $v\in\mathcal{W}$. As a consequence of Lemma C.1, we have

$\displaystyle m\cdot F(v)-\sum_{i\in[m]}F(v^{\oplus
i})=-m\cdot\frac{2(1-\gamma)}{\gamma}\cdot F(v).$ (7)

We compute

$\displaystyle\mathsf{outdeg}(v;\sigma_{F,\lambda})=$
$\displaystyle\sum_{i\in[m]}(1-\sigma_{F,\lambda}((i,e_{i,v}))(v))$
$\displaystyle=$ $\displaystyle\sum_{i\in[m]}\frac{1-\lambda\cdot(F(v^{\oplus
i})-F(v))}{2}$ $\displaystyle=$ $\displaystyle\frac{m}{2}+\frac{\lambda
m}{2}\cdot F(v)-\frac{\lambda}{2}\sum_{i\in[m]}F(v^{\oplus i})$
$\displaystyle=$ $\displaystyle\frac{m}{2}-\frac{(1-\gamma)\lambda
m}{\gamma}\cdot F(v)\leq\frac{m}{2}-(1-\gamma)\lambda m\cdot F(v),$ (8)

where the first equality uses that if $v^{\oplus
i}\in\mathcal{W}^{\mathrm{c}}$, then
$1-\sigma_{F,\lambda}((i,e_{i,v}))(v)=0\leq\frac{1-\lambda(1-F(v))}{2}$, and
the final equality uses Eq. 7. ∎

Next, Lemma C.3 lower bounds the function
$M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)$, which is needed to apply Lemma C.2.

######  Lemma C.3.

Let $m\geq 4$ be an integer, $\gamma\in(0,1)$, and
$\mathcal{W}\subset\\{0,1\\}^{m}$ be given. Then, if $\frac{1}{1-\gamma}\geq
4m\log m$ and $|\mathcal{W}|\leq\frac{1}{m}2^{m-2}$,

$\displaystyle\min_{v\in\mathcal{W}}M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)\geq\frac{1}{4e}.$

###### Proof.

Suppose for the purpose of contradiction that there is some $v\in\mathcal{W}$
for which $M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)<1/(4e)$. Let
$X_{v}^{(0)},X_{v}^{(1)},\ldots\in V$ denote the lazy random walk on the
$m$-dimensional hypercube, $G_{m}$, started at $v$. Since
$\gamma^{1/(1-\gamma)}\geq 1/e$ for all $\gamma<1$, we have that

$\displaystyle\frac{1}{e}\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v}\leq\lfloor
1/(1-\gamma)\rfloor)=\sum_{0\leq t\leq\lfloor
1/(1-\gamma)\rfloor}\gamma^{t}\cdot\operatorname{Pr}(\tau_{\mathcal{W}^{\mathrm{c}},v}=t)\leq
M_{\mathcal{W}^{\mathrm{c}},v}(\gamma).$ (9)

Let us write $L:=\lfloor 1/(1-\gamma)\rfloor$ and
$\tau=\tau_{\mathcal{W}^{\mathrm{c}},v}$. Note that the distribution of
$X_{v}^{(0)},\ldots,X_{v}^{(\tau)}$ is exactly the distribution of a lazy
random walk $Y_{v}^{(0)},\ldots,Y_{v}^{(\tau)}$ on the hypercube
$\\{0,1\\}^{m}$, up to the stopping time $\tau$. Let $U$ denote a uniformly
distributed random variable on $\\{0,1\\}^{m}$. By Lemma A.1 together with the
fact that $L\geq 1/(2(1-\gamma))\geq 2m\log(m)\geq m\log m+m\log(4)$, we have
that $D_{\mathsf{TV}}({Y_{v}^{(L)}},{U})\leq 1/4$. Let
$\bar{X}_{v}^{(t)}:=X_{v}^{(t\wedge\tau)}$ denote the stopped random walk,
with respect to the stopping time $\tau$.

Consider a coupling between the distributions $\\{\bar{X}_{v}^{(t)}\\}_{t\geq
0}$ and $\\{Y_{v}^{(t)}\\}_{t\geq 0}$ so that $\bar{X}_{v}^{(t)}=Y_{v}^{(t)}$
for all $t\leq\tau$, almost surely. Since $\tau>L$ with probability at least
$1-e\cdot M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)$ by Eq. 9, we have that
$\operatorname{Pr}(\bar{X}_{v}^{(L)}=Y_{v}^{(L)})\geq\operatorname{Pr}(\tau\geq
L)\geq 1-e\cdot M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)$, where the probability
is with respect to the coupling. It follows that
$D_{\mathsf{TV}}({\bar{X}_{v}^{(L)}},{Y_{v}^{(L)}})\leq e\cdot
M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)<1/4$. By the triangle inequality, we
have

$\displaystyle D_{\mathsf{TV}}({\bar{X}_{v}^{(L)}},{U})\leq e\cdot
M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)+1/4<1/2.$

Let $\bar{N}(\mathcal{W}):=\\{v\in\\{0,1\\}^{m}\ :\ v\in\mathcal{W}\mbox{ or
}\exists i\mbox{ s.t. }v^{\oplus i}\in\mathcal{W}\\}$ denote the union of
$\mathcal{W}$ and its neighborhood. Thus, we must have
$\operatorname{supp}(\bar{X}_{v}^{(L)})>2^{m-1}$, which contradicts
$|\mathcal{W}|\leq\frac{1}{m}2^{m-2}$ since
$\operatorname{supp}(\bar{X}_{v}^{(L)})\subset\bar{N}(\mathcal{W})$, and
$\bar{N}(\mathcal{W})\leq 2m|\mathcal{W}|\leq 2^{m-1}$.

∎

###  C.2 Transductive learning guarantee

###### Proof of Theorem 3.2.

Let us write $\gamma:=1-\frac{1}{C_{1}m\log m}$. Set
$\epsilon=\frac{1-\gamma}{16e}$ and
$L:=\lceil\log(2/\epsilon)/\log(1/\gamma)\rceil=\lceil\log(32e/(1-\gamma))/\log(1/\gamma)\rceil\leq
O(\log(1/(1-\gamma))/(1-\gamma))$. Moreover, write $\delta=\epsilon/2$ and
$U=C_{1}m^{2}\log^{3}m$; note that
$U=\Theta(\frac{\log(1/\delta)}{\epsilon^{2}})$.

Let us write $X=(x_{1},\ldots,x_{m})\in\mathcal{X}^{m}$,
$y=(y_{1},\ldots,y_{m})\in\\{0,1\\}^{m}$. Let $\mathcal{W}:=\mathcal{H}|_{X}$
be the projection of $\mathcal{H}$ onto $\mathcal{X}$ and $G_{m}=(V,E)$ denote
the $m$-dimensional hypercube graph. For $y^{\prime}\in\mathcal{W}$, recall
the definition of the stopping time
$\tau_{\mathcal{W}^{\mathrm{c}},y^{\prime}}$ in Eq. 4. Note that, for any
$y^{\prime}\in V$ and each $u\in U$, the random variable $T_{u}$ constructed
in
$\texttt{EstimatePotential}(X,y^{\prime},U,\gamma,\mathcal{O}^{\mathsf{con,w}})$
is distributed exactly according to
$L\wedge\tau_{\mathcal{W}^{\mathrm{c}},y^{\prime}}$. Thus, for any $\delta,U$
satisfying $U\geq C\log(1/\delta)/\epsilon^{2}$ for a sufficiently large
constant $C$, we have from Hoeffding’s inequality that with probability
$1-\delta$,

$\displaystyle\left|\frac{1}{U}\sum_{u=1}^{U}\gamma^{T_{u}}-\mathbb{E}[\gamma^{L\wedge\tau_{\mathcal{W}^{\mathrm{c}},y^{\prime}}}]\right|\leq$
$\displaystyle\epsilon/2.$ (10)

Moreover, by our choice of $L$, we have that, almost surely,

$\displaystyle\left|\gamma^{L\wedge\tau_{\mathcal{W}^{\mathrm{c}},y^{\prime}}}-\gamma^{\tau_{\mathcal{W}^{\mathrm{c}},y^{\prime}}}\right|\leq\gamma^{L}\leq\epsilon/2.$
(11)

Thus, combining Eqs. 10 and 11, with probability at least $1-\delta$, the
output of
$\texttt{EstimatePotential}(X,y^{\prime},U,\gamma,\mathcal{O}^{\mathsf{con,w}})$
satisfies

$\displaystyle\left|\frac{1}{U}\sum_{u=1}^{U}\gamma^{T_{u}}-M_{\mathcal{W}^{\mathrm{c}},y^{\prime}}(\gamma)\right|=\left|\frac{1}{U}\sum_{u=1}^{U}\gamma^{T_{u}}-\mathbb{E}[\gamma^{\tau_{\mathcal{W}^{\mathrm{c}},y^{\prime}}}]\right|\leq\epsilon.$
(12)

For $y^{\prime}\in\mathcal{W}$, define
$F(y^{\prime}):=M_{\mathcal{W}^{\mathrm{c}},y^{\prime}}(\gamma)$. For each
$i\in[m]$, write $y^{i,0}=(y_{-i},0)$ and $y^{i,1}=(y_{-i},1)$. Now consider
$i\in[m]$ for which $y^{i,0},y^{i,1}\in\mathcal{W}$. Note that
$\texttt{WeakRealizable}(S_{-i},x_{i},\gamma,\lambda,\mathcal{O}^{\mathsf{con,w}})$
calls
$\texttt{EstimatePotential}(X,y^{0},U,\gamma,\mathcal{O}^{\mathsf{con,w}})$
and
$\texttt{EstimatePotential}(X,y^{1},U,\gamma,\mathcal{O}^{\mathsf{con,w}})$.
These calls return values $\hat{F}(y^{i,0}),\hat{F}(y^{i,1})\in[0,1]$
respectively. Since can ensure, by our choices of the values $U,\delta$ above,
that $U\geq C\log(1/\delta)/\epsilon^{2}$ (by making $C_{1}$ sufficiently
large), it follows by Eq. 12 and a union bound that with probability at least
$1-2\delta$, for each $b\in\\{0,1\\}$,

$\displaystyle\left|\hat{F}(y^{i,b})-F(y^{i,b})\right|=\left|\hat{F}(y^{i,b})-M_{\mathcal{W}^{\mathrm{c}},y^{i,b}}(\gamma)\right|\leq\epsilon.$

Thus, with probability at least $1-2\delta$, the output
$\hat{y}_{i}:=\frac{1+(\hat{F}(y^{i,0})-\hat{F}(y^{i,1}))}{2}$ of
$\texttt{WeakRealizable}(S_{-i},x_{i},\gamma,1,\mathcal{O}^{\mathsf{con,w}})$
satisfies

$\displaystyle\left|\hat{y}_{i}-\sigma_{F,1}(e_{i,y})(y^{i,1})\right|=$
$\displaystyle\left|\frac{1+(\hat{F}(y^{i,0})-\hat{F}(y^{i,1}))}{2}-\frac{1+(F(y^{i,0})-F(y^{i,1}))}{2}\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\cdot|\hat{F}(y^{i,0})-F(y^{i,0})|+\frac{1}{2}\cdot|\hat{F}(y^{i,1})-F(y^{i,1})|\leq\epsilon,$

and thus, using that $y=y^{i,y_{i}}$,

$\displaystyle|\hat{y}_{i}-y_{i}|=|\hat{y}_{i}-\sigma_{F,1}(e_{i,y})(y^{i,1})|+|\sigma_{F,1}(e_{i,y})(y^{i,1})-y_{i}|\leq\epsilon+(1-\sigma_{F,1}(e_{i,y})(y)).$

By our choice of $\delta={\epsilon/2}$, it follows that, for each $i\in[m]$,

$\displaystyle\mathbb{E}\left[\ell^{\mathsf{bin}}(\mathscr{A}(S_{-i};x_{i}),y_{i})\right]=$
$\displaystyle\mathbb{E}\left[|\hat{y}_{i}-y_{i}|\right]\leq
2\delta+\epsilon+(1-\sigma_{F,1}(e_{i,y})(y))=2\epsilon+(1-\sigma_{F,1}(e_{i,y})(y)).$
(13)

Next, the Sauer-Shelah lemma (Lemma A.2) gives that
$|\mathcal{W}|=|\mathcal{H}|_{X}|\leq(em/d)^{d}\leq\frac{1}{m}2^{m-2}$, since
we have chosen $m\geq C_{1}d\log d$ for a sufficiently large constant $C_{1}$.
Thus, by our choice of $\gamma=1-\frac{1}{C_{1}m\log m}$ and Lemma C.3 we have
that
$\min_{v\in\mathcal{W}}F(v)=\min_{v\in\mathcal{W}}M_{\mathcal{W}^{\mathrm{c}},v}(\gamma)\geq
1/(4e)$. We may now compute

$\displaystyle\sum_{i\in[m]}\mathbb{E}[\ell^{\mathsf{bin}}(\mathscr{A}(S_{-i};x_{i}),y_{i})]\leq$
$\displaystyle 2\epsilon m+\sum_{i\in[m]}(1-\sigma_{F,1}(e_{i,y})(y))$
$\displaystyle=$ $\displaystyle 2\epsilon m+\mathsf{outdeg}(y;\sigma_{F,1})$
$\displaystyle\leq$ $\displaystyle 2\epsilon
m+\frac{m}{2}-\frac{(1-\gamma)m}{4e}\leq\frac{m}{2}-\frac{(1-\gamma)m}{16e},$

where the first inequality uses Eq. 13, the second inequality uses Lemma C.2,
and the final inequality uses the choice of $\epsilon=\frac{1-\gamma}{16e}$. ∎

Finally, for use in applying Theorem 3.2, we state the following standard
lemma, which relates the transductive error of a learning algorithm
$\mathscr{A}$ to its expected error with respect to any realizable
distribution.

######  Lemma C.4 (Leave-one-out).

Let $P\in\Delta(\mathcal{X}\times\\{0,1\\})$ be $\mathcal{H}$-realizable and
$m\in\mathbb{N}$ be given. Furthermore, let
$\mathscr{A}(\cdot,\cdot):(\mathcal{X}\times\\{0,1\\})^{m-1}\times\mathcal{X}\to\\{0,1\\}$
be a (possibly randomized) mapping which takes as input a dataset of size
$m-1$ and a point in $\mathcal{X}$, and outputs a real number. Then

$\displaystyle\mathop{\mathbb{E}}_{S^{\prime}\sim
P^{m-1}}\mathop{\mathbb{E}}_{(X,Y)\sim
P}\mathop{\mathbb{E}}[\ell^{\mathsf{bin}}(\mathscr{A}(S^{\prime},X),Y)]=\mathop{\mathbb{E}}_{\begin{subarray}{c}S\sim
P^{m}\\\
S=\\{(x_{i},y_{i})\\}_{i\in[m]}\end{subarray}}\left[\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}[\ell^{\mathsf{bin}}(\mathscr{A}(S_{-i},x_{i}),y_{i})]\right],$

where the inner expectation is over the randomness in $\mathscr{A}$.

###### Proof.

Let $(x_{1},y_{1}),\ldots,(x_{m},y_{m}),(X,Y)$ denote i.i.d. samples from $P$,
and write
$S^{\prime}=\\{(x_{i},y_{i})\\}_{i\in[m-1]},S=\\{(x_{i},y_{i})\\}_{i\in[m]}$.
By exchangeability of these samples and linearity of expectation, we have

$\displaystyle\mathbb{E}_{S^{\prime}}\mathbb{E}_{(X,Y)\sim
P}\mathbb{E}[\ell^{\mathsf{bin}}(\mathscr{A}(S^{\prime},X),Y)]=$
$\displaystyle\mathbb{E}_{S^{\prime}}\mathbb{E}_{(x_{m},y_{m})\sim
P}\mathbb{E}[\ell^{\mathsf{bin}}(\mathscr{A}(S^{\prime},x_{m}),y_{m})]$
$\displaystyle=$
$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}_{S}\mathbb{E}[\ell^{\mathsf{bin}}(\mathscr{A}(S_{-i},x_{i}),y_{i})]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{S}\left[\frac{1}{m}\sum_{i=1}^{n}\mathbb{E}[\ell^{\mathsf{bin}}(\mathscr{A}(S_{-i},x_{i}),y_{i})]\right].$

∎

##  Appendix D Boosting

In this section, we discuss the technique of boosting, which is used to
upgrade a weak learner (in the sense of Definition 3.1) to a strong learner,
i.e., one which achieves error at most an arbitrary threshold
$\epsilon\in(0,1)$ with high probability. Notice that we allow a weak learner
to only possess its guarantee Eq. 2 _in expectation_ , rather than with high
probability. To account for this weaker assumption, it is necessary to
slightly modify standard boosting results [SF12, Chapters 3 & 4], as stated in
Lemma D.1 below. The main difference in the proofs is the use of an
appropriate martingale concentration inequality (namely, Lemma A.3) to deal
with the deviations in errors exhibited by the individual calls to the weak
learner by the boosting algorithm. Lemma D.1 gives a bound on the training
error of the Adaboost algorithm (Algorithm 5).

Algorithm 5 Adaboost (Algorithm 1.1 of [SF12])

1:Input dataset
$\\{(x_{i},y_{i})\\}_{i\in[n]}\subset(\mathcal{X}\times\\{0,1\\})^{n}$,
randomized weak learner $\mathscr{A}$, number of time steps $T$.

2:Initialize $D_{1}:=\operatorname{Unif}([n])\in\Delta([n])$.

3:for $1\leq t\leq T$ do

4: Sample a fresh string of uniform bits $R_{t}$ for use in $\mathscr{A}$ and
to sample $S_{t}$ in 5 below.

5: Sample an i.i.d. dataset $S_{t}$ of size $m$ from the distribution of
$x_{i},\ i\sim D_{t}$, so that $S_{t}\in(\mathcal{X}\times\\{0,1\\})^{m}$.

6: Let $h_{t}:\mathcal{X}\to\\{0,1\\}$ be the output of
$\mathscr{A}_{R_{t}}(S_{t},\cdot)$.

7: Define $\epsilon_{t}:=\operatorname{Pr}_{i\sim D_{t}}(h_{t}(x_{i})\neq
y_{i})$, and
$\alpha_{t}:=\frac{1}{2}\ln\left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)$.

8: For $i\in[n]$, define  $\displaystyle
D_{t+1}(i):=\frac{D_{t}(i)\cdot\exp(-\alpha_{t}\cdot(2y_{i}-1)\cdot(2h_{t}(x_{i})-1))}{Z_{t}},$
(14) where
$Z_{t}:=\sum_{j\in[n]}D_{t}(j)\cdot\exp(-\alpha_{t}\cdot(2y_{j}-1)\cdot(2h_{t}(x_{j})-1))$.

9:return the hypothesis $H:\mathcal{X}\to\\{0,1\\}$, where
$H(x):=\frac{1}{2}+\frac{1}{2}\mathrm{sign}\left(\sum_{t=1}^{T}\alpha_{t}\cdot(2h_{t}(x)-1)\right)$.

######  Lemma D.1 (Training error of Adaboost).

Let $m,n\in\mathbb{N}$ and $\eta\in(0,1)$ be given, and suppose algorithm
$\mathscr{A}$ is an $m$-sample weak learner with margin $\eta$ for the class
$\mathcal{H}$. Let $\bar{S}\in(\mathcal{X}\times\\{0,1\\})^{n}$ be an
$\mathcal{H}$-realizable sample. Then if Algorithm 5 is run for $T\geq\lceil
16\log(2n/\delta)/\eta^{2}\rceil$ rounds on $\bar{S}$, the output hypothesis
$H(x)$ satisfies $\widehat{\mathrm{er}}_{S}(H)=0$ with probability $1-\delta$.

Moreover, for $x\in\mathcal{X}$, to compute $H(x)$, one must only call
$\mathscr{A}(S_{t},x)$ for $T$ different choices of datasets
$S_{t}\in(\mathcal{X}\times\\{0,1\\})^{m}$.

###### Proof.

The proof follows closely to that in, e.g., [SF12, Chapter 3], with minor
modifications. We use the notation in Algorithm 5. Define
$F(x):=\sum_{t=1}^{T}\alpha_{t}h_{t}(x)$. From the definition of $Z_{t}$ in
Algorithm 5 we have, for $i\in[m]$,

$\displaystyle D_{T+1}(i)=$ $\displaystyle\frac{D_{1}(i)\cdot\exp(-y_{i}\cdot
F(x_{i}))}{Z_{1}\cdots Z_{T}}.$

For all $(x,y)\in\mathcal{X}\times\\{\pm 1\\}$, we have
$\mathbbm{1}\\{{H(x)\neq y}\\}\leq e^{-F(x)\cdot y}$. We can thus bound the
training error over the dataset $\\{(x_{i},y_{i})\\}_{i\in[n]}$ as follows:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{{H(x_{i})\neq
y_{i}}\\}\leq\sum_{i=1}^{n}D_{1}(i)\cdot e^{-F(x_{i})\cdot
y_{i}}=\sum_{i=1}^{n}D_{T+1}(i)\cdot(Z_{1}\cdots Z_{T})=Z_{1}\cdots Z_{T}.$
(15)

By the choice of
$\alpha_{t}=\frac{1}{2}\ln\left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)$ in
7 of Algorithm 5, we have

$\displaystyle Z_{t}=\sum_{j=1}^{n}D_{t}(j)\cdot e^{-\alpha_{t}\cdot
y_{j}h_{t}(x_{j})}=(1-\epsilon_{t})\cdot e^{-\alpha_{t}}+\epsilon_{t}\cdot
e^{\alpha_{t}}=2\sqrt{\epsilon_{t}(1-\epsilon_{t})}=\sqrt{1-4\gamma_{t}^{2}},$

where the second equality uses the fact that
$\sum_{j:y_{j}h_{t}(x_{j})=1}D_{t}(j)=1-\epsilon_{t}$ and
$\sum_{j:y_{j}h_{t}(x_{j})=-1}D_{t}(j)=\epsilon_{t}$, and we have written
$\gamma_{t}:=1/2-\epsilon_{t}$ for the final equality.

For each $t\in[T]$, let $\mathcal{F}_{t}$ denote the sigma-algebra generated
by $\\{(S_{s},h_{s})\\}_{1\leq s\leq t}$. Note that $D_{t}$ is measurable with
respect to $\mathcal{F}_{t-1}$. Since the distribution over $(x_{i},y_{i})$,
for $i\sim D_{t}$, is $\mathcal{H}$-realizable, the fact that $\mathscr{A}$ is
an $m$-sample weak learner with margin $\eta$ yields that for each $t$,
$\mathbb{E}\left[\epsilon_{t}\mid\mathcal{F}_{t-1}\right]\leq\frac{1}{2}-\eta$,
i.e., $\mathbb{E}[\gamma_{t}\mid\mathcal{F}_{t-1}]\geq\eta$. By Jensen’s
inequality it follows that
$\mathbb{E}[\gamma_{t}^{2}\mid\mathcal{F}_{t-1}]\geq\eta^{2}$. Note that
$\gamma_{t}^{2}\in[0,1]$ for all $t\in[T]$. Then by Lemma A.3 with $R=1$,
there is an event $\mathcal{E}$ occurring with probability $1-\delta$ so that,
under $\mathcal{E}$,
$\sum_{t=1}^{T}\gamma_{t}^{2}\geq\frac{1}{2}T\eta^{2}-4\log(2/\delta)$. Thus,
under the event $\mathcal{E}$, we have

$\displaystyle Z_{1}\cdots
Z_{T}=\left(\prod_{t=1}^{T}(1-4\gamma_{t}^{2})\right)^{1/2}\leq
e^{-2(\gamma_{1}^{2}+\cdots+\gamma_{T}^{2})}\leq
e^{-T\eta^{2}+8\log(2/\delta)}\leq e^{-T\eta^{2}/2}\leq\frac{1}{2n},$ (16)

where the second-to-last inequality above holds since we have chosen $T$ to
satisfy $T\geq\frac{16\log(2/\delta)}{\eta^{2}}$, and the final inequality
holds since $T$ also satisfies $T\geq\frac{2\log(2n)}{\eta^{2}}$. Combining
the above display and Eq. 15, we obtain that, under $\mathcal{E}$,
$\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{{H(x_{i})\neq y_{i}}\\}\leq 1/(2n)$,
which implies that $H(x_{i})=y_{i}$ for all $i\in[n]$. ∎

###  D.1 Generalization error of Adaboost

Next, using the technique of _sample compression schemes_ , and in particular
their connection to generalization (Lemma 2.1), we prove that the output
hypothesis $H$ of Adaboost generalizes well. Proposition D.2 carries out this
argument for the realizable setting, and Proposition D.3 does so for the
agnostic setting. Even in the agnostic setting, the input dataset for Adaboost
must still be realizable by $\mathcal{H}$, as the weak learner’s guarantee
depends on realizability. Thus, in the statement of Proposition D.3, we assume
that Adaboost is passed a subsample of maximum size which is
$\mathcal{H}$-realizable. Our final algorithm which agnostically learns
partial concept classes (Algorithm 6) will find such a subsample to pass to
Adaboost using a weak ERM oracle.

######  Proposition D.2 (Generalization error of Adaboost – realizable
setting).

Let $m,n\in\mathbb{N}$ and $\eta,\delta\in(0,1)$ be given, and suppose
algorithm $\mathscr{A}$ is an $m$-sample weak learner with margin $\eta$ for
the class $\mathcal{H}$. Let $P\in\Delta(\mathcal{X}\times\\{0,1\\})$ be
$\mathcal{H}$-realizable. Then if Algorithm 5 is run for $T=\lceil
16\log(4n/\delta)/\eta^{2}\rceil$ rounds on a dataset $\bar{S}\sim P^{n}$, the
random output hypothesis $H\in\\{0,1\\}^{\mathcal{X}}$ satisfies the following
with probability $1-\delta$:

$\displaystyle\mathrm{er}_{P}(H)\leq$ $\displaystyle
O\left(\frac{\log^{2}(n/\delta)\cdot(m+\log n)}{\eta^{2}n}\right).$

In particular, the probability is over the draw of $\bar{S}$.

###### Proof.

We use a compression-based argument, following [SF12, Chapter 4.2]. Let us
denote the input dataset to Algorithm 5 by
$\bar{S}\in(\mathcal{X}\times\\{0,1\\})^{n}$. We consider a distribution $Q$
over sample compression schemes on $n$-sample datasets, $(\kappa,\rho)$,
defined as follows. Given a dataset $\bar{S}$, let $S_{t},\alpha_{t},R_{t}$,
for $t\in[T]$, be the random variables generated in the course of the
procedure in Algorithm 5. Since the bits $R_{t}$ are used for the sampling
step in 5 and by $\mathscr{A}$ (where the portions of $R_{t}$ that are used
for the two tasks are independent), given a dataset $\bar{S}$, the random
variable $(S_{t},\alpha_{t})_{t\in[T]}$ is a deterministic function of
$(R_{t})_{t\in[T]}$ and $\bar{S}$. Then we define $(\rho,\kappa)$ to be the
distributed as the following (deterministic) function of $(R_{t})_{t\in[T]}$:

  * •

$\kappa$ maps a dataset $\bar{S}\in(\mathcal{X}\times\\{0,1\\})^{n}$ to
$\kappa(\bar{S})=((S_{1},\ldots,S_{T}),(\alpha_{1},\ldots,\alpha_{T}))$, where
$S_{t},\alpha_{t}$ are defined as a function of $(R_{t})_{t\in[T]}$ and
$\bar{S}$, as described above.

  * •

$\rho$ maps an input of the form
$((S_{1}^{\prime},\ldots,S_{T}^{\prime}),(\alpha_{1}^{\prime},\ldots,\alpha_{T}^{\prime}))$
(where $(S_{1}^{\prime},\ldots,S_{T}^{\prime})$ is a sequence of examples in
$\mathcal{X}\times\\{0,1\\}$ of length $Tm$ and
$(\alpha_{1}^{\prime},\ldots,\alpha_{T}^{\prime})$ is a sequence of real
numbers, encoded in binary) to the hypothesis
$x\mapsto\mathrm{sign}\left(\sum_{t=1}^{T}\alpha_{t}\cdot\mathscr{A}_{R_{t}}(S_{t},x)\right)$.

Since the values $\epsilon_{t}$ in Algorithm 5 lie in
$\\{0,1/n,2/n,\ldots,1\\}$, each parameter $\alpha_{t}$ can be encoded with
$O(\log n)$ bits. Thus, with probability 1 over $(\kappa,\rho)\sim Q$, we have
that the size of $\kappa$ (for input samples $\bar{S}$ of size $n$) is
$|\kappa|\leq O(T\cdot(m+\log(n)))$. Next, Lemma D.1 establishes that, for any
fixed $\mathcal{H}$-realizable $\bar{S}$, there is a set $\mathcal{E}$ of
compression schemes satisfying $Q(\mathcal{E})\geq 1-\delta$ so that, for all
$(\kappa,\rho)\in\mathcal{E}$,
$\widehat{\mathrm{er}}_{\bar{S}}(\rho(\kappa(\bar{S})))=0$. (Here we crucially
use that the output hypothesis of $\rho$ depends on the same random bits
$R_{t}$ used to generate the sequence $(S_{t},\alpha_{t})_{t\in[T]}$.)
Moreover, by Lemma 2.1 and our bound on the size of $\kappa$ drawn from $Q$,
there is a constant $C>0$ so that the following holds for any fixed
$(\kappa,\rho)\in\operatorname{supp}(Q)$: with probability $1-\delta$ over the
draw of $\bar{S}\sim P^{n}$,

$\displaystyle\mathrm{er}_{P}(\rho(\kappa(\bar{S})))\leq\mathbbm{1}\\{{\widehat{\mathrm{er}}_{\bar{S}}(\rho(\kappa(\bar{S})))=0}\\}+\frac{C}{n}\cdot\left(T\log(n)\cdot(m+\log
n)+\log\frac{1}{\delta}\right).$

By our choice of $T$ together with the fact that $Q(\mathcal{E})\geq
1-\delta$, it follows that with probability $1-2\delta$ over the draw of
$\bar{S}\sim P^{n}$, we have

$\displaystyle\mathrm{er}_{P}(\rho(\kappa(\bar{S})))\leq
C\cdot\frac{\log(2n^{2})\log(n)\cdot\frac{1}{\eta^{2}}\cdot(m+\log
n)+\log(1/\delta)}{n}.$

Since, for fixed $\bar{S}$, the distribution of $\rho(\kappa(\bar{S}))$ is the
distribution of the output hypothesis $H$ of Algorithm 5, the claim of the
proposition follows after rescaling $\delta$. ∎

######  Proposition D.3 (Generalization error of Adaboost – agnostic setting).

Let $m,n\in\mathbb{N}$ and $\eta,\delta\in(0,1)$ be given, and suppose
algorithm $\mathscr{A}$ is an $m$-sample weak learner with margin $\eta$ for
the class $\mathcal{H}$. Let $P\in\Delta(\mathcal{X}\times\\{0,1\\})$ be an
arbitrary distribution. Consider a procedure which samples a dataset
$\bar{S}\sim P^{n}$, deterministically chooses a subsample
$\tilde{S}\subset\bar{S}$ of maximum size which is realizable by
$\mathcal{H}$, and then runs Algorithm 5 for $T=\lceil
16\log(4n/\delta)/\eta^{2}\rceil$ rounds on $\tilde{S}$. Then the output
hypothesis $H(x)$ satisfies the following with probability $1-\delta$:

$\displaystyle\mathrm{er}_{P}(H)\leq\inf_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{\bar{S}}(h)+O\left(\sqrt{\frac{\log^{2}(n/\delta)\cdot(m+\log
n)}{\eta^{2}n}}\right).$

###### Proof.

The proof closely follows that of Proposition D.2. In particular, we consider
the same distribution $Q$ over sample compression schemes on datasets with (at
most) $n$-samples. We again have that with probability 1 over
$(\kappa,\rho)\sim Q$, $|\kappa|\leq O(T\cdot(m+\log n))$, and that, for any
fixed $\mathcal{H}$-realizable $\tilde{S}$, there is a set $\mathcal{E}$ of
compression schemes satisfying $Q(\mathcal{E})\geq 1-\delta$ so that, for all
$(\kappa,\rho)\in\mathcal{E}$,
$\widehat{\mathrm{er}}_{\tilde{S}}(\rho(\kappa(\tilde{S})))=0$.

Next, let the deterministic mapping from samples
$\bar{S}\in(\mathcal{X}\times\\{0,1\\})^{n}$ to $\tilde{S}$ be denoted by
$\Sigma$. For any compression scheme $(\kappa,\rho)\in\operatorname{supp}(Q)$,
note that $(\kappa\circ\Sigma,\rho)$ is a compression scheme of size
$|\kappa\circ\Sigma|\leq|\kappa|\leq O(T\cdot(m+\log n))$. Thus, by Lemma 2.1,
there is a constant $C>0$ so that, for any fixed
$(\kappa,\rho)\in\operatorname{supp}(Q)$, with probability $1-\delta$ over the
draw of $\bar{S}\sim P^{n}$,

$\displaystyle\mathrm{er}_{P}(\rho(\kappa(\Sigma(\bar{S}))))\leq\widehat{\mathrm{er}}_{\bar{S}}(\rho(\kappa(\Sigma(\bar{S}))))+C\sqrt{\frac{1}{n}\left(T\log(n)\cdot(m+\log
n)+\log(1/\delta)\right)}.$

The choice of $\Sigma$ yields that, if
$\bar{S}\in(\mathcal{X}\times\\{0,1\\})^{n}$ and $\tilde{S}=\Sigma(\bar{S})$,
then for any hypothesis $h^{\prime}$ satisfying
$\widehat{\mathrm{er}}_{\tilde{S}}(h^{\prime})=0$, we have

$\displaystyle\widehat{\mathrm{er}}_{\bar{S}}(h^{\prime})\leq\frac{n-|\tilde{S}|}{n}=\inf_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{\bar{S}}(h)$
(17)

Thus, by our choice of $T$, Eq. 17, and the fact that $Q(\mathcal{E})\geq
1-\delta$, it follows that with probability $1-2\delta$ over the draw of
$\bar{S}\sim P^{n}$,

$\displaystyle\mathrm{er}_{P}(\rho(\kappa(\Sigma(\bar{S}))))\leq\inf_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{\bar{S}}(h)+O\left(\sqrt{\frac{\log^{2}(n/\delta)\cdot(m+\log
n)}{\eta^{2}n}}\right).$

Since for fixed $\bar{S}$, the distribution of $\rho(\kappa(\Sigma(\bar{S})))$
is the distribution of the output hypothesis $H$ of Algorithm 5, the claim
follows after rescaling $\delta$. ∎

##  Appendix E Proof of Theorem 3.1

Algorithm 6 Oracle-efficient PAC learner for partial concept classes

1:Partial concept class $\mathcal{H}$, $n\in\mathbb{N}$, sample
$S=\\{(x_{i},y_{i})\\}_{i=1}^{n}\in(\mathcal{X}\times\\{0,1\\})^{n}$, weak
learner $\mathscr{A}$ for $\mathcal{H}$ with margin $\eta\in(0,1)$, failure
probability $\delta\in(0,1)$, weak ERM oracle $\mathcal{O}^{\mathsf{erm,w}}$
for $\mathcal{H}$, domain point $x\in\mathcal{X}$.

2:function RealizablePartial($S,x,\mathscr{A},\eta,\delta$)

3: Call Adaboost (Algorithm 5) on the dataset $S$ using the weak learner
$\mathscr{A}$ with $T=\lceil 16\log(4n/\delta)/\eta^{2}\rceil$, and denote its
output hypothesis by $H:\mathcal{X}\to\\{0,1\\}$.

4: return $H(x)$.

5:function
AgnosticPartial($S,x,\mathscr{A},\eta,\delta,\mathcal{O}^{\mathsf{erm,w}}$)

6: Let $z\in\\{0,1\\}^{n}$ be the output of
$\texttt{SampleERM.Binary}(S,x,\ell^{\mathsf{bin}},\mathcal{O}^{\mathsf{erm,w}})$.$\triangleright$
_( Algorithm 2)_

7: Define $\tilde{S}:=\\{(x_{i},y_{i})\ :\ z_{i}=0\\}$.

8: Call Adaboost (Algorithm 5) on the dataset $\tilde{S}$ using the weak
learner $\mathscr{A}$ with $T=\lceil 16\log(6n/\delta)/\eta^{2}\rceil$, and
denote its output hypothesis by $H:\mathcal{X}\to\\{0,1\\}$.

9: return $H(x)$.

The guarantees of Theorem 3.1 are established with the algorithms
RealizablePartial and AgnosticPartial (Algorithm 6). These algorithms call
Adaboost on an appropriate $\mathcal{H}$-realizable dataset and use
WeakRealizable as the weak learner. We remark that AgnosticPartial uses the
algorithm SampleERM.Binary (defined in Appendix B) to find the largest subset
of labels which can be realized by the class $\mathcal{H}$. Note that in the
algorithms’ descriptions we have stated that Adaboost returns a hypothesis
$H:\mathcal{X}\to\\{0,1\\}$. RealizablePartial and AgnosticPartial never have
to compute this entire hypothesis $H$, and instead only have to evaluate
$H(x)$, which, as we shall show, can be done using few calls to the oracle
$\mathcal{O}^{\mathsf{con,w}}$ or $\mathcal{O}^{\mathsf{erm,w}}$,
respectively.

###### Proof of Theorem 3.1.

Let $d_{\mathsf{VC}}\in\mathbb{N},\epsilon,\delta\in(0,1)$ be given. Let
$C_{1},C_{2}$ denote the constants of Theorem 3.2,
$m:=C_{1}d_{\mathsf{VC}}\log d_{\mathsf{VC}}$, and $\eta:=\frac{1}{C_{2}m\log
m}$. Let $\mathscr{A}$ denote the randomized mapping
$\mathscr{A}:(\mathcal{X}\times\\{0,1\\})^{m}\times\mathcal{X}\to\\{0,1\\}$
which, given as input $(S,x)$, returns
$\texttt{WeakRealizable}(S,x,\frac{1}{C_{1}m\log
m},1,C_{1}m^{2}\log^{3}m,\mathcal{O}^{\mathsf{con,w}})$ (see Algorithm 1). By
Theorems 3.2 and C.4, $\mathscr{A}$ is an $m$-sample weak learner with margin
$\eta$ for the class $\mathcal{H}$.

#### Realizable setting.

We take
$n=\frac{d_{\mathsf{VC}}^{3}\cdot\log(1/\delta)}{\epsilon}\cdot(c\log(d_{\mathsf{VC}}\log(1/\delta)/\epsilon))^{c}$,
for a sufficiently large constant $c$ as specified below. The output
hypothesis $H$ of Adaboost in RealizablePartial is a deterministic function of
$S$ and the random bits $R$ used in Adaboost (including in its calls to
$\mathscr{A}$). By Lemma D.1, for any $S$, with probability $1-\delta$ over
the draw of $R$, we have $\widehat{\mathrm{er}}_{S}(H)=0$. Moreover, by
Proposition D.2, with probability $1-\delta$ over the draw of $S,R$, we have

$\displaystyle\mathrm{er}_{P}(H)\leq
O\left(\frac{\log^{2}(n/\delta)\cdot(m+\log n)}{\eta^{2}n}\right).$

Combining the above inequality with our choice of $n$ and rescaling
$\epsilon,\delta$, we obtain that with probability $1-\delta$ over the draw of
$S\sim P^{n}$, $\mathrm{er}_{P}(H)\leq\epsilon$.

Finally, we analyze the oracle complexity of RealizablePartial: to compute the
value of $H(x)$, we need to compute the values $h_{t}(x)$ for the hypotheses
$h_{t}$, $t\in[T]$, defined in Adaboost. Given the value of $S_{t}$, each
computation of $h_{t}(x)$, for any $x\in\mathcal{X}$, requires a single run of
$\mathscr{A}(S_{t},x)$, which requires $\tilde{O}(m^{3})$ calls to
$\mathcal{O}^{\mathsf{con,w}}$ with datasets of size $m$ (Theorem 3.2). In
turn, the datasets $S_{t}$ are computed inductively as follows: given $S_{t}$,
we can compute $h_{t}(x_{i})$ for each $i\in[n]$, which requires
$\tilde{O}(nm^{3})$ calls to $\mathcal{O}^{\mathsf{con,w}}$. This in turn
allows us to compute $D_{t+1}$ (per Eq. 14), which then allows us to sample
$S_{t+1}$. Thus, overall, we need $\tilde{O}(nm^{3}\cdot
T)\leq\operatorname{poly}(n)$ calls to $\mathcal{O}^{\mathsf{con,w}}$ to
compute $H(x)$, each of which uses a dataset of size at most $n$. Hence the
cumulative oracle cost is $\operatorname{poly}(n)$.

#### Agnostic setting.

We take
$n=\frac{d_{\mathsf{VC}}^{3}\cdot\log(1/\delta)}{\epsilon^{2}}\cdot(c\log(d_{\mathsf{VC}}\log(1/\delta)/\epsilon))^{c}$,
for a sufficiently large constant $c$ as specified below. The output
hypothesis $H$ of Adaboost in AgnosticPartial is a deterministic function of
$S$ as well as the random bits $R$ used in Adaboost (including in its calls to
$\mathscr{A}$). By Lemma B.1, the set $\tilde{S}$ constructed from $S$ in
AgnosticPartial is a subset of $S$ of maximum size which is realizable by
$\mathcal{H}$. Thus, by Lemma D.1, for any $S$, with probability $1-\delta$
over the draw of $R$, the hypothesis $H$ satisfies
$\widehat{\mathrm{er}}_{\tilde{S}}(H)=0$.

Moreover, by Proposition D.3, the (random) output hypothesis $H$ of Adaboost
satisfies the below with probability $1-\delta$ over the draw of $S,R$:

$\displaystyle\mathrm{er}_{P}(H)\leq\inf_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{S}(h)+O\left(\sqrt{\frac{\log^{2}(n/\delta)\cdot(m+\log
n)}{\eta^{2}n}}\right).$ (18)

Since $n\geq\frac{C\log 1/\delta}{\epsilon^{2}}$ for a sufficiently large
constant $C$, McDiarmid’s inequality yields that with probability $1-\delta$
over the choice of $S\sim P^{n}$,

$\displaystyle\inf_{h\in\mathcal{H}}\widehat{\mathrm{er}}_{S}(h)\leq\mathbb{E}_{S^{\prime}\sim
P^{n}}\left[\inf_{h^{\prime}\in\mathcal{H}}\widehat{\mathrm{er}}_{S^{\prime}}(h^{\prime})\right]+\epsilon\leq\mathrm{er}_{P}(\mathcal{H})+\epsilon.$
(19)

Combining Eqs. 18 and 19 with our choice of $n$ and rescaling
$\epsilon,\delta$, we obtain that with probability $1-\delta$ over the draw of
$S\sim P^{n}$, we have
$\mathrm{er}_{P}(H)\leq\mathrm{er}_{P}(\mathcal{H})+\epsilon$.

Finally, note that, to compute the value $H(x)$, for any $x\in\mathcal{X}$, we
need a single call to $\mathcal{O}^{\mathsf{erm,w}}$ to compute $\tilde{S}$ (7
of Algorithm 6), and then need to compute the values $h_{t}(x)$ for the
hypotheses $h_{t}$, $t\in[T]$, defined in Adaboost. The oracle complexity of
these calls are analyzed in the same manner as in the realizable case, so we
again obtain $\operatorname{poly}(n)$ cumulative oracle cost. ∎

##  Appendix F Multiclass classification

In this section, we generalize our results on binary classification to the
setting of multiclass classification. We begin by establishing that a variant
of WeakRealizable yields a weak learner in the multiclass setting, in an
appropriate sense. It is less clear how to define a “weak learner” in the
multiclass setting than in the binary setting, and the literature on
multiclass boosting has identified several possible definitions (see [SF12,
Chapter 10] as well as many more recent works [MS13, BDMM23, BHM+21, BCD+22,
BHM23]). Our approach proceeds by defining a _partial binary_ concept class
given any multiclass classification problem, in Definition F.1 below. We will
then feed our weak learner for partial binary classes (WeakRealizable;
Algorithm 1) into Adaboost, and finally show how to translate good performance
of the boosted learner back to good performance for the original multiclass
problem.

Our approach is similar to the one taken in [SF12, Chapter 11] (which
originally appeared in [SS98]), where multiclass classification is reduced to
boosting with rankings and the Adaboost.MR algorithm is used. However, our
approach is syntactically different since the weak learner for a menu class
(in the sense of Definition F.1) takes as input _two labels_ together with the
covariate $x$, and must determine which of them is the correct label, in
contrast to [SS98] where the weak learner takes as input a single label
together with $x$ and outputs a scalar indicating how likely the label is to
be correct.

######  Definition F.1 (Menu class).

Consider a hypothesis class $\mathcal{H}\subset[K]^{\mathcal{X}}$, and let
$\mathcal{P}_{2}({K})$ denote the set of all length-2 vectors consisting of
distinct elements of $[K]$. We refer to the elements of $\mathcal{P}_{2}({K})$
as _menus_.888This terminology is inspired by [BCD+22, BHM23], which
considered such menus, though used them together with techniques distinct from
ours. Given $\mu\in\mathcal{P}_{2}({K}),k\in[K]$, we write $k\in\mu$ to mean
that $k$ is one of the two elements of $\mu$.

Given $h\in\mathcal{H}$ and
$(x,(\ell,k))\in\mathcal{X}\times\mathcal{P}_{2}({K})$, we define

$\displaystyle{h}^{\mathsf{menu}}(x,(\ell,k)):=\begin{cases}0&:h(x)=\ell\\\
1&:h(x)=k\\\ *&:\mbox{otherwise}.\end{cases}$

we let
$\mathscr{M}_{2}(\mathcal{H})\subset\\{0,1,*\\}^{\mathcal{X}\times\mathcal{P}_{2}({K})}$
denote the (binary) partial hypothesis class defined by

$\displaystyle\mathscr{M}_{2}(\mathcal{H}):=\left\\{(x,\mu)\mapsto{h}^{\mathsf{menu}}(x,\mu)\
:\ h\in\mathcal{H}\right\\}.$

We often refer to $\mathscr{M}_{2}(\mathcal{H})$ as the _menu class_ of
$\mathcal{H}$.

The below definition gives a procedure to map hypotheses in
$\\{0,1,*\\}^{\mathcal{X}\times\mathcal{P}_{2}({K})}$ to multiclass hypotheses
in $[K]^{\mathcal{X}}$.

######  Definition F.2 (Multiclass decoder).

We define a map
$\mathsf{Dec}^{\mathsf{mc}}:\\{0,1,*\\}^{\mathcal{X}\times\mathcal{P}_{2}({K})}\to[K]^{\mathcal{X}}$,
as follows. For $J:\mathcal{X}\times\mathcal{P}_{2}({K})\to\\{0,1,*\\}$, we
define $\mathsf{Dec}^{\mathsf{mc}}(J):=H$, where $H(x)$ is defined to be the
unique value $k\in[K]$ for which $J(x,(k,\ell))=0$ and $J(x,(\ell,k))=1$ for
all $\ell\in[K]\backslash\\{k\\}$, if such $k$ exists. Otherwise $H(x)$ is
defined to be 1.

Note that $\mathsf{Dec}^{\mathsf{mc}}$ depends on $K,\mathcal{X}$; for
simplicity, we omit this dependence in our notation. Lemma F.1 bounds the VC
dimension of the menu class of $\mathcal{H}$ in terms of the Natarajan
dimension of $\mathcal{H}$.

######  Lemma F.1.

For any $\mathcal{H}\subset[K]^{\mathcal{X}}$, it holds that
$d_{\mathsf{VC}}(\mathscr{M}_{2}(\mathcal{H}))\leq
O(d_{\mathsf{N}}(\mathcal{H})\log K)$.

###### Proof.

Let us write $d:=d_{\mathsf{VC}}(\mathscr{M}_{2}(\mathcal{H}))$, and let
$(x_{1},\mu_{1}),\ldots,(x_{d},\mu_{d})$ be shattered by
$\mathscr{M}_{2}(\mathcal{H})$. Note that the values $x_{1},\ldots,x_{d}$ are
all distinct, since no hypothesis ${h}^{\mathsf{menu}}$ can shatter the points
$(x,\mu),(x,\mu^{\prime})$ for distinct menus
$\mu,\mu^{\prime}\in\mathcal{P}_{2}({K})$. Thus, the number of vectors
$y\in[K]^{n}$ for which there exists $h\in\mathcal{H}$ so that
$y_{i}=h(x_{i})$, $i\in[n]$, is at least $2^{d}$. But the number of such $y$
may also be upper bounded by
$(K^{2}ed/d_{\mathsf{N}}(\mathcal{H}))^{d_{\mathsf{N}}(\mathcal{H})}$, by
[HL95]. It follows that
$2^{d}\leq(K^{2}ed/d_{\mathsf{N}}(\mathcal{H}))^{d_{\mathsf{N}}(\mathcal{H})}$,
i.e., $d\leq d_{\mathsf{N}}(\mathcal{H})\cdot
O(\log(Kd/d_{\mathsf{N}}(\mathcal{H})))$, which yields $d\leq
O(d_{\mathsf{N}}(\mathcal{H})\cdot\log(K))$. ∎

Algorithm 7 Multiclass learner

1:Concept class $\mathcal{H}\subset[K]^{\mathcal{X}}$, sample
$\\{(x_{i},y_{i})\\}_{i\in[n]}\subset(\mathcal{X}\times[K])^{n}$, domain point
$x\in\mathcal{X}$, weak learner $\mathscr{A}$ for
$\mathscr{M}_{2}(\mathcal{H})$ with margin $\eta$, failure probability
$\delta$, weak ERM oracle $\mathcal{O}^{\mathsf{erm,w}}$.

2:function MulticlassRealizable($S,x,\mathscr{A},\eta,\delta$)

3: Define a dataset
$\tilde{S}\subset(\mathcal{X}\times\mathcal{P}_{2}({K})\times\\{0,1,*\\})^{2n(K-1)}$
as follows:  $\displaystyle\tilde{S}=\left\\{(x_{i},(y_{i},\ell),0)\ :\
i\in[n],\ell\in[K]\backslash\\{y_{i}\\}\right\\}\cup\left\\{(x_{i},(\ell,y_{i}),1)\
:\ i\in[n],\ell\in[K]\backslash\\{y_{i}\\}\right\\}.$ (20)

4: Call Adaboost (Algorithm 5) on the dataset $\tilde{S}$ using the weak
learner $\mathscr{A}$ with $T=\lceil 16\log(4nK/\delta)/\eta^{2}\rceil$, and
denote the resulting hypothesis by
$J:\mathcal{X}\times\mathcal{P}_{2}({K})\to\\{0,1\\}$.

5: Define the hypothesis
$H:=\mathsf{Dec}^{\mathsf{mc}}(J)\in[K]^{\mathcal{X}}$ (see Definition F.2).

6: return $H(x)$.

7:function MulticlassAgnostic($S,\mathscr{A},\eta,\delta$)

8: Let $z\in\\{0,1\\}^{n}$ denote the output of
$\texttt{SampleERM.Binary}(S,\ell^{\mathsf{mc}},\mathcal{O}^{\mathsf{erm,w}})$.
$\triangleright$ _( Algorithm 2)_

9: Define $\tilde{S}:=\\{(x_{i},y_{i})\ :\ i\in[n],z_{i}=0\\}$.

10: Set $H:=\texttt{MulticlassRealizable}(\tilde{S},\mathscr{A},\eta,\delta)$.

11: return $H(x)$.

Note that, given a weak consistency oracle $\mathcal{O}^{\mathsf{con,w}}$ for
the class $\mathcal{H}\subset[K]^{\mathcal{X}}$, we immediately obtain a weak
consistency oracle $\mathcal{O}^{\mathsf{con,menu}}$ for the class
$\mathscr{M}_{2}(\mathcal{H})$: for a
$\mathscr{M}_{2}(\mathcal{H})$-realizable dataset
$S=\\{(x_{i},\mu_{i},y_{i})\\}_{i\in[n]}$, the oracle
$\mathcal{O}^{\mathsf{con,menu}}(S)$ defines
$y_{i}^{\prime}=(\mu_{i})_{y_{i}+1}$, and returns
$\mathcal{O}^{\mathsf{con,w}}(\\{(x_{i},y_{i}^{\prime})\\}_{i\in[n]})$. Using
this observation, we may obtain a weak learner for the class
$\mathscr{M}_{2}(\mathcal{H})$ as a corollary of Theorem 3.2:

######  Corollary F.2.

There are constants $C_{1},C_{2}$ so that the following holds. Consider a
multiclass concept class $\mathcal{H}\subset[K]^{\mathcal{X}}$ of Natarajan
dimension $d_{\mathsf{N}}$, and suppose $m\geq C_{1}d_{\mathsf{N}}\log
K\cdot\log(d_{\mathsf{N}}\log K)$. Let
$S=\\{((x_{i},\mu_{i}),y_{i})\\}\in(\mathcal{X}\times\mathcal{P}_{2}({K})\times\\{0,1\\})^{m}$
be $\mathscr{M}_{2}(\mathcal{H})$-realizable. and let
$\mathscr{A}(S_{-i},(x_{i},\mu_{i}))$ be the output of
$\texttt{WeakRealizable}(S_{-i},(x_{i},\mu_{i}),1-\frac{1}{C_{1}m\log
m},1,C_{1}m^{2}\log^{3}m,\mathcal{O}^{\mathsf{con,menu}})$ (Algorithm 1) for
each $i\in[m]$. Then

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}_{\mathscr{A}}\left[\ell^{\mathsf{bin}}(\mathscr{A}(S_{-i},(x_{i},\mu_{i})),y_{i})\right]\leq\frac{1}{2}-\frac{1}{C_{2}m\log
m},$

where the expectation is taken over the randomness in the runs of
WeakRealizable as well as the sampling of $\hat{y}$ from its output. Moreover,
WeakRealizable makes at most $\tilde{O}(m^{3})$ calls to
$\mathcal{O}^{\mathsf{con,menu}}$, each with a dataset of size $m-1$.

###### Proof.

The corollary follows immediately from Theorem 3.2 applied to the class
$\mathscr{M}_{2}(\mathcal{H})$, which has VC dimension bounded by
$O(d_{\mathsf{N}}\log K)$ by Lemma F.1, together with the fact observed above
that a weak consistency oracle for $\mathscr{M}_{2}(\mathcal{H})$ can be
implemented using a weak consistency oracle for $\mathcal{H}$. ∎

######  Lemma F.3 (Training error of Adaboost in multiclass setting).

Let $m,n\in\mathbb{N}$ and $\eta,\delta\in(0,1)$ be given, and suppose that
algorithm $\mathscr{A}$ is an $m$-sample weak learner with margin $\eta$ for
the class $\mathscr{M}_{2}(\mathcal{H})$. Let $x\in\mathcal{X}$ and
$\bar{S}\in(\mathcal{X}\times[K])^{n}$ be an $\mathcal{H}$-realizable sample.
Then the hypothesis $H$ defined in 5 of
$\texttt{MulticlassRealizable}(\bar{S},x,\mathscr{A},\eta,\delta)$ (Algorithm
7) satisfies $\widehat{\mathrm{er}}_{\bar{S}}(H)=0$ with probability
$1-\delta$.

Note that the domain point $x$ plays no role in Lemma F.3.

###### Proof of Lemma F.3.

By Lemma D.1 applied to the dataset $\tilde{S}$ (defined in Eq. 20) together
with the guarantee on the weak learner $\mathscr{A}$, the output hypothesis
$J:\mathcal{X}\times\mathcal{P}_{2}({K})\to\\{0,1\\}$ of Adaboost satisfies
the following with probability $1-\delta$:

$\displaystyle\forall i\in[n],\ \ell\in[K]\backslash\\{y_{i}\\},\quad
J(x,(y_{i},\ell))=0,\ J(x,(\ell,y_{i}))=1.$ (21)

For each $(x,y)\in\mathcal{X}\times[K]$, we have

$\displaystyle\ell^{\mathsf{mc}}(H(x),y)=\mathbbm{1}\\{{H(x)\neq
y}\\}\leq\sum_{\ell\in[K]\backslash\\{y\\}}\mathbbm{1}\\{{J(x,(y,\ell))=1}\\}+\mathbbm{1}\\{{J(x,(\ell,y))=0}\\},$

since if $H(x)\neq y$, then there must be some $\ell\neq y$ so that
$J(x,(y,\ell))=1$ or $J(x,(\ell,y))=0$. The guarantee Eq. 21 on $J$ yields
that we must have $H(x_{i})=y_{i}$ for all $i\in[n]$, with probability
$1-\delta$.

∎

###### Proof of Theorem 4.1.

Let $d_{\mathsf{N}}\in\mathbb{N}$ be given and consider a concept class
$\mathcal{H}\subset[K]^{\mathcal{X}}$ with $d_{\mathsf{N}}(\mathcal{H})\leq
d_{\mathsf{N}}$, together with a weak consistency oracle
$\mathcal{O}^{\mathsf{con,w}}$ and a weak ERM oracle
$\mathcal{O}^{\mathsf{erm,w}}$ for $\mathcal{H}$. Let $C_{1},C_{2}$ denote the
constants in the statement of Corollary F.2, and define
$m:=C_{1}d_{\mathsf{N}}\log K\cdot\log(d_{\mathsf{N}}\log K)$ and
$\eta:=\frac{1}{C_{2}m\log m}$. Write $T=\lceil
16\log(4nK/\delta)/\eta^{2}\rceil$ as in Algorithm 7. Let
$\mathscr{A}:(\mathcal{X}\times\mathcal{P}_{2}({K})\times\\{0,1\\})^{m}\times(\mathcal{X}\times\mathcal{P}_{2}({K}))\to\\{0,1\\}$
denote the learner of Corollary F.2 (in particular, $\mathscr{A}(S,(x,\mu))$
calls WeakRealizable with inputs $S,(x,\mu),\mathcal{O}^{\mathsf{con,w}}$, and
an appropriate choice of the parameters). Then by Corollary F.2 and Lemma C.4,
$\mathscr{A}$ is an $m$-sample weak learner for the partial concept class
$\mathscr{M}_{2}(\mathcal{H})$ with margin $\eta$.

#### Realizable case.

We begin by proving the first statement of the theorem. Given
$\epsilon,\delta\in(0,1)$ and an $\mathcal{H}$-realizable distribution
$P\in\Delta(\mathcal{X}\times[K])$, consider a sample $S\sim P^{n}$, where $n$
will be chosen below. We will show that the algorithm which, given $S$ and
some $x\in\mathcal{X}$ as input, returns the output $H(x)$ of
$\texttt{MulticlassRealizable}(S,x,\mathscr{A},\eta,\delta)$ satisfies the
requirements of the theorem. Let $H:\mathcal{X}\to[K]$ denote the hypothesis
constructed in 5 of MulticlassRealizable; we wish to show that with
probability $1-\delta$ over $S$ and the random bits of MulticlassRealizable,
$\mathrm{er}_{P}(H)\leq\epsilon$. To do so, we will define a distribution $Q$
over sample compression schemes $(\rho,\kappa)$ on $n$-sample datasets, so
that the distribution of $\rho(\kappa(S))$ is the same as the distribution of
$H$. The call to Adaboost (Algorithm 5) in 4 of Algorithm 7 generates a
sequence of i.i.d. datasets
$\tilde{S}_{1},\ldots,\tilde{S}_{T}\in(\mathcal{X}\times\mathcal{P}_{2}({K})\times\\{0,1\\})^{m}$,
each consisting of examples in $\tilde{S}$ (defined in Eq. 20), together with
a sequence of parameters $\alpha_{1},\ldots,\alpha_{T}\in\mathbb{R}$ and a
sequence of random bitstrings $R_{1},\ldots,R_{T}$ for use in the weak learner
$\mathscr{A}$ and in the sampling step on 5 of Algorithm 5. The values of
$\tilde{S}_{t},\alpha_{t},R_{t}$ satisfy the following: the output hypothesis
$J:\mathcal{X}\times\mathcal{P}_{2}({K})\to\\{0,1\\}$ of Adaboost is given by

$\displaystyle
J(x,\mu):=\frac{1}{2}+\frac{1}{2}\mathrm{sign}\left(\sum_{t=1}^{T}\alpha_{t}\cdot(2\mathscr{A}_{R_{t}}(\tilde{S}_{t},x,\mu)-1)\right).$
(22)

For $j\in[m]$, the $j$th example in $\tilde{S}_{t}$ may be written as
$(x_{i_{t,j}},(\ell_{t,j},k_{t,j}),b_{t,j})$, for some
$i_{t,j}\in[n],\ell_{t,j}\in[K],k_{t,j}\in[K],b_{t,j}\in\\{0,1\\}$. We then
define the (random) dataset
$S_{t}:=\\{(x_{i_{t,j}},y_{i_{t,j}})\\}_{j\in[m]}$.

Note that, for fixed $S\in(\mathcal{X}\times[K])^{n}$, the resulting random
variables $(\tilde{S}_{t},S_{t},\alpha_{t})_{t\in[T]}$ are a deterministic
function of $S$ and $(R_{t})_{t\in[T]}$. We now define $(\rho,\kappa)\sim Q$
to be distributed as follows:

  * •

$\kappa$ maps the dataset $S\in(\mathcal{X}\times[K])^{n}$ to
$\kappa(S)=(S_{1},\ldots,S_{T}),\left(\alpha_{t},(\ell_{t,j},k_{t,j},b_{t,j})_{j\in[m]}\right)_{t\in[T]}$,
where $S_{t},\alpha_{t},\ell_{t,j},k_{t,j},b_{t,j}$ are defined as a function
of $(R_{t})_{t\in[T]}$ and $S$ as described above.

  * •

$\rho$ proceeds as follows, given an input of the form
$(S_{1}^{\prime},\ldots,S_{T}^{\prime}),\left(\alpha_{t}^{\prime},(\ell_{t,j}^{\prime},k_{t,j}^{\prime},b_{t,j}^{\prime})_{j\in[m]}\right)_{t\in[T]}$
(where $S_{1}^{\prime},\ldots,S_{T}^{\prime}$ is a sequence of examples in
$\mathcal{X}\times[K]$ of length $Tm$ and the supplemental information
$\alpha_{t}^{\prime}\in\mathbb{R}$,
$\ell_{t,j}^{\prime},k_{t,j}^{\prime}\in[K],b_{t,j}^{\prime}\in\\{0,1\\}$ are
encoded in binary). Denoting
$S_{t}^{\prime}=\\{(x_{t,j}^{\prime},y_{t,j}^{\prime})\\}_{j\in[m]}$, let us
define
$\tilde{S}_{t}^{\prime}:=\\{(x_{t_{j}}^{\prime},(\ell_{t,j}^{\prime},k_{t,j}^{\prime}),b_{t,j}^{\prime})\\}_{j\in[m]}$;
then $\rho$ outputs the hypothesis
$x\mapsto\mathsf{Dec}^{\mathsf{mc}}(J^{\prime})$, where
$J^{\prime}(x,\mu):=\left(\frac{1}{2}+\frac{1}{2}\mathrm{sign}\left(\sum_{t=1}^{T}\alpha_{t}^{\prime}\cdot(2\mathscr{A}_{R_{t}}(\tilde{S}_{t}^{\prime},x,\mu)-1)\right)\right)$.

Since the values $\alpha_{t}$ defined in Adaboost can be encoded with $O(\log
n)$ bits (as $\epsilon_{t}\in\\{0,1/n,\ldots,1\\}$) and the list
$((\ell_{t,j},k_{t,j},b_{t,j}))_{j\in[m]}$ can be encoded with $O(m\log K)$
bits, with probability 1 over $(\kappa,\rho)\sim Q$, the size of $\kappa$ for
inputs samples $S$ of size $n$ is bounded by $|\kappa|\leq O(T\cdot(m\log
K+\log n))$. Next, Lemma F.3 together with the definition of $Q$ above (and in
particular the fact that $\rho$ uses the same bits $R_{t}$ as in the
definition of $\kappa$), gives that for any $\mathcal{H}$-realizable dataset
$S$, there is a subset $\mathcal{E}$ of compression schemes for which
$Q(\mathcal{E})\geq 1-\delta$ so that for all $(\kappa,\rho)\in\mathcal{E}$,
$\widehat{\mathrm{er}}_{S}(\rho(\kappa(S)))=0$. By Lemma 2.1 applied to the
multiclass loss function, there is a constant $C>0$ so that for each
$(\kappa,\rho)\in\operatorname{supp}(Q)$, with probability $1-\delta$ over the
draw of $S\sim P^{n}$,

$\displaystyle\mathrm{er}_{P}(\rho(\kappa(S)))\leq\mathbbm{1}\\{{\widehat{\mathrm{er}}_{S}(\rho(\kappa(S)))=0}\\}+C\cdot\frac{T\cdot(m\log
K+\log n)\cdot\log n+\log(1/\delta)}{n},$

for some sufficiently large constant $C$. By our choice of $T$ together with
the fact that $Q(\mathcal{E})\geq 1-\delta$, it follows that with probability
$1-2\delta$ over the draw of $S\sim P^{n}$ and the draw of $(\rho,\kappa)\sim
Q$, we have

$\displaystyle\mathrm{er}_{P}(\rho(\kappa(S)))\leq
C\cdot\frac{\log(n)\log(nK/\delta)\cdot\frac{1}{\eta^{2}}\cdot(m\log K+\log
n)}{n}.$

For fixed $S$, the distribution of $\rho(\kappa(S))$ is the same as the
distribution of the output hypothesis $H$ of MulticlassRealizable. Thus, by
our choices of $m,\eta$, after rescaling $\delta$, we can ensure that
$\mathrm{er}_{P}(H)\leq\epsilon$ with probability $1-\delta$ as long as we
take
$n=\frac{d_{\mathsf{N}}^{3}\log^{4}(K/\delta)}{\epsilon}\cdot\operatorname{poly}(\log
1/\epsilon,\log d_{\mathsf{N}},\log\log K)$.

Note that the dataset $\tilde{S}$ passed to Adaboost in MulticlassRealizable
is of size $|\tilde{S}|=O(nK)$. Since the number of rounds of Adaboost is
$T\leq\operatorname{poly}(n)$ and the weak learner $\mathscr{A}$ makes
$\operatorname{poly}(m)$ calls to $\mathcal{O}^{\mathsf{con,w}}$, which can
simulate $\mathcal{O}^{\mathsf{con,menu}}$ (Corollary F.2), the same argument
as in the proof of Theorem 3.1 shows that the cumulative query cost of