# Multiclass Learnability Beyond the PAC Framework:
Universal Rates and Partial Concept Classes

Alkis Kalavasis
NTUA
<EMAIL_ADDRESS>Equal contribution. Grigoris Velegkas*
Yale University
<EMAIL_ADDRESS>Amin Karbasi
Yale University
<EMAIL_ADDRESS>
###### Abstract

In this paper we study the problem of multiclass classification with a bounded
number of different labels $k$, in the realizable setting. We extend the
traditional PAC model to a) distribution-dependent learning rates, and b)
learning rates under data-dependent assumptions. First, we consider the
_universal learning_ setting (Bousquet, Hanneke, Moran, van Handel and
Yehudayoff, STOC ’21), for which we provide a complete characterization of the
achievable learning rates that holds for every fixed distribution. In
particular, we show the following trichotomy: for any concept class, the
optimal learning rate is either exponential, linear or arbitrarily slow.
Additionally, we provide complexity measures of the underlying hypothesis
class that characterize when these rates occur. Second, we consider the
problem of multiclass classification with _structured_ data (such as data
lying on a low dimensional manifold or satisfying margin conditions), a
setting which is captured by _partial concept classes_ (Alon, Hanneke, Holzman
and Moran, FOCS ’21). Partial concepts are functions that can be _undefined_
in certain parts of the input space. We extend the traditional PAC
learnability of total concept classes to partial concept classes in the
multiclass setting and investigate differences between partial and total
concepts.

##  1 Introduction

Classifying data into multiple different classes is a fundamental problem in
machine learning that has many real-life applications, such as image
recognition, web advertisement and text categorization. Due to its importance,
multiclass classification has been an attractive field of research both for
theorists [NT88, BCHL95, RBR09, Nat89, DSBDSS11, DSS14, SSBD14] and for
practitioners [SSKS04, Col04, Aly05]. Essentially, it boils down to learning a
classifier $h$ from a domain $\mathcal{X}$ to a label space $\mathcal{Y}$,
where $|\mathcal{Y}|\geq 2,$ and the error is measured by the probability that
$h(x)$ is incorrect. In this work, we focus on the setting where the number of
labels is finite and we identify $\mathcal{Y}$ with $[k]:=\\{0,1,...,k\\}$ for
some constant $k\in\mathbb{N}$.

##### Multiclass PAC Learning

The PAC model [Val84] constitutes the gold-standard learning framework. A
seminal result in learning theory [VC71, BEHW89] characterizes PAC
learnability of binary classes ($k=1$) through the Vapnik-Chervonenkis (VC)
dimension and provides a clear algorithmic landscape with the _empirical risk
minimization_ (ERM) principle yielding (almost) optimal statistical learning
algorithms. The picture established for the binary setting extends to the case
of multiple labels when the number of classes $|\mathcal{Y}|$ is bounded. The
works of [NT88, Nat89] and [BCHL95] identified natural extensions of the VC
dimension, such as the _Natarajan dimension_ , whose finiteness characterizes
multiclass learnability in this setting. Moreover, the ERM principle still
holds and achieves the desired learning rate by essentially reducing
learnability to optimization. The fundamental result of the multiclass PAC
learning (in the realizable setting for the expected prediction error) 111We
mention that Equation 1 essentially works in the probabilistic prediction
model of [HLW94]. In this model, one does not require the hypotheses used for
prediction to be represented in any specified way since the prediction for the
test point $x$ is performed on the fly. For instance, a valid classification
rule in this model is to memorize all the training points and run an algorithm
for every unlabeled instance $x.$ In Valiant’s PAC model, we are interested in
approximating a target hypothesis $h\in\mathcal{H}$ given an $h$-labeled
sample and we must output a representation of a hypothesis in some hypothesis
class $\mathcal{F}$ [HLW94]. Also, Equation 1 deals with the expected error.
can be summarized in the following elegant equation for any $n\in\mathbb{N}$,
which we explain right-after:

$\inf_{\widehat{h}_{n}}\sup_{P\in\mathrm{RE}(\mathcal{H})}\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]=\min\left(\widetilde{\Theta}_{k}\left(\frac{\mathrm{Ndim}(\mathcal{H})}{n}\right),1\right)\,,$
(1)

where $\mathrm{Ndim}(\mathcal{H})$ stands for the Natarajan dimension of
$\mathcal{H}$ and $\widetilde{\Theta}_{k}$ subsumes dependencies on $k$ (the
lower bound of order $\mathrm{Ndim}(\mathcal{H})/n$ is from [RBR09] and the
upper bound $\mathrm{Ndim}(\mathcal{H})\log(k)/n$ comes from an application of
the one-inclusion hypergraph algorithm [BCD+22]). In words, assume that $n$ is
the number of training samples and let $\mathcal{H}\subseteq[k]^{\mathcal{X}}$
be a set of multiclass classifiers mapping the elements of the domain
$\mathcal{X}$ to $[k]$ that the learner has access to. The learner observes
$n$ labeled examples $(x,y)\in\mathcal{X}\times[k]$ generated i.i.d. from some
unknown distribution $P$ with the constraint that $P$ is _realizable_ with
respect to $\mathcal{H}$, i.e., there is some $h\in\mathcal{H}$ that has
(almost surely) zero classification error. The learner then outputs a guess
hypothesis $\widehat{h}_{n}:\mathcal{X}\to[k]$ (potentially, without an
explicit description). The fundamental theorem of PAC learning, as shown
above, controls the expected error $\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]$, where
$\mathrm{er}(\widehat{h}_{n}):=\mathop{\bf Pr\/}_{(x,y)\sim
P}[\widehat{h}_{n}(x)\neq y]$, in a _minimax_ sense, i.e., it controls the
performance of the best algorithm $\widehat{h}_{n}$ (inf) against the worst-
case realizable distribution $P\in\mathrm{RE}(\mathcal{H})$ (sup) and states
that the following dichotomy occurs: if the Natarajan dimension
$\mathrm{Ndim}(\mathcal{H})$ is finite, the error rate decreases as, roughly,
$1/n$, so $\mathcal{H}$ is PAC learnable at a linear rate; otherwise, the
class $\mathcal{H}$ is not PAC learnable. Additionally, this theory provides a
clean algorithmic landscape: the ERM principle, which means outputting some
classifier in $\mathcal{H}$ that best fits the training set, (roughly)
achieves the rates of Equation 1.

##### Towards Novel Learning Theories

While the PAC model provides a solid and attractive theoretical framework, it
fails to (fundamentally) capture the real-world behavior of various applied ML
problems. In this work, we focus on the following two points of criticism for
the standard PAC model. The first natural point concerns the supremum over all
realizable distributions in Equation 1.

######  Observation 1.

The PAC model is distribution-independent and captures the worst-case learning
rate. Is it possible to design a learning theory that provides distribution-
dependent learning rates?

Another critique is that one cannot express natural data-dependent assumptions
through the PAC framework. For instance, high-dimensional data may lie in a
low-dimensional manifold. To be more specific, consider the task of
classifying images of vehicles. The representation of such images corresponds
to a low-dimensional subset of the space of all possible images, most of which
do not correspond to vehicles. A prominent way to capture such assumptions is
via _partial concepts_ [AHHM22]: these are functions which can be _undefined_
on a subset of $\mathcal{X}$, a departure from the traditional model.

######  Observation 2.

The PAC model only considers total concept classes, i.e.,
$\mathcal{H}\subseteq[k]^{\mathcal{X}},$ which cannot express data-dependent
constraints. Is it possible to design a learning theory for partial concepts
$h:\mathcal{X}\to\\{0,1,...,k,\star\\}$, where $h(x)=\star$ means that $h$ is
undefined at $x$?

The aim of this paper is to develop (i) a distribution-dependent learning
theory for multiclass classification and (ii) a learning theory for partial
multiclass concept classes in the distribution-independent setting222While we
believe that one could design a unified learning theory addressing the two
questions at once, we prefer to provide two separate theories, since they are
both interesting in their own.. We comment that we focus on the realizable
setting that already poses important challenges and requires novel ideas and
we believe that our results can be extended to the agnostic case, which is
left for future work. We remark that such theories for binary classification
were recently developed [BHM+21, AHHM22]. However, in various practical
applications, such explanations may not suffice, since it is rarely the case
that there are only two classes. As it is already evident from the PAC
setting, moving from binary classification to multiclass classification is not
trivial [DSBDSS11]. We now discuss 1 and 2; we underline that our goal is not
to replace, but to build upon and complement, the traditional PAC model, which
constitutes the bedrock of learning theory.

##### Distribution-Dependent Learning Rates

In many modern machine learning applications the generalization error
$\mathop{\bf E\/}[\mathrm{er}(\widehat{h}_{n})]$ drops _exponentially fast_ as
a function of the sample size $n$ [CT90, CT92, Sch97, VL21]. However, the
traditional PAC learning theory predicts merely $\widetilde{O}(d/n)$ rates in
the realizable setting, where $d$ is the complexity measure of the underlying
concept class that the algorithm is trying to learn. A possible explanation
for this discrepancy between the theoretical guarantees and the empirical
performance of the learning algorithms is the worst-case nature of the PAC
guarantees. Notice that in Equation 1, for any fixed learning algorithm, one
considers its performance against the worst distribution for it. In
particular, this means that as the sample size $n$ increases and new
classifiers $\widehat{h}_{n}$ are produced, the distribution that is used as a
benchmark can differ. However, in many practical applications, one considers
some _fixed_ distribution $P$ and measures the performance of the classifier
as $n\rightarrow\infty$ without changing $P$. Hence, there is an important
need to study mathematical models that capture this behavior of learning
algorithms and not just the minimax one. One such approach that was recently
proposed by [BHM+21] is to study _universal learning rates_ , which means that
the learning rates guarantees hold for every fixed (realizable) distribution
$P$, but there is not a _uniform_ bound over all of the distributions. To be
more precise, $\mathcal{H}$ is learnable at rate $R$ (where
$\lim_{n\to\infty}R(n)=0)$ in the universal setting if

$\exists\widehat{h}_{n}:\forall P\in\mathrm{RE}(\mathcal{H}),~{}\exists
C=C(P),c=c(P)>0\text{ so that }\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]\leq C\cdot R(c\cdot n),\forall
n\in\mathbb{N}.$ (2)

Note that the above equation is the same as in the PAC model with the
exception of a change between the existential quantifiers: in PAC, the focus
is on the case where $\exists C,c>0:\forall P\in\mathrm{RE}(\mathcal{H})$ the
guarantee holds (which expresses _uniformity_), while in the universal setting
distribution-dependent constants are allowed. This subtle change in the
definition can make the error-rate landscape vastly different. As an example,
consider the case where for $\widehat{h}_{n}$, we have that
$\mathrm{er}(\widehat{h}_{n})\leq C(P)e^{-c(P)n}$, for every distribution $P$,
where $C(P),c(P)$ are some distribution-dependent constants. When we take the
pointwise supremum over all of these infinitely many distributions, it can be
the case that the resulting function drops as $C^{\prime}/n$, where
$C^{\prime}$ is a distribution-independent constant [BHM+21].

##### Partial Concept Classes

The motivation behind 2 is that, in various practical learning tasks, the data
satisfy some special properties that make the learning process simpler. For
instance, it is a common principle to use classification with margin where the
points in the dataset have a safe gap from the decision boundary. Such
properties induce _data-dependent_ assumptions that the traditional PAC
learning theory framework provably fails to express. In fact, existing data-
dependent analyses diverge from the standard PAC model [STBWA98, HW01] and
provide problem-specific approaches. Thus, there is a need for a formal
framework that allows us to express such data-dependent restrictions and study
these problems in a _unified and principled way_. Recently, [AHHM22] proposed
an elegant extension of the binary PAC model to handle such tasks via the
framework of _partial concept classes_. As an intuitive example, a halfspace
with margin is a partial function that is undefined inside the forbidden
margin and is a well-defined halfspace outside the margin boundaries.

###  1.1 The Traditional Multiclass Learning Problem

Let $[k]=\\{0,1,...,k\\}$ for some fixed positive integer $k\in\mathbb{N}$. We
consider a domain $\mathcal{X}$ and a concept class
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$. A classifier is a universally
measurable333We discuss measurability formally in Section B.5 function
$h:\mathcal{X}\to[k]$. The error rate of a classifier $h$ with respect to a
probability distribution $P$ on $\mathcal{X}\times[k]$ is equal to
$\mathrm{er}(h)=\mathrm{er}_{P}(h)=\mathop{\bf Pr\/}_{(x,y)\sim P}[h(x)\neq
y]$. We focus on the setting where $P$ is realizable, i.e.,
$\inf_{h\in\mathcal{H}}\mathrm{er}_{P}(h)=0$. Formally, a (deterministic444We
focus for simplicity on deterministic learners. Our results extend to
randomized algorithms.) learning algorithm is a sequence of universally
measurable functions
$H_{n}:(\mathcal{X}\times[k])^{n}\times\mathcal{X}\to[k]$, which take as input
a sequence of $n$ independent pairs $(x_{i},y_{i})\sim P$ (training set) and
output data-dependent classifiers $\widehat{h}_{n}:\mathcal{X}\rightarrow[k]$,
where $\widehat{h}_{n}(x)=H_{n}((x_{1},y_{1}),\ldots,(x_{n},y_{n}),x)$. The
goal is to come up with algorithms whose $\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]$ admits a fast decay as a function of $n$,
where the expectation is over the training set.

###  1.2 Universal Multiclass Learning: Our Results

The aim of our first theory is to fully characterize the admissible universal
rates of learning, i.e., $\mathop{\bf E\/}[\mathrm{er}(\widehat{h}_{n})],$ in
the multiclass classification setting with a bounded number of labels. The
following definition formalizes this notion of achievable rate in the
(realizable) universal learning model [BHM+21].

######  Definition 1 ([BHM+21], Definition 1.4).

Let $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ and let $R:\mathbb{N}\to[0,1],$
with $R(n)\to 0$, be a rate function. We say that $\mathcal{H}$ is learnable
at rate $R$ if there exists a learning algorithm $\widehat{h}_{n}$ such that
for every realizable distribution $P$ on $\mathcal{X}\times[k]$ with respect
to $\mathcal{H}$, there exist distribution-dependent $C,c>0$ for which
$\mathop{\bf E\/}[\mathrm{er}(\widehat{h}_{n})]\leq CR(cn),$ for all
$n\in\mathbb{N}$. Also, $\mathcal{H}$ is not learnable at rate faster than $R$
if for any learning algorithm $\widehat{h}_{n}$, there exists a realizable
distribution $P$ on $\mathcal{X}\times[k]$ with respect to $\mathcal{H}$ and
distribution-dependent $C,c>0$ for which $\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]\geq CR(cn)$ for infinitely many
$n\in\mathbb{N}$. $\mathcal{H}$ is learnable with optimal rate $R$ if it is
learnable at rate $R$ and is not learnable faster than $R$. Finally,
$\mathcal{H}$ requires arbitrarily slow rates if, for every $R(n)\to 0$,
$\mathcal{H}$ is not learnable at rate faster than $R$.

In the universal multiclass setting, we show that the following fundamental
trichotomy occurs (in comparison with the dichotomy witnessed in the uniform
PAC model). This result is a theoretical justification of the exponential
error rates observed in practice.

######  Theorem 1.

Fix a constant $k\in\mathbb{N}$. Consider a hypothesis class
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$ with $|\mathcal{H}|>k+2$. Then,
exactly one of the following holds for the learning rate of $\mathcal{H}$ in
the realizable case:

  * •

$\mathcal{H}$ is learnable at an optimal rate $e^{-n}$.

  * •

$\mathcal{H}$ is learnable at an optimal rate $1/n$.

  * •

$\mathcal{H}$ requires arbitrarily slow rates.

We mention that $|\mathcal{H}|>k+2$ comes without loss of generality.555The
constraint $|\mathcal{H}|>k+2$ rules out some degenerate scenarios, we kindly
refer to Appendix A. In contrast to the standard PAC model, any concept class
is learnable in the universal rates setting [HKSW20]. Intuitively, the
analogue of non-learnability in the uniform setting is the case of arbitrarily
slow rates. Our second result is the specification of some combinatorial
complexity measures of $\mathcal{H}$ that characterize the optimal learning
rate of this class. Let us first provide some informal definitions of these
measures. We begin with the notion of _multiclass Littlestone trees_ , which
extends the binary Littlestone trees from [BHM+21].

######  Definition 2 (Informal (see Definition 5)).

A multiclass Littlestone tree for $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ is a
complete binary tree of depth $d\leq\infty$ whose internal nodes are labeled
by $\mathcal{X}$, and whose two edges connecting a node to its children are
labeled by two different elements in $[k]$, such that every path of length at
most $d$ emanating from the root is consistent with a concept
$h\in\mathcal{H}$. We say that $\mathcal{H}$ has an infinite multiclass
Littlestone tree if there is a multiclass Littlestone tree for $\mathcal{H}$
of depth $d=\infty$.

For some intuition we refer the reader to Figure 1. The above complexity
measure appears in the definition of the multiclass Littlestone dimension
[DSBDSS11]. In fact, a class $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ has
multiclass Littlestone dimension $d$ if it has a multiclass Littlestone tree
of depth $d$ but not of depth $d+1$. We underline that having an infinite
multiclass Littlestone tree is _not_ the same as having an unbounded
multiclass Littlestone dimension. A class $\mathcal{H}$ has unbounded
Littlestone dimension if for every $d\in\mathbb{N}$ there is _some_ tree of
depth $d$. However, this does not mean that there is a _single_ infinite tree.
This is a fundamental conceptual gap between the uniform and the universal
settings.

