Optimal Mistake Bounds for Transductive Online Learning
Authors: Zachary Chase
Steve Hanneke
Shay Moran
Jonathan Shafer
Venue: NeurIPS 2025 oral ()
Keywords: Online Learning
Primary area: theory

Abstract: We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. We prove that for every concept class $\mathcal{H}$ with Littlestone dimension $d$, the transductive mistake bound is at least $\Omega(\sqrt{d})$. This establishes an exponential improvement over previous lower bounds of $\Omega(\log \log d)$, $\Omega(\sqrt{\log d})$, and $\Omega(\log d)$, respectively due to Ben-David, Kushilevitz, and Mansour (1995, 1997) and Hanneke, Moran, and Shafer (2023). We also show that our bound is tight: for every $d$, there exists a class of Littlestone dimension $d$ with transductive mistake bound $O(\sqrt{d})$. Our upper bound also improves the previous best known upper bound of $(2/3) \cdot d$ from Ben-David et al. (1997). These results demonstrate a quadratic gap between transductive and standard online learning, thereby highlighting the benefit of advanced access to the unlabeled instance sequence. This stands in stark contrast to the PAC setting, where transductive and standard learning exhibit similar sample complexities.

Optimal Mistake Bounds for Transductive Online Learning
Zachary Chase Kent State University zchase20kent.co edu
Steve Hanneke Purdue University steve. www.hheegmani.lccoooomo com
Shay Moran
Jonathan Shafer MIT shaferjo@mit.cm edu
Departments of Mathematics, Computer Science, and Data and Decision Sciences Technion Israel Institute of Technology; Google Research smoran@technion ac. i1
Abstract
We resolve 30-year-old open problem concerning the power of unlabeled data online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mistake bound is characterized by the Littlestone dimension d of the concept class H (Littlestone, 1987). We prove that in the transductive setting, the mistake bound is at least 22 (Vd). This consti- tutes an exponential improvement over previous lower bounds of (ollg log(d)), 2 (oog(d) and (2(log(d)), due respectively to Ben-David, Kushilevitz, and Mansour (1995, 1997). and Hanneke, Moran, and Shafer (2023). We also show that this lower bound is tight: for every there exists class of Littlestone dimension d with transductive mistake bound O (vr) Our upper bound also improves upon the best known upper bound of (2/3) d from Ben-David et al. (1997). These results establish quadratic gap between transductive and standard online learning, thereby highlighting the benefit of advance access to the unlabeled instance sequence. This contrasts with the PAC setting, where transductive and standard learning cxhibit similar sample complexities.
Introduction
The transductive model is basic and well-studied framework in learning theory, dating back to the early works Vapnik. has been investigated both in statistical and online settings, and is motivated by the principle that to make good predictions on specific set of test instances, one need not construct a fully general classifier that performs well on the entire domain including points that may never actually appear. Rather, it may be sufficient to tailor predictions for fixed, known set of instances.
This perspective naturally connects to a broader question in learning theory: what is the value of unlabeled data? the transductive setting. the learner is given the sequence of unlabeled test instances in advance and is then required to predict their labels one by one. Thus, the transductive model can be viewed as a natural formalization of learning with unlabeled data: the test instances are known in advance, but their labels are not. The central question is whether such prior access to the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

unlabeled sequence can help reduce the number of prediction mistakes - compared to the standard online model, where the instances arrive and are labeled one at a time.
Recall for instance that in the standard PAC! model of supervised learning, there are cases where access unlabeled data is not helpful. Indeed, the "hard population distributions" used prove the standard VC² lower bound are constructed by taking fixed and known marginal distribution over a VC-shattered set. Namely, the cases that are hardest to learn in the PAC setting include ones where the learner knows the marginal distribution over the domain, and can therefore generate as much unlabeled data as it wishes. And yet, in those cases, access unlabeled data provides no acceleration compared to an algorithm (like ERM*) that does not use unlabeled data.
Seeing as unlabeled data is often lot easier obtain than labeled data, there have been considerable efforts to understand when and to what extent can access to unlabeled data accelerate learning."
In particular, it is natural to ask, for which plausible models of learning is access to unlabeled data beneficial? Online learning (Littlestone, 1987) is perhaps the model of learning that most- extensively studied in learning theory after the PAC model and its variants. Therefore, the general question considered in this paper is:
Question 1. Quantitatively, how much (if at all) is access to unlabeled data beneficial for learning in the online learning setting?
This question is naturally instantiated by comparing transductive online learning - where the learner has advance access to the full sequence 21, .2,....... .., F. Ta, of unlabeled instances with standard online learning, where no such access is given. This perspective has also been adopted in prior work: for example, Kakade and Kalai (2005), Cesa-Bian Bianchi and Shamir (2013), and Hoi, Sahoo, Lu, and Zhao (2021) (Section 7.3) all describe transductive online learning as setting in which the learner has access to "unlabeled data". We thus refine the question above follows:
Question Quantitatively, how much (if at all) is learning in the transductive online learning setting easier than learning in the standard online learning setting? Specifically, how much is the optimal number of mistakes in the transductive setting smaller than in the standard setting?
Addressing this question, our main result (Theorem 1.1) states that the optimal number of mistakes in the transductive setting (with access to unlabeled data) is at most quadratically smaller than in the standard setting (without unlabeled data). Furthermore, there are hypothesis classes for which a quadratic gap is achieved.
1.1 Setting: Standard vs. Transductive Online Learning
Standard online learning (Littlestone, 1987) is a zero-sum, perfect- and complete-informatiin game played over n rounds between two players, a learner and an adversary. The game is played with respect to a domain set X' and a hypothesis class H C {0, 10, (consisting of functions X' + {0, 1}), where n. X and H are fixed and known both players. The game proceeds in Game 1. The number of mistakes for learner L and an adversary A is MaaaHH L. A) = Ktt E [n] de * vc We are interested in understanding the optimal number of mistakes, which
Mstal H)) = sup inf sup Matd (H, n, L,
NEN LEC AEA
where A and L are the set of all deterministic adversaries and learners, respectively.'
Probably Approximately Correct. For an exposition of the standard terminology and results mentioned in this paragraph see, e.g., Shalev-Shwartz and Ben-David (2014).
Sopnik-Chhevvnennii.
"Emirrical Risk Minimization.
*The literature semi-supervised learning is surveyed in Joachims (1999); Zhu (2005); Zhu and Goldberg (2009); Zhu (2010); Chapelle, Schölkopf, and Zien (2006). Theoretical works on the topic include Benedek and Itai (1991); Blum and Mitchell (1 (1998); Ben-David, Lu, Pál, and Sotáková (2008); Balcan and Blum (2010); Darnstädt, Simon, and Szörényi (2013); Göpfert, David, Bousquet, Gelly, Tolstikhin, and Urner (2019).
'Because the adversary selects y: after seeing ú.. randomness is not beneficial for either party, and we assume without loss of generality that both the learner and the adversary are deterministic. As is common in learning theory, we avoid questions of computability and allow the learner and adversary to be any function. See Section A for formal definitions of A and L.
2

---

For each round 1, ,
a. The adversary selects an instance 24 E X' and sends the learner.
b. The learner selects prediction Ye E {0, 1) and sends it to the adversary.
c. The adversary selects a label y/ {0, } and sends it the learner. The selected label must be realizable, meaning that 3h H. vi E [t]: h(z,) = yi-
Game 1: The standard online learning setting.
The adversary selects sequence Tı, .2..... ... 1, ,,.......
X and sends it to the learner.
For each round
a. The learner selects a prediction dt E {0, 1} and sends it to the adversary.
b. The adversary selects a label y/: E {0, 1) and sends it to the learner. The selected label must be realizable, meaning that 3h H E [4] h(x;) = yi-
Game 2: The transductive online learning setting.
is well known that (H) is characterized by the the Littlestone dimension, namely, Mata (H) = LD(H) (see Theorem A.7 and Definition A.6).
The transductive online learning setting (Ben-David et al., 1995, 1997) is similar, except that the learner has access to the full sequence of unlabeled instances in advance. Namely, in Game 2. The optimal number of mistakes for the transductive setting defined exactly as before,
Mr nu, L, A) Kt [n]: ú. 3. and (H) sup inf sup Mr n, L, A),
wEN LEC AEA
with the only difference between the standard quantity Mad (H) and the transductive quantity Mrr being in how the game is defined.
1.2
Main Result
Notice that for every hypothesis class H. MH) S Ms)(HH. Indeed, in the transductive setting the adversary declares the sequence x at the start the game. This reduces the number of mistakes because the transductive adversary is less powerful (it cannot adaptively alter the sequence mid- midd-,ame,, and also because the transductive learner is more powerful (it has more information).
While for some classes (H) Maa (H), we study the largest possible separation. The best previous lower bound on My. due to Hanneke, Moran, and Shafer (2023), states that for every class H.
(H) 2 (dlog(d),
where d = Mstal (H). In the other direction, Ben-David et al. (1997) constructed? a class H such that Mst(H) and (H) < dd. This left exponential gap between the best known lower and upper bounds on Mr. namely 12(log d) versus dd. Our main result closes this gap: Theorem 1.1 (Main result).
For every hypothesis class H C 10,
Mb(H) =
where MMd (HL).
'One could also define intermediate setting, where the adversary is less powerful because it must select the sequence the start of the game and cannot change it during the gameplay, but the learner does not have information because the adversary only reveals instances in sequence one at setting. However, this intermediate setting would not model the learner having access to unlabeled data. Their class consists of all disjoint unions of (dd) functions from specific constant-size sized class.
as in the standard

---

On the other hand, for every d there exists hypothesis class H. with Msta(H) = d and
(r) 0 (Vd).
This result is stated in considerably greater detail in Theorems B.1 and D.1.
1.3 Related Works
The notion of transductive inference more efficient alternative inductive inference in statistical learning theory was introduced by Vapnik (1979, 2006); Gammerman, Vovk, and Vapnik (1998); Chapelle, Vapnik, and Weston (1999). The online learning setting is due to Littlestone (1987), who also proved that the optimal number of mistakes is characterized by the Littlestone dimension (see Theorem A.7).
The transductive online learning setting studied in the current paper, was first defined by Ben-David, Kushilevitz, and Mansour (1995), who used the name worst sequence off- off-line model. Among other re- sults, they showed a lower bound of S2(log log(d) on the number of mistakes required to learn a class with Littlestone dimension d. The authors subsequently presented an exponentially stronger lower
bound of 52 (log(d) in Ben-David, Kushilevitz, and Mansour (1997). However, understanding
[2 (Tg((d) 2d/3 remained
where the optimal number of mistakes is situated within the range an open question.
Kakade and Kalai (2005) presented an oracle-efficient algorithm for the transductive online learning setting, and may have been the first to that name. Their result was subsequently improved upon by Cesa-Bianche and Shamir (2013).
The present work is most similar to that of Hanneke, Moran, and Shafer (2023) which, among other results, gave a quadratically--trong
mistake lower bound of ([log(d) for classes with Littlestone dimension d in the transductive online setting. The proof of our lower bound utilizes some of their ideas, but yields a quantitative improvement by combining with some new ideas.
Hanneke, Raman, Shaeiri, and Subedi (2024) studied a setting of multi-class transductive online learning where the number of possible labels is unbounded.
2 Technical Overview
In this section we explain some of the main ideas in our proofs. Formal definition appear in Section A. Full formal statements of the results, as well as detailed rigorous proofs, appear in Sections B to D.
2.1
Paths in Trees
We make extensive use of the following notion. Given a perfect binary tree Ta of depth d, every function
Ta + 1} defines unique path in the tree. The path is a sequence of nodes path(f) = (Zig Ligs... ). as explained in Figure Ic. See Section A for formal definitions.
2.2 Proof Ideas for the Lower Bound
We start with an elementary observation about the adversary's dilemma in the transductive online learning setting. Before round of the game, the adversary selected full sequence of instances I1, ........ Ln E X. and assigned some initial labels y1, 3/........ .,, Vt-1 E {0, 1}. At the start of round t, the adversary must consider the version space,
Hi {h E H: (Vi
1): Mxx)) = y:)}
If all E H4 assign h(xz) = for some b E {0, 1}. then the adversary has no choice but to assign the label y/2 b. Otherwise, the adversary can force mistake time t. Namely, after seeing the learner's prediction i., the adversary can assign mistakes by 1.
Dr. incrementing the number of learner
But "just because you can, doesn't mean you should". If the adversary is greedy and forces a mistake at time t, they may pay dearly for that later. As an extreme example, consider the case where there

---

63
24 155 26
(a) A perfect binary free of depth 2. Each node is labeled by element of the domain X. These labels need not distinct (e.g., it possible that æ1 = 26). au is the rool of the tree, Zo, æ1 and zy are internal nodes, and ..,.... Do are leaves.
(b) A function f X ++ {0, 1] assigns binary label to each node in the tree, represented here by edges with arrowhead tips. This figure depicts the function f(x,) = L(i & {2, 3}). (Note that the gray dots (o) in the figure are purely pictorial detail. In this paper they not considered nodes leaves of the trec.)
(c) Every function f X' + {0, 1} defines a path
(d) In this paper without loss of generality, we identify domain elements o; that are assigned to nodes with strings. The root is identified with the empty string A, and for each pair of nodes u, such that is the b-child 1)). we have
naming convention where.
in the tree, which is sequence uo, u1, u2..... Md-11 where is the root, is the depth of the tree, and for each [d - 1]. u, is the b-child of u with b f(:-1)) E {0, 1}. This figure shows that the func- tion f from Figure 1b has pfth(f) = (Iro, 22, xts), depicted in red. In particular, 22 is 'on-path" for f. but zg 'off-path' for
of (for denotes string concatenation. (Because x; 's may not be distinct, a domain element may be identified with more than one bit string.)
where 'o'
Figure I: Paths in trees.
a single hn E Hr that assigns hi (xx) = 1, and all other functions h H. assign l(xz)) = 0. If the learner selects subsequent times s will be H., = {hr}, and the adversary will be prevented from forcing any further mistakes.
and the adversary forces mistake at time f, the version space at all
natural strategy for the adversary therefore be greedy up a certain limit. Namely, each time the adversary computes the ratio*
kh E He h(x1) 1H1
[74
If r, E -= for some parameter s > 0 ("the version space is not too unbalanced"), then the adversary forces mistake. Otherwise, the adversary assigns the majority label, i.e., y/ 1(; 2 1/2). This ensures that the version space does not shrink too fast:
If no mistake is forced, then [He- 1| 2 (1 e) |He,, and
If mistake is forced, 1441| 2 [7,]-
*For a class H. of Littlestone dimension d. the adversary will use only a subset of 74 of cardinality 2 that shatters Littlestone tree of depth d 1. So without loss of generality, we assume that H. has cardinality 2 (in particular, H is finite), and the ratio well-defined.
5

---

In particular, at the end of the game, the version space Hn+1 is of size
|Ha+1 2 EM - --= [H] 2 e (1-E)) (1-
where M is the number of mistakes that the adversary forces and n is the length of the sequence. The class has size (7( 2 2d because LD( = d, and by removing functions from the class if necessary (which can only make learning easier), we may assume without loss of generality that [7| = 24. Namely, the class precisely shatters Littlestone tree of depth d - such that for every assignment of labels to a root-to-leaf path in the tree, the class contains exactly one function that agrees with that assignment (see Definition A.6 for detail).
Notice that we have not yet specified how the adversary selects the sequence æ, While the adversary's labeling strategy is extremely simple (determined by the ratio r; and the prediction (t). constructing of the sequence x: requires some care, to ensure that it has the following two properties:
Property I: The length n of the sequence satisfies n ( and
For every sequence of predictions Ú1,.... In selected by the learner, the resulting sequence of labels y...... Un selected by the adversary consistent with some function E H such that x contains all the nodes in path(h).
Property II:
These properties can be achieved by carefully simulating all possible execution paths of the adversary.
Observe that if path(h) (u,...., ug) then the sequence of labels h(u)), (uu))..... h(ua) uniquely identifies the function h within the class H. Hence, Property II and the assumption [7|| 2d imply that at the end of the game, the version space Hn+1 has cardinality
1 1.
Combining Property I (n 20((v)), Eqs. (1) and (2), and choosing e 2 22- -0(()) gives
1 2 M (1 =)" 2d 2 2 (
which implies M = 22 (d as desired.
M-
2.3 Proof Ideas for the Upper Bound
In this section explain the main ideas in the proof of Theorem D.1, which states that for every E N, there exists class of Littlestone dimension d that is learnable in the transductive online setting with mistake bound of O
Of course, not every Littlestone class satisfies this property. For instance, the set of all functions [d] {0. 1} has Littlestone dimension d, but the adversary can force the learner to make d mistakes when learning this class in the transductive setting. 10 So our task in this proof is to construct a class
that is especially easy to learn in the transductive setting (i.e., learnable with O (Vd) mistakes), while still being hard (requiring d mistakes) in the standard setting.
2.3.1 Sparse Encodings are Easy to Guess
We start with an elementary observation. Consider the following two bit strings:
Binary: 110101
One-hot: 00000000000000000000000000000000
Both of these strings encode the number 53. However, one of the encodings is much easier to guess than the other: suppose
tasked with guessing the bits in an encoding of an integer between and 26 1. We guess the bits one at a time, and after each guess, an adaptive adversary tells us whether guess correct.
Recall that the path of function h is depicted in Figure 1c, and detined in Definition A.5.
10ee adversary simply selects the sequence x = (1, 2, 3, ...., d). and for each x,, the adversary forces a mistake by selecting = 1- g:. The adversary's choice of labels is realizable because we are working with the class of all function
{0, 1}.

---

Now, if the bit string is a binary encoding, the task is hard. Each bit can either be 0 or 1, regardless of the values of the previous bits, and so the adversary can force mistake on every bit. On the other hand, if we know that the string is a one-hot encoding, there exists an attractive strategy - always guess This ensures that we will make at most mistake.
Note that at the end of the guessing game we have learned the same amount of information (for a number between 0 and 2 1, we learned bits of information), but the number of mistakes is very different (n mistakes vs. mistake).
2.3.2 Construction of the Hypothesis Class
We now describe a construction of a hypothesis class that is easy to learn in the transductive setting, using the idea of a sparse encoding. Recall that class H. has Littlestone dimension at least d (Definition A.6 in Section A) if there exists a Littlestone tree of depth d 1 such that for every b E {0. 1 there exists h = ha E H. such that the values on the path of h agree with b. More formally, Vi E [d]: h(bb;)) = 6,. and in particular path(h) = (A, b.g1, b=2, bg3.... .......... bga-1). Thus, when constructing a class that shatters a specific Littlestone tree of depth d 1, we need to define 24 functions/ hhg E {0. 1 For each function hg, the on-path values of the function are fixed (fully determined by b), while for the remaining values there is complete freedom (for the nodes that are off-path we may assign any values (u( E {0, 13).
Perhaps the simplest way to construct a class of Littlestone dimension d is simply to assign all on-path values as required, and assign 0 to all other values. Namely, if is a prefix of then hu(u) = b and otherwise hu( 0. In sense, this is the 'minimal' class of Littlestone dimension d for specific Littlestone tree." 1I
Observe that the 'minimal' class does not have the desired property of being easy to learn in the transductive setting. 12 However, a certain variation of the 'minimal' class that embeds a sparse encoding does satisfy the requirement. In this variation, on-path value of the function hú, are assigned as they must (as determined by b), while the off-path values are sampled independently using a biased coin, such that each of them is 0 with high probability, but has small probability of being 1. The probability is chosen carefully so that the class satisfies some simple combinatorial properties, as described further in Section 2.3.6 and Lemma D.2.
2.3.3 Naive Learning Strategy
We now explain in broad strokes how the probabilistic construction of the hypothesis class in Section 2.3.2 is useful for learning with few mistakes in the transductive setting.
Notice that when predicting labels for the 'minimal' class with nodes in breadth-firs first order, the learner knows at each step whether they are labeling an on-path off-path node, because the learner has already seen the correct labels for all ancestors of the current node. For off-path nodes, the learner knows that the true label is O, so it never makes mistakes on off-path nodes, but it also gains no new information when the true labels for off- -atth nodes are revealed. No risk, but no reward either. Instead, all the information about the true labeling function is revealed only at on aa-path nodes, where the adversary has complete freedom to assign labels and force mistakes. That's 's why the adversary can force d mistakes
For the andomly-chosee class, when predicting labels for off-path nodes, the learner may still safely predict a label of 0. But the reasoning for this is quite different. Conceptually, every off- path label is part of a sparse codeword that identifies the correct labeling function." Because the coin is biased, each bit of the codeword is easy to guess (it is likely to be 0), but every time that the adversary reveals that the true label for an off-path node is indeed O, the learner gains a small (nonzero) amount of
1I More formally, this is a class with a minimal number of nodes labeled 1.
Thee adversary declare sequence x consisting of all the nodes in the tree in breadth-first order, and then force d mistakes - one mistake in each layer (depth) of the tree. Specifically, regardless of how the adversary selects the labels, for each E [d] there exists a node u, at depth i that is on-path. When it is time for the learner to predict a label for this u, the learner knows that u, is on on-path because it has seen the correct labels for all the ancestors of u:. However, the adversary has the freedom extend the path arbitrarily the left the right, and can therefore force a mistake on ui.
Thee coin- flips for off- path labels are all independent. For example, if X is a set of nodes all of which are off pat-path for subset H of the hypothesis class, then the random variables (h(x): h E H, E X) are ii.d.
7

---

information about the true labeling function. Additionally, when the adversary selects an off- off-path label of that reveals a lot of information about the true labeling function (such labels are rare in the hypothesis class), and therefore the adversary cannot force many off-path mistakes. Overall, the information about the true labeling function 'smeared' throughout all labels of the tree (Os and 1s, on-path and off- off-path).. 14
Thus, the naive general strategy for the learner when using the probablissiially-conssene class is to learn most of the information about the true labeling function by observing off- labels. By the time the learner reaches an on-path node, it hopefully has already learned enough about the true labeling function in order to make a good prediction on that node.
However, making this general strategy work requires overcoming some very substantial obstacles:
1. Recall that in the transductive setting, the adversary can present the nodes of the tree in any order of its choosing - it does not have to present the tree in strategy works only if the learner sees many off- nodes before it sees most on-path nodes. But what happens if the adversary decides to present many on-path nodes near the beginning of the sequence? To handle this, the learner incorporates a strategy we call 'danger zone minimization', as described in Section 2.3.4.
order. The naive
2. Another, equally problematic, issue also arises from the fact that the sequence presented by the adversary might not be in breadth-fiss order. Recall that breadth- first order 15 has the property that for every node u the sequence, all the ancestors of appear before in the sequence. This means that by the time the learner needs to predict a label for u, the learner knows whether is on-path or off -ff-path for the true labeling function. But what happens the adversary presents u before some of u's ancestors? Or omits some of u's ancestors from the sequence altogether? In this case the learner doesn't 't know if u is on-path or off-path, and this presents a double hazard. One hazard is that the leaner doesn't 't know what label to predict for u - if u is off-path, the learner can simply predict 0, but if it is on-path it must do something more elaborate. The second hazard is that, after seeing the correct label for it is not clear what the learner can infer from it. If u is off-path, its label should be interpreted part of sparse encoding of the labeling function. But if u is on- on-path, the interpretation must be entirely different. To overcome this challenge, the learner incorporates a strategy we call 'splitting experts', described in Section 2.3.5.
3. Limiting off-path mistakes. Thanks to the coin's 's bias, most off-path nodes have a true label of O. Nonetheless, each function in the hypothesis class still has an expected number of 20(d) off off-path nodes labeled 1, so the learner can afford to misclassify only vanishing fraction of them! To limit the number of mistakes, the learner extracts information from the sparse encoding and executes a 'transition to Halving' strategy, as described in Section 2.3.6.
2.3.4 Danger Zone Minimization
Utilizing information from the 'sparse encoding' of the off-path nodes to make good predictions for on-p nodes requires that the learner first see the true labels for many off off-path nodes. Until that happens, the learner expects to make many mistakes on on-path nodes. However, whether node is on-path or off-path is not fixed in advanced - the adversary may decide this adaptively, in response to the learners predictions.
Danger zone minimization is a strategy used by the learner, to force the adversary to assign few nodes in the beginning of the sequence on-path (otherwise, if initial nodes are assigned to be on-path by the adversary, then the learner will make few mistakes on those nodes). This is analogous to the standard Halving algorithm (Algorithm 7), but instead of minimizing the cardinality of the set of consistent hypotheses (the 'version space'), ) the learner minimizes a subset of the domain (the 'danger zone').
#Furthermore, the labels for most not-too-small subsets of the nodes reveal a lot of information about the correct labeling function - not just for particular subset of nodes. These properties led us to code-name this construction while working on the paper 'everything everywhere all at once" (in reference to 2022 film of that name). This is in contrast to the 'minimal' function, where the information is concentrated entirely the function path. The asymmetry between the 'minimal' class and the probabilistic class similar to that between the hinary and one-hot encodings in Section 2 above. As well as depth-firs first order.
8

---

Concretely, at the beginning of the game the learner initializes set S = {21. 22, 2............................... Ttem } consisting of the first max = (v())) instances in the sequence 2 selected by the adversary. This set represents the "danger zone' nodes in the beginning of the sequence that have not been labeled yet, that might be on on.path, and that are not ancestors of a previously-
on-path node. 16 To predict a label for an instance 24, the learner selects a label y; such that if U is wrong, the danger zone will shrink by at least 1/3. That is, for b E {0, 1). if the set Sp of b-descendants of x; has cardinality |S&| 2 1S//3, the learner predicts it- = b. Then, if the adversary selects y; 1 - b, that implies that all b-descendants of z; are off-patt for the true labeling functions. Therefore, the learner removes all b-descendants of Ty from the danger zone, and the new cardinality is |.S Ss S (2/3) - SS]. This guarantees that the learner can make at most (1og((max)) O O(vi) such mistakes before the danger zone is empty." 17
If neither Sy nor S have cardinality at least |S|/3, the learner predicts ÿ = 0. If yi = 1 and x; is on-path for the true labeling function, then the learner updates the danger zone be So U.S. again shrinking the danger zone by a factor of at most 2/3. Otherwise, if y; = and x; is off--pah, then it was an off-path node labeled (which is rare), and the learner can afford misclassify it (see Section 2.3.6).
2.3.5 Splitting Experts
The danger zone minimization strategy requires that the learner know whether the node being classified is on-path or off- for the true labeling function. However, if u appears in the sequence before some of its ancestors, the learner does not know this. To overcome this difficulty, the learner implements a variant of the standard multiplicative weights algorithm using splitring experts. This means that initially there is single expert executing danger reached for which danger zone minimization requires knowing whether u is on-path or off-path and that information is not yet evident, each expert is split into two experts, one of which continues the execution of danger zone minimization under the assumption that u is on-path, and the other under the opposite assumption. Thus, at each point in time, there exists precisely one expert for which all
minimization. When a node is
path-related assumptions are correct, and therefore that expert will make at most O (Vd mistakes. The multiplicative weights algorithm guarantees that the overall number of mistakes will be linear in the the number of mistakes of the best expert, i.c., O ((vd)
2.3.6 Transition Halving
The hypothesis class is engineered such that it satisfies the following property: there are at most (v(V)) functions the hypothesis class that agree with any set of mmx = 20(V)) labels, or that agree that set of O Vd) nodes are all off-path and labeled (this follows from Lemma D.2).
Therefore, once the true labels for the first max instances I1, T2, tmae have been revealed, or once @ (va) off-path labels of 1 have been revealed (whichever happens first), the learner can transition to halving: stop doing danger zone minimization, and instead predict the labels for the remaining nodes using the standard Halving algorithm (Algorithm 7) on the subset of the hypothesis class that survived. Halving on (vV)) functions is guaranteed to make at most O (V)) mistakes (Fact 1.
However, seeing as the learner lacks information on which nodes are off off-,,ah, it uses experts, and each expert maintains different path-related assumptions. Thus, each expert decides separately at which point to transition to Halving. The unique expert that makes only correct assumptions will
1Iff is ancestor of some on-path node and e is b-descendant of u for E (0, 1). then the true label for must be 17 Once the danger zone is empty. the learner cannot make any further on- on-path mistakes within the prefix
F1, 22 ... Brax. And will make most 0 (Vdd) mistakes on the remaining nodes 11tm++1 Timo +2..... explained Section 2.3.6.
18 Because on on-path nodes must be either be descendants or ancestors of æ,, and the definition of the danger zone does not require that it contain ancestors of nodes that have been labeled.

---

transition 'at the right time'. That expert will make at most O (vd) mistakes during danger zone minimization, and then at most O OVV additional mistakes during halving.
2.4 Some Intuition for the Quantity vd
We briefly sketch where the quantity vd arises from. This is back-of-the-envelope calculation without proof, intended purely as an aid for intuition. Suppose we assigned off-path labels of 1 with
probability 2 instead of 2 2- vd Consider sequence I1,...,2 In of n d/2k 2k leaves. For any sequence of labels 1/1-
Un {0, 1}, taking EiE(n) M/e there exist roughly
2 "2" (1 (1-2-#) " 2a (2"")"
functions in the class for which these leaves are off- faff-path and which agree with the labels yı.... Vn- Therefore, the adversary can force at least n Q)d/k k) mistakes.
Similarly, for the sequence #1,-.... Fin consisting of all the nodes in the tree of depth at most k/2 in breadth-first order, the adversary can force mistake on every on-path node while assigning label of to all off-path nodes, for a total of k/2 mistakes. This is true because for any assignment of on- on-path labels, the fraction of functions which agree with the on-path labels that assign label of 0 to all 24/2 off-path nodes is roughly (1 ) there exists function in the class that agrees with that labeling and assigns 0 to off-path nodes.
~ 1, so in particular for any labeling of the on-path nodes
Therefore, for any k. obtain lower bound of C + k) the number of mistakes. For any k. + 2 vd, giving lower bound of Ω (Vi). Choosing k: vd minimize the lower bound will fact yield matching upper bound of O (Va). as we show in this paper. This completes our overview of the upper bound.
3 Directions for Future Work
Following are some interesting open questions:
1. Does there exist an efficient learning algorithm that achieves the O (vv upper bound of Theorem D.1? One needs be careful about the definition of efficiency here, but one possible formalization is as follows. Does there exist learning algorithm A and sequence of classes H., Hg,... such that for every d N:
LD(Ha) d, and
Given as input the index and a sequence Pi....,Ins the algorithm runs in time poly(d,n) n) and makes most O ((vd) mistakes assuming the labels are realizable by Ha.
2. Is there a tradeoff between the cardinality of the domain and the upper bound on the number of mistakes? We used a domain of size roughly 2d in order to obtain upper bound of O (vd) Is it possible to get the same bound with domain of size poly(d)?
3. Obtaining more precise asymptotics; for example, is there (an explicit) constant a > 0 such that the optimal transductive mistake bound is (a + o(1) /d?
Organization
Complete rigorous mathematical details are deferred to the appendices. Formal definitions appear in Section Formal statements and proofs for the lower bound and upper bound appear Section and Section D, respectively. Optimal sequence length is discussed in Section C.
10

---

Acknowledgments and Disclosure of Funding
ZC is supported in part by NSF EnCORE inst (award #2217058) and by Shachar Lovett's Simons Investigator Award (#929894). SM is Robert Shillman Fellow: he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION, 101039692). JS is supported in part by NSF CNS-2154149, an Amazon Research Award, and by Vinod Vaikuntanathan's Simons Investigator Award.
Views and opinions expressed are however those of the author(s) only and do not necessarily reflcct those of the European Union the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
Maria-Florina Balcan and Avrim Blum. A discriminative model for semi-supervised learning. J. ACM, 57(9):1:1-11:46, 2010. N0f:10.1445/77059111770666 URL https: /ttp:////0..../......
1145/1706591 0156/77766991.7069999 1706599.
Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. Online learning versus offline learning. In Paul M. B. Vitányi, editor, Computational Learning Theory, Second European Conference, EuroCOLT '95, Barcelona, Spain, March 13-15, 1995, Proceedings, volume 904 of Lecture URL
Notes in Computer Science, pages 38-52. Springer, 1995. https://doi. org/10. 10. 1007 00077/3-40---- 140-59911-22_16
Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. Online learning versus offline learning. URL https://doi org/10.
Mach. Learn,, (95))5556 1997. 111.1100//1111444455010000000
1023/A:100746590775
Shai Ben-David, Tyler Lu, Dávid Pál, and Miroslava Sotáková. Learning low-density separators.
CoRR, abs/0805.289) 2008. URL http:// www.oogg//////aeeeoeeoooeoeeeo/o aaaaabb/00005 2891.
Gyora M. Benedek and Alon Itai. Learnability with respect to fixed distributions. Theor. Comput. Sci., 86(2):377-390 1991. 0001100..01600344339559191 1016/0304-3977 (91) (90000066600 90026-X.
URL https: http::///oooor//././/
Avrim Blum and Tom M. Mitchell. Combining labeled and unlabeled data with co-training. In
Peter L. Bartlett and Yishay Mansour, editors, Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT 1998, Madison, Wisconsin. USA, July 24-26, 1998, pages 92-100. ACM, 1998. doi: 15521144///9922211 279992. URL https: org. http:/1..1111/222 1145/279943 279962.
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Ychudayoff. A theory of universal learning. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC 2021: 53rd Annual ACM SIGACT Symposium Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 532-541. ACM, 2021. 150:1000145/3346225533444 //doi.org//i 1tt///0011440 1145/34006325 3451087.
URL https:
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-194. Springer, 2013. doi: 10. 10.0077/97 642-41136-6 16. URL atttp:://do org/ 10. 1007 9978/97833303 3- 2--42-440 11122-4116----6 6_16.
Olivier Chapelle, Vladimir Vapnik, and Jason Weston. Transductive inference for estimating values of functions. In Sara A. Solla, Todd K. Leen, and Klaus-Robert Müller,, editors, Advances in Neural Information Processing Systems 12, [NIPS Conference, Denver, Colorado, USA, November 29 December 4, 1999], pages 421-424 The MIT Press, 1999. URL http: //ttt:://ppppr/ cc/ paper/ / http:/1999tttatatec www.tttaannnneeeeinnnee www.:/frrrneroooooooeeeeenninnna
Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien, editors. Semii-Sueerviiee Learnig The
MIT Press, 2006. ISBN 9780262033588, doi: dei.00055..M11PPE5779000330.....
URL
001 0001.
Malte Darnstädt, Hans Ulrich Simon, and Balázs Szörényi. Unlabeled data does provably help. In Natacha Portier and Thomas Wilke, editors, 30th International Symposium Theoreti-

---

Shai Shalev-Shwartz. and Shai Ben-David. ing: From Theory to Algorithms. ISBN 978-1-10-705713-5. cal Aspects of Computer Science, STACS 2013, February 27 March 2, 2013. Kiel, Ger- many, volume 20 of LIPlcs, pages 185-196. Schloss Dagstuhl LeibnizzZentrumm für Infor- matik, 2013.
2013.18 hRt.tttss:/ddo..rrg wtt.l/..og/...23///////////
STACS. STACS.2013.00 2 185.
Alexander Gammerman, Volodya Vovk, and Vladimir N. Vapnik. Learning by transduction. In Gregory F. Cooper and Serafín Moral, editors, UAI 1998: Proceedings of the Four- teenth Conference on Uncertainty in Artificial Intelligence, University of Wisconsin Business School, Madison, Wisconsin, USA, July 24-26, 1998, pages 148-155, Morgan Kaufmann, jsp7 1&smuu=28
1998. URL
Christina Göpfert, Shai Ben- Olivier Bousquet, Sylvain Gelly, Ilya O. Tolstikhin, and Ruth Umner. When can unlabeled data improve the learning rate? In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 1500-1518. PMLR, 2019. URL http:// http:///poceeeingss. mlr. aalr.prese ptwss/v99/ http////ppprtta//e/ html.
Steve Hanneke, Shay Moran, and Jonathan Shafer. A trichotomy for transductive online learn- ing. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, Decem- ber 10 16, 2023, 2023. URL httpc//beeeea.11111oo-ooaaraae--
nips. cc/ cwppppr..ccppppppceepeeee wwles/paper//////ee (aaper/2023/haa 2023/hash/ .ttml.
3e32af2df2dd1 hat.://2ecccdaadcbbbbeeeeee333 11068
Steve Hanneke, Vinod Raman, Amirreza Shaciri, and Unique Subedi. Multiclass transductive online learning. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, UIrich Paquet, Jakub M. Tomezak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NewrlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024. URL http::tttp::p/eee miippprrreesp.ppeepeeeepppeppsse cc peteepppr__fffee _ills// paper/2024, haper/2024/hashh
Abstratt-----ttttt-----aa--- Conf erence. html.
Steven C. H. Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: A comprehensive survey. Neurocomputing, 459:249-255 2021. doi: 10. 10..110/.EEUCOO..02222 https://doi. org/10. 10. 1016/j neucom. 2021. 2221.04.11 112.
URL
Thorsten Joachims. Transductive inference for text classification using support vector machines. In Ivan Bratko and Saso Dzeroski, editors, Proceedings of the Sixteenth International Conference on Machine Learning (ICML 1999), Bled, Slovenia, June 27 30, 1999, pages 200-209, Morgan Kaufmann, 1999.
Sham M. Kakade and Adam Kalai. From batch to transductive online learning. In Advances Neural Information Processing Systems 18 [Neural Information Process- ing Systems, NIPS 2005, December 5-8, 2005, Vancouver, British Columbia, Canada), pages 611-618, 2005. URL https: htap::////roceeingee 7768309/d204077774442243aaa wwt.:e03--bbttaat....... .html..
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn., 2(4):285-318, 1987. 10.:1001007/BF000 16827. URL https: //doi.
org/10. 1007 /BF001
Understanding Machine Learn- Cambridge University Press, 2014.
cambridge ort. astddmic// hanplcccc/cmmmpteeercccceeeeetto otg.ae/sieeet.tt..oooooooooooaaa
URL http://www.caamrridee
Vladimir N. Vapnik. Estimation of Dependencies Based on Empirical Data. Nauka, Moscow, 1979.
URL https: h/t::://wwwwww wwwpopp...//////eeeeee (w335///ubiicatteeee
In Russian.
Vladimir N. Vapnik. Estimation of Dependences Based Empirical Data. Springer, 2nd edition,
2006. ISBN -3-0--387730865-4 doi: 1001100100770-3873422333 URL https://doi org/10.
1007/0-387 300700-377-3223--7
Xiaojin Zhu. Sepi-super learning literature survey. Technical report, Department of Computer Sciences, University of Madion,,,,,,,don,,nnomoo 2005.
12

---

Xiaojin Zhu. Semi- cemi-supervised learning. In Claude Sammut and Geoffrey I. Webb, editors, Encyclo- pedia of Machine Learning, pages 892-897. Springer, 2010. (6::10..007/9780.-88--00016600 -_9.. URL attpss//ddes org/10. 1007 10w.110000977000 -00---00007--3-----------
Xiaojin Zhu and Andrew B. Goldberg. Introduction to Semi-Stpervised Learning. Synthesis Lectures
Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2009. ISBN 178-3-031-00420-- 22000//0011000000002000001111010
URL https://doi org/
13

---

Technical Appendices and Supplementary Material
A Preliminaries
A.1 Basic Notation
Notation A.1. N = (1,2,3,... ie., 0 $ N. log(-) and In(-) denote logarithm to base 2 and e, respectively.
Notation A.2 (Sequences). Let X be a set and n,, k E For a sequence x = (Z1..... ,n,. In) E X", write Tgk denote the subsequence ( Ik). If k then Egkk denotes the empty sequence, which is also denoted by X == x We use the notation X 0
A.2 Standard Online Learning
Let X' be set, and let H S {0, 11²² be a collection of functions called a hypothesis class. A learner strategy or simply learner for the standard online learning game (Game 1) is function
n-1
L
U:U 4=0
(X x (0. 17)² x x - {0,1},
where E N is the number of rounds in the game. The set of all such learner strategies is denoted L.. An adversary strategy or simply adversary for the standard online learning game pair of functions
n-1
Ainstance
U
(X
(0, 13 x 10, 11)* - X, and
i=0
Alabel
(X x 1) x 10, 13)* (0.1) 10,1).
1=1
The set of all such adversary strategies is denoted A..
Semantically, the interpretation of these strategies is that in each round [na] of Game 1, the adversary selects an instance
Ainstance (11, U1, V1, 2t-1, Pt-1. Ve 11-1) E X
then the learner makes a prediction
9r L(x1, T1 11
E {0,11} 1}.
and finally, the adversary assigns label
Alabel 01. W1...... It- 0r W1 De) E {0, 1}.
The adversary's 's function Alabel must satisfy realizability, meaning that there exists h E H. such that V [n] Y/ = h(xz).
The number of mistakes in game with n rounds and hypothesis class H between learner L and adversary A is
Mad MaadHH L, A) (t E [m] de v.Hl
A.3
Transductive Online Learning
Given X' and H as in Section A.2, learner strategy for the transductive online learning setting
(Game 2) a function
n-1 x" U f=0
L:
-0,1)' (0,1),
where n E N is the number of rounds in the game. An adversary strategy consists of a sequence n and adversary labeling strategy, which is function
A:
U i=0
(0, 12 x {0.1) 10,
14

---

The sets of all such learner and adversary strategies are denoted Cn and A,, respectively.
Semantically, the interpretation of these strategies is that the start of Game 2, the adversary selects the sequence z. Then, in each round E [n]. the learner makes a prediction
ye = L(, U1,
M1-1) E {0,
and then the adversary assigns a label
A(i1, Mi..... 20--1.9-11.00 E 10. Yv
Exactly in Section A.2, the adversary's function A must satisfy realizability, namely,
3h E H Vt
[n] yt h(xt),
and the number of mistakes in game with sequence length n and hypothesis class between learner I, and adversary A is
Mr L, A) = Me E [m] de ve
A.4 Mistake Bounds
In this paper, we study optimal mistake bounds, or the optimal number of mistakes, which is the value of Games and For M E (Madd, Mr the optimal number mistakes game with hypothesis class H and sequence length is,
M (H, n) inf LEC, AEA.
sup M(H. n, A).
The optimal number of mistakes for hypothesis class is
M(H) = sup M(H, n2)
EEN
Remark A.3. As is common in learning theory literature, in both Game and Game 2, we take the sets C. and A, to be the sets all (deterministic) functions. In this paper, we do not consider randomized strategies. By allowing arbitrary functions, we ignore issues relating to computability.
A.5 Trees
Definition A.4 (Notation for binary trees). Let d E N U (0). A perfect binary tree of depth d is collection of 2d+1_ nodes, which we identify with the collection of binary strings
Ta = 110,
10.1,2,...,dd
The empty string, denoted X {0, 1) is member of Ta and is called the root of the tree. Every string u E {0, 13d is called leaf. The depth of a node u Ta denoted ju], is the length of as string, namely, the integer such that u E {0, 1
For two nodes u, E Tas we say that u is parent of v, and that v is a child u, u, if = u o 0 or where denotes string concalenation. More fully, for b {0, 11. we say that a b-child of if u b.b.
Recursively, define that is ancestor of and that v is descendant of u. and write x if one of the following holds:
u -; or
Ew Ta 36 (0,1) (u x w) (wob= v).
For b E (0, we say that is a b-descendant of denoted So if descendant of the b-child of u.
function f Ta -> (0. 1) specifies a particular root-to-leaf path the tree Ta (see Figure 1). The on-path nodes for f are the set of + nodes that root-to-leaf path, as in the following definition.
15

---

Definition A.5 (Paths in binary tree). Let d, E N. h S d. Let E {0, 13 be a node in Ta- The path to u is the unique sequence path(u) (ug. U1 U2, ..., ux) such that un X is the root, Wk = and is child of for all E [k.
Let f Ta - {0,1} be a function. The path of is the unique sequence path(f) (wo, u1, U2...., (d) such that ug X is the root, and for each E [d], = u f(u--1). Namely, u, the ((iii)-child of U;-1-
For a node Ta and a function f: Ta - {0, 13, we write v E path(s) if path(() (up. Ua) and there exists i E {O..... dj such that u, Otherwise, write & path(f).
For node u Ta and set of functions - {0, 137h, we write E path(FF)
Vf F: path(f).
Otherwise, we write u & pFth
A.6 Littlestone Dimension
Definition A.6 (Littlestone, 1987). Let X be a set, let H C [0,1}* and let d E [O] We say that H shatters the binary tree Ta if there exists mapping Ta + X' given by u ト Fa such that for every u E {0, d there exists byg E such that
Vi E [d + 1]: h(Zugg 1) Ug.
The Littlestone dimension of H. denoted LD(H), is the supremum over all such that there exists a Littlestone tree of depth d that is shattered by H.
Note that by defining the Littlestone dimension this way, every class with Littlestone dimension d E N contains at least 2d functions.
300
E0
3h E H:
T01
1(xx)) 1
XX
M(11) 0
Æ00
h(010) =
Æ1
T11
Figure 2: A shattered Littlestone tree depth The empty sequence is denoted by
(Source: Bousquet et al., 2021)
Theorem A.7 (Littlestone, 1987). Let X be a and let H C {0, 1] such that d = LD(H) co.
Then there exists a strategy for the learner that guarantees that the learner will make at most mistakes in the standard (non-transductivv) online learning setting, regardless of the adversary' strategy and of the number of instances to be labeled. Furthermore, there exists an adversary that forces every learner make at least min {n, d} mistakes.
B
Lower Bound
B.1
Statement
Our li e(va) lower bound states the following.
Theorem B.1 (Lower bound). There exists a constant de 2 0 as follows. d E N, d 2 do, let X be set, and let H. C 10 be hypothesis class with LD(H) d. Then there exist sequence
16

---

2 of length n n= O 2v4) and an adversary A that always selects the sequence and uses simple udaptive labeling strategy (as in Algorithm 1), such that for every leurning rule L,
Mr n, L, A) 2 Va/10.
(3)
Furthermore, for every integer N,
My (H, n) min {Vā/10, [log(n + 1)1
Remark B.2. The assumption LD(H) implies that for all [d]. H. shatters Littlestone tree of depth k. Thus, the lower bound of Eq. (3) in Theorem B.1 immediately implies that for every
E [d] there exists sequence (kk) E xm of length nu = 0 2vF such that the adversary A that presents the sequence (*() and assigns labels using the simple labeling strategy of Algorithm ensures that for every learner L,
(H, L, Ab) 2 Vk/10.
See Section 2.2 for a general overview of Theorem B.1 and the main proof ideas. In the following subsections we prove Theorem B.1. Algorithm gives explicit construction of the adversary that witnesses the lower bound, using Algorithm subroutine. We start with presenting some initial observations about the behavior of these algorithms in Section B.2.
Assumptions:
de N, 2-
T Ta is perfect binary tree of depth d.
S 10 is class that shatters T.
TRANDUCCIVEADVERSAAN (HO): (I1, vn) CONSTRUCTSEQUENCC (H)
D. See Algorithm 2.
send D2, Fn) to learner
Ho H
for t [n]]
receive Jr from learner
Ti +- 11h E He-1 Mxx)) = 1}
174-11
ymaj
1(r: 2 1/2)
Umaj
rı E [e, e] otherwise
y/ f
1 Ur
send y/, to learner
H4 + {h E H4-1: h(x,) = ye
Algorithm 1: The strategy for the adversary that achieves the lower bound in Theorem B.1. Note that while the construction the sequence x is not entirely trivial, the adversary's strategy for labeling this sequence is very simple.
B.2 Analysis of the Adversary
Claim B.3. Let d E N, let M = Vd/10, and let H C (0, be hypothesis class. Consider execution of CONSTRICTSFFQUENCE (H) as Algorithm 2 that produces sequence Tn F2, ..... Fy- Then:
17

---

Assumptions:
=
T Ta is perfect binary tree of depth d.
the empty string, is the root of T'.
H S 10, is class that shatters T'.
CONSTRUCTSEQUENCH (H): HY +
Hig + {H)}
D A set of classes indexed by bit strings.
@ - {Y}
D. A set of nodes to be processed.
t + 0
while |2] > 0:
++
x - urbitrary element from
Pop an arbitrary element from and add it to the output sequence.
Q 2 {z))
IHI
for Ho E H
rt 1hh Ho h(x,) 131
[76l
y {
10 [1 1/2)3
(r a)) a (1b) < M)
& Adversary will force mistakes on the first M balanced nodes.
otherwise
for y EED y:
6 b
y
Restrict class agree with y. If split- ting the class in two to force a mis- take then create new indices.
boy
=1=2 2
Hy + {h Ho .((x)) = y}
H4, H, U }Hrr
if 3t path(HW)) A lorel d: If is on-path for Hy and it has y-child, add that child to Q.
2 - -ut o
return (21, 22,,,,,,
Algorithm 2: A subroutine of Algorithm 1 for selecting the sequence x.
(a) For all [n], path(z;) subsequence of Jo, F
(b) The length of the sequence satisfies n. < ng, where n. = (d + 1) 2M1-
Proof.
(a) Fix é E [n]. It suffices to show that for all u E Ta, if u & H; then u E (x), I2...., ...,..., I.). Proceed by induction i. For the base case = the claim holds because
X.
For the induction step, assume the claim holds for E [n - 1]. Let * 34 we prove that u E (21, ..,.... I++1). Assume Z;+1 * À (otherwise, there is nothing to prove).
18

---

Because 1:+1 appears in the sequence æ, it must have been added to Q before it was added to
z. The only place where items that are not À are added to Q is in the line Q + QU {I, o y)- Namely, there exist an index j E [i] and bit E (0, } such that 2i++1 = 3 y (note that j < + 1 because 2y was added to the sequence before Ii+1). If x. done. Otherwise, note that 2; is the parent of 14+1. and therefore u % z.. By the induction hypothesis, u E (2.,,22...... ,y). This concludes the proof.
we are
(b) Items are added to the sequence only if they were previously added to Q. By induction on i E [n]. for each z; in the sequence, there is at most one iteration of the "while Q > 0" loop which I; is added to Q. The base case i = holds because 21 = À is the root, which is added to Q before the while loop, and À is never added to Q within that loop because the line "Q + @ U {I+e o y can only add non-empty bit strings. For the induction step, if the claim holds for all natural numbers such that 1 S < S nt then it holds for i. Indeed, for 2 2. 24 can be added to Q only via the line "Q + QU {xz o yy}", and only in the iteration of the while loop where 2; is the parent of x; in the tree Ta. In that iteration, the parent x; of z, is popped from Q. which implies that 2y was added to Q in some previous iteration of the while loop (t < i), and is no longer in Q after being popped. By the induction hypothesis, Ze will never be added to Q again, and therefore in all subsequent iterations of the while loop H, will not be the parent of Vi, I2 cannot be added to in subsequent iterations via the line "Q < Q U (Ia o y)".
Furthermore, if a node H; is added to Q in some iteration of the while loop, then it remains in Q for the duration of that iteration. So for all i E {2, 3, ......,, n.. there is precisely one execution of the line "Q + QU {ar o y}" that adds x; to Q. Namely, there is precisely one point in time during the execution of Algorithm line t Q U (x, y)" is executed resulting in 2;, Q.
which x; - I2 o y, Ty & Q, and the
Consider function f that maps i E 32. n) to the value of the index d' during the unique execution of the line "Q 4- QU (2; oy) that adds to Q. Namely, if V had some value 3 when I; was added to Q, then f(i) = B.
Notice that "Q t (, is executed only if the condition x4 E path(H(s) is satisfied in the previous line. Furthermore, the line "Hy + [h E Hs : h(xx;)) - y}" ensures that the node x3- I2 o y being added to Q satisfies I y E path(Hys), namely
vh E Hy x, E path(h).
Consequently, x, E pGth(G) for any class G that is a subset of Hy: in particular, because the only way that Hy might be modified later during the execution of Algorithm 2 is by removing elements, it follows that x, E path (Hy. when the line "Q + Q U {z, o yy" is executed and in all subsequent times.
However, |path(9) (g)l = d + for any class 9 S {0, 137a, This implies that f maps at most (d + 1) nodes to each bit string. In other words, for any bit string b, the size of the preimage satisfies [b)] < + 1.
The condition "1b] < M in Algorithm 2 ensures that [8 s M, namely, 6' e (0, 13 for & E 10,,, M). Thus,
+ 32,,3...... ..............
m31
= ++ Σ
li (,, s(i) = b)
bE(0,1)*
ke (O......MM)
-I+
Σ
(-)
bE(0,1)*
Σ
(d+1)
kc (O.......M
11 (d ( 1)- (2 M21 - 1).
(d+ 1) M+1
19

---

as desired.
Claim B.4. Let d EN let M = Va/10, and let H C 13 be hypothesis class. Consider an
execution of "TTANSDCCTIVAADDERRSAA (H) in Algorithm I. Let
Ho. .i...., Nn
be the sequence of hypothesis classes created by 'RANSDUCTIVEADVERSSYY let
S = { Ta E [ -
be the set of indices where TRANSDUCHIVADVVRSSAY forces a mistake, and let
Ho, H.....,HH..
be the sequence of collections created by the subroutine CONSTRUCTSFQQURNC (Algorithm 2). If
|S| S then
e 10,,,,..... n. Hz H4.
Proof. Proceed by induction on / 10, nJ. The base case = 0 is satisfied, because Ho = H {H) lHl. For the induction step, assume that H4-1 E Hi,-1 for some E [n]. We prove that H, E H4,
Let ys be the label assigned to x; by TRANSOUCTIVADVVRSAAR Then
H4 {h H4-1 h(x,) y.).
Consider the iteration of the while loop in CONSTRUCTSEQUENC that starts with t +- By the induction hypothesis, H4-1 I1;-1. Therefore, in this iteration the while loop, there will be an iteration of the "for Hs IHl,-1" loop where Ho. Hi-1. i. In that iteration, y/ E y by construction of Y/ and y. Therefore, in the iteration of the "for E y" loop which y = yis
Hy {h H4s h(x,) = y} {h e H4-1 h(x;) yi H. The class Hy is then added to HI; HH, in the line "H, H, (Hw)". Furthermore, class is ever removed from H4. So Hi E [H,, as desired.
Claim B.5. Let d N, let M = Vd/10, and let H [0, be hypothesis class. Consider an (H.) in Algorithm where the adversary constructs Ta and a sequence of classes Ho, Hi...., Hn C {0, 1s Let
execution of "TTRANDCCTVVAADERRS..
sequence of nodes 21, Ø2 ..... Fn
S = {1 E [m]: n E [s, =
be the set of indices where TRANSDUCTVEADVERS.R forces a mistake, and assume that [S| S M. Then for all E {0, ..,, there exists E [n]] such that
1. [xa] = k, and
2. E path(H:--)).
Proof. Proceed by induction on k. For the base case k = 0, notice that æ1 = X, | = 0, and path(H-1)-
For the induction step, assume the claim holds for some e {0, 1, I..... - 1}. and take in [n] such that |æ,,]| = k and Tı, path(H,.-1))
prove that the claim holds for k as well.
Consider the iteration of the while loop CONSTRUCTSEQUENCE in which Ta is added to the sequence (i.e., the iteration starting with & +- 44). By Claim B.4 and the assumption |S] < M, Hap-1 H4,-1- Hence, within this iteration of the while loop, there is an iteration of the "for Ha E H4-1 loop such that H4 = Hig-1- By construction, the set ) always contains the label predicted by the adversary, so Vi. V. Consider the iteration of the "for y E y" loop such that y Vig By the induction hypothesis,
E path(H,, 1), and since Ho C Hs. = Hi, -1, it follows that di, (ptth(He)) Seeing as |ır, < d, the last line of this iteration of the "for y ) loop, the node Ties The Vig is added to Q. This guarantees that Zizzi will eventually be popped from
20

---

Q and added to the sequence returned by CONSTRUCTSEQUENCE: Once node has been added to the sequence. is never removed.
Notice that |oaetal = | + = + 1, satisfying Item 1. Therefore, it remains to show Item 2, namely, to show that 2i. E path((Hatt-1))
Indeed, by the induction hypothesis, v, path(Hi,,1)) and in the iteration of the "for y E y discussed above, Hy = Hig-1, Hy Hiu and Hy = (h E Ho h(xr)) = Vi J Hence,
vh Hip Die E path(h) A h(xw)) yhu
Seeing Tigs1 Dig. D/g This implies that
vh Hip : Dhan E path(h).
Item 2 follows from the inclusion H H C His-
B.3 Proof
Finally, we complete the proof of the lower bound.
Proof of Theorem B.I. Fix do 800 and assume d 2 do- Seeing as LD(H) d, H shatters the tree Ta- By replacing H. with suitable subset of H. of cardinality 2d+1, renaming the elements in the domain of H to nodes of Ta, and restricting the domain of each function H to Ta, assume without loss of generality that H S {0, 1 [H] 2d+1, and H shatters Ta-
Consider the loop "for [n]] Algorithm 1, and let
S {$1, $2,.... sm) {t [n] ra E [=,
be the of indices where the adversary forces mistake, such that the learner makes at least |S] mistakes. Let M vd/10, and assume for contradiction that m S M.
By Claim B.5, there exists E [n] such that |az| = (i.e., 21 is leaf in Tạ) and Fı E pathhHH--1), namely,
wh E H4-1: : x E path(h).
Sceing as F, a leaf,
Vh E H4-1: path(r;) = path(h).
(5)
By construction,
Hi S h E H: (Vi [4] M(x;)) = wi)
and H4 is not empty. Fix some h² H4 C H4-1- By Item (a) in Claim B.3, path(x;) path(h*) a subsequence of Iı, T2,..., Tt,
80
Vh H, Vx E path(h"): M(x) h=))..
Sceing H. shatters Ta and H 2 if two functions h, h H. agree the labels for all nodes in path(h"), then h = h²" We conclude that H. {h*} and [gg] = 1.
Consider the loop "for f E [n]" in Algorithm 1. For each t E [n].
Se 1H [11 ee) 17411
L S
Hd >
t $ S.
Hence,
1 Hc
2 m
(1 nm Hol
(1 - 8) 2d+1
2 cm (1 8)n 2d+1
2 m (1 24 2d+1
(by Item (b) in Claim B.3.)
2 m pd = my m/222+
(6)
21

---

where the final line holds because =2-v//2, (d + 1) 228/1041 and
=)= -1-2 11-2-va/2 (d+1))2v4/0+)
1
for our choice of d 800. Rearranging Eq. (6) yields
2vd S
This is contradiction the assumption M vd/10. We conclude that adversary A following Algorithm satisfies
inf Mr L, L, m M vd/10. LEC.
as desired.
To establish the "furthermore" part the theorem, length n E N. Let be the largest integer such that 2[vk/10| < n++1 and k & d. By Eq. (7), there exists some sequence on which the adversary can force every learning rule to make at least Vk/110 mistakes. By Theorem C.2, this implies that
there exists sequence of length 2 g[vk/10] 1 v n on which the adversary can force every learning rule make least /Vk/10 min {[va/10 10 [log(n + +)] mistakes. Namely,
mr, n) 2 min [[Va/10| [log(n +113.
as in Eq. (4).
C Sequence Length
In this section, we show that if there exists a sequence on which the adversary can force mistakes, then sequence of length 2 - is sufficient, and this upper bound is tight for some classes. 19 Definition C.1 (Minimal sequence). Let X be set, let H 1), be class, and let M E N. The minimal sequence length for forcing M mistakes for the class H. denoted MinLen (H,
MinLen(H, M) = inf (n E E:: (Ex E Xm: M,, x) 2 M)}.
In words, Min is the smallest integer n for which there exists a sequence of length which the adversary can force at least mistakes; if such sequence exists, then MinLen H, .M) = =c.
Theorem C.2 (Minimal sequence bound). Let X be set, and fix M E N. Then for any class H. (0, 1)x MinLen(H, M) co then
MinLen (H, M) < MM -
Furthermore, there exists a class H C (0,1)* 1)x for which MinLen(H,, M) = 2
Theorem C.2 is corollary of the tree rank characterization of M, from Ben-David et al. (1997). For completeness, we present direct proof of Theorem C.2 that does not directly invoke that characterization. Roughly, given an adversary Ag that forces every learner make least M mistakes on (possibly long) sequence we apply two modifications to obtain new adversaries
Ao A Ag.
A forces M mistakes and has specific structure that call 'rigidity', but it still uses the same (possibly long) sequence z. Capitalizing on the rigid structure, A2 selects a subsequence of æ of length most 2 1, and forces M mistakes on that subsequence.
Of course, there also exist classes for which shorter sequence is sufficient. For instance, if the class shatters (in the VC sense) subset of the domain of cardinality M. then sequence of length M suffices.
22

---

C.1 Rigid Adversary
Definition C.3 (Rigid adversary). Let n let be a set, and let
2-1 ( [0.1) {0,
A:
be an adversary strategy for some fixed sequence x E X We say that A is rigid there exists
function
n- U
1 10,1,
k=U
such that for all l E {0, (0,1.....,, 1} and all y, E 10.1)*
A(o M1 Dk Uks 11+1) {
f(y1.- - Uk)
Jyn, yk) E {0, f(yh,..., yk) =
ūk+1
Note that if an adversary is rigid, then the function f that witnesses this is uniquely determined. Claim C.4 (Rigid adversary exists). Let n, M E let X be a set. let X", and let S {0, 1) be a class. Let A be an adversary strategy that forces every learner to make at least M mistakes on Then there exists an adversary strategy A such that:
1. A forces every learner to make at least M mistakes on and A is rigid.
2. Let f be the function that witnesses the rigidity of A Then for every {0, the sequence
(ugoo, I(Vs)), (WV2)).........................) ,(y),
has at least M members equal to
Proof of Claim C.4. For Item consider the adversary strategy A that simulates execution of A, as in Algorithm 3. In broad strokes, A functions as a middle-man between the learner and A. As the learner makes a sequence of predictions ý {0, 1)" the adversary A" generates sequence of (possibly different) predictions ý E {0, 1]"", and sends those to the adversary A. Adversary A sees only the predictions y, and assigns labels f0. 1)", which are relayed back the learner by A with no modifications.
First, observe that A satisfies the realizability requirement. Indeed, A simulates execution of A such that the sequence of labels y1....,W0 Un sent by A to the learner is exactly the sequence of labels selected by A. Seeing A is realizable, every sequence of labels selected by A is realizable, and therefore every sequence of labels selected by A must be realizable as well.
Second, observe that A" forces every leaner to make at least M mistakes. To see this, notice that in Algorithm 3,
Σ 1 + vt) 2 M. TE[M]
Indeed, A forces every learner to make at least A mistakes, and in particular this applies to a learner that makes predictions ý in the simulation. Furthermore, observe that A only alters the predictions receives from the learner in cases when selects a label that accepted by A, namely.
Vt [n]]
Ee # Ec
ÿt yc.
Therefore, if {t E [n] Dt
}. then
Σ (Ne + v.) = Σ (1e + Me) + 4E(m)
1 + y1)
LEE
XE [m)] F
Σ
1 + Me +0
(By Eq. (9))
Σ
( + m))
(Defintion of E)
23

---

Assumptions:
n N, a X is fixed sequence of instances.
:: (o.10t))))))) x {0, - {0, 1] an adversary labeling strategy for a.
RIGIDADVERSARY:
send T1, , in to the learner
for t 1.2....,
receive prediction D, from learner
A(J1, y1....... Wt- 11. 0) =
f 0
else A(J, U1. 11-1, 1) =
1
else:
1/ 51
send prediction d. to
receive label Yr from A send label y, learner
Algorithm Construction of rigid adversary, by simulating given adversary A.
Σ 10 + 14).
(10)
:E(m)
Combining Eqs. (8) and (10) implies that forces at least M mistakes.
Third, we show that A is rigid. We claim that there exists function g: 10, 10, - (0,11smm such that for every {0, 1,2,, 1.. 1),
(ū1.- Dt) = o Vt).
Proceed by induction on For the base case = there is nothing prove. For the induction step, we assume the claim holds for some f = 1 Algorithm 3, 1 satisfies
1, and show that it holds for = h 1. From
0
A 151 91.............................. UR. yk 0) 0
Uk+1
1
A V1. 91.....
Uv. 8k. 0) = A VI..... Uk yk. 1) =
(11)
1
yk++1
otherwise
The first two cases in Eq. (11) are immediate from Algorithm 3, and the remaining case occurs when A forces mistake at time k + 1, namely, when A selects W 1 ūk+11 Thus, Ūk+1 is function of Ugk+1 and TSK- By the induction hypothesis, ÎS* = ), so Øk+1 is simply a function of USL+1- This establishes the existence of the desired function g.
Hence, A" is rigid, as witnessed by the function
0 A(i1, Ui,.... A(D1, ....... Dc. Uk. 0) A A(i.. V1..... Dr. Mes 1)
Jk. Uk. 0) = 0
f(y 119i.....1.. M6.
otherwise
where f is well-defined function because UCA = g(v5)). We have seen that A is valid (realizable) adversary that forces every learner to make at least M mistakes, and rigid. This concludes the proof of Item
Finally, For Item 2, note that Jt * only if A forces a mistake at time in the sense that A selects {0, 1} provided at time 4. If A forces mistake at time I, then A*
V/ for any prediction forces mistake at time as well. Therefore, if Tt * yr, then ((ee) = namely, makes mistakes only when the value of *. By Eq. (8), Dt makes at least M mistakes throughout the game, so there must be at least M rounds where f outputs x, desired.

---

C.2 Essential Indices
Definition C.5. Let n, M N, let X be set, let X", and let H S 1) be class. Let A be a rigid adversary strategy witnessed by function f. We say that an index E [n] is essential for A for forcing M mistakes on x if there exists a sequence E {0, (0,1)-1 such that f(y) = * and the sequence
f(yoo), f(ys)), f.. f(yst--)))
contains most M members equal to
Claim C.6. Let M N, let X be set, let z E X", and let H. {0. 1)x be class. Let A be a rigid adversary strategy. Then [n] contains at most 2M indices that are essential for A for forcing M mistakes on
Proof. For each essential index t [n], there exists label sequence y E {0, 1)r-1 that witnesses that is essential, as in Definition C.5. Each label sequence y is witness for at most one index (the index ly] + 1), so suffices to show that the set Y C {0, 1n of witness label sequences is of cardinality at most 2 -
Think Y as collection of nodes in the binary tree Tn (Definition A.4). By Definition C.5, E Y, then the collection of all ancestors of in Y has cardinality
Kys e {0, 1,2, ..... ly| 1)} n Y s M -
Namely, Y is subtree of depth at most d = M - in the binary tree Tn-1. Hence, the number of nodes in at most
2d+1 1 = 2M - 1,
as desired.
C.3
Proof
Proof of Theorem C.2. If MinLen(H, M) < co, then there exist a sequence x E X", and an adver- sary Ag that forces every learner make at least M mistakes adversary A₁ that causes every learner to make at least M mistakes on xr 21 and also satisfies Item in Claim C.4. Let f be the function that witnesses the rigidity of A1. By Claim C.6, the set I [m] of indices that are essential for A, for forcing M mistakes on & has cardinality = |7| & 1.
By Claim C.4, there exists rigid
Algorithm 4 defines new adversary, A2, which forces every learner to make at least M mistakes on a sequence of length A: A2 is realizable, because Ai realizable."
To see that adversary Ag forces every learner to make at least M mistakes, let y...... be the sequence of labels assigned by Ag. Seeing A2 assigns the same labels A1. and A satisfies Item 2 in Claim C.4, it follows that there are at least M indices j E [n] such that f(y3)-1) = *. Fix S [n] be the first M such indices. Then J, namely, all the indices in J essential for A for forcing M mistakes on (Definition C.5).
Therefore, for each E J, A2 includes the instance æy in the sequence of length is sent to the learner. Then, in round j of the rounds simulated by A2:
The leaner makes a prediction úe {0, 1} corresponding to instance Tij-
Adversary A₂ sends prediction új to adversary A₁. Because (vCj-1) = *, adversary A assigns the label yyj learner makes mistake on Tj--
ýj. Adversary A2 then sends that label yj the learner. So the
Hence, the learner makes at least |J| = AM mistakes, as desired.
The depth of subtree is if the longest root-to-node path contains + 1 nodes from the subtrec. Tiis Item Claim C.4.
The argument for realizabilitty is the same in the proof of Claim C.4.
25

---

Assumptions:
n, M E A' set, 2 is fixed sequence of instances.
A1: (UR-d 10. {0.1} f0, 1} is rigid adversary labeling strategy for x that forces every learner to make at least M mistakes on the sequence I, and satisfies Items and Claim C.4.
= {ú, i2, .... i C [n]] the set of indices that are essential for A for forcing .M mistakes x, and S i2 I S ig. By Claim C.6, k s 2 1.
MINIMALADVERSAAR:
send Tig Rigs... ................................ Fig to the learner
for t 1.2....,, n.
if / E
receive prediction J, from learner send prediction ÿt. to A receive label y/ from A1 send label ye learner else:
send prediction ÿ. to A receive label y: from A
Algorithm 4: Construction an adversary that forces M mistakes using a sequence x of length at
most 2M -1 1. In the proof of Theorem C.2, this adversary is Ag. Internally, simulates rigid adversary A
D
Upper Bound
D.1
Statement
The following result states that the lower bound of Theorem B.1 is tight for some classes. Theorem D.1 (Upper bound, and separation between standard and transductive online learning). For every integer d. 2 43, there exists hypothesis class H C (0, 1)x with domain X of size | = 2d -1 such that LD(H) = d and the following two conditions hold for all E N:
1. Mc,(H, n)) < 48 Vd.
2. Msta (H, min (n, d}.
D.2 Hypothesis Class
In this section we construct the hypothesis class for Theorem D.I.
Lemma D.2. Let d E N, d 2 42. Let Ta be perfect binary tree of depth d, as in Desinition A.4. Then there exists a collection of functions H (0. 1)7 such that LD(H) = d + and the following two conditions hold for all H H and all X C Ta:
1. 1f E H Vx. E X: x & path(h) A Mxx) = 0, then min (1H), X}} < 23va
2. 1f E H X x path(h) A h(x) = 1, then H < 22vd or X < 3
The proof employs the probabilistic method, showing that hypothesis class sampled randomly from suitable distribution has the desired properties with very high probability.
26

---

Proof. Let P be probability distribution over hypothesis classes. Formally, P E
A ((10, 13 13Ta)a(*1) of 2d+1 hypotheses,
a distribution over vectors of hypotheses. Each vector H E supp(P) consists
= (ho))e(0.1)44):
where for each b {0, 13 hypothesis h2 is function hy Ta {0, sampled independently as follows:
For each i E [d] U {0}: (bgg))) b (In particular, with probability 1, path(hs) (bgo, bgi,...,baal Dggd), each entry in the vector H unique, and H shatters Ta-)
For each E Ta (aa) path((s)), the bit hx(2) E {0, 1} is sampled Ber (2 vā) independently of all other bits in H. i.e., ([4)(2)= = 1] (=))((()))))) = 1 { Ju U1y (3") }=)))'''' = 2-vd,
In words, for all nodes on the path in the tree corresponding to 6, the function hs assigns label according to b, and for all other nodes, hy assigns a label with probability 2 ~~v and a label of otherwise. In particular, the collection H. Littlstone--satter the tree Td-
Fix B S {0, 1] and X _ Ta, and let E(B, x,
y) denote the event {Ab B Vx E X & path(hs) A ha(z) = v).
(12)
Seeing as each off- off-path label (x)r)= E {0, 1} is sampled independently.
PHUP
II
PH~PlE & path(ho) A ho(x) = 0]
(b.x)
$ (1 2 vā V BxX]
(13)
Hence,
3B C (0, (0.1) X Ta: E(B,X,0) A min (IB) > 22v
Pæ-P
PPWw 3B S 10,1) 3x Ta: E(B,X,0) A |B| X [22v]]]
(0, 10, 11a+11
Tal
[2ava] (1- 2-Vajaaa
[2ava]
(union bound, Eq. (13))
2d+1 2
(1 - 2 vājzava
(2 may not be an integer; for- mally, we use the generalized bino- mial coefficient, or simply skip to the next line)
22v2 +1
< (d+1))
-2 -2- v2.2
"
< nt for k: 2 e; cel+ e for x E R)
k
2d+2))22224
2-2- gavi
22 > d+ for for
2 22
(2d 22a___ - for d 42)
(14)
Similarly,
PH~P Vo X: æ & path(bs) hn(x)) 1] 1 2 vallxx 2
(15)
PHwP
B C (0.1)* d+ 3 C Ta: E(B,X,0) I 2 22v |X|2
27

