A Trichotomy for List Transductive Online Learning
Authors: Steve Hanneke
Amirreza Shaeiri
Venue: ICML 2025 poster (2025)
Keywords: Online Learning
Transductive Learning
List Learning
Primary area: theory->online_learning_and_bandits
TL;DR: We study the problem of list transductive online learning when the number of labels can be unbounded.

Abstract: List learning is an important topic in both theoretical and empirical machine learning research, playing a key role in the recent breakthrough result of (Brukhim et al., 2022) on the characterization of multiclass PAC learnability, as well as addressing label ambiguity in computer vision classification tasks, among others. In this paper, we study the problem of list transductive online learning. In this framework, the learner outputs a list of multiple labels for each instance rather than just one, as in traditional multiclass classification. In the realizable setting, we demonstrate a trichotomy of possible rates of the minimax number of mistakes. In particular, if the learner plays for $\text{T} \in \mathbb{N}$ rounds, its minimax number of mistakes can only be of the orders $\Theta(\text{T})$, $\Theta(\log \text{T})$, or $\Theta(1)$. This resolves an open question raised by (Hanneke et al., 2024). On the other hand, in the agnostic setting, we characterize the learnability by constructively proving the $\widetilde{\mathcal{O}}(\sqrt{\text{T}})$ upper bound on the minimax expected regret. Along the way, we also answer another open question asked by (Moran et al., 2023). To establish these results, we introduce two new combinatorial complexity dimensions, called the Level-constrained $(\mathrm{L+1})$-Littlestone dimension and Level-constrained $(\mathrm{L+1})$-Branching dimension, if the list size is $\mathrm{L} \in \mathbb{N}$. Eventually, we conclude our work by raising an open question regarding eliminating the factor list size, which seems to be a crucial step, as it has consistently appeared in previous works on this subject.

A Trichotomy for List Transductive Online Learning
Steve Hanneke'
Amirreza Shaeiri
Abstract
result by (Brukhim et al., 2022) on the combinatorial char- acterization of multiclass PAC learnability is the use list learners. Subsequent works, including (Charikar & Pab- baraju, 2023), (Moran et al., 2023), (Brukhim et al., 2024), (Hanneke et al., 2024a), and (Pabbaraju & Sarmasarkar, 2024) have studied the notion of list learnability in various contexts, such as PAC learning, online learning, boosting, as well as sample compression and uniform convergence, and real-valued regression, accordingly. Moreover, this topic brings to mind the fundamental setting of list-decodable learning in statistics. For a detailed discussion, for example, refer to Chapter 5 of the recent textbook by (Diakonikolas & Kane, 2023). From an empirical point of view, there are many scenarios in which one may prefer the list learning approach to the classical multiclass classification. For in- stance, in recommendation systems, the objective is often to present short list of items to users, trying to ensure that the user will select one of the items from the list. As another example, in computer vision classification tasks, predict- ing list of labels can potentially prevent label ambiguity. Furthermore, this subject may bring to mind the fundamen- tal setting of conformal prediction in practical applications, which can be viewed as a dual counterpart of the list setting.
List learning is an important topic in both theoreti- cal and empirical machine learning research, play- ing key role in the recent breakthrough result of (Brukhim al., 2022) on the characterization of multiclass PAC learnability, well the ambi- guity of labels in computer vision classification tasks, among others. In this paper, we study the problem of list transductive online learning. In this framework, the learner outputs a list of mul- tiple labels for each instance rather than just one, as in traditional multiclass classification. In the realizable setting, we demonstrate a trichotomy of possible rates of the minimax number of mistakes. In particular, if the learner plays for T E N rounds, its minimax number of mistakes can only be of the orders (TT), O (log T), or @(1). This resolves an open question raised by (Hanneke et al., 2024b). On the other hand, in the agnostic setting, we char- acterize the learnability by constructively prov- ing the Õ(vT) upper bound on the minimax ex- pected regret. Along this way. we also answer an- other open question asked by (Moran et al., 2023). To establish these results, we introduce two new combinatorial complexity dimensions, called the Level-constrained (I. + 1) Li-Littlestone dimension and Level-constrained (L + 1)- B-Brnnching dimen- sion, if the list size is L. E N. Eventually, we open question
Consider a round-robin tennis tournament consisting of T N matches, all scheduled in advance. In tennis, each set continues until one player leads by at least two games, so sets can, in theory, play indefinitely; this means the space of possible exact outcomes is countably infinite. A gambler, aware of the players participating in each match based on the schedule, aims to predict the exact outcomes. Since predicting the precise results is challenging, the gambler allowed submit list of L N possible outcomes for each match before it begins. After each match concludes, the actual result is disclosed. The gambler earns profit if the actual outcome is among the predictions they have submitted for that match. Given minimal assumptions about the nature of the matches, how can the gambler effectively select predictions to maximize the number of rounds that yield a profit?
conclude our work by raising regarding eliminating the factor of list size, which seems to be a crucial step, as it has consistently appeared in previous works on this subject.
1. Introduction
List learning is significant subject in both theoretical and empirical machine learning research. From theoretical point of view, key technique in the recent breakthrough
Department of Computer Science, Purdue University, West Lafayette, IN, USA. Correspondence to: Steve Hanneke <steve.hanneke@ waw.aannnkkgggglmmmm...m..... gmail.com>.
The aforementioned example, along with many other real- world scenarios involving possibly adversarially chosen pre- specified schedules, can be formulated within the framework called List Transductive Online Learning. This framework is informally defined as follows. Initially, an adversary
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Trichotomy for List Transductive Online Learning
selects a finite sequence of instances, such as images, of which the learner is aware. In each subsequent round, the learner must predict a list of labels, such a list of possible categories for an image, for the next instance in the sequence. Following each prediction, an adversary reveals the correct label. Importantly, in this setting, the learner provides a list of multiple labels for each instance instead of a single label, as in traditional multiclass classification. Moreover, the primary quantity of interest in this framework is the notion of the number of mistakes the learner makes over time. In particular, a mistake occurs if the correct label is not included in the learner's predicted list of labels. For simplicity, the informal formulation is presented here in the context of deterministic learners.
results answer an open question posed in their paper, re- garding the generalization of their results to the list setting. Moreover, we also demonstrate the existence of concept class that is not learnable in the multiclass transductive on- line learning framework; however, again, it is learnable in the list transductive online learning framework with only a few mistakes by using a list size of two Proposition C.3. To complete our findings, we illustrate an example of another concept class, which is easily list PAC learnable, but it is not list transductive online learnable, showing that the finiteness of the dimension from the work of (Charikar & Pabbaraju, 2023) is not sufficient for list transductive online learnability Proposition C.4. Finally, we note that in the way of proving the agnostic result, we also resolve another open question asked by (Moran et al., 2023), regarding the extension of their agnostic result the unbounded label spaces.
To derive meaningful results, this work adopts the well- established notion of concept class, consisting of fune- tions mapping the instance space to the label space. In the realizable setting, we assume that the sequence gener- ated by the adversary is consistent with at least one of the concepts within the concept class. Furthermore, in this set- ting, we focus specifically on minimizing the number of mistakes made by the learner as the primary objective. In contrast, in the agnostic setting, no assumptions are made about the sequence generated by the adversary. Here, rather than directly minimizing the learner's 's number of mistakes, we compare the learner's 's performance to that of the best concept within the concept class, a standard performance measure known as regret. Additionally, we note that when the learner's 's predictions are randomized, we focus on the expected values of the mentioned objectives.
1.1. Related Work
Online Learning. Online learning has been a subject of study for more than half a century, gaining significant atten- tion within the computer science community since the semi- nal work of (Littlestone, 1988). This foundational contribu- tion introduced the adversarial online learning framework for binary classification setting, where during each round, an adversary selects an instance; afterward, the learner required to predict binary label for that instance; following this, the adversary reveals the correct label. The celebrated work of (Littlestone, 1988) also provided combinatorial characterization of learnability for the mentioned problem in the realizable setting based on the Littlestone dimension. Later, (Ben-David et al., 2009) extended Littlestone's 's result to the agnostic setting, showing that the Littlestone dimen- sion continues to characterize the learnability. Since then, online learning has been explored in various frameworks, including multiclass setting (Daniely et al., 2012; Hanneke et al., 2023a), and list setting (Moran et al., 2023). Given its fundamental nature, online learning has found numerous practical applications.
In this paper, our main contribution is constructively answer- ing the following questions in the list transductive online learning framework:
What are the possible rates of the minimax number of mistakes in the realizable setting function of the concept class C and the size of the initial sequence selected by the adversary T?
What is the necessary and sufficient combinatorial con- dition to make learnability possible in the agnostic regime?
Transductive Online Learning. In contrast to the above definition of online learning, an alternative setting involves scenario where the sequence of instances is predetermined by adversary before the start of the game. This setting can eliminate the uncertainty associated with instances, yet retains the uncertainty about the labels. The study of this setting was first initiated by (Ben-David et al., 1997), with the goal of exploring how uncertainty in labeling alone influences the optimal number of mistakes. Furthermore, given that the online learnable classes are quite limiting. it is natural extend the learnable classes whenever we have additional assumptions. Notably, the recent work of (Hanneke et al., 2023b) referred to this setting by the term "Transductive Online Learning" due to its relation to trans- ductive PAC learning. Given the set of instances before the
Before this study, the questions outlined above remained entirely open, particularly in scenarios where the number of labels is unbounded. In fact, we show that there exists a concept class that is not learnable in the list online learning framework of (Moran al., 2023), which does not assume prior knowledge of the sequence of instances, but it becomes learnable in the list transductive online learning framework with only a few mistakes Proposition C.5. Notably, the special case of list size of one, which is equivalent to the multiclass transductive online learning framework, was re- cently studied in (Hanneke et al., 2024b). In particular, our
2

---