$\scriptstyle\ell^{(0)}_{\emptyset}$$\scriptstyle\ell^{(1)}_{\emptyset}$$\scriptstyle\ell_{0}^{(0)}$$\scriptstyle\ell_{0}^{(1)}$$\scriptstyle\ell_{1}^{(0)}$$\scriptstyle\ell_{1}^{(1)}$$\scriptstyle\ell_{10}^{(1)}$$\scriptstyle\ell_{10}^{(0)}$$\bm{x_{\varnothing}}$$x_{0}$$\bm{x_{1}}$$x_{00}$$x_{01}$$\bm{x_{10}}$$x_{11}$$\exists\,h\in\mathcal{H}:$$h(x_{\varnothing})=\ell_{\emptyset}^{(1)}$$h(x_{1})=\ell_{1}^{(0)}$$h(x_{10})=\ell_{10}^{(1)}$
Figure 1: A multiclass Littlestone tree of depth $3$. Each node $x_{u}$ has
two children $\ell_{u}^{(0)}\neq\ell_{u}^{(1)}$ where $\ell_{u}^{(i)}\in[k]$
for any $i\in\\{0,1\\}$ and $u\in\\{0,1\\}^{*},$ i.e., the set of binary
strings of arbitrary length. Every branch is consistent with some concept
$h\in\mathcal{H}$. The figure is adapted from [BHM+21].

The next definition is novel and is motivated by the fundamental notion of the
Natarajan dimension from the multiclass PAC setting (see Definition 12). We
first need some terminology: a tuple
$(x_{1},...,x_{t},s^{(0)}_{1},...,s^{(0)}_{t},s^{(1)}_{1},...,s^{(1)}_{t})\in\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}$
with $s_{i}^{(0)}\neq s_{i}^{(1)}$, for any $i\in[t],$ is $N$-consistent with
the edge $(y_{1},...,y_{t})\in\\{0,1\\}^{t}$ and the concept $h\in\mathcal{H}$
if $h(x_{i})=s^{(y_{i})}_{i}$ for any $i\in[t]$. Recall that if the tuple is
$N$-consistent with any binary pattern $y\in\\{0,1\\}^{t}$, we say that
$(x_{1},...,x_{t})$ is $N$-shattered. More generally, a path is $N$-consistent
with a concept $h\in\mathcal{H}$ if each node of the path is $N$-consistent
with the edge connecting the node with its child across the path and $h$.
Since the next definition might be hard to parse, we refer the reader to
Figure 2 for some intuition.

######  Definition 3 (Informal (see Definition 6)).

A Natarajan-Littlestone (NL) tree for $\mathcal{H}\subseteq[k]^{\mathcal{X}}$
is a complete tree of depth $d\leq\infty$ so that every level $1\leq t\leq d$
has branching factor $2^{t}$ and nodes that are labeled by
$\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}$ (so that for all $i\in[t]$ the two
labels in $[k]\times[k]$ are different) and whose $2^{t}$ edges connecting a
node to its children are labeled by the elements of $\\{0,1\\}^{t}$. It must
hold that every path of length at most $d$ emanating from the root is
$N$-consistent with a concept $h\in\mathcal{H}$. We say that $\mathcal{H}$ has
an infinite Natarajan-Littlestone tree if there is an NL tree for
$\mathcal{H}$ of depth $d=\infty$.

$(\bm{x_{\varnothing}},\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s_{\varnothing}^{(0)}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},\bm{s_{\varnothing}^{(1)}})$$(x_{0}^{0},s_{0}^{0(0)},s_{0}^{0(1)},x_{0}^{1},s_{0}^{1(0)},s_{0}^{1(1)})$$\bm{(x_{1}^{0},s_{1}^{0(0)},}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s_{1}^{0(1)}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},\bm{x_{1}^{1},s_{1}^{1(0)},}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s_{1}^{1(1)}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0})$$\scriptstyle
0$$\scriptstyle\bm{1}$$\scriptstyle 11$$\scriptstyle 10$$\scriptstyle
01$$\scriptstyle\bm{00}$$(x_{1,01}^{0},s_{1,01}^{0(0)},s_{1,01}^{0(1)},x_{1,01}^{1},s_{1,01}^{1(0)},s_{1,01}^{1(1)},x_{1,01}^{2},s_{1,01}^{2(0)},s_{1,01}^{2(1)})$$(x_{1,10}^{0},s_{1,10}^{0(0)},s_{1,10}^{0(1)},x_{1,10}^{1},s_{1,10}^{1(0)},s_{1,10}^{1(1)},x_{1,10}^{2},s_{1,10}^{2(0)},s_{1,10}^{2(1)})$$(x_{1,11}^{0},s_{1,11}^{0(0)},s_{1,11}^{0(1)},x_{1,11}^{1},s_{1,11}^{1(0)},s_{1,11}^{1(1)},x_{1,11}^{2},s_{1,11}^{2(0)},s_{1,11}^{2(1)})$$\bm{(x_{1,00}^{0},}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s_{1,00}^{0(0)}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},\bm{s_{1,00}^{0(1)},x_{1,00}^{1},s_{1,00}^{1(0)}},\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s_{1,00}^{1(1)}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},\bm{x_{1,00}^{2},s_{1,00}^{2(0)},}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s_{1,00}^{2(1)}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0})$$(x_{0,00}^{0},s_{0,00}^{0(0)},s_{0,00}^{0(1)},x_{0,00}^{1},s_{0,00}^{1(0)},s_{0,00}^{1(1)},x_{0,00}^{2},s_{0,00}^{2(0)},s_{0,00}^{2(1)})$$\scriptstyle
00$$\scriptstyle 01$$\scriptstyle 10$$\scriptstyle 11$$\scriptstyle
000$$\scriptstyle 001$$\scriptstyle 010$$\scriptstyle
011$$\scriptstyle\bm{100}$$\scriptstyle 101$$\scriptstyle 110$$\scriptstyle
111$$\exists\,h\in\mathcal{H}:$$h(x_{\varnothing})=s_{\emptyset}^{(1)}$$h(x_{1}^{0})=s_{1}^{0(0)},~{}h(x_{1}^{1})=s_{1}^{1(0)}$$h(x_{1,00}^{0})=s_{1,00}^{0(1)},~{}h(x_{1,00}^{1})=s_{1,00}^{1(0)},~{}h(x_{1,00}^{2})=s_{1,00}^{2(0)}$
Figure 2: A Natarajan-Littlestone tree of depth $3$. Every branch is
consistent with a concept $h\in\mathcal{H}$. This is illustrated here for one
of the branches. Due to lack of space, not all nodes and external edges are
drawn. The figure is adapted from [BHM+21]. The root of the tree is the point
$(x_{\emptyset})$ with two colors $s^{(0)}_{\emptyset}\neq
s^{(1)}_{\emptyset}$. In this example, the branch picks the string
${}^{\prime}1^{\prime}$ and hence the node of the second level contains the
two points $(x_{1}^{0},x_{1}^{1})$ and the associated colors. We proceed in a
similar manner.

An NL tree looks like a multiclass Littlestone tree whose branching factor
increases exponentially with the depth of the tree and where each node at
depth $t$ in the NL tree contains $t$ points $x_{1},...,x_{t}$ of
$\mathcal{X}$ and two colorings $s^{(0)},s^{(1)}$ so that $s^{(0)}(x_{i})\neq
s^{(1)}(x_{i})$ for all $i\in[t]$. Crucially, this structure encapsulates the
notion of $N$-shattering in the combinatorial structure of a Littlestone tree.
Intuitively, along each path in the NL tree, we encounter $N$-shattered sets
of size increasing with the depth. Using these two definitions, we can state
our second result which is a complete characterization of the optimal rates
achievable for any given concept class
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$.

######  Theorem 2.

Fix a constant positive integer $k$. Consider a hypothesis class
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$ with $|\mathcal{H}|>k+2$. Then, one of
the following holds for any $n\in\mathbb{N}$ in the realizable case:

  * •

If $\mathcal{H}$ does not have an infinite multiclass Littlestone tree, then
it is learnable at an optimal rate $e^{-n}$.

  * •

If $\mathcal{H}$ has an infinite multiclass Littlestone tree but does not have
an infinite Natarajan-Littlestone tree, then it is learnable at an optimal
rate $1/n$.

  * •

If $\mathcal{H}$ has an infinite Natarajan-Littlestone tree, then it requires
arbitrarily slow rates.

It is clear that the above result implies Theorem 1. We remark that not only
the achievable rates are different compared to the uniform setting, but also
the algorithms we use to get these rates differ vastly from ERM. We sketch the
main techniques in Section 2.1. For the formal proof, see Section 3. We
briefly summarize our main technical contributions in this setting: using the
pre-described complexity measures of $\mathcal{H}$, we introduce novel Gale-
Stewart games (see Section 1.4 for a definition) which lead to new learning
algorithms that achieve the optimal learning rates. Also, we extend the lower
bounds from [BHM+21] that hold for binary classification to the multiclass
setting using our combinatorial measures. Our constructions raise interesting
questions about how the equivalence between various combinatorial dimensions,
like the Graph dimension and the Natarajan dimension, which is established in
the PAC setting translates to the universal setting. For further details, we
refer to Section 2 and Section 3.5.

###  1.3 Partial Multiclass Learning: Our Results

As we mentioned earlier, traditional PAC learning cannot capture data-
dependent assumptions. Inspired by [AHHM22], we slightly modify the basic
multiclass learning problem in a quite simple manner: instead of dealing with
concept classes $\mathcal{H}\subseteq\\{0,1,...,k\\}^{\mathcal{X}}$ where each
concept $h\in\mathcal{H}$ is a total function
$h:\mathcal{X}\to\\{0,1,...,k\\}$, we study partial concept classes
$\mathcal{H}\subseteq\\{0,1,...,k,\star\\}^{\mathcal{X}}$, where each concept
$h$ is now a partial function and $h(x)=\star$ means that the function $h$ is
undefined at $x$. We define the support of $h$ as the set
$\mathrm{supp}(h)=\\{x\in\mathcal{X}:h(x)\neq\star\\}.$

To illustrate the power of partial classes, we comment that the fundamental
class of $d$-dimensional halfspaces with margin $\gamma>0$ and $k$ labels can
be cast as a partial class
$\mathcal{H}_{\gamma}=\\{h_{W}:W\in\mathbb{R}^{k\times d}\\}$, where
$h_{W}(x)=i\in[k]$ if $(W_{i}-W_{j})\cdot x\geq\gamma$ for all $j\neq i$ and
$h_{W}(x)=\star$ otherwise [AHHM22]. As another example, we can express the
constraint that the data have to be in a low-dimensional space by considering
the partial concept class
$\mathcal{H}=\left\\{h:\mathbb{R}^{d}\rightarrow\\{0,1,...,k,\star\\}:\mathrm{dim}\left(\mathrm{supp}(h)\right)\ll
d\right\\}$, where $\mathrm{dim}(S)$ captures the dimension of the set of
points in $S$.

We characterize multiclass PAC learnability of partial concepts in the
realizable setting. A distribution $P$ on $\mathcal{X}\times\\{0,1,...,k\\}$
is realizable by $\mathcal{H}$ if, almost surely, for any $n$, a training set
$(x_{i},y_{i})_{i\in[n]}\sim P^{n}$ is realizable by some partial concept
$h\in\mathcal{H}$, i.e., $\\{x_{i}\\}_{i\in[n]}\subseteq\mathrm{supp}(h)$ and
$h(x_{i})=y_{i}$ for all $i\leq n$. For a partial concept $h$ and a
distribution $P$ on $\mathcal{X}\times\\{0,1,...,k\\}$, we let
$\mathrm{er}_{P}(h)=\mathop{\bf Pr\/}_{(x,y)\sim P}[h(x)\neq y]$, i.e.,
whenever $h$ outputs $\star$ it is counted as a mistake. We mention that the
standard combinatorial measures such as the VC or the Natarajan dimension
_naturally extend to the partial setting_ ; e.g., a partial class
$\mathcal{H}$ VC shatters a set of points if any _binary_ pattern is realized
by $\mathcal{H}$ (we forget about $\star$).

######  Definition 4 (Multiclass Partial PAC Learnability [AHHM22]).

A partial concept class
$\mathcal{H}\subseteq\\{0,1,...,k,\star\\}^{\mathcal{X}}$ is PAC learnable if
for every $\epsilon,\delta\in(0,1)$, there exists a finite
$\mathcal{M}(\epsilon,\delta)\in\mathbb{N}$ and a learning algorithm
$\mathbb{A}$ such that, for every distribution $P$ on
$\mathcal{X}\times\\{0,1,...,k\\}$ realizable with respect to $\mathcal{H}$,
for $S\sim P^{\mathcal{M}(\epsilon,\delta)}$, it holds that $\mathop{\bf
Pr\/}_{S}\left[\mathrm{er}_{P}(\mathbb{A}(S))\leq\epsilon\right]\geq
1-\delta\,.$ The sample complexity of $\mathbb{A}$ is the value
$\mathcal{M}(\epsilon,\delta)$ and the optimal sample complexity is the
minimum possible value of $\mathcal{M}(\epsilon,\delta)$ for any given
$\epsilon,\delta$.

We provide a combinatorial characterization of multiclass PAC learnability in
the partial setting with a bounded number of labels. We additionally give
bounds for $\mathcal{M}(\epsilon,\delta)$ in our more general Theorem 6. We
mention that this result is essentially implied by combining the results of
[BCD+22, AHHM22] and we state (and prove) it for completeness.

######  Theorem 3.

Fix a positive constant $k\in\mathbb{N}$. For any partial concept class
$\mathcal{H}\subseteq\\{0,1,\ldots,k,\star\\}^{\mathcal{X}}$, it holds that
$\mathcal{H}$ is PAC learnable if and only if
$\mathrm{Ndim}(\mathcal{H})<\infty$.

Here, $\mathrm{Ndim}(\mathcal{H})$ is the Natarajan dimension of $\mathcal{H}$
(see Definition 12 and Remark 2). At first sight this result may not seem
surprising. However, its proof is different from the standard multiclass PAC
learning (for constant $k$), which goes through uniform convergence and ERM.
In fact, such tools provably fail [AHHM22]. For a sketch, see below Theorem 6.
We complement the above structural result with some additional insight which
sheds light towards the, perhaps unanticipated, complexity of partial concept
classes. To this end, we discuss the question of _disambiguation_ [AKM19,
AHHM22]: Can a partial Natarajan class (i.e., with finite $\mathrm{Ndim}$) be
represented by total Natarajan classes? To address this task, the notion of
disambiguation is required: roughly, a total class $\overline{\mathcal{H}}$
disambiguates the partial class $\mathcal{H}$ if every partial concept
$h\in\mathcal{H}$ can be extended to some total concept
$\overline{h}\in\overline{\mathcal{H}}$, i.e., $\overline{h}$ agrees with $h$
in the support of $h$ and assigns to the undefined points some labels. For a
formal definition of disambiguation, see Definition 9. For the case $k=1$,
[AHHM22] provided an easy-to-learn partial class that cannot be represented by
any total class of bounded VC dimension using, surprisingly, some recent
results from communication complexity and graph theory (see e.g., [BBDG+22]).
We extend this result to the multiclass setting using Sauer’s lemma, which
provides a bound on the growth function [SSBD14], and tools from the binary
impossibility result.

######  Theorem 4 (Informal, see Theorem 15).

Fix $k\in\mathbb{N}$. For any $n\in\mathbb{N}$, there exists a class
$\mathcal{H}\subseteq\\{0,1,...,k,\star\\}^{\mathbb{N}}$ with
$\mathrm{Ndim}(\mathcal{H})=O_{k}(1)$ such that any disambiguation
$\overline{\mathcal{H}}$ of $\mathcal{H}$ has
$\mathrm{Ndim}(\overline{\mathcal{H}})=\infty$.

We denote with $O_{k}(1)$ a constant that depends on $k.$ Via Theorem 3, the
above partial class $\mathcal{H}$ is PAC learnable; however, _any_
disambiguation of $\mathcal{H}$ causes a blow-up to the Natarajan dimension.
This result showcases the complexity of partial concepts. We briefly outline
the main technical contributions in this regime: we extend the main results of
[AHHM22] for binary classification to the multiclass setting using appropriate
complexity measures. Recall that the combinatorial Sauer-Shelah-Perles (SSP)
lemma [Sau72, SSBD14] bounds the size of a (total) class
$\mathcal{H}\subseteq\\{0,1\\}^{n}$ by
$\sum_{i=0}^{\mathrm{VC}(\mathcal{H})}\binom{n}{i}$. Notably, [AHHM22] showed
that this lemma does _not_ hold true for partial concept classes. To obtain
our disambiguation result, we prove that the second variant of the SSP lemma,
which uses the growth function of the class [SSBD14], _does_ hold in the
partial regime, which may be of independent interest.

###  1.4 Preliminaries and Related Work

####  1.4.1 Preliminaries

In this section, we discuss some preliminaries for this paper. We refer to
Appendix B for further details.

##### Gale-Stewart Games & Ordinals