---

1idi {0.
Paad 1
2 2-
(union bound, Eq. (15))
22va + 1
2441
2d+1
2 3dd
3v + 1
2 (d41)) 2(d+1) 1) (3v0-1) 2 2dd
(x) n for ts 2 e)
< 2 (242)))22
2-33d
2dd22v0 2 3d.22v
(for d 2 4)
<2 <2-22 d2va
(16)
Applying a union bound to Eqs. (14) and (16) gives
PH~P (H satisfies Items and 2] 2 1 1-2-2 2-
-2-02 2 1 10
In particular, there exists a collection H. that satisfies Items and 2. Furthermore, this collection has LD(H) = d + 1 (namely, LD(H) 2 d because it shatters Ta; and LD(H) I d because [76| = 2d+1) )
D.3 Algorithm
In this section describe Algorithms 5, 6a, and 6c, which together constitute the learning algorithm that achieves the O (Vd)
mistake upper bound in the transductive setting, as in Theorem D.1. See Section 2.3 for a general overview of these algorithms.
D.3.1 How Experts Work
We start with some preliminary remarks about experts in Algorithms 5, 6a, and 6c.
Experts. A tuple (S, u, H) defines an expert that can make predictions using the procedure EXPERT.PREDICTIC, The tuple reflects two kinds of information:
1. Knowledge. Information that the expert knows with certainty. Specifically, this reflects the labels y1, .2.... sent by the adversary so far. All experts see the labels sent by the adversary, so this knowledge is the same for all experts.
2. Assumptions. At certain times, experts make assumptions about things that are not known for certain. Specifically, experts assume that certain nodes on-path (æ: path(h) (h)) or off-path (x & path(h)) with respect to the correct labeling function : Ta - {0. 1}. Assumptions simply guesses that may be wrong, and therefore when expert needs to make such an assumption, it splits into two experts (as described below), with one expert assuming path(h), and the other expert assuming path(h). This ensures that there always exists an expert for which all assumptions are correct.
In greater detail, the contents of the state tuple (S, u. H) represents the knowledge and assump- tions of the expert as follows:
E Ta - This single node encodes everything the expert knows and assumes about which of the nodes labeled so far are on on-path. Observe that if U1 .2...., Ug E Ta are nodes that are assumed to be on-path (and all these assumptions are consistent), then these k assumptions can be represented succinctly by assigning u = 0t- where U,- is the deepest node among U1, U2,-... Uk. Therefore, u simply holds the deepest node in the tree that is known or assumed to be on-path. At the start of the algorithm, this value is initialized to be u = X, because the root is known be on-path regardless of the target function.
S C Ta - the 'danger zone', as described in Section 2.3.4. This is collection that contains all nodes in the prefix &stt.... = (I1, T2, Tt..)) of the sequence to be classified that have not been labeled yet and might be on-path for the true labeling function h given what
28

