Steve<EMAIL_ADDRESS>
Department of Computer Science, Purdue University and Shay
<EMAIL_ADDRESS>
Departments of Mathematics, Computer Science, Data and Decision Sciences,
Technion, and Google Research and Tom<EMAIL_ADDRESS>
Department of Mathematics, Technion

# List Sample Compression and Uniform Convergence

###### Abstract

List learning is a variant of supervised classification where the learner
outputs multiple plausible labels for each instance rather than just one. We
investigate classical principles related to generalization within the context
of list learning. Our primary goal is to determine whether classical
principles in the PAC setting retain their applicability in the domain of list
PAC learning. We focus on uniform convergence (which is the basis of Empirical
Risk Minimization) and on sample compression (which is a powerful
manifestation of Occam’s Razor). In classical PAC learning, both uniform
convergence and sample compression satisfy a form of ‘completeness’: whenever
a class is learnable, it can also be learned by a learning rule that adheres
to these principles. We ask whether the same completeness holds true in the
list learning setting.

We show that uniform convergence remains equivalent to learnability in the
list PAC learning setting. In contrast, our findings reveal surprising results
regarding sample compression: we prove that when the label space is
$\mathcal{Y}=\\{0,1,2\\}$, then there are 2-list-learnable classes that cannot
be compressed. This refutes the list version of the sample compression
conjecture by [Littlestone and Warmuth (1986)]. We prove an even stronger
impossibility result, showing that there are $2$-list-learnable classes that
cannot be compressed even when the reconstructed function can work with lists
of arbitrarily large size. We prove a similar result for (1-list) PAC
learnable classes when the label space is unbounded. This generalizes a recent
result by [Pabbaraju (2023)].

In our impossibility results on sample compression, we employ direct-sum
arguments which might be of independent interest. In fact, these arguments
raise natural open questions that we leave for future research. Our findings
regarding uniform convergence rely on a coding theoretic perspective.

##  1 Introduction

List learning is a natural generalization of supervised classification, in
which, instead of predicting the correct label, the learner outputs a small
list of labels, one of which should be the correct one. This approach can be
viewed as giving the learner more than one guess at the correct label.

There are many settings in which one may prefer the list learning approach to
the classical one. For example, recommendation systems often suggest a short
list of products to users, with the hope that the customer will be interested
in one of them (see Figure 1).

Figure 1: Amazon recommendation system gives their users a short list of books
based on their past reading, aiming that one of those books will capture their
interest.

Another example is the top-$k$ loss function in which the model gets $k$
guesses for each sample. This loss function is often used in ML competitions
and can be seen as a variant of list learning. Additionally, list learning
addresses label ambiguity; for example, in computer vision recognition
problems, it is often impossible to determine if a certain image is of a pond
or a river. As a result, training a model for such problems by penalizing it
for every mistake can be too restrictive. However, using a top-$k$ approach
seems like a reasonable alternative. This approach has been studied in recent
works such as Lapin, Hein, and Schiele (2015) and Yan, Luo, Liu, Li, and Zheng
(2018), which demonstrate its usefulness in certain problems.

List learning has also found applications in theoretical machine learning. For
example in Brukhim, Carmon, Dinur, Moran, and Yehudayoff (2022) it was an
essential part of establishing the equivalence between finite Daniely-Shwartz
(DS) dimension and multiclass learnability. Consequently, list learning has
been studied in several recent works in learning theory. For example, Charikar
and Pabbaraju (2022) characterized list PAC learnability by using a list
variant of the DS dimension, and Moran, Sharon, Tsubari, and Yosebashvili
(2023) characterized list online learnability using a list variant of the
Littlestone dimension. Another recent application of list learning is in the
realm of multiclass boosting; Brukhim, Hanneke, and Moran (2023) employed it
to devise the first boosting algorithm whose sample complexity is independent
of the label space’s size.

A natural question that has not yet been systematically addressed is the
identification of fundamental principles in list PAC learning. In the binary
case, PAC learning is guided by fundamental algorithmic principles, notably
Empirical Risk Minimization, and Occam’s Razor principles such as compression
bounds. In this work, we ask which of these foundational principles remains
applicable in the domain of list learning.

###  1.1 Our Contribution

In this section we summarize our main results. It is based on natural
adaptations of basic learning theoretic definitions to the list setting. These
definitions are fully stated in Section 2.

####  1.1.1 Sample Compression

##### Occam’s Razor.

Occam’s razor is a philosophical principle applied broadly across disciplines,
including machine learning. It suggests that among competing hypotheses, the
simplest one should be selected. In machine learning, this principle is often
quantified in terms of the number of bits required to encode an hypothesis,
thereby serving as a guideline for preferring simpler models. This concept
forms the basis of a general approach in machine learning, where simplicity is
directly linked to the efficiency and effectiveness of learning algorithms.

A more refined manifestation of Occam’s razor in machine learning is evident
in sample compression schemes. These schemes go beyond merely considering the
bit-size of an hypothesis. They involve an additional use of a small,
representative subset of input examples to encode hypotheses. This approach is
a more nuanced application of the principle, allowing for both the
simplification of data and the preservation of its essential characteristics.
In fact, while the classical interpretation of Occam’s razor, based on bit-
encoding, is sound — implying generalization — it lacks completeness. This
means that there exist learnable classes whose learnability cannot be
demonstrated solely through bit-encoding (see Figure 2)111Figures 2 and 3 from
Alon, Hanneke, Holzman, and Moran (2021), used with permission.. In contrast,
sample compression schemes offer a more comprehensive manifestation of Occam’s
razor: every PAC learnable class can be effectively learned by a sample
compression algorithm (David, Moran, and Yehudayoff, 2016).

Support Vector Machine

Figure 2: Support Vector Machine (SVM) as sample compression: The SVM
algorithm identifies a maximum-margin separating hyperplane, which is defined
by a subsample of $d+1$ support points. This exemplifies a concept class which
cannot be learned with hypotheses specified by finite bit-encoding, yet for
which there is an algorithm which learns effectively using hypotheses
specified using a bounded number of input-examples.

##### List Sample Compression Schemes.

Sample compression schemes were initially developed by Littlestone and Warmuth
(1986) for the purpose of proving generalization bounds; however, they can
also be interpreted as a standalone mathematical model for _data
simplification_. Sample compression resembles a scientist who collects
extensive experimental data but then selects only a crucial, representative
subset from it. From this subset, a concise hypothesis is formulated that
effectively explains the entire dataset. This analogy highlights the essence
of sample compression: distilling a complex dataset into a simpler form, while
maintaining the capacity to accurately explain the patterns and phenomena of
the entire original dataset.

More formally, a compression scheme consists of a pair of functions: a
_compressor_ and a _reconstructor_. The compressor gets an input sample of
labeled examples $S$ and uses it to construct a small subsequence of labeled
examples $S^{\prime}$ which she sends to the reconstructor. The reconstructor
uses $S^{\prime}$ to generate an concept $h$. The goal is that $h$ will be
consistent with the original sample $S$, even on examples that did not appear
in $S^{\prime}$ (see Figure 3)foot:figures.

We extend the notion of sample compression to the list setting naturally by
changing the concept $h$ outputted by the reconstructor to be a $k$-list map.
Now the goal is that $h$ will be consistent with $S$ in the sense that for any
example $x$, its label will be one of the $k$ elements of the list $h(x)$. In
more detail, a concept class $\mathcal{C}$ is $k$-list compressible if there
exists a $k$-list sample compression scheme with a finite size such that
whenever the input sample $S$ is realizable222I.e. there exists
$c\in\mathcal{C}$ such that $c(x_{i})=y_{i}$ for all $(x_{i},y_{i})\in S$ by
$\mathcal{C}$ then the reconstructed $k$-list concept $h$ satisfies $y_{i}\in
h(x_{i})$ for all $(x_{i},y_{i})\in S$. We refer to Section 2.2 for more
details.

A pictorial definition of a sample compression scheme

Reconstructor Compressor $S^{\prime}$$S$input sample$h$output concept

Figure 3: An illustration of a sample compression scheme: $S^{\prime}$ is a
subsample of $S$; the output concept $h$ should be consistent with the entire
input sample $S$. In the context of $k$-list sample compression, the concept
$h$ assigns a list of $k$ possible labels to each data point $x$. The
objective is refined such that for every input example $(x_{i},y_{i})$, the
actual label $y_{i}$ is included within the list provided by $h(x_{i})$.

In their original paper Littlestone and Warmuth (1986) showed that sample
compression schemes are PAC learners, and conjectured that every PAC learnable
class admits a sample compression scheme. Moran and Yehudayoff (2016)
confirmed this conjecture in the binary setting, and David et al. (2016)
further showed that any PAC learnable class over a finite label space admits a
sample compression scheme. It is therefore natural to ask whether the analogue
of Littlestone and Warmuth (1986) conjecture holds in the list setting:

_Does every $k$-list learnable class has a finite $k$-list sample compression
scheme?_

Our first result provides a negative answer in the simplest list PAC learning
setting: $2$-list learning a $3$-label space:

######  Theorem 1.1 (List-Learnability vs. List-Compressibility).

There exists a concept class $\mathcal{C}$ over the label space
$\mathcal{Y}=\\{0,1,2\\}$ such that:

  * •

$\mathcal{C}$ is $2$-list PAC learnable.

  * •

$\mathcal{C}$ has no finite $2$-list sample compression scheme.

##### Reconstruction with Larger Lists.

The class $\mathcal{C}$ in Theorem 1.1 is trivially $3$-list compressible:
simply take the reconstructed concept $h$ be such that $h(x)=\\{0,1,2\\}$ for
every $x$. In a related and recent result, Pabbaraju (2023) considers the
setting of multiclass PAC learning over an infinite label space and
establishes the existence of a concept class $\mathcal{C}$ that is (1-list)
PAC learnable but not (1-list) compressible. Also in his construction, the
class $\mathcal{C}$ is trivially $2$-list compressible. These examples raise
the following question:

_Does every $k$-list PAC learnable class $\mathcal{C}$ admit a $(k+1)$-list
sample compression scheme? _

We not only answer this question in the negative but also prove a
significantly stronger result. We demonstrate the existence of learnable
classes that are not $k$-compressible for any arbitrarily large $k$:

######  Theorem 1.2.

[$2$-Learnability vs $k$-Compressibility] For any $k>0$ there exists a concept
class $\mathcal{C}_{k}$ over a finite label space $\mathcal{Y}_{k}$ that
satisfies the following:

  1. 1.

$\mathcal{C}_{k}$ is $2$-list PAC learnable.

  2. 2.

$\mathcal{C}_{k}$ has no finite $k$-list sample compression scheme.

######  Theorem 1.3.

[$1$-Learnability vs $k$-Compressibility] For any $k>0$ there exists a concept
class $\mathcal{C}_{k}$ satisfying the following:

  1. 1.

$\mathcal{C}_{k}$ is PAC learnable. (I.e. $1$-list PAC learnable)

  2. 2.

$\mathcal{C}_{k}$ has no finite $k$-list sample compression scheme.

Note that by David, Moran, and Yehudayoff (2016) the label space of the class
in Theorem 1.3 is inevitably infinite and that the case $k=1$ gives the
aforementioned result of Pabbaraju (2023). Additionally, a close examination
of the proofs for these theorems reveals that in both scenarios, the
respective classes lack a compression scheme of size $f(n)$ for any function
$f(n)=o(\log n)$.

The proof of Theorem 1.1 is based on a construction from Alon, Hanneke,
Holzman, and Moran (2021) of a learnable partial concept class which is not
compressible. This is similar to how Pabbaraju (2023) derives a non
compressible PAC learnable class over an infinite label space; however, the
argument is somewhat more involved because Theorem 1.1 provides a consturction
over a finite label space, whereas in Pabbaraju (2023) the label space is
inevitably infinite. The proofs of Theorem 1.2 and Theorem 1.3 are by
induction on $k$, where the base case reduces to the partial concept class
construction from Alon et al. (2021). The induction step, however, requires
new ideas and will use direct sum arguments that we develop in the full
version of this paper and overview in Section 1.1.3. We give a more detailed
review of the proof method in Section 3.1.

####  1.1.2 Uniform Convergence

Uniform convergence and empirical risk minimization (ERM) are arguably the
most extensively studied algorithmic principles for generalization in machine
learning. For example, the Fundamental Theorem of PAC Learning for binary
classification states the equivalence between PAC learnability, uniform
convergence, and the ERM principle (Shalev-Shwartz and Ben-David, 2014). In
fact, the equivalence between uniform convergence and PAC learnability holds
whenever the label space is finite (Shalev-Shwartz, Shamir, Srebro, and
Sridharan, 2010). Moreover, ERM is closely related to other statistical
principles such as maximum likelihood estimation.

Informally, uniform convergence refers to the phenomenon where, given a
sufficiently large sample from a population, the empirical losses of all
concepts in a class closely approximate their true losses over the entire
population. This phenomenon forms the basis of the Empirical Risk Minimization
principle. It posits that selecting a concept in the class that minimizes
empirical loss is a sound strategy, as such a concept is also likely to
approximately minimize the population loss.

In the context of list learning, we consider classes $\mathcal{C}$ of $k$-list
concepts. So, each $c\in\mathcal{C}$ assigns a list of $k$ labels to each
point $x\in\mathcal{X}$. For a target distribution $\mathcal{D}$ over
$\mathcal{X}\times\mathcal{Y}$, the population loss of $c$ is
$\mathtt{L}_{\mathcal{D}}(c)=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[1_{y\notin
c(x)}]$ and for a sample $S=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, the empirical loss
of $c$ is $\mathtt{L}_{S}(c)=\frac{1}{n}\sum_{i=1}^{n}1[y_{i}\notin
c(x_{i})]$. We investigate when $k$-list concept classes exhibit uniform
convergence and ask whether a parallel to the Fundamental Theorem of PAC
Learning exists in this setting.

_Does the equivalence between PAC learning and uniform convergence extend to
$k$-list concept classes?_

We confirm this is the case, providing an affirmative response to these
questions, though via a novel analysis deviating significantly from the
traditional approach (as outlined below). Please see Section 2.1 for the
definitions of PAC learnability and uniform convergence, adapted to the list
learning setting.

######  Theorem 1.4 (List Learnability vs. Uniform Convergence).

Let $\mathcal{C}\subset{\mathcal{Y}\choose k}^{\mathcal{X}}$ be a $k$-list
concept class over a finite label space $\lvert\mathcal{Y}\rvert<\infty$.
Then, the following properties are equivalent:

  * •

$\mathcal{C}$ is $k$-list PAC learnable.

  * •

$\mathcal{C}$ is $k$-list agnostically PAC learnable.

  * •

$\mathcal{C}$ satisfies the uniform convergence property.

In Theorem 5.3 in Section 5 we also provide quantitative bounds on the uniform
convergence rate. These bounds follow from analyzing the $\mathtt{DS}_{k}$
dimension (which controls the learning rate) and the graph dimension (which
controls the uniform convergence rate); see Section 2 for further details. In
particular, our result implies
$\mathtt{DS}_{k}(\mathcal{C})=\tilde{\Omega}\bigl{(}\frac{\mathtt{G}_{k}(\mathcal{C})}{k\cdot\log(\lvert\mathcal{Y}\rvert\cdot\mathtt{G}_{k})}\bigr{)}$.
This implies the following upper bound on the uniform convergence rate:

$\displaystyle\varepsilon(n|\mathcal{C})=\tilde{O}\Biggl{(}\sqrt{\frac{k\cdot\mathtt{DS}_{k}(\mathcal{C})\cdot\log(\lvert\mathcal{Y}\rvert\cdot\mathtt{DS}_{k}(\mathcal{C}))}{n}}\Biggr{)}.$

This finding extends the ERM principle in the realm of list learning: for any
class of $k$-list concepts that is $k$-list learnable, an effective learning
strategy is to choose a concept from the class that minimizes the empirical
loss.

