# A Combinatorial Characterization of Online Learning Games with Bounded
Losses

Vinod Raman  Unique Subedi  Ambuj Tewari

###### Abstract

We study the online learnability of hypothesis classes with respect to
arbitrary, but bounded, loss functions. We give a new scale-sensitive
combinatorial dimension, named the sequential Minimax dimension, and show that
it gives a tight quantitative characterization of online learnability. As
applications, we give the first quantitative characterization of online
learnability for two natural learning settings: vector-valued regression and
multilabel classification.

##  1 Introduction

The learnability of a hypothesis class $\mathcal{H}$ is a fundamental question
in online learning theory. In the standard supervised model, a learner plays a
repeated game against an adversary over $T\in\mathbb{N}$ rounds. In each round
$t\in[T]$, an adversary picks a labeled example
$(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$ and reveals $x_{t}$ to the
learner. The learner observes $x_{t}$, picks a probability measure $\mu_{t}$
over $\mathcal{Z}$, and then makes a randomized prediction $z_{t}\sim\mu_{t}$.
Finally, the adversary reveals the true label $y_{t}$ and the learner suffers
the loss $\ell(y_{t},z_{t})$, where
$\ell:\mathcal{Y}\times\mathcal{Z}\rightarrow\mathbb{R}_{\geq 0}$ is some pre-
specified, bounded loss function. At the end of $T$ rounds, the expected
regret is the expected difference between the cumulative loss of the learner’s
predictions and that of the best fixed hypothesis in hindsight. We say a tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$ is online learnable
if there exists a learner such that its expected regret is a sublinear
function of $T$, for any strategy of the adversary.

Mathematically, we can reformulate the notion of online learnability in terms
of the minimax value of the game (Rakhlin et al., 2015a), defined as

$\mathcal{V}_{T}(\mathcal{H},\ell):=\sup_{x_{1}\in\mathcal{X}}\inf_{\mu_{1}\in\Pi(\mathcal{Z})}\sup_{y_{1}\in\mathcal{Y}}\operatorname*{\operatorname{\mathbb{E}}}_{z_{1}\sim\mu_{1}}\ldots\sup_{x_{T}\in\mathcal{X}}\inf_{\mu_{T}\in\Pi(\mathcal{Z})}\sup_{y_{T}\in\mathcal{Y}}\operatorname*{\operatorname{\mathbb{E}}}_{z_{t}\sim\mu_{T}}\left[\sum_{t=1}^{T}\ell(y_{t},z_{t})-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{t},h(x_{t}))\right],$

where $\Pi(\mathcal{Z})$ is the set of all probability measures over a measure
space $(\mathcal{Z},\sigma(\mathcal{Z}))$. Equivalently, we say a tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$ is online learnable
if and only if the minimax value of the associated game satisfies

$\limsup_{T\to\infty}\frac{\mathcal{V}_{T}(\mathcal{H},\ell)}{T}\leq 0.$

In other words, we require $\mathcal{V}_{T}(\mathcal{H},\ell)$ to be a
sublinear function of $T$.

In this work, we are interested in characterizing online learnability in full
generality. The only known sequential complexity measure for an arbitrary
tuple $(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$ is the
sequential Rademacher complexity of the loss class
$\ell\circ\mathcal{H}:=\\{(x,y)\mapsto\ell(y,h(x)):h\in\mathcal{H}\\}$.
Rakhlin et al. (2015a) show that this complexity measure upper bounds the
minimax value of the game, thus providing a sufficient condition for online
learnability in general. In particular, Rakhlin et al. (2015a) show that if
the sequential Rademacher complexity of the loss class $\ell\circ\mathcal{H}$
is sublinear in the time horizon $T$, then the tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$ is online learnable.
However, Hanneke et al. (2023) prove that even for the natural problem of
online multiclass classification, sublinear sequential Rademacher complexity
is not necessary for online learnability. Accordingly, we investigate the
following question.

Guiding Question 1 Given any tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$, what are necessary
and sufficient conditions for $\mathcal{H}$ to be online learnable with
respect to $\ell$?

In many settings, the online learnability of a tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$ is characterized in
terms of a combinatorial dimension. For instance, when
$\mathcal{Z}=\mathcal{Y}$ and $\ell(y,z)=\mathbbm{1}\\{y\neq z\\}$, the
Littlestone dimension of $\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$,
denoted $\text{Ldim}(\mathcal{H})$, characterizes its online learnability.
That is, a hypothesis class $\mathcal{H}$ is online learnable with respect to
the 0-1 loss if and only if $\text{Ldim}(\mathcal{H})$ is finite (Littlestone,
1987; Daniely et al., 2011; Hanneke et al., 2023). When
$\mathcal{Z}=\mathcal{Y}$ is a bounded subset of $\mathbb{R}$, the sequential
fat-shattering dimension of a real-valued function class
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$, denoted $\text{seq-
fat}_{\gamma}(\mathcal{H})$, characterizes the online learnability of
$\mathcal{H}$ with respect to the absolute value loss. Rakhlin et al. (2015a)
show that a real-valued function class
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ is online learnable with
respect to the absolute value loss if and only if its sequential fat-
shattering dimension is finite at every scale $\gamma>0$.

Remarkably, the Littlestone and sequential fat-shattering dimension also
provide a tight quantitative characterization of online learnability,
appearing in both the lower and upper bounds of their respective minimax
values. In addition, the finiteness of these dimension allows us to design
generic online learners for arbitrary hypothesis classes in their respective
settings. This motivates the next question we investigate.

Guiding Question 2 Given any tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$, is there a
combinatorial dimension that provides a tight quantitative characterization of
the online learnability of $\mathcal{H}$ with respect to $\ell$? If so, does
its finiteness lead to a generic online learner?

Guided by these two questions, we make the following contributions.

Main Technical Contributions 1. We give a new scale-sensitive dimension, named
the sequential Minimax dimension (SMdim), that gives a tight quantitative
characterization of online learnability for any tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$. 2. Using SMdim, we
construct a generic online learner for any tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$. 3. We show that the
SMdim reduces to existing combinatorial dimensions in the case where
$\mathcal{Z}=\mathcal{Y}$, like the Ldim and seq-fat, as well as the case
where $\mathcal{Z}\neq\mathcal{Y}$, like the $(k+1)$-Ldim from Moran et al.
(2023) and MSdim from Raman et al. (2023b). 4. We give the first quantitative
characterization of online learnability for two natural learning settings:
vector-valued regression and multilabel classification.

###  1.1 Related Works

Characterizing learnability in terms of complexity measures has a long rich
history in statistical learning theory, originating from the seminal work of
Vapnik and Chervonenkis (1971). In online learning, Littlestone (1987) showed
that a combinatorial parameter, later named as Littlestone dimension, provides
a quantitative characterization of online binary classification in the
realizable setting. Twenty-two years later, Ben-David et al. (2009) proved
that the Littlestone dimension also provides a tight quantitative
characterization of online binary classification in the agnostic setting.
Daniely et al. (2011) generalized the Littlestone dimension to multiclass
classification and showed that it fully characterizes online learnability when
the label space is finite. Recently, Hanneke et al. (2023) proved that the
multiclass extension of the Littlestone dimension characterizes multiclass
learnability under the $0$-$1$ loss even when the label space is unbounded. In
a parallel line of work, Rakhlin et al. (2015a, b) defined the sequential fat-
shattering dimension and showed that it tightly characterizes the online
learnability of scalar-valued regression with respect to the absolute value
loss. In addition, they defined a general complexity measure called the
sequential Rademacher complexity and proved that it upper bounds the minimax
value of any online game. In a similar spirit, we define a complexity measure
that upper and lower bounds the minimax value of any online game.

The proof techniques in online learning are generally constructive and result
in beautiful algorithms such as Follow The (Regularized) Leader, Hedge,
Multiplicative Weights, Online Gradient Descent, and so forth. In online
binary classification, Littlestone (1987) proposed the Standard Optimal
Algorithm and proved its optimality in the realizable setting. Daniely et al.
(2011) and Rakhlin et al. (2015a) generalize this algorithm to multiclass
classification and scalar-valued regression respectively. The ideas of the
Standard Optimal Algorithm is foundational in online learning and still
appears in more recent works by Moran et al. (2023); Filmus et al. (2023) and
Raman et al. (2023b). A common theme in these variants of the Standard Optimal
Algorithm is their use of combinatorial dimensions to make predictions.
Similarly, Rakhlin et al. (2012) use the sequential Rademacher complexity to
directly construct a generic online learner in the agnostic setting. However,
their online learner requires the sequential Rademacher complexity of the loss
class to be sublinear in $T$, and thus does not work for arbitrary tuples
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$. Closing this gap, we
define a new scale-sensitive dimension, named the sequential Minimax
dimension, and use it to give a generic online learner for any tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$.

##  2 Preliminaries

###  2.1 Notation

Let $\mathcal{X}$ denote the instance space, $\mathcal{Y}$ denote the label
space, and $\mathcal{Z}$ denote the prediction space. For a sigma algebra
$\sigma(\mathcal{Z})$ on the prediction space $\mathcal{Z}$, define
$\Pi(\mathcal{Z})$ to be the set of all distributions on
$(\mathcal{Z},\sigma(\mathcal{Z}))$. For any set $S\in\sigma(\mathcal{Z})$,
let $S^{c}$ denote its complement. Let
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ denote an arbitrary hypothesis
class consisting of predictors $h:\mathcal{X}\rightarrow\mathcal{Z}$ that maps
an instance to a prediction. Given any prediction $z\in\mathcal{Z}$ and a
label $y\in\mathcal{Y}$, we consider a loss function
$\ell:\mathcal{Y}\times\mathcal{Z}\to\mathbb{R}_{\geq 0}$. We put no
restrictions on the loss function $\ell$, except that it is bounded,
$\sup_{y,z}\ell(y,z)\leq c$ for some $c\in\mathbb{R}_{>0}$. In particular, the
loss can asymmetric, and therefore we reserve the first argument for the label
and the second argument for the prediction. Finally, we let $[N]$ denote the
set of positive integers $\\{1,2,\ldots,N\\}$.

###  2.2 Online Learning

In the online setting, an adversary plays a sequential game with the learner
over $T$ rounds. In each round $t\in[T]$, the adversary selects a labeled
instance $(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$ and reveals $x_{t}$ to
the learner. The learner picks a probability measure
$\mu_{t}\in\Pi(\mathcal{Z})$ and then makes a randomized prediction
$z_{t}\sim\mu_{t}$. Finally, the adversary reveals the feedback $y_{t}$, and
the learner suffers the loss $\ell(y_{t},z_{t})$. As is standard in online
learning, we consider an adaptive adversary that can use learner’s measure
$\mu_{t}$ to select the label $y_{t}$, but not its prediction $z_{t}$. To
formally define an online learning algorithm, we follow the convention in
Chapter 4 of Cesa-Bianchi and Lugosi (2006).

Definition 1:  Online Learning Algorithm An online learning algorithm is a
deterministic mapping
$\mathcal{A}:(\mathcal{X}\times\mathcal{Y})^{\star}\times\mathcal{X}\to\Pi(\mathcal{Z})$
that maps past examples and the newly revealed instance $x\in\mathcal{X}$ to a
probability measure $\mu\in\Pi(\mathcal{Z})$. The learner then randomly
samples $z\sim\mu$ to make a prediction.

Although $\mathcal{A}$ is a deterministic mapping, the prediction $z\sim\mu$
is random. Restricting the range of $\mathcal{A}$ to be the set of Dirac
measures on $\mathcal{Z}$ yields a deterministic online learner. When the
context is clear, with a slight abuse of notation, we use $\mathcal{A}(x)$ to
denote the random sample $z$ drawn from the distribution that $\mathcal{A}$
outputs.

We say that $\mathcal{H}$ is online learnable with respect to $\ell$ if there
exists an online learning algorithm such that for any sequence of labeled
examples, $(x_{1},y_{1}),...,(x_{T},y_{T})$, the difference in expected
cumulative loss between its predictions and the predictions of the best-fixed
hypothesis in $\mathcal{H}$ is small. We formalize this notion in the
following definition.

Definition 2:  Online Agnostic Learnability A hypothesis class
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ is online learnable if there
exists an 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{Z}$ at every iteration
$t\in[T]$ such that
$\mathbb{E}\left[\sum_{t=1}^{T}\ell(y_{t},\mathcal{A}(x_{t}))-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{t},h(x_{t}))\right]\leq
R_{\mathcal{A}}(T)$ where the expectation is taken with respect to the
randomness of $\mathcal{A}$ and that of the possibly adaptive adversary, and
$R_{\mathcal{A}}(T):\mathbb{N}\rightarrow\mathbb{R}^{+}$ is a non-decreasing,
sub-linear function of $T$ referred to as the regret of $\mathcal{A}$.

Note that the existence of an online learner with sublinear regret is
equivalent to requiring
$\limsup_{T\to\infty}\frac{\mathcal{V}_{T}(\mathcal{H},\ell)}{T}\leq 0$. A
sequence of labeled examples $(x_{1},y_{1}),...,(x_{T},y_{T})$ is said to be
realizable by $\mathcal{H}$ if there exists a hypothesis
$h^{\star}\in\mathcal{H}$ such that $\ell(y_{t},h^{\star}(x_{t}))=0$ for all
$t\in[T]$. In such case, we have
$\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{t},h(x_{t}))=0$, and the setting
is typically referred to as the realizable setting.

##  3 Combinatorial Dimensions in Online Learning

Combinatorial dimensions play an important role in understanding when a
hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is online
learnable. As discussed in the introduction, two important examples are the
Littlestone and the sequential fat-shattering dimension, which characterize
the online learnability of classification and scalar-valued regression
respectively. Common to both the Littlestone and sequential fat-shattering
dimension is their definition in terms of trees, a basic combinatorial object
that captures the temporal dependence in online learning. Accordingly, we
start this section by formally defining the notion of a tree. Our notation is
borrowed from Rakhlin et al. (2015a) and Raman et al. (2023b).

