# On the Learnability of Multilabel Ranking

Vinod Raman, Unique Subedi, Ambuj Tewari

###### Abstract

Multilabel ranking is a central task in machine learning with widespread
applications to web search, news stories, recommender systems, etc. However,
the most fundamental question of learnability in a multilabel ranking setting
remains unanswered. In this paper, we characterize the learnability of
multilabel ranking problems in both the batch and online settings for a large
family of ranking losses. Along the way, we also give the first equivalence
class of ranking losses based on learnability.

Keywords: Multilabel Ranking, PAC Learnability, Online Learning

##  1 Introduction

Learning-to-rank, henceforth referred to as multilabel ranking, is a
supervised learning problem where a learner is presented with an instance
$x\in\mathcal{X}$ and is required to output a ranking of $K$ different labels
in decreasing order of relevance to $x$. This is in contrast with multilabel
classification where given an instance $x\in\mathcal{X}$, the learner is
tasked with predicting a subset of the $K$ labels without any explicit
ordering. Multilabel ranking is a canonical learning problem with a wide range
of applications to web search, news stories, recommender systems, social
networks, and bioinformatics (Chapelle and Chang, 2011; Hong et al., 2012;
Agarwal, 2010; Karatzoglou et al., 2013; Vargas and Castells, 2011; Leaman et
al., 2013). Recent years has seen a surge in research in developing practical
methods for multilabel ranking as well as proving generalization bounds for
specific model classes (Liu et al., 2009; Severyn and Moschitti, 2015; Burges
et al., 2005; Cao et al., 2007; Ramaswamy et al., 2015; Tewari and Chaudhuri,
2015; Chaudhuri and Tewari, 2015). Despite the vast literature on ranking, the
most fundamental question of when a multilabel ranking problem is learnable
remains unanswered.

In statistical learning theory, the learnability of a hypothesis class is
often characterized in terms of a complexity measure. For instance, the VC
dimension characterizes the learnability of binary hypothesis classes (Vapnik
and Chervonenkis, 1974), and the Natarajan dimension characterizes the
learnability of multiclass hypothesis classes Ben-David et al. (1992). Closing
multiclass learnability, Brukhim et al. (2022) show that the Daniely-Shwartz
(DS) dimension, originally proposed by Daniely and Shalev-Shwartz (2014),
characterizes multiclass learnability even when the label space is unbounded.
In the online setting, the Littlestone dimension (Littlestone, 1987)
characterizes the online learnability of a binary hypothesis class and the
Multiclass Littlestone dimension (Daniely et al., 2011) characterizes the
online learnability of a multiclass hypothesis class. Unlike binary and
multiclass classification, a distinguishing property of multilabel ranking is
the mismatch between the prediction of the learner and the label it receives
as feedback. In particular, a learner is required to produce a permutation
that ranks the relevance of the labels, but only receives a relevance score
vector as feedback. This mismatch creates a barrier for the characterizations
of learnability in binary and multiclass classification to extend to the
multilabel ranking. Accordingly, to our best knowledge, no such
characterization of ranking learnability has been proposed in literature.

In this paper, we close this gap by characterizing the learnability of ranking
hypothesis classes $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$, where
$\mathcal{S}_{K}$ is the set of all permutations over $[K]=\\{1,...,K\\}$. We
first show that a ranking hypothesis class $\mathcal{H}$ embeds $K^{2}$
different binary hypothesis classes $\mathcal{H}_{i}^{j}$ for $i,j\in[K]$,
where hypotheses in $\mathcal{H}_{i}^{j}$ answer whether the label $i$ should
be ranked in the top $j$ or not. Our main result then states that a ranking
hypothesis class is learnable if and only if a sufficient number of these
$K^{2}$ binary hypothesis classes are learnable. We prove a version of this
result for both batch and online learning settings for different families of
ranking loss functions that capture most, if not all, ranking losses used in
practice. By relating the learnability of $\mathcal{H}$ to the learnability of
binary hypothesis classes $\mathcal{H}_{i}^{j}$, we show that existing
combinatorial dimensions, like the VC and Littlestone dimension, continue to
characterize learnability in the multilabel ranking setting. Finally, as an
application of our characterization, we provide dimension-based sufficient
conditions under which score-based ranking hypothesis classes are learnable.

A unifying theme throughout both learning settings is our ability to
constructively convert a learning algorithm $\mathcal{A}$ for $\mathcal{H}$
into a learning algorithm $\mathcal{A}^{j}_{i}$ for $\mathcal{H}_{i}^{j}$ for
each $i,j\in[K]$ and vice versa. To do so, our proof techniques involve
adapting the agnostic-to-realizable reduction for batch and online
classification, proposed by Hopkins et al. (2022) and Raman et al. (2023)
respectively, to the ranking setting.

##  2 Preliminaries and Notation

Let $\mathcal{X}$ denote the instance space, $\mathcal{S}_{K}$ the set of
permutations over $[K]:=\\{1,...,K\\}$, and $\mathcal{Y}=\\{0,1,...,B\\}^{K}$
the target space for some $K,B\in\mathbbm{N}$. We will often refer to an
element $y\in\mathcal{Y}$ as a relevance-score vector that indicates the
relevance of each of the $K$ labels. Throughout the paper, we will slightly
abuse notation by also treating a permutation $\pi\in\mathcal{S}_{K}$ as a
vector in $\\{1,...,K\\}^{K}$. This allows us to define loss functions that
perform vector operations on $\pi$. For a relevance-score vector
$y\in\mathcal{Y}$, let $y^{m}$ denote the relevance of the $m$’th label. For a
permutation $\pi\in\mathcal{S}_{K}$, let $\pi_{i}\in[K]$ denote the rank of
the $i$’th label. Using this notation, we can define different notions of
equivalence between two permutations $\pi,\hat{\pi}\in\mathcal{S}_{K}$. We say
that $\pi=\hat{\pi}$ iff for all $i\in[K]$, $\pi_{i}=\hat{\pi}_{i}$. On the
other hand, we say $\pi\stackrel{{\scriptstyle p}}{{=}}\hat{\pi}$ iff
$\\{i:\pi_{i}\leq p\\}=\\{i:\hat{\pi}_{i}\leq p\\}$. That is, two permutations
are $p$-equivalent if the set of labels they rank in the top-$p$ are equal.
Finally, we say $\pi\stackrel{{\scriptstyle[p]}}{{=}}\hat{\pi}$ iff for all
$j\in[p]$, $\\{i:\pi_{i}\leq j\\}=\\{i:\hat{\pi}_{i}\leq j\\}$. That is, two
permutations are $[p]$-equivalent if not only the set but also the order of
labels they rank in the top-$p$ are equal. Given any permutation
$\pi\in\mathcal{S}_{K}$, it will also be useful to define a mapping onto the
set of binary strings $\\{0,1\\}^{K}$. In particular, we define
$\text{BinRel}(\cdot,\cdot):\mathcal{S}_{K}\times[K]\rightarrow\\{0,1\\}^{K}$
as an operator that given a permutation $\pi\in\mathcal{S}_{K}$ and integer
$p\in[K]$, outputs a bit string $b\in\\{0,1\\}^{K}$ s.t.
$b[i]=\mathbbm{1}\\{\pi_{i}\leq p\\}.$

A ranking hypothesis $h:\mathcal{X}\rightarrow\mathcal{S}_{K}$ maps instances
in $\mathcal{X}$ to a permutation in $\mathcal{S}_{K}$. Given an instance
$x\in\mathcal{X}$, one can think of $h(x)$ as $h$’s ranking of the $K$
different labels in decreasing order of relevance. For any ranking hypothesis
$h$, let $h_{i}:\mathcal{X}\rightarrow[K]$ denote its restriction to the
$i$’th coordinate output. Accordingly, for an instance $x\in\mathcal{X}$,
$h_{i}(x)$ gives the rank that $h$ assigns to the $i$’th label.

In this paper, we study the learnability of an arbitrary ranking hypothesis
class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ under different
ranking loss functions, which we denote generally by
$\ell:\mathcal{S}_{K}\times\mathcal{Y}\rightarrow\mathbbm{R}_{\geq 0}$. For
any unlabeled sample $S_{U}=\\{x_{1},...,x_{n}\\}$, we let
$\mathcal{H}_{|{S_{U}}}$ denote the restriction of $\mathcal{H}$ onto $S_{U}$.
That is, $\mathcal{H}_{|{S_{U}}}\subseteq\mathcal{H}$ is the subset of
hypothesis in $\mathcal{H}$ which uniquely label $S_{U}$. Given a ranking
hypothesis class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$, for every
$i,j\in[K]$, define its binary threshold-restricted hypothesis class
$\mathcal{H}_{i}^{j}=\\{h_{i}^{j}|h\in\mathcal{H}\\}$ where
$h_{i}^{j}:\mathcal{X}\rightarrow\\{0,1\\}$ is defined as
$h_{i}^{j}(x)=\mathbbm{1}\\{h_{i}(x)\leq j\\}$. We can think of a hypothesis
in $\mathcal{H}_{i}^{j}$ as providing binary responses to queries of the form:
“for instance $x$, is label $i$ in the top $j$ ranks”? These threshold-
restricted classes are central to our characterization of learnability.

###  2.1 Batch Setting

In the batch setting, we are interested in characterizing the learnability of
an arbitrary ranking hypothesis class $\mathcal{H}$ under a model similar to
the classical PAC setting (Valiant, 1984). While in traditional supervised
learning the range space of the hypothesis class matches the label space, this
is not the case for ranking with relevance-score feedback. Indeed, while the
range space of a ranking hypothesis class is the set of all permutations
$\mathcal{S}_{K}$, the target space $\mathcal{Y}=\\{0,1,...,B\\}^{K}$ is the
set of all relevance-score vectors. Thus, a unique challenge in characterizing
the learnability of ranking is figuring out how to handle this mismatch in
prediction and feedback. We now formally define the notion of ranking
learnability under relevance-score feedback in the batch setting.

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

A ranking hypothesis class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$
is agnostic PAC learnable w.r.t. loss
$\ell:\mathcal{S}_{K}\times\mathcal{Y}\to\mathbb{R}_{\geq 0}$, if there exists
a function $m:(0,1)^{2}\to\mathbb{N}$ and a learning algorithm
$\mathcal{A}:(\mathcal{X}\times\mathcal{Y})^{\star}\to\mathcal{S}_{K}^{\mathcal{X}}$
with the following property: for every $\epsilon,\delta\in(0,1)$ and for every
distribution $\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$, running
algorithm $\mathcal{A}$ on $n\geq m(\epsilon,\delta)$ iid samples from
$\mathcal{D}$ outputs a predictor $g=\mathcal{A}(S)$ such that with
probability at least $1-\delta$ over $S\sim\mathcal{D}^{n}$,

$\operatorname{\mathbb{E}}_{\mathcal{D}}[\ell(g(x),y)]\leq\inf_{h\in\mathcal{H}}\operatorname{\mathbb{E}}_{\mathcal{D}}[\ell(h(x),y)]+\epsilon.$

Note that we do not require the output predictor $\mathcal{A}(S)$ to be in
$\mathcal{H}$, but only require $\mathcal{A}(S)$ to compete with the best
predictor in $\mathcal{H}$. If $\mathcal{D}$ is further restricted to the
class of distributions such that
$\inf_{h\in\mathcal{H}}\operatorname{\mathbb{E}}_{\mathcal{D}}[\ell(h(x),y)]=0$,
then we get realizable ranking PAC learnability.

Since many of the ranking losses we consider map to values in $\mathbbm{R}$,
the empirical Rademacher complexity will be a useful tool for proving
learnability in the batch setting.

######  Definition 2 (Empirical Rademacher Complexity of Loss Class).

Let $\mathcal{D}$ be a distribution over $\mathcal{X}\times\mathcal{Y}$, and
let $\ell(h,(x,y))$ be a loss function. Let
$S=\\{(x_{1},y_{1}),...,(x_{n},y_{n})\\}$ be a set of examples drawn i.i.d
from $\mathcal{D}$ and
$\mathcal{F}=\\{(x,y)\mapsto\ell(h,(x,y)):h\in\mathcal{H}\\}$ be a loss class.
The empirical Rademacher complexity of $\mathcal{F}$ is defined as

$\hat{\mathfrak{R}}_{n}(\mathcal{F})=\mathbbm{E}_{\sigma}\left[\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(x_{i},y_{i})\right)\right]$

where $\sigma_{1},...,\sigma_{n}$ are independent _Rademacher_ random
variables, random variables uniformly distributed over $\\{-1,1\\}$.

In particular, a standard result relates the empirical Rademacher complexity
to the generalization error of hypotheses in $\mathcal{H}$ with respect to a
real-valued bounded loss function $\ell(h(x),y)$ (Bartlett and Mendelson,
2002).

######  Proposition 2.1 (Rademacher-based Uniform Convergence).

Let $\ell(h,(x,y))\leq c$ be a bounded loss function. With probability at
least $1-\delta$ over the sample $S\sim\mathcal{D}^{m}n$, for all
$h\in\mathcal{H}$ simultaneously,

$\left|\mathbbm{E}_{\mathcal{D}}[\ell(h(x),y)]-\hat{\mathbbm{E}}_{S}[\ell(h(x),y)]\right|\leq
2\hat{\mathfrak{R}}_{n}(\mathcal{F})+O\left(c\sqrt{\frac{\ln(\frac{1}{\delta})}{n}}\right)$

where $\hat{\mathbbm{E}}_{S}[\ell(h,(x,y))]=\frac{1}{|S|}\sum_{(x,y)\in
S}\ell(h,(x,y))$ is the empirical average of the loss over $S$.

When the empirical Rademacher complexity of the loss class
$\mathcal{F}=\\{(x,y)\mapsto\ell(h,(x,y)):h\in\mathcal{H}\\}$ is $o(1)$, we
often state that $\mathcal{H}$ enjoys the uniform convergence property w.r.t
$\ell$. When $\mathcal{H}$ enjoys the uniform convergence property w.r.t
$\ell$, a standard result shows that $\mathcal{H}$ is learnable according to
Definition 1 via Empirical Risk Minimization (ERM) (see Theorem 26.5 in
Shalev-Shwartz and Ben-David (2014)).

###  2.2 Online Setting

In the online setting, an adversary plays a sequential game with the learner
over $T$ rounds. In each round $t\in[T]$, an adversary selects a labeled
instance $(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$ and reveals $x_{t}$ to
the learner. The learner makes a (potentially randomized) prediction
$\hat{\pi}_{t}\in\mathcal{S}_{K}$. Finally, the adversary reveals the true
relevance score $y_{t}$, and the learner suffers the loss
$\ell(\hat{\pi}_{t},y_{t})$, where $\ell$ is some pre-specified ranking loss
function. Given a ranking hypothesis class
$\mathcal{H}\subseteq\mathcal{S}_{K}^{\mathcal{X}}$, the goal of the learner
is to output predictions $\hat{\pi}_{t}$ such that its cumulative loss is
close to the best possible cumulative loss over hypothesis in $\mathcal{H}$. A
hypothesis class is online learnable if there exists an algorithm such that
for any sequence of labeled examples $(x_{1},y_{1}),...,(x_{T},y_{T})$, the
difference in cumulative loss between its predictions and the predictions of
the best possible function in $\mathcal{H}$ is small.

######  Definition 3 (Online Ranking Learnability).

A ranking hypothesis class $\mathcal{H}\subseteq\mathcal{S}_{K}^{\mathcal{X}}$
is online learnable w.r.t. loss $\ell$, if there exists an (potentially
randomized) algorithm $\mathcal{A}$ such that for any adaptively chosen
sequence of labeled examples $(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$,
the algorithm outputs $\mathcal{A}(x_{t})\in\mathcal{S}_{K}$ at every
iteration $t\in[T]$ such that

$\mathbb{E}\left[\sum_{t=1}^{T}\ell(\mathcal{A}(x_{t}),y_{t})-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(h(x_{t}),y_{t})\right]\leq
R(T)$

where the expectation is taken w.r.t. the randomness of $\mathcal{A}$ and that
of the possibly adaptive adversary, and
$R(T):\mathbb{N}\rightarrow\mathbb{R}^{+}$ is the additive regret: a non-
decreasing, sub-linear function of $T$.

If it is further guaranteed that there always exists a hypothesis
$h^{\star}\in\mathcal{H}$ such that
$\sum_{t=1}^{T}\ell(h^{\star}(x_{t}),y_{t})=0$, then we say we are in the
realizable setting.

##  3 Ranking Loss Families

Unlike the 0-1 loss in classification, there is no canonical loss function in
multilabel ranking. In this section, we define two general families of loss
functions. In Appendix A, we show that many of the ranking losses used in
practice fall into one of these two families.

At the highest-level, we can classify ranking losses into two main groups: (A)
those losses that care about both the order and magnitude of the relevance-
scores within the top-$p$ ranked labels and (B) those losses that only care
about the magnitude of the relevance-scores within the top-$p$ ranked labels.
Our goal will be to define a loss family for both group A and B. To do so, we
start by identifying a canonical ranking loss that lies in each group. For
group A, the normalized sum loss@p,

$\ell^{@p}_{\text{sum}}(\pi,y)=\sum_{i=1}^{K}\min(\pi_{i},p+1)y_{i}-Z^{p}_{y}$

captures both the order and magnitude of the relevance-scores only for the
top-$p$ ranked labels. Here, $Z^{p}_{y}$ is an appropriately chosen
normalization factor s.t
$\min_{\pi\in\mathcal{S}_{K}}\ell^{@p}_{\text{sum}}(\pi,y)=0$ and only depends
on $p$ and $y$. For Group B, the normalized precision loss@p,

$\ell^{@p}_{\text{prec}}(\pi,y)=Z^{p}_{y}-\sum_{i=1}^{K}\mathbbm{1}\\{\pi_{i}\leq
p\\}y_{i}$

cares only about the magnitude of relevance-scores in the top-$p$ ranked
labels. Again, $Z^{p}_{y}$ is an appropriately chosen normalization constant
that only depends on $p$ and $y$ such that the minimum loss is $0$. Next, we
build loss families around $\ell_{\text{sum}}^{@p}$ and
$\ell_{\text{prec}}^{@p}$. For $\ell_{\text{sum}}^{@p}$, consider the family:

$\mathcal{L}(\ell^{@p}_{\text{sum}})=\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\ell=0\text{
iff
}\ell_{\text{sum}}^{@p}=0\\}\cap\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\pi\stackrel{{\scriptstyle[p]}}{{=}}\hat{\pi}\implies\ell(\pi,y)=\ell(\hat{\pi},y)\\}.$

By definition, $\mathcal{L}(\ell^{@p}_{\text{sum}})$ contains those ranking
losses that are (1) zero-matched with $\ell^{@p}_{\text{sum}}$ and (2) remain
unchanged for any two predicted permutations that are $[p]$-equivalent. Note
that $\ell^{@p}_{\text{sum}}\in\mathcal{L}(\ell^{@p}_{\text{sum}})$. Likewise,
we can construct a similar loss family around $\ell^{@p}_{\text{prec}}$ as
follows:

$\mathcal{L}(\ell^{@p}_{\text{prec}})=\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\ell=0\text{
iff
}\ell_{\text{prec}}^{@p}=0\\}\cap\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\pi\stackrel{{\scriptstyle
p}}{{=}}\hat{\pi}\implies\ell(\pi,y)=\ell(\hat{\pi},y)\\}.$