The assumption that the label space $\mathcal{Y}$ is finite is necessary.
Indeed, Daniely, Sabato, Ben-David, and Shalev-Shwartz (2015) demonstrate that
already in the case of $k=1$, there are PAC learnable classes that do not
satisfy uniform convergence.

The proof of Theorem 1.4 deviates from the classical approaches to deriving
uniform convergence. Typically, these bounds are obtained using a ghost sample
argument combined with a growth function bound for the concept class
$\mathcal{C}$. However, in the $k$-list learning context, some list-learnable
classes $\mathcal{C}$ exhibit growth functions that are excessively large to
apply this method. To overcome this, we directly analyze the VC dimension of
the loss functions. Utilizing a probabilistic argument, we demonstrate that a
high VC dimension of the loss function directly implies a significantly large
$k$-DS dimension for the class $\mathcal{C}$. Consequently, if the class
$\mathcal{C}$ does not satisfy uniform convergence, it is not PAC learnable.

####  1.1.3 Direct Sum

In computer science, the term ’direct sum’ refers to fundamental questions
about the scaling of computational or information complexity with respect to
multiple task instances. Consider an algorithmic task $T$ and a computational
resource $C$. For instance, $T$ might be the task of computing a polynomial,
with $C$ representing the number of arithmetic operations required, or $T$
could be a learning task with its sample complexity as $C$. The direct sum
inquiry focuses on the cost of solving $k$ separate instances of $T$,
particularly how this aggregate cost compares to the resources needed for a
single instance. Typically, the cost for multiple instances is at most $k$
times the cost of one, since each can be handled independently.

However, there are intriguing scenarios where the total cost for $k$ instances
is less than this linear relationship. These cases suggest more efficient
methods for simultaneously handling multiple instances of a task than
addressing them one by one. As an example, consider an $n\times n$ matrix $A$
and the objective of calculating its product with an input column vector $x$,
where the computational resource $C$ is the number of arithmetic operations.
For a single vector $x$, it is easy to see that $\Theta(n^{2})$ operations are
necessary and sufficient. However, if instead of one input vector $x$, there
are $n$ input vectors $x_{1},\ldots,x_{n}$ then one can do better than
$n\times\Theta(n^{2})=\Theta(n^{3})$. Indeed, by arranging these $n$ vectors
as columns in an $n\times n$ matrix $B$, computing the product $A\cdot B$ is
equivalent to solving the $n$ products $A\cdot x_{i}$. This task can be
accomplished using roughly $n^{\omega}\leq n^{2.37}$ arithmetic operations
with fast matrix multiplication algorithms. Direct sum questions are well-
studied in information theory and complexity theory. For more background we
refer the reader to the thesis by Pankratov (2012) or the books by Wigderson
(2019) and Rao and Yehudayoff (2020).

##### Direct Sum in Learning Theory.

Natural direct sum questions can also be posed in learning theory. To
formalize these, we use the notion of cartesian product of concept classes:
consider two concept classes, $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, defined
over domains $\mathcal{X}_{1}$ and $\mathcal{X}_{2}$, and label spaces
$\mathcal{Y}_{1}$ and $\mathcal{Y}_{2}$ respectively. Their product,
$\mathcal{C}_{1}\otimes\mathcal{C}_{2}$, has domain
$\mathcal{X}_{1}\otimes\mathcal{X}_{2}$ and label space
$\mathcal{Y}_{1}\otimes\mathcal{Y}_{2}$. Each concept $c$ in
$\mathcal{C}_{1}\otimes\mathcal{C}_{2}$ is parameterized by a pair of concepts
$c_{1}\in\mathcal{C}_{1}$ and $c_{2}\in\mathcal{C}_{2}$, and is defined as
$c((x_{1},x_{2}))=(c_{1}(x_{1}),c_{2}(x_{2}))$. Thus, learning $c$ effectively
means learning both $c_{1}$ and $c_{2}$ simultaneously.

In our proofs of Theorems 1.2 and 1.3, we study the sample compression
complexity of such product classes. While direct sum analysis serves primarily
as a technical instrument in our research, it also leads to basic questions
that we propose for future research. For instance, consider the following
question:

######  Open Question 1 (Direct Sum: PAC Learning Curves)

Let $\mathcal{C}\subseteq\mathcal{Y}^{\mathcal{X}}$ be a concept class, and
let $\varepsilon(n|\mathcal{C})$ denote the realizable PAC learning curve of
$\mathcal{C}$ (see Definition 2.2). For $r\in\mathbb{N}$ let
$\mathcal{C}^{r}=\Pi_{i=1}^{r}\mathcal{C}$ be the $r$-fold Cartesian product
of $\mathcal{C}$. By a union bound, learning each component independently
gives

$\varepsilon(n|\mathcal{C}^{r})\leq r\cdot\varepsilon(n|\mathcal{C}).$

Can the upper bound be asymptotically improved for some classes $\mathcal{C}$?

Further discussion and open questions related to the direct sums of learning
problems are elaborated in the full version of this paper.

##### Organization.

The remainder of this paper is organized as follows: Section 2 presents the
fundamental definitions of PAC learnability and sample compression, adapted
for the list learning setting. Subsequently, Section 3 provides an overview of
the techniques and key ideas employed in our proofs. Then, in Section 4 we
give proofs for results on sample compression, and in Section 5 the uniform
convergence results are proven. Finally in Section 6 we look deeper into the
direct sum questions in learning theory and propose some open questions and
directions for future research.

##  2 Basic Definitions

###  2.1 Generalization

We use standard notation from learning theory, see e.g. Shalev-Shwartz and
Ben-David (2014). Let $\mathcal{X}$ denote the domain and $\mathcal{Y}$ denote
the label space. A $k$-list function (or $k$-list concept) is a function
$c:\mathcal{X}\to{\mathcal{Y}\choose k}$, where ${\mathcal{Y}\choose k}$
denotes the collection of all subsets of $\mathcal{Y}$ of size $k$. A $k$-list
concept class $\mathcal{C}\subseteq{\mathcal{Y}\choose k}^{\mathcal{X}}$ is a
set of $k$-list functions. Note that by identifying sets of size one with
their single elements, $1$-list concept classes correspond to standard concept
classes.

A $k$-list learning rule is a map
$\mathcal{A}:(\mathcal{X}\times\mathcal{Y})^{*}\to{\mathcal{Y}\choose
k}^{\mathcal{X}}$, i.e. it gets a finite sequence of labeled examples as input
and outputs a $k$-list function. A learning problem $\mathcal{D}$ is a
distribution over $\mathcal{X}\times\mathcal{Y}$. The population loss of a
$k$-list function $c$ with respect to $\mathcal{D}$ is defined by
$\mathtt{L}_{\mathcal{D}}(c)=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[1_{y\notin
c(x)}]$.

We quantify the learning rate of a given learning rule on a given learning
problem using learning curves:

######  Definition 2.1 (Learning Curve).

The learning curve of a learner $\mathcal{A}$ with respect to a learning
problem $\mathcal{D}$ is the sequence
$\\{\varepsilon_{n}(\mathcal{D}|\mathcal{A})\\}_{n=1}^{\infty}$, where

$\varepsilon_{n}(\mathcal{D}|\mathcal{A})=\mathop{\mathbb{E}}_{S\sim\mathcal{D}^{n}}\Big{[}\mathtt{L}_{\mathcal{D}}\big{(}\mathcal{A}(S)\big{)}\Big{]}.$

In words, $\varepsilon_{n}(\mathcal{D}|\mathcal{A})$ is the expected error of
the learner $\mathcal{A}$ on samples of size $n$ drawn from the distribution
$\mathcal{D}$.

For a sequence $S$ of labeled examples, the empirical loss of a $k$-list
function $c$ with respect to $S$ is
$\mathtt{L}_{S}(c)=\frac{1}{|S|}\sum_{(x,y)\in S}1_{y\notin c(x)}$. A sequence
$S\in(\mathcal{X}\times\mathcal{Y})^{n}$ is realizable by a $k$-list function
$c$ if $y\in c(x)$ for every $(x,y)\in S$. It is realizable by a concept class
$\mathcal{C}$ if it is realizable by some concept $c\in\mathcal{C}$. A
learning problem $\mathcal{D}$ is realizable by a concept class $\mathcal{C}$
if for any $n\in\mathbb{N}$, a random sample $S\sim\mathcal{D}^{n}$ is
realizable by $\mathcal{C}$ with probability $1$.

######  Definition 2.2 (List PAC Learnability).

We say that a concept class $\mathcal{C}$ is agnostically $k$-list learnable
if there exists a $k$-list learning rule $\mathcal{A}$ and a sequence
$\varepsilon_{n}\xrightarrow{n\to\infty}0$ such that for every learning
problem $\mathcal{D}$, $(\forall
n):\varepsilon_{n}(\mathcal{D}|A)\leq\inf_{c\in\mathcal{C}}\mathtt{L}_{\mathcal{D}}(c)+\varepsilon_{n}$.
If the latter only holds for $\mathcal{C}$-realizable distributions then we
say that $\mathcal{C}$ is $k$-list learnable in the realizable case. The
$k$-list realizable PAC learning curve of a concept class $\mathcal{C}$ is
defined as follows:

$\varepsilon(n|\mathcal{C})=\inf_{\mathcal{A}}\sup_{\mathcal{D}}\varepsilon_{n}(\mathcal{D}|A),$

where the infimum is taken over all $k$-list learning rules $\mathcal{A}$ and
the supremum over all distributions $\mathcal{D}$ that are realizable by
$\mathcal{C}$.

Observe that a class $\mathcal{C}$ is $k$-list PAC learnable in the realizable
case if and only if its PAC learning curve approaches zero as $n\to\infty$.

######  Remark 2.3.

In the literature, PAC learnability is sometimes defined with a more stringent
requirement: that the error is small with high probability, as opposed to
merely the expected error in our definition. These two formulations are
equivalent, as follows by a standard confidence amplification technique. We
chose the above definition as it is simpler in that it involves fewer
parameters (it omits the confidence parameter).

In the full version of the paper we prove an equivalence between agnostic and
realizable case learnability:

######  Theorem 2.4.

Let $\mathcal{C}$ be a concept class. Then $\mathcal{C}$ is $k$-list learnable
in the realizable setting if and only if it is $k$-list learnable in the
agonstic setting.

Hence, we sometimes refer to a concept class as ’learnable’ without
distinguishing between the agnostic and realizable cases. The proof of Theorem
2.4 is a straight-forward adaptation of the proof of the parallel result for
$k=1$ David et al. (2016).

Our last definition in this section is of uniform convergence.

######  Definition 2.5 (Uniform Convergence).

We say that a $k$-list concept class $\mathcal{C}$ satisfies uniform
convergence if there exists a vanishing sequence
$\varepsilon_{n}\xrightarrow{n\to\infty}0$ such that for all distributions
$\mathcal{D}$,

$\mathop{\mathbb{E}}_{S\sim\mathcal{D}^{n}}[\sup_{h\in\mathcal{C}}\lvert\mathtt{L}_{\mathcal{D}}(h)-\mathtt{L}_{S}(h)\rvert]\leq\varepsilon_{n}.$

The uniform convergence rate of $\mathcal{C}$ is defined by
$\varepsilon_{\mathtt{UC}}(n|\mathcal{C})=\sup_{\mathcal{D}}\mathop{\mathbb{E}}_{S\sim\mathcal{D}^{n}}[\sup_{h\in\mathcal{C}}\lvert\mathtt{L}_{\mathcal{D}}(h)-\mathtt{L}_{S}(h)\rvert]$,
where the supremum is over all distributions $\mathcal{D}$.

Note that $\mathcal{C}$ satisfies uniform convergence if and only if its
uniform convergence rate converges to zero as $n\to\infty$. It is also worth
mentioning that in the binary setting (i.e. when $\mathcal{Y}=\\{0,1\\}$), PAC
learnability is equivalent to uniform convergence, and that this equivalence
justifies the Empirical Risk Minimization principle of outputting an concept
in $\mathcal{C}$ which minimizes the sample error.

###  2.2 List Sample Compression

######  Definition 2.6 (List Compressibility).

A concept class $\mathcal{C}$ is agnostically $k$-list compressible if there
exist $d\in\mathbb{N}$ and a reconstruction function
$\rho:(\mathcal{X}\times\mathcal{Y})^{d}\to{\mathcal{Y}\choose
k}^{\mathcal{X}}$ such that the following holds. For every sample
$S\in(\mathcal{X}\times\mathcal{Y})^{n}$ there exists
$S^{\prime}=\big{(}(x_{1},y_{1}),\ldots(x_{d},y_{d})\big{)}$, where
$(x_{i},y_{i})\in S$ for all $i\leq d$ such that
$\mathtt{L}_{S}(\rho(S^{\prime}))\leq\inf_{c\in\mathcal{C}}\mathtt{L}_{S}(c)$.
If the latter only holds for $\mathcal{C}$-realizable samples then we say that
$\mathcal{C}$ is $k$-list compressible in the realizable case.

In some places, the map that takes $S$ to $S^{\prime}$ is explicitly defined
as the compression map and is denoted by $\kappa$, and the pair
$(\rho,\kappa)$ is called the sample compression scheme.

In the full version of this paper we include additional basic results on list
sample compression schemes. In particular, we prove that any list sample
compression scheme generalizes and that learnability is equivalent to
_logarithmic_ -compressibility. The latter is a variant of the above
definition of sample compression where the size of the compression scheme is
not a fixed constant $d$, but rather depends logarithmically on the size of
the input sample.

######  Remark 2.7 (Functions vs. List Functions).

Let $\mathcal{C}$ be a $k$-list concept class. Define a function class

$\mathcal{F}=\mathcal{F}(\mathcal{C})=\\{f:\mathcal{X}\to\mathcal{Y}:f\prec
c\text{ for some }c\in\mathcal{C}\\},$

where $f\prec c$ means $f(x)\in c(x)$ for all $x\in\mathcal{X}$. Note that
$\mathcal{F}$ and $\mathcal{C}$ are equivalent in the sense that a sample $S$
is realizable by $\mathcal{F}$ if and only if it is realizable by
$\mathcal{C}$. In particular $\mathcal{F}$ is $k$-learnable ($k$-compressible)
if and only if $\mathcal{C}$ is. Thus, when discussing learnability (or
compressibility), we may restrict our attention to ($1$-list) function classes
without losing generality. For this reason in Theorems 1.1, 1.2 and 1.3 we can
focus on function classes.

In contrast, this reduction from list-functions to functions does not make
sense when studying empirical risk minimization over a $k$-list concept class
$\mathcal{C}$. Moreover, the above reduction from $\mathcal{C}$ to
$\mathcal{F}(\mathcal{C})$ does not preserve uniform convergence. Indeed, let
$\mathcal{C}=\\{c\\}$, where $c$ is the $2$-list function such that
$c(x)=\\{0,1\\}$ for all $x$. Clearly, $\mathcal{C}$ satisfies uniform
convergence (because it is finite), however
$\mathcal{F}(\mathcal{C})=\\{0,1\\}^{\mathcal{X}}$ does not satisfy uniform
convergence when $\mathcal{X}$ is infinite. For this reason in Theorem 1.4 we
focus on $k$-list function classes.

###  2.3 Combinatorial Dimensions

We next introduce the Graph and Daniely-Shwartz (DS) dimensions which are
known to characterize Uniform Convergence and List PAC learnability.

######  Definition 2.8 (Graph Dimension).

A sequence $S=\\{x_{i}\\}_{i=1}^{n}$ is $\mathtt{G}_{k}$-shattered by a
$k$-list concept class $\mathcal{C}$ if there is $p\in\mathcal{Y}^{n}$ called
a piovt, such that for any $b\in\\{0,1\\}^{n}$ there is $c_{b}\in\mathcal{C}$
such that $1[p_{i}\in c_{b}(x_{i})]=b_{i}$. In other words the (binary)
concept class $\\{1_{p_{i}\in c(x_{i})}:c\in\mathcal{C}\\}$ shatters $S$ in
the classical VC sense of shattering. The $k$-graph dimension of $\mathcal{C}$
is $\mathtt{G}_{k}(\mathcal{C})$ the size of the largest
$\mathtt{G}_{k}$-shattered sequence, or infinity if there are $\mathtt{G}_{k}$
shattered sequences of arbitrary size.