Given an instance space $\mathcal{X}$ and a (potentially uncountable) set of
objects $\mathcal{M}$, a $\mathcal{X}$-valued, $\mathcal{M}$-ary tree
$\mathcal{T}$ of depth $T$ is a complete rooted tree such that (1) each
internal node $v$ is labeled by an instance $x\in\mathcal{X}$ and (2) for
every internal node $v$ and object $m\in\mathcal{M}$, there is an outgoing
edge $e^{m}_{v}$ indexed by $m$. Such a tree can be identified by a sequence
$(\mathcal{T}_{1},...,\mathcal{T}_{T})$ of labeling functions
$\mathcal{T}_{t}:\mathcal{M}^{t-1}\rightarrow\mathcal{X}$ which provide the
labels for each internal node. A path of length $T$ is given be a sequence of
objects $m=(m_{1},...,m_{T})\in\mathcal{M}^{T}$. Then,
$\mathcal{T}_{t}(m_{1},...,m_{t-1})$ gives the label of the node by following
the path $(m_{1},...,m_{t-1})$ starting from the root node, going down the
edges indexed by the $m_{t}$’s. We let $\mathcal{T}_{1}\in\mathcal{X}$ denote
the instance labeling the root node. For brevity, we define
$m_{<t}=(m_{1},...,m_{t-1})$ and therefore write
$\mathcal{T}_{t}(m_{1},...,m_{t-1})=\mathcal{T}_{t}(m_{<t})$. Analogously, we
let $m_{\leq t}=(m_{1},...,m_{t})$.

Often, it is useful to label the edges of a tree with some auxiliary
information. Given a $\mathcal{X}$-valued, $\mathcal{M}$-ary tree
$\mathcal{T}$ of depth $T$ and a (potentially uncountable) set of objects
$\mathcal{N}$, we can formally label the edges of $\mathcal{T}$ using objects
in $\mathcal{N}$ by considering a sequence $(f_{1},...,f_{T})$ of edge-
labeling functions $f_{t}:\mathcal{M}^{t}\rightarrow\mathcal{N}$. For each
depth $t\in[T]$, the function $f_{t}$ takes as input a path $m_{\leq t}$ of
length $t$ and outputs an object in $\mathcal{N}$. Accordingly, we can think
of the object $f_{t}(m_{\leq t})$ as labeling the edge indexed by $m_{t}$
after following the path $m_{<t}$ down the tree. We now use this notation to
rigorously define existing combinatorial dimensions in online learning.

###  3.1 Existing Combinatorial Dimensions

We start of with the Littlestone dimension, first proposed by Littlestone
(1987) for binary classification, and then generalized by Daniely et al.
(2011) to multiclass classification. In classification, we take
$\mathcal{Z}=\mathcal{Y}$ and $\ell(y,z)=\mathbbm{1}\\{y\neq z\\}$.

Definition 3:  Littlestone dimension Let $\mathcal{T}$ be a complete,
$\mathcal{X}$-valued, $\\{\pm 1\\}$-ary tree of depth $d$. The tree
$\mathcal{T}$ is shattered by $\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$
if there exists a sequence $(f_{1},...,f_{d})$ of edge-labeling functions
$f_{t}:\\{\pm 1\\}^{t}\rightarrow\mathcal{Y}$ such that for every path
$\sigma=(\sigma_{1},...,\sigma_{d})\in\\{\pm 1\\}^{d}$, there exists a
hypothesis $h_{\sigma}\in\mathcal{H}$ such that for all $t\in[d]$,
$h_{\sigma}(\mathcal{T}_{t}(\sigma_{<t}))=f_{t}(\sigma_{\leq t})$ and
$f_{t}((\sigma_{<t},-1))\neq f_{t}((\sigma_{<t},+1))$. The Littlestone
dimension of $\mathcal{H}$, denoted $\text{Ldim}(\mathcal{H})$, is the maximal
depth of a tree $\mathcal{T}$ that is shattered by $\mathcal{H}$. If there
exists shattered trees of arbitrarily large depth, we say
$\text{Ldim}(\mathcal{H})=\infty$.

It is well known that the Littlestone dimension characterizes online
learnability with respect to the 0-1 loss (Littlestone, 1987; Ben-David et
al., 2009; Daniely et al., 2011; Hanneke et al., 2023). For online regression,
we take $\mathcal{Z}=\mathcal{Y}=[-1,1]$, $\ell(y,z)=|y-z|$, and define the
sequential-fat shattering dimension.

Definition 4:  Sequential Fat-shattering dimension Let $\mathcal{T}$ be a
complete, $\mathcal{X}$-valued, $\\{\pm 1\\}$-ary tree of depth $d$ and fix
$\gamma\in(0,1]$. The tree $\mathcal{T}$ is $\gamma$-shattered by
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ if there exists a sequence
$(f_{1},...,f_{d})$ of edge-labeling functions $f_{t}:\\{\pm
1\\}^{t}\rightarrow\mathcal{Y}$ such that for every path
$\sigma=(\sigma_{1},...,\sigma_{d})\in\\{\pm 1\\}^{d}$, there exists a
hypothesis $h_{\sigma}\in\mathcal{H}$ such that for all $t\in[d]$,
$\sigma_{t}(h_{\sigma}(\mathcal{T}_{t}(\sigma_{<t}))-f_{t}(\sigma_{\leq
t}))\geq\gamma$ and $f_{t}((\sigma_{<t},-1))=f_{t}((\sigma_{<t},+1))$. The
sequential fat-shattering dimension of $\mathcal{H}$ at scale $\gamma$,
denoted $\text{seq-fat}_{\gamma}(\mathcal{H})$, is the maximal depth of a tree
$\mathcal{T}$ that is $\gamma$-shattered by $\mathcal{H}$. If there exists
$\gamma$-shattered trees of arbitrarily large depth, we say that $\text{seq-
fat}_{\gamma}(\mathcal{H})=\infty$.

Unlike the Littlestone dimension, the two outgoing edges from every internal
node in the sequential fat-shattering tree are labeled by the same real number
in $\mathcal{Y}$. These scalars labeling the outgoing edges in the sequential
fat-shattering tree are commonly referred to as witnesses to shattering in
literature. Rakhlin et al. (2015a) showed that
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ is online learnable with
respect to the absolute value loss if and only if $\text{seq-
fat}_{\gamma}(\mathcal{H})$ is finite at every scale $\gamma>0$.

We now move to the more recent setting of list online classification (Moran et
al., 2023). Here, we take $\mathcal{Z}=\\{S:S\subset\mathcal{Y},|S|\leq k\\}$
and $\ell(y,z)=\mathbbm{1}\\{y\notin z\\}$. That is, the learner is allowed to
play a set of labels of size at most $k$ and is penalized only if the true
label is not in this set. Moran et al. (2023) show that the $(k+1)$\-
Littlestone dimension, characterizes online learnability of a hypothesis class
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$.

Definition 5:  $(k+1)\text{-Littlestone dimension}$ Let $\mathcal{T}$ be a
complete, $\mathcal{X}$-valued, $[k+1]$-ary tree of depth $d$. The tree
$\mathcal{T}$ is shattered by $\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$
if there exists a sequence $(f_{1},...,f_{d})$ of edge-labeling functions
$f_{t}:[k+1]^{t}\rightarrow\mathcal{Y}$ such that for every path
$p=(p_{1},...,p_{d})\in[k+1]^{d}$, there exists a hypothesis
$h_{p}\in\mathcal{H}$ such that for all $t\in[d]$, $f_{t}(p_{\leq t}))\in
h_{\sigma}(\mathcal{T}_{t}(\sigma_{<t}))$ and for all distinct $i,j\in[k+1]$,
$f_{t}((p_{<t},i))\neq f_{t}((p_{<t},j))$. The $(k+1)$-Littlestone dimension
of $\mathcal{H}$ denoted $\text{Ldim}_{k+1}(\mathcal{H})$, is the maximal
depth of a tree $\mathcal{T}$ that is shattered by $\mathcal{H}$. If there
exists shattered trees of arbitrarily large depth, we say that
$\text{Ldim}_{k+1}(\mathcal{H})=\infty$.

At a high-level, the $(k+1)$-Littlestone tree is a $[k+1]$-ary tree where
every internal node has $k+1$ outgoing edges indexed by natural numbers in
$[k+1]$ and labeled by different labels in $\mathcal{Y}$. In this way, when
$k=1$, the $(k+1)$-Littlestone dimension reduces to the original Littlestone
dimension. Finally, we consider the “flip” of list online classification where
now $\mathcal{Y}\subset\sigma(\mathcal{Z})$ is some collection of measurable
subsets of $\mathcal{Z}$ and $\ell(y,z)=\mathbbm{1}\\{z\notin y\\}$. In this
setting, Raman et al. (2023b) show that the Measure shattering dimension
characterizes online learnability of a hypothesis class
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ under set-valued feedback.

Definition 6:  Measure shattering dimension Let $\mathcal{T}$ be a complete
$\mathcal{X}$-valued, $\Pi(\mathcal{Z})$-ary tree of depth $d$, and fix
$\gamma\in(0,1]$. The tree $\mathcal{T}$ is $\gamma$-shattered by
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ if there exists a sequence
$(f_{1},...,f_{d})$ of edge-labeling set-valued functions
$f_{t}:\Pi(\mathcal{Z})^{t}\rightarrow\mathcal{Y}$ such that for every path
$\mu=(\mu_{1},...,\mu_{d})\in\Pi(\mathcal{Z})^{d}$, there exists a hypothesis
$h_{\mu}\in\mathcal{H}$ such that for all $t\in[d]$,
$h_{\mu}(\mathcal{T}_{t}(\mu_{<t}))\in f_{t}(\mu_{\leq t})$ and
$\mu_{t}(f_{t}(\mu_{\leq t}))\leq 1-\gamma$. The Measure Shattering dimension
of $\mathcal{H}$ at scale $\gamma$, denoted
$\text{MSdim}_{\gamma}(\mathcal{H},\mathcal{Y})$, is the maximal depth of a
tree $\mathcal{T}$ that is $\gamma$-shattered by $\mathcal{H}$. If there
exists $\gamma$-shattered trees of arbitrarily large depth, we say
$\text{MSdim}_{\gamma}(\mathcal{H},\mathcal{Y})=\infty$.

Note that unlike the $(k+1)$-Littlestone dimension, the Measure shattering
dimension is a scale-sensitive dimension and has infinite-width. Raman et al.
(2023b) show that the MSdim also characterizes online learnability for a wide
range of practical problems, like online multilabel ranking, online multilabel
classification with $\varepsilon$-sensitive losses, and online interval
learning.

###  3.2 A New Combinatorial Dimension

In this work, we are interested in a combinatorial dimension that
characterizes the online learnability for an arbitrary tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$. Inspired by the
minimax value of the game, we define a dimension that provides an adversary
with a strategy against every possible move of the learner. Since the learner
plays measures in $\Pi(\mathcal{Z})$, this amounts to defining a tree where
each internal node has an outgoing edge for every measure in
$\Pi(\mathcal{Z})$ labeled by an element of $\mathcal{Y}$. For any prediction
$\mu\in\Pi(\mathcal{Z})$ of the learner, the label on the edge corresponding
to $\mu$ gives the element $y\in\mathcal{Y}$ that the adversary should play.
Definition 3.2 makes this precise.

Definition 7:  Sequential Minimax dimension Let $\mathcal{T}$ be a complete
$\mathcal{X}$-valued, $\Pi(\mathcal{Z})$-ary tree of depth $d$, and fix
$\gamma>0$. The tree $\mathcal{T}$ is $\gamma$-shattered by
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ with respect to
$\ell:\mathcal{Y}\times\mathcal{Z}\rightarrow\mathbb{R}_{\geq 0}$ if there
exists a sequence $(f_{1},...,f_{d})$ of edge-labeling functions
$f_{t}:\Pi(\mathcal{Z})^{t}\rightarrow\mathcal{Y}$ such that for every path
$\mu=(\mu_{1},...,\mu_{d})\in\Pi(\mathcal{Z})^{d}$, there exists a hypothesis
$h_{\mu}\in\mathcal{H}$ such that for all $t\in[d]$,
$\mathbb{E}_{z\sim\mu_{t}}\left[\ell(f_{t}(\mu_{\leq
t}),z)\right]\geq\ell(f_{t}(\mu_{\leq
t}),h_{\mu}(\mathcal{T}_{t}(\mu_{<t})))+\gamma.$ The sequential Minimax
dimension of $\mathcal{H}$ at scale $\gamma$, denoted
$\text{SMdim}_{\gamma}(\mathcal{H},\ell)$, is the maximal depth of a tree
$\mathcal{T}$ that is $\gamma$-shattered by $\mathcal{H}$. If there exists
$\gamma$-shattered trees of arbitrarily large depth, we say
$\text{SMdim}_{\gamma}(\mathcal{H},\ell)=\infty$. Analogously, we can define
$\text{SMdim}_{0}(\mathcal{H},\ell)$ by requiring strict inequality,
$\mathbb{E}_{z\sim\mu}\left[\ell(f_{t}(\mu_{\leq
t}),z)\right]>\ell(f_{t}(\mu_{\leq t}),h_{\mu}(\mathcal{T}_{t}(\mu_{<t})))$.

One can also view the SMdim as a generalization of the MSdim proposed in Raman
et al. (2023b). It is not too hard to see that the finiteness of SMdim at
every scale is an obvious necessary condition. Often in mathematics, the
obvious necessary condition also turns out to be sufficient. It is no
different here as, in Section 5, we show that the finiteness of SMdim at every
scale is also sufficient for online learnability. We note that the SMdim is a
function of both the hypothesis class $\mathcal{H}$ and the loss function
$\ell$. However, when it is clear from context, we drop the dependence of
$\ell$ and only write $\text{SMdim}_{\gamma}(\mathcal{H})$. As with most
scale-sensitive dimensions, SMdim has a monotonicity property, namely,
$\text{SMdim}_{\gamma_{1}}(\mathcal{H})\leq\text{SMdim}_{\gamma_{2}}(\mathcal{H})$
for any $\gamma_{2}\leq\gamma_{1}$. In Section 6, we show that the SMdim
reduces to all four dimensions defined above.

##  4 $\varepsilon_{t}$-Realizable Setting