$\mathcal{L}(\ell^{@p}_{\text{prec}})$ contains those ranking losses that are
(1) zero-matched with $\ell^{@p}_{\text{prec}}$ and (2) remain unchanged for
any two predicted permutations that are _$p$ -equivalent_. Again,
$\ell^{@p}_{\text{prec}}\in\mathcal{L}(\ell^{@p}_{\text{prec}})$. The two loss
families, $\mathcal{L}(\ell^{@p}_{\text{sum}})$ and
$\mathcal{L}(\ell^{@p}_{\text{prec}})$ precisely capture the desired
characteristics of losses in group A and group B respectively. While losses in
$\mathcal{L}(\ell^{@p}_{\text{sum}})$ care about both the order and magnitude
of the relevance-scores within the top-$p$ ranked labels, the losses in
$\mathcal{L}(\ell^{@p}_{\text{prec}})$ only care about the magnitude of the
relevance-scores within the top-$p$ labels. In fact, a major contribution of
this paper is showing that both $\mathcal{L}(\ell^{@p}_{\text{sum}})$ and
$\mathcal{L}(\ell^{@p}_{\text{prec}})$ are actually equivalence classes - the
same characterization of learnability holds for every loss in that family.

##  4 Batch Multilabel Ranking

In this section, we characterize the agnostic PAC learnability of hypothesis
classes $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ with respect to both
$\mathcal{L}(\ell^{@p}_{\text{sum}})$ and
$\mathcal{L}(\ell^{@p}_{\text{prec}})$. Our main results, stated below as two
theorems, relate the learnability of $\mathcal{H}$ to the learnability of the
threshold-restricted classes $\mathcal{H}_{i}^{j}$.

######  Theorem 4.1.

A hypothesis class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is
agnostic PAC learnable w.r.t $\ell\in\mathcal{L}(\ell^{@p}_{\text{sum}})$ if
and only if for all $(i,j)\in[K]\times[p]$, $\mathcal{H}_{i}^{j}$ is agnostic
PAC learnable w.r.t the 0-1 loss.

######  Theorem 4.2.

A hypothesis class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is
agnostic PAC learnable w.r.t $\ell\in\mathcal{L}(\ell^{@p}_{\text{prec}})$ if
and only if for all $i\in[K]$, $\mathcal{H}_{i}^{p}$ is agnostic PAC learnable
w.r.t the 0-1 loss.

The proof of Theorem 4.2 follows exactly the same way as Theorem 4.1 with some
minor changes. Thus, we focus on proving Theorem 4.1 in this section and defer
all discussion of Theorem 4.2 to Appendix C.2.

We prove Theorem 4.1 in three parts. First, we show that if for all
$(i,j)\in[K]\times[p]$, $\mathcal{H}_{i}^{j}$ is agnostic PAC learnable w.r.t
0-1 loss, then $\mathcal{H}$ is agnostic PAC learnable w.r.t
$\ell_{\text{sum}}^{@p}$. Next, we show that if $\mathcal{H}$ is agnostic PAC
learnable w.r.t $\ell_{\text{sum}}^{@p}$, then $\mathcal{H}$ is agnostic PAC
learnable w.r.t any loss $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$.
Finally, we prove the necessity direction - if $\mathcal{H}$ is agnostic PAC
learnable w.r.t an arbitrary $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$,
then for all $(i,j)\in[K]\times[p]$, $\mathcal{H}_{i}^{j}$ is agnostic PAC
learnable w.r.t 0-1 loss.

We begin with Lemma 4.3, which asserts that agnostic PAC learnability of
$\mathcal{H}_{i}^{j}$ for all $(i,j)\in[K]\times[p]$ implies agnostic PAC
learnability of $\mathcal{H}$ w.r.t $\ell_{\text{sum}}^{@p}$.

######  Lemma 4.3.

A function class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is PAC
learnable w.r.t $\ell_{\text{sum}}^{@p}$ if for all $(i,j)\in[K]\times[p]$,
$\mathcal{H}_{i}^{j}$ is PAC learnable w.r.t the 0-1 loss.

###### Proof.

Let $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ be an arbitrary ranking
hypothesis class. We need to show that if $\mathcal{H}_{i}^{j}$ is agnostic
PAC learnable w.r.t to 0-1 loss for all $(i,j)\in[K]\times[p]$, then
$\mathcal{H}$ is agnostic PAC learnable w.r.t $\ell_{\text{sum}}^{@p}$. By
Proposition 2.1, it suffices to show that the empirical Rademacher complexity
of the loss class $\ell_{\text{sum}}^{@p}\circ\mathcal{H}$ is sublinear in the
sample size $n$. This will imply that $\ell_{\text{sum}}^{@p}$ enjoys the
uniform convergence property, and therefore ERM is an agnostic PAC learner for
$\mathcal{H}$ w.r.t $\ell_{\text{sum}}^{@p}$. By definition, we have that

$\displaystyle\mathfrak{R}_{n}(\ell_{\text{sum}}^{@p}\circ\mathcal{H})$
$\displaystyle=\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\ell_{\text{sum}}^{@p}(h(x_{i}),y_{i}))\right]$
$\displaystyle=\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\left(\sum_{m=1}^{K}\sigma_{i}\min(h_{m}(x_{i}),p+1)y^{m}_{i}-\sigma_{i}Z_{y_{i}}^{p}\right)\right]$
$\displaystyle=\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sum_{m=1}^{K}\sigma_{i}\min(h_{m}(x_{i}),p+1)y^{m}_{i}\right]$
$\displaystyle\leq\sum_{m=1}^{K}\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\min(h_{m}(x_{i}),p+1)y^{m}_{i}\right]=\sum_{m=1}^{K}\mathfrak{R}_{n}(\ell\circ\mathcal{H}_{m})$

where $\ell(h(x),y)=\min(h(x),p+1)y$ and
$\mathcal{H}_{m}=\\{h_{m}:h\in\mathcal{H}\\}$. Note that $\ell(h(x),y)$ is a
$B$-Lipschitz function of $\min(h(x),p+1)$ since $y_{i}^{m}\leq B$ for all
$i,m$. Therefore, by Talagrand’s Contraction Lemma Ledoux and Talagrand
(1991), $\mathfrak{R}_{n}(\ell\circ\mathcal{H}_{m})\leq
B\mathfrak{R}_{n}(\mathcal{H}_{m})$. Substituting in, we have that

$\mathfrak{R}_{n}(\ell^{@p}_{\text{sum}}\circ\mathcal{H})\leq\sum_{m=1}^{K}\mathfrak{R}_{n}(\ell\circ\mathcal{H}_{m})\\\
\leq\sum_{m=1}^{K}B\mathfrak{R}_{n}(\mathcal{H}_{m})=B\sum_{m=1}^{K}\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h_{m}\in\mathcal{H}_{m}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\min(h_{m}(x_{i}),p+1)\right]$

Next note that
$\min(h_{m}(x_{i}),p+1)=(p+1)-\sum_{j=1}^{p}\mathbbm{1}\\{h_{m}(x_{i})\leq
j\\}=(p+1)-\sum_{j=1}^{p}h_{m}^{j}(x_{i})$. Substituting and getting rid of
constant factors, we have that

$\displaystyle\mathfrak{R}_{n}(\ell^{@p}_{\text{sum}}\circ\mathcal{H})$
$\displaystyle\leq B\sum_{m=1}^{K}\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h_{m}\in\mathcal{H}_{m}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\sum_{j=1}^{p}h_{m}^{j}(x_{i})\right]$
$\displaystyle\leq B\sum_{m=1}^{K}\sum_{j=1}^{p}\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h_{m}\in\mathcal{H}_{m}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}h_{m}^{j}(x_{i})\right]$
$\displaystyle=B\sum_{m=1}^{K}\sum_{j=1}^{p}\mathfrak{R}_{n}(\mathcal{H}_{m}^{j}).$

Since for all $(m,j)\in[K]\times[p]$, $\mathcal{H}_{m}^{j}$ is agnostic PAC
learnable w.r.t 0-1 loss, by Theorem 6.5 in Shalev-Shwartz and Ben-David
(2014), $d_{m}^{j}=\text{VC}(\mathcal{H}_{m}^{j})<\infty$. By standard VC
arguments, it follows that $\mathfrak{R}_{n}(\mathcal{H}_{m}^{j})\leq
O\left(\sqrt{\frac{d_{m}^{j}\ln(\frac{n}{d_{m}^{j}})}{n}}\right)$. Putting
things together, we have that
$\mathfrak{R}_{n}(\ell_{\text{sum}}^{@p}\circ\mathcal{H})\leq
O(B\sum_{m=1}^{K}\sum_{j=1}^{p}\sqrt{\frac{d_{m}^{j}\ln(\frac{n}{d_{m}^{j}})}{n}})$.
Since $K$ is finite,
$\mathfrak{R}_{n}(\ell_{\text{sum}}^{@p}\circ\mathcal{H})$ vanishes as $n$
becomes large. By Proposition 2.1, this implies that $\ell_{\text{sum}}^{@p}$
enjoys the uniform convergence property, and therefore ERM using
$\ell_{\text{sum}}^{@p}$ is an agnostic PAC learner for $\mathcal{H}$. ∎

Next, Lemma 4.4 extends the learnability of $\ell_{\text{sum}}^{@p}$ to the
learnability of any loss $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$. In
particular, Lemma 4.4 asserts that if $\mathcal{H}$ is agnostic PAC learnable
w.r.t $\ell_{\text{sum}}^{@p}$ then $\mathcal{H}$ is also agnostic PAC
learnable w.r.t any $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$.

######  Lemma 4.4.

Let $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$. A function class
$\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is agnostic PAC learnable
w.r.t $\ell$ if $\mathcal{H}$ is agnostic PAC learnable w.r.t
$\ell_{\text{sum}}^{@p}$.

###### Proof.

Fix $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$. Let
$b=\max_{\pi,y}\ell(\pi,y)$ and $a=\min_{\pi,y\text{ s.t
}\ell(\pi,y)>0}\ell(\pi,y)$. We need to show that if $\mathcal{H}$ is agnostic
PAC learnable w.r.t $\ell_{\text{sum}}^{@p}$, then $\mathcal{H}$ is agnostic
PAC learnable w.r.t $\ell$. We will do so in two steps. First, we will show
that if $\mathcal{A}$ is an agnostic PAC learner for $\ell_{\text{sum}}^{@p}$,
then $\mathcal{A}$ is also a realizable PAC learner for $\ell$. Next, we will
show how to convert a realizable PAC learner for $\ell$ into an agnostic PAC
learner for $\ell$ in a black-box fashion. The composition of these two pieces
yields an agnostic PAC learner for $\mathcal{H}$ w.r.t $\ell$.

If $\mathcal{H}$ is agnostic PAC learnable w.r.t $\ell_{\text{sum}}^{@p}$,
there there exists a learning algorithm $\mathcal{A}$ with sample complexity
$m(\epsilon,\delta,K)$ s.t. for any distribution $\mathcal{D}$ over
$\mathcal{X}\times\mathcal{Y}$, with probability $1-\delta$ over a sample
$S\sim\mathcal{D}^{n}$ of size $n\geq m(\epsilon,\delta,K)$,

$\mathbbm{E}_{\mathcal{D}}\left[\ell_{\text{sum}}^{@p}(\mathcal{A}(S),(x,y))\right]\leq\inf_{h\in\mathcal{H}}\mathbbm{E}_{\mathcal{D}}\left[\ell_{\text{sum}}^{@p}(h,(x,y))\right]+\epsilon.$

In the realizable setting, we are further guaranteed that there exists a
hypothesis $h^{\star}\in\mathcal{H}$ s.t.
$\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star},(x,y))\right]=0$. Since
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$, this also implies that
$\mathbbm{E}_{\mathcal{D}}\left[\ell_{\text{sum}}^{@p}(h^{\star},(x,y))\right]=0$.
Therefore, under realizability and the fact that $\ell\leq
b\ell_{\text{sum}}^{@p}$, we have
$\mathbbm{E}_{\mathcal{D}}\left[\ell(\mathcal{A}(S),(x,y))\right]\leq
b\epsilon$. Therefore, $\mathcal{A}$ is also a realizable PAC learner for
$\mathcal{H}$ w.r.t $\ell$ with sample complexity
$m(\frac{\epsilon}{b},\delta,K)$. This completes the first part of the proof.

Now, we show how to convert the realizable PAC learner $\mathcal{A}$ for
$\ell$ into an agnostic PAC learner for $\ell$ in a black-box fashion. For
this step, we will extend the agnostic-to-realizable reduction proposed by
Hopkins et al. (2022) to the ranking setting by accommodating the mismatch
between the range space of $\mathcal{H}$ and the label space $\mathcal{Y}$. In
particular, we will show that Algorithm 1 below converts a realizable PAC
learner for $\ell$ into an agnostic PAC learner for $\ell$. Note that although
input $\mathcal{A}$ is a realizable learner, the distribution $\mathcal{D}$
may not be realizable.

Input: Realizable PAC learner $\mathcal{A}$ for $\mathcal{H}$, unlabeled
samples $S_{U}\sim\mathcal{D}_{\mathcal{X}}^{n}$, and labeled samples
$S_{L}\sim\mathcal{D}^{m}$

1

2For each $h\in\mathcal{H}_{|S_{U}}$, construct a dataset

3 $S_{U}^{h}=\\{(x_{1},\tilde{y}_{1}),...,(x_{n},\tilde{y}_{n})\\}\text{ s.t.
}\tilde{y}_{i}\sim\text{Unif}\\{\text{BinRel}(h(x_{i}),1),...,\text{BinRel}(h(x_{i}),p)\\}$

4Run $\mathcal{A}$ over all datasets to get
$C(S_{U}):=\left\\{\mathcal{A}\big{(}S_{U}^{h}\big{)}\mid
h\in\mathcal{H}_{|S_{U}}\right\\}$

Return $\hat{g}\in C(S_{U})$ with the lowest empirical error over $S_{L}$
w.r.t. $\ell$.

Algorithm 1 Agnostic PAC learner for $\mathcal{H}$ w.r.t. $\ell$

Let
$h^{\star}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\mathbbm{E}\left[\ell(h,(x,y))\right]$
denote the optimal predictor in $\mathcal{H}$ w.r.t $\mathcal{D}$. Consider
the sample $S_{U}^{h^{\star}}$ and let $g=\mathcal{A}(S_{U}^{h^{\star}})$. We
can think of $g$ as the output of $\mathcal{A}$ run over an i.i.d sample $S$
drawn from $\mathcal{D}^{\star}$, a joint distribution over
$\mathcal{X}\times\mathcal{Y}$ defined procedurally by first sampling
$x\sim\mathcal{D}_{\mathcal{X}}$, then independently sampling
$j\sim\text{Unif}([p])$, and finally outputting the labeled sample
$(x,\text{BinRel}(h^{\star}(x),j))$. Note that $\mathcal{D}^{\star}$ is indeed
a realizable distribution (realized by $h^{\star}$) w.r.t both $\ell$ and
$\ell_{\text{sum}}^{@p}$. Recall that
$m_{\mathcal{A}}(\frac{\epsilon}{b},\delta,K)$ is the sample complexity of
$\mathcal{A}$. Since $\mathcal{A}$ is a realizable learner for $\mathcal{H}$
w.r.t $\ell$, we have that for $n\geq
m_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}p},\delta/2,K)$, with probability at
least $1-\frac{\delta}{2}$,

$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]\leq\frac{a\epsilon}{2bp}.$

By definition of $\mathcal{D}^{\star}$, it further follows that
$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]=\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\mathbbm{E}_{j\sim\text{Unif}([p])}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),j))\right]$.
Therefore,

$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\mathbbm{E}_{j\sim\text{Unif}([p])}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),j))\right]\right]\leq\frac{a\epsilon}{2bp}.$

Next, by Lemma E.1, we have pointwise that

$\ell(g(x),y)\leq\ell(h^{\star}(x),y)+\frac{bp}{a}\mathbbm{E}_{j\sim\text{Unif}([p])}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),j))\right].$

Taking expectation of both sides of the inequality gives

$\displaystyle\mathbbm{E}_{\mathcal{D}}\left[\ell(g(x),y)\right]$
$\displaystyle\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\mathbbm{E}_{\mathcal{D}}\left[\frac{bp}{a}\mathbbm{E}_{j\sim\text{Unif}([p])}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),j))\right]\right]$
$\displaystyle=\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{bp}{a}\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\mathbbm{E}_{j\sim\text{Unif}([p])}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),j))\right]\right]$
$\displaystyle=\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{bp}{a}\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]$
$\displaystyle\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{\epsilon}{2}.$

Therefore, we showed that $C(S_{U})$ contains a hypothesis $g$ that
generalizes well with respect to $\mathcal{D}$. Now we want to show that the
predictor $\hat{g}$ returned in step 4 also has good generalization.
Crucially, observe that $C(S_{U})$ is a finite hypothesis class with
cardinality at most $2^{nK}$. Therefore, by standard Chernoff and union
bounds, with probability at least $1-\delta/2$, the empirical risk of every
hypothesis in $C(S_{U})$ on a sample of size
$\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C(S_{U})|}{\delta}}$ is at most
$\epsilon/4$ away from its true error. So, if
$m=|S_{L}|\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C(S_{U})|}{\delta}}$, then
with probability at least $1-\delta/2$, we have

$\frac{1}{|S_{L}|}\sum_{(x,y)\in
S_{L}}\ell(g(x),y)\leq\operatorname{\mathbb{E}}_{\mathcal{D}}\left[\ell(g(x),y)\right]+\frac{\epsilon}{4}\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{3\epsilon}{4}.$

Since $\hat{g}$ is the ERM on $S_{L}$ over $C(S)$, its empirical risk can be
at most
$\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{3\epsilon}{4}$.
Given that the population risk of $\hat{g}$ can be at most $\epsilon/4$ away
from its empirical risk, we have that

$\operatorname{\mathbb{E}}_{\mathcal{D}}[\ell(\hat{g}(x),y)]\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\epsilon.$

Applying union bounds, the entire process succeeds with probability
$1-\delta$. We can upper bound the sample complexity of Algorithm 1, denoted
$n(\epsilon,\delta,K)$, as

$\begin{split}n(\epsilon,\delta,K)&\leq
m_{\mathcal{A}}\left(\frac{a\epsilon}{2b^{2}p},\delta/2,K\right)+O\left(\frac{1}{\epsilon^{2}}\log{\frac{|C(S_{U})|}{\delta}}\right)\\\
&\leq
m_{\mathcal{A}}\left(\frac{a\epsilon}{2b^{2}p},\delta/2,K\right)+O\left(\frac{Km_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}p},\delta/2,K)\,\,+\log{\frac{1}{\delta}}}{\epsilon^{2}}\right),\end{split}$

where we use $|C(S_{U})|\leq
2^{Km_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}p},\delta/2,K)}$. This shows that
Algorithm 1 is an agnostic PAC learner for $\mathcal{H}$ w.r.t $\ell$. This
completes the proof as we have constructively converted a agnostic PAC learner
for $\ell_{\text{sum}}^{@p}$ into an agnostic PAC learner for $\ell$. ∎

Lemma 4.3 and 4.4 together complete the proof of sufficiency for Theorem 4.1.
Finally, Lemma 4.5 below shows that the agnostic PAC learnability of
$\mathcal{H}_{i}^{j}$ for all $(i,j)\in[K]\times[p]$ is necessary for the
agnostic PAC learnability of $\mathcal{H}$ w.r.t any
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$.