An important tool we leverage to establish our results in the universal
learning setting is the theory of _Gale-Stewart_ (GS) _games_ [GS53]. Every
such game consists of two players, a learner $\texttt{P}_{L}$ and an adversary
$\texttt{P}_{A}$, and is played over an infinite sequence of discrete steps.
In each step, the adversary presents some point $x_{t}\in\mathcal{X}_{t}$ to
the learner and the learner picks a response $y_{t}\in\mathcal{Y}_{t}$. If
some predefined condition gets violated at some step $t$, the game terminates
and the learner wins. On the other hand, if the condition does not get
violated during the infinite sequence of these time-steps, the adversary wins.
The main property which characterizes the GS game is that the winning strategy
of the learner is _finitely-decidable_ , i.e., she knows that she has won the
game after playing a finite number of rounds. [GS53, Kec12, HW+93] proved that
either $\texttt{P}_{L}$ or $\texttt{P}_{A}$ has a winning strategy, i.e.,
playing that strategy makes them win regardless of the opponents actions.
Similar to [BHM+21], the main reason we use GS games in this work is to obtain
functions that are _eventually_ correct. We deal with GS games that are finite
but there is not a bound on the number of steps they need to terminate. It
turns out that an _ordinal_ is the right notion to use for measuring the
remaining steps needed for the game to terminate. The key motivation behind
the use of ordinal numbers is to capture the intermediate state between an
infinite tree and a uniformly bounded tree.

####  1.4.2 Related Work

Classification with multiple labels is extensively studied and, for the
setting with bounded $k$, PAC learnability is well-understood [Nat89, BCHL95,
SSBD14, DSBDSS11]. The works of [VC71, BEHW89] provide a fundamental
dichotomy/equivalence between the finiteness of the VC dimension and binary
classification (PAC learnability). [NT88] and [Nat89] extend the PAC framework
to the multiclass setting by providing the notions of the Graph and the
Natarajan dimension. When the number of labels $k$ is a finite constant, then
these two dimensions both characterize PAC learnability since
$\mathrm{Ndim}(\mathcal{H})\leq\mathrm{Gdim}(\mathcal{H})\leq\mathrm{Ndim}(\mathcal{H})\cdot
O(\log(k))$ [DSBDSS11]. Afterwards, [BCHL95] and [HL95] provide a
combinatorial abstraction which captures as special cases e.g., the Graph and
Natarajan dimensions and Pollard’s pseudo-dimension. In this general setting,
[BCHL95] identify the notion of _$\Psi$ -distinguishers_ that characterize PAC
learnability when $k$ is bounded. More to that, uniform convergence still
applies when the number of classes is bounded and, so, PAC learning provides
the ERM principle for algorithm design. We remark the situation gets much more
complicated when the number of labels is not bounded [DSS14, BCD+22, RBR09,
DSBDSS11]. For instance, [DSS14] show that the ERM principle does not apply in
this case. In a recent breakthrough, [BCD+22] show that the DS dimension
captures learnability and the Natarajan dimension provably fails to achieve
this.

Our work provides two theoretical perspectives complementing and extending the
standard multiclass PAC learning. For the universal rates, the seminal work of
[BHM+21] provided a similar trichotomy for the binary setting (we obtain their
results by setting $k=1$). The gap between exponential and linear rates was
studied by [Sch97] in some special cases. Also, [AL98] showed that there exist
concept classes for which no improvement on the PAC learning rate is possible
in the universal setting. A natural approach to obtain results for the
multiclass setting is via reductions to the binary setting. In the exponential
rates setting, a first idea would be to consider for the class
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$ the binary restrictions
$\mathcal{H}|_{i}=\\{h_{i}:h\in\mathcal{H}\\},$ where $h_{i}$ denotes the
$i$-th bit of the output of $h$. In order to obtain the desired result for
exponential rates, one has to prove that if $\mathcal{H}$ does not have an
infinite multiclass Littlestone tree, then every $\mathcal{H}|_{i}$ does not
have an infinite binary Littlestone tree. However, it is not clear how to
obtain such a result. This is why we design statistical learning algorithms
for the multiclass setting from scratch, following the conceptual roadmap
introduced in [BHM+21]. We note that the existence of multiple labels requires
various novel ideas compared to the binary setting. We introduce novel Gale-
Stewart games (see Algorithm 1, Algorithm 2) in order to provide winning
strategies for the learning player both in the exponential and the linear
rates settings. Finally, in terms of reductions for the linear rates setting,
we provide a sufficient condition for learnability at a linear rate using a
reduction to the binary setting; however, it is again not clear how to use
these complexity measures in order to obtain lower bounds (see 1). In general,
the idea of “universal learning” has been studied in various concepts such as
universal consistency [Sto77, DGL13, Han20, HKSW20, BC21, Han22, Bla22, BJ22,
BCH22] and active learning [Han09, BHV10, Han11, HY15]. For an extended
discussion, we refer to [BHM+21]. For the partial concepts setting, our work
builds on the seminal work [AHHM22] and uses tools from [BCD+22]. The work of
[AHHM22] shows that the algorithmic landscape behind partial concept classes
is quite elusive. We extend some of their results to learning scenarios where
one deals with more than two labels. Our contributions draw ideas from various
directions, namely the one-inclusion hypergraph algorithm [HLW94, RBR09,
DSS14, BCD+22] which we define formally in Section B.2, the Sauer-Shelah-
Perles lemma [Sau72] and recent breakthroughs in the intersection of graph
theory and complexity theory concerning the Alon-Saks-Seymour problem [HS12,
Ama14, Göö15, SA15, BDHT17, GPW18, AHHM22, BBDG+22].

######  Remark 1 (Connection between Universal Rates and Partial Concept
Classes).

There is an interesting and intrinsic connection between universal rates and
partial concepts: in the universal learning setting, the first step of the
approach is to use the data to simulate some Gale-Stewart games and show that,
with high probability, most of them will have “converged”, i.e., the function
that corresponds to the learning strategy of the learner will be correct. In
turn, this defines some data-dependent constraints. For instance, assume that
$g$ is a successful NL pattern avoidance function, i.e., a function which
takes as input any $\ell$ points $x_{1},\ldots,x_{\ell}$ and any two
(everywhere different) mappings $s^{(0)},s^{(1)}$ from points to labels and
returns an invalid pattern, i.e., a binary pattern $y$ of length $\ell$ that
is not compatible with the definition of the Natarajan dimension (i.e., there
is no function $h\in\mathcal{H}$ such that if $y_{i}=1$ then
$h(x_{i})=s^{(1)}(x_{i})$ and if $y_{i}=0$ then $h(x_{i})=s^{(0)}(x_{i})$, for
all $i\in[\ell]$). Then, we can define a partial concept class
$\mathcal{H}^{\prime}$, the set of all functions from $X$ to
$\\{1,\ldots,k,\star\\}$ that satisfy the constraint of this pattern avoidance
function, and it has two important properties: its Natarajan dimension is
bounded by $\ell$ and a learning algorithm for $\mathcal{H}^{\prime}$ also
learns $\mathcal{H}$. Hence, understanding the learnability of partial concept
classes is an essential step in coming up with more natural learning
strategies in the universal learning setting.

Moreover, a unifying message of both of these settings is that going beyond
the traditional PAC learning framework is essential to understanding the
behavior of learning algorithms in practice. Importantly, in both of these
settings ERM is not an optimal learning algorithm and the one-inclusion graph
predictor is an essential part in deriving results in both theories.

###  1.5 Summary of Technical Contributions

Let us start with the technical challenges concerning the universal multiclass
classification setting: the first natural idea is to reduce the problem to the
binary setting, i.e., use the algorithms from [BHM+21] as a black-box to
derive algorithms for the multiclass case. However, this approach introduces
various technical challenges when dealing with the induced binary hypothesis
classes. We discuss in detail these challenges for the exponential rates case.

First, it was not clear to us how to prove that if the original class
$\mathcal{H}$ does not have an infinite multiclass Littlestone tree, then each
of the induced binary classes satisfies this property as well. As a result, we
developed new algorithms from scratch. There were several technical challenges
that we had to overcome. The straightforward extension of the Gale-Stewart
games that appear in [BHM+21], i.e., where the adversary presents a point $x$
and the learner picks a label in $[k]$ (imitating the online learning game),
does not seem to work. Therefore, we propose a more involved Gale-Stewart game
where the learner proposes both a point $x$ and two potential labels for it,
and the learner has to commit to one of the two. This game allows us to obtain
tight upper and lower bounds that depend on the finiteness of the multiclass
Littlestone tree. Note that the function that is obtained from the winning
strategy of the leaner in this game cannot be directly used to make
predictions, since it takes as input two labels. Hence, our predictor,
essentially, plays a tournament between all the potential labels using this
function we just mentioned. In the next step of the approach, i.e., in the
transition from the online setting to the statistical setting, one needs to
show how to simulate this Gale-Stewart game using the data that the learner
has access to. Since our Gale-Stewart game is more complex than the one in
[BHM+21], simulating it using data becomes more challenging.

In the case of linear rates these challenges are even more technically
involved and this is related to the fact that the Natarajan-Littlestone tree
has a more complicated structure than the VCL tree (for example, we need to
check all the possible mappings from some given points to labels). The Gale-
Stewart game that handles the case of linear rates goes as follows: the
adversary presents to the learner a tuple of points $x$, and two (different)
colorings for these points. Similarly as before, we could not use a simpler
game to obtain the result. Subsequently, as in the exponential rates case,
simulating this game using data becomes more complicated than in [BHM+21].
Proving the arbitrarily slow rates lower bound required some extra care than
in the VCL tree in order to guarantee that the designed distribution is
realizable.

In the setting of partial concept classes, our main contribution is a proof
that an alternative version of the SSP lemma, which bounds the growth
function, holds in this setting. In contrast, [AHHM22] showed that the
traditional version of the lemma (the "combinatorial" one) does not hold for
partial concept classes. We remark that these two versions are equivalent for
total concept classes. This lemma allows us to "tensorize" the disambiguation
lower bound that was proved in [AHHM22] for binary classes and establish it
for the multiclass setting.

###  1.6 Future Directions

We deal with the settings of universal learning and partial concept classes,
two fundamental questions [BHM+21, AHHM22] which are witnessed in real-life
applications, nevertheless the classical theory fails to explain. Our results
raise various interesting questions for future work (apart from 1). First, it
would be interesting to extend our results to the agnostic setting. Second,
for the universal setting, we believe it is an important next step to shed
light towards multiclass universal learning with an unbounded number of labels
(whose uniform learnability was recently characterized by [BCD+22]). We
shortly mention that the analysis of the exponential case still holds even for
a countably infinite number of labels. Moreover, for the partial concepts
setting, the work of [AHHM22] leaves numerous fascinating open questions for
the binary setting that can be asked in the multiclass setting too. In
general, our work along with its seminal binary counterparts [BHM+21, AHHM22]
shows that the algorithmic landscape occuring in practice is quite diverse and
the ERM principle is provably insufficient. It is important to come up with
principled algorithmic strategies that bring theory closer to practice.

##  2 Technical Overview & Proof Sketches

In this section we briefly discuss the technical details and provide proof
sketches of our main results.

###  2.1 Technical Overview of Universal Multiclass Learning

In the universal multiclass setting, we provide three lower bounds and two
algorithms in order to get the desired trichotomy of Theorem 1. The first
lower bound states that no class $\mathcal{H}$ is learnable at rate faster
than exponential (see Proposition 1). Our first essential contribution is that
any $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ is learnable at (optimal) rate
$e^{-n}$ if and only it has no infinite multiclass Littlestone tree. For this
task, we provide Algorithm 1 that achieves this rate. Our approach uses tools
from infinite game theory (Gale-Stewart games) and set theory (ordinals) in
order to show that there exists an online learning algorithm that makes only a
finite number of mistakes. We denote this key subroutine with $g_{t}$ in
Algorithm 1. In fact, this subroutine can be seen as an extension of the well-
known multiclass Standard Optimal Algorithm (SOA) to ordinal numbers. Our
final algorithm runs the above subroutine $g_{t}$ on multiple batches using
data-splitting techniques and then takes a majority vote; the intuition behind
this step is that the majority vote of various executions of our algorithm
will be much better concentrated than a single execution and will achieve the
desired exponential rate. The main technical challenge is to construct
$g_{t}$.

Algorithm 1 Exponential Rates Algorithm for Universal Multiclass Learning

Exponential Rates

Let $g_{t}:\mathcal{X}\rightarrow Y$ be an _eventually correct_ labeling
function (Theorem 5).

Let $(X_{1},Y_{1},\ldots,X_{n},Y_{n})$ be the training set.

Estimate $\hat{t}_{n}$ such that $\mathop{\bf
Pr\/}[\mathrm{er}(g_{\widehat{t}_{n}})]\leq 3/8$.

Break the training set into $N=n/\widehat{t}_{n}$ batches.

Create $N$ copies of $g$: $g^{1},...,g^{N}$ where the $i$-th copy is trained
on the $i$-th batch.

To predict the label of some $x\in\mathcal{X}$, take the majority vote over
all $g^{i}_{\widehat{t}_{n}}$.

Exponential GS Game

For any $t\in\mathbb{N}:$

$\texttt{P}_{A}$ picks
$\kappa_{t}=(\xi_{t},y^{(0)}_{t},y^{(1)}_{t})\in\mathcal{X}\times[k]\times[k].$

$\texttt{P}_{A}$ reveals $\kappa_{t}$ to the learner $\texttt{P}_{L}$.

$\texttt{P}_{L}$ chooses $\eta_{t}\in\left\\{0,1\right\\}$.

$\texttt{P}_{L}$ wins the game if for some $t\in\mathbb{N}$
$\\{h\in\mathcal{H}:h(\xi_{\ell})=y_{\ell}^{(\eta_{\ell})}~{}\forall\ell\in[1..t]\\}=\emptyset\,.$

Our approach to construct the eventually correct function $g_{t}$ passes
through the adversarial online learning setting. As a first step, we introduce
the standard multiclass online learning game [DSBDSS11] between an adversary
and a learner. In this game, the adversary picks a point $x_{t}\in\mathcal{X}$
and the learner guesses its true label $y_{t}\in[k]$. In the standard mistake
bound model [Lit88, DSBDSS11], the learner’s goal is to achieve a _uniformly_
bounded number of mistakes (and this is associated with the multiclass
Littlestone dimension and the Standard Optimal Algorithm). We extend this
model to the case where we can guarantee a finite number of mistakes for each
realizable sequence, but without an a priori bound on the number of mistakes,
i.e., this number is not _uniformly bounded_. This is the motivation behind
Definition 2. We prove that when $\mathcal{H}$ does not have an infinite
multiclass Littlestone tree, there exists an online learning algorithm for
this setting which makes finitely many mistakes. This is exactly the
eventually correct function $g_{t}$ of Algorithm 1. To be precise, the
function $g_{t}$ corresponds to the _winning strategy_ in round $t$ of the
learning player in the above game.

######  Theorem 5 (Informal, see Theorem 8).

For any $\mathcal{H}\subseteq[k]^{\mathcal{X}}$, if $\mathcal{H}$ does not
have an infinite multiclass Littlestone tree, there is a strategy
$g_{t},t\in\mathbb{N},$ for the learner that makes only finitely many
mistakes. Otherwise, the adversary has a winning strategy.

To prove this result, we invoke the theory of Gale-Stewart games. We introduce
a novel two-player game, the Exponential GS Game outlined in Algorithm 1. The
structure of this game looks like the standard multiclass online learning game
but has some evident differences; the adversary not only reveals a point
$\xi_{t}$ but also two colors for it. Then, the learner should choose between
these two. The structure of this game (while unaccustomed) is crucial and
generalizes the game of [BHM+21]. The learner wins if the class of consistent
hypotheses
$\mathcal{H}_{\kappa_{1},\eta_{1},...,\kappa_{t},\eta_{t}}=\\{h\in\mathcal{H}:h(\xi_{\ell})=y_{\ell}^{(\eta_{\ell})}~{}\forall\ell\in[1..t]\\}$
becomes empty after a finite number of rounds. If the game continues
indefinitely, the adversary wins. The intuition behind the definition of the
class in Algorithm 1 is that the adversary wins as long as there is always a
hypothesis in $\mathcal{H}$ that is consistent with the examples (this is in
parallel with the definition of an infinite path in the multiclass Littlestone
tree). Using tools from Gale-Stewart games (Proposition), we manage to show
that the learning player $\texttt{P}_{L}$ has a winning strategy if and only
if $\mathcal{H}$ does not have an infinite multiclass Littlestone tree. This
winning strategy is in fact the _ordinal Standard Optimal Algorithm_. Recall
that it is possible to have unbounded multiclass Littlestone dimension while
not having an infinite multiclass Littlestone tree.

In order to quantify this intermediate state (between uniformly bounded and
truly infinite), we invoke the theory of ordinal numbers and introduce the
_ordinal multiclass Littlestone dimension_ , which quantifies “how infinite”
the multiclass Littlestone dimension is. Hence, the learner’s strategy is to
play according to the SOA where the standard Littlstone dimension is replaced
by the ordinal one (see Section 3.1.1). We note that the analysis of the above
game constitutes an important technical contribution in the exponential rates
setting. More to that, we believe that the link between the multiclass SOA and
ordinals’ theory is an interesting conceptual step. For further details
concerning the exponential rates, we refer to Section 3.1. Our next result
(Theorem 10) is a lower bound indicating a sharp transition in the learning
rate: A class $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ that has an infinite
multiclass Littlestone tree is learnable no faster than $1/n$. Its proof uses
the probabilistic method and shows that for any learning algorithm
$\widehat{h}_{n}$, there exists a realizable distribution $P$ over
$\mathcal{X}\times[k]$ such that $\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]\geq\Omega(1/n)$ for infinitely many $n$,
when $\mathcal{H}$ has an infinite multiclass Littlestone tree.