It is well known that the graph dimension characterizes uniform convergence in
the following sense

######  Theorem 2.9 (Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011)).

A $k$-list concept class $\mathcal{C}$ satisfies uniform convergence if and
only if $\mathtt{G}_{k}(\mathcal{C})<\infty$. Furthermore, the uniform
convergence rate of $\mathcal{C}$ is
$\Theta\bigl{(}\sqrt{\frac{\mathtt{G}_{k}(\mathcal{C})}{n}}\bigr{)}$.

##### Daniely-Shwartz Dimension.

To define the DS dimension we first need to introduce the concept of a pseudo-
cube, which is a generalization of the boolean hypercube $\\{0,1\\}^{n}$ when
the label space is $\mathcal{Y}=[m]$. We say that $y,y^{\prime}\in[m]^{n}$ are
neighbors in direction $i$ (or simply $i$-neighbors) if $y_{j}=y_{j}^{\prime}$
if and only if $j\neq i$. We say that $B\subset\mathcal{Y}^{n}$ is a pseudo-
cube of rank $d$ if each $y\in B$ has at least $d$ distinct neighbors in each
direction $i\in[n]$.

######  Definition 2.10 (DS Dimension).

A sequence $S=\\{x_{i}\\}_{i=1}^{n}$ is $\mathtt{DS}_{k}$-shattered by
$\mathcal{C}$ if $\\{(c(x_{1}),\ldots,c(x_{n})):c\in\mathcal{C}\\}$ contains a
pseudo-cube of rank $k$. The $k$-DS dimension of $\mathcal{C}$ is
$\mathtt{DS}_{k}(\mathcal{C})$ the size of the largest $\mathtt{DS}_{k}$
shattered sequences, or infinity if there are $\mathtt{DS}_{k}$-shattered
sequences of arbitrary size.

As shown by Charikar and Pabbaraju (2022) the $\mathtt{DS}_{k}$ is the
combinatorial dimension that characterizes $k$-list learnability in the
following sense

######  Theorem 2.11 (Charikar and Pabbaraju (2022)).

A concept class $\mathcal{C}$ is $k$-list PAC learnable if and only if
$\mathtt{DS}_{k}(\mathcal{C})<\infty$.

##  3 Technical Overview

In this section, we overview the main ideas which are used in the proofs. We
also try to guide the reader on which of our proofs reduce to known arguments
and which require new ideas.

###  3.1 Sample Compression Schemes

Theorems 1.1, 1.2, and 1.3 provide impossibility results for sample
compression schemes. These types of results are relatively uncommon in the
literature, underscoring the technical challenges involved in comprehensive
reasoning about all sample compression schemes. We circumvent these challenges
by defining a simpler combinatorial notion of _coverability_ , which is
implied by compressibility. In essence, if a small-sized sample compression
exists, then small covers must also exist, and conversely, the lack of small
covers indicates the absence of such a compression scheme.

####  3.1.1 Coverability

A $k$-list concept class $\mathcal{H}$ is a $k$-list cover of a ($1$-list)
function class $\mathcal{C}$ if for any $c\in\mathcal{C}$ there is
$h\in\mathcal{H}$ such that $c(x)\in h(x)$ for all $x\in\mathcal{X}$. We say
that $\mathcal{C}$ is $k$-list coverable if there is some polynomial $p$ such
that for any finite $S\subset\mathcal{X}$, the finite class
$\mathcal{C}|_{S}=\\{c|_{S}:c\in\mathcal{C}\\}$ has a $k$-list cover of size
$p(\lvert S\rvert)$. (Recall that $c|_{S}$ denotes the restriction (or
projection) of the function $c$ to the set $S$.)

This generalizes the notion of _disambiguation of partial concept classes_ : A
partial concept class $\mathcal{C}$ is a class of partial functions
$c:\mathcal{X}\to\mathcal{Y}\cup\\{\star\\}$, where $\star\notin\mathcal{Y}$
and $c(x)=\star$ means that $c$ is undefined on $x$. A class $\mathcal{H}$ is
said to disambiguate $\mathcal{C}$ if for every $c\in\mathcal{C}$ there exists
$h\in\mathcal{H}$ such that $h(x)=c(x)$ whenever $c(x)\neq\star$. Notice that
$1$-covers are equivalent to disambiguations. Partial concept classes and
disambiguations were studied by (Long, 2001; Attias, Kontorovich, and Mansour,
2022; Alon, Hanneke, Holzman, and Moran, 2021; Hatami, Hosseini, and Meng,
2023; Cheung, Hatami, Hatami, and Hosseini, 2023).

In Lemma 4.22 we prove that if $\mathcal{C}$ is $k$-list compressible then it
is $k$-list coverable. Thus, to show that $\mathcal{C}$ is not $k$-list
compressible it suffices to show that it is not $k$-list coverable. Given this
reduction, the proof can be divided into the following steps:

  * (i)

By Alon et al. (2021) there is a partial concept class $\mathcal{C}$ that is
$1$-list learnable but not $1$-list coverable.

  * (ii)

Boosting the hardness of $\mathcal{C}$: by a direct sum argument we show that
the $k$-fold power $\mathcal{C}^{k}$ is $1$-list learnable but not $k$-list
coverable.

  * (iii.a)

Theorems 1.1 and 1.2 follow333For Theorem 1.1 we just use the case of $k=1$.
by taking the _minimal disambiguation_ of $\mathcal{C}^{k}$ (defined below).

  * (iii.b)

Theorem 1.3 follows by taking the _free disambiguation_ of $\mathcal{C}^{k}$
(defined below).

The first two steps yield a partial concept class that is $1$-list learnable
but not $k$-list compressible. The next two steps are parallel to each other,
these steps employ two types of disambiguations which complete the partial
concept class to a total concept class in two ways that witness Theorems 1.2
and 1.3.

####  3.1.2 Free Disambiguations

######  Definition 3.1 (Free Disambiguation).

Let $\mathcal{C}$ be a partial concept class. For each $c\in\mathcal{C}$ let
$y_{c}$ be a distinct new label. Let $\hat{c}$ denote the completion of $c$
such that $\hat{c}(x)=y_{c}$ whenever $c(x)=\star$. The class
$\hat{\mathcal{C}}=\\{\hat{c}:c\in\mathcal{C}\\}$ is called the free
disambiguation of $\mathcal{C}$.

That is, each function in $\mathcal{C}$ is disambiguated by replacing all
instances of $\star$ with a unique label for that function. The following
lemma is the key to step (iii.b):

######  Lemma 3.2.

A partial concept class $\mathcal{C}$ is $k$-list learnable (compressible) if
and only if its free disambiguation $\hat{\mathcal{C}}$ is $k$-list learnable
(compressible)

We note that the free disambiguation was used in Pabbaraju (2023) on the
partial concept class by Alon et al. (2021) to establish the existence of a
learnable class that is not compressible, here we apply it more generally to
the classes generated by the direct sum argument.

####  3.1.3 Minimal Disambiguations

Since the free disambiguation invetiably has an infinite label space, it
cannot be used to derive Theorems 1.1 and 1.2. For that, we introduce a
different type of disambiguation:

######  Definition 3.3 (Minimal Disambiguation).

Let $\mathcal{C}$ be a partial concept class and let $y_{\star}$ be a new
label. For a partial concept $c$, let $\bar{c}$ denote the completion of $c$
such that $\bar{c}(x)=y_{\star}$ whenever $c(x)=\star$. The class
$\bar{\mathcal{C}}=\\{\bar{c}:c\in\mathcal{C}\\}$ is called the minimal
disambiguation of $\mathcal{C}$.

So, all instances of $\star$ are disambiguated by the same new label. Here,
the label space of $\bar{\mathcal{C}}$ has just one more label than that of
$\mathcal{C}$. In particular, the label space of $\bar{\mathcal{C}}$ is finite
whenever the label space of $\mathcal{C}$ is finite. The following lemma is
the key to step (iii.a):

######  Lemma 3.4.

Let $\mathcal{C}$ be a partial concept class over a finite label space and let
$\bar{\mathcal{C}}$ be its minimal disambiguation. Then, (i) if $\mathcal{C}$
is $k$-list learnable then $\bar{\mathcal{C}}$ is $(k+1)$-list learnable, and
(ii) if $\mathcal{C}$ is $k$-list learnable and $\bar{\mathcal{C}}$ is
$(k+1)$-list coverable then $\mathcal{C}$ is $k$-list coverable.

The above lemma is significantly more nuanced then Lemma 3.2. In particular it
replaces compressibility with coverability and provides implications in one
direction rather than equivalences. Nevertheless it suffices to yield Theorems
1.1 and 1.2: we apply it to the basic partial concept class from (Alon et al.,
2021) to deduce Theorem 1.1, and to the classes generated by the direct sum
argument to deduce Theorem 1.2. It would be interesting to find a simpler and
more direct argument like in Lemma 3.2.

###  3.2 Uniform Convergence

Theorem 1.4 states an equivalence between learnability, agnostic learnability,
and uniform convergence for $k$-list concept classes $\mathcal{C}$. It is
clear that uniform convergence implies agnostic learnability, which implies
learnability. Thus, it remains to show that learnability implies uniform
convergence. Towards this end it suffices to show that if the graph dimension
$\mathtt{G}_{k}(\mathcal{C})$ (which controls uniform convergence) is
unbounded then also the DS dimension $\mathtt{DS}_{k}(\mathcal{C})$ (which
control list learnability) is unbounded.

Assume $S=\\{x_{i}\\}_{i=1}^{n}$ is $\mathtt{G}_{k}$-shattered by
$\mathcal{C}$; thus there exists a pivot $p\in\mathcal{Y}^{S}$ and functions
$\\{c_{b}\\}_{b\in\\{0,1\\}^{S}}$ such that $p_{i}\in c_{b}(x_{i})$ if and
only if $b_{i}=1$. For each $c_{b}$ let
$A_{b}:=\\{y\in\mathcal{Y}^{S}\;:\;\forall i\;y_{i}\in c_{b}(x_{i})\\}$ denote
its set of realizable sequences. To lower bound $\mathtt{DS}_{k}(\mathcal{C})$
we lower bound the size of the union
$\lvert\bigcup_{b\in\\{0,1\\}^{n}}A_{b}\rvert$ and apply a version of the
Sauer–Shelah-Perles lemma from Charikar and Pabbaraju (2022). Our lower bound
on $\lvert\bigcup_{b\in\\{0,1\\}^{n}}A_{b}\rvert$ is based on a coding
theoretic approach and consists of the following steps:

  1. 1.

We first upper bound the size of the intersection $\lvert A_{b}\cap
A_{b^{\prime}}\rvert$ in terms of the Hamming distance between $b$ and
$b^{\prime}$.

  2. 2.

We then utilize the above within an inclusion-exclusion bound on
$\\{A_{b}\\}_{b\in R}$, where $R\subseteq\\{0,1\\}^{n}$ is a random subset of
the cube. This yields a lower bound on $\lvert\bigcup_{b\in R}A_{b}\rvert$ and
hence also on $\lvert\bigcup_{b\in\\{0,1\\}^{n}}A_{b}\rvert$.

The first part is just the simple observation that if $y\in c_{b}(x)$,
$y\notin c_{b^{\prime}}(x)$ then $\lvert c_{b}(x)\cap
c_{b^{\prime}}(x)\rvert\leq k-1$. This yields the bound

$\displaystyle\lvert A_{b}\cap A_{b^{\prime}}\rvert\leq\prod_{i=1}^{n}\lvert
c_{b}(x_{i})\cap c_{b^{\prime}}(x_{i})\rvert\leq
k^{n}(\frac{k-1}{k})^{d_{H}(b,b^{\prime})},$

where $d_{H}(b,b^{\prime})=\lvert\\{i\in[n]\;:\;b_{i}\neq
b_{i}^{\prime}\\}\rvert$ is the Hamming distance between $b$ and $b^{\prime}$.

This upper bound on the sizes of the pairwise intersections naturally suggests
us to employ the inclusion-exclusion principle to lower bound the size of the
entire union. Unfortunately, directly applying it to the entire set
$\\{A_{b}\\}_{b\in\\{0,1\\}^{n}}$ does not work, because the average hamming
distance is too small. To overcome this issue we restrict ourselves to a
random subset of $\\{0,1\\}^{n}$. Such a set is both large and has a large
average Hamming distance.

##  4 Sample Compression Proofs

Here we prove our main results concerning sample compression. We begin with
proving equivalence between variable size compressibility and learnability in
Section 4.1. Then in Section 4.2 we prove our main results on sample
compression: Theorems 1.1, 1.2 and 1.3.

###  4.1 Learnability is Equivalent to Variable Size Compressibility

The next definition extends the concept of sample compression schemes to
permit the compression size to vary based on the size of the input sample.

######  Definition 4.1 (Variable Size Compression).

A $k^{\prime}$-list concept class $\mathcal{C}$ is $k$-list (variable-size)
compressible if there exist a sublinear sequence $d(n)=o(n)$ and a
reconstruction function
$\rho:(\mathcal{X}\times\mathcal{Y})^{\star}\to{\mathcal{Y}\choose
k}^{\mathcal{X}}$ such that the following holds. For every sample
$S\in(\mathcal{X}\times\mathcal{Y})^{n}$ there exists
$S^{\prime}=\big{(}(x_{1},y_{1}),\ldots(x_{d(n)},y_{d(n)})\big{)}$, where
$(x_{i},y_{i})\in S$ for all $i\leq d(n)$ such that

$\mathtt{L}_{S}(\rho(S^{\prime}))\leq\inf_{c\in\mathcal{C}}\mathtt{L}_{S}(c).$
(1)

If Equation 1 only holds for $\mathcal{C}$-realizable samples then we say that
$\mathcal{C}$ is $k$-list (variable-size) compressible in the realizable case.
As an important special case, we say that $\mathcal{C}$ is compressible of
logarithmic size if $d(n)=O(\log n)$.

We state and prove two basic results regarding the connection between
compressibility and learnability: (i) an equivalence between learnability and
(variable-size) compressibility, and (ii) a quantitative bound on the
gnerealization error of sample compression schemes.

######  Theorem 4.2.

[Learnability and Logarithmic-Compressibility] Let
$k,k^{\prime}\in\mathbb{N}$. Then, the following statements are equivalent for
a $k^{\prime}$-list concept class $\mathcal{C}$:

  1. 1.

$\mathcal{C}$ is $k$-list learnable in the agnostic setting.

  2. 2.

$\mathcal{C}$ is $k$-list learnable in the realizable setting.

  3. 3.

$\mathcal{C}$ is $k$-list compressible in the agnostic setting with
compression size $d(n)=O(\log n)$.

  4. 4.

$\mathcal{C}$ is $k$-list compressible in the realizable setting with
compression size $d(n)=O(\log n)$.

######  Proposition 4.3 (Compression Size vs. Generalization Error).

Let $k,k^{\prime}\in\mathbb{N}$, $\mathcal{C}$ be a $k^{\prime}$-list concept
class that is compressible with compression size $d(n)$, and set
$\mathcal{A}:=\rho\circ\kappa$. Then for any $\mathcal{D}$ realizable
distribution and $\varepsilon>0$ we have for all $n>0$

$\displaystyle\Pr\Big{(}\mathtt{L}_{\mathcal{D}}\big{(}\mathcal{A}(S)\big{)}>\varepsilon\Big{)}\leq
2\exp\big{(}d(n)\ln(n)-\varepsilon^{2}n\big{)}.$

And for all $n>0$ the learning curve
$\varepsilon_{n}(\mathcal{A}|\mathcal{D})$ satisfies