######  Lemma 4.5.

Let $\ell\in\mathcal{L}(\ell^{@p}_{\text{sum}})$. If a hypothesis class
$\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is agnostic PAC learnable
w.r.t $\ell$, then $\mathcal{H}_{i}^{j}$ is agnostic PAC learnable w.r.t the
0-1 loss for all $(i,j)\in[K]\times[p]$.

Like the sufficiency proofs, the proof of Lemma 4.5 is constructive. In fact,
the proof of Lemma 4.5 is very similar to the proof Lemma 4.4. Given an
agnostic PAC learner $\mathcal{A}$ for $\mathcal{H}$ w.r.t $\ell$, we
construct a realizable PAC learner for $\mathcal{H}_{i}^{j}$ w.r.t
$\ell_{0\text{-}1}$ using a slight modification of Algorithm 1. Since for
binary classification, realizable PAC learning implies agnostic PAC learning
(see Theorem 6.7 in Shalev-Shwartz and Ben-David (2014)), our proof sketch is
complete. Because the construction of the realizable PAC learner for
$\mathcal{H}_{i}^{j}$ w.r.t $\ell_{0\text{-}1}$ is very similar to Algorithm
1, the analysis is also similar, and thus we defer the full proof to Appendix
C. Combining Lemma 4.3, 4.4 and 4.5 gives Theorem 4.1.

In Appendix B, we highlight the usefulness of our characterization by giving
dimension-based sufficient conditions under which generic score-based ranking
hypothesis classes are agnostic PAC learnable. As a specific example, we
consider the class of linear ranking hypotheses and prove Lemma 4.6 in
Appendix B.

######  Lemma 4.6.

Let $\mathcal{H}=\\{x\mapsto\emph{argsort}(Wx):W\in\mathbbm{R}^{K\times d}\\}$
be the class of linear ranking hypothesis. Then for all $i,j\in[K]$,
$\text{VC}(\mathcal{H}_{i}^{j})=\tilde{O}(Kd)$, where $\tilde{O}$ hides
logarithmic factors of $d$.

Combining Lemma 4.6 with Theorems 4.1 and 4.2 shows that linear ranking
hypothesis classes (with finite ambient dimension $d$) are agnostic PAC
learnable w.r.t to all losses in
$\mathcal{L}(\ell^{@p}_{\text{sum}})\cup\mathcal{L}(\ell^{@p}_{\text{prec}})$

##  5 Online Multilabel Ranking

In this section, we characterize the online learnability of hypothesis classes
$\mathcal{H}\subseteq\mathcal{S}_{K}^{\mathcal{X}}$ with respect to both
$\mathcal{L}(\ell^{@p}_{\text{sum}})$ and
$\mathcal{L}(\ell^{@p}_{\text{prec}})$. As in the batch setting, our
characterization relates the learnability of $\mathcal{H}$ to the learnability
of the threshold-restricted classes $\mathcal{H}_{i}^{j}$. Our main theorems
are presented below.

######  Theorem 5.1.

Let $\ell\in\mathcal{L}(\ell^{@p}_{\text{sum}})$. A hypothesis class
$\mathcal{H}\subseteq\mathcal{S}_{K}^{\mathcal{X}}$ is online learnable w.r.t
$\ell$ if and only if for all $i\in[K]$ and $j\in[p]$, $\mathcal{H}_{i}^{j}$
is online learnable w.r.t the 0-1 loss.

######  Theorem 5.2.

Let $\ell\in\mathcal{L}(\ell^{@p}_{\text{prec}})$. A hypothesis class
$\mathcal{H}\subseteq\mathcal{S}_{K}^{\mathcal{X}}$ is online learnable w.r.t
$\ell$ if and only if for all $i\in[K]$, $\mathcal{H}_{i}^{p}$ is online
learnable w.r.t the 0-1 loss.

The proofs of Theorems 5.1 and 5.2 follow a similar trajectory. So, we will
only provide the proof of Theorem 5.1 here and defer discussion of Theorem 5.2
to Appendix D.1. Recall that, in the batch setting, we proved the learnability
for equivalence class $\mathcal{L}(\ell_{\text{sum}}^{@p})$ in two steps:
first for $\ell_{\text{sum}}^{@p}$ and then for general losses
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$. However, for the online setting,
we will prove the learnability of all the losses in the equivalence class with
one proof using the celebrated Randomized Exponential Weights Algorithm (REWA)
algorithm.

###### Proof of sufficiency in Theorem 5.1.

We will first show the online learnability of $\mathcal{H}_{i}^{j}$ w.r.t.
$0$-$1$ loss for all $(i,j)\in[K]\times[p]$ is sufficient for the online
learnability of $\mathcal{H}$ w.r.t. any
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$. Our proof here will be
constructive. That is, given online learners for $\mathcal{H}_{i}^{j}$, we
will construct an online learner $\mathcal{Q}$ for $\mathcal{H}$ such that for
any stream of labeled instances, $\mathcal{Q}$ achieves sublinear regret in
$T$. To that end, we will construct a set of experts $\mathcal{E}$ using the
online learners for $\mathcal{H}_{i}^{j}$’s and run the REWA using
$\mathcal{E}$ and an appropriately scaled version of $\ell$. Exploiting the
specific structure of our expert construction, we will then relate the
cumulative loss of the best-fixed expert in hindsight to the best-fixed
hypothesis in hindsight. Our proof borrows ideas from the realizable-to-
agnostic online conversion from Raman et al. (2023), and thus, for clarity
sake, we will use the same notation whenever possible.

Let $(x_{1},y_{1}),...,(x_{T},y_{T})\in(\mathcal{X}\times\mathcal{Y})^{T}$
denote the stream of points to be observed by the online learner. We will
assume an oblivious adversary, that is the stream is fixed before the game
starts. A standard reduction (Chapter 4 in Cesa-Bianchi and Lugosi (2006))
allows us to convert oblivious regret bounds to adaptive regret bounds. Since
$\mathcal{H}_{i}^{j}\subseteq\\{0,1\\}^{\mathcal{X}}$ is online learnable
w.r.t. $0$-$1$ loss, we are guaranteed the existence of online learners
$\mathcal{A}_{i}^{j}$ for $\mathcal{H}_{i}^{j}$. In fact, our construction
works even if $\mathcal{A}_{i}^{j}$ is just a realizable learner for
$\mathcal{H}_{i}^{j}$. We will now use these realizable learners
$\mathcal{A}_{i}^{j}$ to construct a set of experts $\mathcal{E}$.

For any bitstring $b\in\\{0,1\\}^{T}$, let
$\phi:\\{t\in[T]:b_{t}=1\\}\rightarrow\mathcal{S}_{K}$ denote a function
mapping time points where $b_{t}=1$ to permutations. Let
$\Phi_{b}\subseteq\mathcal{S}_{K}^{\\{t\in[T]:b_{t}=1\\}}$ denote all such
functions $\phi$. For every $h\in\mathcal{H}$, there exists a
$\phi_{b}^{h}\in\Phi_{b}$ such that for all $t\in\\{t:b_{t}=1\\}$,
$\phi_{b}^{h}(t)=h(x_{t})$. Let $|b|=|\\{t\in[T]:b_{t}=1\\}|$. For every
$b\in\\{0,1\\}^{T}$ and $\phi\in\Phi_{b}$, we will define an Expert
$E_{b,\phi}$. Expert $E_{b,\phi}$, formally presented in Algorithm 2, uses
$\mathcal{A}_{i}^{j}$’s to make predictions in each round. However,
$E_{b,\phi}$ only updates the $\mathcal{A}_{i}^{j}$’s on those rounds where
$b_{t}=1$, using $\phi$ to compute a labeled instance $(x_{t},\phi(t))$. For
every $b\in\\{0,1\\}^{T}$, let
$\mathcal{E}_{b}=\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$ denote the set of
all Experts parameterized by functions $\phi\in\Phi_{b}$. If $b$ is the
bitstring with all zeros, then $\mathcal{E}_{b}$ will be empty. Therefore, we
will actually define
$\mathcal{E}_{b}=\\{E_{0}\\}\cup\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$,
where $E_{0}$ is the expert that never updates $\mathcal{A}_{i}^{j}$’s and
only use them for predictions in all $t\in[T]$. Note that
$1\leq|\mathcal{E}_{b}|\leq(K!)^{|b|}\leq K^{K|b|}$. Using these experts,
Algorithm 3 presents our agnostic online learner $\mathcal{Q}$ for
$\mathcal{\mathcal{H}}$ w.r.t $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$.
Here, $M$ is the upper bound on loss $\ell$.

Input: Independent copy of realizable learners $\mathcal{A}_{i}^{j}$ of
$\mathcal{H}_{i}^{j}$ for each $(i,j)\in[K]\times[p]$

1 for  _$t=1,...,T$_ do

2 Receive example $x_{t}$

3 Define a binary vote matrix $V_{t}\in\mathbb{R}^{K\times p}$ such that
$V_{t}[i,j]=\mathcal{A}_{i}^{j}(x_{t})$

4 Predict
$\hat{\pi}_{t}\in\operatorname*{arg\,min}_{\pi\in\mathcal{S}_{K}}\langle\pi,V_{t}\mathbf{1}_{p}\rangle$

5 if  _$b_{t}=1$_ then

6 For all $(i,j)\in[K]\times[p]$, update $\mathcal{A}_{i}^{j}$ by passing
$(x_{t},\phi_{i}^{j}(t))$

7

8 end for

Algorithm 2 Expert $(b,\phi)$

Input: Parameter $0<\beta<1$

1

2Let $B\in\\{0,1\\}^{T}$ s.t.
$B_{t}\overset{\text{iid}}{\sim}\text{Bernoulli}(\frac{T^{\beta}}{T})$

3Construct the set of experts
$\mathcal{E}_{B}=\\{E_{0}\\}\cup\bigcup_{\phi\in\Phi_{B}}\\{E_{B,\phi}\\}$
according to Algorithm 2

4Run REWA $\mathcal{P}$ using $\mathcal{E}_{B}$ and the loss function
$\frac{\ell}{M}$ over the stream $(x_{1},y_{1}),...,(x_{T},y_{T})$

Algorithm 3 Agnostic online learner $\mathcal{Q}$ for $\mathcal{H}$ w.r.t.
$\ell$

Next, we will show that the algorithm $\mathcal{Q}$ enjoys agnostic sublinear
regret. Before we analyze the algorithm, let us note that there are three
sources of randomness in Algorithm $\mathcal{Q}$, namely the randomness of
sampling $B$, the internal randomness of $\mathcal{A}_{i}^{j}$’s, and the
internal randomness of $\mathcal{P}$. One may think of internal randomness as
arising from the sampling step involved in the randomized predictions. Let $A$
be the random variable associated with joint internal randomness of
$\mathcal{A}_{i}^{j}$ for all $(i,j)\in[K]\times[p]$. Similarly, denote $P$ to
be the random variable associated with internal randomness of $\mathcal{P}$,
and $B$ is a random variable itself.

Using Theorem 21.11 in Shalev-Shwartz and Ben-David (2014) and the fact that
$B,A$ and $P$ are independent, REWA guarantees almost surely that

$\sum_{t=1}^{T}\mathbbm{E}\left[\ell(\mathcal{P}(x_{t}),y_{t})|B,A\right]\leq\inf_{E\in\mathcal{E}_{B}}\sum_{t=1}^{T}\ell(E(x_{t}),y_{t})+M\sqrt{2T\ln(|\mathcal{E}_{B}|)}.$

Taking an outer expectation gives

$\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{P}(x_{t}),y_{t})\right]\leq\mathbbm{E}\left[\inf_{E\in\mathcal{E}_{B}}\sum_{t=1}^{T}\ell(E(x_{t}),y_{t})\right]+\mathbbm{E}\left[M\sqrt{2T\ln(|\mathcal{E}_{B}|)}\right].$

Thus, we have

$\displaystyle\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{Q}(x_{t}),y_{t})\right]$
$\displaystyle=\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{P}(x_{t}),y_{t})\right]$
$\displaystyle\leq\mathbbm{E}\left[\inf_{E\in\mathcal{E}_{B}}\sum_{t=1}^{T}\ell(E(x_{t}),y_{t})\right]+\mathbbm{E}\left[M\sqrt{2T\ln(|\mathcal{E}_{B}|)}\right]$
$\displaystyle\leq\mathbbm{E}\left[\sum_{t=1}^{T}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\right]+M\mathbbm{E}\left[\sqrt{2T\ln(|\mathcal{E}_{B}|)}\right].$

In the last step, we used the fact that for all $b\in\\{0,1\\}^{T}$ and
$h\in\mathcal{H}$, $E_{b,\phi_{b}^{h}}\in\mathcal{E}_{b}$. Here,
$h^{\star}=\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(h(x_{t}),y_{t})$ is the
optimal function in hindsight. First, note that $\ln(|\mathcal{E}_{B}|)\leq
K|B|\ln(K)$. Using Jensen’s inequality gives
$\mathbbm{E}\left[\sqrt{2T\ln(|\mathcal{E}_{B}|)}\right]\leq\sqrt{2T^{1+\beta}K\ln{K}}$.
Thus, we obtain

$\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{Q}(x_{t}),y_{t})\right]\leq\mathbbm{E}\left[\sum_{t=1}^{T}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\right]+M\sqrt{2T^{1+\beta}K\ln{K}}.$
(1)

It now suffices to upperbound
$\mathbbm{E}\left[\sum_{t=1}^{T}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\right]$.
Recall that Lemma E.1 gives

$\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\leq\ell(h^{\star}(x_{t}),y_{t})+\frac{M}{a}\,p\operatorname{\mathbb{E}}_{j\sim\text{Unif([p])}}[\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),j))]$

pointwise, where $M=\max_{\pi,y}\ell(\pi,y)$ and
$a=\min_{\pi,y}\\{\ell(\pi,y)\,\mid\,\ell(\pi,y)\neq 0\\}$. Note that, by
definition of the constant $M$, we further get

$\begin{split}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),j))&\leq
M\,\mathbbm{1}\\{\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),j))>0\\}\\\
&=M\,\mathbbm{1}\\{\ell_{\text{sum}}^{@p}(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),j))>0\\},\end{split}$

where the equality follows from the fact that
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$.

In order to upperbound the indicator above, we need to introduce some more
notations. Given the realizable online learner $\mathcal{A}_{i}^{m}$ for
$(i,m)\in[K]\times[p]$, an instance $x\in\mathcal{X}$, and an ordered finite
sequence of labeled examples $L\in(\mathcal{X}\times\\{0,1\\})^{*}$, let
$\mathcal{A}_{i}^{m}(x|L)$ be the random variable denoting the prediction of
$\mathcal{A}_{i}^{m}$ on the instance $x$ after running and updating on $L$.
For any $b\in\\{0,1\\}^{T}$, $h_{i}^{m}\in\mathcal{H}_{i}^{m}$, and $t\in[T]$,
let $L_{b_{<t}}^{h}(i,m)=\\{(x_{s},h_{i}^{m}(x_{s})):s<t\text{ and
}b_{s}=1\\}$ denote the subsequence of the sequence of labeled instances
$\\{(x_{s},h_{i}^{m}(x_{s}))\\}_{s=1}^{t-1}$ where $b_{s}=1$. Then, for any
$j\in[p]$, we have

$\begin{split}\mathbbm{1}\\{\ell_{\text{sum}}^{@p}(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),j))>0\\}&\leq\sum_{i=1}^{K}\sum_{m=1}^{j}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq h_{i}^{\star,m}(x_{t})\\}\\\
&\leq\sum_{i=1}^{K}\sum_{m=1}^{p}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq h_{i}^{\star,m}(x_{t})\\}\end{split}$

To prove the first inequality above, consider the case when
$\sum_{i=1}^{K}\sum_{m=1}^{p}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq h_{i}^{\star,m}(x_{t})\\}=0$ because the
inequality is trivial otherwise. Then, we must have
$\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))=h_{i}^{\star,m}(x_{t})$ for all
$(i,m)\in[K]\times[p]$. Let $V_{t}\in\mathbb{R}^{K\times p}$ be a binary vote
matrix $E_{B,\phi_{B}^{h^{\star}}}$ constructs in round $t$. Then, we have
$V_{t}[i,m]=\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))=h_{i}^{\star,m}(x_{t})$ for all
$(i,m)\in[K]\times[p]$. Since $h^{\star}(x_{t})$ is a permutation, the vote
vector $V_{t}\mathbf{1}_{p}$ must contain $p$ labels with distinct number of
non-zero votes, namely $p,p-1,p-2,\ldots,2,1$ votes. Similarly, there must be
$K-p$ labels with exactly $0$ vote. Thus, every
$\hat{\pi}_{t}\in\operatorname*{arg\,min}_{\pi\in\mathcal{S}_{K}}\langle\pi,V_{t}\mathbf{1}_{p}\rangle$
must rank item that obtained $p$ votes as $1$, item with $p-1$ votes as $2$,
and so forth. In other words, we must have
$\hat{\pi}_{t}\stackrel{{\scriptstyle\mathclap{[p]}}}{{=}}h^{\star}(x_{t})$,
and thus
$\ell_{\text{sum}}^{@p}(\hat{\pi}_{t},\text{BinRel}(h^{\star}(x_{t}),j))=0$
for any $j\leq p$ by definition of $\ell_{\text{sum}}^{@p}$. Our claim now
follows because
$E_{B,\phi_{B}^{h^{\star}}}(x_{t})\in\operatorname*{arg\,min}_{\pi\in\mathcal{S}_{K}}\langle\pi,V_{t}\mathbf{1}_{p}\rangle$.
Combining everything, we obtain

$\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\leq\ell(h^{\star}(x_{t}),y_{t})+\frac{pM^{2}}{a}\>\sum_{i=1}^{K}\sum_{m=1}^{p}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq h_{i}^{\star,m}(x_{t})\\},$

which further implies that

$\mathbb{E}\left[\sum_{t=1}^{T}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\right]\leq\sum_{t=1}^{T}\ell(h^{\star}(x_{t}),y_{t})+\frac{pM^{2}}{a}\>\sum_{i=1}^{K}\sum_{m=1}^{p}\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq h_{i}^{\star,m}(x_{t})\\}\right].$

The first term above is the cumulative loss of the best-fixed hypothesis in
hindsight. So, it now suffices to show that
$\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq h_{i}^{\star,m}(x_{t})\\}\right]$ is
sublinear for every $(i,m)\in[K]\times[p]$. Note that we can write

$\begin{split}\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq
h_{i}^{\star,m}(x_{t})\\}\right]&=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq
h_{i}^{\star,m}(x_{t})\\}\right]\frac{\mathbb{P}\left[B_{t}=1\right]}{\mathbb{P}\left[B_{t}=1\right]}\\\
&=\frac{T}{T^{\beta}}\,\sum_{t=1}^{T}\operatorname{\mathbb{E}}\left[\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq
h_{i}^{\star,m}(x_{t})\\}\right]\mathbb{E}\left[\mathbbm{1}\\{B_{t}=1\\}\right]\\\
&=\frac{T}{T^{\beta}}\,\sum_{t=1}^{T}\operatorname{\mathbb{E}}\left[\mathbbm{1}\\{\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq
h_{i}^{\star,m}(x_{t})\\}\mathbbm{1}\left\\{B_{t}=1\right\\}\right],\end{split}$