We can now move to the linear rates setting where the situation is
significantly more involved technically. In this setting, we show that any
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$ is learnable at rate $1/n$ if and only
if it has no infinite NL tree. The structure of an NL tree indicates that the
notion of the Natarajan dimension (which characterizes learnability in the
uniform setting) is invoked in order to control the complexity/expressivity of
our concept class. Compared to the exponential rates setting, we shift our
goal from hoping for a finite number of mistakes to looking for a control over
the _model complexity_. This model complexity is quantified by the notion of
an _NL pattern in the data_ (see Definition 7). Conceptually, the design of
the algorithm for the linear rates follows a similar path as in the
exponential case; we first develop an infinite game which makes use of the
structure of the NL trees. This Linear GS Game is also original and can be
found in Algorithm 2. We remark that the precise structure of the game is
quite important for our results and various modifications of it seem to fail.

Algorithm 2 Linear Rates Algorithm for Universal Multiclass Learning

Linear Rates

Let $g_{t}:\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}\rightarrow\\{0,1\\}^{t}$
be an _eventually correct_ NL-pattern avoidance function.

Let $(X_{1},Y_{1},\ldots,X_{n},Y_{n})$ be the training set.

Estimate $\hat{t}_{n}$ such that $\mathop{\bf
Pr\/}[\mathrm{er}(g_{\widehat{t}_{n}})]\leq 3/8$.

Break the training set into $N=n/\widehat{t}_{n}$ batches.

Create $N$ copies of $g$: $g^{1},...,g^{N}$, where the $i$-th copy is trained
on the $i$-th batch.

Create $N$ copies of the one-inclusion graph predictor, each copy is equipped
with $g^{i}_{\widehat{t}_{n}}$.

To predict the label of $x$, take the majority vote over all the one-inclusion
graph predictors.

Linear GS Game

For any $t\in\mathbb{N}:$

$\texttt{P}_{A}$ picks a point
$\xi_{t}=\left(\xi_{t}^{(0)},...,\xi_{t}^{(t-1)},s_{t}^{(0)},s_{t}^{(1)}\right)$

where (i) $\xi_{t}\in\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}$ and

(ii) $s_{t}^{(0)},s_{t}^{(1)}$ s.t. $s_{t}^{(0)}(\xi_{t}^{(i)})\neq
s_{t}^{(1)}(\xi_{t}^{(i)})~{}\forall i$.

$\texttt{P}_{A}$ reveals $\xi_{t}$ to the learner $\texttt{P}_{L}$.

$\texttt{P}_{L}$ chooses a pattern $\eta_{t}\in\left\\{0,1\right\\}^{t}$.

$\texttt{P}_{L}$ wins the game if for some $t\in\mathbb{N}$
$\left\\{h\in\mathcal{H}~{}\textnormal{s.t.}\begin{array}[]{ll}h(\xi_{z}^{(i)})=s_{z}^{(\eta_{z}^{(i)})}(\xi_{z}^{(i)})\\\
\textnormal{for}~{}0\leq i<z,z\in[1..t]\\\ \end{array}\right\\}=\emptyset\,.$

In the Linear GS Game, the adversary picks $t$ points and two colorings for
these points which are everywhere different. Then the learner responds with an
_NL pattern_ $\eta_{t}\in\\{0,1\\}^{t}$ with the goal that there is _no_
$h\in\mathcal{H}$ that is $N$-consistent with the adversary’s input. Hence,
the learner aims to find _forbidden NL patterns in the data_. The finiteness
of the NL tree implies the existence of a winning strategy for the learner in
the game and, hence, an algorithm (which one can construct) for learning to
rule out NL patterns. Then, we show how to simulate this game using any
$\mathcal{H}$-realizable sequence and utilize the learner’s strategy to,
eventually, find forbidden NL patterns in the data. The simulation of the game
is another novel part for the linear rates (see Figure 7). Intuitively, there
exists some finite number $m$, which depends on the data sequence, such that
for any collection of $m+1$ points, there exists some invalid NL pattern. The
definition of the NL patterns then indicates that we cannot $N$-shatter any
collection of $m+1$ points and hence we can work, in some sense, with a class
whose Natarajan dimension is $m$. We can then use the one-inclusion hypergraph
algorithm [HLW94, RBR09, DSS14, BCD+22] (see Section B.2) to get a good
predictor for the data. Again a single execution of the above strategy is not
sufficient, we have to use data-splitting and aggregate our collection of
predictors using the majority vote. Algorithm 2 achieves an optimal rate of
$1/n$. Finally, we prove that a class with an infinite NL tree requires
arbitrarily slow rates.

######  Example 1 (Universal Rates for Linear Multiclass Classification).

Let us define the class of linear classifiers with $k$ labels in
$\mathbb{R}^{d}$ as $L=\\{h_{W}(x)=\arg\max(Wx)|W\in\mathbb{R}^{k\times
d}\\}$. We first remark that the Natarajan dimension of $L$ is
$\widetilde{\Theta}(kd)$ as noted for instance in [DSBDSS11] and so for fixed
$k,d$, this is a Natarajan class. Let us discuss the complexity of learning
this class in the universal setting. It is important to note that our
characterization of universal multiclass learning depends only on whether the
two proposed trees are infinite or not. In particular, we note that class $L$
has an infinite multiclass Littlestone tree and a finite Natarajan tree (since
it can only shatter a finite number of points as a Natarajan class). We also
remark that if we consider the class of linear multiclass classifiers over
$\mathbb{N}^{d}$ (a discrete geometric space), then this class does not even
have an infinite multiclass Littlestone tree and hence is learnable at an
exponentially fast rate. To see this, one can use the one-versus-one reduction
and observe that any classifier $h_{W}$ corresponds to a collection of
$\binom{k}{2}$ binary classifiers which are halfspaces in $\mathbb{N}^{d}$
where $h_{W}^{i,j}(x)=\textnormal{sgn}((W_{i}-W_{j})x)$ for any $i<j$. Then,
due to realizability, one can use an argument from infinite Ramsey theory (see
Example 2.10 from [BHM+21]) and prove that after a finite number of mistakes,
they can detect the correct halfspace for any pair $i<j$. Aggregating these
predictors, we get a multiclass linear classifier that enjoys an exponentially
fast learning rate.

###  2.2 Technical Overview of Partial Multiclass Learning

In the partial multiclass setting with a bounded number of labels, we first
characterize learnability in terms of the Natarajan dimension. For the proof
of Theorem 3, it suffices to show the following more fine-grained Theorem 6.

######  Theorem 6.

For any partial class
$\mathcal{H}\subseteq\\{0,1,...,k,\star\\}^{\mathcal{X}}$ with
$\mathrm{Ndim}(\mathcal{H})\leq\infty$, the sample complexity of PAC learning
$\mathcal{H}$ satisfies
$C_{1}\cdot\frac{\mathrm{Ndim}(\mathcal{H})+\log(1/\delta)}{\epsilon}\leq\mathcal{M}(\epsilon,\delta)\leq
C_{2}\cdot\frac{\mathrm{Ndim}(\mathcal{H})\log(k)\log(1/\delta)}{\epsilon},$
for some constants $C_{1},C_{2}$. In particular, if
$\mathrm{Ndim}(\mathcal{H})=\infty,$ then $\mathcal{H}$ is not PAC learnable.

For the upper bound, we have to employ the one-inclusion hypergraph algorithm
(see Section B.2). Following the methodology of [AHHM22], we extend its
guarantees (which hold for total concept classes) to the partial setting. This
algorithm guarantees an expected error which can be boosted to a high
probability result using standard concentration and boosting techniques. To
show that the partial concept class
$\mathcal{H}\subseteq\\{0,1,...,k,\star\\}$ is not learnable if it has
infinite Natarajan dimension, we reduce the problem to classification with
total concepts and invoke the existing (standard) lower bound. The main take-
away from Theorem 6 is that the algorithmic landscape of partial concept
classes is provably elusive, as already indicated by the seminal work of
[AHHM22]. To this end, we provide a second result that shows when one can
apply the well-understood ERM principle (which is valid when the number of
labels is bounded) with partial concepts. For details, we refer to Proposition
2. To conclude, we address the task of disambiguation [AKM19, AHHM22] of
partial concepts (see Definition 9). Our proof of Theorem 4 relies on an
interesting observation: the seminal work of [AHHM22] showed that the
combinatorial variant of the SSP lemma [Sau72] does not hold in this setting.
This lemma has a second variant that uses the growth function [SSBD14] instead
of the size of the class. We show that a natural extension of this variant for
partial classes is still correct (see Lemma 11). Using this tool and
techniques from [AHHM22], we obtain our impossibility result.

##  3 Universal Multiclass Learning: The Proof of Theorem 2

In this section, we prove Theorem 2 which then directly gives us Theorem 1 as
well. Our text is organized as follows:

  * •

In Section 3.1, we analyze the exponential rates case for multiclass learning.
We introduce the notion of the multiclass Littlestone tree and prove Theorem
7.

    * –

In order to achieve this, we first analyze the problem from an adversarial
online perspective in Section 3.1.1. The main result in this section is
Theorem 8.

    * –

The above result is in the adversarial setting and hence we have to transform
this online algorithm into a statistical one, i.e., we have to move from the
adversarial setting to the probabilistic setting. This is done is Section
3.1.2. We provide the analysis of our final algorithm in Theorem 9.

  * •

In Section 3.2, we show that a class with infinite multiclass Littlestone tree
cannot be learned at a rate faster than linear.

  * •

In Section 3.3, we introduce the notion of a Natarajan-Littlestone tree and we
prove Theorem 11.

    * –

In Section 3.3.1, we provide the important notion of a Natarajan-Littlestone
game which guarantees the existence of an eventually correct algorithm when
the class does not have an infinite NL tree.

    * –

In Section 3.3.2, we introduce the notion of an NL pattern in the data and
using the above algorithm as a pattern avoidance function.

    * –

The behavior of the pattern avoidance algorithm in the probabilistic setting
is given in Section 3.3.3.

    * –

The final linear rate algorithm can be found at Section 3.3.4.

  * •

In Section 3.4, the final lower bound which is related to arbitrarily slow
rates (see Theorem 13).

  * •

In Section 3.5, we provide the notion of a Graph-Littlestone tree and give a
sufficient condition for learning with a linear rate. More to that, we propose
1.

The missing proofs are presented in Appendix C.

###  3.1 Exponential Rates for Multiclass Learning

For a sequence $\bm{y}=(y_{1},y_{2},...)$, we denote $\bm{y}_{\leq
k}=(y_{1},...,y_{k})$. We may also usually identify elements of
$\\{0,1\\}^{d}$ with strings or a prefix of a sequence of length $d$. We begin
with a formal definition of a crucial combinatorial measure, namely the
multiclass Littlestone tree of a class $\mathcal{H}$.

######  Definition 5 (Multiclass Littlestone Tree).

A multiclass Littlestone tree for
$\mathcal{H}\subseteq\\{0,1,...,k\\}^{\mathcal{X}}$ is a complete binary tree
of depth $d\leq\infty$ whose internal nodes are labeled by $\mathcal{X}$, and
whose two edges connecting a node to its children are labeled by two different
elements in $[k]$, such that every path of length at most $d$ emanating from
the root is consistent with a concept $h\in\mathcal{H}$. Typically, a
multiclass Littlestone tree is a collection

$\bigcup_{0\leq\ell<d}\left\\{x_{u}:u\in\\{0,1\\}^{\ell}\right\\}=\\{x_{\emptyset}\\}\cup\\{x_{0},x_{1}\\}\cup\\{x_{00},x_{01},x_{10},x_{11}\\}\cup...$

such that for every path $\bm{y}\in\\{0,1\\}^{d}$ and finite $n<d$, there
exists $h\in\mathcal{H}$ so that
$h(x_{\bm{y}_{\leq\ell}})=s_{\bm{y}_{\leq\ell+1}}$ for $0\leq\ell\leq n$,
where $s_{\bm{y}_{\leq\ell+1}}$ is the label of the edge connecting the nodes
$x_{\bm{y}_{\leq\ell}}$ and $x_{\bm{y}_{\leq\ell+1}}$. We say that
$\mathcal{H}$ has an infinite multiclass Littlestone tree if there is a
multiclass Littlestone tree for $\mathcal{H}$ of depth $d=\infty$.

To give some intuition about this construction we state some of its
properties. First, it is crucial to note that a class $\mathcal{H}$ with a
finite multiclass Littlestone tree can have infinite multiclass Littlestone
dimension. In fact, a class has finite multiclass Littlestone dimension if the
depth of the tree admits a _uniform_ upper bound. However, it may be the case
that the class admits an unbounded tree, in the sense that for any finite
depth, there exists a tree of that depth; nevertheless the class does not have
an infinite tree. Second, a class with a finite multiclass Littlestone tree
may contain trees with infinite paths (e.g., a class that contains the
constant mapping $h=1$ can shatter the rightmost path at an infinite depth).
Finally, a class with finite multiclass Littlestone tree cannot have a tree
with an infinite complete binary subtree, since one could use only this
subtree and obtain an infinite tree. Essentially, this tree captures “how
infinite” the multiclass Littlestone dimension of $\mathcal{H}$ is: even if
there is no uniform bound on the multiclass Littlstone dimension of
$\mathcal{H}$, whenever $\mathcal{H}$ does not have an infinite tree we know
that for _any_
$S=\bigcup_{0\leq\ell<d}\left\\{x_{u}:u\in\\{0,1\\}^{\ell}\right\\}$ there is
some $n^{*}(S)<\infty$, which depends on the sequence $S$, so that the tree
can be shattered up to level $n^{*}(S)$.

The goal of this section is to prove the next result.

######  Theorem 7 (Exponential rates).

If $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ does not have an infinite
multiclass Littlestone tree, then for any distribution $P$, $\mathcal{H}$ is
learnable with an exponential optimal rate.

In order to prove this result, two steps are required: first, it suffices to
show that no class of hypotheses can be learned in a rate faster than
exponential (lower bound) and second, we have to show that not having an
infinite multiclass Littlestone tree is a sufficient for learning at an
exponential rate condition (upper bound). Hence, these two directions tightly
characterize universal learnability at exponential rates for multiclass
classification.

For the lower bound, the argument is essentially the same as in [BHM+21]. Let
us first give some intuition. If the distribution is supported on a finite
number of points, e.g., two, there is an exponentially small probability that
all the $n$ samples will contain the same point $(x,y)$, so it will not help
the learner distinguish between the functions $h\in\mathcal{H}$ that label
this point correctly. For completeness, we present the argument formally in
Section C.1.

######  Proposition 1 (Exponential Rates (Lower Bound)).

Fix $\mathcal{H}\subseteq\\{0,1,...,k\\}^{\mathcal{X}}$. For any learning
algorithm $\widehat{h}_{n}$, there exists a realizable distribution $P$ over
$\mathcal{X}\times\\{0,1,...,k\\}$ such that $\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]\geq\Omega(2^{-n})$ for infinitely many $n$.
This means that $\mathcal{H}$ is not learnable at rate faster than
exponential.

We continue with the upper bound, i.e., the design of an algorithm that learns
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$ at an exponentially fast rate when its
multiclass Littlestone tree is not infinite. Our approach consists of two main
steps. First, we consider the classical online adversarial setting where a
learner has to guess the label of a point that is presented to her by an
adversary. We prove that if $\mathcal{H}$ does not have an infinite multiclass
Littlestone tree, there is a strategy the learner can employ that makes a
_finite_ number of mistakes. Then, given such a strategy, we prove that there
is an algorithm in the statistical setting which achieves exponential learning
rates. The details are outlined in the subsequent sections.

####  3.1.1 Viewing Exponential Rates in an Online Setting

In order to design our algorithms, we have to consider the following setting.
We introduce the multiclass online learning game (Figure 3) that has been
studied extensively (see e.g., [DSBDSS11]). In this game, there are two
players, the adversary that chooses features and reveals them to the second
player, the learner whose goal is to guess a label for the given example.

1. The adversary picks a point $x_{t}\in\mathcal{X}$. 2. The learner guesses a value $\widehat{y}_{t}\in[k]$ 3. The adversary chooses the value $y_{t}$ as true label so that $y_{t}=h(x_{t})$ for some $h\in\mathcal{H}$ that is consistent with the previous examples $(x_{p},y_{p})$ for any $p\leq t$. Figure 3: Realizable Online Setting

The learner makes a mistake in round $t$ whenever the guess $\widehat{y}_{t}$
differs from the true label $y_{t}$. The goal of the learner is to minimize
her loss and the adversary’s intention is to provoke many errors to the
learner.

We say that the concept class $\mathcal{H}$ is online learnable if there
exists a strategy
$\widehat{y}_{t}=\widehat{y}_{t}(x_{1},y_{1},...,x_{t-1},y_{t-1},x_{t})$ that
makes a mistake only _finitely_ many times, regardless of what realizable
sequence is presented by the adversary. Notice that compared to the classical
online learning setting that asks for a bounded number of mistakes $d$, we
settle for a more modest goal. The main result in this setting is the
following.

######  Theorem 8 (Strategies in the Adversarial Setting).

For any concept class $\mathcal{H}\subseteq[k]^{\mathcal{X}}$, the following
dichotomy occurs.

  1. 1.

If $\mathcal{H}$ does not have an infinite multiclass Littlestone tree, then
there is a strategy for the learner that makes only finitely many mistakes
against any adversary.

  2. 2.

If $\mathcal{H}$ has an infinite multiclass Littlestone tree, then there is a
strategy for the adversary that forces any learner to make a mistake in every
round.