Before we study online learnability with bounded losses in the agnostic
setting, we consider a slightly easier setting, which we term the
$\varepsilon_{t}$-realizable setting. In this setting, an adversary plays a
sequential game with the learner over $T$ rounds. In each round $t\in[T]$, the
adversary selects a thresholded labeled instance
$(x_{t},(y_{t},\varepsilon_{t}))\in\mathcal{X}\times(\mathcal{Y}\times[0,c])$
and reveals $x_{t}$ to the learner. The learner selects a measure
$\mu_{t}\in\Pi(\mathcal{Z})$ and makes a randomized prediction
$z_{t}\sim\mu_{t}$. Finally, the adversary reveals both the true label $y_{t}$
and the threshold $\varepsilon_{t}$ and the learner suffers the loss
$\ell(y_{t},z_{t})$. A sequence of thresholded labeled examples
$\\{(x_{t},(y_{t},\varepsilon_{t}))\\}_{t=1}^{T}$ is called
$\varepsilon_{t}$-realizable if there exists a hypothesis
$h^{*}\in\mathcal{H}$ such that $\ell(y_{t},h^{*}(x_{t}))\leq\varepsilon_{t}$
for all $t\in[T]$. Given any $\varepsilon_{t}$-realizable stream, the goal of
the learner is to output predictions such that the difference
$\mathbb{E}\left[\sum_{t=1}^{T}\ell(y_{t},z_{t})\right]-\sum_{t=1}^{T}\varepsilon_{t}$
is sublinear in $T$. We can think of the thresholds $\varepsilon_{t}$ as the
adversary additionally revealing the loss that the best fixed hypothesis in
hindsight suffers on the labeled instance $(x_{t},y_{t})$. This intuition is
critical to our construction of an agnostic learner in Section 5. Note that if
it is guaranteed ahead of time that $\varepsilon_{t}=0$ for all $t\in[T]$,
then this setting boils down to the standard realizable setting. Theorem 4
shows that the finiteness of $\text{SMdim}_{\gamma}(\mathcal{H})$ at every
scale $\gamma>0$ is sufficient for $\mathcal{H}$ to be online learnable in
$\varepsilon_{t}$-realizable setting.

Theorem 1:  $\varepsilon_{t}$-Realizable Learnability For any tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$, there exists a
randomized online learner whose expected cumulative loss on any
$\varepsilon_{t}$-realizable stream
$\\{(x_{t},(y_{t},\varepsilon_{t}))\\}_{t=1}^{T}$ is at most
$\sum_{t=1}^{T}\varepsilon_{t}+\inf_{\gamma>0}\,\Big{\\{}\gamma
T+c\cdot\text{SMdim}_{\gamma}(\mathcal{H})\Big{\\}}.$

The key idea to prove Theorem 4 is to modify the Randomized Standard Optimal
Algorithm from Raman et al. (2023b) to account for the additional information
$\varepsilon_{t}$ that the adversary reveals in each round. Algorithm 1 makes
this idea more precise.

Minimax Randomized Standard Optimal Algorithm  Input: $\mathcal{H}$, Target
accuracy $\gamma>0$ Initialize: $V_{0}=\mathcal{H}$ For $t=1,\ldots,T:$ 1.
Receive unlabeled example $x_{t}\in\mathcal{X}$. 2. For all
$(y,\varepsilon)\in\mathcal{Y}\times[0,c]$, define
$V_{t-1}(y,\varepsilon):=\\{h\in
V_{t-1}\,\mid\,\ell(y,h(x_{t}))\leq\varepsilon\\}$. 3. Let
$\mathcal{C}_{t}:=\\{(y,\varepsilon)\in\mathcal{Y}\times[0,c]:\exists h\in
V_{t-1}\text{ such that }\ell(y,h(x_{t}))\leq\varepsilon\\}.$ 4. If
$\text{SMdim}_{\gamma}(V_{t-1})=0$, let $\mu_{t}\in\Pi(\mathcal{Z})$ be such
that for all $(y,\varepsilon)\in\mathcal{C}_{t}$ we have
$\mathbb{E}_{z\sim\mu_{t}}\left[\ell(y,z)\right]<\varepsilon+\gamma$ 5. Else,
compute
$\mu_{t}=\operatorname*{arg\,min}_{\mu\in\Pi(\mathcal{Z})}\,\max_{\begin{subarray}{c}(y,\varepsilon)\in\mathcal{Y}\times[0,c]\\\
\mathbb{E}_{z\sim\mu}\left[\ell(y,z)\right]\geq\varepsilon+\gamma\end{subarray}}\,\text{SMdim}_{\gamma}(V_{t-1}(y,\varepsilon)).$
6. Predict $z_{t}\sim\mu_{t}.$ 7. Receive feedback $(y_{t},\varepsilon_{t})$.
8. Update $V_{t}=V_{t-1}(y_{t},\varepsilon_{t}).$ Figure 1: Minimax Randomized
Standard Optimal Algorithm (MRSOA)

We now prove that the expected cumulative loss of Algorithm 1 satisfies the
upperbound given in Theorem 4.

###### Proof.

We show that given any target accuracy $\gamma>0$, the expected cumulative
loss of Algorithm 1 is at most
$\sum_{t=1}^{T}\varepsilon_{t}+c\,d_{\gamma}+\gamma T$ on any
$\varepsilon_{t}$-realizable stream, where
$d_{\gamma}=\text{SMdim}_{\gamma}(\mathcal{H})$. In fact, we show that
Algorithm 1 achieves an even stronger guarantee, namely that on any
$\varepsilon_{t}$-realizable sequence
$\\{(x_{t},(y_{t},\varepsilon_{t}))\\}_{t=1}^{T}$, Algorithm 1 computes
distributions $\mu_{t}\in\Pi(\mathcal{Z})$ such that

$\sum_{t=1}^{T}\mathbbm{1}\\{\mathbb{E}_{z\sim\mu_{t}}\left[\ell(y_{t},z)\right]\geq\gamma+\varepsilon_{t}\\}\leq
d_{\gamma}.$ (1)

From here, it follows that
$\mathbbm{E}\left[\sum_{t=1}^{T}\ell(y_{t},z_{t})\right]\leq
c\,d_{\gamma}+\gamma T+\sum_{t=1}^{T}\varepsilon_{t}.$ To see this, observe
that