$\displaystyle\varepsilon_{n}(\mathcal{A}|\mathcal{D})\leq\sqrt{\frac{(d(n)+1)\ln(n)}{n}}+\frac{2}{n}.$

The proofs of Theorem 4.2 and Proposition 4.3 are adaptations of the proofs of
the classical cases of $k=1$, which can be found e.g. in David et al. (2016).
For completeness, we repeat the argument with the necessary adjustments below.

######  Proof 4.4 (Proof of Theorem 4.2 and Proposition 4.3).

We will show that $1\implies 2\implies 4\implies 3\implies 1$,where the proof
of $3\implies 1$ implies Proposition 4.3. The direction $1\implies 2$ is clear
by definition. Next, we show that $4\implies 3$. Indeed let $(\rho,\kappa)$ be
a realizable $k$-list compression scheme for $\mathcal{C}$. Let
$S\subset(\mathcal{X}\times\mathcal{Y})^{*}$ be some sample and take
$S^{\prime}\subset S$ to be a $\mathcal{C}$ realizable subsample of maximal
size. by definition $\lvert S\rvert\cdot\mathtt{L}_{S}(c)\geq\lvert S\setminus
S^{\prime}\rvert$ for any $c\in\mathcal{C}$. Now since $S^{\prime}$ is
realizable we have
$\mathtt{L}_{S^{\prime}}\big{(}\rho(\kappa(S^{\prime}))\big{)}=0$ implying

$\displaystyle\lvert
S\rvert\cdot\mathtt{L}_{S}\Big{(}\rho\big{(}\kappa(S^{\prime})\big{)}\Big{)}\leq\lvert
S\rvert\cdot\mathtt{L}_{S^{\prime}}\Big{(}\rho\big{(}\kappa(S^{\prime})\big{)}\Big{)}+\lvert
S\setminus S^{\prime}\rvert=\lvert S\setminus S^{\prime}\rvert\leq\lvert
S\rvert\cdot\inf_{c\in\mathcal{C}}\mathtt{L}_{S}(c).$

Therefore $\rho$ is also an agnostic $k$-list reconstruction function for
$\mathcal{C}$.

Now we show that $3\implies 1$. Let $\rho$ be a reconstructor for
$\mathcal{C}$ of size $\\{d(n)\\}_{n=1}^{\infty}$ for some sequence
$d(n)=O(\log(n))$. We will show that
$\mathcal{A}(S):=\rho\big{(}\kappa(S)\big{)}$ is a $k$-list learner for
$\mathcal{C}$. Fix some realizable learning problem $\mathcal{D}$, and draw a
sample $S$ of size $n$ according to $\mathcal{D}$. define

$\displaystyle\mathcal{T}:=\\{(x_{1},y_{1}),(x_{2},y_{2}),\dots(x_{d(n)},y_{d(n)})\;:\;\forall
1\leq i\leq d(n)\;(x_{j},y_{j})\in S\\}.$

The set of all possible inputs to our reconstructor (with respect to the
sample $S$). For any $T\in\mathcal{T}$, define

$\displaystyle S_{T}=S\setminus T=\\{(x,y)\in S\;:(x,y)\notin T\\},$
$\displaystyle h_{T}=\rho(T).$

For any $s=(x,y)\in S$ define the random variable
$X_{s,T}=1_{y_{\in}h_{T}(x_{)}}$. So

$\displaystyle\mathtt{L}_{S_{T}}(h_{T})=\frac{1}{d(n)}\sum_{s\in
S_{T}}X_{s,T}.$

Now since clearly, $h_{T}$ is independent of $S_{T}$ and the
$\\{X_{s,T}\\}_{s\in S}$ are independent of each other we may use Hoeffding’s
inequality to get

$\displaystyle\Pr(\lvert\mathtt{L}_{S_{T}}(h_{T})-\mathtt{L}_{\mathcal{D}}(h_{T})\rvert>\varepsilon)\leq
2e^{-\varepsilon^{2}n},$

and by simple union bound deduce

$\displaystyle\Pr(\exists T\;\text{ s.t
}\;\lvert\mathtt{L}_{S_{T}}(h_{T})-\mathtt{L}_{\mathcal{D}}(h_{T})\rvert>\varepsilon)\leq
2n^{d(n)}e^{-\varepsilon^{2}n}=2\exp(d(n)\ln(n)-\varepsilon^{2}n).$

Finally, we note that on the above event, we have
$\lvert\mathtt{L}_{\mathcal{D}}(\mathcal{A})-\mathtt{L}_{S}(\mathcal{A})\rvert\leq\varepsilon$.
hence

$\displaystyle\Pr\big{(}\lvert\mathtt{L}_{\mathcal{D}}(\mathcal{A})-\mathtt{L}_{S}(\mathcal{A})\rvert>\varepsilon\big{)}\leq
2\exp(d(n)\ln(n)-\varepsilon^{2}n).$

From this, we can use $d(n)=O(\log(n))$ to deduce the desired result.

Finally, we show that $2\implies 4$. Let $\mathcal{A}$ be a $k$-list learning
rule for $\mathcal{C}$. Let $\varepsilon>0$ be such that
$\varepsilon<\frac{1}{2(k+1)}$and take $d$ large enough such that the learning
curve $\varepsilon_{d}(\mathcal{A}|\mathcal{D})\leq\varepsilon$ for any
realizable $\mathcal{D}$. We will show that $\mathcal{C}$ has a compression
scheme of size $d(n)=\frac{d\log(3n)}{\varepsilon^{2}}$, note that
$\varepsilon,d$ are constants so this indeed gives a logarithmic compression
size.

We define the reconstruction function $\rho$ as follows. Given a sample $S$ of
size $d\cdot T$ partition it into $T$ samples of size $d$ so
$S=(S_{1},S_{2},\dots,S_{T})$, then we can think of $\rho(S)$ as a majority
vote of the $\\{A(S_{t})\\}_{t=1}^{T}$, formally for any $x\in\mathcal{X}$ we
define $\phi_{x}:\mathcal{Y}\to\mathbb{N}$, $\Phi_{x}:{\mathcal{Y}\choose
k}\to\mathbb{N}$ by

$\displaystyle\phi_{x}(y)=\lvert\\{t\in[T]\;:\;y\in A(S_{t})(x)\\}\rvert,$
$\displaystyle\Phi_{x}(Y)=\sum_{y\in Y}\phi_{x}(y).$

and then define $\rho(S)(x)$ by

$\displaystyle\rho(S)(x)=\underset{Y\in{\mathcal{Y}\choose k}}{\text{argmax
}}\Phi_{x}(Y)$

where ties are resolved arbitrarily. Now we need to show that $\rho$ is indeed
a reconstruction function for $\mathcal{F}$. Fix some realizable sample
$S=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ of size $n$ and define

$\displaystyle\mathcal{H}:=\Big{\\{}\mathcal{A}(S^{\prime})\;:\;S^{\prime}\subset{S\choose
d}\Big{\\}}.$

Note that for any realizable distribution $\mathcal{D}$ over $S$ there is some
$h\in\mathcal{H}$ such that $\mathtt{L}_{\mathcal{D}}(h)\leq\varepsilon$. Now
let us consider the zero-sum game between a learner and an adversary that goes
as follows, the learner picks $h\in\mathcal{H}$ and the adversary picks
$(x_{i},y_{i})\in S$, the learner wins if and only if $y_{i}\in h(x_{i})$.
With this view, the above remark states that for any randomized strategy of
the adversary, the learner has a deterministic strategy that loses with
probability at most $\varepsilon$. Hence by the well-known min-max theorem,
there is some randomized strategy, for which the expected loss of the learner
is at most $\varepsilon$ for any randomized strategy of the adversary. Let
$\mu$ be the distribution over $\mathcal{H}$ that induce the above strategy
and let $\\{H_{t}\\}_{t=1}^{T}$ be $T$ elements of $\mathcal{H}$ independently
drawn according to $\mu$ where $T=\frac{\log(3n)}{\varepsilon^{2}}$. We also
define

$\displaystyle X_{t,i}=1_{y_{i}\in H_{t}(x_{i})},$ $\displaystyle
X_{i}=\frac{1}{T}\sum_{t=1}^{T}X_{t,i}.$

note that $EX_{t,i}=EX_{i}\geq 1-\varepsilon$ by the choice of $\mu$. Now by
Hoeffding’s inequality, we have

$\displaystyle\Pr(\lvert X_{i}-EX_{i}\rvert>\varepsilon)\leq
2\exp(-\varepsilon^{2}T)=2e^{\frac{-\varepsilon^{2}\log(3n)}{\varepsilon^{2}}}<\frac{1}{n},$
$\displaystyle\Pr\Big{(}\bigcup_{i=1}^{n}\lvert
X_{i}-EX_{i}\rvert>\varepsilon\Big{)}<1.$

Hence, there are some $\\{h_{t}\\}_{t=1}^{T}$ in $\mathcal{H}$ such that

$\displaystyle\frac{1}{T}\lvert\\{t\in[T]\;:\;y_{i}\in
h_{t}(x_{i})\\}\rvert>EX_{1}-\varepsilon>1-2\varepsilon>\frac{k}{k+1}.$

Note that $h_{t}=A(S_{t})$ for some $S_{t}\subset S$, $\lvert S_{t}\rvert=d$,
we claim that $\kappa(S)=(S_{1},S_{2},\dots S_{T})$ will give the desired
result. And indeed given some $(x_{i},y_{i})\in S$ and using the same
$\phi_{x_{i}}$, $\Phi_{x_{i}}$ as above we see that
$y_{i}\notin\rho(\kappa(S))$ if and only if there at least $k$ other elements
in $\mathcal{Y}$ at which $\phi_{x_{i}}$ is more then $\phi_{x_{i}}(y_{i})$.
But by the above $\phi_{x_{i}}(y_{i})>\frac{kT}{k+1}$, hence we have $k+1$
points at which $\phi_{x_{i}}$ is at more then $\frac{kT}{k+1}$ implying that

$\displaystyle kT=\sum_{t=1}^{T}\lvert
h_{t}(x_{i})\rvert=\sum_{y\in\mathcal{Y}}\phi_{x_{i}}(y)>(k+1)\frac{kT}{k+1}=kT.$

Which is clearly impossible.

###  4.2 Impossibility Results for List Sample Compression

In this section, we prove Theorems 1.1, 1.2 and 1.3. We start by giving
technical background and stating some lemmas that are required for our proofs
in Section 4.2.1. Then, in Section 4.2.2 we prove Lemma 4.17 which is key to
the proofs of both Theorems 1.2 and 1.3; this lemma uses a direct sum argument
to construct a $1$-list learnable class that is not $k$-list coverable. We
then utilize this lemma to prove Theorem 1.2 and Theorem 1.1 in Section 4.2.3
and Theorem 1.3 in Section 4.2.4.

####  4.2.1 Technical Background

Below we introduce definitions and claims that will be used throughout our
proofs in this section.

##### Sauer-Shelah-Perles Lemma for List Learning.

We use the following version of the Sauer-Shelah-Perles (SSP) Lemma by
Charikar and Pabbaraju (2022)

######  Lemma 4.5 (SSP for DS Dimension (Charikar and Pabbaraju, 2022)).

Let $\mathcal{F}\subset\mathcal{Y}^{n}$ be a function class with
$d=\mathtt{DS}_{k}(\mathcal{F})$, $m=\lvert\mathcal{Y}\rvert$, then we have

$\displaystyle\lvert\mathcal{F}\rvert\leq k^{n-d}\sum_{i=0}^{d}{n\choose
i}{m\choose k+1}^{i}\leq k^{n}n^{d}m^{(k+1)d}.$

##### Partial Concepts.

We next introduce some useful results from the theory of partial concept
classes (Alon et al., 2021).

######  Definition 4.6.

Given a domain $\mathcal{X}$, a partial concept $c$ is a function whose domain
$\text{supp}(c)$ is a subset of $\mathcal{X}$, if $\text{supp}(c)=X$ then $c$
is referred to as a total concept. A partial concept class is a collection of
partial functions.

Note that in the above definition, we may take $c$ to be a $k$-list function.
However, for our results, this will not be necessary, as all our partial
functions will be of the standard $k=1$ type.

A standard way to model partial concept classes is to introduce a new label
“$\star$” for the inputs on which any function is not defined. In this view, a
partial concept class is simply a concept class
$\mathcal{C}\subset(\mathcal{Y}\cup\\{\star\\})^{\mathcal{X}}$, where for any
$c\in\mathcal{C}$, we have
$\text{supp}(c)=\\{x\in\mathcal{X}\;:\;c(x)\neq\star\\}=c^{-1}(\mathcal{Y})$.

The definitions of standard learning theory extend naturally into the partial
concept class

######  Definition 4.7.

A sample $S$ of size $n$ is realizable by a $k$-list partial function $c$ if
for any $(x,y)\in S$ we have $x\in\text{supp}(c)$, $y\in c(x)$. A learning
problem $\mathcal{D}$ is realizable by a partial concept class
$\mathcal{C}\subset({\mathcal{Y}\choose k}\cup\\{\star\\})^{\mathcal{X}}$ if
for any $n\in\mathbb{N}$ a random sample $S$ of size $n$ drawn independently
according to $\mathcal{D}$ is realizable by some $c\in\mathcal{C}$ with
probability 1.

Note that a realizable sequence can not contain the $\star$ symbol in it. Now
the notions of compression and learnability can be defined for partial concept
classes in the same way as they are defined for total $k$-list concept
classes.

######  Definition 4.8.

A partial concept class
$\mathcal{C}\subset(\mathcal{Y}\cup\\{\star\\})^{\mathcal{X}}$ is $k$-list
covered by a $k$-list class $\mathcal{H}\subset{\mathcal{Y}\choose
k}^{\mathcal{X}}$ (and respectively $\mathcal{H}$ is a $k$-list covering of
$\mathcal{C}$ ) if for any $c\in\mathcal{C}$, there exists $h\in\mathcal{H}$
such that $c(x)\in h(x)$ for all $x\in\text{supp}(c)$. In such cases, we write
$\mathcal{C}\prec\mathcal{H}$ and $c\prec h$

Note that in the standard case of $k=1$, covering is equivalent to
disambiguation. Although for $k>1$ covering can be seen as a generalization of
disambiguation, it can also be studied in the context of total $k$-list
classes.

######  Definition 4.9.

For any $\mathcal{F}\subset(\mathcal{Y}\cup\\{\star\\})^{\mathcal{X}}$,
$k\in\mathbb{N}$ we define its $k$-list covering size

$\displaystyle\mathtt{C}_{\mathcal{F}}(n,k):=\sup\\{\mathtt{C}(\mathcal{F}|_{S},k)\;:\;S\subset\mathcal{X},\;\lvert
S\rvert=n\\},$

where $C(\mathcal{F}|_{S},k)$ is the size of the minimal $k$-list cover of
$\mathcal{F}|_{S}$, i.e.

$\displaystyle\mathtt{C}(\mathcal{F}|_{S},k):=\inf\bigg{\\{}\lvert\mathcal{H}\rvert\;:\;\mathcal{H}\subset{\mathcal{Y}\choose
k}^{\mathcal{X}},\;\mathcal{F}|_{S}\prec\mathcal{H}\bigg{\\}}.$

##### Direct Sum.

We extend the definition of cartesian product to partial concepts.

######  Definition 4.10.

Given a $k$-list partial function $f:\mathcal{U}\to{\mathcal{Y}\choose
k}\cup\\{\star\\}$ and a $k^{\prime}$-list partial function
$g:\mathcal{V}\to{\mathcal{Z}\choose k^{\prime}}\cup\\{\star\\}$, define their
(cartesian) product $f\otimes
g:\mathcal{U}\otimes\mathcal{V}\to{\mathcal{Y}\otimes\mathcal{Z}\choose
kk^{\prime}}\cup\\{\star\\}$ as follows