Before the formal proof, we provide a proof sketch. The adversary’s strategy
is clear. Whenever the learner predicts a label, she must choose a different
label that will cause the learner to make a mistake in that round; an infinite
Littlestone tree is exactly the combinatorial structure the adversary is
looking for. On the other hand, since there is no infinite multiclass
Littlestone tree, the learner’s predictions should lead her to a leaf of the
Littlestone tree that is defined by her interaction with the learner. This is
established by a variant of the (multiclass) Standard Optimal Algorithm (SOA)
[Lit88, DSBDSS11], which works whenever $\mathcal{H}$ has a finite multiclass
Littlestone dimension $d$. To gain some intuition, it is instructive to
consider the first step of her algorithm. The learner is presented with a
point $x_{1}$ and she picks the label
$y_{1}=\operatorname*{argmax}_{y\in[k]}\mathrm{Ldim}_{k}(\mathcal{H}_{x_{1},y})$.
It is easy to see that there is at most one $y$ such that
$\mathrm{Ldim}_{k}(\mathcal{H}_{x_{1},y})=d$; if there were two of them then
$\mathrm{Ldim}_{k}(\mathcal{H})=d+1$. Thus, by picking the one that induces
the subset of the hypothesis class with the largest Littlestone dimension, the
learner either does not make a mistake or gets closer to a leaf of the tree.

In our universal setting, this approach does not work immediately since it may
be the case that the multiclass Littlestone tree is not infinite but the
associated class has infinite multiclass Littlestone dimension. To this end,
we have to introduce the _ordinal multiclass Littlestone dimension_ , which
quantifies “how infinite” the multiclass Littlestone dimension is. Hence, the
learner’s strategy will be to play according to the _ordinal Standard Optimal
Algorithm_. The intuition is similar as in the classical setting, but the
proof becomes more involved. To establish the result, we follow the approach
of [BHM+21] and define a more general infinite game $\mathcal{G}$ between the
learner and the adversary and prove that it belongs to the family of the so-
called Gale-Stewart games. Then, we leverage results from the theory of Gale-
Stewart games and [BHM+21] in order to show that the ordinal SOA makes a
finite number of mistakes whenever $\mathcal{H}$ does not have an infinite
multiclass Littlestone tree. Let us continue with the proof.

###### Proof of Theorem 8.

We first introduce a two-player game $\mathcal{G}$ that is played in discrete
timesteps $t=1,2,\ldots$ between the adversary and the learner.

1. The adversary picks a point $\kappa_{t}=\left(\xi_{t},y^{(0)}_{t},y^{(1)}_{t}\right)\in\mathcal{X}\times[k]\times[k]$ and reveals it to the learner. 2. The learner chooses a point $\eta_{t}\in\left\\{0,1\right\\}$. Figure 4: Adversarial Setting - 2-Player Game

The learning player wins in some finite round $t$ if
$\mathcal{H}_{\xi_{1},y_{1}^{(\eta_{1})},...,\xi_{t},y_{t}^{(\eta_{t})}}=\emptyset$.
The adversary wins if the game continues indefinitely (i.e., the class of
consistent hypotheses from $\mathcal{H}$ never gets empty) . Clearly, the set
of winning strategies for the learning player is

$\mathcal{W}=\\{(\bm{\kappa},\bm{\eta})\in(\mathcal{X}\times[k]\times[k]\times\\{0,1\\})^{\infty}:\exists~{}1\leq
t^{\star}<\infty~{}\textnormal{ such that
}~{}\mathcal{H}_{\xi_{1},y_{1}^{(\eta_{1})},...,\xi_{t^{\star}},y_{t^{\star}}^{(\eta_{t^{\star}})}}=\emptyset\\}\,.$

We now recall an important theorem (see Proposition) about Gale-Stewart games:
In any Gale-Stewart game, exactly one of the adversary player and the learning
player has a winning strategy.

Equipped with Proposition, we can show that the adversary has a winning
strategy if and only if $\mathcal{H}$ has an infinite multiclass Littlestone
tree (provided that $\mathcal{G}$ is a Gale-Stewart game). This is summarized
in the next claim.

######  Claim 1.

The game $\mathcal{G}$ is a Gale-Stewart game and the adversary has a winning
strategy in $\mathcal{G}$ if and only if the hypothesis class $\mathcal{H}$
has an infinite multiclass Littlestone tree.

###### Proof.

It is clear from the definition of $\mathcal{W}$ that every winning strategy
of the learner is finitely decidable, hence $\mathcal{G}$ is a Gale-Stewart
game. For the other part of the claim, notice that if $\mathcal{H}$ has an
infinite multiclass Littlestone tree, then the adversary’s strategy is to
present the learner at step $t$ the point of the tree at depth $t$ that is
consistent with the execution of the game so far along with the labels of the
edges that connect it with its children. By the definition of the tree, this
strategy ensures that the game will keep going on forever. For the other
direction, assume that the adversary has a winning strategy
$\kappa_{\tau}(\eta_{1},\ldots,\eta_{\tau-1})\in\mathcal{X}\times[k]\times[k]$.
Then, define the multiclass Littlestone tree $\mathcal{T}=\\{x_{\bm{u}}:0\leq
k<\infty,\bm{u}\in\\{0,1\\}^{k}\\}$ where
$x_{\eta_{1},\ldots,\eta_{\tau-1}}=\xi_{\tau}(\eta_{1},\ldots,\eta_{\tau-1})$
where the labels that connect $x_{\eta_{1},\ldots,\eta_{\tau-1}}$ with its
left, right children are
$y^{(0)}_{\tau}(\eta_{1},\ldots,\eta_{\tau-1}),y^{(1)}_{\tau}(\eta_{1},\ldots,\eta_{\tau-1})$,
respectively. We can see that $\mathcal{T}$ is infinite since this is a
winning strategy for the adversary. ∎

Having shown the above statement, we are ready to establish the desired
dichotomy in the online game. Assume first that $\mathcal{H}$ has an infinite
multiclass Littlestone tree $\\{x_{u}\\}$. The adversary’s strategy is defined
inductively based on the path followed so far in the game: In round $t$, set
$\bm{b}_{t}=(b_{1},...,b_{t-1})\in\\{0,1\\}^{t-1}$ denote the path parsed so
far in the tree by the two players. Then, the adversary picks
$x_{t}=x_{\bm{b}_{t}}$. After the learner reveals her choice
$\widehat{y}_{t}$, the worst case adversary chooses as a response the branch
of the Littlestone tree which does not correspond to the learner’s choice (the
adversary may even have two choices). By the definition of the tree, this
chosen label is valid since there exists some $h\in\mathcal{H}$ that realizes
the path $(x_{b_{1}},...,x_{b_{t-1}},x_{t})$. Moreover, this choice provokes a
mistake to the learning player and this is true for any round. Hence, there is
a strategy for the adversary that forces any learner to make a mistake in
every round.

For the other direction, assume that the class $\mathcal{H}$ does not have an
infinite multiclass Littlestone tree. Before we describe the winning strategy
of the learner, we need to introduce the notion of ordinal multiclass
Littlestone dimension. We will assign an ordinal to every finite multiclass
Littlestone tree. For some preliminaries on ordinals and transfinite
recursion, we refer to [BHM+21]. The rank is defined by a partial order
$\prec$. We set $t^{\prime}\prec t$ if $t^{\prime}$ is a multiclass
Littlestone tree that extends $t$ by one level, i.e., $t$ is obtained from
$t^{\prime}$ by removing its leaves. A multiclass Littlestone tree $t$ is
minimal if it cannot be extended to a multiclass Littlestone tree of larger
depth. For such a tree, we set $\mathrm{rank}(t)=0$. If the tree $t$ is non-
minimal, then it can be extended and this is quantified using transfinite
recursion by

$\mathrm{rank}(t)=\sup\\{\mathrm{rank}(t^{\prime})+1:t^{\prime}\prec t\\}\,.$

The rank is well-defined as long as $\mathcal{H}$ has no infinite multiclass
Littlestone tree (since $\prec$ is well-founded). In particular, we define