$\displaystyle\mathbbm{E}\left[\sum_{t=1}^{T}\ell(y_{t},z_{t})\right]$
$\displaystyle=\sum_{t=1}^{T}\mathbbm{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]$
$\displaystyle=\sum_{t=1}^{T}\mathbbm{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\mathbbm{1}\\{\mathbb{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\geq\gamma+\varepsilon_{t}\\}+\mathbbm{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\mathbbm{1}\\{\mathbb{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]<\gamma+\varepsilon_{t}\\}$
$\displaystyle\leq
c\sum_{t=1}^{T}\mathbbm{1}\\{\mathbb{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\geq\gamma+\varepsilon_{t}\\}+\gamma
T+\sum_{t=1}^{T}\varepsilon_{t}$ $\displaystyle\leq c\,d_{\gamma}+\gamma
T+\sum_{t=1}^{T}\varepsilon_{t}.$

We now show that the outputs of Algorithm 1 satisfy Equation (1). It suffices
to show that (1) on any round where
$\mathbb{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\geq\gamma+\varepsilon_{t}$
and $\text{SMdim}_{\gamma}(V_{t-1})>0$, we have
$\text{SMdim}_{\gamma}(V_{t})\leq\text{SMdim}_{\gamma}(V_{t-1})-1$, and (2) if
$\text{SMdim}_{\gamma}(V_{t-1})=0$ there always exists distribution
$\mu_{t}\in\Pi(\mathcal{Z})$ such that
$\mathbbm{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]<\gamma+\varepsilon_{t}.$

Let $t\in[T]$ be a round where
$\mathbb{E}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\geq\gamma+\varepsilon_{t}$
and $\text{SMdim}_{\gamma}(V_{t-1})>0$. For the sake contradiction, suppose
that $\text{SMdim}_{\gamma}(V_{t})=\text{SMdim}_{\gamma}(V_{t-1})=d$. Then, by
the min-max computation in line (4) of Algorithm 1, for every measure
$\mu\in\Pi(\mathcal{Z})$, there exists a pair
$(y_{\mu},\varepsilon_{\mu})\in\mathcal{Y}\times[0,1]$ such that
$\mathbb{E}_{z\sim\mu}\left[\ell(y_{\mu},z)\right]\geq\varepsilon_{\mu}+\gamma$
and $\text{SMdim}_{\gamma}(V_{t-1}(y_{\mu},\varepsilon_{\mu}))=d$. Now
construct a tree $\mathcal{T}$ with $x_{t}$ labeling the root node. For each
measure $\mu\in\Pi(\mathcal{Z})$, construct an outgoing edge from $x_{t}$
indexed by $\mu$ and labeled by $y_{\mu}$. Append the tree of depth $d$
associated with the version space $V_{t-1}(y_{\mu},\varepsilon_{\mu})$ to the
edge indexed by $\mu$. Note that the depth of $\mathcal{T}$ must be $d+1$.
Furthermore, observe that for every hypothesis $h\in
V_{t-1}(y_{\mu},\varepsilon_{\mu})$, we have that
$\mathbb{E}_{z\sim\mu}\left[\ell(y_{\mu},z)\right]\geq\ell(y_{\mu},h(x_{t}))+\gamma$,
matching the shattering condition in Definition 3.2. Therefore, by definition
of SMdim, we have that $\text{SMdim}_{\gamma}(V_{t-1})=d+1$, a contradiction.
Thus, it must be the case that
$\text{SMdim}_{\gamma}(V_{t})\leq\text{SMdim}_{\gamma}(V_{t-1})-1$.

Now, suppose $t\in[T]$ is a round such that
$\text{SMdim}_{\gamma}(V_{t-1})=0$. We show that there always exist a
distribution $\mu_{t}\in\Pi(\mathcal{Z})$ such that for all
$(y,\varepsilon)\in\mathcal{C}_{t}$ , we have
$\mathbb{E}_{z_{t}\sim\mu_{t}}\left[\ell(y,z_{t})\right]<\gamma+\varepsilon$.
Since we are in the $\varepsilon_{t}$-realizable setting, it must be the case
that $(y_{t},\varepsilon_{t})\in\mathcal{C}_{t}$. To see why such a $\mu_{t}$
must exist, suppose for the sake of contradiction that it does not exist.
Then, for all $\mu\in\Pi(\mathcal{Z})$, there exists a pair
$(y_{\mu},\varepsilon_{\mu})\in\mathcal{C}_{t}$ such that
$\mathbb{E}_{z\sim\mu}\left[\ell(y_{\mu},z)\right]\geq\gamma+\varepsilon_{\mu}$.
As before, consider a tree with root node labeled by $x_{t}$. For each measure
$\mu\in\Pi(\mathcal{Z})$, construct an outgoing edge from $x_{t}$ indexed by
$\mu$ and labeled by $y_{\mu}$. Since
$(y_{\mu},\varepsilon_{\mu})\in\mathcal{C}_{t}$, there exists a hypothesis
$h_{\mu}\in V_{t-1}$ such that
$\ell(y_{\mu},h_{\mu}(x_{t}))\leq\varepsilon_{\mu}$. Therefore, we have
$\mathbb{E}_{z\sim\mu}\left[\ell(y_{\mu},z)\right]\geq\ell(y_{\mu},h_{\mu}(x_{t}))+\gamma$
. By definition of SMdim, this implies that
$\text{SMdim}_{\gamma}(V_{t-1})\geq 1$, which contradicts the fact that
$\text{SMdim}_{\gamma}(V_{t-1})=0$. Thus, there must be a distribution
$\mu_{t}\in\Pi(\mathcal{Z})$ such that for for all
$(y,\varepsilon)\in\mathcal{C}_{t}$ , we have
$\mathbb{E}_{z\sim\mu_{t}}\left[\ell(y,z)\right]<\gamma+\varepsilon$. Since
this is precisely the distribution that Algorithm 1 plays in step (3) and
since
$\text{SMdim}_{\gamma}(V_{t^{\prime}})\leq\text{SMdim}_{\gamma}(V_{t-1})$ for
all $t^{\prime}\geq t$, the algorithm no longer suffers expected loss more
than $\gamma+\varepsilon_{t^{\prime}}$. This completes the proof. ∎

##  5 Agnostic Setting

In this section, we go beyond the $\varepsilon_{t}$-realizable setting and
consider the more general agnostic setting where the adversary does not reveal
$\varepsilon_{t}$ at the end of each round. Our main Theorem shows that the
finiteness of SMdim at every scale $\gamma>0$ is both a necessary and
sufficient condition for agnostic online learnability.

Theorem 2:  Agnostic Learnability Consider a tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$. Then, (i) There
exists a randomized online learner whose expected regret on any stream is at
most $\inf_{\gamma>0}\,\left\\{c\cdot\text{SMdim}_{\gamma}(\mathcal{H})+\gamma
T+1+2c\sqrt{\,\text{SMdim}_{\gamma}(\mathcal{H})\,T\ln(2cT)}\right\\},$ and
this upper bound is tight up to logarithmic factors in $T$. (ii) Suppose
$\sup_{\gamma>0}\text{SMdim}_{\gamma}(\mathcal{H})>0$. Then, for every
randomized online learner, there exists a stream such that the expected regret
of the learner is at least
$\sup_{\gamma>0}\,\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})$ and this lower
bound cannot be improved in general.

The condition $\sup_{\gamma>0}\text{SMdim}_{\gamma}(\mathcal{H})>0$ in (ii) is
necessary to get a non-negative lower bound. Raman et al. (2023b) provide an
example of a tuple $(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$
where $\sup_{\gamma>0}\text{SMdim}_{\gamma}(\mathcal{H})=0$ but there is an
algorithm whose regret has a negative upper bound.

A primary approach to proving online agnostic upperbounds involves defining a
set of experts that exactly covers the hypothesis class and then running
multiplicative weights using these experts. This technique originated in Ben-
David et al. (2009) for binary classification and was later generalized by
Daniely et al. (2011) to multiclass classification. Daniely et al. (2011)’s
generalization involves simulating all possible labels in $\mathcal{Y}$ to
update the experts, thus making their upper bound vacuous when $|\mathcal{Y}|$
is unbounded. Recently, Hanneke et al. (2023) removed $|\mathcal{Y}|$ from the
upperbound by (1) constructing an approximate cover of the hypothesis class
instead of an exact cover and (2) using the feedback in the stream to update
experts rather than simulating all possible labels. Our proof of the
upperbound in Theorem 5 combines the ideas of both Daniely et al. (2011) and
Hanneke et al. (2023). In particular, following Hanneke et al. (2023), we
construct an approximate cover of the hypothesis class but follow Daniely et
al. (2011) in simulating all possible loss values.

###### Proof.

(of (i) in Theorem 5) Let $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$ be the data
stream. Here, we only consider an oblivious adversary since a standard
reduction (Chapter 4 in Cesa-Bianchi and Lugosi (2006)) allows us to convert
oblivious regret bounds to adaptive regret bounds. Let
$h^{\star}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{t},h(x_{t}))$
be an optimal function in hind-sight. For a target accuracy $\gamma>0$, let
$d_{\gamma}=\text{SMdim}_{\gamma}(\mathcal{H})$. Given time horizon $T$, let
$L_{T}=\\{L\subset[T];|L|\leq d_{\gamma}\\}$ denote the set of all possible
subsets of $[T]$ with size at most $d_{\gamma}$. For $\alpha\in[0,1]$, let
$\\{0,\alpha,\ldots,\lceil\frac{c}{\alpha}\rceil\alpha\\}$ be an
$\alpha$-cover of the loss space $[0,c]$. For every $L\in L_{T}$, define
$\Phi_{L}=\\{0,\alpha,\ldots,\lceil\frac{c}{\alpha}\rceil\alpha\\}^{L}$ to be
the set of all functions from $L$ to the $\alpha$-cover of $[0,c]$. Given
$L\in L_{T}$ and $\phi_{L}\in\Phi_{L}$, define an expert $E_{L}^{\phi_{L}}$
such that

$E_{L}^{\phi_{L}}(x_{t}):=\text{MRSOA}_{\gamma}\Big{(}x_{t}\mid\\{i,\phi_{L}(i)\\}_{i\in
L\cap[t-1]}\Big{)},$

where $\text{MRSOA}_{\gamma}\Big{(}x_{t}\mid\\{i,\phi_{L}(i)\\}_{i\in
L\cap[t-1]}\Big{)}$ is the prediction of the Minimax Randomized Standard
Optimal Algorithm (MRSOA) running at scale $\gamma$ that has updated on
thresholded labeled examples $\\{(x_{i},(y_{i},\phi_{L}(i))\\}_{i\in
L\cap[t-1]}$.

Let $\mathcal{E}=\bigcup_{L\in
L_{T}}\bigcup_{\phi_{L}\in\Phi_{L}}\\{E^{\phi_{L}}_{L}\\}$ denote the set of
all Experts. Note that
$|\mathcal{E}|=\sum_{i=0}^{d_{\gamma}}\left(\frac{2c}{\alpha}\right)^{i}\binom{T}{i}\leq\left(\frac{2cT}{\alpha}\right)^{d_{\gamma}}$.
Finally, given our set of experts $\mathcal{E}$, we run the Multiplicative
Weights Algorithm (MWA), denoted hereinafter as $\mathcal{A}$, over the stream
$(x_{1},y_{1}),...,(x_{T},y_{T})$ with a learning rate
$\eta=\sqrt{2\ln(|\mathcal{E}|)/T}$. Let $B$ denote the random variable
denoting the randomized prediction of all MRSOA’s. Then, conditioned on $B$,
Theorem 21.11 of Shalev-Shwartz and Ben-David (2014) tells us that

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\ell(y_{t},\mathcal{A}(x_{t}))\mid
B\right]$
$\displaystyle\leq\inf_{E\in\mathcal{E}}\sum_{t=1}^{T}\ell(y_{t},E(x_{t}))+c\,\sqrt{2T\ln(|\mathcal{E}|)}$
$\displaystyle\leq\inf_{E\in\mathcal{E}}\sum_{t=1}^{T}\ell(y_{t},E(x_{t}))+c\,\sqrt{2d_{\gamma}T\ln\left(\frac{2cT}{\alpha}\right)},$

where the second inequality follows because
$|\mathcal{E}|\leq\left(\frac{2cT}{\alpha}\right)^{d_{\gamma}}$. Taking
expectations on both sides, we obtain

$\mathbb{E}\left[\sum_{t=1}^{T}\ell(y_{t},\mathcal{A}(x_{t}))\right]\leq\operatorname*{\operatorname{\mathbb{E}}}\left[\inf_{E\in\mathcal{E}}\sum_{t=1}^{T}\ell(y_{t},E(x_{t}))\right]+c\,\sqrt{2d_{\gamma}T\ln\left(\frac{2cT}{\alpha}\right)}.$
(2)

Next, we show that the expected loss of the optimal expert is at most the loss
of $h^{\star}$ plus a sublinear quantity. Define
$\varepsilon_{t}:=\ell(y_{t},h^{\star}(x_{t}))$ to be the loss of the optimal
hypothesis in hindsight on each round $t$. We use $\varepsilon_{t}$ to define
a notion of mistake and use the mistake bound guarantee provided by Theorem 4.

Define
$\mu_{t}=\mu$$\text{-MRSOA}_{\gamma}\big{(}x_{t}\mid\\{i,\phi_{L}(i)\\}_{i\in
L\cap[t-1]}\big{)}$ to be the measure returned by $\text{MRSOA}_{\gamma}$, as
described in steps 4 and 5 of Algorithm 1, given that the algorithm has
updated on thresholded labeled examples
$\\{(x_{i},(y_{i},\phi_{L}(i)))\\}_{i\in L\cap[t-1]}$. We say that
$\mu\text{-MRSOA}_{\gamma}$ makes a mistake on round $t$ if
$\operatorname*{\operatorname{\mathbb{E}}}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\geq\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha+\gamma$.
Because
$\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha\geq\varepsilon_{t}$,
the entire stream
$(x_{1},(y_{1},\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha)),\ldots,(x_{T},(y_{T},\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha))$
is $\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha$-realizable.
Thus, with this notion of the mistake, Equation 1 tells us that
$\text{MRSOA}_{\gamma}$ makes at most $d_{\gamma}$ mistakes on the stream
$(x_{1},(y_{1},\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha)),\ldots,(x_{T},(y_{T},\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha))$.

Since $\mu\text{-MRSOA}_{\gamma}$ is a deterministic mapping from the past
examples to a probability measure in $\Pi(\mathcal{Z})$, we can procedurally
define and select a sequence of time points where $\mu\text{-MRSOA}_{\gamma}$,
had it run exactly on this sequence of time points, would make mistakes at
each time point. To that end, let

$t_{1}=\min\Big{\\{}\,t\in[T]:\operatorname*{\operatorname{\mathbb{E}}}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\geq\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha+\gamma\text{
where }\mu_{t}=\mu\text{-MRSOA}_{\gamma}\big{(}x_{t}|\,\\{\\}\big{)}\Big{\\}}$

be the earliest time point, where a fresh, unupdated copy of
$\mu\text{-MRSOA}_{\gamma}$ makes a mistake if it exists. Given $t_{1}$, we
recursively define $t_{i}$ for $i>1$ as

$t_{i}=\min\left\\{\,t>t_{i-1}:\operatorname*{\operatorname{\mathbb{E}}}_{z_{t}\sim\mu_{t}}\left[\ell(y_{t},z_{t})\right]\geq\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha+\gamma\text{
where
}\mu_{t}=\mu\text{-MRSOA}_{\gamma}\left(x_{t}\Big{|}\,\left\\{t_{j},\left\lceil\frac{\varepsilon_{t_{j}}}{\alpha}\right\rceil\alpha\right\\}_{j=1}^{i-1}\right)\right\\}$

if it exists. That is, $t_{i}$ is the earliest timepoint in $[T]$ after
$t_{i-1}$ where $\mu\text{-MRSOA}_{\gamma}$ having updated only on the
sequence
$\\{(x_{t_{j}},(y_{t_{j}},\left\lceil\frac{\varepsilon_{t_{j}}}{\alpha}\right\rceil\alpha))\\}_{j=1}^{i-1}$
makes a mistake. We stop this process when we reach an iteration where no such
time point in $[T]$ can be found where $\mu\text{-MRSOA}_{\gamma}$ makes a
mistake.

Using the definitions above, let $t_{1},...,t_{N}$ denote the sequence of
timepoints in $[T]$ selected via this recursive procedure. Define
$L^{\star}=\\{t_{1},...,t_{N}\\}$ and $\phi_{L^{\star}}$ be the function such
that
$\phi_{L^{\star}}(t)=\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha$
for each $t\in L^{\star}$. Let $E_{L^{\star}}^{\phi_{L^{\star}}}$ be the
expert parametrized by the pair $(L^{\star},\phi_{L^{\star}})$. The expert
$E_{L^{\star}}^{\phi_{L^{\star}}}$ exists because Equation (1) implies that
$N\leq d_{\gamma}$. By definition of the expert, we have
$E_{L^{\star}}^{\phi_{L^{\star}}}(x_{t})=\text{MRSOA}_{\gamma}\Big{(}x_{t}\mid\\{i,\phi_{L^{\star}}(i)\\}_{i\in
L^{\star}\cap[t-1]}\Big{)}$ for all $t\in[T]$. Let us define
$\mu_{t}^{\star}=\mu\text{-MRSOA}_{\gamma}\Big{(}x_{t}\mid\\{i,\phi_{L^{\star}}(i)\\}_{i\in
L^{\star}\cap[t-1]}\Big{)}$. Using the guarantee of Algorithm 1, we obtain

$\begin{split}\operatorname*{\operatorname{\mathbb{E}}}\left[\sum_{t=1}^{T}\ell\Big{(}y_{t},E_{L^{\star}}^{\phi_{L^{\star}}}(x_{t})\Big{)}\right]&\leq
c\,d_{\gamma}+\gamma
T+\sum_{t=1}^{T}\,\left\lceil\frac{\varepsilon_{t}}{\alpha}\right\rceil\alpha\\\
&\leq c\,d_{\gamma}+\gamma T+\sum_{t=1}^{T}\varepsilon_{t}+\alpha T\\\ &\leq
c\,d_{\gamma}+\gamma
T+\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{t},h(x_{t}))+\alpha
T,\end{split}$

where the last step above follows from the definition of $\varepsilon_{t}$’s.
Plugging the bound above to Equation (2), we obtain

$\begin{split}\mathbb{E}\left[\sum_{t=1}^{T}\ell(y_{t},\mathcal{A}(x_{t}))\right]&\leq\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{t},h(x_{t}))+c\,d_{\gamma}+\gamma
T+\alpha T+c\,\sqrt{2d_{\gamma}T\ln\left(\frac{2cT}{\alpha}\right)}\\\
&\leq\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{t},h(x_{t}))+c\,d_{\gamma}+\gamma
T+1+2c\,\sqrt{d_{\gamma}T\ln(2cT)},\end{split}$

where the final step follows upon picking $\alpha=\frac{1}{T}$. Since
$\gamma>0$ is arbitrary, this completes our proof. ∎

We highlight that the upper bound
$\inf_{\gamma>0}\,\left\\{c\cdot\text{SMdim}_{\gamma}(\mathcal{H})+\gamma
T+1+2c\,\sqrt{\text{SMdim}_{\gamma}(\mathcal{H})T\ln(2cT)}\right\\}$ can be
tight up to logarithmic factors in $T$. To see this, consider the case where
$\mathcal{Y}=\mathcal{Z}=[-1,1]$, $\ell(y,z)=|y-z|$, and
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$ such that $\text{seq-
fat}_{\gamma}(\mathcal{H})=d_{\gamma}$. Then, by Proposition 6, we have that
$\text{SMdim}_{\gamma}(\mathcal{H})\leq\text{seq-
fat}_{\gamma^{\prime}}(\mathcal{H})$ for all $\gamma^{\prime}<\gamma$ and
therefore the upperbound on the expected regret given by (i) in Theorem 5 is
at most $2\,\text{seq-
fat}_{\gamma^{\prime}}(\mathcal{H})+2\gamma^{\prime}T+1+4\sqrt{\,\text{seq-
fat}_{\gamma^{\prime}}(\mathcal{H})\,T\ln(4T)}$ for any
$\gamma/2\leq\gamma^{\prime}<\gamma$. However, we have a known lower bound
$\frac{\gamma^{\prime}}{4\sqrt{2}}\sqrt{\text{seq-
fat}_{\gamma^{\prime}}(\mathcal{H})T}$ for scalar valued regression (Rakhlin
et al., 2015a) . Thus, the upper bound given by (i) in Theorem 5 is tight up
to $O(\ln(T))$. We now move on to prove the lower bound.

###### Proof.

(of (ii) in Theorem 5) We now prove the lower bound given by (ii) in Theorem
5. Fix $\gamma>0$ and $d_{\gamma}:=\text{SMdim}_{\gamma}(\mathcal{H})$. By
definition of SMdim, there exists a $\mathcal{X}$-valued,
$\Pi(\mathcal{Z})$-ary tree $\mathcal{T}$ of depth $d_{\gamma}$ shattered by
$\mathcal{H}$. Let $(f_{1},...,f_{d})$ be the sequence of edge-labeling
functions $f_{t}:\Pi(\mathcal{Z})^{t}\rightarrow\mathcal{Y}$ associated with
$\mathcal{T}$. Let $\mathcal{A}$ be any randomized learner for $\mathcal{H}$.
Our goal will be to use $\mathcal{T}$ and its edge-labeling functions
$(f_{1},...,f_{d})$ to construct a difficult stream for $\mathcal{A}$ such
that on every round, the expected loss of $\mathcal{A}$ is at least $\gamma$
more than the loss of the optimal hypothesis in hindsight. This stream is
obtained by traversing $\mathcal{T}$ adapting to the sequence of distributions
output by $\mathcal{A}$.

To that end, for every round $t\in[d_{\gamma}]$, let $\mu_{t}$ denote the
distribution that $\mathcal{A}$ computes before making its prediction
$z_{t}\sim\mu_{t}$. Consider the stream
$\\{\left(\mathcal{T}_{t}(\mu_{<t}),f_{t}(\mu_{\leq
t})\right)\\}_{t=1}^{d_{\gamma}}$, where
$\mu=(\mu_{1},\ldots,\mu_{d_{\gamma}})$ denotes the sequence of distributions
output by $\mathcal{A}$. This stream is obtained by starting at the root of
$\mathcal{T}$, passing $\mathcal{T}_{1}$ to $\mathcal{A}$, observing the
distribution $\mu_{1}$ computed by $\mathcal{A}$, passing the label
$f_{t}(\mu_{\leq 1})$ to $\mathcal{A}$, and then finally moving along the edge
indexed by $\mu_{1}$. This process then repeats $d_{\gamma}-1$ times until the
end of the tree $\mathcal{T}$ is reached. Note that we can observe and use the
distribution computed by $\mathcal{A}$ on round $t$ to generate the label
because $\mathcal{A}$ deterministically maps a sequence of labeled instances
to a distribution.

