A Trichotomy for Transductive Online Learning
Authors: Steve Hanneke
Shay Moran
Jonathan Shafer
Venue: NeurIPS 2023 poster (2023)
Keywords: Online Learning
Transductive Online Learning
Offline Learning
Mistake Bound
TL;DR: A qualitative trichotomy and some quantitative mistakes bounds relating the transductive online learning setting to known combinatorial dimensions.

Abstract: We present new upper and lower bounds on the number of learner mistakes in the `transductive' online learning setting of Ben-David, Kushilevitz and Mansour (1997).
    This setting is similar to standard online learning, except that the adversary fixes a sequence of instances $x_1,\dots,x_n$ to be labeled at the start of the game, and this sequence is known to the learner.
    Qualitatively, we prove a \emph{trichotomy}, stating that the minimal number of mistakes made by the learner as $n$ grows can take only one of precisely three possible values: $n$, $\Theta\left(\log (n)\right)$, or $\Theta(1)$.
    Furthermore, this behavior is determined by a combination of the VC dimension and the Littlestone dimension.
    Quantitatively, we show a variety of bounds relating the number of mistakes to well-known combinatorial dimensions.
    In particular, we improve the known lower bound on the constant in the $\Theta(1)$ case from $\Omega\left(\sqrt{\log(d)}\right)$ to $\Omega(\log(d))$ where $d$ is the Littlestone dimension.
    Finally, we extend our results to cover multiclass classification and the agnostic setting.

A Trichotomy for Transductive Online Learning
Steve Hanneke
Shay Moran
Department of Computer Science
Faculty of Mathematics, Faculty of Computer Science, and Faculty of Data and Decision Sciences Technion Israel Institute of Technology smoran@technion. ac il
Purdue University
steve. steve. hanneeehhnnneeemaal..cmmm com
Jonathan Shafer
Computer Science Division
UC Berkeley shaferjo@berkeeley .ddu edu
Abstract
We present new upper and lower bounds on the number of learner mistakes in the 'transductive' online learning setting Ben-David, Kushilevitz and Mansour (1997). This setting is similar to standard online learning, except that the adversary fixes sequence of instances Ti..... In be labeled the start of the game, and this sequence is known to the learner. Qualitatively, we prove trichotomy, stating that the minimal number mistakes made by the learner as n grows can take only one of precisely three possible values: n, e (log(n)). or ( Furthermore, this behavior is determined by a combination of the VC dimension and the Littlestone dimension. Quantitatively, we show variety of bounds relating the number of mistakes to well-known combinatorial dimensions. In particular, we improve the known lower bound the constant in the (1)) case from Ω (Vlog(d) ((log(() dd) where d is the Littlestone dimension. Finally, we extend our results to cover multiclass classification and the agnostic setting.
Introduction
In classification tasks like PAC learning and online learning, the learner simultaneously confronts two distinct types of uncertainty: labeling-related uncertainty regarding the best labeling function, and instance-related uncertainty regarding the instances that the learner will be required classify in the future. To gain insight into the role played by each type of uncertainty, researchers have studied modified classification tasks in which the learner faces only one type of uncertainty, while the other type has been removed.
In the context of PAC learning, [BB11] studied a variant of proper PAC learning in which the true labeling function is known to the learner, and only the distribution over the instances is not known. They show bounds on the sample complexity in this setting, which conceptually quantify the instance- related uncertainty. Conversely, labeling related uncertainty is captured by PAC learning with respect to fixed (e.g., uniform) domain distribution [BI91], a setting which has been studied extensively.
In this paper we improve upon the work of [BKM97], who quantified the label-related uncertainty in online learning. They introduced a model of transductive online learning. in which the adversary
[BKM97] call their model 'off-line learning with the worst sequence', but in this paper we opt for 'transductive online learning', a name that has appeared in number of publications, including [KK05, PecO8, CS13, SKS16J. We remark there least two different variants referred to in the litera-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

commits in advance to specific sequence of instances, thereby eliminating the instance-related uncertainty.
1.1 The Transductive Online Learning Model
The model of learning studied in this paper, due to [BKM97], is zero-sum, finite, complete- information, sequential game involving two players, the learner and the adversary. Let E N, let X and Y' be sets, and let H C yxx be a collection of functions called the hypothesis class.
The game proceeds as follows (see Section for further formal definitions). First, the adversary selects arbitrary sequence of instances, Fi....,En E N. Then, for each t 1,...,,7
1. The learner selects a prediction, Ds y.
2. The adversary selects a label, yt E y.
In each step t E [n]. the adversary must select label yt such that the sequence (I1, y1 y.......................... is realizuble by H. meaning that there exists h E H satisfying h(x;)) ys for all i E [t]. The learner's objective is to minimize the quantity
..... (Z ye)
M(A z, h)) 1[t E [m] de * h(x))),
which is the number of mistakes when the learner plays strategy A and the adversary chooses sequence x X and labels consistent with hypothesis & H. We are interested in understanding the value of this game,
sup M M(. heH where A is the set of all learner strategies. Note that neither party can benefit from using randomness, so without loss of generality we consider only deterministic strategies.
M n2) inf sup
AEA =
1.2 A Motivating Example
Transductive predictions of the type studied in this paper appear in many real-world situations, essentially in any case where a party has schedule or a to-do list known in advance of specific tasks that need to be completed in order, and there is some uncertainly as to the precise conditions that will arise in each task. As a concrete example, consider the logistics that the management of an airport faces when scheduling the work of passport-control officers.
An airport knows advance what flights are scheduled for each day. However, does not know in advance exactly how muny passengers will go through passport control each day (because tickets can be booked and cancelled in the last minute, and entire flights can be cancelled, delayed or rerouted, etc.). Each day can be 'regular' (the number of passengers is normal), or it can be 'busy' (more passengers than usual). Correspondingly, each day the airport must decide whether to schedule a 'regular shift' of passport-control officers, an 'extended shift' that contains more officers.
Example 1.1.
If the airport assigns a standard shift for busy day, then passengers experience long lines at passport control, and the airport suffers a loss 1; if the airport assigns an extended shift for a regular day, then it wastes money on excess manpower, and it again experiences loss of 1; If the airport assigns a regular shift to a regular day, or an extended shift to a busy day, then it experiences a loss of
Hence, when the airport schedules its staff, it is essentially attempting to predict for each day whether it will be a regular day or a busy day, using information it knows well in advance about which flights are scheduled for each day. This is precisely a transductive online learning problem.
1.3 Our Contributions
I. Trichotomy. We show the following trichotomy. It shows that the rate at which M n) grows as a function of is determined by the VC dimension and the Littlestone dimension (LD).
ture as 'transductive online learning'. - For example, [SKS16] write of "a transductive setting [BKM97] in which the learner knows the arriving contexts a priori, or, less stringently, knows only the set, but not necessarily the actual sequence or multiplicity with which each context arrives." " That is, in setting, the learner knows the sequence (.',..., 22,) advance,
another setting the learner only knows the set (.1,..., J. One could distinguish between these two settings by calling them respectively. Seeing as the current paper deals exclusively with the sequence transducttee setting, we refer to it herein simply the 'transductive' setting.
and "set-transee tenttsuasduttvee"
2

---

Theorem (Informal Version of Theorem 4.1). Every hypothesis class H. C {0, 1 satisfies precisely one of the following:
1. M(H,n) m) n. This happens VFH) DC.
2. M(H, n)) (llg(nn)). This happens ifVC(H) < oo and LD(H) - xc.
3. M(H, n. (1)). This happens if LDH)) < c0.
The (() notations in Items 2. and 3. hide a dependence on VC(H), and LD(H),
respectively.
The proof uses bounds on the number of mistakes in terms of the threshold dimension (Section 3.2), among other tools.
II. Littlestone classes. The minimal constant upper bound in the @(1) of Theorem 4.1 is some value C(H) that depends on the class H. but the precise mapping H. + C(H) is
not known in general. [BKM97] showed that C(H) 2 (log(LD(H))) In Section and Appendix A we improve upon their result follows.
Theorem (Informal Version of Theorem 3.1). Let H. {0, 1}x such that LD(H) d < oc. Then MH, r²) = (d).
III. Multiclass setting, In Section 5, we generalize Theorem 4.1 to the multiclass setting with finite label set )/ showing trichotomy based on the Natarajan dimension. The proof uses simple result from Ramsey theory, among other tools.
Additionally, we show that the DS dimension of [DS14] does not characterize multiclass transductive online learning.
IV. Agnostic setting, In the standard (non-transductive) agnostic online setting, [BPS09] showed that Rontine (H, H. n),, the agnostic online regret for a hypothesis class H for sequence of length satisfies
Ronline LD(H) n) S Ronline (H, S O LDD(L))) nn.lgg log
Later, [ABD+2] 21] showed improved bound of Ronline (H, n1) = = .n)
In Section we show result similar to Eq. (1), for the transductive agnostic online setting.
such Theorem (Informl Version of Theorem 6.1). Let 7 S 10 such that 0 < VC(H) <
C0. Then the agnostic transductive regret for H is
2 <(VVC(H) n) R(H, m) 0 (VVC(H) n -n-lonnon llogn.
1.4 Related Works
The general idea of bounding the number of mistakes by learning algorithms in sequential prediction problems was introduced in the seminal work of Littlestone [Lit87]. That work introduced the online learning model, where the sequence of examples is revealed to the learner one example at time. After each example æ revealed, the learner makes prediction, after which the true target label y is revealed. The constraint, which makes learning even plausible, is that this sequence of (x, y) pairs should maintain the property that there an (unknown) target concept in a given concept class H which is correct on the entire sequence. Littlestone [Lit87] also identified the optimal predictor for this problem (called the SOA, for Standard Optimal Algorithm, and a general complexity measure which is precisely equal to the optimal bound on the number of mistakes: a quantity now referred to as the Liulestone dimension.
Later works discussed variations on this framework. In particular, as mentioned, the transductive model discussed in the present work was introduced in the work of [BKM97]. The idea (and terminology) of transductive learning introduced by [VC74, Vap82, Kuh99], to capture scenarios

---

where learning may be easier due to knowing in advance which examples the learner will be tested on. [VC74, Vap82, Kuh99] study transductive learning model closer in spirit to the PAC framework, where some uniform random subset of examples have their labels revealed to the learner and it is tasked with predicting the labels of the remaining examples. contrast, [BKM97] study transductive learning in sequential prediction setting, analogous to the online learning framework of Littlestone. In this case, the sequence of examples I is revealed to the learner all at once, and only the target labels (the y s) are revealed in an online fashion, with the label of each example revealed just after its prediction for that example in the given sequential order. Since a mistake bound in this setting is still required to hold for any sequence, for the purpose of analysis we may think of the sequence of x as being a worst case set of examples and ordering thereof, for a given learning algorithm. [BKM97] compare and contrast the optimal mistake bound for this setting to that of the original online model of [Lit87]. Denoting by d the Littlestone dimension of the concept class, it is clear that the optimal mistake bound would be no larger than d. However, they also argue that the optimal mistake bound in the transductive model is never smaller than 52 /log(d) d)) (as mentioned, in the present work). They further exhibit a family of concept classes of variable d for which the transductive mistake bound is strictly smaller by a factor of 3. They additionally provide general equivalent description of the optimal transductive mistake bound in terms of the maximum possible rank among certain family of trees, each representing the game tree for the sequential game on a given sequence of examples T.
improve this log (d)
In addition to these two models of sequential prediction, the online learning framework has also been explored in other variations, including exploring the optimal mistake bound under a best-case order of the data sequence x, or even a self-directed adaptive order in which the learning algorithm selects the next point for prediction from the remaining x' from the given sequence on each round. [BKM97, BEK95, GS94, BE98, Kuh99].
Unlike the online learning model of Littlestone, the transductive model additionally allows for nontrivial mistake bounds terms the sequence length (the online model generally has min n} as the optimal mistake bound). In this case, it follows immediately from the Sauer-Shelah-Pert lemma and Halving technique that the optimal transductive mistake bound is no larger than ((w)))(n) [KK05], where e is the VC dimension of the concept class [VC71, VC74].
2 Preliminaries
Notation 2.1. Let X be a set and n, k E N. For a sequence x = (II...., E X",, we write Tzk to denote the subsequence (Ii, If S 0 then Tggk denotes the empty sequence, X0.
Definition 2.2. Let k E N, let X and be sets, and let H C y A sequence (1I,81). (FK, E (X x y is realizable by H. or H-realizable, 3f E H Vi E [K: h(x;)= =1y
Definition 2.3. Let X be a set, let H. S. (0, let d E N, and let X f....... ..) C X. We say that H shatters X ifr every y 10, there exists h E H such that for all E [d], h(x;) = ys- The Vapnik Chenrknenhrsssssss (VC) dimension of H is VC(H) = sup | X S X finite A H shatters X}.
Definition 2.4 ([Lit87]). Let X be set and let d E N. A Littlestone tree of depth d with domain X is a set
T= T. :: ue 010.10
==0
Let H. C 10.1)x We say that H shatters tree T as in Eq. ffr every u E (0, 13 there exists hy E H such that
Vi E [d+ 1]: ((Fag..)) = ui.
The Littlestone dimension of H. denoted LD(H). is the supremum over all d E N such that there exists a Littlestone tree of depth d with domain X that is shattered by H.
Theorem 2.5 ([Lit87]) Let X be set and let H. C {0, 1 such that d = LD(H)= < 00. Then there exists a strategy for the learner that guarantees that the learner will make at most d mistakes in the standard inon-transductive online learning setting, regardless of the adversary's 's strategy and of mumber of instances be labeled.

---

3:00
3 T
301
h(xx) = 1
1(x1) = 0
110
h(010) =
1
1
0_-
C1
Figure I: A shattered Littlestone tree of depth 2. The empty sequence is denoted X. (Source: [BHM
Theorem 2.6 SSauer-Shelah-Perleee [She72, Sau72]), Let n, d E N, let X be a set of cardinality n, and let H S {0,1}* such that VC(H) d. Then [7] < E== (7)
Quantitative Bounds
3.1
Littlestone Dimension: A Tighter Lower Bound
The Littlestone dimension is upper bound the number of mistakes, namely
Vn N: M(H, n) < LD(H)
for any class H. This holds because LD(H) is upper bound on the number of mistakes for standard trontrranduuctive online learning [Lit87], and the adversary in the transductive setting is strictly weaker.
The Littlestone dimension also supplies lower bound. We give a quadratic improvement on the previous lower bound of [BKM97], as follows.
Theorem 3.1. Let be a set, C {0, 11xt such that LD(H) < co, and let N. Then M(H, n) min (llog(d)/2], [oggoo()))/)) (Lgggr)))
depth d that shattered by H. and let H. S H. be a collection of 2 functions that witness the shattering. The adversary selects the sequence consisting of the nodes of T breadth-first order. For each time step E [n]. let He denote the version space, i.e., the subset of Hi that is consistent with all previously-assineed labels. The adversary's adaptive labeling strategy at time f as follows. He very unbalanced, meaning that a large majority of functions in H., assign the same value to ze, then the adversary chooses yr to that value. Otherwise, H. is fairly balanced, the adversary forces a mistake (it can do so without violating H-rralizabilityy. The pivotal observation is that: (1) under this strategy, the version space decreases in cardinality significantly more during steps where the adversary forces a mistake compared steps where it did not force mistake; (2) let be the t-th node in the breadth-fine order. has distance = [log(t) from the root T. Because T is binary tree, the subtree T' of T rooted at x, is tree of depth d t. In particular, seeing as H, contains only functions necessary for shattering T', 1741 < 22-6+1 so Hi must decrease not too slowly with t. Combining (1) and (2) yields that the adversary must be able force mistake not rarely. A careful quantitative analysis shows that the number of mistakes the adversary can force at least logarithmic in
Proof idea for Theorem 3.1. Let T be Littlestone
The full proof of Theorem 3.1 appears in Appendix A.
3.2 Threshold Dimension
We also show some bounds on the number of mistakes in terms of the threshold dimension.
Definition 3.2. Let X be set, let X (x1,..., vK ) C X, and C (0, 13x We say that X is
thrsshold-shatteeedb shattered by H. if there exist h1...., ... hy E H such that h hz(z,) 1(j < for all i, [k].
5

---

The threshold dimension H. denoted TD(H), is the supremum of the set of integers l for which there exists sireshold-shatterel set of cardinality
The following connection between the threshold and Littlestone dimensions is well-known.
Theorem 3.3 ([She90, Hod97]). Let X be set, let H S {0, 13x, and let d N. Then:
1. (H) 2 d then (D(H) 2 [logd]
2. (H) d then LD(H) 2 [logd].
Item I in Theorem 3.3 and Eq. (3) imply that
Vn N: M(H, n) S TD((H)
for any class H. Similarly, Item 2 in Theorem 3.3 and Theorem 3.1 imply mistake lower bound of (log log (og(TT))))) However, one can do exponentially better than that, as follows.
Claim 3.4. Let X be set, let 71 _ 1) such that TD(H) cc, and let n E N. Then MHH, n) 2 min { [Log(d), [log(n)}}.
One of the ideas used in this proof appeared in example called worst in Section 4.1 of [BKM97].
01
02
Q3
N
3 7
Figure 2: Construction of the sequence in the proof of Claim 3.4. is a breadth-first enumeration of the depicted binary tree.
Proof of Claim 3.4. Let k
min (log(d)] [log(n)]} and let N = 2 Let X {Z1...., IN-1] } C X be a set that is threshold-shattese by functions hi,..., hx- E H and
h,(2,) 1(j i) for all i E [N 1]. The strategy for the adversary is to present X in dyadic
order, namely
N T aay N JaN
aan, ZIN
(2t I)N zk
More explicitly, the adversary chooses the sequence g = 0 o gs. where 'o" denotes sequence concatenation and
q:
J
for all E [k]. See Figure 2.
We prove by induction that for each i E [k). all labels chosen by the adversary for the subsequences prior to di H-realizable, and additionally there exists instance in subsequence qi which the adversary can force a mistake regardless of the learners predictions. The base case that the adversary can always force a mistake on the first instance, 91. by choosing the label opposite the learner's prediction (both labels 0 and 1 are H-realizable for this instance). Subsequently, for any i 1, note that by the induction hypothesis, the labels chosen by the adversary for all instances in the previous subsequences are H-realizable. In particular there exists an index E [N] such that instance Fa has already been labeled, and all the labels chosen so far are consistent with hg. Let b be the minimal integer such that b > and P4 has also been labeled. Then Ia and all labeled instances with smaller indices received label 1, while nG, and all labeled instances with larger indices received label () Because the sequence is dyadic, subsequence d contains an element &m such that < m The adversary can force a mistake on I'n because ha and hm agree on all previously labeled instances, but disagree Zm.-

---

for Claim 3,4 is used in the proof of the trichotomy (Theorem 4.1, below).
Finally, we note that for every d N there exists a hypothesis class H such that TD(H) and
Vn E N: M(H, n) min(d, n).
Indeed, take X' = [c] and H {0, 10 The upper bound holds because |X] d, and the lower bound holds by Item in Theorem 4.1, because VC(H) =
4 Trichotomy
Theorem 4.1. Let X' be a set, let S {0, 1]x, and let n such that a S (1
1. IfVC(H) oo then M MH,, =
2. Otherwise, VC)C(H) = d < oo and LD(H) = 0o then max n), [lo(()]} < M(H, S Old (lgl///dd)) Furthermore, each of the bounds in Eq. (4) is tight for some classes. The 2(()) and O(-) notations hide universal constants that do not depend on X or H.
(4)
3. Otherwise, there exists integer C(H) < LD(H) (that depends X and H. but does not depend on n) such that M n) S C(H).
Then there exists set X (f1...., InJ S. of cardinality n that is shattered by H. The adversary can force the learner to make mistakes by selecting the sequence (zi..... Tn). and then selecting labels y all t [n]. This choice of labels is H-rcalizable because X a shattered set.
Proof of Theorem 4.1. For Item 1, assume VC(H) =
To obtain the upper bound in Item the learner can use the halving algorithm, as follows. Let x = (ZI, In) be the sequence chosen by the adversary, and let H|2 denote the collection of functions from elements of x to {0. 1) that restrictions of functions in H. For each E {o....., let
H4 {f M| (Vi E [t] f(x)) v:)
be a set called the version space at time t. At each step E [nx]. the learner makes prediction
J, argmax (0.1) [( f H4-1 f(z,) bb]--
In words, the learner chooses according majority vote among the functions in version space H4-1, and then any function whose vote was incorrect is excluded from the next version space, Hi. This implies that for any E [m]. if the learner made a mistake time then
HHll 5
/H--1l-
(5)
Let M M(H, n). The adversary selects H-realizable labels, H., cannot be empty. Hence, applying Eq. (5) recursively yields
1 < Hml S 2- M Hoo 5 2-M (0((n/dd))
where the last inequality follows from VC(Ho) < VC(H) = d and the Sauer-Shelah-Perles lemma (Theorem 2.6). Hence M O(d (og(nn(n/ (n/ dd), desired.
For the min(d, n lower bound in Item 2, if n S d then the adversary can force mistakes by the same argument as Item 1. For the logarithmic lower bound in Item 2, the assumption that and in particular TD(H) 2 and this
LD(H) oo and Theorem 3.3 imply that TD(H) implies the bound by Claim 3.4.
For Item 3, the assumption LD(H) = k < ce and Theorem 2.5 imply that for any n, the learner will make most & mistakes. This because the adversary the transductive setting strictly weaker than the adversary in the standard online setting. So there exists some C(H) E {O...., k) as desired.
Remark 4.2. One can use Theorem 3.1 to obtain lower bounds for the case of Item 2 in Theorem 4.1. However, that yields a lower bound of 2(lg log(n)), which is exponentially weaker than the bound we show.
7

---

Multiclass Setting
The trichotomy of Theorem 4.1 can be generalized to the multiclass setting, in which the label set Y contains more than two labels. In this setting, the VC dimension is replaced by the Natarajan dimension [Nat89], denoted ND, and the Littlestone dimension is generalized in the natural way. The result holds for finite sets y.
Theorem 5.1 (Informal Version of Theorem B.3). Let X' be set, let y be a finite set, and let H S yx Then H satisfies precisely one of the following:
1. n) = This happens if ND(H) DC.
2. MHH, m)) (log(n))). This happens NH) oo and LD(H) oc.
3. M(H, n.) = O()). This happens if LH)) < co.
The proof of Theorem 5.1 appears in Appendix B, along with the necessary definitions. The main innovation in the proof involves the use of the multiclass threshold bounds developed in Appendix D, which in turn rely on a basic result from Ramsey theory, stated Appendix C.
5.1 The Case of an Infinite Label Set
is interesting to observe that the analogy between the binary classification and multiclass classifica- tion settings breaks down when the label y is not finite.
Example 5.2. There exists a class G S y such that y is countable, LD(g) is infinite, but the class is learnable with a mistake bound of (G, n)
To see this, let X be countable, and let H C {0, 1)x be a class with LD(H) = Cc. For each i E N, let T; be a Littlesoone tree of depth i that shatlered by H. and let ( 1
H be subset that witnesses the shattering. Let G- [ i NENA j E [2 be set of functions such that (z(x)) = (z)(z)),,, for all j. GEN
Let (0, X N. Observe that G S y is a countable set of functions with a countable set of labels. Furthermore, LD(G) corresponding to Tı T2..... However, G can be learned with mistake bound 1, because a single example of the form (x. (hi (z))., reveals the correct labeling function htj-
because G shatters a sequence of suitable Littlestone trees
Recent work by [BCD+ 22] has shown that multiclass PAC learning with infinite is not characterized by the Natarajan dimension, and that instead it is characterized by the DS dimension (introduced by [DS14]]. It therefore natural to ask whether the DS dimension might also characterize multiclass transductive online learning with infinite y. We show that the answer to that question is negative.
Recall the definition of the DS dimension.
Definition 5.3. Let d E N, let X and y be sets, and let H C Cy*, For an index E [d]] and vectors y = (....... ya) E yd. y' = (y'....,3') E yd, we say that y and y' are i-neighbors, denoted ~ v', if ije E [d] + v/} = {i}. We say that C C yd is d-pseudocube if C is non-empty and fimite, and
Vy CVi [d] By CC: y ~ n/-
For vector (I1, , ma) E Xd, we say that H DS DS-shttters if the set
H1 (h(21)) ... M(aa)) h H} S yd
contains a d-pseudocube.
Finally, the Shaeel--Shle--SSwaizz. (DS) dimension 7 is
DS(H) = sup N (3x E x H. DS-shatterd x)
See [BCD+22] for figures and further discussion of the DS dimension.
The following claim shows that the DS dimension does not characterize transductive online learning, when ) is finite.
Claim 5.4. For every n E N. there exists a hypothesis class Hn such that DS( = but the adversary in transductive online learning can can force least M HHn, n) mistakes.
8

---

Proof. Fix n E N and let X' = 10,,,2...... Consider a complete binary tree T of depth such that for each I E X, all the nodes depth x (at distance from the root) are labeled by 2, and each edge in T is labeled by distinct label. Let H be minimal hypothesis class that shatters 7, namely, H shatters T and there does not exist striet subset of H that shatters T.
Observe that M M(Hn n2) n, because the adversary can present the sequence 0, 2, ...., foree a mistake at each time step. To see that DS(H,,) = 1, assume for contradiction that there (21, x2) E X² that is DS-shattered by H.. namely, there exists 2-pseudocube Hzz. Note that æ A æ2, and without loss of generality #1 < x2 (H DS-shatters (21,42) if and only if it DS-shatters (22,
and
exists vector
Fix y E C. So y = (h(x1). h(x22) for some H. Because C is 2- 2-pseudocuhe, there exists y that is a 1-neighbor of y. Namely, there exists g E 'H such that y' = (g(x)), ((22)) E C, v # y1
and 1/2 = 1/2 However, because each edge in has a distinct label, and is minimal, follows that
for any E X,
g(z) h(x)) =
(Va' 40, g(x') h(x'))
In particular, g(x22 to the choice of y'.
V/2 1/2 = h((2)) implies v/1 = =((=)) = h(m) y1 which is a contradiction
Agnostic Setting
The agnostic transductive online learning setting defined analogously to the realizable (non- agnostic) transductive online learning setting described in Section 1.1. An early work by [Cov65] observed that is not possible for learner to achieve vanishing regret an agnostic online setting with complete information. Therefore, we consider game with incomplete information, follows.
First, the adversary selects an arbitrary sequence of instances, 21, In E X, and reveals the sequence to the learner. Then, for each / = ......
1. The adversary selects a label Y/ E y.
2. The learner selects prediction dL E y and reveals it to the adversary.
3. The adversary reveals ye the learner.
At each time step t E [n). the adversary may select any E y, without restrictions. 2 The learner, which is typically randomized, has the objective of minimizing the regret, namely
R(A, H. x, y) = [E] E [n] de + He min Ht E [m] h(x,)) # y.Hl AEH
where the expectation is over the learner's randomness. In words, the regret is the expected excess number of mistakes the learner makes when it plays strategy A and the adversary chooses the sequence x E X and labels y E y"" as compared to the number of mistakes made by the best fixed hypothesis h E H. We are interested in understanding the value of this game, namely
R(H, inf sup sup R(A, 2,
AEA ze vEy"
where A is the set of all learner strategies. We show the following result.
Theorem 6.1. Let X be set, let H S. 10, and let n E such that n S [2). Assume 0 < VC(H) < co. Then the agnostic transductive regret for H sequences of length is
2(VvC(H) n) < R(H, s (O(VC((HL) n log (n/VC(H)))
The upper bound in Theorem 6.1 follows directly from the the Sheee-hhhhhhhhhh lemma (Theo- rem 2.6), together with the following well-known bound on the regret of the Multiplicative Weights algorithm (see, e.g.. Theorem 21.10 in [SB14]).
Theorem 6.2. Let be a set and let H S. 10 be finite. There exists an algorithm for the standard noo-ttransductvve agnostic online learning setting that satisfies
Ronline (H, n) S /2 log (171)).
'Hence the name 'agnostic', implying that we make no assumptions concerning the choice of labels.

---

Theorem 6.2 implies the upper bound of Theorem 6.1, because the adversary in the transductive agnostic setting weaker than the adversary in the standard agnostic setting.
We prove the lower bound of Theorem 6.1 using an anti-conccntration technique from Lemma of [BPS09]. The proof appears in Appendix E.
Remark 6.3, Additionally:
1. IFVC(H) 0 (i.c., classes with single function)) then the regret is 0.
((VL((H)-))) - by
2. If VCH) < oo and LD(H) < co then the regret is R(H, n) [ABD 21J (as mentioned above). Namely, in some cases the log(n) factor in Theorem 6.1 can be removed.
3. I/VC(H) = oo then the regret is (m
7 Future Work
Some remaining open problems include:
1. Showing a sharper bound for the (1) case in the trichotomy (Theorem 4.1). Currently, there is exponential gap between the best known upper and lower bounds for Littlestone classes.
2. Showing sharper bounds for the @loggn) cases in the trichotomy (Theorem 4.1) and multiclass trichotomy (Theorem B.3).
3. Showing sharper bound for the agnostic case (Theorem 6.1).
4. Characterizing the numeber mistakes in the multiclass setting with an infinite label set y (complementing Theorem B.3).
Acknowledgments
Zachary Chase contributed significantly to this paper. All errors are our own.
SM is Robert J. Shillman Fellow: he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by an Azrieli Faculty Fellowship, by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the European Union (ERC, GENERAL- IZATION, 101039692). IS was supported by DARPA (Defense Advanced Research Projects Agency) contract HR001 12000015 and the Simons Collaboration on The Theory of Algorithmic Fairness. Views and opinions expressed are those of the author(s) only and do not necessarily reflect those of the European Union, the European Research Council Executive Agency, DARPA, the Simons Foundation. The European Union, the granting authority, DARPA, and the Simons Foundation cannot be held responsible for them.
References
[ABD+21] Noga Alon, Omri Ben-Eliezer Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret online classification. Samir Khuller and Virginia Vassilevska Williams, editors, STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 447-455. ACM, 2021. doi: 10.11445/406325534555
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learn- ing implies finite littlestone dimension. In Moses Charikar and Edith Cohen, edi- tors, Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Comput- ing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852-860, ACM, 2019. 1od11...145/331326.33133
[B111] Shalev Ben-David and Shai Ben-David. Learning classifier when the labeling is known. Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann, editors, Algorithmic Learning Theory 22nd International Conference, ALT 2011,
10

---

Espoo, Finland. October 5-7, 2011. Proceedings, volume 6925 of Lecture Notes in Computer Science, pages 440-451. Springer, 2011. 11.1000//978-3-42-4444 -4.
[BCD+22] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Ychudayoff. A characterization of multiclass learnability. In 63rd IEEE Annual Symposium on Founda- tions of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pages 943-955. IEEE, 2022.
[BE98]
Shai Ben-David and Nadav Eiron. Self-directed learning and its relation to the ve-dimension and to teacher-directed learning. Mach. Learn., 33(1):87-104, 1998. doi: 10. 102111003300000110 1005//021007511
[BEK95]
Shai Ben- Nadav Eiron, and Eyal Kushilevitz. On self-directed learning. In Wolfgang Maass, editor, Proceedings of the Eigth Annual Conference on Computational Learning Theory, COLT 1995, Santa Cruz, California, USA, July 5-8, 1995, pages 136-143, ACM, 1995, doi: 4444/22299.22533444
[BHM*21] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehu- dayoff. A theory of universal learning. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 532-541. ACM, 2021. doi: 14111.1144554403355555555056
[B19]]
Gyora M. Benedek and Alon Itai. Learnability with respect to fixed distributions. Theor. Comput. Sci., 86(2):377-390, 1991. doi: 10. 100016000443975011)0022233
[BKM97]
Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. Online learning versus offline learning. Much. Learn, 29(1):45-63, 1997. doi: 1007///71000445577777
[BPS09]
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebee, Canada, June 18-21, 2009, 2009. URL http: /www///wwwo/////////// www.mmaml......oo..o...........a wttp:./s.wgllll.a//aTa.......... / paaers// 032. paf-ee
[CL06]
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[Cov65]
Thomas M. Cover. Behavior of sequential predictors of binary sequences. In Trans- actions of the Fourth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes. Academic Press, 1965. URL https: stanffor............ edu/"cover srapers/paperts pdf.
[CS13]
Nicolò Cesa-Bianchi and Ohad Shamir. Efficient transductive online learning via randomized rounding. In Bernhard Schölkopf, Zhiyuan Luo, and Vladimir Vovk, editors, Empirical Inference Festschrift in Honor of Vladimir N. Vapnik, pages 177- 16.
194. Springer, 2013. 0001100.0007997---4442---2
[DS14]
Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, volume 35 JMLR Workshop and Conference Proceedings, pages 287- 316. JMLR. org, 2014. URL http: htttp://proceeeinggs mlr prwss/ html.
press/v355 /v3////3///// daniely14b.
[DSBS15]
Amit Daniely, Sivan Sabato, Shai Ben-David and Shai Shalev-Shware Multiclass learnability and the ERM principle. J. Mach. Learn. Res., 16:2377-2404, 2015.
doi:00:55//279222.113322
[GS94]
Sally A. Goldman and Robert H. Sloan. The power of self-directed learning. Mach. Learn., 14(1):271-294, 1994. doi:10. 11..110022//A1102255222222
[HL95]
David Haussler and Philip M. Long. generalization of sauer's lemma. J. Comb. Theory, Ser. A, 71(2):219-24 1995. doi:
[Hod97]
Wilfrid Hodges. A Shorter Model Theory. Cambridge University Press, 1997.

---

[KK05]
Sham M. Kakade and Adam Kalai. From batch to transductive online learning. In Advances in Neural Information Processing Systems 18. Neural Information Processing Systems, NIPS 2005, December 5-8, 2005, Vancouver, British Columbia, Canada, pages 61 611-618 2005. URL https: httpp::/ppooceediiiiii http://pooeeee.....eeeeeoo neuris.......................... wwweurris..cpppppeeeeeeep cctppppr//000//////// Abstract. html.
[Kuh99]
Christian Kuhlmann. teaching and learning pntrsectiin-closees concept classes. In Paul Fischer and Hans Ulrich Simon, editors, Computational Learning Theory, 4th European Conference, EuroCOLT 1999, Nordkirchen, Germany, March 29-31, 1999, Proceedings, volume 1572 of Lecture Notes in Computer Science, pages 168-182. Springer, 1999. doi: 10010000077335544499993333 14.
[Lit87]
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. Mach. Learn., 2(4))285-318, 1987. doi:10. 10111001007/F00116660
[Nat89]
B. K. Natarajan. On learning sets and functions. Mach. Learn 4:67-97, 1989.
doi: 1007000001 14804.
[Pec08]
Dmitry Pechyony. Theory and practice of transductive learning. PhD thesis, Technion Israel Institute of Technology, Israel, 2008. URL.
httpps://techhnonn wwwpcchhiiii..mim.eeeeeeeee exlibrssgroup g:j255//alnm0000232200000001111
[Sau72]
Norbert Sauer. On the density of families of sets. J. Comb. Theory, Ser. A, 13(1):145-147, 1972. 00010000016000113165777000999999
[SB14]
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learn- ing: From Theory to Algorithms. Cambridge University Press, 2014. N0f:10.1017/CB09811 1177788117799999
[She72] Saharon Shelah. combinatorial problem; stability and order for models and the- ories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-261, 1972. doi: 200.2140/pjmm. 19t.......77.........
[She90]
Saharon Shelah. Classificution Theory: And the Number of Non-Isomorphic Models, volume 92 of Studies Logic and the Foundations of Mathematics. North-Holland, second edition, 1990.
[SKS16]
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert E. Schapire. Efficient algorithms for adversarial contextual learning. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 2159-211111 2168. JMLR.org. 2016. URL http:// proceedings. mlr press/pess///eee www.:/reesse//eeeeeeeeee /ttp//////////iiiiii.s html.
[Vap82]
V. Vapnik. Estimation of Dependencies Based on Empirical Data. Springer- Opringer-Verlag. New York. 1982.
[VC71]
V. Vapnik and A. Chervonenkis. the uniform convergence of relative frequencies of events their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971. doi: 10.113//111102
[VC74]
V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974.
12

---

Appendices
A Proof of Lower Bound for Littlestone Classes
Proof of Theorem 3.1. Let I' be a Littlestone tree of depth d that is shattered by H. and let H1 C H be a collection of 2d++1 functions that witness the shattering. contains nry 2d+1 nodes. The adversary selects the sequence
consisting of the first nodes of T in breadth- first order (if n ne, then the adversary chooses the suffix +1.... arbitrarily). For each time step t E [n], let Hi denote the version space, i.e., the subset of Hi that is consistent with all previously-assignes labels. Namely, for any / > 1,
H4 = {h H1 (Vs E [t - 1]: h(x,) = ys)}
Similarly, for each b E {0, 1). let He, {h H. h(xx) = b}.
send T1, Fn to learner A +-1
for t <- 1.2....,
+- 22ah
1/TR
Tt 1/|Hell/HHll
receive ÚS from learner
De
rt Ex, Ei]
V1
0
rı E 0, E1)
rt E (1 Et,
send y/ to learner
rt E (s,. - ez]:
k +
Algorithm 1: An adversary that forces ((log(LD(H))) mistakes.
The adversary operates according Algorithm Conceptually, at each time step t [n], if H, is very unbalanced, meaning that a large majority of the functions in H. assign the same value to Ir. then the adversary chooses ye to be that value. Otherwise, if H4 is fairly balanced, the adversary forces a mistake, Note that if Hi is fairly balanced then the adversary can force a mistake without violating H- H-realizability.
We now argue that using this strategy, the adversary forces ?(log(d) mistakes. Let F t2.,t..... {t [n]: : T. [E,, 1-1x]] e be the of time steps where the adversary forces mistake. Note that in the for-loop in Algorithm 1, the value of k at the beginning of iteration &a is k (e.g., at the beginning of iteration 13, 3).
We argue by induction that for any & N, if m2 == 22th < n then:
1. FF A and du mmi and
2.
H.p, Z (1/m²)²² [.
The base case is immediate for 4 = 1 E F. For the induction step, assuming that Items and 2 hold for some E such that m&+1 S n,, we show that they also hold for & + 1. For Item assume for contradiction that & F for all such that to < t S m4+1-
13

---

For each t, to < E m4+1- the definition of ra and the adversary's 's labeling strategy imply that the label Yr agrees with least a (1 E, mmjorriyy of the functions in the version space H,. Hence,
mA-1
Hma+z 2 Hig 1- II (1 (1-E()
t=
Mell 1. (1 1/mx+11 m
Hi, .(1 1/mmx+1) 1411
)
Hil (1/mz)² 11/mm++1) m
(Induction hypothesis for Item 2)
2 Hil (1/m²)² ((1/4)
Hill 2-2 -
(6)
Observe that for every & E [n]] if 2,, is a node with depth l in T (i.e., the shortest path from the root to #t contains edges), then there exists an 'active' node z with the same depth in such that the version space Hi contains only functions from Hi that are consistent with the labels along the path from the root of T to xo. Namely, H4 a subset of the 2d- functions Hi that witness the shattering of the subtree T₃ of T that is rooted at xz.. In particular, the depth (distance from the root)
of node Tma+1 is log (2200+11) = 22k+2, 80
Hmzr S 2d-2 20+1, .221..23 2-22k=2
H11 -
Combining Eqs. (6) and (7) yields 2 2 2-2 which is contradiction. This establishes Item 1. Item 2 follows by similar calculation, which accounts for the fact that time fx+1 the adversary forces a mistake, and this reduces the version space by factor of at most Etyt1
11+1-1
Ho 2 H..l
II (1 ((==a)
-Eut1
1=+++1
2 Hull (1 1/mx+1) me+.
/m (1/m8+1)
HHul (1/4) (1/ma+2)
|Hil (1/ma)² -11/4) (1/mx+1)
(Induction hypothesis for Item 2)
|H4] 2 - (1/4) -2 2--2242
=1741 -6222
2 [71] 2 --222 = 1741 --2.2(0k111)
= -174 (1/mx+1)2.
This completes the induction.
To complete the proof, let k = min [[log(d)/2) (d)] log log(n)/2]]] Then my- < 2d < 2d+1 nr, so T contains least my- nodes. Additionally, my- I n, so Item implies that |F| 2 k. namely, the adversary can force at least k* mistakes, as desired.
B Multiclass Trichotomy
The following generalization of the Littlestone dimesion to the multiclass setting is due to [DSBS15].
Definition B.1 (Multiclass Littlestone Dimension). Let X and y be sets and let E A Littlestone tree of depth d with domain X and label set Y is set
T
(Ias (Fus Bwso, Muoo) X x xx
(0. Dwoo # Buol 3
(8)
where denotes string concatenation, Let 7L C y. We say that H shatters a tree as in Eq. (8) if for every u E {0, 1]+41 there exists lt E H such that
Vi E [d + 1]: (Zuge_)) Yugs-
The Littlestone dimension of H. denoted LD(H), is the supremum over all N. such that there exists a Littlestone tree of depth d with domain X and label set y that is shattered by H.
14

---

The Natarajan dimension is popular generalization of the VC dimension to the multiclass setting,
Definition B.2 ([Nat89]). Let X and y be sets, ler H. S yy² let d N, and let X {01 (21,...,22. fa E N. We say that H Natarajan-shatter X if there exist fo. f1 : X + such that:
1. Vx X: fo(x)) + fi()); and
2. AA V E H Vo E X h(x) [I(HEA)(E))
The Natarajan dimension of H. is ND(H) = sup {|X]: X X & finite A H Natarajan-shatters X
We show the following generalization of Theorem 4.1 for the multiclass setting.
Theorem B.3 (Formal Version of Theorem 5.1). Let and y be sets with k = |3) oc, let
H S yxx and let E N such that S |
(HH) = oo then M (H, n) = n.
2. Otherwise, if ND(H)) d < oc and LD(H) = oc then [log(n)]} S M(H,n) S O(dlog(nk/d)).
m
(9)
The (1()) and O(-) notations hide universal constants that do not depend on X, y or H.
3. Otherwise, there exists a number C(H) N (that depends on X, y and H but does not depend on n) such that (H, n) S C(H).
The proof of Theorem B.3 uses the following generalization of the Sauer-Shelah-Perkee lemma.
Theorem B.4 ([Nat89]; Corollary 5 in [HL95]]. Let d. n, k E N, let X and y be sets of cardinality and k respectively, and let H E y such that ND(H)= I d. Then
17 S
d
n1
h: 2
1
1
eenk2 d
d
Proof of Theorem B.3. Items and and the min fd, n) lower bound in Item follow similarly to the corresponding items in Theorem 4.1. The upper bound in Item 2 also follows similarly to the corresponding item in Theorem 4.1, except that uses Theorem B.4 instead of the Sauer-Shelah- Perles lemma. The [log(n) lower bound in Item follows from Theorem D.5 and Claim D.4. D
C Combinatorics of Trees
In this section we present a simple lemma from Ramsey theory about trees that is used for proving Theorem D.5. We start with a generalized definition of subtrees.
Definition C.1. Let X be a finite set and let (X,z) be a partial order relation. For P.C E X, we say that e a child of p if 3 and there does not exist m E X such that p 3 m 3 We say that E X is leaf if there exists no E X such that I x. (X, is binary tree if every non-leaf x E X has precisely 2 children. The depth of z E X is the largest d E N for which there exist distinct 21,..., T. E such that Iı 22
I ad 1 For d E N, we say that (X, 3) is complete binary tree of depth d if (X, 3) ) is a binary tree and all the leaves in X have depth d. We say that a partial order (X',z') is a subtree of (X. X' X, and da, b E X', a 3' = asb b.
Lemma C.2 (Lemma 16 in [ALMM191). Let q E R be non-negative such that p + q E N. Let
3) be a complete binary tree of depth = p q 1, and let f X - (0, 1). Then at least one of the following statements holds:
=
T has a 0- n-monochromatic complete binary subtree of depth at least p. Namely, there exists
T" = (X', , z') such that T" is a subtree of T. T' is complete binary tree of depth at least
p. and [(x) = for all X'.
. T has a 1-monochromatic complete binary tree subtree of depth at least
For completeness, we include a proof of this lemma.
Proof of Lemma C.2. We prove the claim by induction on the depth The base case of d = 0 (a tree with single node) is immediate. For the induction step, let a denote the root of T, and let T
15

---

and T. denote the subtrees of T of depth d - 1 consisting of all descendants of the left and right child of respectively. Assume that f(a) 0. T or T, contain a 1-monochromatic subtree of depth at least then we are done. Otherwise, by the induction hypothesis, both trees contain O-monochromatic subtree of depth at least p Joining these two subtrees as children of the root yields 0 (--monchrromttc subtree of depth at least as desired. The proof for the case f(a) = is similar.
We use the following corollary of Lemma C.2.
Lemma C.3. Let k, d E N. Let T (X,3) be complete binary tree of depth N, and let f: X - [k]. Then T has an f-monochromatic complete binary subtree T" (X', ,') of depth at least
d+1 d'
2 [[]]
Namely, there exists T" such that T' is subtree of T, T'' is complete binary tree of depth at least d', and (f((a) a E X 1
Proof of Lemma C.3. We will show that for any monochromatic subtree of T of depth at least
N. if S 2 then there exists an f-
d ++1
2
This implies the lemma, which corresponds the special case b [log(A)].
We proceed by induction on b. The base case I = follows from Lemma C.2. For the induction step, we assume that the claim holds for and prove that holds for + Namely, we show that if f X + [k] and k < 2 then there exists an f-monochromatic subtree of depth at least (d + 1)/2
X {1,2} by )(x) = 1 (f(x) mod 2). By Lemma C.2, there exists g- monochromatic complete binary subtree To 3X) of of depth at least (d + 1)/2. In particular [f(x): I XoH| S 2h. By invoking the induction hypotheses on To. there exists a complete binary subtree of To that is f-monochromatic and has depth at least
Define 9
d+1
+
2
21+1
as desired.
D Multiclass Threshold Bounds
Definition D.1. Let X and y be sets, let X (x1.... Iz) C X. and let H C We say that X is shatseeld-saatteeed by H if there exist distinct yo, y1 E and functions hi,...,he E H such that hx(z)) = Vi(ses)- The threshold dimension of H. denoted TD(H), is the supremum of the set of integers L for which there exists threshol-sshateeee set of cardinality l.
We introduce the following generalization of the threshold dimension.
Definition D.2. Let X and y be sets, let X = (xi,..., II)e C X, and let H. C y We say that X
multi-class threshold-shattes shattered by H if there exist y1, y .....,, ye, v/ E y such that ys + 1/, for all
i,j [1, and there exist functions hu,..., he E H such that
......,,,
hs(2;)
Vi
i 1).
(
The multi-class threshold dimension of H. denoted MTD(H), is the supremann of the set of integers t for which there exists shreshold-shuttered set of cardinality
See Table for an illustration of this definition.
Claim D.3. Let X and y be sets, k = | co, and let C y Then TD(H) > [MTD(H)/k])
Proof of Claim D.3. The proof follows from two applications of the pigconhole principle.
0
16

---

21
2/4
25
h1
31
N2
Y's
Y4
112
1/2
1/2
y3
Y4
y
h3
y3
3/3
93
84
14
34
34
34
h5
1/5
5/5
y5
M/
y5
Table 1: An illustration of Definition D.2. The table shows a collection of points fa1...., .i.....,..... 255 that multi-class threshold shattered by functions (hi,..., h-)-
Claim D.4. Let X and y be sets, let H S y* such that d = TD(H) < oc, and let n E N. Then
M (H, n) 2 min [loogdd), [log(n)]}
The proof of Claim D.4 is similar to that of Claim 3.4.
Theorem D.5. Let X and y be sets with | < oc, let H C y LD oo then
MTD(H) = cc.
Proof of Theorem D.5. Let (d) be the largest number such that every class with Littlestone dimen- sion d has multi-class threshold dimension at least fu (d). We show by induction on d that fa satisfies the following recurrence relation:
fa(d) 2 1
d= [ d>
In particular, this implies that fx( d=000 oc, which implies the theorem.
The base case d = LD(H) = immediate. For the induction step, we assume the relation holds whenever LD(H)) [d - 1]. and prove that holds for LD(H) d. Let T be Littlestone tree of depth that shattered by H. Fix E H. Then is a k-cloring of the nodes of T. By Lemma C.3, there exists h-monochromatie subtree T" T of depth at least [d/2k]. Let
the color assigned by to all nodes of T'. T" is shattered by H. so there exists child e of the root x of T" such that edge from subtree rooted at so LD(H') 2 [d/2k] 1. By the induction hypothesis, there exist II...., for fu (T [[d/2k] 1) that are multi-class threshold shattered by functions hy..... h, H'.
is labeled by some value y' # y. Let H' {g H g(x) = y y'). H' shatters the
By construction, the set X = {x1,..., To. Is+1 (hi...., h,, h f.). because h441 (14)(1;) = y for all j [s + 1]. and h;(x++1) y for all i E [s]. Hence, fa(d) 2 8 + = 1+ fx([d/2k] - 1), as desired.
x} is multi-class threshold shattered by
E Proof of Agnostic Lower Bound
The lower bound in Theorem 6.1 is derived using an onti-concentration technique from Lemma 14 of [BPS09]. Specifically, this technique uses the following inequality.
Theorem E.1 (Khinchine's inequality; Lemma 8.2 in [CL06]). Let k E N, and let σı, 02,02..... Th be random variables sampled independently and uniformly random from {+1}. Then
E
Σ iEk
ok
k/2
Proof of lower bound in Theorem 6.1. Letd = VC(H). Let f.i...., x X be aet of cardinality that VC-shattered by H. Let be the largest integer such that kd S n.
Let E X be sequence consisting of copies of the shattered set, namely,
(II,..., Ikd) (=), "i. ... at 21. 22.... , .r....,, 2
such that of = at for all E [d] and j E [M). If kd then the remaining n kd elements of may be arbitrary.
17

---

Consider a randomized adversary that selects the sequence æ, and chooses all labels to be i.i.d. uniform random bits. For each E [d] and j [k), let v = y(1-1)4+3 and 'y D(j-1) denote, respectively, the labels and the predictions corresponding to ar. Then for any learner strategy A,
E
R(A x. v)]
B
Σ iE(m)
(ūe # ve)
min WEH
Σ vE(M)
(h(())) + y.)
y-U(((.1)m)
9
E
min kCH iE/mo
(h(x)) # ve)
(y4 1 9.)
2
kd
E
min NEH
(Maz)) + vł) Σ
(10)
2
1=-((1011)ka)
kE [c] [
kd
Σ (h(x²) # #1?) uE)
E
min WEH
(H shatters
2
LE|d
JE[K]
E
min Σ NEW ]K(
(M(x²) # (m(=)++b)
2
km
E
min Onin k 1or-ral ri]
(Letr; = Σ vt)
(10.11))
1=1
SE(A]
k
E
2
(Let = { 1 y
E
{ -1 y
2
jE(M
E U((001))
Σ
2 ==1
bE[k]
dvk
22( (((vnd) v
(1I)
2/2
where the final inequality is Khinchine's 's inequality (Theorem E. To see that Inequality (10) holds, let h" E argminneN Edd kdd 1 (h(x:) # y1), and then
E -~U((1.1))))
min REH kE(m)
Σ
1 (h(ar)) + ye)
kd
11 (xxe))) + w1)
E 10)")
Σ
n
1 (1i + m.)
k=kd+1
n - kd
E y-U(((
11 (h' (xx) + ve)
Aychesa 1 Lh))
In particular, Eq. (11) implies that for every learner strategy A there exists y E (0, 1)" such that R(A, H., 3) Q (Vnd).
O
18


Reviews:
[{"review_id": "dDgIUhHwdI", "reviewer": "Reviewer_a8Lo", "summary": "This paper studies transductive online learning. In this setup, the adversary fixes the sequence of unlabeled instances and reveals labels sequentially following learner's prediction in each round. The paper shows a trichotomy of rates for binary classification: $n$, $\\Theta(\\log{n})$ and $\\Theta(1)$ based on finiteness/infiniteness of VC and Littlestone dimension of the hypotheses class. The authors also extend the result to multiclass setting establishing a similar trichotomy depending on Natarajan and multiclass extension of Littlestone dimension. Finally, the authors provide a quadratic improvement in the known lower bound in the case $\\Theta(1)$.", "questions": "1. Does Theorem 3.1 imply the $\\log{n}$ lower bound in Item (2) of Theorem 4.1 using the fact that $\\text{LD}(\\mathcal{H}) \\geq n$ for each $n$? If so, is the discussion of Threshold dimension and Claim 3.4 required to establish the trichotomy for binary case? What about multiclass extension?\n\n2. In Line 44-45, the authors claim that neither party benefit  from using randomness. Do authors mean that there wont be any quantitative difference (up to a constant factor) between deterministic and randomized learning rules? This is most likely true but I would like authors to justify their statement instead of just claiming it.\n", "limitations": "Not applicable. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper identifies the trichotomy of rates in online transductive learning. Such trichotomy has been identified in the recently introduced setting of universal learning [BHMvHY2021]. As far as I know, this is the first paper to note such trichotomy in any variant of online learning model. Qualitatively, the paper shows that VC, instead of more restrictive Littlestone, is necessary and sufficient for  learnability of the hypotheses class in transductive online setting.\n\n2. The paper studies a theoretically interesting problem and motivates the problem through a meaningful example. Apart from the proof in Section 6 which I found to be written sloppily, the paper is well-written and easy to follow.\n\n3. The proof technique of Theorem 3.1 is novel and differs from standard lower bound techniques in online learning literature.  \n\n\n\n[BHMvHY2021]  Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. 2021. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021). Association for Computing Machinery, New York, NY, USA, 532–541. https://doi.org/10.1145/3406325.3451087\n", "weaknesses": "My general impression of the paper is that there is a room for a more comprehensive treatment of the material considered here.\n\n1. I might be speaking with a hindsight bias here, but I think most of proofs regarding trichotomy (Theorem 4.1) is straightforward except that of Claim 3.4 (also see my question below).  In view of that, I would have preferred to see a sharper analysis of mistake bounds in Items 2 and 3 . Namely: (a)  What is the optimal dependence of  $\\text{VC}(\\mathcal{H})$ and $n$ for the case $\\text{VC}(\\mathcal{H}) < \\infty$ and $\\text{LD} (\\mathcal{H}) = \\infty$? (b) Is there an algorithm that exploits the transductive nature of the game to get a mistake bound better than $\\text{LD}(\\mathcal{H})$ when it is finite?\n\n2. The exposition of proof of Theorem 3.1, arguably the main technical contributions of the paper, can be improved. For instance, what is $j$ in $\\varepsilon_t = \\varepsilon^{(j+1)}$ in line 267? What is the role of the constant $C_1$ in the proof/result? Line 263 claims we can take $C_1=5$? If so, why not just use  $5$ for a clearer presentation (although I dont see why it cant be 2)? What is superscript $1$ in $C_1$ indexing? The paragraph following line 270 (that analyzes the adversary) can also be improved in its clarity. \n\n3. The authors could have considered agnostic setting as well. What is the characterization of learnability for online agnostic transductive learning? Does one observe such trichotomy of rates? \n\n\n \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:\nI might be speaking with a hindsight bias here, but I think most of proofs regarding trichotomy (Theorem 4.1) is straightforward except that of Claim 3.4 (also see my question below).**\n\n**Answer:** We believe our paper makes some neat and non-trivial contributions, see our **_General Answer 1_** in the Author Rebuttal section.\n\n**Comment**\n**The exposition of proof of Theorem 3.1, arguably the main technical contributions of the paper, can be improved.**\n\n**Answer:** Agreed. That proof is clearly less polished than the rest of the paper. In a camera-ready version, we would be sure to iron it out and bring it up to the standard of writing we have shown in the rest of the paper. (The math of the proof is correc)\n\n**Comment:\nDoes Theorem 3.1 imply the $\\log n$ lower bound in Item (2) of Theorem 4.1 using the fact that $\\mathsf{LD}(\\mathcal{H}) \\geq n$ for each $n$ ? If so, is the discussion of Threshold dimension and Claim 3.4 required to establish the trichotomy for binary case? What about multiclass extension?**\n\n**Answer:** This is a good question! But no -- Theorem 3.1 does not imply the $\\log(n)$ lower bound in the trichotomy. Suppose that $\\mathsf{LD}(\\mathcal{H}) \\geq d$ for some integer $d$. In the lower bound of Theorem 3.1, the adversary takes a shattered Littlestone tree of depth $d$, presents the nodes of that tree in breadth-first order, and forces $c_0 \\cdot \\log(d)$ mistakes. However, a tree of depth $d$ has $\\Omega(2^d)$ nodes, so the lower bound implies that if the adversary presents $n = \\Omega(2^d)$ instances, it can force $c_0 \\cdot \\log(d) = \\Omega(\\log\\log(n))$ mistakes. Namely, using Theorem 3.1 would yield a lower bound of $\\Omega(\\log\\log(n))$ mistakes, which is exponentially weaker than the $\\log(n)$ lower bound we present in Item (2) of Theorem 4.1.\n\nAs an aside, we note that beyond this quantitative advantage, our proof of the $\\log(n)$ lower bound via the threshold dimension has the additional advantage that it generalizes to the multiclass setting, as we show in the supplementary materials.\n\n**Question:**\n\n**Is there an algorithm that exploits the transductive nature of the game to get a mistake bound better than \n when it is finite?**\n\n**Answer:**\nThis is an open question. The \"correct\" mistake bound in the $\\Theta(1)$ case can be anywhere between $\\mathsf{LD}(\\mathcal{H})$ and $\\log(\\mathsf{LD}(\\mathcal{H}))$.\n\n**Question:**\n\n**In Line 44-45, the authors claim that neither party benefit from using randomness. Do authors mean that there wont be any quantitative difference (up to a constant factor) between deterministic and randomized learning rules? This is most likely true but I would like authors to justify their statement instead of just claiming it.**\n\n**Answer:**\nAgreed. This is not hard, we will include a proof in the camera-ready version."}, {"review_id": "rHPgleEBiP", "reviewer": "Reviewer_gZ3U", "summary": "This work considers transductive online learning where the pool of examples to be labeled is fixed and known to the learner.  Thus, the adversary can\ncontrol the order that the points are presented to the learner and the label that the learner receives in each round.  The  goal of the learner is to predict labels in each round so that they do as few mistakes as possible.  In this work the\nauthors provide new results on the minimum possible number of mistakes.\nThey show that the minimal mistakes can either be constant, grow logarithmically, or grow linearly with the number of examples $n$ that are to be labeled by the learner.  More precisely, they show that if the VC dimension of the class is infinite then the number of mistakes is $n$, if the VC dimension is bounded but the Littlestone dimension is infinite then the number of mistakes is $\\Theta(\\log n)$, and when the Littlestone dimension is bounded the number of mistakes is constant.  Morever, when the Littlestone dimension is at most $d$ the authors show a $\\Omega(\\log d)$ lower bound on the number of mistakes.\n", "questions": "See weaknesses. Stating the key ideas or differences of the techniques of this work compared to the prior works could help.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The transductive learning model is a well-motivated, and interesting learning model that may often be more realistic than the fully adversarial (standard) online setting where the adversary can choose the examples to be labeled.\n\nThis work provides a new trichotomy result and an improved bound ($\\Omega(\\log d)$ instead of $\\Omega(\\sqrt{\\log d})$ that was shown in the prior work) on the number of mistakes under bounded Littlestone dimension. Moreover, the argument for the $\\Omega(\\log d)$ is nice.", "weaknesses": "\nMy main concern about the main result (the trichotomy of Theorem 4.1) of this work follows rather easily from prior works.  It is not hard to show that when the VC dimension is infinite the adversary can always make the learner to do $n$ mistakes.  Moreover, with bounded VC dimension (less than or equal to $d$), the algorithm that achieves the $d \\log (n/d)$ mistake bound is the standard halving algorithm that has been used extensively in the online learning literature.  Finally for the third assertion of Theorem 4.1, when Littlestone dimension is bounded the work of Littlestone '87 directly yields a finite mistake bound. The multiclass generalization of the trichotomy is a nice generalization but follows in the same way as the binary result and does not seem to add much to the paper from a technical point of view.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:\nMy main concern about the main result (the trichotomy of Theorem 4.1) of this work follows rather easily from prior works. It is not hard to show that when the VC dimension is infinite the adversary can always make the learner to do \n mistakes. Moreover, with bounded VC dimension (less than or equal to $d$), the algorithm that achieves the $d\\log(n/d)$ mistake bound is the standard halving algorithm that has been used extensively in the online learning literature. Finally for the third assertion of Theorem 4.1, when Littlestone dimension is bounded the work of Littlestone '87 directly yields a finite mistake bound.**\n\n**Answer:**\n\nWe believe our paper makes some neat and non-trivial contributions, and is worthy of publication. We invite the reviewer to reconsider their position on this after reading our **_General Answer 1_** in the Author Rebuttal section.   \n\n\n**Comment:\nThe multiclass generalization of the trichotomy is a nice generalization but follows in the same way as the binary result and does not seem to add much to the paper from a technical point of view.**\n\n**Answer:**\n\nSpecifically, see the third bullet of General Answer 1 in the Author Rebuttal.\n\n**Comment:**\n\n**Stating the key ideas or differences of the techniques of this work compared to the prior works could help.**\n\n**Answer:**\n\nThe camera-ready version will include a discussion comparing our work with [KK05] and the other papers mentioned in Footnote 1 on Page 1.\n"}, {"review_id": "hhNTRT2IhH", "reviewer": "Reviewer_e1Y3", "summary": "The paper considers the realizable case in the transductive online learning setting. It shows that, for a sequence of length $n$, the number of errors is $\\Theta(n)$, $\\Theta(\\log n)$ or $\\Theta(1)$ depending on the finiteness of the VC dimension and the Littlestone dimension. In the last case, the paper also improves the dependence on the Littlestone dimension $D_L$ from $\\Omega(\\sqrt{D_L})$ to $\\Omega(D_L)$.", "questions": "* Could the multi-dimensional case be stated in terms of graph dimension? Then there would be no $\\log k$ factor.", "limitations": "The paper only considers the realizable case", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The paper looks sound and their main result is clear.", "weaknesses": "I have the following concerns:\n1. The significance of the main contribution. In Theorem 4.1, the only non-trivial case is the upper bound in Item 2, and, as I understand, it follows from [KK05]. Maybe pointing out the trichotomy is significant in itself, but I'm not in the area, so I can't judge it.\n2. Presentation should be improved. It took me some time to parse Definition 2.4, and I could do this only because I knew the definition before.  Both this definition and the reasoning in lines 185-188 are better replaced with pictures.\n3. I didn't judge by this point, but I suspect that not all relevant references are included. E.g. I think that some papers [KK05] should potentially be cited.\n\nMinor issues:\n* Line 202: \"claim\" is repeated\n* Why did you move some material to the supplementary? There should be enough space in the main body.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:**\n\n**The significance of the main contribution. In Theorem 4.1, the only non-trivial case is the upper bound in Item 2, and, as I understand, it follows from [KK05]. Maybe pointing out the trichotomy is significant in itself, but I'm not in the area, so I can't judge it.**\n\n**Answer:**\n\nPlease see General Answer 1 above. Regarding [KK05], note that:\n - They do not discuss lower bounds\n - Their upper bounds are a bit different. Specifically, they use a randomized or “hallucination” algorithm to show an expected bound whereas we show a worst-case bound (we also shave off a log(d) factor from their result, reducing from $d\\log(n))$ to $d\\log(n/d))$, but that is easy).\n\n\n**Comment:** \n**Presentation should be improved. It took me some time to parse Definition 2.4, and I could do this only because I knew the definition before. Both this definition and the reasoning in lines 185-188 are better replaced with pictures.**\n\n**Answer:** \n\nAgreed, we will add figures for the definition of a Littlestone tree and for the dyadic order argument.\n\n**Comment:**\n**I think that some papers [KK05] should potentially be cited.**\n\n**Answer:**\n\nThank you for pointing this out! The camera-ready version will include a discussion comparing our work with [KK05] and the other papers mentioned in Footnote 1 on Page 1.\n"}, {"review_id": "j1S4k50aw2", "reviewer": "Reviewer_GnLU", "summary": "This paper studies transductive online learning, which differs from standard learning in that the adversary must commit to a sequence of instances to be labelled by the learner at the start of the game. The adversary's strategy can thus only be adaptive w.r.t. the labeling of the sequence, not the sequence itself. The goal of the paper is to bound the number of mistakes made by learning algorithms on a sequence of length $n$.\n\nThe main result is comprised of three different set ups: \n- If the VC dimension of a concept class is infinite, then the number of mistakes is $n$,\n- If the VC dimension is finite, but the Littlestone dimension is infinite, then the number of mistakes is logarithmic in $n$,\n- Finally, if the Littlestone dimension is finite, then the number of mistakes is constant (in the sense that it does not depend on $n$ -- it will however depend on the Littlestone dimension). ", "questions": "Questions\n- l.236: what is $m$? Do you mean $d$?\n- Is there a fundamental difference in the derivation of the results for the multiclass setting (vs binary)? \n\nComments:\n- Informal version of Thm 4.1 (l.69): I think it should be specified that the constants in cases 2 and 3 hide a dependence on the VC and Littlestone dimensions, respectively.\n- l.202: \"Claim claim\"\n- Perhaps include a future work/conclusion section?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- Conceptually interesting to have a trichotomy that depends on the VC and Littlestone dimensions \n- The paper is well-written and easy to follow, especially the proofs, which are clear and well-explained\n- The proof of Theorem 3.1 is interesting, and carries the technical weight of the paper, in addition to being a significant improvement on previous lower bounds \n- This paper seems of interest to the online learning theory community ", "weaknesses": "- Apart from the proof of Theorem 3.1, the proofs seem relatively straightforward, so the originality/novelty of the work is mainly conceptual, not technical. More specifically, items 1 and 3 from Theorem 4.1 are applications of the definitions of the VC and Littlestone dimensions -- but Theorem 4.1 is the main contribution of the paper, apart from the lower bound. Item 2 on appearance seems more substantial but l.218-225 are simply explaining the Halving algorithm, leaving the main technical tool to be an application of the Sauer-Shelah-Perles lemma. \n- A substantial improvement would come from getting a tighter bound w.r.t. the Littlestone dimension for the constant in item 3 of Theorem 4.1, as for now the proof (l.234-236) follows directly from the definition of the Littlestone dimension (of course, easier said than done! I just think there is some technical weight missing in the paper) \n\nI was hesitating between a 4 and 5, but opted for 5 because of Thm 3.1 and the conceptual contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:**\n**Apart from the proof of Theorem 3.1, the proofs seem relatively straightforward, so the originality/novelty of the work is mainly conceptual, not technical. [...] I just think there is some technical weight missing in the paper.**\n\n**Answer:**\nWe believe our paper makes some neat and non-trivial contributions, see our **_General Answer 1_** in the Author Rebuttal section.\n\n\n**Comment: l.236: what is m? Do you mean d?**\n\n**Answer:** Yes, this should be $d$. Thanks for identifying this typo!\n\n**Question:**\n**Is there a fundamental difference in the derivation of the results for the multiclass setting (vs binary)?**\n\n**Answer:** \nTechnically, the multi-class case involves some considerable additional work, as we explain in the third bullet in _General Answer 1_ in the Author Rebuttal section.\n\n**Comment:**\n**Informal version of Thm 4.1 (l.69): I think it should be specified that the constants in cases 2 and 3 hide a dependence on the VC and Littlestone dimensions, respectively.**\n\n**Answer:**\nThanks for the suggestion! We will add this.\n\n**Question:**\n**Perhaps include a future work/conclusion section?**\n\n**Answer:**\nThe camera-ready version will include a Future Works section, touching on the agnostic case, and discussing our thoughts on obtaining sharper bounds in the $\\Theta(\\log(n))$ and $\\Theta(1)$ cases of the trichotomy.   \n"}, {"review_id": "0IlyFxHPiy", "reviewer": "Reviewer_Hibd", "summary": "This paper studies realizable transductive online learning on a fixed and *known* sequence $x_1,\\dots,x_n$ (meaning the order is given). The authors state a trichotomy of error rates depending on the finiteness of the VC dimension and Littlestone dimension of the given hypothesis space. Along the way they improve a lower bound on the number of mistakes in terms of the Littlestone dimension. They use the relationship to the threshold dimension to achieve their bounds. Finally, they extend their results to the multi-class case.", "questions": "Essentially the results (as most such online learning papers) leave the gap between $VC+\\log n$ and $VC \\cdot \\log n$ open. Do you have any ideas how to close this gap? Sure you state that both bounds are tight on specific instance sequences, but maybe there is a different combinatorial parameter (probably depending on the particular sequence?) interpolating between \"$+$\" and \"$\\cdot$\" allowing to get instance-dependent tight bounds.\n\nYou briefly discuss some issues in the multi-class case with $|\\mathcal{Y}|=\\infty$. However there is the recent work by Brukhim et al [FOCS 2022] using the Daniely-Shalev-Shwartz (DS) dimension to characterize multi-class learnability even if $|\\mathcal{Y}|=\\infty$. Do these results apply in your setting by swapping the Natarajan dimension (or graph dimension etc.) with the DS dimension?\n\nIs the $\\log(LD(H))$ lower bound best possible? I.e., are there specific examples where this is tight (meaning, same upper bound).", "limitations": "/", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Nice overview. Well written. Easy to follow proofs.\n\n---- rebuttal comment -----\nAs authors addressed multiple concerns and added additional results on the agnostic case, I raised my score from 6 to 7. I think this paper is valuable for the online learning community.", "weaknesses": "Most of the claimed results are already known or exist implicitly. In particular, all the bounds used in the trichotomy are standard (either from Littlestone's Halving / SOA, or from the online vs offline paper). Even the additional $\\log(n)$ lower bound given by the threshold dimension was essentially covered by an example (called \"$\\sigma_{\\text{worst}}$\") in [BKM97] (without using the threshold dimension explicitly though). The actual main novelty (which is still a decent and interesting contribution) is the improvement of the lower bound from $\\sqrt{\\log(LD(H))}$ to $\\log(LD(H))$.\n\nThe informal version of Thm 4.1. is slightly misleading. E.g., case 2 If $VC(H)=n$ the rate is still $\\Theta(n)$ instead of $\\log(n)$.\n\nI would suggest writing up the bounds for a finite instance space $|\\mathcal{X}|=n$ as corollaries. This might be interesting for various settings (e.g., node classfication) and guide the intuition of the reader. \n\nI am not sure referring to the setting here with the sequence $(x_1,\\dots,x_n)$ known in advance to the learner as \"transductive\" is the best idea. Transductive typically refers to the set (without knowing the order) $\\\\{x_1,\\dots,x_n\\\\}$ to be known. Even one of the referenced papers [KK05], which the authors use to justify the name change from $M_{worst}$ to transductive, is merely referring the fact that the set is known but not necessarily the sequence (e.g., \"the set of unlabeled examples is then presented to the learner\") as transductive. Similarly for instance, the paper [CS13] refers to the fact that the set is known (instead of the sequence) as transductive \"In this model, we have an arbitrary sequence of\nlabeled examples $(x_1, y_1), . . . , (x_T , y_T)$, where only the set $\\\\{x_1, . . . , x_T\\\\}$ is known\". I might be wrong though. Please discuss.\n\nSmall typos and writing\n* line 126: $u_{\\leq k}$ should probably be $x$?\n* line 202: \"Claim claim\"\n* line 235: \"makes $d$ mistakes --> \"makes at most $d$ mistakes\". \n* line 236: What is $m$? Probably $d$?\n\nGiven these weaknesses I would say that this work is rather incremental and has limited novelty. Nevertheless it offers some nice new connections (e.g., threshold dimension) and gives a nice overview (the trichotomy) about bounds which (implicitly or explicitly) exist in previous work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:\nMost of the claimed results are already known or exist implicitly. In particular, all the bounds used in the trichotomy are standard [...]. Even the additional lower bound given by the threshold dimension was essentially covered by an example (called \"sigma_worst\") in [BKM97] (without using the threshold dimension explicitly though). The actual main novelty (which is still a decent and interesting contribution) is the improvement of the lower bound from \nsqrt(log(LD)) to log(LD).**\n\n**Answer:**\nWe believe our paper makes some neat and non-trivial contributions, see our **_General Answer 1_** in the Author Rebuttal section.\n\n\n**Comment:\nThe informal version of Thm 4.1. is slightly misleading. E.g., case 2 If $V C(H)=n$ the rate is still $\\Theta(n)$ instead of $\\log (n)$.**\n\n**Answer:** Following the suggestion of  Reviewer GnLU, we will add a comment that the constants in cases 2 and 3 of the informal trichotomy hide a dependence on the VC and Littlestone dimensions, respectively.  \n\n**Comment:\nI would suggest writing up the bounds for a finite instance space $|\\mathcal{X}|=n$ as corollaries. This might be interesting for various settings (e.g., node classfication) and guide the intuition of the reader.**\n\nInteresting suggestion! We are happy to do add this to the paper. Are there any references or specific examples that you have in mind? Were you perhaps thinking of something like Herbster, Pontil & Wainer \"Online learning over graphs\", or something else?\n\n**Comment:\nI am not sure referring to the setting here with the sequence $\\left(x_1, \\ldots, x_n\\right)$ known in advance to the learner as \"transductive\" is the best idea. Transductive typically refers to the set (without knowing the order) $\\\\{x_1, \\dots, x_n\\\\}$ to be known.**\n\n**Answer:** Thank you for pointing this out! There appears to be some ambiguity in the literature regarding which of these settings should be called \"transductive\". For instance, Syrgkanis, Krishnamurthy and Schapire (http://proceedings.mlr.press/v48/syrgkanis16.pdf) write of \"a transductive setting (Ben-David et al., 1997) in which the learner knows the arriving contexts a priori, or, less stringently, knows only the set, but not necessarily the actual sequence or multiplicity with which each context arrives.\" We agree that it is better to avoid this ambiguity. To that end, we will qualify the name used in our paper, distinguishing between a \"sequence-transductive setting\" and \"set-transductive setting\" or something similar. Suggestions for names are welcome!\n\n**Comment:\nEssentially the results (as most such online learning papers) leave the gap between $VC+\\log n$ and $VC \\cdot \\log n$ open. Do you have any ideas how to close this gap? Sure you state that both bounds are tight on specific instance sequences, but maybe there is a different combinatorial parameter (probably depending on the particular sequence?) interpolating between \"+\" and \"\\cdot\" allowing to get instance-dependent tight bounds.**\n\nWe agree that this is an intriguing question. We don't know the answer, and we intend to continue investigating this in future worsks. \n\n**Comment:\nYou briefly discuss some issues in the multi-class case with $|\\mathcal{Y}|=\\infty$. However there is the recent work by Brukhim et al using the DS dimension to characterize multi-class learnability even if $|\\mathcal{Y}|=\\infty$. Do these results apply in your setting by swapping the Natarajan dimension with the DS dimension?**\n\n**Answer:**\n\nExcellent question! It is indeed interesting to note that the **_DS dimension does not characterize learnability_** in the transductive online learning setting. Here is a counterexample: for any natural $n$, we construct a hypothesis class $\\mathcal{H}$ that has DS dimension $1$, but the adversary can force $M(\\mathcal{H},n)=n$ mistakes. The class is defined as follows. Let $\\{x_0,\\dots,x_{n-1}\\}\\subseteq \\mathcal{X}$ be distinct instances. Consider a complete binary tree of depth $n$, such that for each $i \\in \\{0,1,...,n-1\\}$, all the nodes at layer $i$ of the tree (i.e., at distance $i$ from the root) are labeled with instance $x_i$, and each edge in the tree is labeled with a unique label (that does not appear anywhere else in the tree). Let $\\mathcal{H}$ be a set functions that shatters this tree. Observe that the adversary can select the sequence $(x_0,\\dots,x_{n-1})$ and force $n$ mistakes. We now argue that the DS dimension of $\\mathcal{H}$ is $1$.\n\nAssume for contradiction that there exists a $2$-pseudocube for $\\mathcal{H}$ in the DS sense. Namely, there exists a collection of vectors of length 2, $C = \\{((x_i^1,y_i^1),(x_i^2,y_i^2)): i \\in I\\} \\subseteq (\\mathcal{X}\\times\\mathcal{Y})^2$ such that each vector is realizable by a function in $\\mathcal{H}$, and for each $v = ((x_i^1,y_i^1),(x_i^2,y_i^2)) \\in C$ and $j \\in \\{0,1\\}$ there exists $\\tilde{v} = ((x_i^1,\\tilde{y}_i^1),(x_i^2,\\tilde{y}_i^2)) \\in C$ such that $y^j_i = {\\tilde{y}_i}^j$ and $y_i^{1-j} \\neq \\tilde{y}_i^{1-j}$.\n\nFix $j$ and a pair $v, \\tilde{v}$ that agree on the label of $x_i^j$ and disagree on the label of $x_i^{1-j}$. Choose $v$ and $\\tilde{v}$ that $x_i^j$ appears deeper down in the tree than $x_i^{1-j}$ does (this is possible because $C$ is a pseudocube). Because all the labels in the tree are unique, if two functions agree on the label for the deeper node $x_i^j$, then they must also agree on the label for the less deep node $x_i^{1-j}$. This is a contradiction to the assumption that both $v$ and $\\tilde{v}$ are realizable by $\\mathcal{H}$.\n\n**Comment:\nIs the log(LD) lower bound best possible? I.e., are there specific examples where this is tight (meaning, same upper bound).**\n\nExcellent question. We have an idea that could potentially yield an $\\sqrt{\\mathsf{LD}}$ upper bound, but it is quite complex and would justify an entirely new paper (if it works). Even if that proof works, the gap between the upper and lower bounds would still be large.  \n"}]

Author rebuttal:
**General Comment 1:**

**A recurring comment is that the technical contribution of the paper is not substantial enough (e.g., Reviewer gZ3U: “the main result of this work follows rather easily from prior works”).**

**General Answer 1:**
 -  First, we believe that our trichotomy (Theorem 4.1) is a meaningful conceptual contribution. As one reviewer pointed out, “Such trichotomy has been identified in the recently introduced setting of universal learning [BHMvHY2021] [...] this is the first paper to note such trichotomy in any variant of online learning model”. We feel that this result uncovers an elegant picture of the landscape. We believe it is neat and didactic enough that it could, for instance, be taught in an undergraduate course that covers online learning. The community would benefit from having this published.
 - That being said, the proof of the trichotomy does include a technical contribution that is not entirely trivial. Specifically, the lower bound in item 2 of the trichotomy uses the lower bound that follows from the threshold dimension (Theorem 3.3 and Claim 3.4). One reviewer called this a “nice new connection”.
 - On top of that, the proof of the multiclass trichotomy (Theorem B.2 in the supplementary materials) involves considerably more technical work. First, it requires identifying the “correct” definition of threshold dimension for the multiclass case (Definition A.2). Next, the proof of the log(n) lower bound (Theorem A.5) uses a result from Ramsey theory (Lemma A.7), which would probably not be the first thing that comes to mind for most people. We did not emphasize this technical aspect in the main body of the paper because we focused on the conceptually-clean message of the trichotomy, but we feel that the appendix constitutes a worthy technical contribution.
 - Finally, the proof of our $\log(\mathsf{LD}(\mathcal{H}))$ lower bound (Theorem 3.1) is both non-trivial, and improves on the previous result of Ben-David, Kushilevitz, and Mansour from 26 years ago. As one reviewer wrote, “the proof technique of Theorem 3.1 is novel and differs from standard lower bound techniques in online learning literature.” We maintain that this result does not follow “rather easily” from prior works.

Taken together, we believe that these contributions merit accepting the paper to NeurIPS.


Meta-review: The decision on this paper is difficult.

I will begin with the positives. First, the conceptual contribution from the trichotomy is valuable. From a technical standpoint, the main innovation is Theorem 3.1, and there is some novelty in the proof of Claim 3.4 as well.

There is also one (in my opinion) weakly positive point. The authors mention as a plus the didactic aspect. I recognize the importance of pedagogy, but I don’t see that as an argument for publication at a top venue (the teaching aspect is like a "cherry on top"). Of course, there is value in simplicity as it can make it easier for more complexity to be added.

Next, the downsides. Other than the results mentioned above, the proofs are straightforward. While there are results for the multiclass case, the technical innovations involved are described only in the appendix, and so it is difficult properly account for these innovations in evaluating the paper.

I have carefully avoided the discussion of the results for the agnostic setting, along with the DS dimension example. I will discuss those now; they are very important for the decision. The authors developed results for the agnostic case late in the review process (during discussion with the reviewers). These results complete the story of the paper and, if their addition to the paper is permissible at this late stage, significantly improve the outlook for this paper. Therefore, let us consider whether these new results should be considered. First, two reviewers are not in favor of considering these new results, while one reviewer is in favor, and (I believe) another also in favor. I will also weigh in. The results for the agnostic setting use standard techniques; hence, they are not that novel (this is a good thing, in this case, as including these results is more palatable). The DS dimension example also looks like a smaller addition (at the level of discussion). which makes me more more willing to go along with the inclusion of this example.

I think this work is interesting, and it carries enough strength for acceptance at NeurIPS.
Decision: Accept (poster)