$\displaystyle(f\otimes g)(u,v)=\begin{cases}\big{\\{}(y,z)\;:\;y\in f(u),z\in
g(v)\big{\\}}&u\in\text{supp}(f),v\in\text{supp}(g),\\\
\star&\text{else.}\end{cases}$

Similarly, given a $k$-list (partial) concept class
$\mathcal{F}\subset{\mathcal{Y}\choose k}^{\mathcal{U}}$ and a
$k^{\prime}$-list (partial) concept class
$\mathcal{G}\subset{\mathcal{Z}\choose k^{\prime}}^{\mathcal{V}}$, define
their product $\mathcal{F}\otimes\mathcal{G}$ as

$\displaystyle\mathcal{F}\otimes\mathcal{G}=\\{f\otimes
g\;:\;f\in\mathcal{F},\;g\in\mathcal{G}\\}.$

We primarily focus on the case where $k=k^{\prime}=1$, simplifying the
definition to

$\displaystyle(f\otimes g)(u,v)=\big{(}f(u),g(v)\big{)}.$

######  Definition 4.11 (Product of Learning Rules).

Given a $k$-list learning rule
$\mathcal{A}_{1}:(\mathcal{X}_{1}\times\mathcal{Y}_{1})^{\star}\to{\mathcal{Y}_{1}\choose
k}^{\mathcal{X}_{1}}$ and a $k^{\prime}$-list learning rule
$\mathcal{A}_{2}:(\mathcal{X}_{2}\times\mathcal{Y}_{2})^{\star}\to{\mathcal{Y}_{2}\choose
k^{\prime}}^{\mathcal{X}_{2}}$. We define their product
$\mathcal{A}_{1}\otimes\mathcal{A}_{2}:((\mathcal{X}_{1}\otimes\mathcal{X}_{2})\times(\mathcal{Y}_{1}\otimes\mathcal{Y}_{2}))^{\star}\to{\mathcal{Y}_{1}\times\mathcal{Y}_{2}\choose
k\cdot k^{\prime}}^{\mathcal{X}_{1}\times\mathcal{X}_{2}}$ as follows

$(\mathcal{A}_{1}\otimes\mathcal{A}_{2})(S)=\mathcal{A}_{1}(\pi_{1}(S))\otimes\mathcal{A}_{2}(\pi_{2}(S)),$

where
$\pi_{b}\bigl{(}\\{(x_{i,1},x_{i,2}),(y_{i,1},y_{i,2})\\}_{i=1}^{n}\bigr{)}=\\{(x_{i,b},y_{i,b})\\}_{i=1}^{n}$.

######  Remark 4.12 (Products of Learning Rules and Sample Compressions
Schemes).

Notice that if $\mathcal{F}$ is $k$-list compressible with comprssion size
$d_{1}$ and $\mathcal{G}$ is $k^{\prime}$-list compressible with compression
size $d_{2}$ then $\mathcal{F}\otimes\mathcal{G}$ is $kk^{\prime}$-list
compressible with compression size $d_{1}+d_{2}$. Moreover we have

$\displaystyle\rho\big{(}\kappa(S)\big{)}=\rho_{1}\big{(}\kappa_{1}(\pi_{1}(S))\big{)}\otimes\rho_{2}\big{(}\kappa_{2}(\pi_{2}(S))\big{)}.$

Similarly if $\mathcal{F}$ is $k$-list learnable and $\mathcal{G}$ is
$k^{\prime}$-list learnable then $\mathcal{F}\otimes\mathcal{G}$ is
$kk^{\prime}$-list learnable. Moreover, if $\mathcal{A}_{1}$ is $k$-list
learner for $\mathcal{F}$ and $\mathcal{A}_{2}$ is $k^{\prime}$ list learner
for $\mathcal{G}$ then $\mathcal{A}_{1}\otimes\mathcal{A}_{2}$ is
$kk^{\prime}$ list learner for $\mathcal{F}\otimes\mathcal{G}$ satisfying

$\displaystyle\varepsilon(n|\mathcal{A}_{1}\otimes\mathcal{A}_{2})\leq\varepsilon(n|A_{1})+\varepsilon(n|A_{2}).$

####  4.2.2 Main Lemma: Coverability Under Direct-Sum

In this part, we prove a main lemma on direct sum of partial concept classes
and use it to deduce Lemma 4.17, establishing the existence of a learnable
partial class that is not $k$-list coverable, which is a key part in the proof
of Theorem 1.3 and Theorem 1.2.

######  Lemma 4.13 (Main Direct Sum Lemma).

Let $\mathcal{F}\subset\mathcal{Y}^{\mathcal{U}}$,
$\mathcal{G}\subset\mathcal{Z}^{\mathcal{V}}$ be partial concept classes, then
for any $k,k^{\prime},n,n^{\prime}\in\mathbb{N}$ we have

$\displaystyle\min\Big{(}\mathtt{C}_{\mathcal{F}}(n,k),{\mathtt{C}_{\mathcal{G}}(n^{\prime},k^{\prime})}\Big{)}\leq\min(n,n^{\prime})\cdot\mathtt{C}_{\mathcal{F}\otimes\mathcal{G}}(n\cdot
n^{\prime},k+k^{\prime}).$

In particular, if $\mathcal{F}$ is not $k$-list coverable and $\mathcal{G}$ is
not $k^{\prime}$-list coverable then $\mathcal{F}\otimes\mathcal{G}$ is not
$(k+k^{\prime})$-list coverable.

The proof of Lemma 4.13 requires the following technical claim

######  Claim 1.

Assume
$h:(\mathcal{U}\times\mathcal{V})\to{\mathcal{Y}\otimes\mathcal{Z}\choose
k+k^{\prime}}$ is a $(k+k^{\prime})$-list function. Then for every
$(u,v)\in\mathcal{U}\times\mathcal{V}$ at least one of the following holds:

  * •

$\pi_{2}(h(u,v)):=\\{z\in\mathcal{Z}:(y,z)\in h(u,v)\text{ for
some}y\in\mathcal{Y}\\}$ has at most $k^{\prime}$ distinct labels.

  * •

For all $z\in\mathcal{Z}$ the set $\\{y\in\mathcal{Y}:(y,z)\in h(u,v)\\}$ has
at most $k$ distinct labels.

######  Proof 4.14 (Proof of claim 1).

Let $z^{\prime}\in Z$, a simple computation gives

$\displaystyle k+k^{\prime}=|h(u,v)|$
$\displaystyle=\sum_{z\in\pi_{2}(h(u,v))}|\\{y\in\mathcal{Y}:(y,z)\in
h(u,v)\\}|$ $\displaystyle\leq|\\{y\in\mathcal{Y}:(y,z^{\prime})\in
h(u,v)\\}|+\sum_{\begin{subarray}{c}z\in\pi_{2}(h(u,v))\\\ z\neq
z^{\prime}\end{subarray}}1$
$\displaystyle=|\\{y\in\mathcal{Y}:(y,z^{\prime})\in
h(u,v)\\}|+|\pi_{2}(h(u,v))|-1.$

From which the claim follows immediately.

######  Proof 4.15 (Proof of Lemma 4.13).

Let $U\subset\mathcal{U}$, $V\subset\mathcal{V}$ samples and denote their
sizes $|U|=n$, $|V|=n^{\prime}$. Define $F=\mathcal{F}|_{U}$,
$G=\mathcal{G}|_{V}$ and note that $F\otimes
G=(\mathcal{F}\otimes\mathcal{G})|_{U\otimes V}$, and $|U\otimes V|=n\cdot
n^{\prime}$. Hence there is some $H$ a $(k+k^{\prime})$ list cover of
$F\otimes G$ such that
$|H|\leq\mathtt{C}_{\mathcal{F}\otimes\mathcal{G}}(n\cdot
n^{\prime},k+k^{\prime})$. Without loss of generality we assume $n\leq
n^{\prime}$, so we need to show that either there exists a $k$-list cover of
$F$ of size at most $n\cdot|H|$ or there exists a $k^{\prime}$-list cover of
$G$ of size at most $n\cdot\lvert H\rvert$.

The proof is based on a win-win argument; we show that if there exists a
‘good’ $g\in G$ (to be defined below) then we we can cover $F$ using at most
$\lvert H\rvert$ $k$-list functions. And, otherwise, if no $g\in G$ is ‘good’
then we can cover $G$ using at most $n\cdot\lvert H\rvert$ $k^{\prime}$-list
functions.

For any $h\in H$, $g\in G$, $v\in\text{supp}(g)$, and $u\in U$ define
$h_{g,v}(u)$ by

$\displaystyle h_{g,v}(u)=\big{\\{}y\in\mathcal{Y}\;:\;\big{(}y,g(v)\big{)}\in
h(u,v)\big{\\}}$

Now Define $g$ as good if it satisfies

$\displaystyle(\forall f\in F)(\forall h\in H\text{ such that }f\otimes g\prec
h)(\forall u\in\text{supp}(f))(\exists
v\in\text{supp}(g))\;:\;|h_{g,v}(u)|\leq k.$

Now assume that there is some $g\in G$ that is good, we show how to use it to
construct the desired $k$-list cover of $F$. Note that if $f\otimes g\prec h$
then $f\prec h_{g,v}$ for all $v\in\text{supp}(g)$. Indeed for any
$u\in\text{supp}(f)$ we have $\big{(}f(u),g(v)\big{)}\in h(u,v)$ hence by
definition $f(u)\in h_{g,v}$. Now in general the best bound we have on the
size of $|h_{g,v}(u)|$ is $(k+k^{\prime})$, so $h_{g,v}$ may not be a $k$-list
function. To fix this, we wish to ‘trim’ it somehow, removing some of the
unnecessary labels. Note that in the above argument, we got $f(u)\in
h_{g,v}(u)$ for all $v\in\text{supp}(g)$, hence it seems natural to take
intersection over all such $v$. For any $h\in H$ we define

$\displaystyle h_{g}(u)=\bigcap_{v\in\text{supp}(g)}h_{g,v}(u).$

We already saw that if $f\otimes g\prec h$ we have that $f(u)\in h_{g,v}$ for
all $v\in\text{supp}(g)$. As a result $f(u)$ will be in the intersection and
$f\prec h_{g}$. Now since $g$ for any $f\in F$, $h\in H$ such that $f\otimes
g\prec h$ we have that for all $u\in U$ there is some $v\in\text{supp}(g)$
such that $|h_{g,v}(u)|\leq k$. In particular, $|h_{g}(u)|\leq k$. So we have
that $h_{g}$ is a $k$-list function444It is technically possible that the size
of $h_{v}(u)$ is strictly less than $k$, in which case we add some labels to
it arbitrarily to make it a $k$-list function  for all $h\in H$ such that
there is some $f\in F$ with $f\otimes g\in h$. Hence we may define

$\displaystyle H_{g}=\\{h_{g}\;:\;\exists f\in F\;f\otimes g\in h\\}.$

and by the above get that $H_{g}$ is a $k$-list cover of $F$, and clearly
$|H_{g}|\leq|H|$.

Now we assume that no $g\in G$ is good and show that this implies the
existence of a $k^{\prime}$-list cover of $G$ of size at most $n\cdot|H|$.
Using De Morgan’s laws if no $g\in G$ is good then we have

$\displaystyle(\forall g\in G)(\exists f\in F)(\exists h\in H\text{ s.t\
}f\otimes g\prec h)(\exists u\in\text{supp}(f))(\forall
v\in\text{supp}(g))\;:\;|h_{g,v}(u)|>k.$

Now by Claim 1 if $|h_{g,v}(u)|>k$ then with $\pi_{2}(y,z)=z$ the projection
map we have $|\pi_{2}\big{(}h(u,v)\big{)}|\leq k^{\prime}$. So the above
becomes

$\displaystyle(\forall g\in G)(\exists f\in F)(\exists h\in H\text{ s.t.\
}f\otimes g\prec h)(\exists u\in\text{supp}(f))(\forall
v\in\text{supp}(g)):|\pi_{2}\big{(}h(u,v)\big{)}|\leq k^{\prime}.$

Note that if $f\otimes g\prec h$ then for all
$u\in\text{supp}(f)$,$v\in\text{supp}(g)$ we have $\big{(}f(u),g(v)\big{)}\in
h(u,v)$ hence $g(v)\in\pi_{2}\big{(}h(u,v)\big{)}$. Now by the above for all
$g\in G$ there are some $f\in F$, $h\in H$, $u\in\text{supp}(f)$ such that
$|\pi_{2}\big{(}h(u,v)\big{)}|\leq k$ for all $v\in\text{supp}(g)$, but we
can’t say that $v\to\pi_{2}\big{(}h(u,v)\big{)}$ is a $k^{\prime}$-list
function since we cant bound its size on $v\notin\text{supp}(g)$. Luckily,
when we try to cover $g$ we don’t care for the value of the function on
$v\notin\text{supp}(g)$, so we may trim it arbitrarily. For any $u\in U$,
$h\in H$ let $h_{u}:V\to\\{\mathcal{Z}\choose k^{\prime}\\}$ be any
$k^{\prime}$-list function such that $\pi_{2}\big{(}h(u,v)\big{)}\subset
h_{u}(v)$ for any $v\in V$ such that $|\pi_{2}\big{(}h(u,v)\big{)}|\leq
k^{\prime}$. Now by the above for any $g\in G$ there is some $h\in H$, $u\in
U$ such that $g(v)\in h_{u}(v)$ for all $v\in\text{supp}(g)$ hence if we
define

$\displaystyle H_{U}=\\{h_{u}\;:\;h\in H,\;u\in U\\}$

we have that $G\prec H_{U}$ and clearly $|H_{U}|\leq n\cdot|H|$.

######  Remark 4.16.

Note that in the second case of the above proof, we get a bound of $n\cdot|H|$
on the size of the cover of $G$, as opposed to the bound $|H|$ in the case of
the cover of $F$. This $n$ term appears since our functions are partial
functions, and when dealing with total classes we may improve that bound.
Indeed, similarly to the first case, we may try to trim $h_{u}$ by taking
intersections and define

$\displaystyle\pi_{h}(v)=\bigcap_{u\in U}h_{u}(v).$

And while at first, it seems that $\\{\pi_{h}\;:\;h\in H\\}$ will give a
$k^{\prime}$-list cover for $G$, a closer look will reveal that we don’t
necessarily have that it covers $G$ since $f\otimes g\prec$ only implies that
$g(v)\in h_{u}(v)$ for $u\in\text{supp}(f)$. Hence when we take the
intersection over all of $U$ we can no longer guarantee that
$g(v)\in\pi_{h}(v)$, unless $\text{supp}(f)=U$, i.e. $f$ is a total function.

######  Lemma 4.17.

For any $k\geq 1$ there is a partial concept class
$\mathcal{F}_{k}\subset(\\{0,1\\}^{k}\cup\\{\star\\})^{\mathbb{N}^{k}}$ such
that $\mathcal{F}_{k}$ is $1$-list learnable but
$n^{k-1}\mathtt{C}_{\mathcal{F}^{k}}(n^{k},k)\geq
n^{\big{(}\log(n))\big{)}^{1-o(1)}}$

######  Proof 4.18.

The proof is by induction on $k$. For the base case $k=1$ we can take
$\mathcal{F}_{1}$ to be the partial class from Alon et al. (2021). It is a
learnable binary partial concept class over the natural number, and for any
disambiguation of it $\mathcal{C}$ and $n>0$ there is some
$S\subset\mathbb{N}$ of size $n$ such that $|\mathcal{C}|_{S}|\geq
n^{\big{(}\log(n))\big{)}^{1-o(1)}}$. Thus it satisfies the required
properties.

For the induction step we simply define
$\mathcal{F}_{k+1}=\mathcal{F}_{k}\otimes\mathcal{F}_{1}$. Indeed
$\mathcal{F}_{k+1}\subset(\\{0,1\\}^{k}\cup\\{\star\\})^{\mathbb{N}^{k}}$ is a
$1$-list learnable and from the induction assumption and Lemma 4.13 it
satisfies