the last equality follows because the prediction of
$\mathcal{A}_{i}^{m}(x_{t}\mid L_{B_{<t}}^{h^{\star}}(i,m))$ on round $t$ only
depends on bitstring ($B_{1},\ldots,B_{t-1}$), but is independent of $B_{t}$.
Next, we can use the regret guarantee of the algorithm $\mathcal{A}_{i}^{m}$
on the rounds it was updated. That is,

$\begin{split}\sum_{t=1}^{T}\operatorname{\mathbb{E}}\left[\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\mathbbm{1}\left\\{B_{t}=1\right\\}\right]&=\operatorname{\mathbb{E}}\left[\sum_{t:B_{t}=1}\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq h_{i}^{\star,m}(x_{t})\\}\right]\\\
&=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{E}}\left[\sum_{t:B_{t}=1}\mathcal{A}_{i}^{m}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,m))\neq
h_{i}^{\star,m}(x_{t})\\}\right]\Bigg{|}B\right]\\\
&\leq\operatorname{\mathbb{E}}\left[R_{i}^{m}(|B|)\right],\end{split}$

where $R_{i}^{m}(|B|)$ is a sublinear function of $|B|$. In the last step, we
use the fact that $\mathcal{A}_{i}^{m}$ is a realizable algorithm for
$\mathcal{H}_{i}^{m}$ and the feedback that the algorithm received was
$(x_{t},h_{i}^{\star,m}(x_{t}))$ in the rounds whenever $B_{t}=1$. Next,
without loss of generality, we assume that $R_{i}^{m}(|B|)$ is a concave
function of $|B|$. Otherwise, by Lemma 5.17 from Woess (2017), there exists a
concave sublinear function $\tilde{R}_{i}^{m}(|B|)$ that upperbounds
$R_{i}^{m}(|B|)$. By Jensen’s inequality,
$\mathbbm{E}_{B}\left[R_{i}^{m}(|B|)\right]\leq R_{i}^{m}(T^{\beta})$, a
sublinear function of $T^{\beta}$.

Putting everything together, we obtain

$\begin{split}\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{Q}(x_{t}),y_{t})\right]&\leq\sum_{t=1}^{T}\ell(h^{\star}(x_{t}),y_{t})+\frac{pM^{2}}{a}\sum_{i=1}^{K}\sum_{m=1}^{p}\frac{T}{T^{\beta}}\,R_{i}^{m}(T^{\beta})+M\sqrt{2T^{1+\beta}K\ln{K}}\\\
&\leq\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(h(x_{t}),y_{t})+\frac{pM^{2}}{a}\frac{T}{T^{\beta}}R(T^{\beta})+M\sqrt{2T^{1+\beta}K\ln{K}},\end{split}$

where we used the definition of $h^{\star}$ for the first term and defined
$R(T^{\beta})=\sum_{i=1}^{K}\sum_{m=1}^{p}R_{i}^{m}(T^{\beta})$ for the second
term. Since $R(T^{\beta})$ is a sum of sublinear functions of $T^{\beta}$, it
must be sublinear. Subsequently, $T/T^{\beta}R(T^{\beta})=To(1)=o(T)$ is a
sublinear function of $T$. And the third term is sublinear for any choice of
$\beta\in(0,1)$. This completes our proof as we have shown that the algorithm
$\mathcal{Q}$ achieves sublinear regret in $T$.

∎

Next, we prove the necessity part of Theorem 5.1.

###### Proof.

(of necessity in Theorem 5.1) We will now show that the online learnability of
$\mathcal{H}$ w.r.t $\ell$ implies that $\mathcal{H}_{i}^{j}$ for each
$(i,j)\in[K]\times[p]$ is online learnable. Our proof is based on reduction.
Given an online learner $\mathcal{A}$ for $\mathcal{H}$ w.r.t $\ell$, we will
construct an online learner $\mathcal{A}_{i}^{j}$ for $\mathcal{H}_{i}^{j}$
for a fixed $(i,j)$ in the realizable setting. By symmetry, one can construct
the online learner for any $(i,j)$ pairs. Moreover, as $\mathcal{H}_{i}^{j}$
is a binary class, for which realizable and agnostic online learnability are
equivalent, it suffices to show that $\mathcal{H}_{i}^{j}$ is online learnable
in the realizable setting. Our construction uses Expert’s algorithm and is
similar to that in the sufficiency proof above.

For any bitstring $b\in\\{0,1\\}^{T}$, let
$\phi:\\{t\in[T]:b_{t}=1\\}\rightarrow\mathcal{S}_{K}$ denote a function
mapping time points where $b_{t}=1$ to permutations. Let
$\Phi_{b}\subseteq\mathcal{S}_{K}^{\\{t\in[T]:b_{t}=1\\}}$ denote all such
functions $\phi$. For every $h\in\mathcal{H}$, there exists a
$\phi_{b}^{h}\in\Phi_{b}$ such that for all $t\in\\{t:b_{t}=1\\}$,
$\phi_{b}^{h}(t)=h(x_{t})$. Let $|b|=|\\{t\in[T]:b_{t}=1\\}|$. For every
$b\in\\{0,1\\}^{T}$ and $\phi\in\Phi_{b}$, define an Expert $E_{b,\phi}$.
Expert $E_{b,\phi}$, formally presented in Algorithm 4, uses $\mathcal{A}$’s
to make predictions in each round. For every $b\in\\{0,1\\}^{T}$, let
$\mathcal{E}_{b}=\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$ denote the set of
all Experts parameterized by functions $\phi\in\Phi_{b}$. As before, we will
actually define
$\mathcal{E}_{b}=\\{E_{0}\\}\cup\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$,
where $E_{0}$ is the expert that never updates $\mathcal{A}$ and only use them
for predictions in all $t\in[T]$. Note that
$1\leq|\mathcal{E}_{b}|\leq(K!)^{|b|}\leq K^{K|b|}$.

The realizable learner for $\mathcal{H}_{i}^{j}$, henceforth denoted by
$\mathcal{Q}$, is similar to Algorithm 3. First, it samples a
$B\in\\{0,1\\}^{T}$ s.t. $B_{t}\sim\text{Bernoulli}(T^{\beta}/T)$, construct
set of experts $\mathcal{E}_{B}$ using Algorithm 4 and run REWA, denoted by
$\mathcal{P}$, on $0$-$1$ loss over the realizable stream
$(x_{1},h_{i}^{j\star}(x_{1})),...,(x_{T},h_{i}^{j\star}(x_{T}))\in(\mathcal{X}\times\\{0,1\\})^{T}$
for some $h^{\star}\in\mathcal{H}$.

Input: Independent copy of online learner $\mathcal{A}$ for $\mathcal{H}$

1 for  _$t=1,...,T$_ do

2 Receive example $x_{t}$

3 Predict $\hat{\pi}_{i}^{j}=\mathbbm{1}\\{\hat{\pi}_{i}\leq j\\}$ where
$\hat{\pi}=\mathcal{A}(x_{t})$

4 if  _$b_{t}=1$_ then

5 Update $\mathcal{A}$ by passing $(x_{t},\text{BinRel}(\phi(t),j))$

6

7 end for

Algorithm 4 Expert $(b,\phi)$

As before, let $A$ and $P$ be the random variables denoting internal
randomness of the algorithm $\mathcal{A}$ and $\mathcal{P}$. Using REWA
guarantees and following exactly the same calculation as in the sufficiency
proof, we arrive at

$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{Q}(x_{t})\neq
h_{i}^{\star,j}(x_{t})\\}\right]\leq\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,j}(x_{t})\\}\right]+\sqrt{2T^{1+\beta}K\ln{K}}.$

The inequality above is the adaptation of Equation (1) for this proof, where
we use the fact that $y_{t}=h_{i}^{\star,j}(x_{t})$ and $M=1$. It now suffices
to show that
$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,j}(x_{t})\\}\right]$ is sublinear in $T$.

Given an online learner $\mathcal{A}$ for $\mathcal{H}$, an instance
$x\in\mathcal{X}$, and an ordered finite sequence of labeled examples
$L\in(\mathcal{X}\times\mathcal{Y})^{*}$, let $\mathcal{A}(x|L)$ be the random
variable denoting the prediction of $\mathcal{A}$ on the instance $x$ after
running and updating on $L$. For any $b\in\\{0,1\\}^{T}$, $h\in\mathcal{H}$,
and $t\in[T]$, let
$L^{h}_{b_{<t}}=\\{(x_{i},\text{BinRel}(h(x_{s}),j)):s<t\text{ and
}b_{s}=1\\}$ denote the subsequence of the sequence of labeled instances
$\\{(x_{s},\text{BinRel}(h(x_{s}),j))\\}_{s=1}^{t-1}$ where $b_{s}=1$. Thus,
using Lemma E.3, we have

$\begin{split}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,j}(x_{t})\\}&\leq\mathbbm{1}\\{\ell_{\text{sum}}^{@p}(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),j))>0\\}\\\
&=\mathbbm{1}\\{\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),j))>0\\}\\\
&\leq\frac{M}{a}\,\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),j),\text{BinRel}(h^{\star}(x_{t}),j)),\end{split}$

where equality follows from the fact that $\ell\in\ell_{\text{sum}}^{@p}$.
Here, $M$ is the upperbound on loss $\ell$ and $a$ is the lower bound whenever
it is non-zero. Taking expectation of both sides gives,

$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,j}(x_{t})\\}\right]\leq\frac{M}{a}\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),j))\right].$

To upperbound the right-hand side, we will again use the fact that the
prediction $\mathcal{A}(x_{t}\mid L^{h^{\star}}_{B_{<t}})$ only depends on
$(B_{1},\ldots,B_{t-1})$, but is independent of $B_{t}$. The details of this
calculation are omitted because they are identical to that of the sufficiency
proof. Using independence of $\mathcal{A}(x_{t}\mid L^{h^{\star}}_{B_{<t}})$
and $B_{t}$, we obtain

$\begin{split}\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),j))\right]&\leq\frac{T}{T^{\beta}}\,\mathbbm{E}\left[\sum_{t:B_{t}=1}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),j))\right]\\\
&\leq\frac{T}{T^{\beta}}\,\mathbbm{E}\left[\mathbbm{E}\left[\sum_{t:B_{t}=1}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),j))\,\Bigg{|}B\right]\right]\\\
&\leq\frac{T}{T^{\beta}}\operatorname{\mathbb{E}}\left[R(|B|,K)\right],\end{split}$

where $R(|B|,K)$ is the regret of the algorithm $\mathcal{A}$, a sublinear
function of $|B|$. In the last step, we use the fact that $\mathcal{A}$ is a
(realizable) online learner for $\mathcal{H}$ w.r.t. $\ell$ and the feedback
that the algorithm received was $(x_{t},\text{BinRel}(h^{\star}(x_{t}),j))$ in
the rounds whenever $B_{t}=1$. Again, using Lemma 5.17 from Woess (2017) and
Jensen’s inequality yields $\mathbbm{E}\left[R(|B|,K)\right]\leq
R(T^{\beta},K)$, a sublinear function of $T^{\beta}$. Combining everything, we
get

$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{Q}(x_{t})\neq
h_{i}^{\star,j}(x_{t})\\}\right]\leq\frac{M}{a}\frac{T}{T^{\beta}}R(T^{\beta},K)+\sqrt{2T^{1+\beta}K\ln{K}}.$

For any choice of $\beta\in(0,1)$, the right-hand side is a sublinear function
of $T$. Therefore, we have shown that $\mathcal{Q}$ is a realizable learner
for $\mathcal{H}_{i}^{j}$ w.r.t. $0$-$1$ loss. Since realizable and agnostic
online learnability are equivalent for binary classification problems, we have
shown that $\mathcal{H}_{i}^{j}$ is agnostic online learnable. This completes
our proof. ∎

##  6 Discussion

In this paper, we characterize the learnability of a multilabel ranking
hypothesis class in both the batch and online setting for a wide range of
practical ranking losses. In all cases, we show that a ranking hypothesis
class is learnable if and only if a sufficient number of its binary-valued
threshold-restrictions are learnable. We leave it as an open problem to
improve our bounds on sample complexity and regret in the batch and online
settings respectively.

## References

  * Agarwal [2010] Shivani Agarwal.  Learning to rank on graphs.  _Machine learning_ , 81:333–357, 2010.
  * Alon et al. [2020] Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer.  Closure properties for private classification and online prediction.  In _Conference on Learning Theory_ , pages 119–152. PMLR, 2020.
  * Bartlett and Mendelson [2002] Peter L Bartlett and Shahar Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3(Nov):463–482, 2002.
  * Ben-David et al. [1992] Shai Ben-David, Nicolò Cesa-Bianchi, and Philip M. Long.  Characterizations of learnability for classes of O, …, N-valued functions.  In _Proceedings of the Fifth Annual Workshop on Computational Learning Theory_ , COLT ’92, page 333–340. Association for Computing Machinery, 1992.  doi: 10.1145/130385.130423.
  * Brukhim et al. [2022] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff.  A characterization of multiclass learnability, 2022.  URL https://arxiv.org/abs/2203.01550.
  * Burges et al. [2005] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender.  Learning to rank using gradient descent.  In _Proceedings of the 22nd international conference on Machine learning_ , pages 89–96, 2005.
  * Cao et al. [2007] Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li.  Learning to rank: from pairwise approach to listwise approach.  In _Proceedings of the 24th international conference on Machine learning_ , pages 129–136, 2007.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Chapelle and Chang [2011] Olivier Chapelle and Yi Chang.  Yahoo! learning to rank challenge overview.  In _Proceedings of the learning to rank challenge_ , pages 1–24. PMLR, 2011.
  * Chaudhuri and Tewari [2015] Sougata Chaudhuri and Ambuj Tewari.  Online ranking with top-1 feedback.  In _Proceedings of the 18th International Conference on Artificial Intelligence and Statistics_ , volume 38 of _JMLR Workshop and Conference Proceedings_ , pages 129–137, 2015.  URL http://jmlr.csail.mit.edu/proceedings/papers/v38/chaudhuri15.html.  Honorable Mention, Best Student Paper Award.
  * Daniely and Shalev-Shwartz [2014] Amit Daniely and Shai Shalev-Shwartz.  Optimal learners for multiclass problems.  In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, _Proceedings of The 27th Conference on Learning Theory_ , volume 35 of _Proceedings of Machine Learning Research_ , pages 287–316, Barcelona, Spain, 13–15 Jun 2014. PMLR.
  * Daniely et al. [2011] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the erm principle.  In Sham M. Kakade and Ulrike von Luxburg, editors, _Proceedings of the 24th Annual Conference on Learning Theory_ , volume 19 of _Proceedings of Machine Learning Research_ , pages 207–232, Budapest, Hungary, 09–11 Jun 2011. PMLR.
  * Dudley [1978] Richard M Dudley.  Central limit theorems for empirical measures.  _The Annals of Probability_ , pages 899–929, 1978.
  * Hong et al. [2012] Liangjie Hong, Ron Bekkerman, Joseph Adler, and Brian D Davison.  Learning to rank social update streams.  In _Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval_ , pages 651–660, 2012.
  * Hopkins et al. [2022] Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan.  Realizable learning is all you need.  In _Proceedings of Thirty Fifth Conference on Learning Theory_ , volume 178 of _Proceedings of Machine Learning Research_ , pages 3015–3069. PMLR, 02–05 Jul 2022.
  * Karatzoglou et al. [2013] Alexandros Karatzoglou, Linas Baltrunas, and Yue Shi.  Learning to rank for recommender systems.  In _Proceedings of the 7th ACM Conference on Recommender Systems_ , pages 493–494, 2013.
  * Leaman et al. [2013] Robert Leaman, Rezarta Islamaj Doğan, and Zhiyong Lu.  Dnorm: disease name normalization with pairwise learning to rank.  _Bioinformatics_ , 29(22):2909–2917, 2013.
  * Ledoux and Talagrand [1991] Michel Ledoux and Michel Talagrand.  _Probability in Banach Spaces: isoperimetry and processes_ , volume 23.  Springer Science & Business Media, 1991.
  * Littlestone [1987] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine Learning_ , 2:285–318, 1987.
  * Liu et al. [2009] Tie-Yan Liu et al.  Learning to rank for information retrieval.  _Foundations and Trends® in Information Retrieval_ , 3(3):225–331, 2009.
  * Raman et al. [2023] Vinod Raman, Unique Subedi, and Ambuj Tewari.  A characterization of multioutput learnability, 2023.
  * Ramaswamy et al. [2015] Harish G. Ramaswamy, Ambuj Tewari, and Shivani Agarwal.  Convex calibrated surrogates for hierarchical classification.  In _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _JMLR Workshop and Conference Proceedings_ , pages 1852–1860, 2015.  URL http://jmlr.org/proceedings/papers/v37/ramaswamy15.html.
  * Severyn and Moschitti [2015] Aliaksei Severyn and Alessandro Moschitti.  Learning to rank short text pairs with convolutional deep neural networks.  In _Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval_ , pages 373–382, 2015.
  * 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.
  * Tewari and Chaudhuri [2015] Ambuj Tewari and Sougata Chaudhuri.  Generalization error bounds for learning to rank: Does the length of document lists matter?  In _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _JMLR Workshop and Conference Proceedings_ , pages 315–323, 2015.  URL http://jmlr.org/proceedings/papers/v37/tewari15.html.
  * Valiant [1984] Leslie G. Valiant.  A theory of the learnable.  In _Symposium on the Theory of Computing_ , 1984.
  * Vapnik and Chervonenkis [1974] V. Vapnik and A. Chervonenkis.  _Theory of Pattern Recognition [in Russian]_.  1974\.
  * Vargas and Castells [2011] Saúl Vargas and Pablo Castells.  Rank and relevance in novelty and diversity metrics for recommender systems.  In _Proceedings of the fifth ACM conference on Recommender systems_ , pages 109–116, 2011.
  * Woess [2017] Wolfgang Woess.  _Groups, graphs and random walks_ , volume 436.  Cambridge University Press, 2017.

##  Appendix A Categorizing Popular Ranking Losses

In this section, we show that our loss families
$\mathcal{L}(\ell_{\text{sum}}^{@p})$ and
$\mathcal{L}(\ell_{\text{prec}}^{@p})$ are general and capture many of the
popular ranking loss functions used in practice. Recall, that

$\mathcal{L}(\ell^{@p}_{\text{sum}})=\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\ell=0\text{
iff
}\ell_{\text{sum}}^{@p}=0\\}\cap\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\pi\stackrel{{\scriptstyle[p]}}{{=}}\hat{\pi}\implies\ell(\pi,y)=\ell(\hat{\pi},y)\\},$

and

$\mathcal{L}(\ell^{@p}_{\text{prec}})=\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\ell=0\text{
iff
}\ell_{\text{prec}}^{@p}=0\\}\cap\\{\ell\in\mathbbm{R}^{\mathcal{S}_{K}^{\mathcal{X}}\times\mathcal{Y}}:\pi\stackrel{{\scriptstyle
p}}{{=}}\hat{\pi}\implies\ell(\pi,y)=\ell(\hat{\pi},y)\\}.$

where

$\ell^{@p}_{\text{sum}}(\pi,y)=\sum_{i=1}^{K}\min(\pi_{i},p+1)y_{i}-Z^{p}_{y}$

and