Recall that the shattering condition implies that there exists a
$h_{\mu}\in\mathcal{H}$ such that
$\operatorname*{\operatorname{\mathbb{E}}}_{z_{t}\sim\mu_{t}}[\ell(f_{t}(\mu_{\leq
t}),z_{t})]\geq\ell(f_{t}(\mu_{\leq
t}),h_{\mu}(\mathcal{T}_{t}(\mu_{<t}))+\gamma$ for all $t\in[d_{\gamma}]$.
Therefore, the regret of $\mathcal{A}$ on the stream described above is at
least

$\begin{split}R_{\mathcal{A}}(T)\geq\sum_{t=1}^{d_{\gamma}}\operatorname*{\operatorname{\mathbb{E}}}_{z_{t}\sim\mu_{t}}[\ell(f_{t}(\mu_{\leq
t}),z_{t})]-\sum_{t=1}^{d_{\gamma}}\ell(f_{t}(\mu_{\leq
t}),h_{\mu}(\mathcal{T}_{t}(\mu_{<t}))\geq\sum_{t=1}^{d_{\gamma}}\gamma=\gamma
d_{\gamma}.\end{split}$

Since our choice of $\gamma$ and the randomized algorithm $\mathcal{A}$ is
arbitrary, this holds true for any $\gamma>0$ and randomized online learner.
This completes the proof of part (ii). ∎

In full generality, the lower bound of
$\sup_{\gamma>0}\,\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})$ cannot be
improved. In Section 5 of their work, Raman et al. (2023b) provide a tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$ demonstrating the
tightness of this lower bound in the context of set-valued feedback. Another
example demonstrating the tightness of the lower bound up to $O(\ln(T))$ is
provided in Section 7.1 following the proof of Corollary 7.2.

###  5.1 When is a lower bound of $\Omega(\sqrt{T})$ possible?

In many natural problems, one typically gets an agnostic lower bound that
scales with $\Omega(\sqrt{T})$. This includes problem settings such as
classification with $0$-$1$ loss, scalar-valued regression with absolute loss,
and multilabel ranking with $0$-$1$ ranking loss (Ben-David et al., 2009;
Daniely et al., 2011; Rakhlin et al., 2015a; Raman et al., 2023b). All of the
aforementioned settings exploit the problem structure such as the symmetry
between the prediction and the label space or loss-specific properties such as
being a distance metric. The following Lemma generalizes these properties and
derives a sufficient condition to obtain the lower bound of
$\Omega(\sqrt{T})$.

Lemma 1:  Sufficient condition for $\Omega(\sqrt{T})$ regret Consider a tuple
$(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$. Suppose there exists
two distinct hypotheses $h_{-1},h_{+1}\in\mathcal{H}$, an instance
$x\in\mathcal{X}$, and a pair of labels $y_{-1},y_{+1}\in\mathcal{Y}$ such
that (i) $\eta:=\min_{\sigma\in\\{\pm
1\\}}\Big{(}\ell(y_{-\sigma},h_{\sigma}(x))-\ell(y_{\sigma},h_{\sigma}(x))\Big{)}>0$
(ii)
$\inf_{z\in\mathcal{Z}}\Big{(}\ell(y_{-1},z)+\ell(y_{+1},z)\Big{)}\geq\frac{1}{2}\sum_{\sigma_{1},\sigma_{2}}\ell(y_{\sigma_{1}},h_{\sigma_{2}}(x))$
Then, for every randomized online learner, there exists a stream such that the
expected regret of the learner is at least $\eta\,\sqrt{\frac{T}{8}}$.

In the case when $\mathcal{Y}=\mathcal{Z}$ and the loss $\ell$ is a distance
metric, the conditions above reduce to requiring two distinct hypotheses
$h_{-1},h_{+1}\in\mathcal{H}$.

###### Proof.

(of Lemma 5.1) Let $(\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{H},\ell)$ be
such that there exists $h_{-1},h_{+1}\in\mathcal{H}$, $x\in\mathcal{X}$, and
$y_{-1},y_{+1}\in\mathcal{Y}$ that satisfies the aforementioned properties.
Let $\eta=\min_{\tau\in\\{\pm
1\\}}\Big{(}\ell(y_{-\tau},h_{\tau}(x))-\ell(y_{\tau},h_{\tau}(x))\Big{)}>0$.
For an odd $T\in\mathbb{N}$, consider the stream
$\\{x,y_{\sigma_{t}}\\}_{t=1}^{T}$ where $\sigma_{t}\sim\text{Unif}(\\{\pm
1\\})$. The expected loss of any randomized algorithm $\mathcal{A}$ on this
stream is

$\operatorname*{\operatorname{\mathbb{E}}}\left[\sum_{t=1}^{T}\ell(y_{\sigma_{t}},\mathcal{A}(x))\right]=\operatorname*{\operatorname{\mathbb{E}}}\left[\sum_{t=1}^{T}\frac{1}{2}\Big{(}\ell(y_{-1},\mathcal{A}(x))+\ell(y_{+1},\mathcal{A}(x))\Big{)}\right]\geq\frac{T}{4}\sum_{\tau_{1},\tau_{2}}\ell(y_{\tau_{1}},h_{\tau_{2}}(x)),$

where the first equality follows because $\sigma_{t}$’s are sampled uniformly
at random and the second inequality follows due to condition (ii) in Lemma
5.1. Let $\sigma=\text{sign}\left(\sum_{t=1}^{T}\sigma_{t}\right)$. Then,

$\begin{split}\operatorname*{\operatorname{\mathbb{E}}}\left[\min_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{\sigma_{t}},h(x))\right]&\leq\operatorname*{\operatorname{\mathbb{E}}}\left[\sum_{t=1}^{T}\ell(y_{\sigma_{t}},h_{\sigma}(x))\right]\\\
&=\operatorname*{\operatorname{\mathbb{E}}}\left[\sum_{t=1}^{T}\Big{(}\ell(y_{\sigma_{t}},h_{\sigma}(x))\mathbbm{1}\\{\sigma=\sigma_{t}\\}+\ell(y_{\sigma_{t}},h_{\sigma}(x))\mathbbm{1}\\{\sigma=-\sigma_{t}\\}\Big{)}\right]\\\
&=\sum_{t=1}^{T}\operatorname*{\operatorname{\mathbb{E}}}\left[\ell(y_{\sigma},h_{\sigma}(x))\,\left(\frac{1+\sigma\sigma_{t}}{2}\right)+\ell(y_{-\sigma},h_{\sigma}(x))\,\left(\frac{1-\sigma\sigma_{t}}{2}\right)\right]\\\
&=\frac{T}{2}\Big{(}\operatorname*{\operatorname{\mathbb{E}}}\left[\ell(y_{\sigma},h_{\sigma}(x))\right]+\operatorname*{\operatorname{\mathbb{E}}}\left[\ell(y_{-\sigma},h_{\sigma}(x))\right]\Big{)}\,-\frac{1}{2}\operatorname*{\operatorname{\mathbb{E}}}\left[\Big{(}\ell(y_{-\sigma},h_{\sigma}(x))-\ell(y_{\sigma},h_{\sigma}(x))\Big{)}\sum_{t=1}^{T}\sigma\,\sigma_{t}\right]\\\
&=\frac{T}{4}\sum_{\tau_{1},\tau_{2}}\ell(y_{\tau_{1}},h_{\tau_{2}}(x))\,-\frac{1}{2}\operatorname*{\operatorname{\mathbb{E}}}\left[\Big{(}\ell(y_{-\sigma},h_{\sigma}(x))-\ell(y_{\sigma},h_{\sigma}(x))\Big{)}\left|\sum_{t=1}^{T}\sigma_{t}\right|\right]\\\
&\leq\frac{T}{4}\sum_{\tau_{1},\tau_{2}}\ell(y_{\tau_{1}},h_{\tau_{2}}(x))-\frac{\eta}{2}\operatorname*{\operatorname{\mathbb{E}}}\left[\left|\sum_{t=1}^{T}\sigma_{t}\right|\right],\end{split}$

where the final equality follows upon using the fact that
$\sigma\sim\text{Unif}(\\{-1,1\\})$ and the final inequality follows from
condition (i). Thus, the expected regret of $\mathcal{A}$ is

$\begin{split}\operatorname*{\operatorname{\mathbb{E}}}\left[\sum_{t=1}^{T}\ell(y_{\sigma_{t}},\mathcal{A}(x))\right]-\operatorname*{\operatorname{\mathbb{E}}}\left[\min_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(y_{\sigma_{t}},h_{\sigma}(x))\right]&\geq\frac{\eta}{2}\operatorname*{\operatorname{\mathbb{E}}}\left[\left|\sum_{t=1}^{T}\sigma_{t}\right|\right]\\\
&\geq\eta\sqrt{\frac{T}{8}},\end{split}$

where the final step follows upon using Khinchine’s inequality (Cesa-Bianchi
and Lugosi, 2006, Page 364). This completes our proof. ∎

##  6 Relations Between Combinatorial Dimensions

In this section, we show that SMdim reduces to existing combinatorial
dimensions. We start with Proposition 6, which shows that SMdim $\equiv$ Ldim.

Proposition 1:  SMdim $\equiv$ Ldim Let $\mathcal{Y}=\mathcal{Z}$,
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$, and
$\ell(y,z)=\mathbbm{1}\\{y\neq z\\}$ be the 0-1 loss function. Then,
$\text{SMdim}_{\gamma}(\mathcal{H})=\text{Ldim}(\mathcal{H})$ for all
$\gamma\in[0,\frac{1}{2}]$.

###### Proof.

Fix $\gamma\in(0,\frac{1}{2}]$. We first show that
$\text{SMdim}_{\gamma}(\mathcal{H})\leq\text{Ldim}(\mathcal{H})$. Let
$\mathcal{T}$ be a $\mathcal{X}$-valued, $\Pi(\mathcal{Z})$-ary tree of depth
$d_{\gamma}=\text{SMdim}_{\gamma}(\mathcal{H})$ shattered by $\mathcal{H}$.
Let $v$ be the root node of $\mathcal{T}$ and $x$ denote the instance labeling
the node. Recall that $v$ has an outgoing edge for each measure
$\mu\in\Pi(\mathcal{Z})$. Let $\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$ be the
set of elements in $\mathcal{Y}$ that label the outgoing edges from $v$. We
first claim that there at least two distinct elements in the set
$\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$. For the sake of contradiction,
suppose this was not the case. That is, there is only one distinct element
that labels the outgoing edges from $v$. Let $y$ denote the element that
labels the outgoing edges from $v$. That is, $y_{\mu}=y$ for all
$\mu\in\Pi(\mathcal{Z})$. Consider the Dirac measure $\delta_{y}$ that puts
all mass on $y$. Note that $\delta_{y}\in\Pi(\mathcal{Z})$ and therefore there
exists an outgoing edge from $v$ indexed by $\delta_{y}$ and labeled by $y$.
However, it must be the case that $\mathbb{P}_{z\sim\delta_{y}}\left[y\neq
z\right]=0$. Since $\gamma>0$, the shattering condition required by Definition
3.2 cannot be met, which is a contradiction. Accordingly, there is at least
two distinct elements in the set $\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$.

Let $y_{-1},y_{+1}$ be the distinct elements of the set
$\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$, and $\mu_{-1},\mu_{+1}$ be the
indices of the edges labeled by $y_{1}$ and $y_{2}$ respectively. Let
$\mathcal{H}_{-1}=\\{h_{\mu}:\mu\in\Pi(\mathcal{Z})^{d},\mu_{1}=\mu_{-1}\\}$
denote the set of shattering hypothesis that corresponds to following a path
down $\mathcal{T}$ that takes the outgoing edge indexed $\mu_{-1}$ from the
root node. Likewise define $\mathcal{H}_{+1}$. Keep the edges indexed by
$\mu_{-1}$ and $\mu_{+1}$ and remove all other outgoing edges along with their
corresponding subtree. Reindex the two edges using $\\{\pm 1\\}$. The root
node $v$ should now have two outgoing edges, indexed by $\\{\pm 1\\}$ and
labeled by a distinct element of $\mathcal{Y}$, matching the first constraint
of a Ldim tree. As for the second constraint, observe that for all
$h_{-1}\in\mathcal{H}_{-1}$ and $h_{+1}\in\mathcal{H}_{+1}$ the shattering
condition from Definition 3.2 implies that
$\mathbb{P}_{z\sim\mu_{-1}}\left[y_{-1}\neq
z\right]\geq\mathbbm{1}\\{y_{-1}\neq h_{-1}(x)\\}+\gamma$ and
$\mathbb{P}_{z\sim\mu_{+1}}\left[y_{+1}\neq
z\right]\geq\mathbbm{1}\\{y_{+1}\neq h_{+1}(x)\\}+\gamma.$ However, this can
only be true if both $\mathbbm{1}\\{y_{-1}\neq h_{-1}(x)\\}=0\implies
y_{-1}=h_{-1}(x)$ and $\mathbbm{1}\\{y_{+1}\neq h_{+1}(x)\\}=0\implies
y_{+1}=h_{+1}(x)$. Accordingly, the hypotheses that shatters the edges indexed
by $\mu_{-1}$ and $\mu_{+1}$ in the original tree according to Definition 3.2
also shatters the newly re-indexed edges according to Definition 3.1.
Recursively repeating the above procedure on the subtrees following the two
reindexed edges results in a Ldim tree shattered by $\mathcal{H}$ of depth
$d$. Thus, $\text{SMdim}_{\gamma}(\mathcal{H})\leq\text{Ldim}(\mathcal{H})$
for $\gamma\in(0,\frac{1}{2}]$. The case when $\gamma=0$ follows similarly and
uses the fact that when $\gamma=0$, we define the shattering condition in
SMdim with a strict inequality (see last sentence in Definition 3.2).