$\overline{\mathrm{Ldim}}_{k}(\mathcal{H})=\left\\{\begin{array}[]{ll}-1&\textnormal{if
$\mathcal{H}$ is empty}\,,\\\ \Omega&\textnormal{if $\mathcal{H}$ has an
infinite multiclass Littlestone tree}\,,\\\
\mathrm{rank}(\emptyset)&\textnormal{otherwise}\,.\\\ \end{array}\right.$

The strategy is chosen so that
$\overline{\mathrm{Ldim}}_{k}(\mathcal{H}_{x_{1},y_{1},...,x_{t},y_{t}})$
decreases in every round and the learner that follows this strategy will win
the game, since the ordinals do not admit an infinite decreasing chain. We
note that this statement at first is purely existential via the theory of
Gale-Stewart games. We next shortly provide a “constructive” way to compute
the winning strategy of the learning player in the set of games we consider.
Let us describe the winning strategy: The learner invokes the ordinal
(multiclass) Standard Optimal Algorithm and chooses the label $y_{t}$ (given
$x_{t})$ that maximizes the ordinal multiclass Littlestone dimension, i.e.,
$y_{t}=\operatorname*{argmax}_{y\in[k]}\overline{\mathrm{Ldim}}_{k}(V^{y}_{t})$,
where =
$V^{y}_{t}=\\{h\in\mathcal{H}_{x_{1},y_{1},...,x_{t-1},y_{t-1}}:h(x_{t})=y\\}$.
The ordinal SOA at round $t=1,2,...$ with initial set $V_{0}=\mathcal{H}$
works as follows:

  1. 1.

Receive $x_{t}$.

  2. 2.

For any $y\in[k]$, let $V_{t}^{y}=\\{h\in V_{t-1}:h(x_{t})=y\\}$.

  3. 3.

Predict
$\widehat{y}_{t}\in\operatorname*{argmax}_{y\in[k]}\overline{\mathrm{Ldim}}_{k}(V_{t}^{y})$,
where $\overline{\mathrm{Ldim}}_{k}$ is the ordinal multiclass Littlestone
dimension.

  4. 4.

Receive true answer $y_{t}$ and set $V_{t}=V_{t}^{y_{t}}$.

This algorithm drives the game in a win-win phenomenon for the learner in
every round: If the adversary forces the learner to a mistake, then she will
“prune” the tree and set the learner closer to winning the game. Otherwise,
the learner will be correct and will not incur any loss. In order to show that
the ordinal SOA makes a finite number of mistakes, we couple the online game
with a Gale-Stewart game. The idea is that every time the learner makes a
mistake in the online game on point $x_{t}$, we advance the Gale-Stewart game
by one round where we pretend that
$\xi_{\tau}=x_{t},y^{(0)}_{\tau}=\widehat{y}_{t},y^{(1)}_{\tau}=y_{t},\eta_{\tau}=y_{t}$.
Notice that if the learner makes an infinite number of mistakes in the online
game using the ordinal SOA, then the Gale-Stewart game can proceed infinitely.
Hence, to conclude the proof, we need to show that in this coupled game, there
is some finite point $\tau^{*}$ such that
$\mathcal{H}_{\xi_{1},y_{1}^{(\eta_{1})},\ldots,\xi_{\tau^{\star}},y_{\tau^{\star}}^{(\eta_{\tau^{\star}})}}=\emptyset$.
The following result helps us establish that. In fact, the next lemma follows
from [BHM+21](Proposition B.8) by choosing the value of the game being the
ordinal multiclass Littlestone dimension.

######  Lemma 1 (See Proposition B.8 of [BHM+21]).

Assume that $\mathcal{H}$ does not contain an infinite multiclass Littlestone
tree. Then, for any choices of the adversary $\kappa_{1},\ldots,\kappa_{t-1}$
up to round $t$ and for any choice
$\kappa_{t}=(\xi_{t},y^{(0)}_{t},y^{(1)}_{t})$ in round $t$ there is a choice
$\eta_{t}$ of the learner such that

$\overline{\mathrm{Ldim}}_{k}\left(\mathcal{H}_{\xi_{1},y_{1}^{(\eta_{1})},\ldots,\xi_{t-1},y_{t-1}^{(\eta_{t-1})},\xi_{t},y_{t}^{(\eta_{t})}}\right)<\overline{\mathrm{Ldim}}_{k}\left(\mathcal{H}_{\xi_{1},y_{1}^{(\eta_{1})},\ldots,\xi_{t-1},y_{t-1}^{(\eta_{t-1})}}\right)\,.$

The previous result shows that for every $\xi_{t}$ there is at most one label
$\ell_{t}\in[k]$ such that

$\overline{\mathrm{Ldim}}_{k}\left(\mathcal{H}_{\xi_{1},y_{1}^{(\eta_{1})},\ldots,\xi_{t-1},y_{t-1}^{(\eta_{t-1})},\xi_{t},\ell_{t}}\right)=\overline{\mathrm{Ldim}}_{k}\left(\mathcal{H}_{\xi_{1},y_{1}^{(\eta_{1})},\ldots,\xi_{t-1},y_{t-1}^{(\eta_{t-1})}}\right)\,.$

Indeed, assume that there are two such labels $\ell_{t},\ell_{t}^{\prime}$ for
some $\xi_{t}$. Then, if the adversary proposes the point
$(\xi_{t},\ell_{t},\ell_{t}^{\prime})$, there is no choice $\eta_{t}$ of the
learner that decreases that ordinal Littlestone dimension in this round, which
leads to a contradiction. Hence, the learner can pick any label as long as it
is not the one that maximizes the ordinal Littlestone dimension. This is
exactly how the coupled Gale-Stewart game proceeds, so we know that every time
the learner makes a mistake in the online game the ordinal Littlestone
dimension of the coupled game decreases. Since ordinals that are less than
$\Omega$ do not admit infinitely decreasing chains, we get the desired result.

∎

####  3.1.2 Moving from the Adversarial Setting to the Probabilistic Setting

The measurability of the winning strategies and of the learning algorithm
developped in the previous section constitutes an important detail,
extensively discussed in [BHM+21], in order to move from the adversarial
setting to the probabilistic one. We provide the next useful result. Its proof
can be found at Section C.2.

######  Lemma 2.

Let $\mathcal{X}$ be Polish, $k\in\mathbb{N}$ be a finite constant and
$\mathcal{H}\subseteq[k]^{\mathcal{X}}$ be measurable. Then, the Gale-Stewart
game $\mathcal{G}$ of Figure 4 has a universally measurable winning strategy.

Crucially the above result states that the winning strategy $\eta_{t}$ of the
learning player is measurable. However, the previous proof made use of the
ordinal multiclass SOA algorithm, whose measurability is not directly implied.
To this end, we modify the adversarial algorithm to handle the measurability
issue. The modification follows:

1. Initialize $\tau\leftarrow 1,G=\texttt{Clique}(V=[k]),f(\cdot,\cdot,\cdot)\leftarrow\eta_{1}(\cdot,\cdot,\cdot)$ $\triangleright$ $\tau$ is the mistake counter 2. For every round $t\geq 1:$ (a) Observe $x_{t}$ (b) For any $y\neq y^{\prime}$ with $y,y^{\prime}\in[k]$, orient the edge $(y,y^{\prime})$ of $G$ according to $f(x_{t},y,y^{\prime})$ (c) Let $G^{\prime}$ the directed clique (d) Predict $\widehat{y}_{t}\leftarrow\operatorname*{argmax}_{y\in[k]}\mathrm{outdeg}(y;G^{\prime})$ (e) If $\widehat{y}_{t}\neq y_{t}$, let $\xi_{\tau}\leftarrow x_{t},f(\cdot,\cdot,\cdot)\leftarrow\eta_{\tau+1}(x_{1},y_{1},\ldots,x_{\tau},y_{\tau},\cdot,\cdot,\cdot),\tau\leftarrow\tau+1$ Figure 5: Measurable Modification of Online Learning Algorithm for Exponential Rates

The above algorithm makes use of a tournament procedure. The algorithm is a
measurable function since (i) the winning strategy of the learner is
measurable and (ii) the countable maximum of measurable functions is
measurable. This algorithm can be used in order to show that if $\mathcal{H}$
does not have an infinite multiclass Littlestone tree, then the above
algorithm makes only a finite number of mistakes against any adversary.
Essentially, this is due to the fact that when the winning strategy has
converged to a zero-mistake prediction rule (which occurs after a finite
number of mistakes), the tournament procedure will always output the correct
label for the observed example. Hence, the algorithm will eventually make a
finite number of mistakes in the adversarial setting.

The algorithm of Figure 5 works in the adversarial setting. We first show that
it also applies to the probabilistic setting (and this is why we require the
above measurability discussion). The proof is quite similar to Lemma 4.3 of
[BHM+21] and can be found at Section C.3.

######  Lemma 3 (From Adversarial to Probabilistic).

For any distribution $P$ over $\mathcal{X}\times[k]$ and for the learning
algorithm $\widehat{y}_{t}:\mathcal{X}\to[k]$ of Figure 5, we have

$\mathop{\bf Pr\/}_{S_{t}}\left[\mathop{\bf Pr\/}_{(x,y)\sim
P}[\widehat{y}_{t}(x)\neq y]>0\right]\to 0~{}as~{}~{}t\to\infty\,,$

where $S_{t}$ is the training set $(x_{1},y_{1},...,x_{t-1},y_{t-1})$ of the
algorithm.

The above result guarantees that the expected error of the learning algorithm
tends to zero as $t$ goes to infinity, i.e., we have established that that
$\mathop{\bf E\/}[\mathrm{er}(\widehat{y}_{t})]\rightarrow 0$ as
$t\rightarrow\infty$. This means that the ordinal SOA is a consistent
algorithm in the statistical setting. However, this fact is not enough to
establish the exponential convergence rate. We follow the approach of [BHM+21]
to come up with an algorithm that achieves this guarantee. The first step is
to observe that there is some distribution-dependent $t^{\star}$ such that
$\mathop{\bf Pr\/}[\mathrm{er}(\widehat{y}_{t^{\star}})>0]<1/4$. If we were to
know this $t^{\star}$ one way to get the exponential rates is the following:
We divide the training set into $\Theta(n/t^{\star})$ batches and we get one
classifier $\widehat{y}^{i}_{t^{\star}}$ for every batch. Afterwards, we
output as classifier the multiclass majority vote among the classifiers.
Nevertheless, we can obtain this exponential convergence even without knowing
$t^{\star}$ by computing an estimate for this quantity using samples.
Essentially, we provide this estimator in Lemma 4. For the proof, we refer to
the Section C.4.

######  Lemma 4.

For any $n\in\mathbb{N}$, there exists a universally measurable
$\widehat{t}_{n}=\widehat{t}_{n}(X_{1},Y_{1},...,X_{n},Y_{n})$ whose
definition does not depend on $P$ so that the following holds. Set the
critical time $t^{\star}\in\mathbb{N}$ be such that

$\mathop{\bf Pr\/}\left[\mathop{\bf Pr\/}_{(x,y)\sim
P}[\widehat{y}_{t^{\star}}(x)\neq y]>0\right]\leq 1/8\,,$

where the probability is over the training set of the algorithm
$\widehat{y}_{t}$. There exist $C,c>0$ that depend on $P,t^{\star}$ but not
$n$ so that

$\mathop{\bf Pr\/}[\widehat{t}_{n}\in T^{\star}]\geq 1-Ce^{-cn}\,.$

where the probability is over the training of the estimator $\widehat{t}_{n}$
and $T^{\star}$ is the set

$T^{\star}=\left\\{1\leq t\leq t^{\star}:\mathop{\bf Pr\/}\left[\mathop{\bf
Pr\/}_{(x,y)\sim P}[\widehat{y}_{t}(x)\neq y]>0\right]\leq 3/8\right\\}\,,$

where the probability is over the training of $\widehat{y}_{t}$.

Our main result follows.

######  Theorem 9 (Exponential Rates).

Assume that class $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ does not have an
infinite multiclass Littlestone tree. Then, $\mathcal{H}$ admits a learning
algorithm that achieves an exponentially fast rate.

###### Proof.

Consider the sequence $\widehat{t}_{n}$ which satisfies the properties of
Lemma 4. Consider the collection of the learners
$\mathbb{A}_{i,n}:=\widehat{y}_{\widehat{t}_{n}}^{i}:\mathcal{X}\to[k]$ for
any $1\leq i\leq\lfloor\frac{n}{2\widehat{t}_{n}}\rfloor$ and
$n\in\mathbb{N}$. Let us fix a time $t\in T^{\star}$, where $T^{\star}$ is the
set of good estimates of the critical time $t^{\star}$ (see Lemma 4). We have
that

$\mathop{\bf
Pr\/}\left[\frac{1}{\lfloor\frac{n}{2t}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{2t}\rfloor}\bm{1}\left\\{\mathop{\bf
Pr\/}_{(x,y)\sim P}\left[\widehat{y}_{t}^{i}(x)\neq
y\right]>0\right\\}>\frac{7}{16}\right]\leq\exp\left(-\Big{\lfloor}n/(2t^{\star})\Big{\rfloor}/128\right)\,,$

using Hoeffding’s inequality. The above probability is over the sequence of
all the training sets and essentially states that the “bad” event that the
misclassification error is non-zero holds for the majority of the trained
algorithms $\widehat{y}_{t}^{i}$ with exponentially small probability.
Conversely, except on an event of exponentially small probability, we have
that $\mathop{\bf Pr\/}_{(x,y)\sim P}[\widehat{y}_{t}^{i}(x)\neq y]=0$ for the
majority of $i$. Recall that the above discussion holds for a chosen good $t$.
We have to understand how well our learners $\mathbb{A}_{i,n}$ perform. To
this end, we have that

$\displaystyle\mathop{\bf Pr\/}\left[\mathop{\bf Pr\/}_{(x,y)\sim
P}[\mathbb{A}_{i,n}(x)\neq y]>0\text{ for the majority of $i\leq\lfloor
n/(2\widehat{t}_{n})\rfloor$}\right]$ $\displaystyle\leq\mathop{\bf
Pr\/}\left[\widehat{t}_{n}\notin T^{\star}\right]+\mathop{\bf
Pr\/}\left[\exists t\in T^{\star}:\mathop{\bf Pr\/}_{(x,y)\sim
P}[\widehat{y}_{t}^{i}(x)\neq y]>0\text{ for the majority of $i\leq\lfloor
n/(2\widehat{t}_{n})\rfloor$}\right]$ $\displaystyle\leq C(P)\exp(-c(P)\cdot
n)+t^{\star}\cdot\exp\left(-\Big{\lfloor}n/(2t^{\star})\Big{\rfloor}/128\right)\,.$

This implies that the majority of our learners $\mathbb{A}_{i,n}$ will not
incur loss except on an event of exponentially small probability. As a result,
the majority vote of these classifiers is almost surely correct on a random
sample from the distribution $P$ over $\mathcal{X}\times[k]$. Hence, we have
that

$\displaystyle\mathop{\bf E\/}\left[\mathop{\bf Pr\/}_{(x,y)\sim
P}\left[\mathrm{Maj}((\mathbb{A}_{i,n}(x))_{i})\neq y\right]\right]$
$\displaystyle\leq\mathop{\bf Pr\/}\left[\mathop{\bf Pr\/}_{(x,y)\sim
P}\left[\mathrm{Maj}((\mathbb{A}_{i,n}(x))_{i})\neq y\right]>0\right]$
$\displaystyle\leq C(P)\exp(-c(P)\cdot
n)+t^{\star}\cdot\exp\left(-\Big{\lfloor}n/(2t^{\star})\Big{\rfloor}/128\right)\,.$

This concludes the proof. ∎

###  3.2 Infinite Multiclass Littlestone Trees and Rates

We next show that if $\mathcal{H}$ has an infinite mutliclass Littlestone
tree, then there exists a significant drop in the rate: any learning algorithm
$\mathcal{H}$ cannot be faster than linear. Our proof follows the approach in
[BHM+21].

######  Theorem 10.

Assume that $\mathcal{H}\subseteq\\{0,1,...,k\\}^{\mathcal{X}}$ has an
infinite multiclass Littlestone tree. Then, for any learning algorithm
$\widehat{h}_{n}$, there exists a realizable distribution $P$ over
$\mathcal{X}\times[k]$ such that $\mathop{\bf
E\/}[\mathrm{er}(\widehat{h}_{n})]\geq\Omega(1/n)$ for infinitely many $n$.
This means that $\mathcal{H}$ is not learnable at rate faster than linear,
i.e., $R(n)\geq 1/n$.

Let us provide some intuition. We will make use of the probabilistic method.
We are going to define a distribution over probability distributions so that,
with positive probability over this choice of the random object, any learning
algorithm will have an expected error of order $\Omega(1/n)$. This positive
probability implies that there exists such a distribution and hence the above
result holds true. The key idea is that we are going to associate any random
distribution $P_{\bm{y}}$ with a branch $\bm{y}$ of the infinite multiclass
Littlestone tree. Given a finite number of samples from this distribution,
only a finite part of this infinite path will be discovered; hence any
algorithm after the “revealed path” must guess whether this random path goes
left or right. This implies that the algorithm will err with probability $1/2$
when it observes a point that lies deeper in the branch than the training
examples. The proof can be found at Section C.5.

The above result states that a class which does not have exponential rates
cannot be learned faster than linearly. However, it is not clear if even
linear rates are achievable. The next section deals with this case.

###  3.3 Linear Learning Rates and Natarajan-Littlestone Trees

We introduce a novel combinatorial measure, the Natarajan-Littlestone (NL)
tree, which essentially combines the structure of the Natarajan dimension and
the Littlestone dimension.

######  Definition 6.

A Natarajan-Littlestone (NL) tree for $\mathcal{H}\subseteq[k]^{\mathcal{X}}$
of depth $d\leq\infty$ consists of a tree

$\bigcup_{0\leq\ell<d}\\{x_{u}\in\mathcal{X}^{\ell+1},u\in\\{0,1\\}\times\\{0,1\\}^{2}\times...\times\\{0,1\\}^{\ell}\\}$

and two colorings $s^{(0)},s^{(1)}$ mapping each position $u^{i}\in u$ for any
node with pattern $u\in\\{0,1\\}\times...\times\\{0,1\\}^{\ell}$ for
$i\in\\{0,1,...,\ell\\}$ and $\ell\in\\{0,1,...,d-1\\}$ of the tree to some
color $\\{0,1,...,k\\}$ such that for every finite level $n<d$, the subtree
$T_{n}=\cup_{0\leq\ell\leq
n}\\{x_{u}=(x_{u}^{0},...,x_{u}^{\ell}):u\in\\{0,1\\}\times\\{0,1\\}^{2}\times...\times\\{0,1\\}^{\ell}\\}$
satisfies the following:

  1. 1.

At any point $x_{u}^{i}\in x_{u}\in T_{n}$, it holds $s^{(0)}(x_{u}^{i})\neq
s^{(1)}(x_{u}^{i})$ and

  2. 2.

for any path $\bm{y}\in\\{0,1\\}\times...\times\\{0,1\\}^{n+1}$, there exists
a concept $h\in\mathcal{H}$ so that
$h(x^{i}_{\bm{y}_{\leq\ell}})=s^{(0)}(x^{i}_{\bm{y}_{\leq\ell}})$ if
$y^{i}_{\ell+1}=1$ and
$h(x^{i}_{\bm{y}_{\leq\ell}})=s^{(1)}(x^{i}_{\bm{y}_{\leq\ell}})$ otherwise,
for all $0\leq i\leq\ell$ and $0\leq\ell\leq n$, where

$\bm{y}_{\leq\ell}=(y_{1}^{0},(y_{2}^{0},y_{2}^{1}),...,(y_{\ell}^{0},...,y_{\ell}^{\ell-1})),x_{\bm{y}_{\leq\ell}}=(x^{0}_{\bm{y}_{\leq\ell}},...,x^{\ell}_{\bm{y}_{\leq\ell}})\,.$

We say that $\mathcal{H}$ has an infinite NL tree if it has a NL tree of depth
$d=\infty$.

We note that in the above definition we identify the color
$s^{(0)}(x^{i}_{\bm{y}\leq\ell})$ with the (unique) position of this point
$x^{i}_{\bm{y}\leq\ell}$ (since typically the coloring is over positions). For
short, we will call the colorings $s^{(0)},s^{(1)}$ used in the above
definition _everywhere different_ and denote by $s^{(0)}\neq s^{(1)}$. As a
sanity check, one can verify that if $\mathcal{H}$ has an infinite NL tree,
then it has an infinite multiclass Littlestone tree. In fact, one can
construct the latter tree by choosing only one point from any node of the
infinite NL tree.

The main result of this section is the next theorem.

######  Theorem 11.

Assume that $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ does not have an infinite
Natarajan-Littlestone tree. Then, there exists an algorithm that learns
$\mathcal{H}$ at a linear rate.

####  3.3.1 The Natarajan-Littlestone Game

In a similar manner as in the exponential rates setting, we need to come up
with a function that is correct after a finite number of steps $n^{*}$ and
this implies that some appropriate data-dependent complexity measure of
$\mathcal{H}$ is finite. The first step towards establishing the desired
result is to introduce the following two-player game between an adversary and
a learning player.

1. The adversary picks $t$ points and two everywhere different colorings of these $t$ points $\xi_{t}=\left(\xi_{t}^{(0)},...,\xi_{t}^{(t-1)},s_{t}^{(0)},s_{t}^{(1)}\right)\in\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}$ and reveals them to the learner. 2. The learner chooses a pattern $\eta_{t}=(\eta_{t}^{(0)},...,\eta_{t}^{(t-1)})\in\left\\{0,1\right\\}^{t}$. Figure 6: Adversarial Setting - 2-Player NL Game

Let
$\Xi_{t}=\\{\xi_{1}^{(0)},\xi_{2}^{(0)},\xi_{2}^{(1)},...,\xi_{t}^{(0)},\ldots,\xi_{t}^{(t-1)},s_{1}^{(0)},s_{1}^{(1)},\ldots,s_{t}^{(0)},s_{t}^{(1)}\\}$
be the sets of all points and colorings chosen by the adversary after $t$
rounds, for some finite integer $t$. The learning player wins the game in
round $t$ if the class
$\mathcal{H}_{t}=\mathcal{H}_{\xi_{1},\eta_{1},...,\xi_{t},\eta_{t}}=\emptyset$,
where $\mathcal{H}_{0}=\mathcal{H}$ and
$\mathcal{H}_{t}=\mathcal{H}_{\xi_{1},\eta_{1},...,\xi_{t},\eta_{t}}$ is the
set

$\left\\{h\in\mathcal{H}~{}\textnormal{so
that}\begin{array}[]{ll}h(\xi_{z}^{(i)})=s_{z}^{(0)}(\xi_{z}^{(i)})~{}\textnormal{if}~{}\eta_{z}^{(i)}=0\\\
h(\xi_{z}^{(i)})=s_{z}^{(1)}(\xi_{z}^{(i)})~{}\textnormal{if}~{}\eta_{z}^{(i)}=1\\\
\end{array}~{}\textnormal{for}~{}0\leq i<z,z\in[1..t]\right\\}\,.$

Note that the collection of valid functions decreases as the game proceeds,
i.e., $\mathcal{H}_{t}\subseteq\mathcal{H}_{t-1}.$ The next lemma guarantees
the existence of a winning strategy for the learner in the game. For the
proof, see Section C.6.

######  Lemma 5.

If $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ has no infinite NL tree, then there
is a universally measurable winning strategy for the learning player in the
game $\mathcal{G}.$

####  3.3.2 Pattern Avoidance Algorithm

Our learning algorithm for the linear rates case will be built over the notion
of data patterns and pattern avoidance functions. In the exponential rates
setting, we focused on the case where the learner is successful if she makes a
finite number of mistakes. In the case of linear rates, this is replaced with
controlling the _model complexity_ , i.e., we have to understand how
expressive the class $\mathcal{H}$ is. We will say that a sequence
$x_{1},y_{1},x_{2},y_{2},...$ in $(\mathcal{X}\times[k])^{\infty}$ is
_consistent_ with $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ if, for every finite
$t<\infty$, there exists $h\in\mathcal{H}$ such that $h(x_{i})=y_{i}$ for all
$i\leq t$.

We next introduce the crucial notion of pattern. Intuitively, the expressivity
of a hypothesis class $\mathcal{H}$ is proportional to the length of the
“patterns” realized by concepts in $\mathcal{H}$. Hence, by controlling the
length of the realizable patterns, we can obtain learners for $\mathcal{H}$.

######  Definition 7.

Given a sequence
$S=(x_{1},y_{2},x_{2},y_{2},...)\in(\mathcal{X}\times[k])^{\infty}$ that is
consistent with $\mathcal{H}$, the binary string $b_{t}\in\\{0,1\\}^{t}$ of
length $t$ is a Natarajan-Littlestone pattern (or simply a pattern) if there
exists a subsequence of consecutive terms
$S^{\prime}=(x_{z+i},y_{z+i})_{i\in[t]}$ of length $t$ for some
$z\in\mathbb{N}$ so that there exist two $k$-colorings everywhere different
$s^{(0)},s^{(1)}$ of the elements $(x_{z+i})_{i\in[t]}$ with
$s^{(0)}(x_{z+i})=y_{z+i}$ if $b_{t}=0$ and $s^{(1)}(x_{z+i})=y_{z+i}$ if
$b_{t}=1$.

We are going to use the winning strategy of the learning player of the game of
Figure 6 in order to design an algorithm that _avoids NL patterns in the
data_. This is exactly the intuition behind the design of the Gale-Stewart
game of Figure 6. The learner predicts a binary string
$\eta_{t}\in\\{0,1\\}^{t}$ with goal that this pattern is not realized by the
class $\mathcal{H}$, i.e., it is not a NL pattern with respect to a sequence
consistent with $\mathcal{H}$. Intuitively, the reason we are aiming for
forbidden patterns is the following: before witnessing the realizable sequence
we have no control over the complexity of the hypothesis class $\mathcal{H}$,
since its Natarajan dimension can be infinite. However, leveraging the fact
that there is no infinite NL-tree we show that for every realizable sequence
$S$ there is some (sequence-dependent) $n^{*}(S)$ such that the class
$\mathcal{H}_{x_{1},y_{1},\ldots,x_{n^{*}},y_{n^{*}}}$ of the concepts that
agree on the first $n^{*}$ terms has Natarajan dimension that is bounded by
$O(n^{*})$. This is because if we can produce a forbidden pattern for every
$x$-tuple of length $n^{*}$ we know that the Natarajan dimension of this class
is bounded by $n^{*}$.

The algorithm will get as input a data sequence consistent with $\mathcal{H}$
and will identify patterns in the data. In particular, the algorithm works as
follows: For any finite pattern length $t$, the algorithm traverses the data
sequence in consecutive blocks of length $t$ and in each such block it tries
all the everywhere different colorings for the points and uses the universally
measurable winning strategy of the learning player to obtain a guess for a
forbidden NL pattern for each of these colorings. The algorithm then checks if
at least one of the pairs of colorings and forbidden patterns are actually
realized by the data. If this is the case (i.e., the guess was false), the
algorithm adds a new point $\xi_{t}$ in its list of “bad points” and continues
searching for patterns of larger length. If the guess was correct and the
pattern is not realized in this block, it continues with the same pattern size
in the next block.