$\displaystyle
n^{\big{(}\log(n))\big{)}^{1-o(1)}}\leq\min\Big{(}\mathtt{C}_{\mathcal{F}}(n,1),n^{k-1}\mathtt{C}_{\mathcal{F}^{k}}(n^{k},k)\Big{)}\leq
n^{k}\mathtt{C}_{\mathcal{F}^{k+1}}(n^{k+1},k+1).$

####  4.2.3 Proof of Theorems 1.1 and 1.2

In this part, we give proof for Theorems 1.1 and 1.2. We start by recalling
the definitions of the minimal disambiguation and proving some of its basic
properties and then use those properties with Lemma 4.17 to prove those
Theorems.

##### Minimal Disambiguation.

Recall the definition of the minimal disambiguation of a partial concept
class.

######  Definition (Definition 3.3 restatement)

Let $\mathcal{C}$ be a partial concept class and let $y_{\star}$ be a new
label. For a partial concept $c$, let $\bar{c}$ denote the completion of $c$
such that $\bar{c}(x)=y_{\star}$ whenever $c(x)=\star$. The class
$\bar{\mathcal{C}}=\\{\bar{c}:c\in\mathcal{C}\\}$ is called the minimal
disambiguation of $\mathcal{C}$.

Note that if $\mathcal{C}\subset(\mathcal{Y}\cup\\{\star\\})^{\mathcal{X}}$ is
partial concept class that is $k$-list learnable then its minimal
disambiguation $\bar{\mathcal{C}}$ is $k+1$-list learnable. Indeed let
$\mathcal{A}$ be a $k$-list learning rule for $\mathcal{F}$. For any sample
$S=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ define
$S^{\prime}=S\setminus(\mathcal{X}\times\\{y_{\star}\\})$, note that if $S$ is
realizable by $\bar{\mathcal{C}}$ then $S^{\prime}$ is realizable by
$\mathcal{C}$. Now we may define $\bar{\mathcal{A}}$ a $(k+1)$-list learning
rule for $\bar{\mathcal{C}}$ by

$\displaystyle\bar{A}(S)(x)=A(S^{\prime})(x)\cup\\{y_{\star}\\}$

And one can easily verify that $\bar{A}$ is a learner for $\bar{F}$.

Similarly if $\mathcal{F}$ is $k$-list compressible with reconstruction
function $\rho$ of size $k_{n}$ we can easily verify that $\bar{\mathcal{F}}$
is $k+1$-list compressible with reconstruction function
$\bar{\rho}(S)(x)=\rho(S^{\prime})(x)\cup\\{y_{\star}\\}$. This phenomenon
continues to hold in the following useful lemma concerning the covering size
function

######  Lemma 4.19.

Let $\mathcal{F}\subset(\mathcal{Y}\cup\\{\star\\})^{\mathcal{X}}$ be a
learnable partial concept class over a finite label space
$\lvert\mathcal{Y}\rvert<\infty$. Define $\lvert\mathcal{Y}\rvert=m$,
$DS_{1}(\mathcal{F})=d$, then we have

$\displaystyle\mathtt{C}_{\mathcal{F}}(n,k)\leq(mn)^{d}\mathtt{C}_{\bar{\mathcal{F}}}(n,k+1)$

######  Proof 4.20.

Let $S\subseteq\mathcal{X}$ be finite of size $n=\lvert S\rvert$, let
$F=\mathcal{F}|_{S}$ and $\bar{F}=\bar{\mathcal{F}}|_{S}$ and let
$\mathcal{H}$ be a $(k+1)$-list covering for $\bar{F}$. We need to show that
$F$ has a $k$-list cover of size $(mn)^{d}|H|$. $H$ is already a cover of $F$
but it consists of $(k+1)$-list functions, thus to construct the desired cover
it is enough to replace each $h\in H$ with some ’sufficiently small’ set of
$k$-list functions that will cover it. Concretely, for any $h\in\mathcal{H}$
we define

$\displaystyle X_{h}=\\{x\in{S}\;:\;y_{\star}\notin h(x)\\}$ $\displaystyle
F_{h}=\\{f|_{X_{h}}\;:\;f(x)\in h(x)\text{ for all }x\in S\\}.$

We now introduce the $k$-list functions that will replace $h$ in the cover of
$F$. For each $y\in\mathcal{Y}$ let $A_{y}$ be some set of size $k$ such that
$y\in A_{y}$, and for every $f\prec h$ define the $k$-list function $h_{f}$ by

$\displaystyle h_{f}(x)=\begin{cases}A_{f(x)}\quad&x\in X_{h},\\\
h(x)\setminus\\{y_{\star}\\}\quad&x\notin X_{h},\end{cases}$

Note that $h_{f}$ is a $k$-list function: indeed for every $x\in X_{h}$ the
set $A_{f(x)}$ has size $k$ and for $x\notin X_{h}$, we have that
$y_{\star}\in h(x)$, the size of $h(x)$ is $k+1$, and hence
$h(x)\setminus\\{y_{\star}\\}$ has size $k$. Now set

$\displaystyle H_{F}=\\{h_{f}\;:\;h\in H,f\in F_{h}\\}.$

We claim that $F\prec H_{F}$. Let $f\in F$. Then, since $H$ covers $\bar{F}$
and $\bar{F}$ disambiguates $F$ there must be some $h\in\mathcal{H}$ such that
$f\prec h$. We show that $f\prec h_{f}$: let $x\in\text{supp}(f)$; if $x\notin
X_{h}$ then $f(x)\in h(x)\setminus\\{y_{\star}\\}=h_{f}(x)$. If $x\in X_{h}$
then $h_{f}(x)=A_{f(x)}$ and hence contains $f(x)$. To bound the size $H_{F}$
note that

$\displaystyle\lvert H_{F}\rvert$ $\displaystyle=\sum_{h\in
H}\lvert\\{f|_{X_{h}}:f\in F,f\prec h\\}\rvert.$

Now notice that $\\{f|_{X_{h}}:f\in F,f\prec h\\}\subseteq\\{f|_{X_{h}}:f\in
F,\text{supp}(f)\subseteq X_{h}\\}$, because $y_{\star}\notin h(x)$ whenever
$x\in X_{h}$. Thus, $\\{f|_{X_{h}}:f\in F,f\prec h\\}$ is a class of total
functions with $k$-DS dimension at most $\mathtt{DS}_{k}(\mathcal{F})=d$ and
hence by the Sauer-Shelah-Perles Lemma:

$\lvert\\{f|_{X_{h}}:f\in F,f\prec
h\\}\rvert\leq\lvert\mathcal{Y}\rvert^{d}\lvert X_{h}\rvert^{d}\leq(mn)^{d},$

implying that

$\displaystyle\mathtt{C}_{\mathcal{F}}(k,n)\leq|\mathcal{H}_{\mathcal{G}}|\leq\sum_{h\in\mathcal{H}}|\mathcal{G}|_{h}|\leq(mn)^{d}|\mathcal{H}|.$

Taking minimum over all possible $\mathcal{H}$ with
$\bar{\mathcal{F}}\prec\mathcal{H}$ gives the desired claim.

######  Theorem (Theorem 1.1 restatement)

There exists a concept class $\mathcal{C}$ over the label space
$\mathcal{Y}=\\{0,1,2\\}$ such that:

  * •

$\mathcal{C}$ is $2$-list PAC learnable.

  * •

$\mathcal{C}$ has no finite $2$-list sample compression scheme.

######  Theorem (Theorem 1.2 restatement)

For any $k>0$ there exists a concept class $\mathcal{C}_{k}$ over a finite
label space $\mathcal{Y}_{k}$ that satisfies the following:

  1. 1.

$\mathcal{C}_{k}$ is $2$-list PAC learnable.

  2. 2.

$\mathcal{C}_{k}$ has no finite $k$-list sample compression scheme.

######  Proof 4.21 (Proof of Theorems 1.1 and 1.2).

Let $\mathcal{F}_{k}$ be the partial concept class given by Lemma 4.17, so
$\mathcal{F}_{k}$ is learnable and
$n^{k}\mathtt{C}_{\mathcal{F}_{k}}(n^{k},k)\geq
n^{\big{(}\log(n)\big{)}^{1-o(1)}}$. Now, set
$\mathcal{C}_{k}=\bar{\mathcal{F}}_{k}$ to be the minimal disambiguation of
$\mathcal{F}_{k}$. We know that $\bar{\mathcal{F}}_{k}$ is $2$-list learnable
since $\mathcal{F}_{k}$ is $1$-list learnable. Now let
$d=\mathtt{DS}_{k}(\mathcal{F}_{k})$ and $m$ be the size of the label space of
$\mathcal{F}_{k}$, then by Lemma 4.19 we have

$\displaystyle(mn)^{d}\mathtt{C}_{\bar{\mathcal{F}_{k}}}(n,k+1)\geq\mathtt{C}_{\mathcal{F}}(n,k)\geq
n^{\big{(}\log(n)\big{)}^{1-o(1)}}.$

for all $n>0$ large enough. Now since the label space of
$\bar{\mathcal{F}}_{k}$ is finite we may use the above with Lemma 4.22 to
deduce that $\bar{\mathcal{F}}_{k}$ is not $(k+1)$-list learnable. We note
that the case $k=1$ gives Theorem 1.1, where we can look at the proof of 4.17
to see that the label space of $\mathcal{F}_{1}$ will be of size $2$ hence the
label space of $\mathcal{C}_{1}=\bar{\mathcal{F}_{1}}$ will be $3$.

####  4.2.4 Proof of Theorem 1.3

##### Free Disambiguation.

Recall the definition of the free disambiguation of a partial concept class.

######  Definition (Definition 3.1 restatement)

Let $\mathcal{C}$ be a partial concept class. For each $c\in\mathcal{C}$ let
$y_{c}$ be a distinct new label. Let $\hat{c}$ denote the completion of $c$
such that $\hat{c}(x)=y_{c}$ whenever $c(x)=\star$. The class
$\hat{\mathcal{C}}=\\{\hat{c}:c\in\mathcal{C}\\}$ is called the free
disambiguation of $\mathcal{C}$.

One can easily verify that for any partial concept class
$\mathcal{C}\subset(\mathcal{Y}\cup\\{\star\\})^{\mathcal{X}}$ its free
disimbaguation $\hat{\mathcal{C}}$ is $k$-list learnable (compressible) if and
only if $\mathcal{C}$ is $k$-list learnable (compressible). Finally, we prove
a short lemma that relates compressibility to polynomial growth of the
covering size function.

######  Lemma 4.22.

For any partial concept class
$\mathcal{F}\subset(\mathcal{Y}\cup\\{\star\\})^{\mathcal{X}}$ that is
$k$-list compressible with a compression scheme of size $d$ we have
$\mathtt{C}_{\mathcal{F}}(n,k)\leq\lvert\mathcal{Y}\rvert^{d}n^{d}$ for all
$n>0$.

######  Proof 4.23.

Let $\mathcal{F}\subset\mathcal{Y}^{\mathcal{X}}$ be such class and without
loss of generality assume that $|\mathcal{X}|=n$ (else we look on
$\mathcal{F}|_{S}$ for some arbitrary $S\subset\mathcal{X}$ of size $n$). Let
$\rho$ be a $k$-list reconstructor of size $d$, so for any $f\in\mathcal{F}$
we have some $S\in(\mathcal{X}\times\mathcal{Y})^{d}$ with $f\prec\rho(S)$.
Hence we can define

$\displaystyle\mathcal{H}=\\{\rho\big{(}S\big{)}\;:\;S\in(\mathcal{X}\times\mathcal{Y})^{d}\\}$

And get that $\mathcal{F}\prec\mathcal{H}$, and clearly
$|\mathcal{H}|=(|\mathcal{X}|\cdot\lvert\mathcal{Y}\rvert)^{d}=(n\lvert\mathcal{Y}\rvert)^{d}$.

######  Proof 4.24 (Proof of Theorem 1.3).

Let $\mathcal{F}_{k}$ be the partial concept class given by Lemma 4.17, so
$\mathcal{F}_{k}$ is learnable and
$n^{k}\mathtt{C}_{\mathcal{F}_{k}}(n^{k},k)\geq
n^{\big{(}\log(n)\big{)}^{1-o(1)}}$. Hence by Lemma 4.22 we have that
$\mathcal{F}_{k}$ has no compression scheme of constant size $d$ for any
$d>0$. Now $\mathcal{C}_{k}=\hat{\mathcal{F}}_{k}$ is the free disambiguation
of $\mathcal{F}_{k}$, and since ${\mathcal{F}}_{k}$ is learnable but not
$k$-list compressible so is $\mathcal{C}_{k}$.

##  5 Uniform Convergence Proofs

In this section we prove Theorem 1.4 and its quantitative parallel Theorem
5.3.

We start by proving Lemma 5.1 which is key to the proof. This lemma relates
the graph dimension of a class to the number of sequences realizable by it.
Then the theorem will follow by an application of the Sauer–Shelah-Perles
lemma for list functions.

######  Lemma 5.1.

Given a $k$-list class $\mathcal{C}\subset{\mathcal{Y}\choose
k}^{\mathcal{X}}$ that $\mathtt{G}_{k}$ shatters $S\in\mathcal{X}^{n}$, we let
$p\in\mathcal{Y}^{n}$ be a pivot and let
$\\{c_{b}\\}_{b\in\\{0,1\\}^{n}}\subset\mathcal{C}|_{S}$ be witnesses for the
shattering, such that $p_{i}\in c_{b}(x_{i})$ if and only if $b_{i}=1$. Denote
by $A_{b}=\\{y\in\mathcal{Y}^{n}\;:\;\forall i\;\;y_{i}\in c_{b}(x_{i})\\}$,
the collection of $c_{b}$ realizable functions. Then we have

$\displaystyle\big{|}\bigcup_{b\in\\{0,1\\}^{n}}A_{b}\big{|}\geq\frac{(2k)^{n}}{4(2k-1)^{n}}k^{n}.$

######  Proof 5.2.

Clearly if $y\in A_{b}\cap A_{b^{\prime}}$ then $y_{i}\in c_{b}(x_{i})\cap
c_{b^{\prime}}(x_{i})$ hence

$\displaystyle|A_{b}\cap A_{b^{\prime}}|\leq\prod_{i=1}^{n}|c_{b}(x_{i})\cap
c_{b^{\prime}}(x_{i})|.$

Now in general we can only know that $|c_{b}(x_{i})\cap
c_{b^{\prime}}(x_{i})|\leq k$ but if $b_{i}\neq b_{i}^{\prime}$ then $p_{i}$
will be in exactly one of $c_{b}(x_{i}),c_{b^{\prime}}$. Hence in that case we
have $|c_{b}(x_{i})\cap c_{b^{\prime}}|\leq k-1$. Now if we denote $d_{H}$ the
Hamming distance $d_{H}(b,b^{\prime})=|\\{i\in[n]\;:\;b_{i}\neq
b_{i}^{\prime}\\}|$ we can use the above to deduce that

$\displaystyle|A_{b}\cap
A_{b^{\prime}}|\leq\prod_{b_{i}=b_{i}^{\prime}}k\cdot\prod_{b_{i}\neq
b_{i}^{\prime}}(k-1)=k^{n-d_{H}(b,b^{\prime})}(k-1)^{d_{H}(b,b^{\prime})}=k^{n}(\frac{k-1}{k})^{d_{H}(b,b^{\prime})}.$

Now we note that for any $I\subset\\{0,1\\}^{n}$ we have by the inclusion-
exclusion principle

$\displaystyle\big{|}\bigcup_{b\in\\{0,1\\}^{n}}A_{b}\big{|}\geq\big{|}\bigcup_{b\in
I}A_{b}\big{|}\geq\sum_{b\in I}|A_{b}|-\sum_{b,b^{\prime}\in I}|A_{b}\cap
A_{b^{\prime}}|\geq k^{n}|I|-\sum_{b,b^{\prime}\in
I}k^{n}(\frac{k-1}{k})^{d_{H}(b,b^{\prime})}.$