We now prove the inequality that
$\text{SMdim}_{\gamma}(\mathcal{H})\geq\text{Ldim}(\mathcal{H})$. Fix
$\gamma\in[0,\frac{1}{2}]$. Let $\mathcal{T}$ be a $\mathcal{X}$-valued,
$\\{\pm 1\\}$-ary tree of depth $d=\text{Ldim}(\mathcal{H})$ shattered by
$\mathcal{H}$ according to Definition 3.1. Our goal will be to expand
$\mathcal{T}$ into a $\Pi(\mathcal{Z})$-ary tree that is $\gamma$-shattered by
$\mathcal{H}$ according to Definition 3.2. Let $v$ be the root node of
$\mathcal{T}$, $x$ be the instance that labels the root node, and
$y_{-1},y_{+1}$ denote the distinct elements of $\mathcal{Y}$ that label the
left and right outgoing edges from $v$ respectively. Let
$\mathcal{H}_{-1}=\\{h_{\sigma}:\sigma\in\\{\pm
1\\}^{d},\sigma_{1}=-1\\}\subset\mathcal{H}$ denote the set of shattering
hypothesis that correspond to following a path down $\mathcal{T}$ that takes
the edge indexed by $-1$ in the first level. Define $\mathcal{H}_{+1}$
analogously. Then, for all $h_{-1}\in\mathcal{H}_{-1}$ and
$h_{+1}\in\mathcal{H}_{+1}$, the shattering condition implies that
$h_{-1}(x)=y_{-1}$ and $h_{+1}(x)=y_{+1}$.

For every measure $\mu\in\Pi(\mathcal{Z})$, we claim that there exists a
$\sigma_{\mu}\in\\{\pm 1\\}$ such that
$\mathbb{P}_{z\sim\mu}\left[y_{\sigma_{\mu}}\neq
z\right]=\mu(\\{y_{\sigma_{\mu}}\\}^{c})\geq\gamma$. Suppose for the sake of
contradiction that this is not true. Then, there exists a measure
$\mu\in\Pi(\mathcal{Z})$ such that for both $\sigma\in\\{\pm 1\\}$, we have
$\mu(\\{y_{\sigma}\\}^{c})<\gamma$. Then,
$1=\mu(\mathcal{Z})=\mu(\\{y_{-1}\\}^{c}\cup\\{y_{+1}\\}^{c})<2\gamma<1$, a
contradiction. Thus, for every measure $\mu\in\Pi(\mathcal{Z})$ there exists a
$\sigma_{\mu}\in\\{\pm 1\\}$ such that
$\mathbb{P}_{z\sim\mu}\left[y_{\sigma_{\mu}}\neq z\right]\geq\gamma$.
Combining this with the fact that for any $h_{-1}\in\mathcal{H}_{-1}$ and
$h_{+1}\in\mathcal{H}_{+1}$, we have $y_{-1}=h_{-1}(x)$ and
$y_{+1}=h_{+1}(x)$, gives that, for every measure $\mu\in\Pi(\mathcal{Z})$,
there exists a $\sigma_{\mu}\in\\{\pm 1\\}$ such that for all
$h_{\sigma_{\mu}}\in\mathcal{H}_{\sigma_{\mu}}$ ,we have
$\mathbb{P}_{z\sim\mu}\left[y_{\sigma_{\mu}}\neq
z\right]\geq\mathbbm{1}\\{y_{\sigma_{\mu}}\neq h_{\sigma_{\mu}}(x)\\}+\gamma$.
Note that if we take $y_{\sigma_{\mu}}$ to be the label on an edge indexed by
$\mu$, then the inequality above matches the shattering condition required by
Definition 3.2.

To that end, for every measure $\mu\in\Pi(\mathcal{Z})$, add an outgoing edge
from $v$ indexed by $\mu$ and labeled by the $y_{\sigma_{\mu}}$, where
$\sigma_{\mu}$ is the index as promised by the analysis above. Grab the sub-
tree in $\mathcal{T}$ following the original outgoing edge from $v$ indexed by
$\sigma_{\mu}$, and append it to the newly constructed outgoing edge from $v$
indexed by $\mu$. Remove the original outgoing edges from $v$ indexed by
$\\{\pm 1\\}$ and their corresponding subtrees. Recursively repeat the above
procedure on the subtrees following the newly created edges indexed by
measures. Upon repeated this process for every internal node in $\mathcal{T}$,
we obtain a $\Pi(\mathcal{Z})$-ary tree that is $\gamma$-shattered by
$\mathcal{H}$ of depth $d$. Thus, we have that
$\text{Ldim}(\mathcal{H})\leq\text{SMdim}_{\gamma}(\mathcal{H})$ for
$\gamma\in[0,\frac{1}{2}]$. ∎

Next, we show an equivalence between SMdim and seq-fat.

Proposition 2:  SMdim $\equiv$ seq-fat Let $\mathcal{Y}=\mathcal{Z}=[-1,1]$,
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$, and $\ell(y,z)=|y-z|$ be the
absolute value loss function. Then for every $\gamma\in(0,1]$, $\text{seq-
fat}_{\gamma}(\mathcal{H})\leq\text{SMdim}_{\gamma}(\mathcal{H})\leq\text{seq-
fat}_{\gamma^{\prime}}(\mathcal{H})$ where $\gamma^{\prime}<\gamma.$

###### Proof.

We first prove the upper bound. Let $\gamma\in(0,1]$ and
$\gamma^{\prime}<\gamma$. Let $\mathcal{T}$ be a $\mathcal{X}$-valued,
$\Pi(\mathcal{Z})$-ary tree of depth
$d_{\gamma}=\text{SMdim}_{\gamma}(\mathcal{H})$ shattered by $\mathcal{H}$.
Let $v$ be the root node of $\mathcal{T}$ and $x$ denote the instance labeling
the node. Recall that $v$ has an outgoing edge for each measure
$\mu\in\Pi(\mathcal{Z})$. In particular, this means that $v$ has outgoing
edges corresponding to the Dirac measures on $\mathcal{Z}$, which we denote by
$\\{\delta_{z}\\}_{z\in\mathcal{Z}}$. Fix a $z\in\mathcal{Z}$ and consider the
outgoing edge from $v$ indexed by $\delta_{z}$. Let $y_{z}\in\mathcal{Y}$ be
the element that labels the outgoing edge indexed by $\delta_{z}$. Let
$\mathcal{H}_{z}=\\{h_{\mu}:\mu\in\Pi(\mathcal{Z})^{d},\mu_{1}=\delta_{z}\\}\subset\mathcal{H}$
denote the set of shattering hypothesis that corresponds to following a path
down $\mathcal{T}$ that takes the edge $\delta_{z}$ in the root node. Then,
for all $h\in\mathcal{H}_{z}$ the shattering condition from Definition 3.2
implies that

$|z-y_{z}|\geq|h(x)-y_{z}|+\gamma>|h(x)-y_{z}|+\gamma^{\prime}.$

Taking the supremum on both sides, gives that:

$|z-y_{z}|>\sup_{h\in\mathcal{H}_{z}}|h(x)-y_{z}|+\gamma^{\prime}=r_{z}+\gamma^{\prime}.$
(3)

where we let $r_{z}=\sup_{h\in\mathcal{H}_{z}}|h(x)-y_{z}|$. Let
$I_{z}:=\left[y_{z}-(r_{z}+\gamma^{\prime}),y_{z}+(r_{z}+\gamma^{\prime})\right]\subset[-3,3]$
denote an interval corresponding to $z$. The inequality above implies that
$z\notin I_{z}$ (note that $I_{z}$ changes depending on $z$). Since
$z\in\mathcal{Z}$ was arbitrary, it must be the case that $z\notin I_{z}$ for
all $z\in\mathcal{Z}$. This means that
$\bigcap_{z\in\mathcal{Z}}I_{z}=\emptyset$. Since $[-3,3]$ is compact and
$\\{I_{z}\\}_{z\in\mathcal{Z}}$ is a family of intervals whose intersection is
empty, the celebrated Helly’s theorem states that there exists two intervals
in $\\{I_{z}\\}_{z\in\mathcal{Z}}$ that are disjoint (Eckhoff, 1993; Radon,
1921). Accordingly, let $z_{1},z_{2}$ be such that $I_{z_{1}}\cap
I_{z_{2}}=\emptyset$. As before, let $y_{z_{1}}$ and $y_{z_{2}}$ be the labels
on the outgoing edges from $v$ indexed by the Dirac measures $\delta_{z_{1}}$
and $\delta_{z_{2}}$ respectively. Without loss of generality, let
$y_{z_{1}}<y_{z_{2}}$ (we have strict inequality because we are guaranteed
that $I_{z_{1}}$ and $I_{z_{2}}$ are disjoint). By inequality 3, for all
$h_{z_{1}}\in\mathcal{H}_{z_{1}}$ and $h_{z_{2}}\in\mathcal{H}_{z_{2}}$ we
have that

$h_{z_{1}}(x)\in\left[y_{z_{1}}-r_{z_{1}},y_{z_{1}}+r_{z_{1}}\right]\quad\text{and}\quad
h_{z_{2}}(x)\in\left[y_{z_{2}}-r_{z_{2}},y_{z_{2}}+r_{z_{2}}\right].$

Let $s=\frac{y_{z_{1}}+r_{z_{1}}+y_{z_{2}}-r_{z_{2}}}{2}\in[-1,1]$ be a
witness. Then, for all $h_{z_{1}}\in\mathcal{H}_{z_{1}}$ and
$h_{z_{2}}\in\mathcal{H}_{z_{2}}$, we have that
$s-h_{z_{1}}(x)\geq\gamma^{\prime}$ and $h_{z_{2}}(x)-s\geq\gamma^{\prime}$.
Relabel the two edges indexed by $\delta_{z_{1}}$ and $\delta_{z_{2}}$ with
the same witness $s$. Reindex the two edges indexed by $\delta_{z_{1}}$ and
$\delta_{z_{2}}$ with $-1$ and $+1$ respectively. Remove all other edges
indexed by measures and their corresponding subtrees. There should now only be
two outgoing edges from $v$, each labeled by the same witness. Next, recall
that for all $h_{z_{1}}\in\mathcal{H}_{z_{1}}$ and
$h_{z_{2}}\in\mathcal{H}_{z_{2}}$ we have that
$s-h_{z_{1}}\geq\gamma^{\prime}$ and $h_{z_{2}}-s\geq\gamma^{\prime}$.
Accordingly, the hypotheses that shatter the edges indexed by $\delta_{z_{1}}$
and $\delta_{z_{2}}$ in the original tree according to Definition 3.2 also
shatter the newly re-indexed and relabeled edges according to Definition 3.1.
Recursively repeating the above procedure on the subtrees following the two
newly reindexed and relabeled edges results in a seq-fat tree
$\gamma^{\prime}$-shattered by $\mathcal{H}$ of depth $d_{\gamma}$. Thus,
$\text{SMdim}_{\gamma}(\mathcal{H})\leq\text{seq-
fat}_{\gamma^{\prime}}(\mathcal{H})$ for $\gamma^{\prime}<\gamma$.

We now move on to prove the lower bound. Let $\gamma\in(0,1]$ and
$\mathcal{T}$ be a $\mathcal{X}$-valued, $\\{\pm 1\\}$-ary tree of depth
$d_{\gamma}=\text{seq-fat}_{\gamma}(\mathcal{H})$ shattered by $\mathcal{H}$
according to Definition 3.1. Our goal will be expand $\mathcal{T}$ into a
$\Pi(\mathcal{Z})$-ary tree that is $\gamma$-shattered by $\mathcal{H}$
according to Definition 3.2. Let $v$ be the root node, $x$ the instance that
labels the root node, and $s$ be the witness that labels the two outgoing
edges of $v$. Let $\mathcal{H}_{-1}=\\{h_{\sigma}:\sigma\in\\{\pm
1\\}^{d_{\gamma}},\sigma_{1}=-1\\}\subset\mathcal{H}$ denote the set of
shattering hypothesis that corresponds to following a path down $\mathcal{T}$
that takes the outgoing edge indexed by $-1$ from the root node. Likewise
define $\mathcal{H}_{+1}$. Then, for all $h_{-1}\in\mathcal{H}_{-1}$ and
$h_{+1}\in\mathcal{H}_{+1}$, the shattering condition implies that
$s-h_{-1}(x)\geq\gamma$ and $h_{+1}(x)-s\geq\gamma$ respectively.

For every measure $\mu\in\Pi(\mathcal{Z})$, we claim that there exist a
$\sigma_{\mu}\in\\{-1,1\\}$ such that
$\mathbb{E}_{z\sim\mu}\left[|\sigma_{\mu}-z|\right]\geq|s-\sigma_{\mu}|$.
Suppose for the sake of contradiction that this is not true. That is, there
exists $\mu\in\Pi(\mathcal{Z})$ such that for all $\tau\in\\{-1,1\\}$ we have
that $\mathbb{E}_{z\sim\mu}\left[|\tau-z|\right]<|s-\tau|$. Then, when
$\tau=-1$, we have that $\mathbb{E}_{z\sim\mu}\left[z\right]<|s+1|-1$ and when
$\tau=1$, we have $1-|s-1|<\mathbb{E}_{z\sim\mu}\left[z\right]$, using the
fact that $|\tau-z|=1-\tau z$. Combining the two inequalities together and
using the fact that $s\in[-1,1]$ gives that $2<|s+1|+|s-1|=2$, which is a
contradiction. Accordingly, for every measure $\mu\in\Pi(\mathcal{Z})$, there
exists a $\sigma_{\mu}\in\\{-1,1\\}$ such that
$\mathbb{E}_{z\sim\mu}\left[|\sigma_{\mu}-z|\right]\geq|s-\sigma_{\mu}|$.
Next, crucially note that for any $\tau\in\\{\pm 1\\}$ and any
$h_{\tau}\in\mathcal{H}_{\tau}$, we have
$|h_{\tau}(x)-\tau|=|s-\tau|-|h_{\tau}(x)-s|\leq|s-\tau|-\gamma$ by the seq-
fat shattering condition from Definition 3.1. Therefore, for every measure
$\mu\in\Pi(\mathcal{Z})$, there exists $\sigma_{\mu}\in\\{\pm 1\\}$ such that
for all $h_{\sigma_{\mu}}\in\mathcal{H}_{\sigma_{\mu}}$, we have that
$\mathbb{E}_{z\sim\mu}\left[|\sigma_{\mu}-z|\right]\geq|\sigma_{\mu}-h_{\sigma_{\mu}}(x)|+\gamma$.
Note that if we take $\sigma_{\mu}$ to be the label on a edge indexed by
$\mu$, then
$\mathbb{E}_{z\sim\mu}\left[|\sigma_{\mu}-z|\right]\geq|\sigma_{\mu}-h_{\sigma_{\mu}}(x)|+\gamma$
exactly matches the shattering condition required by Definition 3.2.