The algorithm operates as follows. We remark that we can construct the
strategy $\eta_{t}$ of the learner by invoking a notion of ordinal NL
dimension in a similar manner as in the exponential rates case.

1. Initialize the pattern length $\ell_{0}=1$. 2. At every time step $t\geq 1:$ (a) Set $L:=\ell_{t-1}$ and create a list $S_{L}$ of all the possible pairs of everywhere different colorings of $L$ elements. (b) Set $j:=1$ be the index that traverses the list $S_{L}.$ (c) Set $s^{(0)}:=S_{L}[j](0),s^{(1)}:=S_{L}[j](1).$ (d) Compute pattern $b_{L}=\eta_{L}(\xi_{1},...,\xi_{L-1},x_{t-L+1},...,x_{t},s^{(0)},s^{(1)})\in\\{0,1\\}^{L}\times[k]^{L}\times[k]^{L}.$ (e) If it holds that, $s^{(0)}_{z}(x_{t-L+1+z})=y_{t-L+1+z},$ if $b_{L}(z)=0$, and $s^{(1)}_{z}(x_{t-L+1+z})=y_{t-L+1+z}$, otherwise, for $z\in\\{0,1,...,L-1\\}$, then i. Set $\xi_{L}=(x_{t-L+1},...,x_{t},s^{(0)},s^{(1)})$ //The pattern is realized (not forbidden). ii. Update $\ell_{t}=L+1$ //Look for larger patterns. (f) Else: i. If $j<L$ then update $j:=j+1$ and go to step (c). ii. Else shift the block, and move to the next timestep, i.e. $\ell_{t}=L,t:=t+1$. Figure 7: Pattern Avoidance Algorithm

Hence, the above procedure defines a pattern avoidance function

$\widehat{y}_{t-1}(x_{1},...,x_{\ell_{t-1}},s^{(0)},s^{(1)}):=\eta_{\ell_{t-1}}(\xi_{1},...,\xi_{\ell_{t-1}-1},x_{1},...,x_{\ell_{t-1}},s^{(0)},s^{(1)})\in\\{0,1\\}^{\ell_{t-1}}\times[k]^{\ell_{t-1}}\times[k]^{\ell_{t-1}}\,.$
(1)

The intuition is that as long as the class $\mathcal{H}$ does not have an
infinite NL tree and a consistent sequence is provided to the algorithm, then
whenever the “if” statement gets True, the game of Figure 6 progresses and the
learner gets closer to winning the game. The finiteness of the NL tree gives
the next key lemma.

######  Lemma 6.

For any sequence $x_{1},y_{1},x_{2},y_{2},...$ that is consistent with
$\mathcal{H}$, the pattern avoidance algorithm of Figure 7, in a finite number
of steps, rules out NL patterns in the data sequence, in the sense that the
“if” statement in Line (c) is false and
$\ell_{t}=\ell_{t-1}<\infty,\widehat{y}_{t}=\widehat{y}_{t-1}$ for all
sufficiently large $t$. Moreover, the mappings $\ell_{t}$ and
$\widehat{y}_{t}$ are universally measurable.

###### Proof.

Consider an infinite sequence of times $t=t_{1},t_{2},...$ and assume that the
“if” condition is true for any time-step in this sequence. Since $\eta_{t}$ is
a winning strategy for the learning player in the Gale-Stewart game
$\mathcal{G}$, we have that there exists some finite time $t^{\star}$ so that
$\mathcal{H}_{\xi_{1},\eta_{1},...,\xi_{t^{\star}},\eta_{t^{\star}}}=\emptyset.$
By the structure of the “if” condition, we have that
$\xi_{i}=(x_{t_{i}-\ell_{t_{i}}-1}+1,...,x_{t_{i}})$ and
$\eta_{i}=(y_{t_{i}-\ell_{t_{i}}-1}+1,...,y_{t_{i}})$. But since the sequence
is consistent with $\mathcal{H}$, the class
$\mathcal{H}_{\xi_{1},\eta_{1},...,\xi_{t^{\star}},\eta_{t^{\star}}}$ must
contain the hypothesis that makes it consistent which is a contradiction since
the class is empty. For the measurability of the strategies, we refer to
Remark 5.4 of [BHM+21]. ∎

####  3.3.3 Asymptotic Behavior of the Algorithm

As in the case of exponential rates, our first goal towards the design of our
algorithms is an asymptotic result. We first have to move from the adversarial
to a probabilistic setting. Fix a realizable distribution $P$ over
$\mathcal{X}\times[k]$ and let $(X_{1},Y_{1}),(X_{2},Y_{2}),...$ be i.i.d.
samples from $P$. As it is clear in this section for the upper bounds, we
assume that $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ does not have an infinite
NL tree.

For any integer $\ell\in\mathbb{N}$ and any universally measurable pattern
avoidance function
$g:\mathcal{X}^{\ell}\times[k]^{\ell}\times[k]^{\ell}\to\\{0,1\\}^{\ell}$, we
consider the error

$\mathrm{per}(g):=\mathrm{per}_{\ell}(g)=\mathop{\bf
Pr\/}_{(x_{1},y_{1},...,x_{\ell},y_{\ell})}[g\textnormal{ fails to avoid some
NL pattern realized by the data }x_{1},y_{1},...,x_{\ell},y_{\ell}]\,,$

i.e., there exist some colorings $s^{(0)},s^{(1)}$ everywhere different that
witness the pattern $g(x_{1},...,x_{\ell},s^{(0)},s^{(1)})$ with colors
$(y_{1},...,y_{\ell})$. The following lemma establishes this result. It
follows the approach in [BHM+21].

######  Lemma 7.

For the algorithm of Equation 1, it holds that

$\mathop{\bf Pr\/}[\mathrm{per}(\widehat{y}_{t})>0]\to 0\textnormal{ as
}t\to\infty\,,$

where the probability is over the random data that are used to train the
algorithm.

###### Proof.

As in the proof of the asymptotic result in the exponential rates, since the
distribution $P$ is realizable, we can get that the data sequence
$X_{1},Y_{1},X_{2},Y_{2},...$ is consistent with $\mathcal{H}$ almost surely.
We can now employ Lemma 6 and get that the random variable

$T=\sup\\{s\geq 1:\textnormal{the Pattern Avoidance Algorithm of
\lx@cref{creftypecap~refnum}{fig:pattern-algo} gets in the ``if''
statement}\\}$

is finite almost surely and $\widehat{y}_{s}=\widehat{y}_{t}$ and
$\ell_{s}=\ell_{t}$ for all $s\geq t\geq T$. We can apply the law of large
nymber for $m$-dependent sequences and get that the quantity $\mathop{\bf
Pr\/}[\mathrm{per}_{\ell_{t}}(\widehat{y}_{t})=0]$ is equal to

$\mathop{\bf
Pr\/}\left[\lim_{S\to\infty}\frac{1}{S}\sum_{s=t+1}^{t+S}1\\{\widehat{y}_{t}\textnormal{
fails to avoid some NL pattern realized by
}(X_{s},Y_{s},...,X_{s+\ell_{t}-1},Y_{s+\ell_{t}-1})\\}=0\right]\,.$

We can decrease the probability of the right-hand side by taking the
intersection of the right-hand side event with the event $\\{T\leq t\\}$.
Hence, we have that

$\mathop{\bf Pr\/}[\mathrm{per}_{\ell_{t}}(\widehat{y}_{t})=0]\geq\mathop{\bf
Pr\/}[T\leq t]\to 1,\textnormal{ as }t\to\infty\,,$

since $T$ is finite with probability one. ∎

####  3.3.4 Linear Learning Rates

Given some pattern avoidance function that is correct on _any_ tuple of size
$t$, we can essentially use the 1-inclusion graph in a similar manner as if
the Natarajan dimension of $\mathcal{H}$ was bounded by $t$. This is
established in the following lemma.

######  Lemma 8 (Learning NL pattern classes).

Fix $t\geq 1.$ Let
$g:\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}\to\\{0,1\\}^{t}$ be the
universally measurable NL pattern avoidance function of Figure 7. For any
$n\geq 1,$ there exists a universally measurable classifier
$\widehat{Y}^{g}_{n}:(\mathcal{X}\times[k])^{n-1}\times\mathcal{X}\to[k]$ such
that for every training set
$(x_{1},y_{1},...,x_{n},y_{n})\in(\mathcal{X}\times[k])^{n}$ where
$g(x_{i_{1}},...,x_{i_{t}},s^{(0)},s^{(1)})$ is an avoiding NL pattern for all
pairwise distinct indices $1\leq i_{1},...,i_{t}\leq n$ and everywhere
different colorings $s^{(0)},s^{(1)}$, the classifier achieves a linear
permutation bound, i.e.,

$\mathop{\bf
Pr\/}_{\sigma\sim\mathcal{U}(\mathbb{S}_{n})}\left[\widehat{Y}^{g}_{n}(x_{\sigma(1)},y_{\sigma(1)},...,x_{\sigma(n-1)},y_{\sigma(n-1)},x_{\sigma(n)})\neq
y_{\sigma(n)}\right]\leq\frac{t\log(k)}{n}\,.$

Note that the above algorithm is transductive. This hints the use of the one-
inclusion learning algortihm.

###### Proof.

Fix $n\geq 1$ and set $X=[n]$. Also let $F$ be a set of colorings $f:X\to[k]$.
We can apply the one-inclusion hypergraph algorithm (see Lemma 13) to get that
there exists an algorithm $\mathbb{A}$ such that

$\mathop{\bf
Pr\/}_{\sigma\sim\mathcal{U}(\mathbb{S}_{n})}[\mathbb{A}(F,\sigma(1),f(\sigma(1)),...,\sigma(n-1),f(\sigma(n-1)),\sigma(n))\neq
f(\sigma(n))]\leq\frac{\mathrm{Ndim}(F)\log(k)}{n}\,,$

for any coloring $f\in F$ and $F\in 2^{[k]^{X}}$. By construction of the
algorithm $\mathbb{A}$, the output of the mapping is preserved under
relabeling of $X$, i.e.,

$\mathbb{A}(F,\sigma(1),y_{1},...,\sigma(n-1),y_{n-1},\sigma(n))=\mathbb{A}(F\circ\sigma,1,y_{1},...,n-1,y_{n-1},n)\,,$

where $F\circ\sigma=\\{f\circ\sigma:f\in F\\}$. Moreover, the mapping
$\mathbb{A}$ is measurable since its domain is finite (since the number of
colors $k$ is a constant).

We will make use of the next result.

######  Claim 2.

Consider the pattern avoidance mapping
$g:\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}\to\\{0,1\\}^{t}$ of Figure 7.
Consider the class $F$ of $k$-colorings of $[n]$ and fix a sequence
$\bm{x}=(x_{1},...,x_{n})\in\mathcal{X}^{n}$. Fix $0<t\leq n$. Define the
subset $F_{\bm{x}}$ that contains the colorings $f:[n]\to[k]$ that satisfy the
following property: For all subsets $(i_{1},...,i_{t})$ of $[n]$ of size $t$
and for all colorings $s^{(0)},s^{(1)}:[n]\to[k]$ which are everywhere
different, at least one of the next $t$ conditions is violated:

$f(i_{j})=s^{(0)}(x_{i_{j}})\textnormal{ if
}g(x_{i_{1}},\ldots,x_{i_{t}},s^{(0)},s^{(1)})[x_{i_{j}}]=0\,,$
$f(i_{j})=s^{(1)}(x_{i_{j}})\textnormal{ if
}g(x_{i_{1}},\ldots,x_{i_{t}},s^{(0)},s^{(1)})[x_{i_{j}}]=1\,.$

Then, we have that $\mathrm{Ndim}(F_{\bm{x}})<t$.

###### Proof.

It must be the case that the Natarajan dimension cannot be more than $t-1$
since we cannot $N$-shatter any $t$-subset of $[n]$. ∎

Given any input sequence $(x_{1},y_{1},...,x_{n},y_{n})$, we introduce the
concept class $F_{x}$ as in 2. Moreover, consider the mapping
$g:\mathcal{X}^{t}\times[k]^{t}\times[k]^{t}\to\\{0,1\\}^{t}$ defined to be
the pattern avoidance function generated by Figure 7. We can introduce a data-
dependent classifier

$\widehat{Y}_{n}(g;x_{1},y_{1},...,x_{n-1},y_{n-1},x_{n})=\mathbb{A}(F_{x},1,y_{1},...,n-1,y_{n-1},n)\,.$

Note that the above mapping is universally measurable due to Lemma 6. By
relabeling we have that

$\widehat{Y}_{n}(g;x_{\sigma(1)},y_{\sigma(1)},...,x_{\sigma(n-1)},y_{\sigma(n-1)},x_{\sigma(n)})=\mathbb{A}(F_{x},\sigma(1),y_{\sigma(1)},...,\sigma(n-1),y_{\sigma(n-1)},\sigma(n))\,.$

By the assumption of the lemma about the input
$(x_{1},y_{1},...,x_{n},y_{n})$, we have that the coloring $y(i)=y_{i}\in[k]$
satisfies $y\in F_{x}$ (due to the construction of 2). Hence, for such a
sequence, we get that

$\mathop{\bf
Pr\/}_{\sigma\sim\mathcal{U}(\mathbb{S}_{n})}\left[\widehat{Y}^{g}_{n}(x_{\sigma(1)},y_{\sigma(1)},...,x_{\sigma(n-1)},y_{\sigma(n-1)},x_{\sigma(n)})\neq
y_{\sigma(n)}\right]\leq\frac{\mathrm{Ndim}(F_{x})\log(k)}{n}\,.$

However, due to the conclusion of 2, we have that the above rate is of order
$\log(k)\cdot t/n$, since by construction $\mathrm{Ndim}(F_{x})<t$. ∎

To make use of the results we just stated, we need to come up with a pattern
avoidance function that is correct on _any_ tuple of size $t$. However, we can
only establish that our pattern avoidance function is _eventually_ correct, so
there is no bound on $t$ that is given to the learner. To deal with this
problem, we keep track of some $\widehat{t}_{n}$ such that, with high
probability, the error of the pattern avoidance function is small. Then, we
divide our sample into $n/\widehat{t}_{n}$ batches of size $\widehat{t}_{n}$.
For each batch $i$ we generate some pattern avoidance function $g^{i}$, whose
error probability is small. To achieve the linear rates we run the algorithm
from Lemma 8 for every different batch $i$ and function $g^{i}$ to get a
classifier $\widehat{h}^{i}$. We output the majority vote of the classifiers
$\widehat{h}^{i}$.

######  Lemma 9.

For any $n\in\mathbb{N}$, Consider a training set $\\{(X_{i},Y_{i})\\}$
consisting of $n$ points i.i.d. drawn from $P$. Then there exists a
universally measurable
$\widehat{t}_{n}=\widehat{t}_{n}(X_{1},Y_{1},...,X_{\lfloor
n/2\rfloor},Y_{\lfloor n/2\rfloor})$ whose definition does not depend on $P$
so that the following holds. Set the critical time $t^{\star}\in\mathbb{N}$ be
such that

$\mathop{\bf Pr\/}[\mathrm{per}(\widehat{y}_{t^{\star}})>0]\leq 1/8\,,$

where the probability is over the training set of the algorithm
$\widehat{y}_{t}$. Then, there exist $C,c>0$ that depend on $P,t^{\star}$ but
not $n$ so that

$\mathop{\bf Pr\/}[\widehat{t}_{n}\in T^{\star}]\geq 1-Ce^{-cn}\,.$

where the probability is over the training of the estimator $\widehat{t}_{n}$
and $T^{\star}$ is the set

$T^{\star}=\left\\{1\leq t\leq t^{\star}:\mathop{\bf
Pr\/}[\mathrm{per}(\widehat{y}_{t^{\star}})>0]\leq 3/8\right\\}\,,$

where the probability is over the training of $\widehat{y}_{t}$.

For the proof of the above lemma, see Section C.7. We continue with the main
result of this section.

######  Theorem 12 (Linear Rates).

Assume that class $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ does not have an
infinite Natarajan-Littlestone tree. Then, $\mathcal{H}$ admits a learning
algorithm that achieves an optimal linear rate.

###### Proof.

The learning algorithm works as follows: It first computes the estimate
$\widehat{t}_{n}$ introduced in Lemma 9. Then it splits the data into two
halves: the first half is used to compute the pattern avoidance functions
$g^{i}:=\widehat{y}^{i}_{\widehat{t}_{n}}$ for $1\leq i\leq\lfloor
n/(4\widehat{t}_{n})\rfloor$ and the second half is used in order to apply
Lemma 8 and get classifiers $\widehat{y}^{i}$ with
$\widehat{y}^{i}(x):=\widehat{Y}^{g^{i}}_{\lfloor n/2\rfloor+2}(X_{\lceil
n/2\rceil},Y_{\lceil n/2\rceil},...,X_{n},Y_{n},x)$. Finally, the algorithm
outputs

$\widehat{h}_{n}=\mathrm{Maj}\left(\widehat{y}^{1},\widehat{y}^{2},...,\widehat{y}^{\lfloor
n/(4\widehat{t}_{n})\rfloor}\right)\,.$