So to bound our desired expression we just need to find a large
$I\subset\\{0,1\\}^{n}$ with a large average hamming distance, this is a
standard problem in coding theory, and in our case, a probabilistic approach
will suffice. Fix $m>0$ a constant that will be chosen later and pick $m$
elements from $\\{0,1\\}^{n}$ independently and uniformly, denote them by
$I=\\{B_{i}\\}_{i=1}^{m}$. Note that for any $B,B^{\prime}\in I$ we have that
$d_{H}(B,B^{\prime})=\sum_{i=1}^{n}1_{B_{i}\neq B_{i}^{\prime}}$ is a sum of
independent Bernoulli random variables, hence by simple computation we have

$\displaystyle\mathop{\mathbb{E}}\Big{(}\frac{k-1}{k}\Big{)}^{d_{H}(B,B^{\prime})}=\prod_{i=1}^{n}\mathop{\mathbb{E}}\Big{(}\frac{k-1}{k}\Big{)}^{1_{B_{i}\neq
B_{i}^{\prime}}}=\prod_{i=1}^{n}\Big{(}\frac{1}{2}+\frac{k-1}{2k}\Big{)}=\frac{(2k-1)^{n}}{(2k)^{n}}.$

Form which we get

$\displaystyle\mathop{\mathbb{E}}\Big{[}\sum_{B,B^{\prime}\in
I}k^{n}(\frac{k-1}{k})^{d_{H}(B,B^{\prime})}\Big{]}=k^{n}{m\choose
2}\frac{(2k-1)^{n}}{(2k)^{n}}\leq m^{2}k^{n}\frac{(2k-1)^{n}}{(2k)^{n}}.$

Now putting this back into the inequality we calculated above we can see that

$\displaystyle\big{|}\bigcup_{b\in\\{0,1\\}^{n}}A_{b}\big{|}\geq
mk^{n}-m^{2}k^{n}\frac{(2k-1)^{n}}{(2k)^{n}}$

Now a simple calculation will reveal that the maximal value is attained when
$m=\frac{(2k)^{n}}{2(2k-1)^{n}}$ for which we get the desired inequality

$\displaystyle\big{|}\bigcup_{b\in\\{0,1\\}^{n}}A_{b}\big{|}\geq\frac{(2k)^{n}}{4(2k-1)^{n}}k^{n}.$

######  Theorem 5.3.

Let $\mathcal{C}$ be some $k$-list concept class. Let
$d=\mathtt{DS}_{k}(\mathcal{C})$, $g=\mathtt{G}_{k}(\mathcal{C})$ and
$m=\lvert\mathcal{Y}\rvert$ the size of the label space of $\mathcal{C}$. Then
we have

$\displaystyle 4g^{d}m^{(k+1)d}\geq\big{(}\frac{2k}{2k-1}\big{)}^{g}.$

In particular if $g=\infty$ then so is $d$ as the above can be simplified to

$\displaystyle d=\tilde{\Omega}\Big{(}\frac{g}{k\cdot\ln(g\cdot m)}\Big{)}.$

######  Proof 5.4 (Proof of Theorem 1.4 and 5.3 ).

Let $S\in\mathcal{X}^{g}$ be a sample of size $g$ that is $\mathtt{G}_{k}$
shattered by $\mathcal{C}$. Define
$\mathcal{F}=\mathcal{F}(\mathcal{C}|_{S})=\\{f\in\mathcal{Y}^{g}\;:\;\exists
h\in\mathcal{C}\;,\;f\prec h|_{S}\\}$. By Lemma 5.1 we have that
$|\mathcal{F}|\geq\frac{(2k)^{g}}{4(2k-1)^{g}}k^{g}$, while by Lemma 4.5 we
have that $|\mathcal{F}|\leq k^{g}(gm^{k+1})^{\mathtt{DS}_{k}(\mathcal{F})}$.
Now we note that
$\mathtt{DS}_{k}(\mathcal{C}|_{S})=\mathtt{DS}_{k}(\mathcal{F})$ since a
sample is $\mathcal{C}|_{S}$ realizable if and only if it is $\mathcal{F}$
realizable, from which we may deduce the desired result. Note that Theorems
2.11 and 2.9 which characterize $k$-list learnability and uniform convergence
by the finiteness of DS-k and graph dimension, respectively. Hence We may
deduce Theorem 1.4 immediately from the above.

##  6 Direct Sum and Open Questions

Below we introduce some open questions and research directions that arise from
our study of direct sum. We start by focusing on studying how learning and
uniform convergence rate scale under direct sum. We then ask similar types of
questions for other learning resources as well as on different combinatorial
parameters that arise in learning theory.

###  6.1 Direct Sum of Learning Rates

One of the most natural questions regarding direct sums of learning problems
is the following question: given two learning tasks, can we learn both of them
in a faster way than learning each individuality? Perhaps the simplest case is
of multiple instances of the same learning task. Let $\mathcal{C}$ be a
concept class and recall that for $r\in\mathbb{N}$, the $r$’th power of
$\mathcal{C}$ is denoted by
$\mathcal{C}^{r}=\underbrace{\mathcal{C}\otimes\mathcal{C}\dots\otimes\mathcal{C}}_{r\text{
times }}$.

_How does the learning rate of $\mathcal{C}^{r}$ scale in terms of the
learning rate of $\mathcal{C}$?_

This problem can be investigated with respect to various formulations of
‘learning rate’, for example:

######  Open Question (Open question 1 restatement )

Let $\mathcal{C}\subseteq\mathcal{Y}^{\mathcal{X}}$ be a concept class, and
let $\varepsilon(n|\mathcal{C})$ denote the realizable PAC learning curve of
$\mathcal{C}$ (see Definition 2.2). For $r\in\mathbb{N}$ let
$\mathcal{C}^{r}=\Pi_{i=1}^{r}\mathcal{C}$ be the $r$-fold cartesian power of
$\mathcal{C}$. By a union bound, learning each component independently gives

$\varepsilon(n|\mathcal{C}^{r})\leq r\cdot\varepsilon(n|\mathcal{C}).$

Can the upper bound be asymptotically improved for some classes $\mathcal{C}$?

Another natural version of the above is assuming a fixed marginal distribution
$\mathcal{D}$:

######  Definition 6.1.

Let $\mathcal{D}$ be a fixed distribution over the domain $\mathcal{X}$ and
let $\mathcal{C}$ be a concept class. For any $c:\mathcal{X}\to\mathcal{Y}$
let $\mathcal{D}_{c}$ be the distribution in which
$(x,y)~{}\sim\mathcal{D}_{c}$ satisfies $x\sim\mathcal{D}$ and $y=c(x)$.
Define the fixed-marginal learning curve
$\varepsilon(n|\mathcal{D},\mathcal{C})$ by

$\displaystyle\varepsilon(n|\mathcal{D},\mathcal{C})=\inf_{\mathcal{A}}\sup_{c\in\mathcal{C}}\varepsilon_{n}(\mathcal{D}_{c}|\mathcal{A})$

where the infimum is taken over all learning rules $\mathcal{A}$.

Note that for any $c\in\mathcal{C}$ we have that $\mathcal{D}_{c}$ is a
realizable distribution, hence
$\varepsilon(n|\mathcal{D},\mathcal{C})\leq\varepsilon(n|\mathcal{C})$ always
holds.

For any $r>0$, let $\mathcal{D}^{r}$ be the product measure over
$\mathcal{X}^{r}$.

###### Open Question 2

Similarly to the case of the PAC learning curve, a simple union bound will
give the upper bound

$\displaystyle\varepsilon(n|\mathcal{D}^{r},\mathcal{C}^{r})\leq
r\cdot\varepsilon(n|\mathcal{D},\mathcal{C}).$

Can the upper bound be asymptotically improved for some concept classes
$\mathcal{C}$ and marginal distributions $\mathcal{D}$?

One can ask similar questions about agnostic learning curves and uniform
convergence. However, in these cases the baseline additive upper bound does
not apply. The reason is because these curves concern relative quantities
(indeed, the agnostic learning curve measures the excess loss and uniform
convergence curve measures the maximum difference between the empirical and
population losses).

For instance, given a distribution $\mathcal{D}$ over the product space
$(\mathcal{X}^{2}\times\mathcal{Y}^{2})$ defined with marginal distributions
$\mathcal{D}_{1},\mathcal{D}_{2}$ over $(\mathcal{X}\times\mathcal{Y})$ we
have by the union bound that $\mathtt{L}_{\mathcal{D}}(h_{1}\otimes
h_{2})\leq\mathtt{L}_{\mathcal{D}_{1}}(h_{1})+\mathtt{L}_{\mathcal{D}_{2}}(h_{2})$.
Similarly if
$S=\\{\big{(}(x_{i,1},x_{i,2}),(y_{i,1},y_{i,2})\big{)}\\}_{i=1}^{n}$, letting
$S_{b}=\\{(x_{i,b},y_{i,b})\\}_{i=1}^{n}$, we have
$\mathtt{L}_{S}(h_{1}\otimes
h_{2})\leq\mathtt{L}_{S_{1}}(h_{1})+\mathtt{L}_{S_{2}}(h_{2})$. These bounds,
however, do not allow us to bound the _difference_
$|\mathtt{L}_{D}(h_{1}\otimes h_{2})-\mathtt{L}_{S}(h_{1}\otimes h_{2})|$ as
needed to bound the uniform convergence rate.

###### Open Question 3

Let $\varepsilon_{\mathtt{UC}}(n|\mathcal{C})$ be the uniform convergence
curve of $\mathcal{C}$ (Definition 2.5). How does
$\varepsilon_{\mathtt{UC}}(n|\mathcal{C}^{r})$ scale as a function of
$\varepsilon_{\mathtt{UC}}(n|\mathcal{C})$ and $r$?

A similar phenomenon happens in the case of agnostic learning: define the
agnostic learning curve of a concept class $\mathcal{C}$ by

$\displaystyle\varepsilon_{\mathtt{agn}}(n|\mathcal{C})=\inf_{\mathcal{A}}\sup_{\mathcal{D}}(\mathtt{L}_{\mathcal{D},n}(\mathcal{A})-\mathtt{L}_{\mathcal{D}}(\mathcal{C})),$

where the infimum is taken over all learning rules $\mathcal{A}$, the supremum
is taken over all distributions, and
$\mathtt{L}_{\mathcal{D},n}(\mathcal{A})=\mathop{\mathbb{E}}_{S\sim\mathcal{D}^{n}}[\mathtt{L}_{\mathcal{D}}(\mathcal{A}(S))]$,
and
$\mathtt{L}_{\mathcal{D}}(\mathcal{C})=\inf_{c\in\mathcal{C}}\mathtt{L}_{\mathcal{D}}(c)$.
Here again we do not have simple bounds to the agnostic learning curve of
$\mathcal{C}^{r}$ in terms of the agnostic learning curve of $\mathcal{C}$.

###### Open Question 4

Let $\varepsilon_{\mathtt{agn}}(n|\mathcal{C})$ be the agnostic PAC learning
curve of $\mathcal{C}$. How does
$\varepsilon_{\mathtt{agn}}(n|\mathcal{C}^{r})$ scale as a function of
$\varepsilon_{\mathtt{agn}}(n|\mathcal{C})$ and $r$?

###  6.2 Direct Sum of Learnability Parameters

Another important resource in the context of list learning is the minimal list
size $k$ for which a given class $\mathcal{C}$ is $k$-list PAC learnable. This
raises the following questions:

###### Open Question 5

Let $\mathcal{C}_{1},\mathcal{C}_{2}$ be concept classes and assume $k_{1}$
and $k_{2}$ are the minimal integers such that $\mathcal{C}_{1}$ is
$k_{1}$-list PAC learnable and $\mathcal{C}_{2}$ is $k_{2}$-list PAC
learnable. What is the minimal integer $k$ such that
$\mathcal{C}_{1}\otimes\mathcal{C}_{2}$ is $k$-list PAC learnable? How does it
scale as a function of $k_{1}$ and $k_{2}$.

It is not hard to see that $k\leq k_{1}\cdot k_{2}$ by just learning each
component independently and taking all possible pairs of labels in the
marginal lists. We also show that $k\geq(k_{1}-1)\cdot(k_{2}-1)$ (see Equation
(2) below). However, it remains open to determine tight bounds on $k$.

We raise the parallel question regarding compressibility:

###### Open Question 6

Let $\mathcal{C}_{1},\mathcal{C}_{2}$ be concept classes and assume $k_{1}$
and $k_{2}$ are the minimal integers such that $\mathcal{C}_{1}$ is
$k_{1}$-list compressible and $\mathcal{C}_{2}$ is $k_{2}$-list compressible.
What is the minimal integer $k$ such that
$\mathcal{C}_{1}\otimes\mathcal{C}_{2}$ is $k$-list PAC learnable? How does it
scale as a function of $k_{1}$ and $k_{2}$.

A natural way to approach questions such as the ones above and in Section 6.1
is by analyzing combinatorial parameters that capture the corresponding
resources.

###### Open Question 7

Let $\mathcal{F},\mathcal{G}$ be concept classes, and let
$\mathtt{dim}(\cdot)$ be either the Graph dimension, the Natarajan dimension,
the Littlestone dimension, or the Daniely-Shwartz dimension. How does
$\mathtt{dim}(\mathcal{F}\otimes\mathcal{G})$ scale in terms of
$\mathtt{dim}(\mathcal{F})$ and $\mathtt{dim}(\mathcal{G})$?

We next provide some preliminary results.

######  Proposition 6.2.

Let $\mathtt{d_{N}}(\cdot)$ be the Natarajan dimension, and let $\mathcal{F}$
and $\mathcal{G}$ be concept classes. Then,

$\displaystyle\mathtt{d_{N}}(\mathcal{F})+\mathtt{d_{N}}(\mathcal{G})-2\leq\mathtt{d_{N}}(\mathcal{F}\otimes\mathcal{G})\leq\mathtt{d_{N}}(\mathcal{F})+\mathtt{d_{N}}(\mathcal{G}).$

######  Proof 6.3.

Let $U=\\{u_{i}\\}_{i=1}^{n}$, $V=\\{v_{j}\\}_{j=1}^{m}$ be sets that are
Natarajan shattered by $\mathcal{F}$ and $\mathcal{G}$ respectively so
$\mathcal{F}|_{U}$ and $\mathcal{G}|_{V}$ contains a Cartesian product of the
form

$\displaystyle\prod_{i=1}^{n}\\{f_{i},\tilde{f_{i}}\\}\subset\mathcal{F}|_{U},$
$\displaystyle\prod_{j=1}^{m}\\{g_{j},\tilde{g}_{j}\\}\subset\mathcal{G}|_{V},$

where $f_{i}\neq\tilde{f_{i}}$, $g_{j}\neq\tilde{g_{j}}$ for all $i,j$. Now
define $S=\\{(u_{i},v_{1})\\}_{i=2}^{n}\cup\\{(u_{1},v_{j})\\}_{j=2}^{m}$ and
note that $|S|=|U|+|V|-2$. We claim that $S$ is Natarajan shattered by
$\mathcal{F}\otimes\mathcal{G}$. Indeed,

$\displaystyle\prod_{i=2}^{n}\\{(f_{i},g_{1}),(\tilde{f_{i}},g_{1})\\}\times\prod_{j=2}^{m}\\{(f_{1},g_{j}),(f_{1},\tilde{g_{j}})\\}\subseteq(\mathcal{F}\otimes\mathcal{G})|_{S}.$

Taking supremum over all such $U,V$ we get that
$\mathtt{d_{N}}(\mathcal{F})+\mathtt{d_{N}}(\mathcal{G})-2\leq\mathtt{d_{N}}(\mathcal{F}\otimes\mathcal{G})$.
Now for the other part of the inequality let $S=\\{(u_{i},v_{i})\\}_{i=1}^{n}$
be some set that is Natrajan shattered by $\mathcal{F}\otimes\mathcal{G}$,
meaning that