To that end, for every measure $\mu\in\Pi(\mathcal{Z})$, add an outgoing edge
from $v$ indexed by $\mu$ and labeled by the $\sigma_{\mu}\in\\{\pm 1\\}$
promised in the analysis above. Grab the sub-tree in $\mathcal{T}$ following
the original outgoing edge from $v$ indexed by $\sigma_{\mu}$, and append it
to the newly constructed outgoing edge from $v$ indexed by $\mu$. Remove the
original outgoing edges from $v$ indexed by $-1$ and $+1$ and their
corresponding subtrees. Recursively repeat the above procedure on the subtrees
following the newly created edges indexed by measures. Upon repeating this
process for every internal node in $\mathcal{T}$, we obtain a
$\Pi(\mathcal{Z})$-ary tree that is $\gamma$-shattered by $\mathcal{H}$ of
depth $d_{\gamma}$. Thus, we have that $\text{seq-
fat}_{\gamma}(\mathcal{H})\leq\text{SMdim}_{\gamma}(\mathcal{H})$. ∎

Next, we show that SMdim reduces to $(k+1)$-Ldim from Moran et al. (2023).

Proposition 3:  SMdim $\equiv$ $\text{Ldim}_{k+1}$ Let
$\mathcal{Z}=\\{S:S\subset\mathcal{Y},|S|\leq k\\}$,
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$, and
$\ell(y,z)=\mathbbm{1}\\{y\notin z\\}$. Then for every
$\gamma\in[0,\frac{1}{k+1}]$, we have
$\text{SMdim}_{\gamma}(\mathcal{H})=\text{Ldim}_{k+1}(\mathcal{H}).$

###### Proof.

Fix $\gamma\in(0,1]$. We first show that
$\text{SMdim}_{\gamma}(\mathcal{H})\leq\text{Ldim}_{k+1}(\mathcal{H})$. Let
$\mathcal{T}$ be a $\mathcal{X}$-valued, $\Pi(\mathcal{Z})$-ary tree of depth
$d_{\gamma}=\text{SMdim}_{\gamma}(\mathcal{H})$ shattered by $\mathcal{H}$.
Let $v$ be the root node of $\mathcal{T}$ and $x$ denote the instance labeling
the node. Recall that $v$ has an outgoing edge for each measure
$\mu\in\Pi(\mathcal{Z})$. Let $\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$ be the
set of elements in $\mathcal{Y}$ that label the outgoing edges from $v$. We
first claim that there at least $k+1$ distinct elements in the set
$\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$. For the sake of contradiction,
suppose this was not the case. That is, there are only $k$ distinct elements
that label the outgoing edges from $v$. Let $y_{1},...,y_{k}$ denote the $k$
distinct elements that label the outgoing edges from $v$, Consider the measure
$\tilde{\mu}$ that puts all mass on $\\{y_{1},...,y_{k}\\}$. Note that
$\tilde{\mu}\in\Pi(\mathcal{Z})$ and let $\tilde{y}\in\\{y_{1},...,y_{k}\\}$
be the label on the outgoing edge from $v$ indexed by $\tilde{\mu}$. By
definition of $\tilde{\mu}$ and $\tilde{y}$, it must be the case that
$\mathbb{P}_{z\sim\mu}\left[\tilde{y}\notin z\right]=0$. Since $\gamma>0$, the
shattering condition required by Definition 3.2 cannot be met, which is a
contradiction. Accordingly, there at least $k+1$ distinct elements in the set
$\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$.

Let $y_{1},...,y_{k+1}$ be the distinct elements of the set
$\\{y_{\mu}\\}_{\mu\in\Pi(\mathcal{Z})}$, and $\mu_{1},...,\mu_{k+1}$ be the
indices of the edges labeled by $y_{1},...,y_{k+1}$ respectively. For
$\mu_{i}\in\\{\mu_{1},...,\mu_{k+1}$}, let $\mathcal{H}_{\mu_{i}}$ denote the
set of shattering hypothesis that corresponds to following a path down
$\mathcal{T}$ that takes the outgoing edge $\mu_{i}$ from the root node. Keep
the edges indexed by $\mu_{1},...,\mu_{k+1}$, and remove all other outgoing
edges along with their corresponding subtree. Reindex the $k+1$ edges using
distinct numbers in $[k+1]$. The root node $v$ should now have $k+1$ outgoing
edges, each indexed by a different natural number in $[k+1]$ and labeled by a
distinct element of $\mathcal{Y}$, matching the first constraint of a
$\text{Ldim}_{k+1}$ tree. As for the second constraint, observe that for all
$h\in\mathcal{H}_{\mu_{i}}$ the shattering condition implies that
$\mathbb{P}_{z\sim\mu_{i}}\left[y_{i}\notin
z\right]\geq\mathbbm{1}\\{y_{i}\notin h(x)\\}+\gamma.$ However, this can only
be true if $\mathbbm{1}\\{y_{i}\notin h(x)\\}=0\implies y_{i}\in h(x)$.
Accordingly, the hypotheses that shatter the edges indexed by
$\mu_{1},...,\mu_{k+1}$ in the original tree according to Definition 3.2 also
shatter the newly re-indexed edges according to Definition 3.1. Recursively
repeating the above procedure on the subtrees following the $k+1$ reindexed
edges results in a $\text{Ldim}_{k+1}$ tree shattered by $\mathcal{H}$ of
depth $d_{\gamma}$. Thus,
$\text{SMdim}_{\gamma}(\mathcal{H})\leq\text{Ldim}_{k+1}(\mathcal{H})$ for
$\gamma\in(0,1]$. The case when $\gamma=0$ follows similarly and uses the fact
that when $\gamma=0$, we define the shattering condition in SMdim with a
strict inequality (see last sentence in Definition 3.2).

We now prove the inequality that
$\text{SMdim}_{\gamma}(\mathcal{H})\geq\text{Ldim}_{k}(\mathcal{H})$. Fix
$\gamma\in[0,\frac{1}{k+1}]$. Let $\mathcal{T}$ be a $\mathcal{X}$-valued,
$[k+1]$-ary tree of depth $d=\text{Ldim}_{k+1}(\mathcal{H})$ shattered by
$\mathcal{H}$ according to Definition 3.1. Our goal will be to expand
$\mathcal{T}$ into a $\Pi(\mathcal{Z})$-ary tree that is $\gamma$-shattered by
$\mathcal{H}$ according to Definition 3.2. Let $v$ be the root node of
$\mathcal{T}$, $x$ be the instance that labels the root node, and
$\\{y_{i}\\}_{i=1}^{k+1}$ denote the distinct elements of $\mathcal{Y}$ that
label the $k+1$ outgoing edges from $v$. For each $i\in[k+1]$, let
$\mathcal{H}_{i}=\\{h_{p}:p\in[k+1]^{d},p_{1}=i\\}\subset\mathcal{H}$ denote
the set of shattering hypothesis that corresponds to following a path down
$\mathcal{T}$ that takes the outgoing edge indexed by $i$ from $v$. Then, for
all $i\in[k+1]$ and $h_{i}\in\mathcal{H}_{i}$, the shattering condition
implies that $y_{i}\in h_{i}(x)\implies\mathbbm{1}\\{y_{i}\notin
h_{i}(x)\\}=0$.

For every measure $\mu\in\Pi(\mathcal{Z})$, we claim that there exists a
$i_{\mu}\in[k+1]$ such that $\mathbb{P}_{z\sim\mu}\left[y_{i_{\mu}}\notin
z\right]\geq\gamma$. Suppose for the sake of contradiction that this is not
true. Then, there exists a measure $\mu\in\Pi(\mathcal{Z})$ such that for all
$i\in[k+1]$, we have $\mathbb{P}_{z\sim\mu}\left[y_{i}\notin z\right]<\gamma$.
This implies that $\mathbb{P}_{z\sim\mu}\left[\exists i\in[k+1]\text{ such
that }y_{i}\notin z\right]<(k+1)\gamma<1$. However, since $\mu$ is supported
only over subsets of $\mathcal{Y}$ of size at most $k$, we have
$\mathbb{P}_{z\sim\mu}\left[\exists i\in[k+1]\text{ such that }y_{i}\notin
z\right]=1$, a contradiction. Thus, for every measure $\mu\in\Pi(\mathcal{Z})$
there exists a $i_{\mu}\in[k+1]$ such that
$\mathbb{P}_{z\sim\mu}\left[y_{i_{\mu}}\notin z\right]\geq\gamma$. Combining
this with the fact that for every $i\in[k+1]$ and $h_{i}\in\mathcal{H}_{i}$ we
have that $y_{i}\in h_{i}(x)$ gives that, for every measure
$\mu\in\Pi(\mathcal{Z})$, there exists a $i_{\mu}\in[k+1]$ such that for all
$h_{i_{\mu}}\in\mathcal{H}_{i_{\mu}}$, we have
$\mathbb{P}_{z\sim\mu}\left[y_{i_{\mu}}\notin
z\right]\geq\mathbbm{1}\\{y_{i_{\mu}}\notin h_{i_{\mu}}(x)\\}+\gamma$. Note
that if we take $y_{i_{\mu}}$ to be the label on an edge indexed by $\mu$,
then the inequality above matches the shattering condition required by
Definition 3.2.

To that end, for every measure $\mu\in\Pi(\mathcal{Z})$, add an outgoing edge
from $v$ indexed by $\mu$ and labeled by the $y_{i_{\mu}}$, where $i_{\mu}$ is
the index as promised by the analysis above. Grab the sub-tree in
$\mathcal{T}$ following the original outgoing edge from $v$ indexed by
$i_{\mu}$, and append it to the newly constructed outgoing edge from $v$
indexed by $\mu$. Remove the original outgoing edges from $v$ indexed by
numbers in $[k+1]$ and their corresponding subtrees. Recursively repeat the
above procedure on the subtrees following the newly created edges indexed by
measures. Upon repeating this process for every internal node in
$\mathcal{T}$, we obtain a $\Pi(\mathcal{Z})$-ary tree of depth $d$ that is
$\gamma$-shattered by $\mathcal{H}$. Thus, we have that
$\text{Ldim}_{k+1}(\mathcal{H})\leq\text{SMdim}_{\gamma}(\mathcal{H})$ for
$\gamma\in[0,\frac{1}{k+1}]$. ∎

Finally, we show that the SMdim $\equiv$ MSdim.

Proposition 4:  SMdim $\equiv$ MSdim Let
$\mathcal{Y}\subset\sigma(\mathcal{Z})$,
$\mathcal{H}\subseteq\mathcal{Z}^{\mathcal{X}}$, and
$\ell(y,z)=\mathbbm{1}\\{z\notin y\\}$. Then for every $\gamma\in[0,1]$, we
have $\text{SMdim}_{\gamma}(\mathcal{H})=\text{MSdim}_{\gamma}(\mathcal{H}).$

###### Proof.

The equality follows directly from the fact that
$\mathbb{E}_{z\sim\mu}\left[\ell(y,z)\right]=\mu(y^{c})$ and the fact that
$\mathbb{E}_{z\sim\mu_{t}}\left[\ell(z,f_{t}(\mu_{\leq
t}))\right]\geq\ell(h_{\mu}(\mathcal{T}_{t}(\mu_{<t})),f_{t}(\mu_{\leq
t}))+\gamma\iff h_{\mu}(\mathcal{T}_{t}(\mu_{<t}))\in f_{t}(\mu_{\leq
t})\text{ and }\mu_{t}(f_{t}(\mu_{\leq t}))\leq 1-\gamma$. ∎

##  7 Applications

In this section, we discuss some applications of our general result presented
in Section 5. For instance, taking $\mathcal{Y}=\mathcal{Z}$ and
$\ell(y,z)=\mathbbm{1}\\{y\neq z\\}$ defines standard multiclass
classification. As pointed out in Proposition 6, the sequential Minimax
dimension reduces to the Littlestone dimension. Similarly, taking
$\mathcal{Y}=\mathcal{Z}=[-1,1]$ and $\ell(y,z)=|y-z|$, Proposition 6 shows
the equivalence between SMdim and sequential fat shattering dimension.
Quantitative characterizations of multiclass classification and scalar-valued
regression are well established in the literature. However, our results in
Section 5 can also be used to fully characterize the online learnability of
vector-valued regression and multilabel classification, which was not known
previously.

We point out that Raman et al. (2023a) consider the problem of multioutput
regression with $L_{p}$ norm losses and multilabel classification with
normalized Hamming loss. For multioutput regression, they consider the case
$\mathcal{Y}=[-1,1]^{K}$. Given any
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, they show that the finiteness
of the sequential fat-shattering dimension of each coordinate output
restriction $\mathcal{H}_{i}\subseteq[-1,1]^{\mathcal{X}}$ is necessary and
sufficient for learnability. This coordinate-wise characterization results in
both their upper and lower bounds on regret depending on $K$, thus preventing
their techniques from generalizing to infinite dimensional label spaces.
Accordingly, they left it open to characterize the learnability when
$\mathcal{Y}$ is infinite-dimensional. Moreover, they asked whether there
exists a combinatorial dimension of the multioutput function class that
provides a sharp quantitative characterization of learnability. We resolve
both open problems in this work and settle the question of learnability for
vector-valued regression. As for multilabel classification with Hamming loss,
Raman et al. (2023a) characterize learnability of
$\mathcal{H}\subseteq(\\{0,1\\}^{K})^{\mathcal{X}}$ in terms of the
Littlestone dimension of each
$\mathcal{H}_{i}\subseteq\\{0,1\\}^{\mathcal{X}}$. Their characterization only
works for small $K$, namely when $K=o(\sqrt{T})$. Furthermore, Raman et al.
(2023b) studies multilabel classification with the thresholded Hamming loss,
$\ell(y,z)=\mathbbm{1}\left\\{\sum_{i=1}^{K}\mathbbm{1}\\{y^{i}\neq
z^{i}\\}\geq q\right\\}$ for $q\in[K-1]$, and provides a $K$-independent
characterization of learnability for this $q$-insensitive model. Extending
Raman et al. (2023a, b), this work resolves the question of learnability for
multilabel classification with Hamming loss for arbitrary $K\in\mathbb{N}$.

###  7.1  Online Vector-Valued Regression