---

the expert knows and assumes so far. However, S is not required to contain ancestors of nodes that are assumed to be on-path. Initially, S equals the prefix I'Stmx As information accumulates, nodes that cannot be on-path are removed from S. For instance, if zy E Ta is assigned label y1 E {0, 1} by the adversary, then any (1 Vj]-descendant of 24 (including 2, itself) may safely be removed from S.
H S f0, 1) the version space of the experts, i.e., the collection of all functions that could be the correct labeling function given everything that the expert knows and assumes. Initially, contains all functions in H. As information accumulates, some functions are ruled out. Specifically, a function & can be removed from H for two reasons: (i) the adversary assigns a label y * h((x) to some node a E Ta; (ii) the expert makes an assumption that some I Ta is an-path for the correct labeling function but & path(h), or vice versa, the expert assumes that x is off-path for the correct labeling function but x E path(h).
Updates and splits. An expert can be modified using the procedure ENPEER.EXTENDEDUUDAA
This procedure either returns a single modified tuple (S, u, H) (in the first two return statements in the procedure), in which case we think of the expert as being updated; or alternatively, the procedure returns two tuples eg = (Se: Ugg, He) and eg = (Sg. ug, Hg) (in the third return statement), in which case we think of the expert as being split into two experts. The expert eg corresponds to adding assumption that the most recently presented node 2y is on path for the correct labeling function, and eg corresponds to adding the opposite assumption.
Ancestry. At the end of each iteration of the outer 'for' loop in Algorithm 5, for each expert e E Es+1 there exists a unique ancestry sequence ancestry(e) = (e1, ...... et+1) such that e1 e1= ((21,...,, Ttmux J. X, H. is the initial single expert that was created before the start of the outer 'for' loop, Ct+1 = e is the latest version of the expert, and for each i E [t], the expert 6;+1 was created by execution of EXPERT. SEPPET.BASSCUPRE BASICUPDATH(CE possibly followed by execution of EXPERT.EXTENDEDDPPIE
23
D.4 Analysis
In this section we prove our main result, Theorem D.I.
D.4.1 Assumption- Expert
Occasionally, when an expert is updated, it makes an assumption about whether the most-recently presented node zz is on-path or off-path with respect to the true labeling function h. In these updates, the expert is split into two: one expert assumes that x; E path(h), and the other assumes Ie phth(h). Clearly, by splitting into two in this manner, we preserve the invariant that the set of experts always contains a 'vindicated" expert e* such that all the assumptions made by e" are correct. This simple observation is made formal in the following definition and claim.
Definition D.3 (Assumption consistency). For an expert e Eet1 with ancestry(e) update of e was assump-
"n,,e2...,,e-- and an index E [t]. we say that the - tion-consistent with a function h Ta + {0,1} if one of the following conditions holds:
C++1 = SAPPERT.BASICUPPATECCC V:):
Noot that in this paper, we use genealogical metaphors in two distinct contexts that should not be confused. First, as is customary. we use "child", "parent". "ancestor" and "descendant" to describe relations between nodes in the binary tree Ta. which constitutes the domain of our hypothesis class, Separately from that, we "ancestor" and "descendant" to deseribe relations between experts.
This overlap in terminology can partially be excused by the fact that the history of experts also forms a binary tree. Indeed, initially there is a single expert (the root of the tree), and experts can split into two, corresponding to a node having two children as in binary tree. Seeing experts cannol merge, the expert history corresponds precisely binary tree. (However, the domain Ta is a perfect binary tree, whereas the binary tree corresponding to expert genealogy need not be balanced).
To reduce confusion, we use path(-) only for nodes in Ta. and ancestry(-) only for experts, even though these operators are mathematically equivalent (however, path(-) is defined not only for nodes in Ta but also for functions l' (0, 1)).
29

---

Assumptions:
d,n E N, X is the empty string.
HC (0,1) Ta is the class that exists by Lemma D.2.
21, In E Ta are points be classified.
TRANSDUCIVELEARNERR..
..,,
0, Imax + 2dva
e ((z1,.... Tmme X, H)
> The initial expert. An expert is defined by a 3-tuple.
w((e) +1
Assign the initial expert a weight of 1.
E1 <- -e}
> E, is the set of experts used for predicting Dt.
E2, Ens Ent1 t
for 1. x- 1-1,2....; n
d/. 5- Σ w(S) EXPERT. PREDICT,,, xt) 2
NeEE:
A weighted majority, using Al Algorithm 6a.
send prediction ÚL to adversary
receive correct label Yt E {00 1} from adversary
for e E Ex: e + EXPERT. CUPERT.BASICUPDATEEC 21,
Update the experts.
24, u1) Remove functions that disagree with the label ye from the version space.
if EXPERT.PREDICTTE. Ve:
Ex+1 + Est1 [e}
If expert e made a correct prediction, further update is needed.
else:
U EXPERT. EXPERREETTEDDEEUPDATTI.CC, v:)
If made mistake, update e using Algo- rithm 6c. This might cause e to be split into experts.
for e' U: Est1 E,4 U {e}
Add updated expert(s) E++1- > When e makes a mistake, its weight is decreased by factor of and then split equally between its descendants.
w(e') -
transductive online learning algorithm that makes at most O ((va) mistakes. is variant of the multiplicative weights algorithm that employs splitting experts. Namely, we start with single expert, and when an expert makes mistake it may split into two experts. The behavior of the experts defined in Algorithms 6a and 6c.
Algorithm 5:
e++1 was the single expert returned when executing EXKEERT.EXEENDDDDDTTTTCCCC for et
I4, y:); or
with EXPERT. BASICUPDATEE(E, 24, y.) returned two experts (Se, Ue. He) and (S ue Hz) (as in the third return statement), and furthermore,
Executing
of
e = {
(Se, Me: He
x; E path(h)
(17)
(S4, ugz Hg)
24 path(h).
30

---

Assumptions:
d de E Ta-
e= (5, u, H) is tuple that defines an expert:
C Ta - collection nodes that could be on-path for the true labeling function given what the expert knows and assumes.
T the deepest node known assumed be on-path by the expert. H S {0.1}"u the collection of all functions that could be the correct labeling function given what the expert knows and assumes.
EXPERT.PREDICE x): (S, H) +
D Unpack the state that defines the expert.
if H| S 22V return HALVING.PREDICTOU
>> Once H becomes small enough, simu- late the Halving algorithm (Algorithm 7). [Case I]
if x & W: return b E {0, such that <a u
> is assumed to be on-path. If u is decendant of z, then the correct label for must be b. [Case II]
return 1(1(2' S $1 x')|> [S|/3)
Output some b {0,1) such that more than 1/3 of suspected on-path nodes are b-decendants of if such b exists. Oth- erwise (when at least 1/3 of S are non- descendants of x)), output 0. [Cases III to VI]
Algorithm 6a: A subroutine of Algorithm 5 that defines how an expert makes predictions.
Assumptions:
S, H - as in Algorithm 6a.
y the correct label for v, as selected by the adversary.
EXPERT.BASICUPDAA.. y):
(S, u, H) t
Unpack the state that defines the expert.
H + HALVING.UPDATE(HH..
Update the version space, in the Halving algorithm (Algorithm 7).
return (S, u, H)
Algorithm 6b: A subroutine of Algorithm 5 that defines how expert is updated each time that label selected by the adversary.
We say that an expert E1+1 is assumptiinn-coniissenn with h for all E [t], the (i 1) update of e was cssumption-consste consistent with h.
Claim D.4 (Existence of coumppion-coosisteen expert). Let e S n, let H. C Thu, let
I1, E1y In Te. and let h Ta {0, 1}. Consider execution of
TRANSDUCTIVLEARNIR d, (II, 22...,...., In))
as Algorithm 5. Then, the end of the t-th iteration of the outer 'for' loop in TRANSDUCTIVE. LEARNER, there exists unique expert e741 Ee+1 that is assumption-consistentt with h.
consistent
31

---

Assumptions:
d, I. e. S, u, H as in Algorithm 6a.
y the correct label for v; as selected by the adversary.
EXPERT. EXPENDEEXTENDEDUPDATTICCC 2, y):
() t
Unpack the state that defines the expert.
if H| < 22Vd: return {(S, u, H)}
If the version space is small, we just simu- late the Halving algorithm, so the update complete. [Case III]
for be {0. 1]: So + fa' E S x6}
Set of suspected on- on-path nodes that are b- descendant of æ.
if (( > /s|/3:
8' + S S(-y) return ((5', u, H)}
At least 1/3 of suspected on-path nodes were 6- decendants of x, and therefore the expert predicted label b. But the correct label y 1 b. Remove all b-descendants of x from S. [Case IV]
else:
Sg +- S; Ue +-
Split in two. First, construct eg to be an updated version e after adding the assump- tion that æ & path(h) for the correct label- ing function h.
He {h H1 x & path(h))
eg + (S ug, H4)
Se + So US
Next, construct eg to be updated version of e adding the assumption æ E path(h). Se contains only nodes that descendants of æ.
Ue f- u
> de represents updating the prior assumption that on path by adding that x also on path.
if Ugg $ x:
Ue f- x
HE {h H x E path(h))
He is obtained by updating the version space to include only function where æ is path.
GE +- (Se, He)
return EE}
[Cases V and VI]
Algorithm 6c: subroutine of Algorithm 5 that defines how an expert is updated (and possibly split into two) when it makes a mistake.
Proof. We prove by induction that, for all s [t [t, E, contains a unique expert that is assumption- consistent with h. The base case is clear, because E₁ contains only single expert that was never modified. For the induction step, let e be the unique assumption-consisee consistent expert in E,, and consider the + (s + update. Notice that by Definition D.3,
For E Fs \ {et), every expert é' FE-1 such that was created from by executing EXPERT. BASICUPDATE(e,, Vs. EXTERRTEXTEENEEDUPPATE is not assumption-consiiten with h; and
Rs, Us) possibly followed by an execution of
and 4s, Us) is not executed (c) is added to E with just basic update), or precisely one of the experts that were created from e by executing EXPERT.EXTENDEE EXTENDEDUPDATE and added to E.41 is assumption-consistrr with h.
Either EXPERT. BASICUPDATE(( Is, Hs.
Es-1
32

---

Assumptions:
X' a set, & E N.
H (0, 1 is a finite hypothesis class.
2, Fk X, E 1),
HALVING(H, (21,22;.... 2x)):
Hi H
for i e [k]]
y/ HALVING. PREDICT(H,)
send prediction O: adversary
receive correct label y/ {0, 1) from adversary
H4+1 < CALVING.UUDATE((MM) 2; ys)
HALYING.PREDDICTCH, 2)::
return 11 1 [2.
Enex h(x) 2
HALVING. CUANNGGHP x, y):
return (h H h(z) y}
Algorithm 7: This is the well-known halving algorithm. The experts in Algorithms 6a and simulate this algorithm once their version space becomes small enough.
Seeing the EXTERD.EEEENDDDUUPAATE at most once for each e E Eg, follows that Es+1 contains precisely one expert that is assumption-consistenn with h.
1) update executes EXPERT, PATE and
An expert e = (S, u, H) that is assumption-consistee with the correct labeling function enjoys two simple properties. The first property is that the node in the expert encodes correct information about which previously seen nodes are on-path for the correct labeling function.
The second property is that the set S contains all future nodes that on-path for the correct labeling function and are also deeper the tree than all nodes assumed to be on-path so far. These two properties are formalized in the following claim.
Claim D.5 (Properties of tasumption-conssssen expert). Let E ler H (0,1)
let Ji, 3 Fn Ta. Consider an execution of
TRANSDUCTVELEANNERR... d, (I1, (I1, 22,,,.,,
as in Algorithm Assume that the adversary selects labels y1 32...., Yo E {0,1} that are consistent with some function h. Ta + (0, 1). Let e = (Si ut, H;) E₁ be the unique expert in E, that is assumption-consistee with 24 Then the following two properties hold:
1. ug path(h).
2. {a Tet......... 2t Dtmnd x path(h) A x * ut) C Sç.
Proof of Claim D.5. The proof proceeds by induction on l. For the base case /. = 1, Fi contains single expert ej (St, wf, HJ) where uf À is the root of Ta- Indeed, E path(A) for
Recall that et exists by Claim D.4.
33

---

any function h : Ta - {0, 1). This establishes the base case for Item 1. Additionally, Si T2,..2..... Ftmm. satisfying the base case for Item 2.
For the induction step, we assume that the claim holds for some integer t = i, and show that it holds EXPERT.BASICUPDAATT
for i + 1 well. First, we establish Item 1. If c,41 h). Otherwise, by Definition D.3 and the first the claim is immediate because 4;+1 = ur E path(h) first two return statements in EXPERT. ENPEER..ETENNDDUPAAAT ----- = " E path(h), in which case the claim is immediate, or else e,+1 satisfies Eq. (17), namely,
Ri, It), then
either e (5 ui+1; (44+2) has
{
(Se, Ug: HE) (S4, ug, He)
21 path(h)
24 & path(h)-
As defined in EXPERT. EXTENDED we is equal either to un or to zs so if x; path(h) then 4 = ue E fut, x.} S path(h).
On the other hand, if r; & path(h) then we get u ug = u, E path(h). We see that all cases, 2,+1 E path(h) as desired. This concludes the proof of Item 1.
For Item 2, again, if 1++ EXPERT. BAHERR.BASICUUDATEE(E. 24, y:), then the claim is immediate because 5 = S and wH+1 = u.. Otherwise, consider the various ways in which u,+1 and S can be assigned by EXPERT. SEEERT..XTEEDDDUPAATEE In the first return statement, ub41 = " and S41 St. and the claim is immediate.
The second return statement assigns "1+1 un and 1 S \ Si- where Si-,, is the set of (1 - y4 -deseenndsssss of x; (including x; itself). Notice that regardless of whether x; is on-path for the correct labeling function h or not, none of the (1 y desseenanssss of x; (except possibly æ; itself) can be on- on-path for h, because assigns a label y/ to z;- And seeing as Item 2 only requires that Taa }. it is also safe to remove F,. Therefore, removing
S contain nodes from {21+1, (2,41, Te42. Si-w. preserves Item 2.
For the third return statement, there are two possibilities. The first possibility is that u44 = -ig and S 5 5/ in which case the claim immediate. The second possibility assigns WH+1 Mgg. and S = Sg So U Sj. namely, S/+1 is constructed by removing the non- descendants of z, from ST By Eq. (17), this happens when x; E path(h), so all non-descendants of r, either off-path for h, or they are ancestors of z;. Seeing H; path(h) and 5r E path(h), and de the deeper node between these two, any node that is an ancestor of x; is also an ancestor of u ug. Thus, all the nodes removed or either off-patt faftpathh for h, they are ancestors of uf+1+ satisfying Item (Similarly, any node that is an ancestor u, is also an ancestor of uf+1, so we do not need add any new nodes to S that are not included in ST
We see that in all cases, Item 2 is preserved, as desired.
D.4.2 Transition to Halving
Claim D.6. Let d, n,, E N. 2 16, let S 10,1)Ta, and let 21. E Ta. Consider an execution of
TRINSOCCTIVLEERRNRRR.... (x1, (,,,,,,,,,
as in Algorithm Let Imax = 24ve and (5, u, H) E Eg an expert. Then
[ < 2v7
Proof of Claim D.6. Assume for contradiction that H > 22vd of size 22v7 1. Let
Let H' C H be an arbitrary subset
P = Uhen pht Seeing as each root-to-leaf path contains d + nodes,
P = H (d (d+1) < (22/4 + +1) (d 1) < d2+1
(18)
Let V/, .2........ Vt be the labels provided by the adversary in the first fmax iterations. The line in
EXPERT. BESER..BSICUPAATE constructing H using HALVING. HALNING.UPDATE(( H, x, y) ensures that Yh. E H Vi [mmx]] h(zz) = Vi.
(19)
Consider two cases:
34

---

. Case I. Eler V/s S mmax/2. Then the set
Xo f2r [max yt 0}
has cardinality [Xol 2 /max/ 2. Let X = Xo P. By Eq. (18);
1 mmx d22vd+1 = 24v2 v d22v
(20)
2
From the choice X/, the inclusion C H, and Eq. (19),
4h E H' Vx E X path(h) A h(x) = 0.
(21)
Seeing |H 22v Eq. (21) and Item from Lemma D.2 imply that Xgo - 22va
(22)
Combining Eqs. (20) and (22) yields
22v2 2 1x 24v 222
2 2'vd-1
(d 2 16),
which is contradiction.
Case II. Σ Eimar V/ tmax /2. A similar argument gives a contradiction by defining
X1 {ar [/max] yi 1}, and X X1 P.
As before,
[ 2 mma d22vd+1 2 24v2 d22vd+1
(23)
2
for all d N. However, [W'1) 22v and Item 2 imply that
|x|] < 3vd,
(24)
which is contradiction.
D.4.3 Performance of Best Expert
Claim D.7 (Existence of expert with large weight). Let d, E N, d2 16, let 7 S 13T and let T1y..., on Ta. Consider an execution of
TRANSOCTIVELEANNERCH T2......... Inn)
as in Algorithm 5. Then, at the end of the execution, there exists En+1 such that
w(e) 2 1-1/
(25)
Note that the lower bound in Eq. (25) does not depend on n.
Proof. Fix a hypothesis h H such that h((a))) ye for all [n] (such h exists because the adversary must always select a realizable label).
By Claim D.4, there exists e En+1 that assumption-comee consistent with h. Let ancestry (1)+1) (ef, e .... 1. ). We argue that this ancestry sequence makes few mistakes. Specifically, for each t (n), let 0r ExPeRT.PREDICT(C. xx). We claim that
= Σ 1(t + vx) S 24vd.
+ 3r be the of indices where a mistake was made. For each t E B. let e² (S, H), and note that each E B has a corresponding execution of EXPERT. PREDICT (e,, Jt), and an execution of e₂ = CAPERT.BASICUPDDTEEE... It, yt) followed by EXPERT. EET.RREEEEENEEDPPAEEEEE
Indeed, let B {t E [n]
-t, yt) that produces e (EXPERT. EXTENDEDUPDATE is ex- ecuted because B, i.e., a mistake was made). We partition the indices B into six cases (six disjoint sets), and bound the number of indices that fall in each.
35

---

Case I. The execution of EEXPERT.PREDICTEE x4) exited via the first return statement in that procedure. This happens once | I 22vd and from that point on, the expert and all subsequent experts in the ancestry are exactly simulating the HALVING algorithm (Algorithm 7) in both predictions and updates. Hence, by Fact E.I, B contains at most m, = 2 such indices.
Case II.
The execution of that procedure. In particular u, and the predicted label was y2 _f = 5 E {0.1} such that di <á u. Because ej is assumption-consiser that E path(h). Namely, we see that is a I-descendant of I and u. E path(h). It
PREDICT(T, .x)) exited via the second return statement in
with h, Item in Claim D.5 implies
follows that De b = h(x))) yt- So no mistakes are made in Case II, and the number of indices & E B that belong to Case II is simply mn 0.
In the remaining cases, assume that in that procedure, so the prediction was
exited via the third return statement
07 = 1([S |8|/3),
(26)
where S = fxd' S: Ie 3i x'}. These cases follows.
Case III.
The execution of EXPPERT.XTTENDEDDUPAATEELS statement in that procedure. Namely, after the update, the resulting expert e has [H] < 22vd, However, because we are not Case I, at the beginning of the iteration expert et had |H| > 22vd, Seeing as the cardinality of H decreases monotonically throughout the ancestry ei, c this type of mistake can happen at most mm = times.
Me) exited via the first return
Case IV. The execution of EXPERT. EXTENEE Ir. Vt) exited via the second return statement in that procedure. In this case, [S(1=,)| [S|/3, and 6 (S" u, H) with 5" = S1 So |S 2/S1/3. Namely, the update causes the cardinality of the set to be multiplied by a factor of at most 2/3 and it strictly decreases. Seeing as the initial cardinality maxx and cardinalities are integers, the number of times this can happen is at most
log(+
4vd log(3/2) + 1.
mgy
13g(3/2)
+
(27)
In the remaining cases, we assume that the execution of EXPERT. EXTEEREEEEEEDEEUUPAEECCC,, 2t, Bt) exited via the third return statement in that procedure. This implies that
sgp: S |S|/3
(28)
Combining this with Eq, (26), follows e and therefore ye = 1. The remaining cases are as follows.
Case V. Iy phth(h). Let ef (S, u, H). Seeing as | > 22v (because we are not in Case I), Claim D.6 (with the assumption d > 16) implies that t S fmax- By Item
of Claim D.5, the facts 2t * u (we are in Case II) and x, E path(h) imply that
E S. In particular, S is not empty.
Because the implies that e'+1 = (Se, Mgg He). with S. = S US. Observe that
(t ++11 1) update of et+1 was assumption-consissen with h. Eq. (17)
|.S| < |S|/3 (plugging #f- = into Eq. (28)); and
|S1 < |S|/3 (because otherwise, by Eq. (26), the prediction would have been
0r 1).
Therefore,
SSel < |Sol + |S| < 2/5\/3.
(29)
As in Case IV, combining Eq. (29) and the fact that S is not empty imply upper bound my on the number of times Case V can happen, with the bound being the same number my my as in Eq. (27).
36

---

Case VI. & path(h). So (2e, yt) is a pair such that xı & path(h) and = 1. Assume for contradiction that this type of mistake can happen strictly more than
My 3
times. Let 11, 1,,2...... byy be the indices of the first my iterations of the outer 'for' loop of TRANsDUCTIVELEARNER
in which this type mistake happened. Note that if at the end of iteration Em we had expert m, (1t +0mmg+1+ H tmm,+
22va then from that point onwards. the expert would be simulating the halving algorithm, and in particular, it would not make any further mistake of the type in Case VI (all subsequent mistakes would belong Case I). Hence, by the assumption that strictly more than my mistakes were made, it follows that H mmm +1| > 22va Let
such that [
H {t' E H. (Vt [mm] : 1'(x,) A xe & path(h'))}
Because Emyy is assumption-consistoor with h, and from the construction of (mmi)) using He and Hę in EXPERT.EXTENDEDD there exist collections H _ H and X {a : [mw]] Ta such that
it follows that H Homgy +1 S H So
| +1mm > 22va
|X| Thn 33dd,
Vh' E H Vo E X 11
vh' E H Yo X: a & path(h').
This contradiction to the choice H. specifically, to Item Lemma D.2.
Thus, combining the analyses of all cases, we see that the number of mistakes made by the ancestry (11+1) most
m, + my + Mm my + my my
4vd
4vd 1og(3/2)
2vd+0+1+
+1)
+ +1) 3vd
log(3/2)
24Vd.
The weights satisfy
w(ci+1) = w(e?)
1r = y/
u((e))
Dt # yt-
This implies that w(e)+1) w/ desired.
I 4 1(0+#))
w(e?) 4 2 4-21/d 2-18V/ as
D.4.4 Multiplicative Weights Mistake Bound
Claim D.8 (Mistake bound for multiplicative weights). Let E N, let a 0, let H C (0. and let Z1...., E Ta. Consider an execution of
TRANSDCCIIVLEARREER (#1, (#1, "n,...,
as in Algorithm Assume that at the end of the execution, there exists e E Eatz such that
w(e") 2 2-a
Then TRANSDUCTVELEARNER makes at most a mistakes.
Proof of Claim D.8. For all i [n+ 1], let ((E)) ELER, w(e). For each [n]. if 9r yı, then w( (EEE+) I w( 22, Hence, if TRANSDUCTIVELEARNEE makes mistakes, then by induction
n
w(En+1) S w(E)) II
((,tt)) = 2 w(Ei).
[=1
37

---

So
2 S 5
Σ
w(e) w(En+1) s 2 ww(ii) 2
eEEnl1
We conclude that
m S a
as desired.
D.5 Proof
Proof of Theorem D. I. Fix an integer d 2 43. Let H C 13 be the class constructed by
invoking Lemma D.2 for the integer d 1 42. We argue that this class satisfies the requirements of Theorem D.I.
By construction, H is class Littlestone dimension precisely By Theorem A.7, this implies the equality in Item 2.
We now show the upper bound in Item 1. We argue that TRANSDUCTIVVLEARRERR (Algorithm 5) satisfies this upper bound. By Claim D.7, at the end of the execution of TRANSDUCTIVELEARNER
there exists expert E,+1 such that wie) 2 2-88 By Claim D.8, this implies that the number mistakes made by TRANSDUCTIVELEARNER
most 48yd, as desired.
E
Halving
Fact E.1. Let X be a set, and let H. S. {0, be a hypothesis class. Then for all n E N, all sequences x E X", and all realizable adversaries, HALVING (Algorithm 7) makes most log([H] mistakes in the transductive online learning (Game 2). 25 Namely,
sup sup Mrr(H, n. HALVING, A) S log( log((?)) EEN AEA,
With the suitable syntactic modification, it also makes at most log([?[)) mistakes in the standard online learning (Game 1).
38

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: Purely rigorous mathematical results. We explain precisely what our proof's imply (and therefore also what they do not imply).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer: [Yes]
Justification: For each theoretical result, the paper provides the full set of assumptions and complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper has no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
40

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/ httpe//uuieeeeeeeeeeaaaaiiiiiiie
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: ctsps.cc/public//eeeee guide// /CodeSubmia sgionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
41

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.
ines?
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The work is purely theoretical with no immediate direct societal impacts forseeable.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
42

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
43

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
44

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMS any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy bectps://neurppe:: httpeeepss../oooeeeeeeeeeeeeeeee cct//oomffeeencc//22///111 for what should or should be described.
45


Reviews:
[{"review_id": "XeGODW5b1i", "reviewer": "Reviewer_neK2", "summary": "In the standard online learning model, the minimum number of mistakes made by the learner is exactly characterized by the Littlestone dimension of the hypothesis class. \nThis paper exactly characterizes the minimum number of mistakes in the transductive version (where the learner knows the test data in advance) by showing that there are classes of Littlestone dimension $d$ on which no learner can do better than $\\Omega(\\sqrt{n})$ mistakes, and conversely that if the LD is $d$ then the learner can always learn with $O(\\sqrt{n})$ mistakes", "questions": "This is sort of a history question: What do you think was the big insight or connection that let you solve the problem? Or from another perspective, what was blocking the previous papers from getting this bound? All the steps seemed almost obvious when reading your paper (which to be clear I don't think is a bad thing).", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "+ Exceptionally well-written paper. Well written proofs, good mix of intuition and formalisms, detailed pseudocode for everything. I enjoyed reading it.\n+ Resolves a ~30-year-old open question with a tight bound.\n? I haven't read the previous bounds on the problem, so I don't know how much the paper innovated in terms of proof ideas.\n- I wish I wrote it.", "was_revised": true, "final_justification": "No change", "rebuttal": "We’re very grateful for the reviewer’s heartwarming comments and score. This kind of encouraging feedback is both humbling and motivating. Thank you for engaging with our work so thoughtfully.\n\n> This is sort of a history question: What do you think was the big insight or connection that let you solve the problem? Or from another perspective, what was blocking the previous papers from getting this bound? All the steps seemed almost obvious when reading your paper (which to be clear I don't think is a bad thing).\n\nThank you for this question! Looking back at our work, we actually don’t believe that there is a single big insight that leads to this result. Rather, it followed from a process (typical in mathematics) of tinkering with a number of specific examples, carefully considering some proofs and seeing whether they can be pushed further, or whether one can prove lower bounds that would preclude improvements, etc. \n\nAs a first point, one needs to understand what is the correct statement to be proved, namely, bounds of $\\Theta(\\sqrt{d})$. But it is hard to say where $\\sqrt{d}$ comes from. Consider:\n * In the PAC setting, unlabeled data doesn’t help. So one could conjecture that there is a lower bound of $\\Omega(d)$.\n * On the other hand, the previous lower bound of $\\Omega(\\log d)$ is actually tight (cannot be improved) if the adversary presents a sequence consisting of the entire Littlestone tree in breadth-first order (as was the case in [1]). So one could conjecture that this is true for all sequences, and therefore that there is an upper bound of $O(\\log d)$.\n * Even now, it is not clear that there is a simple and concise intuition for where the  $\\sqrt{d}$ comes from.\n\nNext, consider the upper bound. It involves constructing a hypothesis class at random, and then utilizing properties of that class in order to learn with few mistakes. While the probabilistic method is of course very common in discrete math, this is arguably not a very typical use case — randomized constructions are more commonly used to obtain “hard instances”: random functions are hard to learn, adding random noise is conjectured to makes it hard to learn linear functions (LPN), refuting random 3-SAT instances is conjectured to be hard [2], random strings are provably hard to compress (Kolmogorov), etc. In contrast, in our proof, we construct a randomized class so that it will be *easy* to learn.\n\nAdditionally, the proofs of the upper bound and lower bounds are very different from each other. Often there is some sort of “correspondence” between elements in the proofs of matching lower and upper bounds, but this does not appear to be the case here.\n\nFor the lower bound, the paper [2] offered a characterization of the transductive mistake bound, but that characterization somewhat obscures or deemphasizes the tree structure of the hypothesis class, which turns out to play an important role in our proof and in [1]. \n\nThat being said, one important insight that allowed us to obtain our improved results, was that in the proof of the previous lower bound in [1], the adversary presents *all* the nodes in the Littlestone tree, and this can be bad for the adversary because some nodes are easy to guess, but still leak a small amount of information about the correct labeling function. Therefore, to obtain a stronger lower bound, one can try to present only a subset of the (“harder to guess”) nodes in the tree.\n\n---\n\n[1] Hanneke, S., Moran, S., & Shafer, J. (2023). A trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36, 19502-19519.\n\n[2] Ben-David, S., Kushilevitz, E., & Mansour, Y. (1997). Online learning versus offline learning. Machine Learning, 29(1), 45-63.\n\n[3] Feige, U. (2002). Relations between average case complexity and approximation complexity. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (pp. 534-543)."}, {"review_id": "m6KbsEgWQd", "reviewer": "Reviewer_zo5C", "summary": "This paper provides improved lower and upper bounds on mistakes for transductive online learning, providing tight guarantees and showing a gap between transductive and standard online learning. The proof technique is intuitive to follow and relies on multiple techniques from the field including the halving algorithm and multiplicative weights algorithm.", "questions": "1. What is the computational efficiency of the algorithm for proving the upper bound? It seems that in the worst case, there could be exponential experts (or probably even super-exponential). Is that correct? Do the authors think the computational efficiency can be improved?", "limitations": "I think this paper does not have any major limitations, but a discussion of the computational efficiency of the algorithm could also add some value.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The main strength of the paper is the novelty and clarity. It solves a 30-year-old open problem by providing matching upper and lower bounds for mistakes in transductive online learning. The proof is also exposed intuitively in the main paper, which makes it easier to understand. I do think the proof is correct based on the exposition in the main paper, but I have not verified the calculations in the appendix. I do not see any major weaknesses in the work.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your supportive review!\n\n> What is the computational efficiency of the algorithm for proving the upper bound? It seems that in the worst case, there could be exponential experts (or probably even super-exponential). Is that correct? Do the authors think the computational efficiency can be improved?\n\nThanks for raising the question of computational efficiency, which is a very interesting topic! We will include this in the Open Questions section in the final version. More broadly, we will also add a discussion on this topic along the following lines. \n\nFirst, one needs to define what computational efficiency means in this context. Kakade & Kalai [1] consider a transductive learner to be efficient if it runs in time $\\mathsf{poly}(n)$, where $n$ is the length of the sequence $x_1,\\dots,x_n$. In their setting they consider the VC dimension to be constant, ignoring the runtime dependence on the VC dimension or the size of the class, etc.\n\nIn our upper bound, we construct a class of Littlestone dimension d with a domain of size roughly $2^d$, and a learning algorithm that makes at most $O(\\sqrt{d})$ mistakes. The algorithm runs in time polynomial in $n$ and the number of experts. Each expert is associated with a subset $H$ of the hypothesis class, and at each time step these subsets are disjoint, so the number of experts is at most the number of hypotheses in the class. Therefore the algorithm runs in time $\\mathsf{poly}(2^d, n)$ which is polynomial in $n$ but is not efficient. (However, the runtime is not super-exponential.)\n\nNote, however, that in our case the class is constructed randomly. Therefore it would be reasonable to think that the learning algorithm receives a description of the hypothesis class as one of its inputs. Such a description would essentially be a $2^d \\times 2^d$ binary matrix. So under this view, our runtime of $\\mathsf{poly}(2^d, n)$ is polynomial (and potentially even *sublinear*) in the input length.\n\nIt is an interesting open question whether there exists a learning algorithm $A$ and a sequence of classes $\\mathcal{H}_1, \\mathcal{H}_2, …$, such that for every integer $d$:\n * $\\mathcal{H}_d$ has Littlestone dimension $d$, and \n * Given as input the index $d$ and a sequence $x_1,\\dots,x_n$, $A$ runs in time $\\mathsf{poly}(d, n)$, and makes at most $O(\\sqrt{d})$ mistakes assuming that the labels are realizable by $\\mathcal{H}_d$. \n\nA natural variation is to ask for an *oracle efficient* algorithm: an algorithm that runs in time $\\mathsf{poly}(d, n)$ using access to an ERM oracle for the hypothesis class $\\mathcal{H}_d$ (or some other similar oracle).\n\n---\n\n[1] Kakade, S., & Kalai, A. T. (2005). From batch to transductive online learning. Advances in Neural Information Processing Systems, 18."}, {"review_id": "cIXRJsnUwz", "reviewer": "Reviewer_EVTg", "summary": "This paper solves a long-standing open problem concerning the power of unlabeled data in online learning. The authors prove rigorously that, in the transductive online setting, the optimal mistake bound is $O(\\sqrt{d})$, where $d$ represents the Littlestone dimension of the hypothesis space $\\mathcal{H}$. Such optimal bound constitutes an exponential improvement over previous lower bound of $\\Omega(\\log{(d)})$, and also improves upon the best known upper bound of $2/3 d$. Overall, this work provides milestone theoretical results to demonstrate the power of unlabeled data in transductive online learning.", "questions": "(1)\tCould you please give more explanations for which proof idea is essential to derive improved mistake bounds when compared with the latest work Hanneke, Moran, and Shafer (2023) ?\n\n(2)\tCould you please introduce more related works about the optimal mistake bound for standard online learning?", "limitations": "(1)\tThis paper exceeds the page limit (nine pages).", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n(1)\tThe proofs are novel and truly technical. I first need to admit that I am not an expert in the field of mistake bounds for transductive online learning, and I am sorry to say I am not familiar with the combinatorial technique to deal with Littlestone dimension. Therefore, it is hard for me to check the proof in very detail, and I could only read the proof as possible as I can. However, according to my experience, the proofs for the optimal mistake bound are elegant and look correct.\n\n(2)\tThe exponential improvement over previous lower mistake bound of $\\Omega(\\log{(d)})$ is a great breakthrough. I read the technical ideas in Section 2.2 and am convinced that it is true.\n\n(3)\tThe improvement from the best known upper bound of $2/3d$ to $O(\\sqrt{d})$ is also very technical and novel. \n\n**Weaknesses**\n\n(1)\tI am convinced that this is a very solid work. However, for reader’s convenience (especially for readers not in this field), it is suggested to give more explanations for which part of proof is new and which idea is borrowed from the existing work of Hanneke, Moran, and Shafer (2023).\n\n(2)\tFor the exhibition of the proof idea for the upper bound, it is truly hard for me to read the so length words in Sections 2.3.1-2.3.5. I would suggest defer the length proof technique description to the appendix, and give more concise lemmas/claims/mathematic notations in the main paper, to show mathematically how to derive improved mistake upper bound. In the current version, it is still truly hard for me to catch the essence of main proof strategy.\n\n(3)\tThe related works section does not introduce the optimal mistake bound for standard online learning setting. It will be easier to see the benefits of access to unlabeled data in online learning when compared with the optimal mistake bound in the standard online setting.\n\n(4)\tThis paper actually exceeds the page limit.", "was_revised": true, "final_justification": "Thanks authors for their detailed responses. It is true that exhibiting Technical Overview instead of mathematical notation the in the main paper has its merit, especially for a truly technical paper. Overall, I believe this is a very nice paper according to its very strong optimal mistake bound and the technical proof technique. I will raise my score and congratulation to the authors.", "rebuttal": "Thank you very much for your thoughtful and constructive review. Your comments — including your suggestions to clarify what is new in our work, to improve the presentation of the upper bound, and to make the standard online learning setting more accessible — will help us improve the clarity and presentation of the paper.\n\n# Weaknesses\n\n> (1) I am convinced that this is a very solid work. However, for reader’s convenience (especially for readers not in this field), it is suggested to give more explanations for which part of proof is new and which idea is borrowed from the existing work of Hanneke, Moran, and Shafer (2023).\n\nAbsolutely! The upper bound is new, and does not have a direct analog in [1]. For the lower bound, there are a number of important differences between our proof and theirs:\n 1. They use an adversary that presents all the nodes in the Littlestone tree, in breadth-first order. However, one can show an upper bound of $O(\\log d)$ mistakes for any adversary that  presents all the nodes in the Littlestone tree in breadth-first order, so in that sense their technique cannot be improved. To overcome this limitation, we devise an adversary that presents only a subset of the nodes in the tree (see Algorithm 2, “ConstructSequence”). The intuition here is that presenting all the nodes in the tree can be bad for the adversary because some nodes are easy to guess, but still leak a small amount of information about the correct labeling function. Therefore, to obtain a stronger lower bound, one can try to present only a subset of the (“harder to guess”) nodes in the tree.\n 2. The proof of the lower bound in [1] actually contains a somewhat complex adversary that maintains a parameter $\\varepsilon_t$ that is an inverse of a double exponential in the number of mistakes that have been forced so far (see Algorithm 1 in [1]). Because we present a shorter sequence with labels that are “harder to guess”, we are actually able to simplify this somewhat cumbersome aspect of their proof, and use a single value $\\varepsilon$ that remains constant (see Algorithm 1 in our paper). \n\n> (2) For the exhibition of the proof idea for the upper bound, it is truly hard for me to read the so length words in Sections 2.3.1-2.3.5. I would suggest defer the length proof technique description to the appendix, and give more concise lemmas/claims/mathematic notations in the main paper, to show mathematically how to derive improved mistake upper bound. In the current version, it is still truly hard for me to catch the essence of main proof strategy.\n\nWe can understand a preference for mathematical notation over textual description. However, at present, the appendices contain 24 pages of nontrivial mathematical proofs, including definitions, pseudocode, equations, etc. We don’t feel that the proofs could really be made to fit in the 9 pages of the main text, even in a condensed and abbreviated form. If we tried to do so, the result might be hard to understand without the full definitions and pseudocode, etc., and it would likely be confusing and inaccurate. \n\nTherefore, the choice we made for presenting our work was to include a clear (but condensed) statement of our results in Theorem 1.1, and then provide a Technical Overview that explains the main ideas, ingredients, and steps of our proofs at an intuitive level, while referring the reader to specific formal definitions, lemmas, and algorithms in the appendix. Our hope is that after reading the Technical Overview, readers will have a general idea of how the proofs work, and they will be able to read the details of the formal proofs more easily.\n\nWe feel that this method of presentation makes sense, but we are of course open to hearing suggestions. Are there any specific changes to the Technical Overview that you feel would make it clearer?\n\nPer your feedback, using the space from the additional 10th page in the camera-ready version of the paper, we will try to add to the main paper a back-of-the-envelope calculation that at least gives a feeling for how the quantity $\\sqrt{d}$ arises in the bounds.\n\n> (3) The related works section does not introduce the optimal mistake bound for standard online learning setting. It will be easier to see the benefits of access to unlabeled data in online learning when compared with the optimal mistake bound in the standard online setting.\n\nThank you for pointing this out! Presently, the classic characterization of the mistake bound for the standard setting using the Littlestone dimension is mentioned already in the abstract, and it is mentioned again in the Related Work sections — but you are correct that the formal statement of this result appears only later on, in the appendix (specifically, in Theorem A.7). To make the paper more readily accessible to a broad audience, we will make the following additions:\n * On page 2, right after defining the number of mistakes $M_{\\mathsf{std}}$ in the standard setting, we will note that this quantity is characterized by the Littlestone dimension, and refer the reader to Theorem A.7 for the full details.\n * In the Related Work section, when mentioning this result, we will again refer the reader to Theorem A.7 for full details.\n\n\n> (4) This paper actually exceeds the page limit.\n\nRespectfully, all content in our main submission PDF ends at the bottom of page 9 — and subsequent pages contain only references and the NeurIPS checklist. This adheres to the page limit in the NeurIPS Call for Papers.\n\nIn the supplementary material, for which no page limit exists, the main text minimally exceeds 9 pages due to merging documents and slight edits.\n\n# Questions:\n\n> (1) Could you please give more explanations for which proof idea is essential to derive improved mistake bounds when compared with the latest work Hanneke, Moran, and Shafer (2023)?\n\n[Repeating our response to Weakness (1):]\n\nAbsolutely! The upper bound is new, and does not have a direct equivalent in [1]. For the lower bound, there are a number of important differences between our proof and theirs:\n 1. They use an adversary that presents all the nodes in the Littlestone tree, in breadth-first order. However, one can show an upper bound of $O(\\log(d))$ mistakes for any adversary that  presents all the nodes in the Littlestone tree in breadth-first order, so in that sense their technique cannot be improved. To overcome this limitation, we devise an adversary that presents only a subset of the nodes in the tree (see Algorithm 2, “ConstructSequence”). The intuition here is that presenting all the nodes in the tree can be bad for the adversary because some nodes are easy to guess, but still leak a small amount of information about the correct labeling function. Therefore, to obtain a stronger lower bound, one can try to present only a subset of the (“harder to guess”) nodes in the tree.\n 2. The proof of the lower bound in [1] actually contains a somewhat complex adversary that maintains a parameter $\\varepsilon_t$ that is an inverse of a double exponential in the number of mistakes that have been forced so far (see Algorithm 1 in [1]). Because we present a shorter sequence with labels that are “harder to guess”, we are actually able to simplify this somewhat cumbersome aspect of their proof, and use a single value $\\varepsilon$ that is constant (see Algorithm 1 in our paper). \n\n> (2) Could you please introduce more related works about the optimal mistake bound for standard online learning?\n\nDefinitely! The paper that established this result is Littlestone [2]. This paper is already cited a number of times in the submission, but as we discuss in our response to Weakness (3) above, we will add direct references to the formal statement of this result (Theorem A.7) from page 2 and from the Related Works. Additionally, we will add references to expositions that are more accessible, including Chapter 21 in Shalev-Shwartz & Ben-David [3], Chapter 8 in Mohri, Rostamizadeh & Talwalkar [4], and the relevant sections in Cesa-Bianchi & Lugosi [5].\n\n# Limitations\n\n> (1) This paper exceeds the page limit (nine pages).\n\n[Repeating our response to Weakness (4):]\n\nRespectfully, all content in our main submission PDF ends at the bottom of page 9 — and subsequent pages contain only references and the NeurIPS checklist. This adheres to the page limit in the NeurIPS Call for Papers.\n\nIn the supplementary material, for which no page limit exists, the main text minimally exceeds 9 pages due to merging documents and slight edits.\n\n\n_______\n\n[1] Hanneke, S., Moran, S., & Shafer, J. (2023). A trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36, 19502-19519.\n\n[2] Littlestone, N. (1988). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4), 285-318.\n\n[3] Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.\n\n[4] Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of machine learning. MIT press.\n\n[5] Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press."}, {"review_id": "SQDXP7sHS7", "reviewer": "Reviewer_bNtP", "summary": "The authors consider the setting of transductive online learning for a concept class with a little stone dimension d.\nThe setting differs from the standard online learning in the sense that the sequence of samples is chosen before the learning stage and is revealed to the learner.\nThe object of interest is how many mistakes do the learner has make given the concept class has little stone dimension d.\nThe problem has been studied since the 90s with the best known lower and upper bound being log d and 2d/3 respectively\n(notably with the upper bound from 1997).\nThe authors give the tight upper and lower bounds showing that the correct answer is \\sqrt{d}.\n\nFor the lower bound, given that the sequence of samples is chosen properly s.t. satisfies the property in lines 143-146.\nThe author shows that the strategy for the adversary is to use a hard threshold on the ratio of the version space shrinking.\nAnd only force a mistake when the version space does not shrink faster than epsilon fraction.\nWhile it is easy to verify that if both properties are satisfied, then such a strategy does force an overall sqrt{d} mistakes for the learner.\nThe author didn't provide further intuition on how to select the sequence to satisfy the two needed properties in the main body.\n\nFor the upper bound, the authors need to construct a particular function class with little stone dimension d such that the learner can learn with at most \\sqrt{d} mistakes.\nThe main intuition here is to maximize the information obtained for each mistake the learner makes.\n(e.g., if 0 and 1 are half/half for the version space of a sample, then a mistake here would only reveal 1 bit to the learner)\nSo the high-level idea is to make each sample have value 1 for a very small subset of the version space.\nAnd the learner would always guess 0, so that if there is an error, this immediately shrinks the version space by a lot.\nWhile this idea seems plausible at a high level, the authors show that there are significant techniques required to implement it.\nIn particular, there are two types of samples, on-path samples and off-path samples.\nThey cannot implement this strategy on on-path samples, as they need on-path samples to maintain the required little stone dimension.\nSo they can only implement it on off-path samples.\nThen, from my understanding, the difficulties are the following:\n1. The adversary might be able to pile up on-path samples in the front before the learner can use off-path samples to learn the sparse encoding\n2. The learner does not know whether a sample is on-path or off-path, which depends on the unknown target function.\n3. When to transition from limiting on path-samples to halving the version space. \nThe author resolves the problems by using a multiplicative algorithm on the splitting experts.", "questions": "While the sparse encoding strategy for the upper bound makes sense,\nit does require the domain of the function class to be sufficiently large (from my understanding).\nAs someone who is not familiar with online learning,\nwould it make sense to consider this setting with a restriction on the domain size?\nAnd if so, would that change the sample complexity?", "limitations": "No, although I don't see any particular limitation that needs to be addressed here.\nThe authors have established the tight lower bound for the problem.\nAlthough it would be better if they could discuss open problems and potential future directions.", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The authors established the tight mistake bound in the setting of transductive online learning (for learning a concept class with little stone dimension d).\nThis solves a long-standing open problem.\nThe paper is also well-presented with enough intuition to explain the high-level construction of both the upper and lower-bound.\nRegarding weaknesses, I do feel like a more concrete (formal) definition of on-path/off-path labels would better help the readers understand the obstacles described in 223-247 if possible.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their generous score and for raising thoughtful and technically insightful questions. We especially appreciate the technical depth reflected in their questions, which is all the more notable given the self-reported low confidence.  We intend to consider and include these open questions in a future revision, with proper acknowledgment of the anonymous reviewer.\n\n# Weaknesses\n\n> Regarding weaknesses, I do feel like a more concrete (formal) definition of on-path/off-path labels would better help the readers understand the obstacles described in 223-247 if possible.\n\nYes, this makes sense of course. Conceptually, given a Littlestone tree, each function in the class corresponds to a root-to-leaf path in the tree. The *on-path* nodes for a function are simply the nodes on that root-to-leaf path. This is mentioned in line 116 and in footnote 9, and is illustrated in Figure 1c. The formal definition is stated in Definition A.5 (lines 463-470). We will explicitly clarify in Definition A.5 that “on-path” refers to nodes that are on the path, as it is defined in that location.\n\n# Questions:\n\n> While the sparse encoding strategy for the upper bound makes sense, it does require the domain of the function class to be sufficiently large (from my understanding). As someone who is not familiar with online learning, would it make sense to consider this setting with a restriction on the domain size? And if so, would that change the sample complexity?\n\nThank you for noticing this — yes, and this is a **very** insightful point! \n\nAt present, we show an upper bound of $O(\\sqrt{d})$ mistakes using a class that has $2^d$ functions on a domain of size roughly $2^d$. \n\nClearly, it is not possible to obtain such an upper bound with a domain of size $d$, because a set of $2^d$ functions on a domain of size $d$ is simply the set of all functions on the domain — and so the adversary can force a mistake on each point in the domain (in other words, the VC dimension will be $d$ as well). \n\nBut what about a domain of size, say, $2d$, $d^2$, $\\mathsf{poly}(d)$, or $2^{\\sqrt{d}}$? Is there some nice tradeoff between domain size and the best upper bound? These are very good questions, and we don’t know the answers. We will include them in the Open Questions section in the camera-ready version.\n\nThanks again for contributing this great technical question — it shows significant insight into our work.\n\n# Limitations\n\n> It would be better if they could discuss open problems and potential future directions.\n\nDefinitely! The final version of the paper is allowed to include an additional page, and in that page we will have a Future Directions section. It will include:\n * Open questions (contributed by Reviewer zo5C): Is it possible to achieve the upper bound with an efficient learning algorithm? (See further discussion in our answer to Reviewer zo5C)\n * Open question (contributed by you, Reviewer bNtP): for a class of Littlestone dimension $d$, what is the tradeoff between the domain size, and the best upper bound? (As discussed above.)\n * Open question: Can we get finer asymptotic bounds? I.e., what are the “correct” (tightest) constants hidden by the $\\Omega(\\sqrt{d})$ and $O(\\sqrt{d})$ notation in the lower and upper bounds? For example, is there some constant $C > 0$ such that the answer is $(C+o(1)) \\sqrt{d}$."}]

Author rebuttal:

Meta-review: This paper solves a long-standing open problem concerning the power of unlabeled data in online learning. It provides an improved lower and upper bounds on mistakes for transductive online learning, providing tight guarantees and showing a gap between transductive and standard online learning. 

Reviewers are all very positive about the contributions as well as the quality of presentation.
Decision: Accept (oral)