$\ell^{@p}_{\text{prec}}(\pi,y)=Z^{p}_{y}-\sum_{i=1}^{K}\mathbbm{1}\\{\pi_{i}\leq
p\\}y_{i}.$

In ranking literature, many evaluation metrics are often stated in terms of
gain functions. However, these can be easily converted into loss functions by
subtracting the gain from the maximum possible value of the gain. When
relevance scores are restricted to be binary (i.e.
$\mathcal{Y}=\\{0,1\\}^{K}$), the Average Precision (AP) metric is a gain
function defined as

$\text{AP}(\pi,y)=\frac{1}{||y||_{1}}\sum_{i:y_{i}=1}\frac{\sum_{j=1}^{K}\mathbbm{1}\\{\pi_{j}\leq
i\\}y_{j}}{i}.$

Since the maximum value AP can take is $1$, we can define its loss function
variant as:

$\ell_{\text{AP}}(\pi,y)=1-\text{AP}(\pi,y).$

Note that $\ell_{\text{AP}}(\pi,y)=0$ if and only if $\pi$ ranks all labels
where $y_{i}=1$ in the top $||y||_{1}$. Therefore,
$\ell_{\text{AP}}(\pi,y)\in\mathcal{L}(\ell_{\text{sum}}^{@K})$.

Another useful metric for binary relevance feedback is the Area Under the
Curve (AUC) loss function:

$\ell_{\text{AUC}}(\pi,y)=\frac{1}{||y||_{1}(K-||y||_{1})}\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbbm{1}\\{\pi_{i}<\pi_{j}\\}\mathbbm{1}\\{y_{i}<y_{j}\\}.$

The AUC computes the fraction of “bad pairs” of labels (i.e those pairs of
labels where $i$ was more relevant than $j$, but $i$ was ranked lower than
$j$). Again, note that $\ell_{\text{AUC}}(\pi,y)=0$ if and only if $\pi$ ranks
all labels where $y_{i}=1$ in the top $||y||_{1}$. Therefore,
$\ell_{\text{AP}}(\pi,y)\in\mathcal{L}(\ell_{\text{sum}}^{@K})$.

Lastly, the Reciprocal Rank (RR) metric is another important gain function for
binary relevance score feedback.

$\text{RR}(\pi,y)=\frac{1}{\min_{i:y_{i}=1}\pi_{i}}$

Its loss equivalent can be written as:

$\ell_{\text{RR}}(\pi,y)=1-\text{RR}(\pi,y)$

Since $\ell_{\text{RR}}(\pi,y)$ only cares about the relevance of the top
ranked item, we have that
$\ell_{\text{RR}}(\pi,y)\in\mathcal{L}(\ell_{\text{prec}}^{@1}).$

Moving onto non-binary relevance scores, we start with the Pairwise Rank Loss
(PL):

$\ell_{\text{PL}}(\pi,y)=\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbbm{1}\\{\pi_{i}<\pi_{j}\\}\mathbbm{1}\\{y_{i}<y_{j}\\}.$

The Pairwise Ranking loss is the analog of AUC for non-binary relevance scores
and thus $\ell_{\text{PL}}(\pi,y)\in\mathcal{L}(\ell_{\text{sum}}^{@K})$.

Finally, we have the Discounted Cumulative Gain (DCG) metric, defined as:

$\text{DCG}(\pi,y)=\sum_{i=1}^{K}\frac{2^{y_{i}}-1}{\log_{2}(1+\pi_{i})}.$

For an appropriately chosen normalizing constant $Z_{y}$, we can define its
associated loss:

$\ell_{\text{DCG}}(\pi,y)=Z_{y}-\text{DCG}(\pi,y).$

Like $\ell_{\text{sum}}^{@K}$, $\ell_{\text{DCG}}(\pi,y)$ is $0$ if and only
if $\pi$ ranks the $K$ labels in increasing order of relevance, breaking ties
arbitrarily. Thus,
$\ell_{\text{DCG}}(\pi,y)\in\mathcal{L}(\ell_{\text{sum}}^{@K})$. If one only
cares about the top-$p$ ranked results, then the DCG@p loss function evaluates
only the top-$p$ ranked labels:

$\ell^{@p}_{\text{DCG}}(\pi,y)=Z^{p}_{y}-\sum_{i=1}^{K}\frac{2^{y_{i}}-1}{\log_{2}(1+\pi_{i})}\mathbbm{1}\\{\pi_{i}\leq
p\\}=Z^{p}_{y}-\text{DCG}^{@p}(\pi,y).$

Analogously, we have that
$\ell^{@p}_{\text{DCG}}(\pi,y)\in\mathcal{L}(\ell_{\text{sum}}^{@p}).$

##  Appendix B Agnostic PAC Learnability of Score-based Rankers

In this section, we apply our results in the main paper to give sufficient
conditions for the agnostic PAC learnability of score-based ranking hypothesis
classes. A score-based ranking hypothesis
$h:\mathcal{X}\rightarrow\mathcal{S}_{K}$ first maps an input
$x\in\mathcal{X}$ to a vector in $\mathbbm{R}^{K}$ representing the “score”
for each label. Then, it outputs a permutation over the labels by sorting the
real-valued vector in decreasing order of score. We formalize this concept
below.

Let $\mathcal{F}\subset(\mathbbm{R}^{K})^{\mathcal{X}}$ denote a set of
functions mapping elements from the input space $\mathcal{X}$ to score-vectors
in $\mathbbm{R}^{K}$. Define the scalar-valued function class
$\mathcal{F}_{k}=\\{f_{k}\mid(f_{1},\ldots,f_{K})\in\mathcal{F}\\}$ by
restricting each function in $\mathcal{F}$ to its $k^{th}$ coordinate output.
Here, each $\mathcal{F}_{k}\subset\mathbbm{R}^{\mathcal{X}}$ and we can write
$\mathcal{F}=(\mathcal{F}_{1},\ldots,\mathcal{F}_{K})$. For a function
$f\in\mathcal{F}$, we will use $f_{k}(x)$ to denote the $k^{th}$ coordinate
output of $f(x)$. For every $(i,j)\in[K]\times[K]$, define the function class
$\mathcal{F}_{i}-\mathcal{F}_{j}=\\{f_{i}-f_{j}:f\in\mathcal{F}\\}$ where we
let $f_{i}-f_{j}:\mathcal{X}\rightarrow\mathbbm{R}$ denote a function such
that $(f_{i}-f_{j})(x)=f_{i}(x)-f_{j}(x).$ Subsequently, for any
$(i,j)\in[K]\times[K]$, define the binary hypothesis classes
$\mathcal{G}_{i,j}=\\{\mathbbm{1}\\{(f_{i}-f_{j})(x)<0\\}:f_{i}-f_{j}\in\mathcal{F}_{i}-\mathcal{F}_{j}\\}$
and $\tilde{\mathcal{G}}_{i,j}=\\{\mathbbm{1}\\{(f_{i}-f_{j})(x)\leq
0\\}:f_{i}-f_{j}\in\mathcal{F}_{i}-\mathcal{F}_{j}\\}$. Finally, let
$C_{j}:\\{0,1\\}^{K}\rightarrow\\{0,1\\}$ be the $K$-wise composition s.t.
$C_{j}(b)=\mathbbm{1}\\{\sum_{i=1}^{K}b_{i}\leq j\\}$ and define
$C_{j}(\mathcal{G}_{1},...,\mathcal{G}_{K})=\\{C_{j}(g_{1},...,g_{K}):g_{i}\in\mathcal{G}_{i}\\}.$
In otherwords, $C_{j}(\mathcal{G}_{1},...,\mathcal{G}_{K})$ is the binary
hypothesis class constructed by taking all combinations of binary classifiers
from $\mathcal{G}_{1},...,\mathcal{G}_{K}$, summing them up, and thresholding
the sum at $j$. Now, we are ready to construct our score-based ranking
hypothesis class.

For each $f\in\mathcal{F}$, define the score-based ranking hypothesis
$h_{f}(x)=\text{argsort}(f(x))$ which first computes the score-vector
$f(x)\in\mathbbm{R}^{K}$, and then outputs a permutation by sorting $f(x)$ in
decreasing order, breaking ties by giving the smaller label the higher rank.
That is, if $f_{1}(x)=f_{2}(x)$, then label $1$ will be ranked higher than
label $2$. Given $\mathcal{F}$, we can define a score-based ranking hypothesis
class $\mathcal{H}=\\{h_{f}:f\in\mathcal{F}\\}$. Since our characterization of
ranking learnability relates the learnability of $\mathcal{H}$ to the
learnability of the binary threshold-restricted classes
$\mathcal{H}_{i}^{j}=\\{h_{i}^{j}:h\in\mathcal{H}\\}$, it suffices to consider
an arbitrary threshold-restricted class $\mathcal{H}_{i}^{j}$ and compute its
VC dimension. To that end, consider a threshold-restricted class
$\mathcal{H}_{i}^{j}$ and a hypothesis $h\in\mathcal{H}$. By definition,
$h_{i}^{j}\in\mathcal{H}_{i}^{j}$. Let $f\in\mathcal{F}$ denote the function
associated with $h$. Given an instance $x\in\mathcal{X}$, recall that
$h_{i}^{j}(x)=\mathbbm{1}\\{h_{i}(x)\leq j\\}$ where $h_{i}(x)$ is the rank
that $h$ gives to the $i$’th label for instance $x$. Since
$h(x)=\text{argsort}(f(x))$, we have

$\displaystyle h_{i}(x)$ $\displaystyle=\text{argsort}(f(x))[i]$
$\displaystyle=\sum_{m=1}^{i}\mathbbm{1}\\{f_{i}(x)\leq
f_{m}(x)\\}+\sum_{m=i+1}^{K}\mathbbm{1}\\{f_{i}(x)<f_{m}(x)\\}$
$\displaystyle=\sum_{m=1}^{i}\mathbbm{1}\\{(f_{i}-f_{m})(x)\leq
0\\}+\sum_{m=i+1}^{K}\mathbbm{1}\\{(f_{i}-f_{m})(x)<0\\}$

Thus, we can write:

$h_{i}^{j}(x)=\mathbbm{1}\left\\{\left(\sum_{m=1}^{i}\mathbbm{1}\\{(f_{i}-f_{m})(x)\leq
0\\}+\sum_{m=i+1}^{K}\mathbbm{1}\\{(f_{i}-f_{m})(x)<0\\}\right)\leq
j\right\\}.$

Note that $h_{i}^{j}\in
C_{j}(\tilde{\mathcal{G}}_{i,1},...,\tilde{\mathcal{G}}_{i,i},\mathcal{G}_{i,i+1},...,\mathcal{G}_{i,K})$
by construction. Since $h$, and therefore $h_{i}^{j}$, was arbitrary, it
further follows that $\mathcal{H}_{i}^{j}\subset
C_{j}(\tilde{\mathcal{G}}_{i,1},...,\tilde{\mathcal{G}}_{i,i},\mathcal{G}_{i,i+1},...,\mathcal{G}_{i,K})$.
Therefore,

$\text{VC}(\mathcal{H}_{i}^{j})\leq\text{VC}(C_{j}(\tilde{\mathcal{G}}_{i,1},...,\tilde{\mathcal{G}}_{i,i},\mathcal{G}_{i,i+1},...,\mathcal{G}_{i,K})).$

Since
$C_{j}(\tilde{\mathcal{G}}_{i,1},...,\tilde{\mathcal{G}}_{i,i},\mathcal{G}_{i,i+1},...,\mathcal{G}_{i,K})$
is some $K$-wise composition of binary classes
$\tilde{\mathcal{G}}_{i,1},...,\tilde{\mathcal{G}}_{i,i},\mathcal{G}_{i,i+1},...,\mathcal{G}_{i,K}$,
standard VC composition guarantees gives that
$\text{VC}(C_{j}(\tilde{\mathcal{G}}_{i,1},...,\tilde{\mathcal{G}}_{i,i},\mathcal{G}_{i,i+1},...,\mathcal{G}_{i,K}))=\tilde{O}(\text{VC}(\tilde{\mathcal{G}}_{i,1})+...+\text{VC}(\tilde{\mathcal{G}}_{i,i})+\text{VC}(\mathcal{G}_{i,i+1})+...+\text{VC}(\mathcal{G}_{i,K}))$,
where we hide log factors of $K$ and the VC dimensions [Dudley, 1978, Alon et
al., 2020]. Putting things together, we have that

$\text{VC}(\mathcal{H}_{i}^{j})\leq\tilde{O}(\text{VC}(\tilde{\mathcal{G}}_{i,1})+...+\text{VC}(\tilde{\mathcal{G}}_{i,i})+\text{VC}(\mathcal{G}_{i,i+1})+...+\text{VC}(\mathcal{G}_{i,K})).$

We note that the above analysis can also be used to give sufficient conditions
for the online learnability of score-based rankers in terms of the Littlestone
dimensions of $\mathcal{H}^{i}_{j}$. Now, we consider a specific ranking
hypothesis class. Let $\mathcal{X}=\mathbbm{R}^{d}$ and
$\mathcal{F}=\\{f_{W}:W\in\mathbbm{R}^{K\times d}\\}$ s.t. $f_{W}(x)=Wx$.
Consider the ranking hypothesis class
$\mathcal{H}=\\{h_{f_{W}}:f_{W}\in\mathcal{F}\\}$ where
$h_{f_{W}}(x)=\text{argsort}(f_{W}(x))=\text{argsort}(Wx)$ breaking ties in
the same way mentioned above. Note for all $i\in[K]$,
$\mathcal{F}_{i}=\\{f_{w}:w\in\mathbbm{R}^{d}\\}$ where $f_{w}(x)=w^{T}x$.
Furthermore,
$\mathcal{F}_{i}-\mathcal{F}_{j}=\mathcal{F}_{i}=\mathcal{F}_{j}$. Therefore,
for any $(i,j)\in[K]\times[K]$,

$\mathcal{G}_{i,j}=\\{\mathbbm{1}\\{(f_{i}-f_{j})(x)<0\\}:f_{i}-f_{j}\in\mathcal{F}_{i}-\mathcal{F}_{j}\\}=\\{\mathbbm{1}\\{f_{w}(x)<0\\}:w\in\mathbbm{R}^{d}\\}$

and

$\tilde{\mathcal{G}}_{i,j}=\\{\mathbbm{1}\\{(f_{i}-f_{j})(x)\leq
0\\}:f_{i}-f_{j}\in\mathcal{F}_{i}-\mathcal{F}_{j}\\}=\\{\mathbbm{1}\\{f_{w}(x)\leq
0\\}:w\in\mathbbm{R}^{d}\\}$

are the set of half-space classifiers passing through the origin with
dimension $d$. Since for all $(i,j)\in[K]\times[K]$,
$\text{VC}(\tilde{\mathcal{G}}_{i,j})=\text{VC}(\mathcal{G}_{i,j})=d$, we get
that $\text{VC}(\mathcal{H}_{i}^{j})\leq\tilde{O}(Kd).$

##  Appendix C Proofs for Batch Multilabel Ranking

###  C.1 Proof of Lemma 4.5

###### Proof.

Fix $\ell\in\mathcal{L}(\ell^{@p}_{\text{sum}})$ and $(i,j)\in[K]\times[p]$.
Let $\mathcal{H}$ be an arbitrary ranking hypothesis class and $\mathcal{A}$
be an agnostic PAC learner for $\mathcal{H}$ w.r.t $\ell$. Our goal will to be
to use $\mathcal{A}$ to construct a realizable PAC learner for
$\mathcal{H}_{i}^{j}$. Since for binary classification, realizable PAC
learning implies agnostic PAC learning (see Theorem 6.7 in Shalev-Shwartz and
Ben-David [2014]), our proof will be complete.

Let $\mathcal{D}$ be a realizable distribution over
$\mathcal{X}\times\\{0,1\\}$ w.r.t $\mathcal{H}_{i}^{j}$ and
$h^{\star,j}_{i}=\operatorname*{arg\,min}_{h_{i}^{j}\in\mathcal{H}_{i}^{j}}\mathbbm{E}_{\mathcal{D}}\left[\mathbbm{1}\\{h_{i}^{j}(x)\neq
y\\}\right]$ be the optimal hypothesis. Let $h^{\star}\in\mathcal{H}$ be any
valid completion of $h^{\star,j}_{i}$. Our goal will be to show that Algorithm
5 is a realizable PAC learner for $\mathcal{H}_{i}^{j}$ w.r.t 0-1 loss.

Input: Agnostic PAC learner $\mathcal{A}$ for $\mathcal{H}$ w.r.t $\ell$,
unlabeled samples $S_{U}\sim\mathcal{D}_{\mathcal{X}}^{n}$, and labeled
samples $S_{L}\sim\mathcal{D}^{m}$

1

2For each $h\in\mathcal{H}_{|S_{U}}$, construct a dataset

3 $S_{U}^{h}=\\{(x_{1},\tilde{y}_{1}),...,(x_{n},\tilde{y}_{n})\\}\text{ s.t.
}\tilde{y}_{i}=\text{BinRel}(h(x_{i}),j)$

4Run $\mathcal{A}$ over all datasets to get
$C(S_{U}):=\left\\{\mathcal{A}\big{(}S_{U}^{h}\big{)}\mid
h\in\mathcal{H}_{|S_{U}}\right\\}$

5Define $C_{i}^{j}(S_{U})=\\{g_{i}^{j}|g\in C(S_{U})\\}$

Return $\hat{g}_{i}^{j}\in C_{i}^{j}(S_{U})$ with the lowest empirical error
over $S_{L}$ w.r.t. 0-1 loss.

Algorithm 5 Realizable PAC learner for $\mathcal{H}_{i}^{j}$ w.r.t. 0-1 loss

Consider the sample $S_{U}^{h^{\star}}$ and let
$g=\mathcal{A}(S_{U}^{h^{\star}})$. We can think of $g$ as the output of
$\mathcal{A}$ run over an i.i.d sample $S$ drawn from $\mathcal{D}^{\star}$, a
joint distribution over $\mathcal{X}\times\mathcal{Y}$ defined procedurally by
first sampling $x\sim\mathcal{D}_{\mathcal{X}}$ and then outputting the
labeled sample $(x,\text{BinRel}(h^{\star}(x),j))$. Note that
$\mathcal{D}^{\star}$ is a realizable distribution (realized by $h^{\star}$)
w.r.t $\ell_{\text{sum}}^{@p}$ and therefore also $\ell$. Let
$m_{\mathcal{A}}(\epsilon,\delta,K)$ be the sample complexity of
$\mathcal{A}$. Since $\mathcal{A}$ is an agnostic PAC learner for
$\mathcal{H}$ w.r.t $\ell$, we have that for sample size $n\geq
m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)$, with probability at least
$1-\frac{\delta}{2}$,

$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]\leq\inf_{h\in\mathcal{H}}\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(h(x),y)\right]+\frac{\epsilon}{2c}\leq\frac{\epsilon}{2c},$

where $c$ is a universal constant s.t. $\ell_{\text{sum}}^{@p}\leq c\ell$.
Furthermore, by definition of $\mathcal{D}^{\star}$,
$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]=\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),j))\right]$.
Therefore,
$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),j))\right]\leq\frac{\epsilon}{2c}.$
Since $\ell_{\text{sum}}^{@p}\leq c\ell$, we have
$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell^{@p}_{\text{sum}}(g(x),\text{BinRel}(h^{\star}(x),j))\right]\leq\frac{\epsilon}{2}.$
Next, using Lemma E.3, we have that $\mathbbm{1}\\{g_{i}^{j}(x)\neq
h_{i}^{\star,j}(x)\\}\leq\ell^{@p}_{\text{sum}}(g(x),\text{BinRel}(h^{\star}(x),j))$,
which gives
$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\mathbbm{1}\\{g_{i}^{j}(x)\neq
h_{i}^{\star,j}(x)\\}\right]\leq\frac{\epsilon}{2}.$ Recalling that
$\mathcal{D}$ is a distribution realized by $h^{\star,j}_{i}$, we get