A Trichotomy for List Transductive Online Learning
start of the game, other related lines of research include the self-directed online learning framework, in which the learn- ing algorithm is permitted to choose the next instance for prediction from the remaining set of instances in each round. Additionally, there is the best order framework, where the learner, rather than an adversary, determines the order of instances at the outset of the game. See (Goldman & Sloan, 1994; Ben-David et al., 1995: Ben-David & Eiron, 1998: Devulapalli & Hanneke, 2024) for more details.
sion, we first need define the Level-constrained (L + 1)- Littlestone tree. A Level-constrained (T. 1)-Littlestone tree is a (L + 1)-Littlestone tree with the additional require- ment that for a given level the same instance has to label all nodes. Then, the (T. + 1)=-Level-oonstrained Littlestone dimension is defined as suPдeN such that there exists a shat- tered Level-constrained (L + 1)-Littlestone tree of depth d. To define the Level-constrained (L + 1)- Branchhig dimen- sion, we first need define the Level-constrained (L. + 1)- Branching tree. A Level-constrained (L + 1)- 1)-Branching tree is a Level-constrained (T. +I.+ 1)-L 1)-Littlestone tree without the restriction that the labels on the two outgoing edges are distinct. Then, the Level-constrained (L + 1)-BBanchhng dimension is defined as suPdeN such that there exists a shat- tered cevel-constrained (L + J-Branching tree such that every root-to-leaf path contains least d nodes with all dis- tinet labels. See subsection 2.3 for more details. Formally, we have the following theorem.
1.2. Overview of the Main Results
In the subsequent subsection, we provide an overview of the primary results in our paper along with summary of the proof techniques.
1.2.1. LIST TRANSDUCTIVE ONLINE LEARNING FRAMEWORK
We consider a sequential game between the learner and an adversary over a total of T E N rounds. Initially, an adver- sary chooses a sequence of T instances from non-empty instance space X, namely 22,,,...... the learner. Morcover, at each round t (T]. the adversary selects a label Yi from non-empty label space y, which can possibly be uncountable; then, the learner predicts a list of size L E N of labels, which can be randomized; sub- sequently, the learner, observes the true label y/- Before going forward, following the well-established frameworks in learning theory, we consider concept class C as set of mappings from X' to y that is known to the learner before starting the game. See subsubsection 2.2.1 I and subsubsec- tion 2.2.2 for more details.
Theorem 1.1. Let Q (x, J,,, C) be an instance of the list transductive online learning framework. Then, we have:
and reveals it to
e())
B(Q) < oo
( T) E O(log),,
D(@) < oo and B(Q) 00,
(()),
D(@)= = 0
where B(Q) is the Level-construined I. L.-Branching dimen- sion of Q and D(2) is the Level-constrained L-Littlestone dimension of Q both of them defined in subsection 2.3.
The proof of the above theorem comprises up several com- ponents. First, to establish the upper bound in the constant case, basically, we generalize the notion of rank introduced by (Ben-David et al., 1997) to the list setting. Then, we use the adaptation of Littlestone's 's Standard Optimal Algorithm (SOA) to get the final result. Next, we derive two lower bounds by using ideas from (Hanneke et al., 2024b). For the upper bound in the log T case, the first idea that one may think of is to employ the Halving algorithm combined with the list Sauer-Shelah-Perie (SSP) Lemma from (Charikar & Pabbaraju, 2023; Hanneke et al., 2024a). However, as discussed by (Hanneke al., 2024b), this approach is in- applicable when the label space is unbounded. Importantly, even when focusing on the finite label space setting, this approach is not applicable at all. To see this, notice that the number of functions based on the list SSP Lemma from (Charikar & Pabbaraju, 2023; Hanneke et al., 2024a), can be of order OL T dd. where k denotes the size of the label space, L the list size, and d is the associated dimen- sion. Consequently, as the reduction in the version space per mistake is only by factor of 1 - -L. k, this approach leads to a bound that is linear in T. To overcome this obstacle, we generalize the technique of (Hanneke et al., 2024b). This technique enables us to establish the desired upper bound of log T on the minimax number of mistakes. In summary,
1.2.2. REALIZABLE SETTING
In the realizable setting, we assume that the sequence (21, vi),..., (Fr, generated by the adversary, con- sistent with at least one mapping in the concept class C. Moreover, in this setting, we focus on the standard notion of the number of mistakes made by the learner over T rounds. In particular, we aim to establish upper and lower bounds on the minimax number of mistakes, as a function of Q as an instance of the list transductive online learning framework and T as a total number of rounds, denoted by M* T). See subsubsection 2.2.4 for more details.
Our primary result in this part demonstrates that if the learner plays for T E N rounds, its minimax number of mistakes can only be of the orders O(T). O(log T), or O(1). Furthermore, this trichotomy is fully characterized by the finiteness of the Level-constrained (L + 1)-Littlestone di- mension and the Level-constrained (L + Brannching di- mension, where the list size is L E N.
To define the Level-constrained (L + L)-Littlestone dimen-
3

---

A Trichotomy for List Transductive Online Learning
we define notion of shattering for a sequence of instances from X. Based on the finiteness of D [), we can bound the total number of sub-sequences of the initial sequence played by the adversary that are shattered. A key observation is that if we do not have any shattered sub-sequence, we will make no more mistakes. Our algorithm can guarantee a decrease in the number of shattered sub-sequences after making a mistake, so the total number of mistakes is bounded. See section 3 and Appendix A for more details.
setting for proving the upper bound in the log(T) case. Fur- thermore, we combined dynamic experts with the celebrated exponential weights algorithm to get the final result. Our finding indicates that the technique introduced in (Hanneke et al., 2023a) effectively addresses infinite label spaces even in the list setting, thereby resolving the question raised by (Moran et al., 2023) regarding the extension of their agnos- tic result to the unbounded label spaces. See section 4 and Appendix B for more details.
Before proceeding, we emphasize that in contrast to the multiclass setting, even the finite label space regime for list learning cannot be handled by the simple approach of Halving via the SSP Lemma. Moreover, there are differ- ent ways of selecting I. labels. We found that decreas- ingly sorting the label set y based on appropriate mea- sures and selecting the first L labels works in both of our upper bounds. Also, we have the following inequalities: DS( S ( S B(Q)= < LD(();; see Appendix C.
1.3. Organization
The rest of the paper is organized as follows. In section 2, we formally set the notation and definitions. Subsequently, in section 3, we present our results for the realizable setting, Then, in section 4, we extend our results to the agnostic set- ting. Afterward. in Appendix C, we provide a few examples showing separations between different related combinato- rial complexity dimensions. Eventually, section 5, we conclude our manuscript and present some future directions.
1.2.3. AGNOSTIC SETTING
In the agnostic setting, we make no assumptions about the sequence (z )1). (I2, 92)....... (2T, Yr), generated by the adversary. Moreover, in this setting, our focus shifts to the standard notion of expected regret, which compares the expected number of mistakes made by the learner to those made by the best concept in the concept class C over the sequence. In particular, we say that an instance of the list transductive online learning framework Q is agnostic learnable in the list transductive online learning framework, if the minimax expected regret, as a function of Q and T total number of rounds, denoted by R (Q, T), is sub-linear in T. See subsubsection 2.2.5 for more details.
2. Notations, Definitions, and Preliminaries
In this section, we set our basic notations in subsection 1. Then, we present the List Transductive Online Learning framework in subsection 2.2. Finally, we define main combi- natorial complexity measures in this paper in subsection 2.3.
2.1. Notations
In this subsection, we present the basic notations that we use throughout our paper. Let N and IR stand for the set of natural and real numbers, accordingly. We denote by N the extended natural number system defined as N := N U (-00, xx). Also, for a given E N, we use [m] to denote {1,2...., ,n). Next, let E N, for any sequence of size n or n-tuple Ir and any i E N such that 1 < i < n, let us use D; to denote the i-th element in x. To increase the readability of our manuscript, we use "" to separate indices of elements when we have more than one index; for instance, let be sequence of size 5 of 2-mulees we denote by I5,1 the first element of the 5-th element of z. We denote by A x B the Cartesian product of two arbitrarily sets A and B. In addition, for any set A and any n E N, we let A indicate n times the Cartesian product of A with itself. Note that, for any set A, we define A := {0]. Also, given set A, we denote by A the set of all finite sequences of the members of A; more formally, A = Ur-o AT Then, for the arbitrary sets X and Y, we use Y to denote the space of all functions from X to Y. Finally, we use O(). o(),, 2(.), w(.), and (() as standard notations of them in the theoretical computer science. We also use O(), ②()), Õ(-) to exclude logarithmic factors as well as constant coefficients.
Our primary result in this part demonstrates that this crite- rion for learnability is fully characterized by the finiteness of the Level-constrained (L + L)-Litlestoone dimension, if the list size is I. E N. Formally, we have the following theorem.
Theorem 1.2. Ler 2= - (X,, be an instance of the list transductive online learning framework. Then, Q is agnostic learnable in the list transductive online learn- ing framework if and only if has finite Level-constraine (L + 1)-Littlestone dimension.
The proof of the above theorem involves a few pieces. First, we establish the lower bound for randomized learners by leveraging ideas from (Moran et al., 2023). To prove the upper bound, we face the challenge of dealing with an un- bounded label space, which renders the standard techniques from -Beid et al., 2009; Daniely et al., 2012) inappli- cable. To overcome this obstacle, we employ the dynamic expert technique from the recent work of (Hanneke et al., 2023a). To do so, we use our technique from the realizable
4

---

A Trichotomy for List Transductive Online Learning
2.2. List Transductive Online Learning Framework
Y", |a*| = |yr [=*1]. A randomized list transductive online learning rule is mapping A D IT))).
In this subsection, we present the List Transductive Online Learning framework. To do so, first, we give the problem setup in subsubsection 2.2.1. Then, we formulate the prob- lem in subsubsection 2.2.2. Afterward, we define list trans- ductive online learning algorithms in subsubsection 2.2.3. Finally, we give the associated definitions with the realizable and agnostic settings in subsubsection 2.2.4 and subsubsec- tion 2.2.5, accordingly.
In words, it is mapping that maps each finite sequence of instances denoted by z', finite sequence of set of labels of size I, denoted by a', and a finite sequence of labels denoted by y' such that |at| = 1y" < on VL.
|a*| to a probability measure
2.2.4. REALIZABLE SETTING
2.2.1. PROBLEM SETUP
Here, we begin by defining a realizable sequence. Then, to evaluate the performance of any deterministic algorithm, we define the well-known notion of the number of mistakes adapted to our framework. Finally, we define the optimal mistake bound, building on the previous definitions.
Fix non-empty set X' as the instance space. Let I E N be the size of the list. Also, fix non-empty set ) equipped with a o-algebra such that every subset of y with cardi- nality L is measurable as the label space. We note briefly that, since our focus is on deterministic algorithms in the realizable setting, no measurability assumptions on y are required. Following the well-established frameworks in learning theory, let C C yit be concept class. In particu- lar, a 4-tuple Q (Xt L, C) presents an instance of the list transductive online learning framework.
Definition 2.3 (Realizable Sequence). Fix T E N. We say that finite sequence of size of instance-label pairs ((11, V1), (22.32),.. 92)..... (Fr, yr)) E (X' x )) is realizable by concept class if there exists a concept e E such that for every i [T]. we have c(2;) = y/+
Definition 2.4 (Number of Mistakes). Let A be a deter- ministic list transductive online learning rule. Fix N. Let S be finite sequence of size T of instance-lahel pairs S = ((Z), 31), (x2, 32),.... ..... (IT, BT)) E (X' x 2/). We define the number of mistakes made by A with respect to the sequence S, denoted by M(A; S), as follows:
2.2.2. LIST TRANSDUCTIVE ONLINE LEARNING GAME
Let T E The problem of list transductive online learn- ing formulated as T-rounded sequential game between the leamer/player and adversary/opponent. Initially, adversary chooses a sequence of T instances X E X and reveals it to the learner. Moreover, at each round & E (T):
M(A;S) = Σ 139h yr & A((S", ....... Vi- 11)) 1=1
The adversary chooses label ye from V.
where S' is defined as follows: S' := (x1, T2.... .T). Definition 2.5 (Optimal Mistake Bound). Let Q (X, C) be an instance of the list transductive online learning framework. The optimal mistake bound of Q as function of the time horizon T, denoted by M' (2, T), is defined follows:
The learner predicts a list of size of labels.
The adversary reveals the true label ye-
2.2.3. LIST TRANSDUCTIVE ONLINE LEARNING RULES
We consider two different types of list transductive online learning rules/algorithms, namely deterministic rules and randomized rules. As a result, we have the following defini- tions.
M (Q.T)) inf A AEA A
sup
M(A S).
SE (X which is realizable
Definition 2.1 (Deterministic List Transductive Online Learning Rule). Let D = {(x",w") x² X y² "", 1y01 [- In addition, let V/2 [ A V, [A| L). A deterministic list transductive online learning rule is mapping A A + +1.
where A is defined as the set of all deterministic list trans- ductive online learning rules.
Before proceeding, important to note that while our definitions are based on an oblivious adversary, it is straight- forward that they are equivalent to the case with an adaptive adversary.
In words, is a mapping that maps each finite sequence of instances and a finite sequence of labels with size smaller than the size of the sequence of instances to set of size L of labels.
2.2.5. AGNOSTIC SETTING
Definition 2.2 (Randomized List Transductive Online Learn- ing Rule). Let Vi- = [A] A C y, |A| = L}. In addi- x² X a* A', y² E
In this subsubsection, we begin by defining the well-known game theoretic notion regret. Then, we present the defini- tion of agnostic learnability.
tion, let D = {xx", { a²)""))))
5

---

A Trichotomy for List Transductive Online Learning
Definition 2.6 (Expected Regret). Let A be randomized list transductive online learning rule. Fix T N. Let S be a finite sequence of size T of instance-label pairs S = ((11,31) (I2, . (xr,, vr)) (r)) E (X' x " We define the expected regret of A with respect to the se- quence S against the competitor concept class C, denoted by R(A; S; C). as follows:
edges are labeled by an element of v Moreover, for any L- ary (L,, 3 > tree, a root to leaf path of length & E N can be identified by sequence of pairs s E (2" x w
2.3.1. (L+ + 1)-LITTLESTONE DIMENSION
Definition 2.11 ((I 1)-ittleess Tree), Let Q = (X, be an instance of the list transductive online learning framework. An (L+ 1)-ary (2())))valued tree T is called (L + 1)-Littlestone tree for @
T 11 (/ + c(x))),
R(A;S;C) = EN (M inf CEC
where we view a single run of the randomized list transduc- tive online learning rule as running a deterministic list transductive online learning rule A'. Moreover, we take the expectation over a random sequence of outputs of A.
Definition 2.12 (Shattered (L + 1)- 1)-Littlestone Tree). Let Q= = (X, L, C) be an instance of the list transductive on- line learning framework. We say that a (L + 1)-Linlestone tree for T for Q is shattered by C, if for every finite root to leaf path in T, identified by s E (X x y) for some e E N. there exists concept E C such that for every i E N, S E we have: $,2 = c(s;,1).
Definition 2.7 (Optimal Expected Regret). Let Q = (x,, C)),) be an instance of the list transductive online learning framework. The optimal expected regret bound of Q as a function of the time horizon T, denoted by R2(2, (Q,T), is defined as follows:
Definition 2.13 ((L + 1)-Littlestone Dimension). Let Q = (,, C) be an instance of the list transductive online learning framework. The (L + 1)-Littlestone dimension of 2, denoted by L(2). is defined as a supaeñ such that there exists (L + 1)-Littlestone tree T of depth d for Q that all children of every node have distinct labels which is shattered by C. Also, if C = {0}, we have: L( O.
R R' (Q.T) = inf A EA
sup SE
R;A;
where A is defined the set of all randomized list transduc- tive online learning rules.
Definition 2.8 (Agnostic Learnability). We say that an in- stance of the list transductive online learning framework Q = (xx, T,, V. C) is agnostic learnable in the list transduc- tive online learning framework, if R (Q, T) as a function of the time horizon T is sub-linear T.
2.3.2. LEVEL-CONSTRAINEED (T. + 1)- LITTLESON, DIMENSION
Definition 2.14 (Level-constrained (L + L)-Littlestone Di- mension). Let Q = (X, C) be instance of the list transductive online learning framework. The Level- constrained (T. + 1)-Littlestonee dimension of Q, denoted by D(Q) E N, is defined as a suPdeN such that there exists a (L 1)-Littlesstoon tree T of depth d for Q that all chil- dren of every node are labeled by distinct elements of y and all nodes at the same level are labeled by the same element of X which is shattered by C. Also, if C {0], we have: D () 0.
Before proceeding, it is important to note that while our definitions based oblivious adversary, it is straight- forward to see that they equivalent to the case with adaptive adversary. See Lemma 4.1 in (Cesa-Bianchi & Lugosi, 2006).
We emphasize that one may also consider a similar notion of learnability defined using (T) the realizable setting.
2.3. Combinatorial Complexity Parameters
In this subsection, we first set our notations for trees. Then, we proceed with the definitions of the main combinatorial complexity parameters in our paper based on previous defi- nitions.
2.3.3. LEVEL-CONSTRAINED (L 1)-BRANCIING DIMENSION
Definition 2.15 (Level-constrained (I. + 1)-Branching Di- mension). Let Q = (X, V,C) be an instance of the list transductive online learning framework. The Level- constrained (L +L+1J 1--Banchhn dimension of denoted by supaeN such that there exists
Definition 2.9 (Perfect Rooted L-ary Trees). Let E N. perfect rooted L-ary tree T is rooted tree, each of whose internal nodes has exactly I, children and all leaves have the same depth.
B ()) N, is defined (I+ 1)-Littlestone tree T for Q that all nodes at the same level are labeled by the same element of X' and every root to leaf path contains at least d nodes labeled by distinct elements of y which is shattered by C. Also, if C = {0). we have: B(Q) = O.
Definition 2.10 (L-ary (2,, --alued Trees). Let L E N. Also, let 2r, 3/ be any non-empty sets. A L-ary (2,, 3/- valued tree T is a perfect rooted L-ary tree, each of whose nodes are labeled by an element of L., and each of whose
6

---

A Trichotomy for List Transductive Online Learning
3. Realizable Setting
construct an adversarial strategy for an arbitrary determin- istic list transductive online learning rule A, we conclude M ( T) 2 T. Finally, note that this argument works for any T E N. This finishes the proof.
First, we restate the main theorem in the realizable setting here for the sake of simplicity.
Theorem 3.1. Let Q = (X,L, C) be an instance of the list transductive online learning framework. Then, we have:
Fix T E N. Indeed, for a given Q = (X. L, L, C), if D(2) d, using the above proof, can show min { [T. d lower bound.
(11,
B(Q) < xc
(2, E<
(log?)), D(2) < oo and B(Q) = 00.
(()), D(2) 00
3.2. Lower Bound log(L T+1) log(L+1)
We continue by proving the lower bound for the Logarith- mic case. Furthermore, the proof requires the following combinatorial Lemma. Additionally, we establish similar lower bound as the one we just proved before presenting the main result.
Proof. The theorem can be proved by combining two lower bounds of Lemma 3.2 and Lemma 3.5 as well as two upper bounds from Lemma A.1 and Lemma A.3. This finishes the proof.
L
We provide the proofs for the lower bounds in the main text, while deferring the more technical proofs for the upper bounds to Appendix A.
Lemma 3.3. Let Q (X,1,,,, be an instance of the list transductive online learning framework. Assume that B(Q) = d for some d E N. Then, there exists a (L + 1)- (T.
Littlestone tree of maximum depth
witnessing
3.1. Lower Bound T
L
B = d, crucially, just using a subset of nodes in any free witnessing ((2) = d.
We start by proving the lower bound for the linear case. Fur- thermore, the proof of the following Lemma uses the main idea in the lower bound proof of the work of (Littlestone, 1988).
Proef. We prove this Lemma by induction. We start with the base case. In particular, assume d = 1. Let T be a (L++t)-Litlestooee tree witnessing B(2) = 1. Thus, in every root-leaf-patte in T, we should have at least one node whose outgoing edges are labeled by (L. + 1) distinct values from y. Take one such node. Indeed, this node can itself witness
Lemma 3.2. Let Q (X, be an instance of the list transductive online learning framework. Assume that D(Q)= = 0c. Then, we have (*, T) E Q(T).
Proof. Fix T E N. Let T be (T. + 1)-Littlestone tree witnessing D)))= T. Note that such tree should exist as D(Q)= = co. Based on Definition 2.14, this tree should have depth T as well. Also, at each level of T, all nodes are labeled by the same instance from X. In addition, children of all nodes are labeled by distinct labels from y. Let A be any deterministic list transductive online learning rule. Now, we will build adversarial strategy against A using T. To do so, we first present T instances at T levels of T in order to the learner before starting the game. Furthermore, we will continue to make this strategy based on a special root-to-leaf path in T, which depends on A. Receive the first set of labels of size predicted by the learner. As we have I. + 1 edges for the root node of labeled with distinet labels from V, there exists at least one of them, which is labeled by a label that is not in the received set. We output that label. Moreover, we will continue this con- struction of the adversarial strategy based on T and A. Indeed, we can force T number of mistakes to the A. In addition, as T is shattered by C, there exists a concept in C, which is consistent with the root-to-leaf path that we used. So, we are in the realizable setting. As a result, we have: sups (X which is M(A:S) 2 T. Since are able to realizable by C
( 1. So, the depth is at most S (L (L+1)' - 1.
This finishes the proof of the base case. Now, assume the claim is true for E N. Subsequently, we prove the claim for 1. More specifically, we show that if B(2) = +1, then there exists (L + Li-titlletoone tree of maximum depth (L + 1) 1)
witnessing B(Q) = d+1. Let T be (L + 1)-Littlestone tree witnessing B(Q) = d+1. Find the node with the minimum level in T whose outgoing edges are labeled by (L+ 1) distinct values from V. Indeed, such a node should exist. Also, we have several of them, just take one. Now, denote (L. + 1) sub-trees of that node by Tı, TT. T(--)-- Restrict our instance space X' to instances on the levels of these sub-trees and call it X', Also, consider functions induced by the projection of C to X' and call it C'. Let Q' == (x', T., y,,,,'". Based on our construction of Q', we have B( = d. Now, we apply the induction hypothesis and get Ti, T..,.,,,7 T(++)) such that each of them witness ((2") = d and their depths (L + 1)a
L
are bounded above by join our one node to these sub-trees. In particular, to keep the level -constraint property, the final depth is bound by
L Subsequently let us
7

---

A Trichotomy for List Transductive Online Learning
(L 1) 1) -1 As we have (I++)xx (L (L+ 1)d +1
we have ( T) 2 r. Finally, note that this argument works for any T E'E N. This concludes the proof.
L
node with I. +1 outgoing edges labeled by I.+1 1 distinct labels from V/ the resulting tree can witness B(Q) d +1. This completes the proof.
4. Agnostic Setting
First, we restate the main theorem in the agnostic setting here for the sake of simplicity.
Lemma 3.4. Let Q= (X) be an instance of the list transductive online learning framework. Assume that B( = d for some d E N. Then, we have (2,T) 2 d for large enough T.
Theorem 4.1. Let Q = (X.L.V,C) be an instance of the list transductive online learning framework. Then, Q is agnostic learnable the list transductive online learning framework if and only D(2) 60.
Proof. Let T be (L + 1)-Littlestone tree of depth r E N witnessing ( = d. Based on Definition 2.15, at each level of T, all nodes are labeled with the same instance from X. Let be any deterministic list transductive online learning rule. Now, we will build an adversarial strategy against A using T. To do so, first present instances at levels of T in order to the learner before starting the game. Furthermore, we will continue to make this strategy based on a special root-to-leaf path in T, which depends on A. Receive the first set of labels of size L predicted by the learner. We may have L + 1 edges for the root node of T labeled with distinet labels from y. If that is the case, then there exists at least one of them, which is labeled by label that is not in the received set. We output that label. If that is not the case, just output any of them. Moreover, we will continue this construction of the adversarial strategy based on T and A. Indeed, we can force d number of mistakes to the A. This is because every root-to-lcaf path in T should contain at least d nodes having I. +1 outgoing edges labeled by distinet labels from Vr In addition, as T is shattered by C, there exists a concept in C, which is consistent with the root- to-leaf path that we used. So, we are in the realizable setting. M(A; S) 2 d.
Proof. The theorem can be proved by combining lower bound of Lemma B.1 and as well as upper bound from Lemma B.2.
5. Conclusion, Discussion, and Future Directions
In this work, we investigated the problem of list transduc- tive online learning with possibly arbitrary label space. In the realizable setting, we showed a trichotomy of possible minimax rates for the number of mistakes. In addition, we demonstrated a dichotomy of the minimax expected regret in the agnostic setting. To do so, we introduced two new combinatorial complexity parameters, the Level-constrained (L + L)-Littlestone dimension and the Level-constrained (L + 1)- Branching dimension for some L. E N.
Finally, we outline a potential future direction for this line of research. Similarly to our work, in all previous studies on list learnability, including (Charikar & Pabbaraju, 2023; Moran et al., 2023; Brukhim et al., 2024), additional factors related to the size of the list appear in the upper bounds. For instance, if the size of the list is L E N, in the work of (Charikar& & Pabbaraju, 2023). a factor L is present, or in the work of (Brukhim et al., 2024), a factor I,* arises. A key open question is how to eliminate such factors from our log T upper bound the realizable setting. Addressing this question could potentially lead to the climination of list size factors in other related problems as well. In close relation to this question, one could explore the problem of list learning with possibly unbounded list size. For example, the label space can be the real numbers, while lists are intervals of size c for some constant c E R.
As result, we have: sups (XXxy)" which
realizable by
Since we are able to construct an adversarial strategy for an arbitrary deterministic list transductive online learning rule A, we conclude M (2,T) T) 2 d for large enough T = r. This finishes the proof.
Lemma 3.5. Let Q = (X,L,,C) be an instance of the list transductive online learning framework. As- Dc. Then, we have (2,T) e
sume that B(Q) = Dc.
2 log(L T+1) E ((llg 7).
log(L+1)
(I. + 1)d - T for d. So, the
Proof. Fix T E N. Solve
L
Impact Statement
Now, define log(L T + 1) log(L + 1) Let T be a (I. + 1)-Littlestone tree witnessing [(2) =
result log(L T T+
This paper presents work whose goal is to advance the field of Statistical Learning Theory. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
log(L + 1)
Note that such a tree should exist as B(Q)= = 00. Now, apply Lemma 3.3 on TT Thus, we can get a (L + 1)- Littlestone tree witnessing B(Q)= = r whose depth is at most T. Subsequently, based on the proof of Lemma 3.4,
8

---

A Trichotomy for List Transductive Online Learning
References
Hanneke, S., Moran, S., Raman, V., Subedi, U., and Tewari, A. Multiclass online learning and uniform convergence. In The Thirty Sixth Annual Conference on Learning The- ory, Pp. 5682-5696. PMLR, 2023a.
Ben-David, S. and Eiron, N. Self-directed learning and its relation to the vc-dimension and to teacher-directee learning. Machine Learning. 33:87-104, 1998.
Hanneke, S., Moran, S., and Shafer, J. A trichotomy for transductive online learning. Advances in Neural Infor- mation Processing Systems, 2023b.
Ben-David, S., Eiron, N., and Kushilevitz, E. On self- directed learning. In Proceedings of the eighth annual conference on Computational learning theory, pp. 136- 143, 1995.
Hanneke, S., Moran, S., and Tom, W. List sample com- pression and uniform convergence. The Thirty Seventh Annual Conference on Learning Theory, pp. 2360-2388. PMLR, 2024a.
Ben-David, S., Kushilevitz, E., and Mansour, Y. Online learning versus offline learning. Machine Learning, 29: 45-63, 1997.
Hanneke, S., Raman, V., Shaeiri, A., and Subedi, Mul- ticlass transductive online learning. Advances in Neural Information Processing Systems, 2024b.
Ben-David, S., Pál, D., and Shalev-Shwartz, S. Agnos- tic online learning. In Conference on Learning Theory, volume 3, pp. 1, 2009.
Littlestone, N. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning. 2:285-318, 1988.
Bousquet, O., Hanneke, S., Moran, S., Van Handel, R., and Ychudayoff, A. A theory of universal learning. In Pro- ceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp.
Moran, S., Sharon, O., Tsubari, I., and Yosebashvili, S. List online classification. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1885-1913, PMLR, 2023.
Brukhim, N., Carmon, D., Dinur, I., Moran, S., and Yehu- dayoff, A. characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 943-955. 955. IEEE, 2022.
Pabbaraju, C. and Sarmasarkar, S. A characterization of list
regression, 2024.
Brukhim, N., Daniely, A., Mansour, Y., and Moran, S. Multi- class boosting: simple and intuitive weak learning criteria. Advances in Neural Information Processing Systems, 36, 2024.
Cesa-Bianchi, N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006. ISBN 9781139454827.
Charikar, M. and Pabbaraju, C. characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1713-1726, 2023.
Daniely, A., Sabato, S., and Shwartz, S. Multiclass learning approaches: A theoretical comparison with implications. Advances in Neural Information Processing Systems, 25, 2012.
Devulapalli, P. and Hanneke, S. The dimension of self- directed learning, 2024.
Diakonikolas, I. and Kane, D. M. Algorithmic high- dimensional robust statistics. Cambridge university press, 2023.
Goldman, S. A. and Sloan, R. H. The power of sire-dire learning. Machine Learning, 14:271-294. 1994.

---

A Trichotomy for List Transductive Online Learning
List Transductive Standard Optimal Algorithm (LTSOA)
Input: A 4-tuple Q (I.,,) total number of rounds T E N, and sequence of T instances X X
Initialize va = C and = 1.
While (t T):
1. Sort labels in y in non-increasing order according the values B (...... V2- for E y
2. Predict the list A, which consists of the top L labels in the above order.
3. Receive a label y/ E V.
4. Set V = Se-m and update = + 1.
Figure 1: List Transductive Standard Optimal Algorithm (LTSOA) is variant of Standard Optimal Algorithm (SOA) originally proposed by (Littlestone, 1988). Further, see the definition of Vz-vy for some V S y a E X, and y E y the proof Lemma A.1. addition, see the definition a sequence-dependent Level-constraint (L + -)-Bannchnng dimension the proof of Lemma A.1.
A. Realizable Upper Bounds Proofs
A.1. Upper Bound (())
Next, we move on to the proof of the constant upper bound. Furthermore, the proof the following Lemma uses the main idea in the upper bound proof of the work of (Littlestone, 1988).
Lemma A.1. Let Q (X, L.V.C) be an instance of the list transductive online learning framework. Assume that
( = d. Then, we have (2,7)) E O(d) E O(1).
Proof. We first define Ve-zy for some V C Sxx E X, and y E V. In particular, Ve-ry := {c Ve-yy: c(x) v). Next, for every X E 2 for some h N, define B (XX,,,
by adding new constraint to Definition 2.15. In particular, require to instances of X in order the label of the nodes of (L + 1)-ary Littlestone tree.
Now, we proceed with the proof of the Lemma. Fix T E N. We run LTSOA Algorithm I with input Q, T, and X E X as the initial sequence of instances chosen by the adversary. First of all, notice that for any instance of the list transductive
online learning framework Q', we have B(Q') 2 0. Also, notice that B (((X), X2, XT), C) I B(Q). As result, based on the following Claim, it is clear that sups (XxY)* which M(LTSOA; S B(2) d. Therefore. realizable by
(*Q2TT) < B(Q) = d. This completes the proof. Subsequently, we prove the following Claim.
Claim A.2. For every t E [T), if Vt & Ac. then B LT)
> B (((X++)
X.),,,
Proof We prove this claim by contradiction. For simplicity, denote B ((XX,, X (, by A. Also. denote B ((Xe+1)Xe42
L, by B. Assume that A B. Indeed, the case that A B is not possible. So, assume that A = B. If that the case, based on lines and in Algorithm 1, it means that there are at least L 1 labels such that the restriction of the current concept class yt-1 to 2, using those labels still leads to A as a new dimension. Thus, this means that A > as we can construct a new tree. This is clear contradiction.
10

---

A Trichotomy for List Transductive Online Learning
List Shattering Algorithm
Input: A 4-tuple Q (X,I, total number of rounds T E N, and sequence of T instances X X
Initialize ya = C and = 1.
While (t T):
1. Sort labels in Y in non-increasing order according to the values Sh ( vo- for E y
2. Predict the list A, which consists of the top L labels in the above order.
3. Receive a label y/ E V.
4. Set V = se-m and update = t 1.
See the definition of V2-+y for some V S v E X, and E Y in the proof of Lemma A.3. In addition, see the definition of Sh(.) in the proof of Lemma A.3.
Figure 2:
A.2. Upper Bound LD(C) log
eT ((@)
Finally, we turn our attention to proving the log T upper bound. Moreover, the proof of the following lemma represents the main contribution of this section, relying on the shattering technique from the recent work of (Hanneke et al., 2024b).
Lemma A.3. Let Q (X,L,V,C) be instance of the list transductive online learning framework. Assume that D(2) Then, we have (* oLdlog (+ log(T).
Proof. We first define Vz-ry for some V S y* x E X, and y E V. In particular, Vz-ry == {c Vz-ty: c(x) y). Next, for every X E 2 for some & E N, we say that X full shattered by there exists a (L + 1)-ary Littlestone tree T of depth & for Q such that all children of every node of T are labeled by distinct elements of y and for every E [k] all nodes at level of T labeled by X; which shattered by C. Now, let V y and X X for some k N. Then, define Sh X2,,., Xa), V)) the number of non-empty sub- uub-sequences of X that are full shattered by V.
The first observation
E X is full shattered by C C, then the size X should be smaller than +1. Next, clearly, X E X does not have any non-empty sub-sequence that full shattered by V C, the projection of on X is unique.
Now, proceed with the proof of the Lemma. Fix T N. We run List Shattering Algorithm 2 with input Q, T, and X E X as the initial sequence of instances chosen by the adversary. Based the previous paragraph, we know Sh (X.L.V.V) < Ei < (eT)². Whenever we make a mistake, there are some cases to consider. (1) For each sub-sequence full shattered by all I of the version spaces related the labels in the predicted list, and by the yt version space, there another full shattered sequence being removed. In particular, the one that has the predicted point its root and the other L + trees its sub-trees. shattered by at most I. 1 of the top I. labels. Since those T. labels all shattered at least as many sub-sequences as yı, that
(2) The remaining full shattered sub-sequences by the y/ version space can be full
should mean the maximum number of sub-sequences that can be full shattered by the ye version space is } fraction
of the total full shattered sub-sequences. As a result, after at most m > In(44) 1n(1+t) mistakes, where ( we have no
full shattered sub-sequences. Therefore, we can get M* T) E o o log (2F) E log(T).

---

A Trichotomy for List Transductive Online Learning
B. Agnostic Proofs
B.1. Lower Bound
We start by proving the lower bound for the linear case. Furthermore, the proof of the following Lemma uses the main idea in the lower bound proof of the work of (Moran et al., 2023).
Lemma B.1. Let Q (X,T. be instance of the list transductive online learning framework. Assume that D(2) = cc. Then, Q is not agnostic learnable in the list transductive online learning framework.
Proof. First of all, note that the realizable setting is particular case of the agnostic setting. Fix T E N. Let T be a (L + 1)-Littlestone tree witnessing D(Q) = 'T Note that such a tree should exist as D(Ω) = cc. Based on Definition 2.14, this tree should have depth T as well. Also, at each level of TT all nodes are labeled by the same instance from X. In addition, children of all nodes are labeled by distinct labels from V. Let A be any randomized list transductive online learning rule. Now, we will build an adversarial strategy against A using T. To do so, first present T instances T levels of T in order to the learner before starting the game. Furthermore, special root-to-leaf path in TT Receive the first set of labels of size I. predicted by the learner. As we have T, + 1 edges for the root node of T labeled by distinct labels from y' there exists at least one of them, which is labeled by a label that is not in the received set. We output a random label from those labels according to the uniform distribution. Moreover, we will continue this construction of the adversarial strategy based on T. Notice that, as is shattered by C, there exists a concept in C, which is consistent with the root-to-leaf path that we used. So, we are in the realizable setting. In addition, notice that our choices of labels are completely independent of the learner's prediction. So, A makes mistake every 1
will continue to make this strategy based
point with probability of at least
I. 11 Since we are able to construct an adversarial strategy for an arbitrary randomized
list transductive online learning rule A, we conclude any randomized rule has at least L+1
expected regret. It means that Q is not agnostic learnable in the list transductive online learning framework. This finishes the proof.
B.2. Upper Bound
Finally, we turn our attention to proving the VT x log(T) upper bound. Moreover, the proof of the following lemma represents the main contribution of this section, relying on the shattering technique from the realizable part, as well as the proof technique of (Hanneke al., 2023a).
We note that Algorithm 2 can be made conservative, that is, only adding an running the line 5 if it is mistake. is not hard to see that we can get the same guarantee in A.3. Also, we note that Algorithm can be made conservative, that is, only adding running the line 5 if it is mistake. It is not hard to see that can get the same guarantee as in Lemma A.
Lemma B.2. Let Q = (x, L,L. C) be an instance of the list transductive online learning framework. Assume that D = d < oo for some inM. Then, Q agnostic learnable the list transductive online learning framework.
Proof. Fix T E N. Based on the results section we know that there exists a conservative version of Algorithm 2, which can give us (2, e o (Ld ( (TF) E log(T). Let us call the best concept in C in the definition of regret for a given S (X x yaTT sequence played by the adversary c*. Denote by R sub-sequence of indices that c* is correct on. Indeed, if we run the mentioned algorithm only on these point, we make at most O [ log (iF) number of mistakes on indices J C R In fact, we only need to update our algorithm on those points. Furthermore, between all experts updating on every possible sub-sequence of size most o (L (2F) of T, one of them is the one that is updating on exactly on & Lugosi, 2006), we can get regret
J Thus, based on the celebrated prediction with expert advise algorithm of:
TT
eT
L D(@) log
log ((@)
(()
L
D(@) log ( (
We note that our experts are at most different on R* with c* on oLdlog (tt) number of instances.
Importantly, the same technique can be used to overcome the issue of infinite label space in the work of (Moran et al., 2023),
thus answering their open question.
12

---

A Trichotomy for List Transductive Online Learning
C. Examples
This section provides three examples of instances within the list transductive online learning framework, revealing the separations between related learnability definitions.
L-DS Dimension
Definition C.1 (i-neighbour), Let fig E Dd for some non-empty set y and some E N. For every i E [d], we say that f and 9 are i-neighbours fi + 9s and V)E[4-(() (1) fn = 93.
Definition C.2 (L-DS Dimension (Charikar& & Pabbaraju, 2023)), Let Q = (X,C, be an instance of the list transductive online learning framework. Let S E 2' be sequence for some d E N. We say that S is L-DS shattered by C, if there exists F C, [F] < co such that for all f E {g g E )", Eger ViEld] 9: = f(;)) and for all i E [d], f has at least L number of i-neighbor. The L-DS dimension of Q, denoted (Q), is the maximal size of sequence S E x² for some d N that is L-DS shattered by C.
C.2. Main Results on Learnability Separations
Our first result in this section implies separation between realizable/agnostic multiclass transductive online learnability (Hanneke et al., 2024b) and realizable/agnosti list transductive online learnability.
Proposition C.3. For every L N, there exists an instance of the list transductive online learning framework Q (X, L))C) and another instance of the list transductive online learning framework Q' (X, + 1.3.C) such that D(2) = co and ((2))= O.
Proof. Fix LE N. Let T be an infinite depth perfect rooted (L + 1)-rry tree Definition 2.9. The definition of such a tree is similar to Definition 1.7 in the work of (Bousquet et al., 2021). For every i E N, label all nodes at the level 1 of T with i - 1. Also, for every node in TT label all its children with distinct elements from [T. + 1]. Let X = {0) U N. In addition, let y = [L + 1]. Further, define C E )xx so that it only contains all functions consistent with a root-to-leaf path of T. Now, define Q = (x, L, C). Also, define Q' == (x, L + 1, 1,,, Based on the definition of T and Q. it is clear that D(2)= = 00. Additionally, notice that for every x E X. the size of {y Beec = c(x)} is bounded above by L + 1. As a result, B(Q²)= = 0. This finishes the proof.
Our second result in this section implies a separation between realizable/agnostic list PAC learnability (Charikar & Pabbaraju, 2023) and realizable/agnostic list transductive online learnability.
Proposition C.4. For every L E N. there exists an instance of the list transductive online learning framework Q (X, C) such that D(Q)= = oo and (S( =
Proof. Fix L E N. Let T be an infinite depth perfect rooted (L + aarr tree Definition 2.9. The definition of such tree is similar to Definition 1.7 in the work of (Bousquet et al., 2021). For every i E N. label all nodes at the level i i of T with i i- 1. Also, label all edges of TT with distinct elements of N. Let X' = {0) U N. In addition, let y = N. Further, define y such that it only contains all functions consistent with a root-to-leaf path of T. Now, define Q = (X, L, 3. C). Based on the definition of T and Q, is clear that D(Q) = Je. Subsequently, we prove that DS(@) = 1. In particular, we prove this mainly by contradiction. Assume DS Q) 2. Thus, there exist (z1. witnessing that DS(C) = 2. Without loss of generality, we assume that æ1 is above 22 in TT Based the fact that the edges of T are labeled with distinct elements of y, we can conclude that every pair of concepts from (cI,02) E C2 such that en (x2) C2 (2(22) should have be equivalent on I1, meaning that ci (æ1) = C2 (z1) as well. So, we cannot even have one neighbor. This is a contradiction. Therefore, DS(C) < 2. It is easy to see that the root node of T is L-DS shattered by C. As a result, DS( Q) = 1. This finishes the proof.
X' of size 2 and F S C, [ < co
Notably, one can also show that for every instance of the list transductive online learning framework Q = (,,,C.))) we always have DS(@)= < D(@).
Our third result in this section implics a separation between realizable/agnostic list online learnability (Moran et al., 2023) and realizable/agnostic list transductive online learnability.
13

---

A Trichotomy for List Transductive Online Learning
Proposition C.S. For every L N, there exists an instance of the list transductive online learning framework Q (X, C) such that (())= oc and B(2) < 2
Proof. Fix I. E N. Let be an infinite depth perfect rottdd (T, + 1)-rry tree Definition 2.9. The definition of such tree is similar to Definition 1.7 in the work of (Bousquet al., 2021). First, label all nodes of T with distinct elements of N. Also, for every node in T, label all of its children with distinct elements from [L + 11. Let X' = N. In addition, let ) = R. Further, define C E yx such that it only contains all functions consistent with root-to-leaf path of T with special property. In particular, each of these functions equals to a unique element of R on all instances outside its associated root-to-leaf path. Now, define Q = (X,,,)))). Based on the definition of T and @ it is clear that L(Q) = oo. Subsequently, we prove that B(Q) 2.
To prove this, we show that for every T E N, we have: (2, S So, we can then conclude that B(Q) 2. To why, just notice that we can prove a lower bound based B(Q). In particular, if ( > 2, we can always force at least three number of mistakes to any deterministic list transductive online learning rule for large enough T.
This part of the proof is essentially identical to the similar part in the proof of Proposition 11 in the work of (Hanneke et al., 2024b). We include it for the sake of completeness. Fix T E Let SXT be the sequence chosen by the adversary at the beginning of the game. Also, let e* E C be the target concept chosen by the adversary. Further, let u be the root-to-leaf path in T associated with the concept c*. In addition, for every E [7]. let U; be a root-to-leaf path in T containing first i members of S, if it exists. Finally, let i* be the smallest positive integer such that U,. does not exist. If i* itself does not exist, let i = T 1. Our algorithm predicts according to the [T. - 1] labels associated with the path 0 for the first i* points in S. Moreover, if the adversary ever reveals a unique label, we use its corresponding c E C' to make predictions in all future rounds. For the 'h member of S, if it exists, we predict arbitrarily. To see that this algorithm makes at most 2 mistakes, we consider two cases. (1) if = T + 1, then our algorithm makes at most one mistake. In fact, our algorithm makes a mistake: (a) if the adversary switches the label from something in [T. + 1] to a unique label corresponding to the target concept c*, (b) perhaps on the last instance. (2) Otherwise, the algorithm makes most two mistakes; the first mistake can be round i* 1, and the second mistake can be on round i*, after which the true c* is known to the leamer from its unique label. Indeed, if the adversary switches the label from [L + 1] to a unique label corresponding to the target concept c" before round i* - 1, we only make one mistake. In fact, we just showed that even by using an algorithm having list size of one, we can do so. This completes the proof.
Notably, one can also show that for every instance of the list transductive online learning framework Q = (X we always have B(Q)= < L(Q).
14


Reviews:
[{"review_id": "zEQxaxbeiX", "reviewer": "Reviewer_WvaW", "summary": "They studied the problem of list transductive online learning. In the realizable setting, they show a trichotomy of possible rates of the minimax number of mistakes.\nIn the agnostic setting, they show a \\tilde{O}(\\sqrt{T}) regret bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. In particular, we thank the reviewer for taking the time to verify that our work is technically sound. We are delighted that the reviewer found that our paper contains novel applications of the techniques in the literature, and moreover mentioned that our paper is written nicely. Below, we address the questions provided by the reviewer.\n\n- We assume that each concept from the concept class assigns one label from the label space to an instance from the instance space.\n- In Definition 2.10, we just assign symbols to nodes and edges of a Perfect Rooted L-ary Tree from two abstract spaces.\n- In Definition 2.11, we just replace abstract spaces in Definition 2.10 with instance space and label space. Moreover, we may apply the property of having distinct labels corresponding to all outgoing edges of any given node in a tree in the definitions of dimensions, such as Definition 2.13. Notably, as you mentioned, we do not require to have |Y| = |L + 1|.\n- Definition 2.14 is the Definition of Level constraint (L + 1)-Littlestone dimension. Here, there are two main differences with the Definition of standard Littlestone dimension. First, the witnessing tree is (L+ 1)-ary tree instead of 2-ary tree. Second, all nodes at the same level of the witnessing tree should correspond to a single instance from the instance space.\n- In a tree witnessing the Level-constrained (L + 1)-Branching Dimension, we may have outgoing edges of a node corresponding to the same label. This contrasts a tree witnessing the (L + 1)-Littlestone Dimension that all outgoing edges of any given node should correspond to unique labels.\n- We appreciate the reviewer's feedback regarding the improvement of the presentation of our paper. We will change the notations in section 2.3 to clarify the definitions in the camera-ready version. Also, we will add a figure to clarify distinction between different combinatorial structures that we have in the camera-ready version.\n- Let us answer your question when L + 1 = 2 for simplicity. Then, the extension for an arbitrary L is straightforward. Intuitively, suppose you have two level constraint trees of the same depth. If you want to join these two trees by adding a root node and still keeping the level constraint property for the new tree, your new tree can have at most 2 times the depth of those two initial trees.", "claims_and_evidence": "Theoretical paper, and they have proved everything theoretically.", "methods_and_evaluation_criteria": "yes, theoretical paper", "theoretical_claims": "I checked the proofs in the main body and they do make sense.", "experimental_designs_or_analyses": "No experiments", "relation_to_broader_scientific_literature": "They study the problem of list transductive online learning. List learning studied both experimentally and theoretically. It is relevant to multi-class classification and conformal prediction.", "essential_references_not_discussed": "I cannot think of any missing references.", "other_strengths_and_weaknesses": "The paper is written nicely (I was confused in some parts and asked my question below), and they solved multiple open problems in earlier papers. I am not too surprised by the techniques, most of them are standard techniques in online learning literature I think (I did not go over the appendix), but the application is novel .", "other_comments_or_suggestions": "Check the questions.", "questions_for_authors": "Questions:\n\nFor the concepts in the concept class, do you assume that they give one label y_i to each example x_i or a list of labels?\n\nDef 2.10. I am confused here. \nusually in L trees each root-leaf path is labeled by a hypothsis, here each node is labeled\nby a hypothesis, why is it the case here?\n\nDef 2.11, usually in Ltree, each branch is labeled by a distinct y, here I don't think you mean that |Y|=L+1(and so all possible labeles are used in different branches), can you clarify on this?\n\n\nDef 2.14, this is exactly Littlestone tree, no? Or is it possible that |Y|>L+1 and that's the difference with Littlestone tree?\n\nDef 2.15, So a level constrained (L+1)-branching D in some sense is a subtree of a \n(L+1)-Littlestone tree.\n\nIn section 2.3, I was very confused, perhaps you can add some pictures and explain which one is littlestone tree and for the ones that are not a standard littlestone tree what is the crucial difference that the reader needs to pay attention to.\n\nLine 385-386 (the first line in this column), can you explain why (L+1) is being multiplied?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZqP2yvDpTi", "reviewer": "Reviewer_yqeS", "summary": "This paper tackles the combined problem of Moran et al.'s (2023) *list online classification* and Hanneke et al's (2024) *transductive online learning* (where the sequence of instance points is given in advance). Two natural variants of Littlestone dimension are proposed combining the (L+1)-Littlestone trees of Moran et al (2023) with the level-contrained (/-branching) trees of Hanneke et al. (2024). \nThese two combinatorial dimensions exactly define the 3 possible mistake rates in the realizable setting (constant, logarithmic, and linear) and the first determines whether sublinear regret is possible in the agnostic setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. In particular, we thank the reviewer for taking the time to verify that the work is technically correct. We are delighted that the reviewer found that our paper is interesting for the theoretical ICML community. We will make sure to correct the typos and incorporate minor suggestions mentioned by the reviewer for the camera-ready version. Below, we address a question provided by the reviewer about the assumption of $|y^{\\star}| < |x^{\\star}|$.\n\n- No. In fact, we use that notation to formally define Deterministic List Transductive Online Learning Rules. In particular, a Deterministic List Transductive Online Learning Rule is a mapping that maps each finite sequence of instances and a finite sequence of labels with a size *smaller* than the size of the sequence of instances to a set of size L of labels. We will change the notations in this part to clarify the definitions in the camera-ready version.", "claims_and_evidence": "Correct proofs.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "All proofs are pretty standard and correct. See below for more comments.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "All good.", "essential_references_not_discussed": "All good.", "other_strengths_and_weaknesses": "Please cite Moran et al 2023 in the Def. 2.11-2.13, otherwise it might seem like you came up with these notions. Similarly maybe cite Hanneke et al (2024) for Def. 2.14, 2.15 and say that you extend their notions.", "other_comments_or_suggestions": "This paper continues an interesting line of work on variants of online classification. While the proof techniques are rather standard (mostly a natural combination of Hanneke et al (2024) and Moran et al (2023)), this paper should be interesting for the theoretical ICML community. While the paper is rather incremental, I vote for acceptance.\n\n\nMinor comments:\n\nSome notation is not defined. E.g. $\\Pi(..)$ presumably for distributions. Also $\\mathcal{A}$ is used for subsets of labels (in the def. of $\\mathcal{Y}_L$ and as the set of all deterministic algorithms.\n\nAny reason you use $\\mathfrak{s}$? Typically $\\mathfrak{s}$ denotes the star number in such contexts.\n\nTypo: A $L$-ary --> An\n\nConsider adding an $L$ or $L+1$ index to $D(\\mathcal{Q})$ and $D(\\mathcal{Q})$ to make the dependence clearer (as in Moran et al (2023)? Similarly $L(\\mathcal{Q})$ could be misleading as $L$ is also the list size. Why not e.g. $k$ for list size (like in some other papers on list learning)?", "questions_for_authors": "Is the assumption of $|y^\\star|<|x^\\star|$ explicitly used anywhere? It's not a big restriction but seems unnecessary. E.g., why would you demand $y_1=y_2$ for $T=2$. Even in cases with $|y^\\star|=|x^\\star|$ you can obviously still \"learn\", e.g., if only one hypothesis is consistent to a prefix of the sequence, the learner can predict everything following the prefix correctly, even if each $x_i$ has its own new label.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cbApizrJqu", "reviewer": "Reviewer_9YMd", "summary": "The authors provide theoretical analysis on the list transductive online learning problem in this paper. They first establish upper and lower bounds for the minimax number of mistakes in the realized setting, by which they solve a open problem raised from previous work. Then, in the agnostic setting, they provide an upper bound for the the minimax expected regret and solve another open problem. The key contribution in their proof is introducing two new combinatorial complexity dimensions named Level-constrained Littlestone dimension and Level-constrained Branching dimension. Finally, they raise the issue of eliminating factors from their upper bound in the realizable setting and left it for future work.\n\n***\n**Update after Rebuttal**\n\nThanks the authors for their responses. I encourage the authors to include the discussions about these related works in the final version. Currently, I have no other concerns. I have raised my score to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. We are delighted that the reviewer found that our paper contains novel techniques and novel combinatorial complexity measures. We will make sure to correct the typos and incorporate minor suggestions mentioned by the reviewer for the camera-ready version. Below, we address major comments provided by the reviewer.\n\n- We appreciate the reviewer's feedback regarding improvement of the presentation of our paper. We will change notations in section 2.3 to clarify the definitions in the camera-ready version. Also, we will add a figure to clarify distinction between different combinatorial structures that we have in the camera-ready version.\n- While there is a conceptual connection between transductive online learning and traditional transductive learning, as noted by Hanneke et al., 2023, there is an important distinction. Generally speaking, in online learning, we make no probabilistic assumptions regarding the data-generating mechanism. However, in traditional transductive statistical learning, we usually assume that we have an underlying data distribution, or that the learner observes labels for a uniform-random subsample of the data (as opposed to predicting online in the order given).\n- As we attempted to explain in the final paragraph of page 3, a technique inspired directly by the Halving algorithm does not yield a logarithmic  \\log(T)  upper bound in our setting, even when the label space is finite. This stands in contrast to the multiclass setting, where this technique is effective when the label space is finite Hanneke et al., 2023. The main novelty in our proof of the trichotomy result lies in extending the shattering technique of Hanneke et al., 2024 to the list setting. In particular, a key and novel component of our algorithm is a new notion of shattering that exploits the sequential nature of list transductive online learning. This result appears fully in the appendix, which serves as the main technical contribution of this work. On the other hand, the solution to the second open problem follows, more or less, from a recent idea in the field.\n\nWe hope this rebuttal has clarified the novelty of our contribution beyond the introduction of new combinatorial complexity dimensions.", "claims_and_evidence": "All claims in this paper are theoretic results on the minimax number of mistakes in the realized setting and the minimax expected regret in the agnostic setting. They are supported by rigorous proofs.", "methods_and_evaluation_criteria": "The authors do not conduct any experiments in this work.", "theoretical_claims": "I roughly browsed through the entire proof process in this paper. Since I am not so familiar with the theory of online learning, I find it difficult to accurately determine whether there are issues in the proof.", "experimental_designs_or_analyses": "The authors do not conduct any experiments in this work.", "relation_to_broader_scientific_literature": "The key contribution of this work is introducing some novel combinatorial complexity dimensions named Level-constrained Littlestone dimension and Level-constrained Branching dimension, which could bring new insights for both online learning community and transductive learning community, particularly for those who working on theory. Since transducitve learning setting is also widely adopted in graph learning area, for example in the node classification task, this work could also bring some insights to graph learning community.", "essential_references_not_discussed": "From my view, I could not find related works that are essential to understanding the key contributions of the paper, but are not currently cited or discussed in the paper.", "other_strengths_and_weaknesses": "The strengths of this paper is introducing novel techniques to establish theoretic bounds for the minimax number of mistakes in the realized setting and the minimax expected regret in the agnostic setting, by which two open problems are solved. The results in this paper provide learning guarantee for model in the transducitve online setting. The weakness in this paper is that the presentation needs further improvement. I encourage the authors to provide more explanations for some key concepts, such as the Level-constrained Littlestone dimension and the Level-constrained Branching dimension, by giving some examples or visualized illustrations. Besides, it would be better to place Section 1.2 after Section 2, since the readers need some background to understand the meaning of notations appear in Section 1.2.", "other_comments_or_suggestions": "The letter $T$ in the article is in regular font in some places (Definition 2.5), while in others it is italicized (Theorem 1,1). It's better to unify them.", "questions_for_authors": "1. Could you elucidate the difference between the transductive online elarning and the traditional transductive learning introduced in [1,2,3,4,5]?\n2. In addition to introducing new combinatorial complexity dimensions, is there other novelty in your proof compared with previous studies? Since you claim that two open problems are solved, why can't the previous proof techniques solve these problems, while your proof can address them?\n\n[1] Estimation of Dependences Based on Empirical Data: Empirical Inference Science. Vladimir Vapnik,1982.\n\n[2] Statistical Learning Theory. Vladimir Vapnik, 1998.\n\n[3] PAC-Bayesian supervised classification: The thermodynamics of statistical learning. Olivier Catoni, 2007.\n\n[4] Combining PAC-Bayesian and generic chaining bounds. Jean-Yves Audibert and Olivier Bousquet, JMLR 2007.\n\n[5] Explicit learning curves for transduction and application to clustering and compression algorithms. Derbeko et al., JAIR 2004.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lDRsFJWBT1", "reviewer": "Reviewer_4R8d", "summary": "The paper studies the problem called list transductive online learning. That is the learner is given a sequence of instance $ (x_1,\\ldots,x_T)\\in\\mathcal{X}$. In $ T $ round the adversary and the learner then does the following. The adversary picks an outcome $ y_{t}\\in \\mathcal{Y}.$ The learner is then asked to predict the outcome of $ x_{t},$ by outputing a list $ A_{t}\\subseteq\\mathcal{Y} $  of size $|A|= L.$ The learner announces the list $ A_{T} $.  If the learner output a list $ A $  such that $ y_{t}\\not\\in A_{t},$ then learner incurs an error.\n    The problem is both studied in the realizable case: there exists some hypothesis class $ \\mathcal{C}\\subset \\mathcal{Y}^{\\mathcal{X}} $ such that for the sequence $ (x_{1},y_{1}),\\ldots,(x_{T},y_{T}) $ there exists $ c\\in \\mathcal{C} $ such that for every $ i\\in[T] $ $ x_{1}=c(y_{1}),$ where the algorithm performance is measured in terms of how many mistakes it makes over the $ T $ round. \n    and the agnostic case, where there is no assumption on the relation between $ x_{i},y_{i} $ and $ \\mathcal{C},$ and the algorithms performance is measured in terms of the regret the difference between how many mistakes the algorithm makes and how many mistakes the best hypothesis in $ \\mathcal{C} $ makes. \n    The paper uses $ Q=(\\mathcal{X},L,\\mathcal{Y},\\mathcal{C}) $ as a description for an instance of a list transductive online learning problem.\n    Given such a $Q$, the paper considers two complexity measures.\n    The first complexity measure is the level constrained $(L+1)$-little stone dimension, the depth of the largest percept balanced $ (L+1) $ tree, with nodes labelled by instances $ x\\in \\mathcal{X} $, where for each level of the tree the nodes in that layer has the same value $ x $ and each of the nodes $ (L+1) $ edges connecting it to its children, are labelled with different values in $ \\mathcal{Y},$ furthermore the tree is realizable by $ \\mathcal{C},$ that is each root to leaf path can be realized by and hypothesis in $ \\mathcal{C} .$ This is denoted $ D(Q) $ \n    The second complexity measure is the level constrained $(L+1)$-branching dimension, which is the largest natural number $ d $ for which there exists a perfect balanced $ L+1 $ tree(realizable by $ C $), with all the levels of the tree having nodes labelled by the same $ x\\in \\mathcal{X},$ and for each root to leaf path contains $ d $ instance $ x\\in \\mathcal{X},$ where each such instance's $ L+1$ edges connecting it to it's children are labelled with distinct values in $ \\mathcal{Y}.$ This dimension is denoted $ B(Q).$\n    Where the paper note that $D(Q)\\leq B(Q).$          \n    The paper shows that the  2 complexity measures characterizes the learnability of list transductive online learning, in the realizable case.\n    More specifically the paper shows that if both of the dimensions are unbounded then for any learning algorithm there exists and instance where the learner get $ \\Omega(T) $- mistakes. \n    If $ B(Q) $ is  unbounded, and $ D(Q) $ is  bounded then the there exists an learning algorithm making at most $ O(log(T)) $ mistakes and for any learning algorithm there exists an instance where the learning algorithm makes $ \\Omega(log(T)) $-mistakes. \n    If $ B(Q) $ is bounded then the learning algorithm makes $ O(1) $-mistakes.\n    In the agnostic setting the paper shows that the regret is sub linear if $ D(Q) $ is  bounded, and linear if $ D(Q) $  is  unbounded.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really thank the reviewer for dedicating their time to assess our work. In particular, we really thank the reviewer for taking the time to carefully read our paper. We are delighted that the reviewer found that our contribution is original, our paper is well written, enjoyable to read, and contains an interesting open problem. We will make sure to correct the typos and incorporate minor suggestions mentioned by the reviewer for the camera-ready version. Below, we address major comments provided by the reviewer.\n\n- Your understanding of our lower bound proofs is fully correct.\n- As you mentioned, the results of Moran et al., 2023 do not imply the results in this paper. We have an example to show this in appendix C. In fact, we mentioned that example in the last paragraph of the first column of page 2.\n- As you mentioned, list learning originates from the work of Brukhim et al., 2022.\n- Regarding measurability issues, following the work of [1], we only require a sigma-algebra so that every subset of $\\mathcal{Y}$ with cardinality $\\mathrm{L}$ is measurable. Notably, following the work of [1], this assumption is enough for the agnostic setting.\n- Regarding our $\\log(T)$ lower bound proof, each of the trees that we want to join can witness B(Q) = d. In fact, each of them can do so even in the restricted version space based on the label of its corresponding outgoing edge of the root node. As a result, they are level-constraint (nodes of each level are assigned to a fixed instance from the instance space), and so on. Now, the main observation is that in trees witnessing the level-constraint branching dimension being equal to some k, we do not require all outgoing edges of all nodes to correspond to distinct labels. Therefore, in each of those trees, we may add a level, correspond all of its nodes to an instance from an instance space, and label all outgoing edges of it with the same label. Note that this modification still leads to a tree witnessing B(Q) = d in the restricted version space. Thus, we can make all trees have exactly similar levels by paying the number of levels less than or equal to $L \\times$ maximum initial depth of them. That is why we have a factor of list size here.\n- The finiteness of B(Q) would imply a *slightly* improved upper bound in the agnostic setting. This is because, in the agnostic setting, we have $\\sqrt{T}$ factor, so a logarithmic improvement that can be achieved using the finiteness of B(Q) is not a big deal.\n- Regarding the computational complexity of our algorithms, we note that our algorithms require calculating the (L + 1)-level-constrained Littlestone dimension or (L + 1)-level-constrained branching dimension for concept classes. In the special case of the binary classification, the (L + 1)-level-constrained Littlestone dimension equals the VC dimension. Moreover, we know the calculation of the VC dimension is computationally hard for general concept classes. Thus, our algorithms are not efficient for general concept classes. However, this is an issue for both PAC and adversarial online learning, even for binary classification. For instance, in the case of adversarial online learning, SOA involves computing the Littlestone dimension of concept classes defined by the online learner in the course of its interaction with the adversary, which is challenging computation, even when the concept class and the set of features are finite [2]. Notably, no efficient algorithm can achieve finite mistake bounds for general Littlestone classes [3].\n\nWe hope this rebuttal has clarified your questions.\n\nFinally, once again, we thank the reviewer for taking the time to carefully read our paper and provide many helpful suggestions.\n\n\n[1] S. Hanneke, S. Moran, V. Raman, U. Subedi, A. Tewari. Multiclass Online Learning and Uniform Convergence. In Proceedings of the 36th Conference on Learning Theory, 2023.\n\n[2] P.Manurangsi, A. Rubinstein. Inapproximability of VC dimension and littlestone’s dimension. 30th Conference on Learning Theory, 2017.\n\n[3] A. Assos, I. Attias, Y. Dagan, C.Daskalakis, M. K. Fishelson. Online learning and solving infinite games with an erm oracle. 36th Conference on Learning Theory, 2023.", "claims_and_evidence": "Q: Are the claims made in the submission supported by clear and convincing evidence? If not, which claims are problematic and why?\n        \nA: The paper contains proofs for the lower bounds of the realizable case in the main of the paper. The paper claims that the remaining proofs are devoted to the appendix, which i have not checked.", "methods_and_evaluation_criteria": "Q: Do proposed methods and/or evaluation criteria (e.g., benchmark datasets) make sense for the problem or application at hand?\n    \nA: I dont see how to answer the above for this theoretical article, let me know if im mistaking and give me and example how to evaluate this question, and I will do that.", "theoretical_claims": "Q: Did you check the correctness of any proofs for theoretical claims? Please specify which ones, and discuss any issues.\n\nA: I read the proofs of the main, lower bounds for the realizable, but could have missed something while reading them. Here is my understanding of the proofs, I encourage the authors to correct my understanding. If the $ D(Q) $ dimension is infinite, then for a given algorithm $A$ the lower bound follows from there existing a $L+1$ perfectly balance tree, with depth $ T $ , realizable by $ C $, on each level the nodes are labelled by the same instance $ x\\in \\mathcal{X},$ and the $L+1$ edges to the nodes children have different labels. Thus when the learner is presented with the instance $ x_{i} $  on level $ i,$ and outputs a list of size $ L,$ the adversary can pick at least one branch of the tree where the learner mispredicts, since the tree have depth $ T $ the learner makes an mistake in each round. Since $ D(Q) $ is infinite, for any $ T $ such a tree can be constructed.   \n    In the proof of the lower bound of $ B(Q)$ being infinite, the guaranteed is that for any $ d $ there exists a realizable $ L+1 $ perfectly balanced tree, with the nodes on each level labelled by the same $ x\\in \\mathcal{X},$ and for any root to leaf path contains $ d $ nodes which edges to their children are label with distinct values from $\\mathcal{Y}.$ Thus presenting the learner with the sequence of instance from each of the levels of the tree $ x_1,\\ldots $, the adversary will again be able to make the learner make $ d $ mistakes, by on the instances where there are $ L+1 $ distinct labelled edges to children choosing the one not outputted by the learner. However since the above guarantee do not say anything about the depth of the tree and when these $d$ distinct labels occur in the sequences, it is not given that one can find a sequence of length $ T $ with this property. Thus the paper presents a way of compressing such a tree in to a subtree of depth at most $((L+1)^d-1)/L,$ while still having the above property of each root to leaf path  having $d$ nodes with distinct values on the edges to their $ L+1 $ children. Now solving $ T= ((L+1)^d-1)/L$ implies $ d= \\Theta(\\log(T))$(omitting dependencies on $ L $ ), thus the adversary can generate this tree of depth at most $ T $ and make the learner make $ \\Omega(\\log(T)) $  mistakes.", "experimental_designs_or_analyses": "Q: Did you check the soundness/validity of any experimental designs or analyses? Please specify which ones, and discuss any issues.\n\nA: I dont see how to answer the above for this theoretical article, let me know if im mistaking and give me and example how to evaluate this question, and I will do that.", "relation_to_broader_scientific_literature": "Be specific in terms of prior related findings/results/ideas/etc.\n    \\item A: Im not that well versed in this literature - but the cited literature seemed relevant. Specifically the paper: 1) Relates to work by for instance (Charikarm, Pabbaraju,\n    2023), which studies list learning in the PAC-setup which allows, and explains how the dimension studied in that work being finite is not sufficient for characterize transductive online list learning. 2) Explains the relation to online learning(uncertainty on both labels and instances) and how that setting have been studied in list (Moran et al., 2023),  and how it previous (initiated by  (Ben-David et al., 1997)) have been studied how removing the uncertainty of the instance (so knowing the sequence in advance).(I assume that the results of (Moran et al., 2023) does not imply the results in this paper, if this is the case i encourage the authors to correct me.)  \n    I had one question do list learning originates from the work of Brukhim et al 2022 else I think it would be good to cite the paper originally introducing it, my apologies to the authors if I missed it.", "essential_references_not_discussed": "Except for might adding a reference about where list learnability originates from i don't see any missing references.", "other_strengths_and_weaknesses": "Strengths: I would say that the paper is well written. From my understanding of the paper being the first to study this setting of list learning it also seems original. The paper combines ideas from previous work. I enjoyed the paper. The paper also leaves an interesting question at the end of the article about whether the lists could be allowed to be unbounded, allowing for instance to output intervals of a certain size instead.", "other_comments_or_suggestions": "Congratulations on your paper. The following is the notes I took will reading the article.\n\nLine 133 namely $(x_1, x_2, . . . , x_T)$ and reveals it to the learner.\n\n Line 152 was Q, defined be mentioned here?\n\n Remark/note I really liked the open question in the end of the article discussing the possibility of list learning with infinite size - to this end could it make since to include the parameters $ L $ and $ d $ in the statement of theorem 3.1., such that the reader in general could think of how to improve the dependencies in the bound?(I would still keep theorem 1.1 informal) \n\n LIne 184 should it be L(Q) and not LD(Q)?\n\n Line 200 second column why $ -\\infty $ included in N?\n \n  Line 235-238: What about measurability in the agnostic setting? Also line 307-311: Lemma 4.1 in Cesa-Bianchi is from my understanding for finite label spaces would this course any measurability problems.\n\n  248: Initially, an adversary chooses a sequence of T instances X $\\in$ X T and reveals it to the learner.\n \n Definition 2.2 was $ A^* $ defined prior?\n\n265-269 second column: Maybe adding the reference to Lemma 4.1 in (Cesa-Bianchi \n    Lugosi, 2006), here also, if it also applies in this case, would help the reader. \n\n326-329 second column: and every root\n    to leaf path contains at least d nodes with edges to its children labeled by distinct elements of Y. And the tree is shattered by C.\n\n line 538: should it be $ V $ in the defintion of $ V_{x\\rightarrow y}.$", "questions_for_authors": "1: Line 378-380 second column: How is the tree join such that realizability, nodes on same level has the same label, and is a subset of the nodes in any tree witnessing $ B(Q)=d $? \n\n2: Agnostic and realizable: $ D(Q) $ also characterizes learnability in the realizable setting, if finite the mistake bound is sub-linear in $ T $ and if infinite linear in $ T,$(so learnable if and only $ D(Q)<\\infty $ ) however the learning rates is more fine grainedly characterized depending on the finiteness of $ B(Q),$ Theorem 3.1. For the agnostic setting theorem 4.1 the statement is only about learnability which again is characterized by $ D(Q) $ bounded or unbounded. Do finiteness of $ B(Q) $ in the agnostic setting also give a more fine grained characterization of the learning rate?\n\n3: Is it correctly understood that the algorithm 1 and 2, is not nessarily efficent since they have to consider all versionspace for labels in $ \\mathcal{Y} $, which might be infinite?\n\nThanks for the answers to my questions. I would like to keep my score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the theory behind a specific type of online learning called "list transductive online learning". Its main achievement is figuring out exactly how well algorithms can possibly perform in this setting. The authors introduce two new ways to measure the problem's difficulty (using special "dimensions") and show these measures perfectly predict the best possible learning rates in terms of mistakes or regret. This key result solves open questions left by earlier papers and fully characterizes the learning problem. Reviewers agreed that these theoretical results are strong and important contributions. The paper was generally considered well-written.

Overall, the assessment is positive, leaning towards acceptance. The paper is recognized for solving known problems and clearly defining the learning limits for this setting, even though the techniques might not be entirely new and the presentation could be improved for clarity.
Decision: Accept (poster)