$\displaystyle\prod_{i=1}^{n}\\{(f_{i},g_{i}),(\tilde{f_{i}},\tilde{g_{i}})\\}\subset\mathcal{F}\otimes\mathcal{G}|_{S}.$

Where $(f_{i},g_{i})\neq(\tilde{f_{i}},\tilde{g_{i}})$ for all $i$, but we can
have $f_{i}=\tilde{f_{i}}$ or $g_{i}=\tilde{g_{i}}$. Now we can define

$\displaystyle
U=\\{u_{i}\;:\;f_{i}\neq\tilde{f_{i}}\\}.V=\\{v_{i}\;:\;g_{i}\neq\tilde{g_{i}}\\}.$

Note that since $(f_{i},g_{i})\neq(\tilde{f_{i}},\tilde{g_{i}})$ we have that
$|U|+|V|\geq n$ and we claim that $U$ and $V$ are Natarajan shattered by
$\mathcal{F}$ and $\mathcal{G}$ respectively. And indeed clearly we have

$\displaystyle\prod_{u_{i}\in
U}\\{(f_{i},\tilde{f_{i}}\\}\subset\mathcal{F}|_{U}.$
$\displaystyle\prod_{v_{i}\in
V}\\{g_{i},\tilde{g_{i}}\\}\subset\mathcal{G}|_{V}.$

By definition of $U$, $V$ we have $f_{i}\neq\tilde{f_{i}}$ for all $i$ such
that $u_{i}\in U$ and $g_{i}\neq\tilde{g_{i}}$ for all $i$ such that $v_{i}\in
V$. Hence we have

$\displaystyle|S|\leq|U|+|V|\leq\mathtt{d_{N}}(\mathcal{F})+\mathtt{d_{N}}(\mathcal{G}).$

Taking supermum over all such $S$ will give the desired result.

######  Proposition 6.4.

Let $\mathtt{LS}(\cdot)$ be the Littlestone dimension, then for any
$\mathcal{F},\mathcal{G}$ concept classes we have

$\displaystyle\mathtt{LS}(\mathcal{F}\otimes\mathcal{G})=\mathtt{LS}(\mathcal{F})+\mathtt{LS}(\mathcal{G})$

######  Proof 6.5.

We use the fact that the Littlestone dimension equals the optimal mistake
bound in deterministic online learning Littlestone and Warmuth (1986). Note
that if $\mathcal{A}_{1}$ is an online learner that makes at most $n_{1}$
mistakes on $\mathcal{F}$ and $\mathcal{A}_{2}$ is an online learner that
makes at most $n_{2}$ mistakes on $\mathcal{G}$ then
$\mathcal{A}_{1}\otimes\mathcal{A}_{2}$ is an online learner that makes at
most $n_{1}+n_{2}$ mistakes on $\mathcal{F}\otimes\mathcal{G}$. Hence using
the equivalence between Littlestone dimension and mistake bound we deduce
$\mathtt{LS}(\mathcal{F}\otimes\mathcal{G})\leq\mathtt{LS}(\mathcal{F})+\mathtt{LS}(\mathcal{G})$.

Now for the other direction let $T_{1}=(V_{1},E_{1})$ be a binary tree that is
Littlestone shattered by $\mathcal{F}$ and let $T_{2}=(V_{2},E_{3})$ be a
binary tree that is Littlestone shattered by $\mathcal{G}$. We will use
$T_{1},T_{2}$ to construct a binary tree $T$ that is shattered by
$\mathcal{F}\otimes\mathcal{G}$, and its depth is the sum of the depths of
$T_{1}$ and $T_{2}$. Our approach is to take a copy of $T_{1}$ and concatenate
a copy of $T_{2}$ to each of its leaves, modifying the vertices as necessary.
Formally, let $r_{2}$ be the root of $T_{2}$ and $L_{1}$ be the set of leaves
of $T_{1}$ and define $T=(V,E)$ by

$\displaystyle V=\\{(v,r_{2})\;:v\in V_{1}\\}\cup\\{(l,v)\;:v\in V_{2},\;l\in
L_{1}\\}$ $\displaystyle E=\\{(v,r_{2})\to(u,r_{2})\;:v\to u\in
E_{1}\\}\cup\\{(l,v)\to(l,u)\;:\;l\in L_{1},\;v\to u\in E_{2}\\}$

So each path $\sigma$ in $T$ is of the form

$(r_{1},r_{2})\to(v_{1},r_{2})\dots\to(v_{n},r_{2})\to(v_{n},u_{1})\dots\to(v_{n},u_{m}),$

where $\sigma_{1}=r_{1}\to v_{1},\dots\to v_{n}$ is a path in $T_{1}$ and
$\sigma_{2}=r_{2}\to u_{1}\dots\to u_{n}$ is a path in $T_{2}$. Hence if
$f\in\mathcal{F}$, $g\in\mathcal{G}$ are the functions that realize the paths
$\sigma_{1},\sigma_{2}$ then $f\otimes g$ realize $\sigma$, implying that $T$
is Littelstone shattered by $\mathcal{F}\otimes\mathcal{G}$, and we can easily
verify that $d(T)=d(T_{1})+d(T_{2})$ where $d(\cdot)$ denote the depth of a
binary tree.

######  Proposition 6.6.

Let $\mathcal{F},\mathcal{G}$ be partial function classes, and let
$k,k^{\prime}\geq 1$. Then we have the following

  1. 1.

$\mathtt{DS}_{k\cdot
k^{\prime}}(\mathcal{F}\otimes\mathcal{G})\geq\min\big{(}\mathtt{DS}_{k}(\mathcal{F}),\mathtt{DS}_{k^{\prime}}(\mathcal{G})\big{)}$.

  2. 2.

$\mathtt{DS}_{\min(k,k^{\prime})}(\mathcal{F}\otimes\mathcal{G})\geq\mathtt{DS}_{k}(\mathcal{F})+\mathtt{DS}_{k^{\prime}}(\mathcal{G}){-1}$.

######  Proof 6.7.

Let $U=\\{u_{i}\\}_{i=1}^{n}$ be a set that is $\mathtt{DS}_{k}$ shattered by
$\mathcal{F}$ and let $V=\\{v_{i}\\}_{i=1}^{m}$ be a set that is
$\mathtt{DS}_{k^{\prime}}$ shattered by $\mathcal{G}$. Without loss of
generality assume that $n\leq m$. Define $S=\\{(u_{i},v_{i})\\}_{i=1}^{n}$ and
notice that if $f$ is a neighbor of $f^{\prime}$ in the $u_{i}$ direction and
$g$ is a neighbor of $g^{\prime}$ in $v_{i}$ direction then $f\otimes g$ is a
neighbor of $f^{\prime}\otimes g^{\prime}$ in the $(u_{i},v_{i})$ direction.
Since each $f\in\mathcal{F}|_{U}$ has $k$ neighbors in each direction, and
each $g\in\mathcal{G}|_{V}$ has $k^{\prime}$ neighbors in each direction we
have that each $f\otimes g\in\mathcal{F}|_{U}\otimes\mathcal{G}|_{S}$ has
$kk^{\prime}$ neighbors in each direction, implying the first claim.

For the second claim, set
$T=\\{(u_{1},v_{i})\\}_{i=2}^{n}\cup\\{(u_{i},v_{1})\\}_{i=2}^{m}\cup\\{(u_{1},v_{1})\\}$.
In a similar way to the above, now $f\otimes g$ is a neighbor of
$f^{\prime}\otimes g$ in the $(u_{i},v_{1})$ direction and of $f\otimes
g^{\prime}$ in the $(u_{1},v_{i})$ direction. So each $f\otimes
g\in\mathcal{F}\otimes\mathcal{G}|_{T}$ has $k$ neighbors in the
$(u_{i},v_{1})$ direction and $k^{\prime}$ neighbors in the $(u_{1},v_{j})$
direction for each $1\leq i\leq n$, $1\leq j\leq m$. From which the second
claim follows.

Note that Proposition 6.6 has direct implications relevant to Open Question 5.
Specifically, it implies that if $\mathcal{F}$ is not $k$-list learnable and
$\mathcal{G}$ is not $k^{\prime}$-list learnable then
$\mathcal{F}\otimes\mathcal{G}$ is not $k\cdot k^{\prime}$-list learnable.
Conversely we know that if $\mathcal{F}$ is $k$-list learnable and
$\mathcal{G}$ is $k^{\prime}$ list learnable then
$\mathcal{F}\otimes\mathcal{G}$ is $k\cdot k^{\prime}$-list learnable. Thus,
letting $K(\mathcal{C})$ denote the minimal $k$ such that a concept class
$\mathcal{C}$ is $k$-list learnable (or infinity if there is no such $k$) we
can summarize the above as

$\displaystyle(K(\mathcal{F})-1)(K(\mathcal{G})-1)\leq
K(\mathcal{F}\otimes\mathcal{G})\leq K(\mathcal{F})\cdot K(\mathcal{G})$ (2)

Note that this result can be seen as parallel with Lemma 4.13 which implies
that if $\mathcal{F}$ is not $k$-list coverable and $\mathcal{G}$ is not
$k^{\prime}$-list coverable then $\mathcal{F}\otimes\mathcal{G}$ is not
$(k+k^{\prime})$-list coverable. It will be interesting to sharpen the latter
result, replacing the $(k+k^{\prime})$ term by $k\cdot k^{\prime}$ like in
Equation 2 above. We may also ask similar questions about compressibility, an
answer to which would be relevant to Open Question 6.

Proposition 6.6 also has implications to Open Question 1 for ($1$-list) PAC
learnable classes. Indeed, let $\mathcal{C}$ be a PAC learnable class. Then,
by Item 2 in Proposition 6.6, it follows that
$\mathtt{DS}_{1}(\mathcal{C}^{r})\geq r\mathtt{DS}_{1}(\mathcal{C})$. Hence,
since the Daniely-Shwartz dimension lower bounds the PAC learning curve
(Charikar and Pabbaraju, 2022) we get

$\displaystyle\varepsilon(n|\mathcal{C}^{r})\geq\frac{{\mathtt{DS}_{1}(\mathcal{C}^{r})}}{n}\geq\frac{{r\cdot\mathtt{DS}_{1}(\mathcal{C}){-r}}}{n}.$

Thus, if it turns out that the realizable PAC learning curve is
$\Theta\bigl{(}\frac{\mathtt{DS}_{1}}{n}\bigr{)}$ then the above in
combination with the naive union bound argument mentioned in Open Question 1
would answer this question up to universal multiplicative constants.

## References

  * Alon et al. (2021) Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran.  A theory of pac learnability of partial concept classes.  _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 658–671, 2021.  URL https://api.semanticscholar.org/CorpusID:236087943.
  * Attias et al. (2022) Idan Attias, Aryeh Kontorovich, and Yishay Mansour.  Improved generalization bounds for adversarially robust learning.  _J. Mach. Learn. Res._ , 23:175:1–175:31, 2022.  URL http://jmlr.org/papers/v23/20-1353.html.
  * Brukhim et al. (2022) Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff.  A characterization of multiclass learnability.  page 13, 2022.  ISBN 9781665455190.  10.1109/FOCS54457.2022.00093.
  * Brukhim et al. (2023) Nataly Brukhim, Steve Hanneke, and Shay Moran.  Improper multiclass boosting.  In Gergely Neu and Lorenzo Rosasco, editors, _The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India_ , volume 195 of _Proceedings of Machine Learning Research_ , pages 5433–5452. PMLR, 2023.  URL https://proceedings.mlr.press/v195/brukhim23a.html.
  * Charikar and Pabbaraju (2022) Moses Charikar and Chirag Pabbaraju.  A characterization of list learnability.  _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , 2022.  URL https://api.semanticscholar.org/CorpusID:253420830.
  * Cheung et al. (2023) TsunMing Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini.  Online learning and disambiguations of partial concept classes.  In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, _50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany_ , volume 261 of _LIPIcs_ , pages 42:1–42:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  10.4230/LIPICS.ICALP.2023.42.  URL https://doi.org/10.4230/LIPIcs.ICALP.2023.42.
  * Daniely et al. (2015) A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz.  Multiclass learnability and the ERM principle.  _Journal of Machine Learning Research_ , 16(12):2377–2404, 2015.
  * Daniely et al. (2011) Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the erm principle.  _J. Mach. Learn. Res._ , 16:2377–2404, 2011.  URL https://api.semanticscholar.org/CorpusID:12851942.
  * David et al. (2016) Ofir David, Shay Moran, and Amir Yehudayoff.  Supervised learning through the lens of compression.  In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain_ , pages 2784–2792, 2016.  URL https://proceedings.neurips.cc/paper/2016/hash/59f51fd6937412b7e56ded1ea2470c25-Abstract.html.
  * Hatami et al. (2023) Hamed Hatami, Kaave Hosseini, and Xiang Meng.  A borsuk-ulam lower bound for sign-rank and its applications.  In Barna Saha and Rocco A. Servedio, editors, _Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023_ , pages 463–471. ACM, 2023.  10.1145/3564246.3585210.  URL https://doi.org/10.1145/3564246.3585210.
  * Lapin et al. (2015) Maksim Lapin, Matthias Hein, and Bernt Schiele.  Loss functions for top-k error: Analysis and insights.  _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1468–1477, 2015.  URL https://api.semanticscholar.org/CorpusID:9657031.
  * Littlestone and Warmuth (1986) N. Littlestone and M. Warmuth.  Relating data compression and learnability.  _Unpublished manuscript_ , 1986.
  * Long (2001) Philip M. Long.  On agnostic learning with {0, *, 1}-valued and real-valued hypotheses.  In David P. Helmbold and Robert C. Williamson, editors, _Computational Learning Theory, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19, 2001, Proceedings_ , volume 2111 of _Lecture Notes in Computer Science_ , pages 289–302. Springer, 2001.  10.1007/3-540-44581-1_19.  URL https://doi.org/10.1007/3-540-44581-1_19.
  * Moran and Yehudayoff (2016) S. Moran and A. Yehudayoff.  Sample compression schemes for VC classes.  _Journal of the ACM_ , 63(3):1–10, 2016.
  * Moran et al. (2023) Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili.  List online classification.  In Gergely Neu and Lorenzo Rosasco, editors, _The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India_ , volume 195 of _Proceedings of Machine Learning Research_ , pages 1885–1913. PMLR, 2023.  URL https://proceedings.mlr.press/v195/moran23a.html.
  * Pabbaraju (2023) Chirag Pabbaraju.  Multiclass learnability does not imply sample compression, 2023.
  * Pankratov (2012) Denis Pankratov.  Direct sum questions in classical communication complexity.  _Master’s thesis, University of Chicago_ , 2012.
  * Rao and Yehudayoff (2020) Anup Rao and Amir Yehudayoff.  _Bibliography_ , page 244–249.  Cambridge University Press, 2020.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, USA, 2014.  ISBN 1107057132.
  * Shalev-Shwartz et al. (2010) Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Learnability, stability and uniform convergence.  _Journal of Machine Learning Research_ , 11(90):2635–2670, 2010.  URL http://jmlr.org/papers/v11/shalev-shwartz10a.html.
  * Wigderson (2019) A. Wigderson.  _Mathematics and Computation: A Theory Revolutionizing Technology and Science_.  Princeton University Press, 2019.  ISBN 9780691189130.  URL https://books.google.co.il/books?id=-WCqDwAAQBAJ.
  * Yan et al. (2018) Caixia Yan, Minnan Luo, Huan Liu, Zhihui Li, and Qinghua Zheng.  Top-k multi-class svm using multiple features.  _Information Sciences_ , 432:479–494, 2018.  ISSN 0020-0255.  https://doi.org/10.1016/j.ins.2017.08.004.  URL https://www.sciencedirect.com/science/article/pii/S0020025517308642.