Let $(\mathcal{V},\left\lVert\cdot\right\rVert)$ be a normed vector space and
define $\mathcal{Z}=\mathcal{Y}:=\\{v\in\mathcal{V}:\,\left\lVert
v\right\rVert\leq 1\\}$ to be the unit ball centered around origin in
$\mathcal{V}$. Note that $\mathcal{Y}$ is infinite-dimensional if
$\mathcal{V}$ is infinite-dimensional. We consider the loss function to be
$\ell(y,z):=\left\lVert y-z\right\rVert^{p}$ for $p\in[1,\infty]$. Clearly,
$\sup_{y,z\in\mathcal{Y}}\ell(y,z)\leq 2^{p}$. The problem of vector-valued
regression is an extremely general framework capturing a wide range of
regression problems. For instance, it captures multioutput regression on
$\mathbb{R}^{K}$ with $\left\lVert\cdot\right\rVert_{p}$ norms as well as
their $p^{th}$ power (Raman et al., 2023a) as well as function-valued
regression (Morris, 2015). As an example, consider
$(\mathcal{V},\left\lVert\cdot\right\rVert)=(C_{\mathbb{R}}(\Omega),\left\lVert\cdot\right\rVert_{\infty})$,
a Banach space of all continuous real-valued functions defined on a
topological space $\Omega$ equipped with the norm $\left\lVert
f\right\rVert_{\infty}=\sup_{\omega\in\Omega}|f(w)|$. One may also consider
the problem of operator learning when both $\mathcal{X}$ and $\mathcal{Y}$ are
subsets of vector spaces and the hypothesis class is a subset of linear
operators between $\mathcal{X}$ and $\mathcal{Y}$ (Tabaghi et al., 2019;
Sridharan and Tewari, 2010).

Theorem 5 immediately implies that a vector-valued hypothesis class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is learnable if and only if
$\text{SMdim}_{\gamma}(\mathcal{H})<\infty$ for all $\gamma>0$. Next, we use
Theorem 5 and Lemma 5.1 to derive quantitative regret bounds.

Corollary 1:  Characterization of Learnability for Vector-Valued Regression
Let $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ and $\ell(y,z)=\left\lVert
y-z\right\rVert^{p}$. Then, (i) There exists a randomized online learner whose
expected regret on any stream is at most
$\inf_{\gamma>0}\,\left\\{2^{p}\,\cdot\text{SMdim}_{\gamma}(\mathcal{H})+\gamma
T+1+2^{p+1}\sqrt{\,\text{SMdim}_{\gamma}(\mathcal{H})\,T\ln(2^{p+1}\,T)}\right\\}.$
(ii) Define
$\eta:=\max_{(x,h_{1},h_{2})\in\mathcal{X}\times\mathcal{H}\times\mathcal{H}}\,\,\ell(h_{1}(x),h_{2}(x))$.
For every randomized online learner, there exists a stream such that the
expected regret of the learner is at least
$\begin{cases}\max\left(\eta\sqrt{\frac{T}{8}}\,,\,\sup_{\gamma>0}\,\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})\right)\quad&\quad\text{
if }p=1,\\\
\sup_{\gamma>0}\,\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})\quad&\quad\text{
otherwise}.\end{cases}$

Note that (i) follows immediately from Theorem 5. So, we only focus on proving
(ii) here.

###### Proof.

(of (ii) in Corollary 7.2) The lower bound of
$\sup_{\gamma>0}\,\gamma\text{SMdim}_{\gamma}(\mathcal{H})$ is immediate from
Theorem 5 as well. Thus, it suffices to establish the lower bound of
$\eta\sqrt{\frac{T}{8}}$ for $p=1$. In view of Lemma 5.1, it amounts to
finding $y_{-1},y_{+1}$ such that the conditions outlined in the Lemma are
satisfied. Let $h_{-1},h_{+1},x$ be such that
$\ell(h_{-1}(x),h_{+1}(x))=\eta>0$. We can always find $h_{-1},h_{+1},x$ for
any non-trivial hypothesis class where $|\mathcal{H}|\geq 2$. As
$\mathcal{Y}=\mathcal{Z}$, we can pick $y_{-1}=h_{-1}(x)$ and
$y_{+1}=h_{+1}(x)$. Then, condition (i) is satisfied because

$\min_{\sigma\in\\{\pm
1\\}}\Big{(}\ell(y_{-\sigma},h_{\sigma}(x))-\ell(y_{\sigma},h_{\sigma}(x))\Big{)}=\ell(h_{-1}(x),h_{+1}(x))=\eta>0.$

As for condition (ii), we can use the triangle inequality to obtain

$\inf_{z\in\mathcal{Z}}\Big{(}\ell(y_{-1},z)+\ell(y_{+1},z)\Big{)}\geq\ell(y_{-1}(x),y_{+1}(x))=\frac{1}{2}\sum_{\sigma_{1},\sigma_{2}}\ell(y_{\sigma_{1}},h_{\sigma_{2}}(x)),$

where the last equality follows because
$\ell(y_{\sigma_{i}},h_{\sigma_{i}}(x))=0$ for $\sigma_{i}\in\\{-1,1\\}$ and
$\ell(y_{-\sigma_{i}},h_{\sigma_{i}}(x))=\ell(y_{\sigma_{i}},h_{-\sigma_{i}}(x))=\ell(y_{-1}(x),y_{+1}(x))$
for $\sigma_{i}\in\\{-1,1\\}$. This completes our proof. ∎

For general $p$ (when the loss is not a distance metric), we provide an
example showing that the lower bound of
$\sup_{\gamma>0}\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})$ is tight up to
logarithmic factors in $T$. This also shows that the lower bound of
$\Omega(\sqrt{T})$ is not always possible. Let $\mathcal{V}$ be a Hibert space
and $\mathcal{Y}=\mathcal{Z}$ be the usual unit ball in $\mathcal{V}$. Define
$\mathcal{H}=\\{v\in\mathcal{V}:\left\lVert v\right\rVert\leq 1\\}$ to be a
set of all constant functions mapping to the vectors in the unit ball, and
consider the loss function $\ell(y,z)=\left\lVert y-z\right\rVert^{2}$. Let
$e_{1},e_{2}$ be two orthonormal bases in $\mathcal{V}$. Since $\left\lVert
e_{i}\right\rVert=1$, we must have $e_{i}\in\mathcal{Y}$. It is easy to see
that $\text{SMdim}_{\frac{1}{2}}(\mathcal{H})\geq 1$. This is true because,
for every $\mu\in\Pi(\mathcal{Z})$, there exists $y\in\\{e_{1},e_{2}\\}$ such
that $\operatorname*{\operatorname{\mathbb{E}}}_{z\sim\mu}\left[\left\lVert
y-z\right\rVert\right]\geq\frac{1}{\sqrt{2}}$. Using Jensen’s, we further
obtain $\operatorname*{\operatorname{\mathbb{E}}}_{z\sim\mu}\left[\left\lVert
y-z\right\rVert^{2}\right]\geq\left(\operatorname*{\operatorname{\mathbb{E}}}_{z\sim\mu}\left[\left\lVert
y-z\right\rVert\right]\right)^{2}\geq\frac{1}{2}$. Suppose, for the sake of
contradiction, there exists $\mu\in\Pi(\mathcal{Z})$ such that
$\operatorname*{\operatorname{\mathbb{E}}}_{z\sim\mu}[\left\lVert
e_{1}-z\right\rVert]<\frac{1}{\sqrt{2}}$ and
$\operatorname*{\operatorname{\mathbb{E}}}_{z\sim\mu}[\left\lVert
e_{2}-z\right\rVert]<\frac{1}{\sqrt{2}}$. Upon adding these two inequalities
and using reverse triangle inequality, we obtain $\left\lVert
e_{1}-e_{2}\right\rVert<\sqrt{2}$, a contradiction as $\left\lVert
e_{1}-e_{2}\right\rVert=\sqrt{2}$. Therefore, Theorem 5 implies the lower
bound of
$\sup_{\gamma>0}\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})\geq\frac{1}{2}$ for
this problem. However, it is well known that the regret of the Follow The
Leader algorithm is $\leq 8(1+\ln(T))$ (see (Cesa-Bianchi and Lugosi, 2006,
Page 43) for the proof), showing that our lower bound is tight up to
$O(\ln(T))$.

Next, consider a particular Hilbert space $\mathcal{V}=\mathbb{R}$ equipped
with inner product $\langle y,z\rangle:=yz$ and take
$\mathcal{Y}=\mathcal{Z}=[-1,1]$. Then, the squared norm loss reduces to
$\left\lVert y-z\right\rVert^{2}=\left\langle y-z,y-z\right\rangle=(y-z)^{2}$,
the usual squared loss for scalar-valued regression. Thus, the result in Cesa-
Bianchi and Lugosi (2006) shows that one cannot obtain a lower bound of
$\Omega(\sqrt{T})$ even for scalar-valued regression with squared loss. This
is in contrast to scalar-valued regression with absolute value loss where one
can obtain a lower bound of $\Omega(\sqrt{T})$ for any non-trivial hypothesis
class where $|\mathcal{H}|\geq 2$. Moreover, one can verify that the squared
loss does not satisfy the conditions of Lemma 5.1 whereas the absolute value
loss does. This highlights how sensitive quantitative characterizations are to
the loss function.

###  7.2 Online Multilabel Classification

For $K\in\mathbb{N}$, let $\mathcal{Y}=\mathcal{Z}=\\{0,1\\}^{K}$. Define
$\ell(y,z):=\frac{1}{K}\sum_{i=1}^{K}\mathbbm{1}\\{y^{i}\neq z^{i}\\}$, the
normalized Hamming distance between $y$ and $z$. As before, Theorem 5
immediately implies that a multilabel hypothesis class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is learnable if and only if
$\text{SMdim}_{\gamma}(\mathcal{H})<\infty$ for all $\gamma>0$. We now use
Theorem 5 and Lemma 5.1 to derive quantitative regret bounds.

Corollary 2:  Characterization of Learnability for Multilabel Classification
Let $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ and
$\ell(y,z)=\frac{1}{K}\sum_{i=1}^{K}\mathbbm{1}\\{y^{i}\neq z^{i}\\}$. Then,
(i) There exists a randomized online learner whose expected regret on any
stream is at most
$\inf_{\gamma>0}\,\left\\{\text{SMdim}_{\gamma}(\mathcal{H})+\gamma
T+1+2\,\sqrt{\text{SMdim}_{\gamma}(\mathcal{H})\,T\ln(T)}\right\\}.$ (ii)
Define
$\eta:=\sup_{(x,h_{1},h_{2})\in\mathcal{X}\times\mathcal{H}\times\mathcal{H}}\,\,\ell(h_{1}(x),h_{2}(x))$.
For every randomized online learner, there exists a stream such that the
expected regret of the learner is at least
$\max\left\\{\eta\sqrt{\frac{T}{8}}\,,\,\sup_{\gamma>0}\,\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})\right\\}$

###### Proof.

The proof of (i) and the lower bound of
$\sup_{\gamma>0}\,\gamma\,\text{SMdim}_{\gamma}(\mathcal{H})$ in (ii) is
immediate from Theorem 5. The lower bound of $\eta\sqrt{\frac{T}{8}}$ is
identical to the proof of Corollary 7.2 and uses the fact that
$\mathcal{Y}=\mathcal{Z}$ and $\ell$ is a distance metric. We leave the
details to the reader. ∎

## References

  * Ben-David et al. [2009] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz.  Agnostic online learning.  In _COLT_ , volume 3, page 1, 2009.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * 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.
  * Eckhoff [1993] Jürgen Eckhoff.  Helly, Radon, and Carathéodory Type Theorems.  In _Handbook of Convex Geometry_ , pages 389–448. North-Holland, Amsterdam, 1993.  ISBN 978-0-444-89596-7.  URL https://www.sciencedirect.com/science/article/pii/B9780444895967500171.
  * Filmus et al. [2023] Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran.  Optimal prediction using expert advice and randomized littlestone dimension, 2023.
  * Hanneke et al. [2023] Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari.  Multiclass online learning and uniform convergence.  _Proceedings of the 36th Annual Conference on Learning Theory (COLT)_ , 2023.
  * Littlestone [1987] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine Learning_ , 2:285–318, 1987.
  * Moran et al. [2023] Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili.  List online classification.  _arXiv preprint arXiv:2303.15383_ , 2023.
  * Morris [2015] Jeffrey S Morris.  Functional regression.  _Annual Review of Statistics and Its Application_ , 2:321–359, 2015.
  * Radon [1921] Johann Radon.  Mengen konvexer körper, die einen gemeinsamen punkt enthalten.  _Mathematische Annalen_ , 83(1-2):113–115, 1921\.
  * Rakhlin et al. [2015a] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning via sequential complexities.  _J. Mach. Learn. Res._ , 16(1):155–186, 2015a.
  * Rakhlin et al. [2015b] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Sequential complexities and uniform martingale laws of large numbers.  _Probability theory and related fields_ , 161:111–153, 2015b.
  * Rakhlin et al. [2012] Sasha Rakhlin, Ohad Shamir, and Karthik Sridharan.  Relax and randomize : From value to algorithms.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.  URL https://proceedings.neurips.cc/paper_files/paper/2012/file/53adaf494dc89ef7196d73636eb2451b-Paper.pdf.
  * Raman et al. [2023a] Vinod Raman, Unique Subedi, and Ambuj Tewari.  A characterization of multioutput learnability.  _arXiv cs.LG_ , 2023a.  preprint arXiv:2303.17716.
  * Raman et al. [2023b] Vinod Raman, Unique Subedi, and Ambuj Tewari.  Online learning with set-valued feedback.  _arXiv preprint arXiv:2306.06247_ , 2023b.
  * 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.
  * Sridharan and Tewari [2010] Karthik Sridharan and Ambuj Tewari.  Convex games in banach spaces.  In _COLT_ , pages 1–13. Citeseer, 2010.
  * Tabaghi et al. [2019] Puoya Tabaghi, Maarten de Hoop, and Ivan Dokmanić.  Learning schatten–von neumann operators.  _arXiv preprint arXiv:1901.10076_ , 2019.
  * Vapnik and Chervonenkis [1971] Vladimir Naumovich Vapnik and Aleksei Yakovlevich Chervonenkis.  On uniform convergence of the frequencies of events to their probabilities.  _Teoriya Veroyatnostei i ee Primeneniya_ , 16(2):264–279, 1971.