$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\mathbbm{1}\\{g_{i}^{j}(x)\neq
h_{i}^{\star,j}(x)\\}\right]=\mathbbm{E}_{\mathcal{D}}\left[\mathbbm{1}\\{g_{i}^{j}(x)\neq
y\\}\right]\leq\frac{\epsilon}{2}.$

Since $g_{i}^{j}\in C_{i}^{j}(S_{U})$, we have shown that $C_{i}^{j}(S_{U})$
contains a hypothesis that generalizes well w.r.t $\mathcal{D}$. Now we want
to show that the predictor $\hat{g}_{i}^{j}$ returned in step 4 also
generalizes well. Crucially, observe that $C_{i}^{j}(S_{U})$ is a finite
hypothesis class with cardinality at most $K^{jn}$. Therefore, by standard
Chernoff and union bounds, with probability at least $1-\delta/2$, the
empirical risk of every hypothesis in $C_{i}^{j}(S_{U})$ on a sample of size
$\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C_{i}^{j}(S_{U})|}{\delta}}$ is at
most $\epsilon/4$ away from its true error. So, if
$m=|S_{L}|\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C_{i}^{j}(S_{U})|}{\delta}}$,
then with probability at least $1-\delta/2$, we have

$\frac{1}{|S_{L}|}\sum_{(x,y)\in S_{L}}\mathbbm{1}\\{g_{i}^{j}(x)\neq
y\\}\leq\operatorname{\mathbb{E}}_{\mathcal{D}}\left[\mathbbm{1}\\{g_{i}^{j}(x)\neq
y\\}\right]+\frac{\epsilon}{4}\leq\frac{3\epsilon}{4}.$

Since $\hat{g}_{i}^{j}$ is the ERM on $S_{L}$ over $C_{i}^{j}(S_{U})$, its
empirical risk can be at most $\frac{3\epsilon}{4}$. Given that the population
risk of $\hat{g}_{i}^{j}$ can be at most $\epsilon/4$ away from its empirical
risk, we have that

$\operatorname{\mathbb{E}}_{\mathcal{D}}[\mathbbm{1}\\{\hat{g}_{i}^{j}(x)\neq
y\\}]\leq\epsilon.$

Applying union bounds, the entire process succeeds with probability
$1-\delta$. We can compute the upper bound on the sample complexity of
Algorithm 5, denoted $n(\epsilon,\delta,K)$, as

$\begin{split}n(\epsilon,\delta,K)&\leq
m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)+O\left(\frac{1}{\epsilon^{2}}\log{\frac{|C(S_{U})|}{\delta}}\right)\\\
&\leq
m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)+O\left(\frac{jm_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)\log(K)\,+\log{\frac{1}{\delta}}}{\epsilon^{2}}\right),\end{split}$

where we use $|C(S_{U})|\leq
K^{jm_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)}$. This shows that
Algorithm 5 is a realizable PAC learner for $\mathcal{H}_{i}^{j}$ w.r.t 0-1
loss. Finally, the realizable-to-agnostic conversion from Hopkins et al.
[2022] can then be used to further transform Algorithm 5 into an agnostic PAC
learner for $\mathcal{H}_{i}^{j}$. Thus, $\mathcal{H}_{i}^{j}$ is agnostic PAC
learnable as needed. Since our choice of loss
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$ and indices $(i,j)$ were
arbitrary, agnostic PAC learnability of $\mathcal{H}$ w.r.t $\ell$ implies
agnostic PAC learnability of $\mathcal{H}_{i}^{j}$ w.r.t the 0-1 loss for all
$(i,j)\in[K]\times[p]$. ∎

###  C.2 Characterizing Batch Learnability of
$\mathcal{L}(\ell^{@p}_{\text{prec}})$

In this section, we prove Theorem 4.2 which characterizes the agnostic PAC
learnability of an arbitrary hypothesis class
$\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ w.r.t losses in
$\mathcal{L}(\ell_{\text{prec}}^{@p})$. Our proof will again be in in three
parts. First, we will show that if for all $i\in[K]$, $\mathcal{H}_{i}^{p}$ is
agnostic PAC learnable w.r.t the 0-1 loss, then $\mathcal{H}$ is agnostic PAC
learnable w.r.t $\ell_{\text{prec}}^{@p}$. Next, we show that if $\mathcal{H}$
is agnostic PAC learnable w.r.t $\ell_{\text{prec}}^{@p}$, then $\mathcal{H}$
is agnostic PAC learnable w.r.t any loss
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$. Finally, we prove the necessity
direction - if $\mathcal{H}$ is agnostic PAC learnable w.r.t an arbitrary
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$, then for all $i\in[K]$,
$\mathcal{H}_{i}^{p}$ is agnostic PAC learnable w.r.t the 0-1 loss.

We begin with Lemma C.1 which asserts that if for all $i\in[K]$,
$\mathcal{H}_{i}^{p}$ is agnostic PAC learnable, then $\mathcal{H}$ is
agnostic PAC learnable w.r.t $\ell_{\text{prec}}^{@p}$.

######  Lemma C.1.

A function class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is agnostic
PAC learnable w.r.t $\ell_{\text{prec}}^{@p}$ if for all $i\in[K]$,
$\mathcal{H}_{i}^{p}$ is agnostic PAC learnable w.r.t the 0-1 loss.

The proof of Lemma C.1 is similar to the proof of Lemma 4.3 and involves
bounding the empirical Rademacher complexity of the loss class
$\ell_{\text{prec}}^{@p}\circ\mathcal{H}$. This will imply that
$\ell_{\text{prec}}^{@p}$ enjoys the uniform convergence property, and
therefore ERM is an agnostic PAC learner for $\mathcal{H}$ w.r.t
$\ell_{\text{prec}}^{@p}$. The key insight is that we can write
$\ell_{\text{prec}}^{@p}(h(x),y)=Z^{p}_{y}-\sum_{i=1}^{K}\mathbbm{1}\\{h_{i}(x)\leq
p\\}y_{i}=Z^{p}_{y}-\sum_{i=1}^{K}h_{i}^{p}(x)y_{i}$. Since $Z_{y}^{p}$ does
not depend on $h(x)$ and $y_{i}\leq B$, we can upperbound the empirical
Rademacher complexity in terms of the empirical Rademacher complexities of
$h_{i}^{p}$ using Talagrands’s contraction.

###### Proof.

Let $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ be an arbitrary ranking
hypothesis class. Similar to the proof of Lemma 4.3, it suffices to show that
the empirical Rademacher complexity of the loss class
$\ell_{\text{prec}}^{@p}\circ\mathcal{H}$ is $o(1)$. This will imply that
$\ell_{\text{prec}}^{@p}$ enjoys the uniform convergence property, and
therefore ERM is an agnostic PAC learner for $\mathcal{H}$ w.r.t
$\ell_{\text{prec}}^{@p}$. By definition, we have that

$\displaystyle\mathfrak{R}_{n}(\ell_{\text{prec}}^{@p}\circ\mathcal{H})$
$\displaystyle=\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\ell_{\text{prec}}^{@p}(h(x_{i}),y_{i}))\right]$
$\displaystyle=\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\left(\sigma_{i}Z_{y_{i}}^{p}-\sum_{m=1}^{K}\sigma_{i}\mathbbm{1}\\{h_{m}(x_{i})\leq
p\\}y_{i}^{m}\right)\right]$ $\displaystyle=\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sum_{m=1}^{K}\sigma_{i}h_{m}^{p}(x_{i})y_{i}^{m}\right]$
$\displaystyle\leq\sum_{m=1}^{K}\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}h_{m}^{p}(x_{i})y_{i}^{m}\right]$
$\displaystyle\leq B\sum_{m=1}^{K}\mathbbm{E}_{\sigma\sim\\{\pm
1\\}^{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}h_{m}^{p}(x_{i})\right]$
$\displaystyle=B\sum_{m=1}^{K}\mathfrak{R}_{n}(\mathcal{H}^{p}_{m})$

where the second inequality follows from Talagrand’s Contraction Lemma and the
fact that $y_{i}^{m}\leq B$ for all $i,m$. Since for all $m\in[K]$,
$\mathcal{H}_{m}^{p}$ is agnostic PAC learnable w.r.t 0-1 loss, by Theorem 6.7
in Shalev-Shwartz and Ben-David [2014],
$d_{m}^{p}=\text{VC}(\mathcal{H}_{m}^{p})<\infty$. By standard VC arguments,
it follows that $\mathfrak{R}_{n}(\mathcal{H}_{m}^{p})\leq
O\left(\sqrt{\frac{d_{m}^{p}\ln(\frac{n}{d_{m}^{p}})}{n}}\right)$. Putting
things together, we have that
$\mathfrak{R}_{n}(\ell_{\text{prec}}^{@p}\circ\mathcal{H})\leq
O(B\sum_{m=1}^{K}\sqrt{\frac{d_{m}^{p}\ln(\frac{n}{d^{p}_{m}})}{n}})$. Since
$K$ is finite, $\mathfrak{R}_{n}(\ell_{\text{prec}}^{@p}\circ\mathcal{H})$
vanishes as $n$ becomes large. By Proposition 2.1, this implies that
$\ell_{\text{prec}}^{@p}$ enjoys the uniform convergence property, and
therefore ERM using $\ell_{\text{prec}}^{@p}$ is an agnostic PAC learner for
$\mathcal{H}$. ∎

Next, Lemma C.2 extends the learnability of $\ell_{\text{prec}}^{@p}$ to the
learnability of any loss $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$. In
particular, Lemma C.2 asserts that if $\mathcal{H}$ is agnostic PAC learnable
w.r.t $\ell_{\text{prec}}^{@p}$ then $\mathcal{H}$ is also agnostic PAC
learnable w.r.t $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$.

######  Lemma C.2.

Let $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$. A hypothesis class
$\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is agnostic PAC learnable
w.r.t $\ell$ if $\mathcal{H}$ is agnostic PAC learnable w.r.t
$\ell_{\text{prec}}^{@p}$.

The proof of Lemma C.2 follows the same the exact same strategy used in
proving Lemma 4.4. More specifically, given an agnostic PAC learner
$\mathcal{A}$ for $\mathcal{H}$ w.r.t. $\ell_{\text{prec}}^{@p}$, we first
create a realizable PAC learner $\mathcal{B}$ for $\mathcal{H}$ w.r.t
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$. Then, we use a similar
realizable-to-agnostic conversion technique as in the proof of Lemma 4.4 to
convert $\mathcal{B}$ into an agnostic PAC learner for $\mathcal{H}$ w.r.t
$\ell$.

###### Proof.

Fix $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$. Let
$b=\max_{\pi,y}\ell(\pi,y)$ and $a=\min_{\pi,y\text{ s.t
}\ell(\pi,y)>0}\ell(\pi,y)$.We need to show that if $\mathcal{H}$ is agnostic
PAC learnable w.r.t $\ell_{\text{prec}}^{@p}$, then $\mathcal{H}$ is agnostic
PAC learnable w.r.t $\ell$. We will do so in two steps. First, we will show
that if $\mathcal{A}$ is an agnostic PAC learner for $\mathcal{H}$ w.r.t.
$\ell_{\text{prec}}^{@p}$, then $\mathcal{A}$ is also a realizable PAC learner
for $\mathcal{H}$ w.r.t $\ell$. Next, we will show how to convert the
realizable PAC learner w.r.t $\ell$ into an agnostic PAC learner w.r.t $\ell$
in a black-box fashion. The composition of these two pieces yields an agnostic
PAC learner for $\mathcal{H}$ w.r.t $\ell$.

If $\mathcal{H}$ is agnostic PAC learnable w.r.t $\ell_{\text{prec}}^{@p}$,
then there exists a learning algorithm $\mathcal{A}$ with sample complexity
$m(\epsilon,\delta,K)$ s.t. for any distribution $\mathcal{D}$ over
$\mathcal{X}\times\mathcal{Y}$, with probability $1-\delta$ over a sample
$S\sim\mathcal{D}^{n}$ of size $n\geq m(\epsilon,\delta,K)$,

$\mathbbm{E}_{\mathcal{D}}\left[\ell_{\text{prec}}^{@p}(\mathcal{A}(S),(x,y))\right]\leq\inf_{h\in\mathcal{H}}\mathbbm{E}_{\mathcal{D}}\left[\ell_{\text{prec}}^{@p}(h,(x,y))\right]+\epsilon.$

In the realizable setting, we are further guaranteed that there exists a
hypothesis $h^{\star}\in\mathcal{H}$ s.t.
$\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star},(x,y))\right]=0$. Since
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$, this also means that
$\mathbbm{E}_{\mathcal{D}}\left[\ell_{\text{prec}}^{@p}(h^{\star},(x,y))\right]=0$.
Furthermore, since $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$, $\ell\leq
b\ell_{\text{prec}}^{@p}$. Together, this means we have
$\mathbbm{E}_{\mathcal{D}}\left[\ell(\mathcal{A}(S),(x,y))\right]\leq
b\epsilon$ showing have that $\mathcal{A}$ is also a realizable PAC learner
for $\mathcal{H}$ w.r.t $\ell$ with sample complexity
$m(\frac{\epsilon}{b},\delta,K)$. This completes the first part of the proof.

Now, we show how to convert the realizable PAC learner $\mathcal{A}$ for
$\ell$ into an agnostic PAC learner for $\ell$ in a black-box fashion. For
this step, we will use a similar algorithm as in the proof of Lemma 4.4. That
is, we will show that Algorithm 6 below is an agnostic PAC learner for
$\mathcal{H}$ w.r.t $\ell$.

Input: Realizable PAC learner $\mathcal{A}$ for $\mathcal{H}$ w.r.t $\ell$,
unlabeled samples $S_{U}\sim\mathcal{D}_{\mathcal{X}}^{n}$, and labeled
samples $S_{L}\sim\mathcal{D}^{m}$

1

2For each $h\in\mathcal{H}_{|S_{U}}$, construct a dataset

3 $S_{U}^{h}=\\{(x_{1},\tilde{y}_{1}),...,(x_{n},\tilde{y}_{n})\\}\text{ s.t.
}\tilde{y}_{i}=\text{BinRel}(h(x_{i}),p)$

4Run $\mathcal{A}$ over all datasets to get
$C(S_{U}):=\left\\{\mathcal{A}\big{(}S_{U}^{h}\big{)}\mid
h\in\mathcal{H}_{|S_{U}}\right\\}$

Return $\hat{g}\in C(S_{U})$ with the lowest empirical error over $S_{L}$
w.r.t. $\ell$.

Algorithm 6 Agnostic PAC learner for $\mathcal{H}$ w.r.t. $\ell$

Let $\mathcal{D}$ be any (not necessarily realizable) distribution over
$\mathcal{X}\times\mathcal{Y}$. Let
$h^{\star}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\mathbbm{E}\left[\ell(h,(x,y))\right]$
denote the optimal predictor in $\mathcal{H}$ w.r.t $\mathcal{D}$. Consider
the sample $S_{U}^{h^{\star}}$ and let $g=\mathcal{A}(S_{U}^{h^{\star}})$. We
can think of $g$ as the output of $\mathcal{A}$ run over an i.i.d sample $S$
drawn from $\mathcal{D}^{\star}$, a joint distribution over
$\mathcal{X}\times\mathcal{Y}$ defined procedurally by first sampling
$x\sim\mathcal{D}_{\mathcal{X}}$, and then outputting the labeled sample
$(x,\text{BinRel}(h^{\star}(x),p))$. Note that $\mathcal{D}^{\star}$ is indeed
a realizable distribution (realized by $h^{\star}$) w.r.t both $\ell$ and
$\ell_{\text{prec}}^{@p}$. Recall that
$m_{\mathcal{A}}(\frac{\epsilon}{b},\delta,K)$ is the sample complexity of
$\mathcal{A}$. Since $\mathcal{A}$ is a realizable learner for $\mathcal{H}$
w.r.t $\ell$, we have that for $n\geq
m_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}},\delta/2,K)$, with probability at
least $1-\frac{\delta}{2}$,

$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]\leq\frac{a\epsilon}{2b}.$

By definition of $\mathcal{D}^{\star}$, it further follows that
$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]=\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),p))\right]$.
Therefore,

$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),p))\right]\leq\frac{a\epsilon}{2b}.$

Next, by Lemma E.2, we have pointwise that:

$\ell(g(x),y)\leq\ell(h^{\star}(x),y)+\frac{b}{a}\ell(g(x),\text{BinRel}(h^{\star}(x),p)).$

Taking expectation of both sides of the inequality gives:

$\displaystyle\mathbbm{E}_{\mathcal{D}}\left[\ell(g(x),y)\right]$
$\displaystyle\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\mathbbm{E}_{\mathcal{D}}\left[\frac{b}{a}\ell(g(x),\text{BinRel}(h^{\star}(x),p))\right]$
$\displaystyle=\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{b}{a}\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),p))\right]$
$\displaystyle\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{\epsilon}{2}.$

Therefore, we have shown that $C(S_{U})$ contains a hypothesis $g$ that
generalizes well with respect to $\mathcal{D}$. The remaining proof follows
exactly as in the proof of Lemma 4.4. We include here for completeness sake.

Now we want to show that the predictor $\hat{g}$ returned in step 4 also has
good generalization. Crucially, observe that $C(S_{U})$ is a finite hypothesis
class with cardinality at most $K^{pn}$. Therefore, by standard Chernoff and
union bounds, with probability at least $1-\delta/2$, the empirical risk of
every hypothesis in $C(S_{U})$ on a sample of size
$\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C(S_{U})|}{\delta}}$ is at most
$\epsilon/4$ away from its true error. So, if
$m=|S_{L}|\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C(S_{U})|}{\delta}}$, then
with probability at least $1-\delta/2$, we have

$\frac{1}{|S_{L}|}\sum_{(x,y)\in
S_{L}}\ell(g(x),y)\leq\operatorname{\mathbb{E}}_{\mathcal{D}}\left[\ell(g(x),y)\right]+\frac{\epsilon}{4}\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{3\epsilon}{4}.$

Since $\hat{g}$ is the ERM on $S_{L}$ over $C(S)$, its empirical risk can be
at most
$\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\frac{3\epsilon}{4}$.
Given that the population risk of $\hat{g}$ can be at most $\epsilon/4$ away
from its empirical risk, we have that

$\operatorname{\mathbb{E}}_{\mathcal{D}}[\ell(\hat{g}(x),y)]\leq\mathbbm{E}_{\mathcal{D}}\left[\ell(h^{\star}(x),y)\right]+\epsilon.$

Applying union bounds, the entire process succeeds with probability
$1-\delta$. We can upper bound the sample complexity of Algorithm 1, denoted
$n(\epsilon,\delta,K)$, as