and aims to get $\mathop{\bf E\/}[\mathop{\bf
Pr\/}_{(X,Y)}[\widehat{h}_{n}(X)\neq Y]]\leq C/n$ for some constant $C$, where
the expectation is over the training set used for the predescribed steps. Set
$\widehat{N}=\lfloor n/(4\widehat{t}_{n})\rfloor$ and $N^{\star}=\lfloor
n/(4t^{\star})\rfloor$. With the notation of Lemma 9, we get

$\mathop{\bf
Pr\/}\left[\frac{1}{\widehat{N}}\sum_{i\in[\widehat{N}]}\bm{1}\\{\mathrm{per}(\widehat{y}^{i}_{\widehat{t}_{n}})>0\\}>\frac{1}{100k},\widehat{t}_{n}\in
T^{\star}\right]\leq t^{\star}\exp(-C_{1}\cdot N^{\star})\,,$

i.e., the strict majority of the pattern avoidance functions have zero error
with high probability where $C_{1}$ is a fixed constant depending on the
(uniformly bounded) number of labels $k\in\mathbb{N}$. Using Lemma 9, we get

$\displaystyle\mathop{\bf E\/}[\mathop{\bf Pr\/}[\widehat{h}_{n}(X)\neq Y]]$
$\displaystyle\leq\mathop{\bf
Pr\/}\left[\mathrm{Maj}\left(\widehat{y}^{1}(X),\widehat{y}^{2}(X),...,\widehat{y}^{\lfloor
n/(4\widehat{t}_{n})\rfloor}(X)\right)\neq Y\right]$ $\displaystyle\leq
C\exp(-cn)+t^{\star}\exp(-C_{1}\cdot n^{\star})+p\,,$

where

$p=\mathop{\bf Pr\/}\left[\widehat{t}_{n}\in
T^{\star},\sum_{i\in[\widehat{N}]}\bm{1}\\{\mathrm{per}(\widehat{y}^{i}_{\widehat{t}_{n}})=0\\}\geq(100k-1)\widehat{N}/(100k),\mathrm{Maj}\left(\widehat{y}^{1}(X),\widehat{y}^{2}(X),...,\widehat{y}^{\lfloor
n/(4\widehat{t}_{n})\rfloor}(X)\right)\neq Y\right]\,.$

We have that

$\mathop{\bf
Pr\/}\left[\mathrm{Maj}\left(\widehat{y}^{1}(X),\widehat{y}^{2}(X),...,\widehat{y}^{\lfloor
n/(4\widehat{t}_{n})\rfloor}(X)\right)\neq Y\right]\leq\mathop{\bf
Pr\/}\left[\sum_{i\in[\widehat{N}]}\bm{1}\\{\widehat{y}^{i}(X)\neq
Y\\}\geq\widehat{N}/k\right]\,,$

since whenever the majority makes a mistake, the right-hand side event occurs.
Since $k$ is a fixed constant, any two sets containing at least $1/k$ and
$1-1/(100k)$ fractions of $\\{1,2,...,\lceil n/\widehat{t}_{n}\rceil\\}$, must
have at least a $\Theta(1)$ fraction in their intersection. Hence, we get that

$p\leq\mathop{\bf Pr\/}\left[\widehat{t}_{n}\in
T^{\star},\frac{1}{\widehat{N}}\sum_{i\in[\widehat{N}]}\bm{1}\\{\widehat{y}^{i}(X)\neq
Y\\}\cdot\bm{1}\\{\mathrm{per}(\widehat{y}^{i}_{\widehat{t}_{n}})=0\\}\geq\Theta(1)\right]$

and using Markov’s inequality

$p\leq\Theta(1)\cdot\mathop{\bf
E\/}\left[\frac{1}{\widehat{N}}\sum_{i\in[\widehat{N}]}\bm{1}\\{\widehat{t}_{n}\in
T^{\star}\\}\cdot\bm{1}\\{\widehat{y}^{i}(X)\neq
Y\\}\cdot\bm{1}\\{\mathrm{per}(\widehat{y}^{i}_{\widehat{t}_{n}})=0\\}\right]$

We can now apply Lemma 8 conditionally on the first half of the data and get

$\mathop{\bf E\/}[\mathop{\bf Pr\/}[\widehat{h}_{n}(X)\neq Y]]\leq
C\exp(-cn)+t^{\star}\exp(-n^{\star}/128)+\Theta(1)\cdot\log(k)\cdot\mathop{\bf
E\/}\left[\bm{1}\\{\widehat{t}_{n}\in
T^{\star}\\}\cdot\frac{1}{\widehat{N}}\sum_{i\in[\widehat{N}]}\frac{\ell^{i}_{\widehat{t}_{n}}}{\lfloor
n/2\rfloor+2}\right]\,.$

Now we have that $\Theta(1)\log(k)=\Theta(1)$ and
$\ell^{i}_{\widehat{t}_{n}}\leq\widehat{t}_{n}+1\leq t^{\star}+1$, since
$\widehat{t}_{n}\in T^{\star}$. This gives

$\mathop{\bf E\/}[\mathop{\bf Pr\/}[\widehat{h}_{n}(X)\neq Y]]\leq C/n\,.$

∎

###  3.4 Arbitrarily Slow Rates

The last step that is needed to establish the characterization of learnability
in the multiclass setting is to show that if $\mathcal{H}$ has an infinite
Natarajan Littlestone tree it is learnable at an arbitrarily slow rate. The
following theorem establishes that. The idea of the proof is similar as in the
setting with the infinite multiclass Littlestone tree. Intuitively, the reason
that in this regime we get arbitrarily slow rates whereas in the other one we
get linear rates is that the branching factor now is _exponential_ in the
depth of the tree, whereas before it remained constant.

######  Theorem 13.

Assume that $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ has an infinite Natarajan-
Littlestone tree. Then, any algorithm that learns $\mathcal{H}$ requires
arbitrarily slow rates. Moreover, there exists an algorithm that learns
$\mathcal{H}$ at an arbitrarily slow rate.

###### Proof.

The desired algorithm that learns $\mathcal{H}$ is provided by [HKSW20]. For
the proof of the lower bound, fix a vanishing rate $R(t)\to 0$, fix any
learning algorithm $\widehat{h}_{n}$ for $\mathcal{H}$ and let $\\{x_{u}\\}$
be an infinite NL tree for $\mathcal{H}$. Consider a random branch of the tree
$y=(y_{1},y_{2},...)$ where the pattern
$y_{\ell}=(y_{\ell}^{0},...,y_{\ell}^{\ell-1})\in\\{0,1\\}^{\ell}$ is chosen
uniformly at random from the $\ell$-dimensional Boolean hypercube for any
$\ell\in\mathbb{N}$. Fix a finite level $n\in\mathbb{N}$. By the structure of
the NL tree, we know that there exist two different colorings $s_{1},s_{2}$
and a hypothesis $h\in\mathcal{H}$ so that $h$ agrees either with $s_{1}$ if
the pattern bit says 1 or with $s_{2}$ otherwise. Our first goal in this
universal lower bound is to construct a realizable distribution. We define the
random distribution that assigns non-zero mass to the points of the branch $y$
with labels consistent with $h$, i.e.,

$P_{y}((x^{i}_{y\leq\ell-1},h(x^{i}_{y\leq\ell-1})))=\frac{p_{\ell}}{\ell}\textnormal{
for }~{}0\leq i<\ell,\ell\in\mathbb{N}\,,$

where $p_{\ell}$ is a sequence of probabilities so that
$\sum_{\ell\in\mathbb{N}}p_{\ell}=1$ that we will select later in the proof.
Intuitively, the distribution $P_{y}$ chooses the node of the infinite branch
at level $\ell$ with probability $p_{\ell}$; this node contains $\ell$ points
of $\mathcal{X}$ and one of them is chosen uniformly at random.

By the structure of the infinite NL tree, we get that such a labeling
$h\in\mathcal{H}$ exists for any level $n\in\mathbb{N}$ and this labeling is
consistent with all the previous levels $1\leq n^{\prime}<n$. Thus, we get
that

$\mathop{\bf Pr\/}_{(x,z)\sim P_{y}}[h(x)\neq z]\leq\sum_{\ell>n}p_{\ell}\,.$

Hence, as $n\to\infty$, we get that $P_{y}$ is realizable for any realization
of the random branch $y$. Moreover, the mapping $y\to P_{y}$ is measurable.

We now have to lower bound the loss of the potential learner $\widehat{h}_{n}$
using the probability measure $P_{y}$. Let
$(X,Z),(X_{1},Z_{1}),(X_{2},Z_{2}),...\in(\mathcal{X}\times[k])^{\infty}$ be a
collection of i.i.d. samples from $P_{y}$. Equivalently, we can write

  1. 1.

$X=x^{I}_{y\leq T-1}$ and $Z=z^{I}_{T}$ for two random variables $(T,I)$ with
joint distribution $\mathop{\bf Pr\/}[T=\ell,I=i]=\frac{p_{\ell}}{\ell}$ for
$0\leq i<\ell,\ell\in\mathbb{N}$.

  2. 2.

For $j\in\mathbb{N}$, set $X_{j}=x^{I_{j}}_{y\leq T_{j}-1}$ and
$Z_{j}=z^{I_{j}}_{T_{j}}$ for two random variables $(T_{j},I_{j})$ with joint
distribution $\mathop{\bf Pr\/}[T_{j}=\ell,I_{j}=i]=\frac{p_{\ell}}{\ell}$ for
$0\leq i<\ell,\ell\in\mathbb{N}$.

We underline that in the above the random variables
$(T,I),(T_{1},I_{1}),(T_{2},I_{2})$ are i.i.d. and independent of the random
branch $y$. Our goal is to lower bound the error of any learning algorithm:
For all $n$ and $\ell$,

$\mathop{\bf Pr\/}[\widehat{h}_{n}(X)\neq
Z,T=\ell]\geq\sum_{i=0}^{\ell-1}\mathop{\bf
Pr\/}[\widehat{h}_{n}(x^{i}_{y\leq\ell-1})\neq
z_{\ell}^{i},T=\ell,I=i,T_{1},...,T_{n}\leq\ell,(T_{1},I_{1}),...,(T_{n},I_{n})\neq(\ell,i)]\,,$

where in the right hand side the probability is decreased by additionally
requiring that the whole training set is concentrated before the level
$\ell+1$ and the testing example is not contained in the training set.
Consider this event
$E_{n,\ell,i}=\\{T=\ell,I=i,T_{1},...,T_{n}\leq\ell,(T_{1},I_{1}),...,(T_{n},I_{n})\leq(\ell,i)\\}$.
If we condition on $E_{n,\ell,i}$, we have that the prediction of
$\widehat{h}_{n}(X)=\widehat{h}_{n}(x^{i}_{y\leq\ell-1})$ is independent of
the label $z_{\ell}^{i}$. Hence, we have that

$\mathop{\bf Pr\/}[\widehat{h}_{n}(X)\neq
Z,T=\ell]\geq\sum_{i=0}^{\ell-1}\mathop{\bf
Pr\/}[\widehat{h}_{n}(x^{i}_{y\leq\ell-1})\neq
z_{\ell}^{i}|E_{n,\ell,i}]\mathop{\bf
Pr\/}[E_{n,\ell,i}]\geq\frac{1}{2}\sum_{i=0}^{\ell-1}\mathop{\bf
Pr\/}[E_{n,\ell,i}]\,.$

By the choice of the randomness over $T,I,T_{1},I_{1},...$, we get that

$\mathop{\bf Pr\/}[\widehat{h}_{n}(X)\neq
Z,T=\ell]\geq\frac{p_{\ell}}{2}\left(1-\sum_{m>\ell}p_{m}-\frac{p_{\ell}}{\ell}\right)^{n}\,.$

To conclude the proof we have to choose the sequence of probabilities
$(p_{\ell})$ and relate it to the vanishing rate $R$. By combining Lemma 5.12
of [BHM+21] and by applying the reverse Fatou’s lemma (see e.g., the end of
the proof of Theorem 5.11 of [BHM+21]), the proof is concluded. ∎

###  3.5 A Sufficient Condition for Linear Rates for Multiclass Learning

Another approach to come up with an algorithm that works in the multiclass
setting is to use the algorithm that was developed in [BHM+21] for the binary
setting. Towards this end, we define a slightly different combinatorial
measure for a class $\mathcal{H}$.

######  Definition 8.

A Graph-Littlestone (GL) tree for $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ of
depth $d\leq\infty$ consists of a tree

$\bigcup_{0\leq\ell<d}\\{x_{u}\in\mathcal{X}^{\ell+1},u\in\\{0,1\\}\times\\{0,1\\}^{2}\times...\times\\{0,1\\}^{\ell}\\}$

and a coloring $s$ mapping each position $u^{i}\in u$ for any node with
pattern $u\in\\{0,1\\}\times...\times\\{0,1\\}^{\ell}$ for
$i\in\\{0,1,...,\ell\\}$ and $\ell\in\\{0,1,...,d-1\\}$ of the tree to some
color $\\{0,1,...,k\\}$ such that for every finite level $n<d$, the subtree
$T_{n}=\cup_{0\leq\ell\leq
n}\\{x_{u}:u\in\\{0,1\\}\times\\{0,1\\}^{2}\times...\times\\{0,1\\}^{\ell}\\}$
satisfies the following:

  1. 1.

For any path $\bm{y}\in\\{0,1\\}\times...\times\\{0,1\\}^{n+1}$, there exists
a concept $h\in\mathcal{H}$ so that
$h(x^{i}_{\bm{y}_{\leq\ell}})=s(x^{i}_{\bm{y}_{\leq\ell}})$ if
$y^{i}_{\ell+1}=1$ and $h(x^{i}_{\bm{y}_{\leq\ell}})\neq
s(x^{i}_{\bm{y}_{\leq\ell}})$ otherwise, for all $0\leq i\leq\ell$ and
$0\leq\ell\leq n$, where

$\bm{y}_{\leq\ell}=(y_{1}^{0},(y_{2}^{0},y_{2}^{1}),...,(y_{\ell}^{0},...,y_{\ell}^{\ell-1})),x_{\bm{y}_{\leq\ell}}=(x^{0}_{\bm{y}_{\leq\ell}},...,x^{\ell}_{\bm{y}_{\leq\ell}})\,.$

We say that $\mathcal{H}$ has an infinite GL tree if it has a GL tree of depth
$d=\infty$.

We note that in the above definition we identify the color
$s(x^{i}_{\bm{y}\leq\ell})$ with the (unique) position of this point
$x^{i}_{\bm{y}\leq\ell}$ (since typically the coloring is over positions). One
can again verify that if $\mathcal{H}$ has an infinite GL tree, then it has an
infinite multiclass Littlestone tree. We show that if a class $\mathcal{H}$
does not have an infinite GL tree, then it is possible to learn $\mathcal{H}$
at a linear rate. The proof of this statement is via a reduction to the binary
setting. In fact, we invoke the well-studied “one versus all” approach, where
we are trying to learn $k$ different classes $\mathcal{H}_{i}$ that
distinguish between points that belong to the $i$-th class and points that
belong to some class $j\neq i$.

######  Theorem 14.

Assume that $\mathcal{H}\subseteq[k]^{\mathcal{X}}$ does not have an infinite
Graph-Littlestone tree. Then, there exists an algorithm that learns
$\mathcal{H}$ at a linear rate.

###### Proof.

Consider $k$ binary classes $\mathcal{H}_{i}$ induced by the hypothesis class
$\mathcal{H}$ where $\mathcal{H}_{i}=\\{x\mapsto
1\\{h(x)=i\\}:h\in\mathcal{H}\\}$, i.e., for
$h\in\mathcal{H},\widetilde{h}\in\mathcal{H}_{i}$ we have that
$\widetilde{h}(x)=1$ if and only if $h(x)=i$.

######  Claim 3.

Assume that $\mathcal{H}$ does not have an infinite GL tree. Then for any
$i\in[k]$ the class $\mathcal{H}_{i}$ is learnable at a linear rate.

###### Proof.

Fix $i\in[k]$. It suffices to show that the class $\mathcal{H}_{i}$ does not
have an infinite VCL tree (VCL trees are introduced in [BHM+21] and,
intuitively, a VCL tree is a GL tree with $k=1$ and $s=1$ everywhere). Towards
contradiction, assume that $\mathcal{H}_{i}$ admits an infinite VCL tree
$\mathcal{T}=\\{x_{u}\\}$. We can construct the following Graph-Littlestone
tree: we use the same nodes as in $\mathcal{T}$ and for any node in the tree
we use the coloring that colors each point with the color $i$. Fix an
arbitrary level $n$ and a path $y$. We know that there exists a binary
hypothesis $\widetilde{h}\in\mathcal{H}_{i}$ that realizes this path in the
VCL tree. Due to the construction of the class $\mathcal{H}_{i}$, we have that
there exists a mapping $h\in\mathcal{H}$ (where
$\widetilde{h}=1\\{h(\cdot)=i\\})$ that realizes the path in the constructed
tree. This property holds for any path and any level. Hence, we have
constructed an infinite GL tree for $\mathcal{H}$ which yields a
contradiction. ∎

Assume that we get $k$ binary classifiers $\widehat{h}_{n}^{(i)}$, one for
each class $\mathcal{H}_{i}$. Finally, we set
$\widehat{h}_{n}(x)=\operatorname*{argmax}_{i}\widehat{h}_{n}^{i}(x)$ for any
$x\in\mathcal{X}$. The above claim concludes the proof since

$\mathop{\bf E\/}\mathop{\bf Pr\/}_{(x,y)\sim P}[\widehat{h}_{n}(x)\neq
y]=\mathop{\bf E\/}\mathop{\bf Pr\/}_{(x,y)\sim P}[\exists