$\begin{split}n(\epsilon,\delta,K)&\leq
m_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}},\delta/2,K)+O\left(\frac{1}{\epsilon^{2}}\log{\frac{|C(S_{U})|}{\delta}}\right)\\\
&\leq
m_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}},\delta/2,K)+O\left(\frac{p\,m_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}},\delta/2,K)\log(K)\,+\log{\frac{1}{\delta}}}{\epsilon^{2}}\right),\end{split}$

where we use $|C(S_{U})|\leq
K^{pm_{\mathcal{A}}(\frac{a\epsilon}{2b^{2}},\delta/2,K)}$. This shows that
Algorithm 1, given as input an realizable PAC learner for $\mathcal{H}$ w.r.t
$\ell$, is an agnostic PAC learner for $\mathcal{H}$ w.r.t $\ell$. Using the
realizable learner we constructed before this step as the input completes this
proof as we have constructively converted an agnostic PAC learner for
$\ell_{\text{prec}}^{@p}$ into an agnostic PAC learner for $\ell$. ∎

Lemma C.1 and C.2 together complete the sufficiency part of the Proof of
Theorem 4.2. Finally, Lemma C.3 below shows that the agnostic PAC learnability
of $\mathcal{H}_{i}^{p}$ for all $i\in[K]$ is necessary for the agnostic PAC
learnability of $\mathcal{H}$ w.r.t any
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$. Like before, the proof of Lemma
C.3 is constructive and follows exactly the same strategy as Lemma 4.5. That
is, given as input a learner for $\ell$, we will convert it into a realizable
learner for $\mathcal{H}_{i}^{p}$. In fact, the conversion is exactly the same
as in the proof of Lemma 4.5 and just requires running Algorithm 5 with an
input learner for $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$ and setting
$j=p$. Since realizable and agnostic learnability are equivalent for binary
classification, our proof is complete.

######  Lemma C.3.

If a function class $\mathcal{H}\subset\mathcal{S}_{K}^{\mathcal{X}}$ is
agnsotic PAC learnable w.r.t $\ell\in\mathcal{L}(\ell^{@p}_{\text{prec}})$,
then $\mathcal{H}_{i}^{p}$ is agnostic PAC learnable w.r.t the 0-1 loss for
all $i\in[K]$.

###### Proof.

Fix $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$ and $i\in[K]$. Let
$\mathcal{H}$ be an arbitrary ranking hypothesis class and $\mathcal{A}$ be an
agnostic PAC learner for $\mathcal{H}$ w.r.t $\ell$. Our goal will to be to
use $\mathcal{A}$ to construct a realizable PAC learner for
$\mathcal{H}_{i}^{p}$. Since for binary classification, realizable PAC
learning implies agnostic PAC learning, our proof will be complete.

Let $\mathcal{D}$ be any realizable distribution over
$\mathcal{X}\times\\{0,1\\}$ (w.r.t $\mathcal{H}_{i}^{j}$),
$h^{\star,p}_{i}=\operatorname*{arg\,min}_{h\in\mathcal{H}_{i}^{p}}\mathbbm{E}_{\mathcal{D}}\left[\mathbbm{1}\\{h(x)\neq
y\\}\right]$ the optimal hypothesis, and $h^{\star}\in\mathcal{H}$ any valid
completion of $h^{\star,p}_{i}$. We will now show that Algorithm 5 from the
proof of Lemma 4.5 is a realizable PAC learner for $\mathcal{H}_{i}^{p}$ if we
set $j=p$ and give it as input an agnostic PAC learner $\mathcal{A}$ for
$\mathcal{H}$ w.r.t. $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$.

Consider the sample $S_{U}^{h^{\star}}$ and let
$g=\mathcal{A}(S_{U}^{h^{\star}})$. We can think of $g$ as the output of
$\mathcal{A}$ run over an i.i.d sample $S$ drawn from $\mathcal{D}^{\star}$, a
joint distribution over $\mathcal{X}\times\mathcal{Y}$ defined procedurally by
first sampling $x\sim\mathcal{D}_{\mathcal{X}}$ and then outputting the
labeled sample $(x,\text{BinRel}(h^{\star}(x),p))$. Note that
$\mathcal{D}^{\star}$ is a realizable distribution (realized by $h^{\star}$)
w.r.t $\ell_{\text{prec}}^{@p}$ and therefore also $\ell$. Let
$m_{\mathcal{A}}(\epsilon,\delta,K)$ be the sample complexity of
$\mathcal{A}$. Since $\mathcal{A}$ is a PAC learner for $\mathcal{H}$ w.r.t
$\ell$, we have that for sample size $n\geq
m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)$, with probability at least
$1-\frac{\delta}{2}$,

$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]\leq\inf_{h\in\mathcal{H}}\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(h(x),y)\right]+\frac{\epsilon}{2c}\leq\frac{\epsilon}{2c}$

where $c$ is a universal constant s.t. $\ell_{\text{prec}}^{@p}\leq c\ell$.
Furthermore, by definition of $\mathcal{D}^{\star}$,
$\mathbbm{E}_{\mathcal{D}^{\star}}\left[\ell(g(x),y)\right]=\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),p))\right]$.
Therefore,
$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell(g(x),\text{BinRel}(h^{\star}(x),p))\right]\leq\frac{\epsilon}{2c}.$
Since $\ell_{\text{prec}}^{@p}\leq c\ell$, we have
$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\ell^{@p}_{\text{prec}}(g(x),\text{BinRel}(h^{\star}(x),p))\right]\leq\frac{\epsilon}{2}.$
Next, using Lemma E.4, we have that $\mathbbm{1}\\{g_{i}^{p}(x)\neq
h_{i}^{\star,p}(x)\\}\leq\ell^{@p}_{\text{prec}}(g(x),\text{BinRel}(h^{\star}(x),p))$,
which gives
$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\mathbbm{1}\\{g_{i}^{p}(x)\neq
h_{i}^{\star,p}(x)\\}\right]\leq\frac{\epsilon}{2}.$ Recalling that
$\mathcal{D}$ is a distribution realized by $h^{\star,p}_{i}$, we get

$\mathbbm{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\mathbbm{1}\\{g_{i}^{p}(x)\neq
h_{i}^{\star,p}(x)\\}\right]=\mathbbm{E}_{\mathcal{D}}\left[\mathbbm{1}\\{g_{i}^{p}(x)\neq
y\\}\right]\leq\frac{\epsilon}{2}.$

Since $g_{i}^{p}\in C_{i}^{p}(S_{U})$, we have shown that $C_{i}^{p}(S_{U})$
contains a hypothesis that generalizes well w.r.t $\mathcal{D}$. Now we want
to show that the predictor $\hat{g}_{i}^{p}$ returned in step 4 also
generalizes well. Crucially, observe that $C_{i}^{p}(S_{U})$ is a finite
hypothesis class with cardinality at most $K^{pn}$. Therefore, by standard
Chernoff and union bounds, with probability at least $1-\delta/2$, the
empirical risk of every hypothesis in $C_{i}^{p}(S_{U})$ on a sample of size
$\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C_{i}^{p}(S_{U})|}{\delta}}$ is at
most $\epsilon/4$ away from its true error. So, if
$m=|S_{L}|\geq\frac{8}{\epsilon^{2}}\log{\frac{4|C_{i}^{p}(S_{U})|}{\delta}}$,
then with probability at least $1-\delta/2$, we have

$\frac{1}{|S_{L}|}\sum_{(x,y)\in S_{L}}\mathbbm{1}\\{g_{i}^{p}(x)\neq
y\\}\leq\operatorname{\mathbb{E}}_{\mathcal{D}}\left[\mathbbm{1}\\{g_{i}^{p}(x)\neq
y\\}\right]+\frac{\epsilon}{4}\leq\frac{3\epsilon}{4}.$

Since $\hat{g}_{i}^{p}$ is the ERM on $S_{L}$ over $C_{i}^{p}(S_{U})$, its
empirical risk can be at most $\frac{3\epsilon}{4}$. Given that the population
risk of $\hat{g}_{i}^{p}$ can be at most $\epsilon/4$ away from its empirical
risk, we have that

$\operatorname{\mathbb{E}}_{\mathcal{D}}[\mathbbm{1}\\{\hat{g}_{i}^{p}(x)\neq
y\\}]\leq\epsilon.$

Applying union bounds, the entire process succeeds with probability
$1-\delta$. We can compute the upper bound on the sample complexity of
Algorithm 5, denoted $n(\epsilon,\delta,K)$, as

$\begin{split}n(\epsilon,\delta,K)&\leq
m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)+O\left(\frac{1}{\epsilon^{2}}\log{\frac{|C(S_{U})|}{\delta}}\right)\\\
&\leq
m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)+O\left(\frac{p\,m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)\,\log{K}\,+\log{\frac{1}{\delta}}}{\epsilon^{2}}\right),\end{split}$

where we use $|C(S_{U})|\leq
K^{p\,m_{\mathcal{A}}(\frac{\epsilon}{2c},\delta/2,K)}$. This shows that
Algorithm 5, when given as input an agnostic PAC learner $\mathcal{A}$ for
$\mathcal{H}$ w.r.t $\ell$ and setting $j=p$, is a realizable PAC learner for
$\mathcal{H}_{i}^{p}$ w.r.t 0-1 loss. The realizable-to-agnostic conversion
from Hopkins et al. [2022] can then be used convert Algorithm 5 into an
agnostic PAC learner. Since our choice of loss $\ell$ and index $i$ were
arbitrary, agnostic PAC learnability of $\mathcal{H}$ w.r.t any
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$ implies agnostic PAC
learnability of $\mathcal{H}_{i}^{p}$ w.r.t the 0-1 loss for all $i\in[K]$. ∎

Combining Lemma C.1, C.2 and C.3 gives Theorem 4.2.

##  Appendix D Proofs for Online Multilabel Ranking

###  D.1 Proof of Theorem 5.2

###### Proof.

(of sufficiency in Theorem 5.2) This proof is virtually identical to the proof
of sufficiency in Theorem 4.1. However, we provide the full details here for
completion. Our proof is also based on reduction. That is, given realizable
learners $\mathcal{A}_{i}^{p}$ of $\mathcal{H}_{i}^{p}$’s for $i\in[K]$ w.r.t.
$0$-$1$ loss, we will construct an agnostic learner $\mathcal{Q}$ for
$\mathcal{H}$ w.r.t. $\ell$. We will construct a set of experts $\mathcal{E}$
that uses $\mathcal{A}_{i}^{p}$ to make predictions and run the REWA algorithm
using these experts.

Let $(x_{1},y_{1}),...,(x_{T},y_{T})\in(\mathcal{X}\times\mathcal{Y})^{T}$
denote the stream of points to be observed by the online learner. As before,
we will assume an oblivious adversary.

For any bitstring $b\in\\{0,1\\}^{T}$, let
$\phi:\\{t\in[T]:b_{t}=1\\}\rightarrow\mathcal{S}_{K}$ denote a function
mapping time points where $b_{t}=1$ to permutations. Let
$\Phi_{b}\subseteq\mathcal{S}_{K}^{\\{t\in[T]:b_{t}=1\\}}$ denote all such
functions $\phi$. For every $b\in\\{0,1\\}^{T}$, use Algorithm 7 to define an
expert. And define $\mathcal{E}_{b}=\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$
to be the set of all Experts parameterized by functions $\phi\in\Phi_{b}$. As
before, we will actually define
$\mathcal{E}_{b}=\\{E_{0}\\}\cup\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$,
where $E_{0}$ is the expert that never updates $\mathcal{A}_{i}^{p}$’s and
only use them for predictions in all $t\in[T]$. Note that
$1\leq|\mathcal{E}_{b}|\leq(K!)^{|b|}\leq K^{K|b|}$. Using these experts,
Algorithm 3 is an agnostic online learner $\mathcal{Q}$ for
$\mathcal{\mathcal{H}}$ w.r.t $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$.
Again, we use $M$ as the upper bound on loss $\ell$.

Input: Independent copy of realizable learners $\mathcal{A}_{i}^{p}$ of
$\mathcal{H}_{i}^{p}$ for $i\in[K]$

1 for  _$t=1,...,T$_ do

2 Receive example $x_{t}$

3 Define a binary vote vector $v_{t}\in\mathbb{R}^{K}$ such that
$v_{t}[i]=\mathcal{A}_{i}^{p}(x_{t})$

4 Predict
$\hat{\pi}_{t}\in\operatorname*{arg\,min}_{\pi\in\mathcal{S}_{K}}\langle\pi,v_{t}\rangle$

5 if  _$b_{t}=1$_ then

6 For each $i\in[K]$, update $\mathcal{A}_{i}^{p}$ by passing
$(x_{t},\phi_{i}^{p}(t))$

7

8 end for

Algorithm 7 Expert $(b,\phi)$

∎

Using REWA guarantees and following exactly the same calculation as in the
proof of Theorem 5.1 we immediately arrive at

$\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{Q}(x_{t}),y_{t})\right]\leq\mathbbm{E}\left[\sum_{t=1}^{T}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\right]+M\sqrt{2T^{1+\beta}K\ln{K}},$

the analog of Equation (1) for this setting. Using Lemma E.2, we have

$\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\leq\ell(h^{\star}(x_{t}),y_{t})+\frac{M}{a}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),p))$

pointwise, where $M=\max_{\pi,y}\ell(\pi,y)$ and
$a=\min_{\pi,y}\\{\ell(\pi,y)\,\mid\,\ell(\pi,y)\neq 0\\}$. By definition of
$M$, we further get

$\begin{split}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),p))&\leq
M\,\mathbbm{1}\\{\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),p))>0\\}\\\
&=M\,\mathbbm{1}\\{\ell_{\text{prec}}^{@p}(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),p))>0\\},\end{split}$

where the equality follows from the fact that
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$.

In order to upperbound the indicator above, we will some more notations. Given
the realizable online learner $\mathcal{A}_{i}^{p}$ for $i\in[K]\times[p]$, an
instance $x\in\mathcal{X}$, and an ordered finite sequence of labeled examples
$L\in(\mathcal{X}\times\\{0,1\\})^{*}$, let $\mathcal{A}_{i}^{p}(x|L)$ be the
random variable denoting the prediction of $\mathcal{A}_{i}^{p}$ on the
instance $x$ after running and updating on $L$. For any $b\in\\{0,1\\}^{T}$,
$h_{i}^{p}\in\mathcal{H}_{i}^{p}$, and $t\in[T]$, let
$L_{b_{<t}}^{h}(i,p)=\\{(x_{s},h_{i}^{p}(x_{s})):s<t\text{ and }b_{s}=1\\}$
denote the subsequence of the sequence of labeled instances
$\\{(x_{s},h_{i}^{m}(x_{s}))\\}_{s=1}^{t-1}$ where $b_{s}=1$. Then, we have

$\begin{split}\mathbbm{1}\\{\ell_{\text{prec}}^{@p}(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),\text{BinRel}(h^{\star}(x_{t}),p))>0\\}&\leq\sum_{i=1}^{K}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq h_{i}^{\star,p}(x_{t})\\}\end{split}$

To prove this claimed inequality, consider the case when
$\sum_{i=1}^{K}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq h_{i}^{\star,p}(x_{t})\\}=0$ because the
inequality is trivial otherwise. Then, we must have
$\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))=h_{i}^{\star,p}(x_{t})$ for all $i\in[K]$. Let
$v_{t}\in\mathbb{R}^{K}$ such that $v_{t}[i]=\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))$ be a binary vote vector that the expert
$E_{B,\phi_{B}^{h^{\star}}}$ constructs in round $t$. Since $h^{\star}(x_{t})$
is a permutation, the vote vector $v_{t}$ must contain exactly $p$ labels with
$1$ vote and $K-p$ labels with $0$ votes. Thus, every
$\hat{\pi}_{t}\in\operatorname*{arg\,min}_{\pi\in\mathcal{S}_{K}}\langle\pi,v\rangle$
must rank labels with $1$ vote in top $p$ and labels with $0$ votes outside
top $p$. In other words, we must have
$\hat{\pi}\stackrel{{\scriptstyle\mathclap{p}}}{{=}}h^{\star}(x_{t})$, and
thus $\ell_{\text{prec}}^{@p}(\hat{\pi},\text{BinRel}(h^{\star}(x_{t}),p))=0$
by definition of $\ell_{\text{prec}}^{@p}$. Our claim follows because
$E_{B,\phi_{B}^{h^{\star}}}(x_{t})\in\operatorname*{arg\,min}_{\pi\in\mathcal{S}_{K}}\langle\pi,v\rangle$.

Combining everything, we obtain

$\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\leq\ell(h^{\star}(x_{t}),y_{t})+\frac{M}{a}\>\sum_{i=1}^{K}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq h_{i}^{\star,p}(x_{t})\\},$

which further implies that

$\mathbb{E}\left[\sum_{t=1}^{T}\ell(E_{B,\phi_{B}^{h^{\star}}}(x_{t}),y_{t})\right]\leq\sum_{t=1}^{T}\ell(h^{\star}(x_{t}),y_{t})+\frac{M}{a}\>\sum_{i=1}^{K}\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq h_{i}^{\star,p}(x_{t})\\}\right].$

So, it now suffices to show that
$\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq h_{i}^{\star,p}(x_{t})\\}\right]$ is a
sublinear function of $T$. Again, using the independence of $B_{t}$ and the
algorithm’s prediction in round $t$, we can write

$\begin{split}\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq
h_{i}^{\star,p}(x_{t})\\}\right]&=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq
h_{i}^{\star,p}(x_{t})\\}\right]\frac{\mathbb{P}\left[B_{t}=1\right]}{\mathbb{P}\left[B_{t}=1\right]}\\\
&=\frac{T}{T^{\beta}}\,\sum_{t=1}^{T}\operatorname{\mathbb{E}}\left[\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq
h_{i}^{\star,p}(x_{t})\\}\right]\mathbb{E}\left[\mathbbm{1}\\{B_{t}=1\\}\right]\\\
&=\frac{T}{T^{\beta}}\,\sum_{t=1}^{T}\operatorname{\mathbb{E}}\left[\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq
h_{i}^{\star,p}(x_{t})\\}\mathbbm{1}\left\\{B_{t}=1\right\\}\right].\end{split}$

Next, we can use the regret guarantee of the algorithm
$\mathcal{A}_{i}^{p\star}$ on the rounds it was updated. That is,

$\begin{split}\sum_{t=1}^{T}\operatorname{\mathbb{E}}\left[\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq
h_{i}^{\star,p}(x_{t})\\}\mathbbm{1}\left\\{B_{t}=1\right\\}\right]&=\operatorname{\mathbb{E}}\left[\sum_{t:B_{t}=1}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq h_{i}^{\star,p}(x_{t})\\}\right]\\\
&=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{E}}\left[\sum_{t:B_{t}=1}\mathbbm{1}\\{\mathcal{A}_{i}^{p}(x_{t}\mid
L_{B_{<t}}^{h^{\star}}(i,p))\neq
h_{i}^{\star,p}(x_{t})\\}\,\Bigg{|}B\right]\right]\\\
&\leq\operatorname{\mathbb{E}}_{B}\left[R_{i}^{p}(|B|)\right],\end{split}$

where $R_{i}^{p}(|B|)$ is a sublinear function of $|B|$. In the last step, we
use the fact that $\mathcal{A}_{i}^{p}$ is a realizable algorithm for
$\mathcal{H}_{i}^{p}$ and the feedback that the algorithm received was
$(x_{t},h_{i}^{\star,p}(x_{t}))$ in the rounds whenever $B_{t}=1$. Without
loss of generality, we assume that $R_{i}^{p}(|B|)$ is a concave function of
$|B|$. Otherwise, by Lemma 5.17 from Woess [2017], there exists a concave
sublinear function $\tilde{R}_{i}^{p}(|B|)$ that upperbounds $R_{i}^{p}(|B|)$.
By Jensen’s inequality, $\mathbbm{E}_{B}\left[R_{i}^{p}(|B|)\right]\leq
R_{i}^{p}(T^{\beta})$, a sublinear function of $T^{\beta}$.

Putting everything together, we obtain

$\begin{split}\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{Q}(x_{t}),y_{t})\right]&\leq\sum_{t=1}^{T}\ell(h^{\star}(x_{t}),y_{t})+\frac{M}{a}\sum_{i=1}^{K}\frac{T}{T^{\beta}}\,R_{i}^{p}(T^{\beta})+M\sqrt{2T^{1+\beta}K\ln{K}}\\\
&\leq\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(h(x_{t}),y_{t})+\frac{M}{a}\frac{T}{T^{\beta}}R(T^{\beta})+M\sqrt{2T^{1+\beta}K\ln{K}},\end{split}$

where we used the definition of $h^{\star}$ for the first term and defined
$R(T^{\beta})=\sum_{i=1}^{K}R_{i}^{p}(T^{\beta})$ for the second term. Since
$R(T^{\beta})$ is a sum of sublinear functions of $T^{\beta}$, it must be
sublinear. Subsequently, $T/T^{\beta}R(T^{\beta})=To(1)=o(T)$ is a sublinear
function of $T$. And the third term is sublinear for any choice of
$\beta\in(0,1)$. This completes our proof as we have shown that the algorithm
$\mathcal{Q}$ achieves sublinear regret in $T$.

###### Proof.

(of necessity in Theorem 5.2)

We will now show that the online learnability of $\mathcal{H}$ w.r.t $\ell$
implies that $\mathcal{H}_{i}^{p}$ for each $i\in[K]$ is online learnable
w.r.t 0-1 loss. Given an online learner $\mathcal{A}$ for $\mathcal{H}$ w.r.t
$\ell$, we will construct an online learner $\mathcal{A}_{i}^{p}$ for
$\mathcal{H}_{i}^{p}$ for a fixed $i\in[K]$ in the _realizable_ setting. One
can construct realizable online learners for $\mathcal{H}_{i}^{p}$ for all
$i\in[K]$ by symmetry. As before, showing $\mathcal{H}_{i}^{p}$ is learnable
in the realizable setting is sufficient. Our construction uses the Experts
algorithm REWA and is similar to the sufficiency proof above.

Let us define function $\phi$’s, the collection of functions $\Phi_{b}$ for
every $b$ in the same way we did before. For every $b\in\\{0,1\\}^{T}$ and
$\phi\in\Phi_{b}$, define an Expert $E_{b,\phi}$. Expert $E_{b,\phi}$, which
is identical to expert presented in Algorithm 4 with $j=p$, uses
$\mathcal{A}$’s to make predictions in each round. For every
$b\in\\{0,1\\}^{T}$, let
$\mathcal{E}_{b}=\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$ denote the set of
all Experts parameterized by functions $\phi\in\Phi_{b}$. As before, we will
actually define
$\mathcal{E}_{b}=\\{E_{0}\\}\cup\bigcup_{\phi\in\Phi_{b}}\\{E_{b,\phi}\\}$,
where $E_{0}$ is the expert that never updates $\mathcal{A}$ and only use them
for predictions in all $t\in[T]$. Note that
$1\leq|\mathcal{E}_{b}|\leq(K!)^{|b|}\leq K^{K|b|}$.

The realizable learner for $\mathcal{H}_{i}^{p}$, henceforth denoted by
$\mathcal{Q}$, is similar to Algorithm 3. First, it samples a
$B\in\\{0,1\\}^{T}$ s.t. $B_{t}\sim\text{Bernoulli}(T^{\beta}/T)$, construct
set of experts $\mathcal{E}_{B}$ using Algorithm 4 and run REWA, denoted by
$\mathcal{P}$, on $0$-$1$ loss over the realizable stream
$(x_{1},h_{i}^{\star,p}(x_{1})),...,(x_{T},h_{i}^{\star,p}(x_{T}))\in(\mathcal{X}\times\\{0,1\\})^{T}$
for some $h^{\star}\in\mathcal{H}$.

Using REWA guarantees and following exactly the same calculation as in the
sufficiency proof, we arrive at

$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{Q}(x_{t})\neq
h_{i}^{\star,p}(x_{t})\\}\right]\leq\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,p}(x_{t})\\}\right]+\sqrt{2T^{1+\beta}K\ln{K}}.$

The inequality above is the adaptation of Equation (1) for this proof, where
we use the fact that $y_{t}=h_{i}^{\star,p}(x_{t})$ and $M=1$. It now suffices
to show that
$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,p}(x_{t})\\}\right]$ is sublinear.

Given an online learner $\mathcal{A}$ for $\mathcal{H}$, an instance
$x\in\mathcal{X}$, and an ordered finite sequence of labeled examples
$L\in(\mathcal{X}\times\mathcal{Y})^{*}$, let $\mathcal{A}(x|L)$ be the random
variable denoting the prediction of $\mathcal{A}$ on the instance $x$ after
running and updating on $L$. For any $b\in\\{0,1\\}^{T}$, $h\in\mathcal{H}$,
and $t\in[T]$, let
$L^{h}_{b_{<t}}=\\{(x_{i},\text{BinRel}(h(x_{s}),j)):s<t\text{ and
}b_{s}=1\\}$ denote the subsequence of the sequence of labeled instances
$\\{(x_{s},\text{BinRel}(h(x_{s}),j))\\}_{s=1}^{t-1}$ where $b_{s}=1$. Using
Lemma E.4, we have

$\begin{split}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,p}(x_{t})\\}&\leq\mathbbm{1}\\{\ell_{\text{prec}}^{@p}(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),p))>0\\}\\\
&=\mathbbm{1}\\{\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),p))>0\\}\\\
&\leq\frac{M}{a}\,\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),p)),\end{split}$

where the equality follows from the definition of the loss class. Here, $M$ is
the upperbound on loss $\ell$ and $a$ is the lower bound whenever it is non-
zero. Thus, we obtain

$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{E_{B,\phi_{B}^{h^{\star}}}(x_{t})\neq
h_{i}^{\star,p}(x_{t})\\}\right]\leq\frac{M}{a}\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),p))\right]$

Now, we will again use the fact that the prediction $\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}})$ only depends on $(B_{1},\ldots,B_{t-1})$, but is
independent of $B_{t}$. Using this independence, we obtain

$\begin{split}\mathbbm{E}\left[\sum_{t=1}^{T}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),p))\right]&\leq\frac{T}{T^{\beta}}\,\mathbbm{E}\left[\sum_{t:B_{t}=1}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),p))\right]\\\
&=\frac{T}{T^{\beta}}\,\mathbbm{E}\left[\mathbbm{E}\left[\sum_{t:B_{t}=1}\ell(\mathcal{A}(x_{t}\mid
L^{h^{\star}}_{B_{<t}}),\text{BinRel}(h^{\star}(x_{t}),p))\,\Bigg{|}B\right]\right]\\\
&\leq\frac{T}{T^{\beta}}\operatorname{\mathbb{E}}\left[R(|B|,K)\right],\end{split}$

where $R(|B|,K)$ is the regret of the algorithm $\mathcal{A}$ and is a
sublinear function of $|B|$. In the last step, we use the fact that
$\mathcal{A}$ is a (realizable) online learner for $\mathcal{H}$ w.r.t. $\ell$
and the feedback that the algorithm received was
$(x_{t},\text{BinRel}(h^{\star}(x_{t}),p))$ in the rounds whenever $B_{t}=1$.
Again, using Lemma 5.17 from Woess [2017] and Jensen’s inequality yields
$\mathbbm{E}_{B}\left[R(|B|,K)\right]\leq R(T^{\beta},K)$, a sublinear
function of $T^{\beta}$. Combining everything, we get

$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{Q}(x_{t})\neq
h_{i}^{\star,p}(x_{t})\\}\right]\leq\frac{M}{a}\frac{T}{T^{\beta}}R(T^{\beta},K)+\sqrt{2T^{1+\beta}K\ln{K}}.$

For any choice of $0<\beta<1$, the upperbound above is a sublinear function of
$T$. Therefore, we have shown that $\mathcal{Q}$ is a realizable learner for
$\mathcal{H}_{i}^{p}$ w.r.t. $0$-$1$ loss. Since realizable and agnostic
online learnability is equivalent for binary classification problems, we have
shown that $\mathcal{H}_{i}^{p}$ is agnostic online learnable. This completes
our proof. ∎

##  Appendix E Useful Lemmas

######  Lemma E.1.

For any $y\in\mathcal{Y}$, $(\pi,\hat{\pi})\in\mathcal{S}_{k}$, and
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$

$\ell(\pi,y)\leq\ell(\hat{\pi},y)+cp\mathbbm{E}_{j\sim\text{Unif}([p])}\left[\ell(\pi,\text{BinRel}(\hat{\pi},j))\right].$

where
$c=\frac{\max_{\tilde{\pi},y}\ell(\tilde{\pi},y)}{\min_{\tilde{\pi},y\text{
s.t }\ell(\tilde{\pi},y)>0}\ell(\tilde{\pi},y)}.$

###### Proof.

Assume that $\ell(\pi,y)>\ell(\hat{\pi},y)\geq 0$ (as otherwise the inequality
trivially holds). Then, since $\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$, it
must be the case that $\hat{\pi}\stackrel{{\scriptstyle[p]}}{{\neq}}\pi$. That
is, $\hat{\pi}$ and $\pi$ assign different ranks to the labels in the top $p$.
Therefore, there exists $i\in[p]$ s.t.
$\ell_{\text{sum}}^{@p}(\pi,\text{BinRel}(\hat{\pi},i))>0$. Since
$\ell\in\mathcal{L}(\ell_{\text{sum}}^{@p})$, for this same $i\in[p]$,
$\ell(\pi,\text{BinRel}(\hat{\pi},i))>0$. Therefore, we have

$\displaystyle
cp\mathbbm{E}_{j\sim\text{Unif}([p])}\left[\ell(\pi,\text{BinRel}(\hat{\pi},j))\right]$
$\displaystyle\geq c\ell(\pi,\text{BinRel}(\hat{\pi},i))$
$\displaystyle=\frac{\max_{\tilde{\pi},y}\ell(\tilde{\pi},y)}{\min_{\tilde{\pi},y\text{
s.t
}\ell(\tilde{\pi},y)>0}\ell(\tilde{\pi},y)}\ell(\pi,\text{BinRel}(\hat{\pi},i))$
$\displaystyle\geq\max_{\tilde{\pi},y}\ell(\tilde{\pi},y)$
$\displaystyle\geq\ell(\pi,y).$

Combining the upperbounds in both cases gives the desired inequality. ∎

######  Lemma E.2.

For any $y\in\mathcal{Y}$, $(\pi,\hat{\pi})\in\mathcal{S}_{k}$, and
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$

$\ell(\pi,y)\leq\ell(\hat{\pi},y)+c\ell(\pi,\text{BinRel}(\hat{\pi},p)).$

where
$c=\frac{\max_{\tilde{\pi},y}\ell(\tilde{\pi},y)}{\min_{\tilde{\pi},y\text{
s.t }\ell(\tilde{\pi},y)>0}\ell(\tilde{\pi},y)}.$

###### Proof.

Assume that $\ell(\pi,y)>\ell(\hat{\pi},y)\geq 0$ (as otherwise the inequality
trivially holds). Then, since $\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$,
it must be the case that $\hat{\pi}\stackrel{{\scriptstyle p}}{{\neq}}\pi$.
That is, $\hat{\pi}$ and $\pi$ assign different labels in the top $p$.
Therefore, $\ell_{\text{prec}}^{@p}(\pi,\text{BinRel}(\hat{\pi},p))>0$. Since
$\ell\in\mathcal{L}(\ell_{\text{prec}}^{@p})$,
$\ell(\pi,\text{BinRel}(\hat{\pi},p))>0$. Therefore, we have

$\displaystyle c\ell(\pi,\text{BinRel}(\hat{\pi},p))$
$\displaystyle=\frac{\max_{\tilde{\pi},y}\ell(\tilde{\pi},y)}{\min_{\tilde{\pi},y\text{
s.t
}\ell(\tilde{\pi},y)>0}\ell(\tilde{\pi},y)}\ell(\pi,\text{BinRel}(\hat{\pi},p))$
$\displaystyle\geq\max_{\tilde{\pi},y}\ell(\tilde{\pi},y)$
$\displaystyle\geq\ell(\pi,y).$

Combining the upperbounds in both cases gives the desired inequality. ∎

######  Lemma E.3.

Let $\pi,\hat{\pi}\in\mathcal{S}_{k}$. Then, for all $(i,j)\in[K]\times[p]$,
$\ell^{@p}_{\text{sum}}(\pi,\text{BinRel}(\hat{\pi},j))\geq\mathbbm{1}\\{\pi_{i}^{j}\neq\hat{\pi}_{i}^{j}\\}$.

###### Proof.

Fix item $i^{\star}\in[K]$ and threshold $j^{\star}\in[p]$. Our goal is to
show that
$\ell^{@p}_{\text{sum}}(\pi,\text{BinRel}(\hat{\pi},j^{\star}))\geq\mathbbm{1}\\{\pi_{i^{\star}}^{j^{\star}}\neq\hat{\pi}_{i^{\star}}^{j^{\star}}\\}$.
Recall that
$\text{BinRel}(\hat{\pi},j^{\star})[i^{\star}]=\mathbbm{1}\\{\hat{\pi}_{i^{\star}}\leq
j^{\star}\\}$ by definition. Since
$\ell_{\text{sum}}^{@p}(\hat{\pi},\text{BinRel}(\hat{\pi},j^{\star}))=0$, we
have that

$\displaystyle\ell_{\text{sum}}^{@p}(\pi,\text{BinRel}(\hat{\pi},j^{\star}))$
$\displaystyle=\ell^{@p}_{\text{sum}}(\pi,\text{BinRel}(\hat{\pi},j^{\star}))-\ell^{@p}_{\text{sum}}(\hat{\pi},\text{BinRel}(\hat{\pi},j^{\star}))$
$\displaystyle=\sum_{i=1}^{K}\min(\pi_{i},p+1)\text{BinRel}(\hat{\pi},j^{\star})[i]-\sum_{i=1}^{K}\min(\hat{\pi}_{i},p+1)\text{BinRel}(\hat{\pi},j^{\star})[i]$
$\displaystyle=\sum_{i=1}^{K}\min(\pi_{i},p+1)\mathbbm{1}\\{\hat{\pi}_{i}\leq
j^{\star}\\}-\sum_{i=1}^{K}\min(\hat{\pi}_{i},p+1)\mathbbm{1}\\{\hat{\pi}_{i}\leq
j^{\star}\\}$
$\displaystyle=\sum_{i=1}^{K}\min(\pi_{i},p+1)\mathbbm{1}\\{\hat{\pi}_{i}\leq
j^{\star}\\}-\sum_{i=1}^{K}\hat{\pi}_{i}\mathbbm{1}\\{\hat{\pi}_{i}\leq
j^{\star}\\}$

Let $\mathcal{I}\subset[K]$ s.t. for all $i\in\mathcal{I}$,
$\hat{\pi}_{i}^{j^{\star}}=\mathbbm{1}\\{\hat{\pi}_{i}\leq j^{\star}\\}=1$.
Then, we have that

$\displaystyle\ell_{\text{sum}}^{@p}(\pi,\text{BinRel}(\hat{\pi},j^{\star}))$
$\displaystyle=\sum_{i\in\mathcal{I}}\min(\pi_{i},p+1)-\sum_{i\in\mathcal{I}}\hat{\pi}_{i}$
$\displaystyle=\sum_{i\in\mathcal{I}}\min(\pi_{i},p+1)-\min_{\pi\in\mathcal{S}_{k}}\sum_{i\in\mathcal{I}}\pi_{i}$
$\displaystyle=\sum_{i\in\mathcal{I}}\min(\pi_{i},p+1)-\sum_{i=1}^{j^{\star}}i$

Suppose that
$\mathbbm{1}\\{\pi_{i^{\star}}^{j^{\star}}\neq\hat{\pi}_{i^{\star}}^{j^{\star}}\\}=1$.
It suffices to show that
$\ell_{\text{sum}}^{@p}(\pi,\text{BinRel}(\hat{\pi},j^{\star}))\geq 1$. There
are two cases to consider. Suppose $i^{\star}\in\mathcal{I}$. Then, it must be
the case that $\mathbbm{1}\\{\pi_{i^{\star}}\leq
j^{\star}\\}=\pi_{i^{\star}}^{j^{\star}}=0$, implying that
$\pi_{i^{\star}}\geq j^{\star}+1$. It then follows that in the best case
$\sum_{i\in\mathcal{I}}\min(\pi_{i},p+1)\geq\sum_{i=1}^{j^{\star}-1}i+(j^{\star}+1)>\sum_{i=1}^{j^{\star}}i$
showcasing that indeed
$\ell_{\text{sum}}^{@p}(\pi,\text{BinRel}(\hat{\pi},j))\geq 1$. Now, suppose
$i^{\star}\notin\mathcal{I}$. Then, $\mathbbm{1}\\{\hat{\pi}_{i^{\star}}\leq
j^{\star}\\}=0$, which means that $\mathbbm{1}\\{\pi_{i^{\star}}\leq
j^{\star}\\}=1$. Accordingly, while $\hat{\pi}$ did not rank item $i^{\star}$
in the top $j^{\star}$, $\pi$ did rank item $i^{\star}$ in the top
$j^{\star}$. Since $|\mathcal{I}|=j^{\star}$, there must exist an item
$\hat{i}\in\mathcal{I}$ which $\pi$ does not rank in the top $j^{\star}$. That
is, there exists $\hat{i}\in\mathcal{I}$ s.t. $\pi_{\hat{i}}\geq j^{\star}+1$.
Using the same logic, in the best case
$\sum_{i\in\mathcal{I}}\min(\pi_{i},p+1)\geq\sum_{i=1}^{j-1}i+(j^{\star}+1)$
showcasing that again
$\ell_{\text{sum}}^{@p}(\pi,\text{BinRel}(\hat{\pi},j^{\star}))\geq 1$. Thus,
we have shown that when
$\mathbbm{1}\\{\pi_{i^{\star}}^{j^{\star}}\neq\hat{\pi}_{i^{\star}}^{j^{\star}}\\}=1$,
$\ell_{\text{sum}}^{@p}(\pi,\text{BinRel}(\hat{\pi},j^{\star}))\geq 1$. Since
$i^{\star}$ and $j^{\star}$ were arbitrary, this must be true for any
$(i,j)\in[K]\times[p]$, completing the proof.

∎

######  Lemma E.4.

Let $\pi,\hat{\pi}\in\mathcal{S}_{k}$. Then, for all $i\in[K]$,
$\ell^{@p}_{\text{prec}}(\pi,\text{BinRel}(\hat{\pi},p))\geq\mathbbm{1}\\{\pi_{i}^{p}\neq\hat{\pi}_{i}^{p}\\}$.

###### Proof.

Fix item $i^{\star}\in[K]$. Our goal is to show that