最优随机适当在线学习

# Optimal Randomized Proper Online Learning
Source: [https://arxiv.org/html/2609.21445](https://arxiv.org/html/2609.21445)
###### Abstract

We prove that the optimal expected mistake bound of online learning a function classℋ\\mathcal\{H\}by a randomized proper learning algorithm isO⁡\(𝙻⁡\(ℋ\)​log⁡T\)O\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log T\), where𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\)is the Littlestone dimension ofℋ\\mathcal\{H\}andTTis the time horizon\. Our result improves upon the previously best known bound ofO⁡\(𝙻⁡\(ℋ\)​log6​T\)O\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log^\{6\}T\)given by\[[7](https://arxiv.org/html/2609.21445#bib.bib14)\]\(STOC 2022\), and is optimal up to a universal constant for worst\-case classes\.

## 1Introduction

The adversarial online learning model dates back to the fundamental work of Littlestone\[[14](https://arxiv.org/html/2609.21445#bib.bib3)\]\. It is defined as a game played between a learner𝖫𝗋𝗇\\mathsf\{Lrn\}and an adversary𝖠𝖽𝗏\\mathsf\{Adv\}forTTmany rounds, in the presence of a concept classℋ\\mathcal\{H\}of predictorsh:𝒳→\{0,1\}h:\\mathcal\{X\}\\to\\\{0,1\\\}, where the domain𝒳\\mathcal\{X\}is any set\. At each roundt∈\[T\]t\\in\[T\], the learner sends a classifierft:𝒳→\{0,1\}f\_\{t\}:\\mathcal\{X\}\\to\\\{0,1\\\}to𝖠𝖽𝗏\\mathsf\{Adv\}, and𝖠𝖽𝗏\\mathsf\{Adv\}responds with a labeled example\(xt,yt\)∈𝒳×\{0,1\}\(x\_\{t\},y\_\{t\}\)\\in\\mathcal\{X\}\\times\\\{0,1\\\}\. The learner suffers the 0/1 loss1\[ft\(xt\)≠yt\]1\[f\_\{t\}\(x\_\{t\}\)\\neq y\_\{t\}\]\. In the realizable setting considered in this paper, the adversary is restricted to output examples that are consistent with some*target*h⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}\. That is, there must beh⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}such thath⋆​\(xt\)=yth^\{\\star\}\(x\_\{t\}\)=y\_\{t\}for allt∈\[T\]t\\in\[T\]\. We denote the minimax optimal*total loss*\(or*mistake bound*\) of the learner in this setting by𝙼⁡\(ℋ,T\)\\mathtt\{M\}\(\\mathcal\{H\},T\)\. If there existsM<∞M<\\inftysuch that𝙼⁡\(ℋ,T\)≤M\\mathtt\{M\}\(\\mathcal\{H\},T\)\\leq Mfor allTT, we say that𝙼⁡\(ℋ,T\)\\mathtt\{M\}\(\\mathcal\{H\},T\)is*learnable*with optimal mistake bound at mostMM\.

The standard online learning model described above allows*improper learning*: the learner can use an arbitrary classifierft:𝒳→\{0,1\}f\_\{t\}:\\mathcal\{X\}\\to\\\{0,1\\\}, not necessarily one belonging toℋ\\mathcal\{H\}\. In this work, we study the more restrictive requirement of*proper learning*, under which every classifier used by the learner must belong to the given classℋ\\mathcal\{H\}\. Somewhat counter\-intuitively, even though the input sequence is realized by someh⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}, deterministic optimal proper learners can demonstrate total loss ofTT, even for extremely simple classes such as the class of singletons \(see\[[11](https://arxiv.org/html/2609.21445#bib.bib5)\]for example\)\. Therefore, the standard proper learning model allows randomization: in roundtt, instead of choosing a classifierht∈ℋh\_\{t\}\\in\\mathcal\{H\}, the learner chooses a distributionPtP\_\{t\}overℋ\\mathcal\{H\}, and the suffered loss is the probability thathth\_\{t\}drawn fromPtP\_\{t\}misclassifiesxtx\_\{t\}\. We denote the minimax optimal total loss \(or*expected mistake bound*\) of a randomized proper learner by𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)\.

In contrast with the improper learning model, where it is known that an optimal deterministic learner is worse than any randomized learner by at most a multiplicative factor of22, the proper learning scenario reveals a completely different picture: it is well known that for any learnable classℋ\\mathcal\{H\}we have𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)=o⁡\(T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=o\(T\)\[[11](https://arxiv.org/html/2609.21445#bib.bib5),[7](https://arxiv.org/html/2609.21445#bib.bib14)\]\. However, prior to this work, there were no tight bounds on𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)for general learnable classes\. Our work shows that𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)=Oℋ​\(log⁡T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=O\_\{\\mathcal\{H\}\}\(\\log T\)for any learnable classℋ\\mathcal\{H\}, and that there exist learnable classes for which the upper bound is tight\.

The fundamental combinatorial parameter governing𝙼⁡\(ℋ,T\)\\mathtt\{M\}\(\\mathcal\{H\},T\)is the*Littlestone dimension*ofℋ\\mathcal\{H\}, denoted by𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\)\(see formal definition and all relevant background in Section[3](https://arxiv.org/html/2609.21445#S3)\)\. The classic work of Littlestone\[[14](https://arxiv.org/html/2609.21445#bib.bib3)\]gives an exact characterization of𝙼⁡\(ℋ,T\)\\mathtt\{M\}\(\\mathcal\{H\},T\): it proves that𝙼⁡\(ℋ,T\)=min⁡\{𝙻⁡\(ℋ\),T\}\\mathtt\{M\}\(\\mathcal\{H\},T\)=\\min\\\{\\mathtt\{L\}\(\\mathcal\{H\}\),T\\\}for allℋ,T\\mathcal\{H\},T\. The online learner achieving this minimax optimal loss bound, termed*SOA*\(Standard Optimal Algorithm\) is generally improper\. This characterization of the improper minimax total loss via𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\)provides a clean and appealing characterization, however, there are settings in which an improper prediction is not a valid output\. The classℋ\\mathcal\{H\}may encode a prescribed model family, a collection of feasible decisions, or the available actions of a player in a repeated game\. In these cases, a classifier outsideℋ\\mathcal\{H\}may have no meaningful implementation\. Proper learning also preserves the semantic, structural, or interpretability constraints that motivated the choice ofℋ\\mathcal\{H\}\. It is therefore natural to ask how much predictive performance must be sacrificed when the learner is required to use only hypotheses from the class being learned\. See, for example,\[[4](https://arxiv.org/html/2609.21445#bib.bib16)\]for more discussion on the importance of proper learning\.

### 1\.1Results

We prove the following theorem\.

###### Theorem 1\.1\. For any domain𝒳\\mathcal\{X\}, for any classℋ⊂\{0,1\}𝒳\\mathcal\{H\}\\subset\\\{0,1\\\}^\{\\mathcal\{X\}\}and for any time horizonT≥2T\\geq 2:𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)=O⁡\(𝙻⁡\(ℋ\)​log⁡T\)\.\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=O\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log T\)\.Furthermore, the upper bound is tight in the sense that for everyd∈ℕ\+d\\in\\mathbb\{N\}\_\{\+\}there exists a classℋ\\mathcal\{H\}such that𝙻⁡\(ℋ\)=O⁡\(d\)\\mathtt\{L\}\(\\mathcal\{H\}\)=O\(d\), and yet for anyT≥d2T\\geq d^\{2\}it holds that𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)=Ω⁡\(𝙻⁡\(ℋ\)​log⁡T\)\.\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=\\Omega\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log T\)\.

The best known upper bound prior to our work wasO⁡\(𝙻⁡\(ℋ\)​log6​T\)O\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log^\{6\}T\), given in\[[7](https://arxiv.org/html/2609.21445#bib.bib14)\]\. Their work considered a more general regression setting, and derived the upper bound for classification as a special case\. The previously best known lower bound was the standard lower bound of𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\)\(for large enoughTT\) for improper learning given in\[[14](https://arxiv.org/html/2609.21445#bib.bib3)\]\. See Table[1](https://arxiv.org/html/2609.21445#S1.T1)for a summary of previous and current bounds\. Determining whether a polylog\(T\)\(T\)factor is necessary or not in𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)was explicitly raised as an open question in\[[7](https://arxiv.org/html/2609.21445#bib.bib14)\]\. Theorem[1\.1](https://arxiv.org/html/2609.21445#S1.Thmtheorem1)shows that alog⁡T\\log Tfactor is indeed sometimes necessary, and is always sufficient\. Note that while the upper bound holds for all classes, the lower bound holds only for some classes\. This is not an artifact of our lower bound’s proof: it is not hard to find classes for which the optimal proper mistake bound is𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\), even using a deterministic proper learner\.

We prove Theorem[1\.1](https://arxiv.org/html/2609.21445#S1.Thmtheorem1)in Sections[4](https://arxiv.org/html/2609.21445#S4)\-[5](https://arxiv.org/html/2609.21445#S5): Section[4](https://arxiv.org/html/2609.21445#S4)contains the proof of the upper bound, and Section[5](https://arxiv.org/html/2609.21445#S5)contains the proof of the lower bound\.

Table 1:Summary of previous and current bounds for proper online learning\. The lower bounds hold for any large enoughTT\. The comment in the last row means that for anyd∈ℕd\\in\\mathbb\{N\}there exists a classℋ\\mathcal\{H\}with𝙻⁡\(ℋ\)=O⁡\(d\)\\mathtt\{L\}\(\\mathcal\{H\}\)=O\(d\)for which the lower bound holds\. That is, the lower bound does not hold for allℋ\\mathcal\{H\}\. This is not an artifact of the lower bound’s proof: it is not hard to find classes for which the optimal proper mistake bound is𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\), even using a deterministic proper learner\.
### 1\.2Comparison with the PAC setting

The price of proper learning \(compared to improper learning\) was also studied in the classic statistical PAC learning framework, and our results have close analogues to results proved in the PAC setting\. Let us briefly recall the PAC learning scenario\. Given a sample sizeTT, an adversary fixes a secret distribution over the domain𝒳\\mathcal\{X\}and an unknown target concepth⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}\. The learner receives an iid labeled sample

S:=\(x1,h⋆​\(x1\)\),…,\(xT,h⋆​\(xT\)\),x1,…,xT∼DS:=\(x\_\{1\},h^\{\\star\}\(x\_\{1\}\)\),\\ldots,\(x\_\{T\},h^\{\\star\}\(x\_\{T\}\)\),x\_\{1\},\\ldots,x\_\{T\}\\sim Dand in response outputs a classifierf:𝒳→\{0,1\}f:\\mathcal\{X\}\\to\\\{0,1\\\}\. Since in the online setting the learner is evaluated against allTTinstances in the input sequence and we wish to compare the price of proper learning in both settings, it is convenient to measure the loss offfas its expected error overTTmany freshly drawn instances drawn iid fromDD\(instead of just one test instance, as usually done in the PAC learning setting\)\. We denote the minimax optimal total loss in this setting as𝙼𝖯𝖠𝖢​\(ℋ,T\)\\mathtt\{M\}^\{\\mathsf\{PAC\}\}\(\\mathcal\{H\},T\)\. We also define the minimax optimal loss in the same setting when the learner is required to be proper, that is, to always outputf∈ℋf\\in\\mathcal\{H\}, as𝙼𝗉𝗋𝗈𝗉𝖯𝖠𝖢​\(ℋ,T\)\\mathtt\{M\}^\{\\mathsf\{PAC\}\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)\.

The work of\[[12](https://arxiv.org/html/2609.21445#bib.bib15)\]established that for any classℋ\\mathcal\{H\}and any large enough sample sizeTT,𝙼𝖯𝖠𝖢​\(ℋ,T\)=Θ⁡\(VC⁡\(ℋ\)\)\\mathtt\{M\}^\{\\mathsf\{PAC\}\}\(\\mathcal\{H\},T\)=\\Theta\(\\operatorname\{VC\}\(\\mathcal\{H\}\)\), whereVC⁡\(ℋ\)\\operatorname\{VC\}\(\\mathcal\{H\}\)denotes the VC\-dimension ofℋ\\mathcal\{H\}, which is the PAC\-analogue of the Littlestone dimension\. Similarly,\[[14](https://arxiv.org/html/2609.21445#bib.bib3)\]showed for the online setting that𝙼⁡\(ℋ,T\)=𝙻⁡\(ℋ\)\\mathtt\{M\}\(\\mathcal\{H\},T\)=\\mathtt\{L\}\(\\mathcal\{H\}\)\(forT≥𝙻⁡\(ℋ\)T\\geq\\mathtt\{L\}\(\\mathcal\{H\}\)\)\. For proper PAC learning, the classic bounds for ERM\[[18](https://arxiv.org/html/2609.21445#bib.bib11)\]show that𝙼𝗉𝗋𝗈𝗉𝖯𝖠𝖢​\(ℋ,T\)=O⁡\(VC⁡\(ℋ\)​log⁡T\)\\mathtt\{M\}^\{\\mathsf\{PAC\}\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=O\(\\operatorname\{VC\}\(\\mathcal\{H\}\)\\log T\)\.\[[6](https://arxiv.org/html/2609.21445#bib.bib18)\]showed that there are classes for which any optimal PAC learner must be improper, but this result is proved for the multiclass setting, where the label set size is larger than two\. The work\[[3](https://arxiv.org/html/2609.21445#bib.bib17)\]established an analog result for standard binary classification, and also gave a quantitative lower bound of𝙼𝗉𝗋𝗈𝗉𝖯𝖠𝖢​\(ℋ,T\)=Ω⁡\(VC⁡\(ℋ\)​log⁡T\)\\mathtt\{M\}^\{\\mathsf\{PAC\}\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=\\Omega\(\\operatorname\{VC\}\(\\mathcal\{H\}\)\\log T\)for some classes and large enoughTT, matching the analysis for ERMs\.

Our work completes the analog picture for online learning: While for all classes𝙼⁡\(ℋ,T\)=𝙻⁡\(ℋ\)\\mathtt\{M\}\(\\mathcal\{H\},T\)=\\mathtt\{L\}\(\\mathcal\{H\}\), Theorem[1\.1](https://arxiv.org/html/2609.21445#S1.Thmtheorem1)establishes that𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)=O⁡\(𝙻⁡\(ℋ\)​log⁡T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=O\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log T\)for all classes, and that this is tight for some classes\.

## 2Proof sketches

In this section, we sketch the main ideas of the proofs of the upper and lower bounds of Theorem[1\.1](https://arxiv.org/html/2609.21445#S1.Thmtheorem1)\. This section assumes some familiarity with standard concepts in learning theory and online learning theory\. The reader may consider to first skim through Section[3](https://arxiv.org/html/2609.21445#S3), where we define and state basic concepts and results, and Section[4\.1](https://arxiv.org/html/2609.21445#S4.SS1), where we present some more advanced tools used to prove the upper bound\.

### 2\.1Upper bound

Our starting point is that our benchmark algorithm is the SOA: we cannot hope that a proper learner will do much better than SOA\.111Even though in the proper setting we allow the learner to randomize its predictions, it is a well\-known fact that randomization does not help by more than a constant factor in the improper setting\.Therefore, it is natural to try approximating the SOA algorithm, and this is the most basic idea of the proof\. For a classV⊂\{0,1\}𝒳V\\subset\\\{0,1\\\}^\{\\mathcal\{X\}\}, we denote the classifier output by the SOA algorithm forVVas𝖲𝖮𝖠V\\mathsf\{SOA\}\_\{V\}, which is defined as

∀x∈𝒳:𝖲𝖮𝖠V​\(x\)=arg​maxr∈\{0,1\}⁡𝙻​\(Vx→r\)\.\\forall x\\in\\mathcal\{X\}:\\mathsf\{SOA\}\_\{V\}\(x\)=\\argmax\_\{r\\in\\\{0,1\\\}\}\\mathtt\{L\}\(V\_\{x\\to r\}\)\.In this spirit, a distributionPPover a set of functionsVVis calledϵ\\epsilon\-*good*if for allx∈𝒳x\\in\\mathcal\{X\}:

Prh∼P\[h\(x\)≠𝖲𝖮𝖠V\(x\)\]≤ϵ\.\\Pr\_\{h\\sim P\}\[h\(x\)\\neq\\mathsf\{SOA\}\_\{V\}\(x\)\]\\leq\\epsilon\.
For a small enoughϵ\\epsilon, if anϵ\\epsilon\-good distribution over the version space exists, it is intuitive that a proper learner may use it to predict and perform well\. Here, we do not get into the details of how small exactly shouldϵ\\epsilonbe for this intuition to hold, and simply assume that it is small enough\. The challenging part of the proof lies in the case where anϵ\\epsilon\-good distribution does not exist\. The heart of the proof lies in the following lemma that handles this situation, and might be of interest on its own right\.

###### Lemma 2\.1\(Small low\-dimensional cover\)\. LetV⊂\{0,1\}𝒳V\\subset\\\{0,1\\\}^\{\\mathcal\{X\}\}andϵ∈\(0,1\)\\epsilon\\in\(0,1\)\. If there is noϵ\\epsilon\-good distribution overVV, then there exists a natural numberk=poly⁡\(𝙻⁡\(V\)/ϵ\)k=\\operatorname\{poly\}\(\\mathtt\{L\}\(V\)/\\epsilon\)and a family of subsets ofVV,𝒱:=\{V1,…,Vk\}⊂𝒫⁡\(V\)\\mathcal\{V\}:=\\\{V\_\{1\},\\ldots,V\_\{k\}\\\}\\subset\\mathcal\{P\}\(V\)such that:1\.𝒱\\mathcal\{V\}coversVV:V⊂⋃i=1kVk\.V\\subset\\bigcup\_\{i=1\}^\{k\}V\_\{k\}\.2\.For alli∈\[k\]i\\in\[k\]:𝙻⁡\(Vi\)<𝙻⁡\(V\)\\mathtt\{L\}\(V\_\{i\}\)<\\mathtt\{L\}\(V\)\.

The role of Lemma[2\.1](https://arxiv.org/html/2609.21445#S2.Thmtheorem1)is to reduce the problem of learningVVto the problem of learningkkmany function classes, wherekkis small, and each class has a strictly smaller dimension than ofVV\. After this reduction, anϵ\\epsilon\-good distribution can be searched again for eachViV\_\{i\}\. If there is still someViV\_\{i\}with noϵ\\epsilon\-good distribution, we re\-apply Lemma[2\.1](https://arxiv.org/html/2609.21445#S2.Thmtheorem1)for it\. Since after each application of Lemma[2\.1](https://arxiv.org/html/2609.21445#S2.Thmtheorem1)the dimension decreases, eventually anϵ\\epsilon\-good distribution must be found, since when the dimension reaches00the problem becomes trivial and a00\-good distribution must exist\. This naturally induces a “win\-win” type of argument: If anϵ\\epsilon\-good distribution exists, we can use it to predict\. If not, we can apply Lemma[2\.1](https://arxiv.org/html/2609.21445#S2.Thmtheorem1)and reduce the dimension at the cost of splitting the problem to a not too large number of easier sub\-problems\.

At a technical level, the upper bound is proved with the help of three classic, yet powerful tools:

1. 1\.*The𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}proper algorithm*of\[[9](https://arxiv.org/html/2609.21445#bib.bib1)\], that aggregatesnndifferent learning rules and performs roughly as the best learning rule up to alog⁡n\\log nadditive factor\.
2. 2\.*The minimax theorem*\[[19](https://arxiv.org/html/2609.21445#bib.bib4)\], extended to infinite Littlestone games by\[[11](https://arxiv.org/html/2609.21445#bib.bib5)\]\.
3. 3\.*The existence of smallε\\varepsilon\-nets*for any distribution over a VC\-class\[[13](https://arxiv.org/html/2609.21445#bib.bib13)\]\.

Each of those tools is formally presented in Section[4\.1](https://arxiv.org/html/2609.21445#S4.SS1)\. Lemma[2\.1](https://arxiv.org/html/2609.21445#S2.Thmtheorem1)is proved via a simple, yet quite sophisticated combination of Item[2](https://arxiv.org/html/2609.21445#S2.I2.i2)and Item[3](https://arxiv.org/html/2609.21445#S2.I2.i3)\. The interested reader may find the details in the proofs of Lemma[4\.7](https://arxiv.org/html/2609.21445#S4.Thmtheorem7)and Lemma[4\.8](https://arxiv.org/html/2609.21445#S4.Thmtheorem8)\.

Item[1](https://arxiv.org/html/2609.21445#S2.I2.i1)is required as well since Lemma[2\.1](https://arxiv.org/html/2609.21445#S2.Thmtheorem1)splits the version space intokkmany version spaces, and we do not know which of them is the correct one\. We therefore use Item[1](https://arxiv.org/html/2609.21445#S2.I2.i1)to aggregate the predictions ofkkexperts, where each expertiiassumes thatViV\_\{i\}is the correct version space\. If Lemma[2\.1](https://arxiv.org/html/2609.21445#S2.Thmtheorem1)is applied more than once, then Item[1](https://arxiv.org/html/2609.21445#S2.I2.i1)is used to aggregate the prediction of more thankkexperts, but still not too many, since after every application the dimension decreases, and thus after at most𝙻⁡\(V\)\\mathtt\{L\}\(V\)many applications the class becomes trivial\. It is worth noting that the idea of aggregating predictions of several experts having different guesses on the nature of the problem was proven useful in previous works on online learning\[[2](https://arxiv.org/html/2609.21445#bib.bib6),[15](https://arxiv.org/html/2609.21445#bib.bib2),[8](https://arxiv.org/html/2609.21445#bib.bib10),[10](https://arxiv.org/html/2609.21445#bib.bib8)\]\.

### 2\.2Lower bound

We intuitively explain how a lower bound ofΩ⁡\(log⁡T\)\\Omega\(\\log T\)is obtained in the case thatTTis fixed in advance and the Littlestone dimension is11\. We then explain how the result can be extended to the case thatTTis not fixed in advance, and for any Littlestone dimension\.

We use the class of singletons overn=Tlog⁡Tn=\\frac\{T\}\{\\log T\}\(assuming for simplicity thatn∈ℕn\\in\\mathbb\{N\}\)\. Formally,ℋn:=\{hi:i∈\[n\]\}\\mathcal\{H\}\_\{n\}:=\\\{h\_\{i\}:i\\in\[n\]\\\}wherehi\(j\)=1\[i=j\]h\_\{i\}\(j\)=1\[i=j\]for allj∈\[n\]j\\in\[n\]\.

As long as the learner did not see some instance labeled with11, every instance not yet labeled with00could be labeled either with11or with00\. Therefore, the adversary only presents instances labeled with00\. It can use this strategy forn−1n\-1many instances, which is more than enough\. Given this behavior of the adversary, there are essentially two reasonable strategies \(or some mix of them\) for the learner:

1. 1\.Since every function predicts00on all instances except11and the adversary always labels instances with00, it makes sense to always predict by a uniform distribution overℋn\\mathcal\{H\}\_\{n\}: no matter what the adversary does, the learner is correct with probability1−1/n1\-1/n\.
2. 2\.Another reasonable strategy is to try to learn the correct target function, by using the uniform distribution only over functionshjh\_\{j\}such thatjjwas not yet labeled with00\.

Let us analyze the total loss suffered by each of those strategies\. For the first strategy, the total loss is

1n​T=log⁡TT​T=log⁡T\.\\frac\{1\}\{n\}T=\\frac\{\\log T\}\{T\}T=\\log T\.For the second strategy, the adversary presents the instances1,…,n−11,\\ldots,n\-1one by one, labeled with00\. Since the learner removeshjh\_\{j\}for anyjjalready labeled with00, its loss in roundj∈\[n−1\]j\\in\[n\-1\]is precisely1n−\(j−1\)\\frac\{1\}\{n\-\(j\-1\)\}\. Therefore its total loss is

∑j=1n−11n−\(j−1\)=∑i=2n1i=Ω⁡\(log⁡n\)=Ω⁡\(log⁡\(T/log⁡T\)\)=Ω⁡\(log⁡T\)\\sum\_\{j=1\}^\{n\-1\}\\frac\{1\}\{n\-\(j\-1\)\}=\\sum\_\{i=2\}^\{n\}\\frac\{1\}\{i\}=\\Omega\(\\log n\)=\\Omega\(\\log\(T/\\log T\)\)=\\Omega\(\\log T\)by the standard harmonic sum analysis\. So, the learner cannot escape from anΩ⁡\(log⁡T\)\\Omega\(\\log T\)total loss using those two reasonable strategies\. In the formal proof, we show that this is true in general using the same ideas\.

To extend the result to the case whereTTis not fixed in advance, we use a “gluing” technique \(see\[[5](https://arxiv.org/html/2609.21445#bib.bib9)\]for example\): we take a union of classes of the form defined above for all \(large enough\) values ofnn, which only increases the Littlestone dimension from11to22\. To extend the result for arbitrary valuesddof Littlestone dimension, one can use the class ofdd\-hamming spheres instead of the class of singletons\. The proof withdd\-hamming spheres builds on the same ideas and adds no significant complication\.

## 3Basic Preliminaries

### 3\.1Concept classes and the Littlestone dimension

Let𝒳\\mathcal\{X\}be a nonempty set called the*domain*\. A*concept*, or*hypothesis*, is a functionh:𝒳→\{0,1\}h:\\mathcal\{X\}\\to\\\{0,1\\\}\. A*concept class*is a subsetℋ⊂\{0,1\}𝒳\\mathcal\{H\}\\subset\\\{0,1\\\}^\{\\mathcal\{X\}\}\.

A*Littlestone tree*of depth00is a single vertex\. A Littlestone tree of depthd∈ℕ\+d\\in\\mathbb\{N\}\_\{\+\}is a perfect binary tree given as a function𝒙:\{0,1\}<d→𝒳\\boldsymbol\{x\}:\\\{0,1\\\}^\{<d\}\\to\\mathcal\{X\}\. A strings∈\{0,1\}<ds\\in\\\{0,1\\\}^\{<d\}indicates a path in the tree starting from the root, where00indicates a left edge and11indicates a right edge\.𝒙⁡\(s\)∈𝒳\\boldsymbol\{x\}\(s\)\\in\\mathcal\{X\}is the instance labeling the vertex the pathssleads to\. A pathb∈\{0,1\}db\\in\\\{0,1\\\}^\{d\}of lengthddis called a*branch*\.

A concepthhrealizes a branchb∈\{0,1\}db\\in\\\{0,1\\\}^\{d\}of𝒙\\boldsymbol\{x\}ifh⁡\(𝒙⁡\(b<t\)\)=bth\(\\boldsymbol\{x\}\(b\_\{<t\}\)\)=b\_\{t\}for allt∈\{0,…,d−1\}t\\in\\\{0,\\ldots,d\-1\\\}\. Intuitively, this means that the concepthhagrees with𝒙\\boldsymbol\{x\}on the sequence of labeled examples\(𝒙⁡\(b<1\),b1\),…,\(𝒙⁡\(b<d\),bd\)\(\\boldsymbol\{x\}\(b\_\{<1\}\),b\_\{1\}\),\\ldots,\(\\boldsymbol\{x\}\(b\_\{<d\}\),b\_\{d\}\)naturally induced by the pathbbin the tree𝒙\\boldsymbol\{x\}\. The tree𝒙\\boldsymbol\{x\}is*shattered*byℋ\\mathcal\{H\}if every branch in𝒙\\boldsymbol\{x\}has a concept fromℋ\\mathcal\{H\}realizing it\. The*Littlestone dimension*of a non\-empty classℋ\\mathcal\{H\}, denoted by𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\)is the maximald∈𝖭d\\in\\mathsf\{N\}such that there exists a Littlestone tree of depthddwhich is shattered byℋ\\mathcal\{H\}\. If there is no such maximaldd, then𝙻⁡\(ℋ\)=∞\\mathtt\{L\}\(\\mathcal\{H\}\)=\\infty\. For an empty classℋ=∅\\mathcal\{H\}=\\emptyset, we define𝙻⁡\(ℋ\)=−1\\mathtt\{L\}\(\\mathcal\{H\}\)=\-1\.

### 3\.2Online learning

#### 3\.2\.1Improper learning

Realizable \(improper\) online learning is a game that proceeds forT∈ℕ\+T\\in\\mathbb\{N\}\_\{\+\}rounds between a learner𝖫𝗋𝗇\\mathsf\{Lrn\}and an adversary𝖠𝖽𝗏\\mathsf\{Adv\}, as follows\. Before the game begins, a concept classℋ\\mathcal\{H\}is revealed to both players\.𝖠𝖽𝗏\\mathsf\{Adv\}then secretly chooses an*input sequence*SSofTTmany*examples*S:=\(x1,y1\),…,\(xT,yT\)S:=\(x\_\{1\},y\_\{1\}\),\\ldots,\(x\_\{T\},y\_\{T\}\)that is realizable byℋ\\mathcal\{H\}\. That is, there must existh∈ℋh\\in\\mathcal\{H\}such thath⁡\(xt\)=yth\(x\_\{t\}\)=y\_\{t\}for allt∈\[T\]t\\in\[T\]\. Then, the game begins, and in every roundtt:

1. 1\.𝖫𝗋𝗇\\mathsf\{Lrn\}chooses a classifierft∈\{0,1\}𝒳f\_\{t\}\\in\\\{0,1\\\}^\{\\mathcal\{X\}\}\.
2. 2\.The example\(xt,yt\)\(x\_\{t\},y\_\{t\}\)is revealed to𝖫𝗋𝗇\\mathsf\{Lrn\}, and𝖫𝗋𝗇\\mathsf\{Lrn\}suffers the*loss*1\[ft\(xt\)≠yt\]1\[f\_\{t\}\(x\_\{t\}\)\\neq y\_\{t\}\]\.

The goal of𝖫𝗋𝗇\\mathsf\{Lrn\}is to minimize its total loss, and𝖠𝖽𝗏\\mathsf\{Adv\}’s goal is to maximize it\. Consequently, we are interested in the minimax optimal loss bound, denoted as𝙼⁡\(ℋ,T\)\\mathtt\{M\}\(\\mathcal\{H\},T\), obtained when both players play optimally\. Formally,𝖫𝗋𝗇\\mathsf\{Lrn\}is a function𝖫𝗋𝗇:\(𝒳×\{0,1\}\)⋆→\{0,1\}𝒳\\mathsf\{Lrn\}:\(\\mathcal\{X\}\\times\\\{0,1\\\}\)^\{\\star\}\\to\\\{0,1\\\}^\{\\mathcal\{X\}\}, where its input in roundttis the sequence oft−1t\-1labeled examples observed so far\. Let𝒮T​\(ℋ\)\\mathcal\{S\}\_\{T\}\(\\mathcal\{H\}\)be the set of all input sequences of lengthTTthat are realized byℋ\\mathcal\{H\}\. Denote the total loss bound of a learner𝖫𝗋𝗇\\mathsf\{Lrn\}on the input sequenceSSby𝙼⁡\(𝖫𝗋𝗇,S\)\\mathtt\{M\}\(\\mathsf\{Lrn\},S\)\. Then

𝙼⁡\(ℋ,T\):=inf𝖫𝗋𝗇supS∈𝒮T​\(ℋ\)𝙼⁡\(𝖫𝗋𝗇,S\)\.\\mathtt\{M\}\(\\mathcal\{H\},T\):=\\inf\_\{\\mathsf\{Lrn\}\}\\sup\_\{S\\in\\mathcal\{S\}\_\{T\}\(\\mathcal\{H\}\)\}\\mathtt\{M\}\(\\mathsf\{Lrn\},S\)\.
The value of𝙼⁡\(ℋ,T\)\\mathtt\{M\}\(\\mathcal\{H\},T\)is well understood already in the work\[[14](https://arxiv.org/html/2609.21445#bib.bib3)\]\.

###### Theorem 3\.1\(\[[14](https://arxiv.org/html/2609.21445#bib.bib3)\]\)\.

For any classℋ\\mathcal\{H\}and time horizonT≥1T\\geq 1, it holds that

𝙼⁡\(ℋ,T\)=min⁡\{T,𝙻⁡\(ℋ\)\}\.\\mathtt\{M\}\(\\mathcal\{H\},T\)=\\min\\\{T,\\mathtt\{L\}\(\\mathcal\{H\}\)\\\}\.

Furthermore, the optimal learner chooses the classifierftf\_\{t\}of roundttas follows\. Letℋ\(t\)⊂ℋ\\mathcal\{H\}^\{\(t\)\}\\subset\\mathcal\{H\}be the subset of concepts realizing the examples\(x1,y1\),…,\(xt−1,yt−1\)\(x\_\{1\},y\_\{1\}\),\\ldots,\(x\_\{t\-1\},y\_\{t\-1\}\)\. Then for everyx∈𝒳x\\in\\mathcal\{X\}, let

ft​\(x\):=arg​maxr∈\{0,1\}⁡𝙻​\(ℋx→r\(t\)\),f\_\{t\}\(x\):=\\argmax\_\{r\\in\\\{0,1\\\}\}\\mathtt\{L\}\(\\mathcal\{H\}^\{\(t\)\}\_\{x\\to r\}\),whereℋx→r\(t\)\\mathcal\{H\}^\{\(t\)\}\_\{x\\to r\}consists of the functions inℋ\(t\)\\mathcal\{H\}^\{\(t\)\}who classifyxxtorr:

ℋx→r:=\{h∈ℋ:h⁡\(x\)=r\}\.\\mathcal\{H\}\_\{x\\to r\}:=\\\{h\\in\\mathcal\{H\}:h\(x\)=r\\\}\.

#### 3\.2\.2Proper learning

In contrast with the setting described above, in this paper we study the problem of*proper*online learning\. Ideally, proper learning just means one modification to the model: instead of allowing the learner to choose anyft∈\{0,1\}𝒳f\_\{t\}\\in\\\{0,1\\\}^\{\\mathcal\{X\}\}, it must chooseht∈ℋh\_\{t\}\\in\\mathcal\{H\}\. However, there are easy lower bounds showing that for some classesℋ\\mathcal\{H\}having𝙻⁡\(ℋ\)<∞\\mathtt\{L\}\(\\mathcal\{H\}\)<\\inftyand even𝙻⁡\(ℋ\)=1\\mathtt\{L\}\(\\mathcal\{H\}\)=1, the loss bound in this ideal proper learning model can be as high asTT\(see\[[11](https://arxiv.org/html/2609.21445#bib.bib5)\]for example\)\.

Therefore, it is standard in the proper learning setting to allow the algorithm to chooseht∈ℋh\_\{t\}\\in\\mathcal\{H\}at random,222A similar standard assumption is traditionally made also in agnostic online learning, and from the same reason\. See for example\[[17](https://arxiv.org/html/2609.21445#bib.bib7)\]\.and the suffered loss is the mistake probability\. Formally, the adversary \(secretly\) chooses\(x1,y1\),…,\(xT,yT\)\(x\_\{1\},y\_\{1\}\),\\dots,\(x\_\{T\},y\_\{T\}\), and then in every roundttof the game:

1. 1\.𝖫𝗋𝗇\\mathsf\{Lrn\}chooses a distributionPt∈Δ⁡\(ℋ\)P\_\{t\}\\in\\Delta\(\\mathcal\{H\}\)\.
2. 2\.The example\(xt,yt\)\(x\_\{t\},y\_\{t\}\)is revealed to𝖫𝗋𝗇\\mathsf\{Lrn\}, and𝖫𝗋𝗇\\mathsf\{Lrn\}suffers the*loss* Prht∼Pt1\[ht\(xt\)≠yt\]\.\\Pr\_\{h\_\{t\}\\sim P\_\{t\}\}1\[h\_\{t\}\(x\_\{t\}\)\\neq y\_\{t\}\]\.

In the proper learning setting, the learner𝖫𝗋𝗇\\mathsf\{Lrn\}is a function𝖫𝗋𝗇:\(𝒳×\{0,1\}\)⋆→Δ⁡\(ℋ\)\\mathsf\{Lrn\}:\(\\mathcal\{X\}\\times\\\{0,1\\\}\)^\{\\star\}\\to\\Delta\(\\mathcal\{H\}\), where its input in roundttis the sequence oft−1t\-1labeled examples observed so far\. The notationΔ⁡\(⋅\)\\Delta\(\\cdot\)refers to the set of all finite support distributions over some set\. We consider only finite support distributions since this suffices for our algorithm, and avoids measure theory formalism\.

For a classℋ\\mathcal\{H\}and a time horizonTT, we denote the minimax optimal total loss by𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\), which is defined as𝙼⁡\(ℋ,T\)\\mathtt\{M\}\(\\mathcal\{H\},T\), with the exception that the infimum is taken over proper randomized learners\. We are interested in bounding𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)in terms of𝙻⁡\(ℋ\)\\mathtt\{L\}\(\\mathcal\{H\}\)andTT\.

## 4The upper bound

###### Theorem 4\.1\.

For any classℋ\\mathcal\{H\}with𝙻⁡\(ℋ\)≥1\\mathtt\{L\}\(\\mathcal\{H\}\)\\geq 1and anyT≥2T\\geq 2, we have

𝙼𝗉𝗋𝗈𝗉​\(ℋ,T\)=O⁡\(𝙻⁡\(ℋ\)​log⁡T\)\.\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\},T\)=O\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log T\)\.

### 4\.1Preliminaries for the proof

We will use the following version of the minimax theorem for infinite Littlestone games of\[[11](https://arxiv.org/html/2609.21445#bib.bib5)\], which is a special case of their Corollary 7\.

###### Theorem 4\.2\(\[[11](https://arxiv.org/html/2609.21445#bib.bib5)\]\)\.

Letℋ⊂\{0,1\}𝒳\\mathcal\{H\}\\subset\\\{0,1\\\}^\{\\mathcal\{X\}\}be a class with𝙻⁡\(ℋ\)<∞\\mathtt\{L\}\(\\mathcal\{H\}\)<\\infty\. Then

infP∈Δ⁡\(ℋ\)supx∈𝒳Prh∼P\[h\(x\)=1\]=supQ∈Δ⁡\(𝒳\)infh∈ℋPrx∼Q\[h\(x\)=1\]\.\\inf\_\{P\\in\\Delta\(\\mathcal\{H\}\)\}\\sup\_\{x\\in\\mathcal\{X\}\}\\Pr\_\{h\\sim P\}\[h\(x\)=1\]=\\sup\_\{Q\\in\\Delta\(\\mathcal\{X\}\)\}\\inf\_\{h\\in\\mathcal\{H\}\}\\Pr\_\{x\\sim Q\}\[h\(x\)=1\]\.

The second tool we will use is the classic*Hedge*framework and algorithm of\[[9](https://arxiv.org/html/2609.21445#bib.bib1)\]\. The hedge framework is defined as follows\. The following game is played between𝖫𝗋𝗇\\mathsf\{Lrn\}and𝖠𝖽𝗏\\mathsf\{Adv\}forTTmany rounds in the presence ofNNmany experts, where each expertiiis referred to asii\. In each roundtt,𝖫𝗋𝗇\\mathsf\{Lrn\}chooses a distributionPt∈Δ⁡\(\[N\]\)P\_\{t\}\\in\\Delta\(\[N\]\)over the experts\. Then, the lossesℓt,i∈\[0,1\]\\ell\_\{t,i\}\\in\[0,1\]of all expertsi∈\[N\]i\\in\[N\]are revealed, and𝖫𝗋𝗇\\mathsf\{Lrn\}suffers the loss

𝔼i∼Pt​\[ℓt,i\]=∑i∈\[N\]Pt​\(i\)​ℓt,i\.\\mathbb\{E\}\_\{i\\sim P\_\{t\}\}\[\\ell\_\{t,i\}\]=\\sum\_\{i\\in\[N\]\}P\_\{t\}\(i\)\\ell\_\{t,i\}\.The learner’s goal is to minimize the total loss suffered in the game\. There is no limitation on how the losses are generated\. The work of\[[9](https://arxiv.org/html/2609.21445#bib.bib1)\]proved the following guarantee\.

###### Theorem 4\.3\(\[[9](https://arxiv.org/html/2609.21445#bib.bib1)\]\)\.

Consider the Hedge framework, with the additional guarantee that there existsK∈ℝK\\in\\mathbb\{R\}and an experti⋆∈\[N\]i^\{\\star\}\\in\[N\]such that

∑t∈\[T\]ℓt,i⋆≤K\.\\sum\_\{t\\in\[T\]\}\\ell\_\{t,i^\{\\star\}\}\\leq K\.Then, there exists an algorithm \(coined as𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}\) with total loss

∑t∈\[T\]∑i∈\[N\]Pt​\(i\)​ℓt,i=O⁡\(log⁡N\+K\)\.\\sum\_\{t\\in\[T\]\}\\sum\_\{i\\in\[N\]\}P\_\{t\}\(i\)\\ell\_\{t,i\}=O\(\\log N\+K\)\.

We will also rely on the classicϵ\\epsilon\-net theorem\. Below, to avoid measure theory formalism, we consider only finite\-support distributions\.

###### Definition 4\.4\(ϵ\\epsilon\-net\)\.

Letℋ⊂\{0,1\}𝒳\\mathcal\{H\}\\subset\\\{0,1\\\}^\{\\mathcal\{X\}\}be a class, and letQQbe some finite\-support probability distribution defined over𝒳\\mathcal\{X\}\. A subsetN⊂𝒳N\\subset\\mathcal\{X\}is anϵ\\epsilon\-net forℋ,Q\\mathcal\{H\},Qif for anyh∈ℋh\\in\\mathcal\{H\}it holds that

Prx∼Q\[h\(x\)=1\]≥ϵ⟹∃x∈N:h\(x\)=1\.\\Pr\_\{x\\sim Q\}\[h\(x\)=1\]\\geq\\epsilon\\implies\\exists x\\in N:h\(x\)=1\.

###### Theorem 4\.5\(\[[13](https://arxiv.org/html/2609.21445#bib.bib13)\]\)\.

Letℋ⊂\{0,1\}𝒳\\mathcal\{H\}\\subset\\\{0,1\\\}^\{\\mathcal\{X\}\}be a class with0<𝙻⁡\(ℋ\)<∞0<\\mathtt\{L\}\(\\mathcal\{H\}\)<\\infty\. For any finite\-support probability distributionQQdefined over𝒳\\mathcal\{X\}, and for anyϵ\>0\\epsilon\>0there exists anϵ\\epsilon\-net forℋ,Q\\mathcal\{H\},Qof sizeO⁡\(𝙻⁡\(ℋ\)ϵ​log⁡\(𝙻⁡\(ℋ\)ϵ\)\)O\\left\(\\frac\{\\mathtt\{L\}\(\\mathcal\{H\}\)\}\{\\epsilon\}\\log\\left\(\\frac\{\\mathtt\{L\}\(\\mathcal\{H\}\)\}\{\\epsilon\}\\right\)\\right\)\.

Theorem[4\.5](https://arxiv.org/html/2609.21445#S4.Thmtheorem5)was originally stated with the VC\-dimension instead of the Littlestone dimension, as stated above\. However, since the Littlestone dimension upper bounds the VC\-dimension, the above formulation of the theorem is correct as well\.

### 4\.2Proof of the upper bound

Fix the classℋ\\mathcal\{H\}and the horizonT∈ℕT\\in\\mathbb\{N\}, and denote𝙻⁡\(ℋ\):=d<∞\\mathtt\{L\}\(\\mathcal\{H\}\):=d<\\infty\. Throughout the proof, we may assume thatT=Ω⁡\(d\)T=\\Omega\(d\)\. In the complementing case, the upper bound is trivial\. The assumption thatTTis given and fixed in advance can be removed via a standard exponential doubling trick \(see\[[1](https://arxiv.org/html/2609.21445#bib.bib19), Section 4\.1\]for example\)\.

The proof constructs a small set of experts which are proper learning algorithms forℋ\\mathcal\{H\}with horizonTT, such that the assigned loss for each expert in roundttis an upper bound on its algorithm’s loss on the example\(xt,yt\)\(x\_\{t\},y\_\{t\}\), and such that the total loss of at least one expert is small\. Then, the𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}algorithm is being executed over this set of experts\. This is done by the𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}algorithm described in Figure[1](https://arxiv.org/html/2609.21445#S4.F1)\.

We now present some notation and the algorithm𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}\. LetV⊂ℋV\\subset\\mathcal\{H\}\. Define the functionyV:𝒳→\{0,1\}y\_\{V\}:\\mathcal\{X\}\\to\\\{0,1\\\}as

yV​\(x\):=arg​maxr∈\{0,1\}⁡𝙻​\(Vx→r\)y\_\{V\}\(x\):=\\argmax\_\{r\\in\\\{0,1\\\}\}\\mathtt\{L\}\(V\_\{x\\to r\}\)for allx∈𝒳x\\in\\mathcal\{X\}\.

Algorithm𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}is instanced by a setℰ\\mathcal\{E\}of experts\. Each expert is a function of a version spaceV⊂ℋV\\subset\\mathcal\{H\}associated with it\. The version space associated withe∈ℰe\\in\\mathcal\{E\}is denoted byV⁡\(e\)V\(e\)\. For algorithmic reasons, each expert is also associated with a leaf in a tree𝐓\\mathbf\{T\}maintained throughout the execution of𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}\. The leaf associated withe∈ℰe\\in\\mathcal\{E\}is denoted byℓ⁡\(e\)\\ell\(e\)\. Each leafℓ\\ellin the tree is associated with a version space denoted byV⁡\(ℓ\)V\(\\ell\)\. For every expertee, we always haveV⁡\(e\)=V⁡\(ℓ⁡\(e\)\)V\(e\)=V\(\\ell\(e\)\)\. That is, an expert is associated with the version space associated with its leaf\. We stress that there could be multiple experts associated with the same leaf\. In fact, at first𝐓\\mathbf\{T\}contains only a single node, which is the rootrr\. We initializeV⁡\(r\)=ℋV\(r\)=\\mathcal\{H\}, andℓ⁡\(e\)=r\\ell\(e\)=rfor alle∈ℰe\\in\\mathcal\{E\}\. Letℰ⁡\(ℓ\)\\mathcal\{E\}\(\\ell\)be the set of experts associated with the leafℓ\\ell\.

In each roundtt, each expert presents a distributionPt,eP\_\{t,e\}overℋ\\mathcal\{H\}\(which is supported overV⁡\(e\)V\(e\)\)\. Algorithm𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}predicts with a distributionPtP\_\{t\}overℋ\\mathcal\{H\}, which is a mixture of\{Pt,e\}e∈E\\\{P\_\{t,e\}\\\}\_\{e\\in E\}, where the weight of every expert in the mixture is given by the weights produced by𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}\.

𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}Initialize:Let the set of expertsℰ\\mathcal\{E\}be of sizeT3​dT^\{3d\}, and set the initial weights of the experts as in𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}\. Initialize a tree𝐓\\mathbf\{T\}with only a rootrr\. SetV⁡\(r\):=ℋV\(r\):=\\mathcal\{H\}, and setℓ⁡\(e\)=r\\ell\(e\)=rfor alle∈ℰe\\in\\mathcal\{E\},
fort=1,…,Tt=1,\\ldots,T:1\.While there is a leafℓ∈𝐓\\ell\\in\\mathbf\{T\}such thatPt,eP\_\{t,e\}is not yet defined fore∈ℰ⁡\(ℓ\)e\\in\\mathcal\{E\}\(\\ell\):\(a\)IfV⁡\(ℓ\)=∅V\(\\ell\)=\\emptyset, setPt,eP\_\{t,e\}to be an arbitrary distribution overℋ\\mathcal\{H\}for alle∈ℰ⁡\(ℓ\)e\\in\\mathcal\{E\}\(\\ell\)\.\(b\)Else, if there is a finite support distributionPPoverV⁡\(ℓ\)V\(\\ell\)such that∀x∈𝒳:Prh∼P\[h\(x\)≠yV⁡\(ℓ\)\(x\)\]≤2/T,\\forall x\\in\\mathcal\{X\}:\\Pr\_\{h\\sim P\}\[h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\)\]\\leq 2/T,setPt,e:=PP\_\{t,e\}:=Pfor alle∈ℰ⁡\(ℓ\)e\\in\\mathcal\{E\}\(\\ell\)\.\(c\)Else, if there is no such distribution, execute𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)\.2\.Define a distributionPtP\_\{t\}overℋ\\mathcal\{H\}which is given by the distribution over the experts according to their weights as in𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}\. The prediction of an experteeis given byPt,eP\_\{t,e\}\.3\.Receive current example\(xt,yt\)\(x\_\{t\},y\_\{t\}\)\.4\.For every leafℓ∈𝐓\\ell\\in\\mathbf\{T\}:\(a\)IfV⁡\(ℓ\)=∅V\(\\ell\)=\\emptyset, setℓt,e:=1\\ell\_\{t,e\}:=1for alle∈ℰ⁡\(ℓ\)e\\in\\mathcal\{E\}\(\\ell\)\.\(b\)Else, ifyt=yV⁡\(ℓ\)​\(xt\)y\_\{t\}=y\_\{V\(\\ell\)\}\(x\_\{t\}\): setℓt,e:=2/T\\ell\_\{t,e\}:=2/Tfor alle∈ℰ⁡\(ℓ\)e\\in\\mathcal\{E\}\(\\ell\)\.\(c\)Else, ifyt≠yV⁡\(ℓ\)​\(xt\)y\_\{t\}\\neq y\_\{V\(\\ell\)\}\(x\_\{t\}\): setℓt,e:=1\\ell\_\{t,e\}:=1for alle∈ℰ⁡\(ℓ\)e\\in\\mathcal\{E\}\(\\ell\)\.\(d\)UpdateV⁡\(ℓ\)V\(\\ell\)toV⁡\(ℓ\):=\{h∈V⁡\(ℓ\):h⁡\(xt\)=yt\}V\(\\ell\):=\\\{h\\in V\(\\ell\):h\(x\_\{t\}\)=y\_\{t\}\\\}\.5\.Update experts’ weights as in𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}\.Figure 1:Main algorithm𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿\\mathsf\{SplitLeaf\}Input:A leafℓ∈𝐓\\ell\\in\\mathbf\{T\}\.
1\.Find a subsetN⊂𝒳N\\subset\\mathcal\{X\}of sizeT3T^\{3\}such that for anyh∈V⁡\(ℓ\)h\\in V\(\\ell\)it holds that there existsx∈Nx\\in Nfor whichh​\(x\)≠yV⁡\(ℓ\)​\(x\)h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\)\. If suchNNdoes not exist, return an error\.2\.Splitℰ⁡\(ℓ\)\\mathcal\{E\}\(\\ell\)toT3T^\{3\}disjoint subsets of equal sizes, each associated with a distinctx∈Nx\\in N\. If\|ℰ⁡\(ℓ\)\|≠T3​k\|\\mathcal\{E\}\(\\ell\)\|\\neq T^\{3k\}for somek∈ℕ\+k\\in\\mathbb\{N\_\{\+\}\}, return an error\. Denote the subset ofℰ⁡\(ℓ\)\\mathcal\{E\}\(\\ell\)associated withxxbyℰx​\(ℓ\)\\mathcal\{E\}\_\{x\}\(\\ell\)\.3\.Turnℓ\\ellto an internal vertex by attaching toℓ\\ellT3T^\{3\}many leaves, each associated with a distinctx∈Nx\\in N\. Denote the new leaf associated withxxbyℓx\\ell\_\{x\}\.4\.For anyx∈Nx\\in Nupdateℰ⁡\(ℓx\):=ℰx​\(ℓ\)\\mathcal\{E\}\(\\ell\_\{x\}\):=\\mathcal\{E\}\_\{x\}\(\\ell\), andV⁡\(ℓx\):=Vx​\(ℓ\)V\(\\ell\_\{x\}\):=V\_\{x\}\(\\ell\), where:Vx​\(ℓ\):=\{h∈V⁡\(ℓ\):h⁡\(x\)≠yV⁡\(ℓ\)​\(x\)\}\.V\_\{x\}\(\\ell\):=\\\{h\\in V\(\\ell\):h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\)\\\}\.Figure 2:Leaf splitting algorithmWe now prove that𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}indeed has a total loss bound ofO⁡\(d​log⁡T\)O\(d\\log T\), by a series of arguments\.

###### Lemma 4\.6\.

At all times, for everyh∈ℋh\\in\\mathcal\{H\}which is consistent with the input, there existsℓ∈𝐓\\ell\\in\\mathbf\{T\}such thath∈V⁡\(ℓ\)h\\in V\(\\ell\)\.

###### Proof\.

Since we initializeV⁡\(r\)=ℋV\(r\)=\\mathcal\{H\}, it is not difficult to see that it suffices to show that for anyℓ∈𝐓\\ell\\in\\mathbf\{T\}, ifNNis the subset used in𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)to splitℓ\\ell, then

V⁡\(ℓ\)⊂⋃x∈NVx​\(ℓ\)\.V\(\\ell\)\\subset\\bigcup\_\{x\\in N\}V\_\{x\}\(\\ell\)\.Leth∈V⁡\(ℓ\)h\\in V\(\\ell\)\. By definition ofNN, there existsx∈Nx\\in Nsuch thath​\(x\)≠yV⁡\(ℓ\)​\(x\)h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\), that is, such thath∈Vx​\(ℓ\)h\\in V\_\{x\}\(\\ell\)\. ∎

###### Lemma 4\.7\.

For anyℓ\\ellfor which𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿\\mathsf\{SplitLeaf\}is executed for, the setNNdefined in𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)exists\. That is, Item[1](https://arxiv.org/html/2609.21445#S4.I2.i1)of𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿\\mathsf\{SplitLeaf\}never returns an error\.

###### Proof\.

We assume for simplicity that\|𝒳\|≥T3\|\\mathcal\{X\}\|\\geq T^\{3\}\(otherwise the subsetNNcan be a multiset, which does not hurt the algorithm\)\. Since𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)is executed, it is implied thatV⁡\(ℓ\)V\(\\ell\)is non\-empty and that there is no finite support distributionPPoverV⁡\(ℓ\)V\(\\ell\)such that

∀x∈𝒳:Prh∼P\[h\(x\)≠yV⁡\(ℓ\)\(x\)\]≤2/T,\\forall x\\in\\mathcal\{X\}:\\Pr\_\{h\\sim P\}\[h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\)\]\\leq 2/T,That is, for any finite support distributionPPoverV⁡\(ℓ\)V\(\\ell\)there existsx∈𝒳x\\in\\mathcal\{X\}for which

Prh∼P\[h\(x\)≠yV⁡\(ℓ\)\(x\)\]\>2/T\.\\Pr\_\{h\\sim P\}\[h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\)\]\>2/T\.For anyh∈ℋh\\in\\mathcal\{H\}, define the functionbhb\_\{h\}for allx∈𝒳x\\in\\mathcal\{X\}as

bh\(x\):=1\[h\(x\)≠yV⁡\(ℓ\)\(x\)\],b\_\{h\}\(x\):=1\[h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\)\],and so we can write that for any finite support distributionPPoverV⁡\(ℓ\)V\(\\ell\)there existsx∈𝒳x\\in\\mathcal\{X\}for which

Prh∼P\[bh\(x\)=1\]\>2/T\.\\Pr\_\{h\\sim P\}\[b\_\{h\}\(x\)=1\]\>2/T\.\(1\)Furthermore, the classBV⁡\(ℓ\):=\{bh:h∈V⁡\(ℓ\)\}B\_\{V\(\\ell\)\}:=\\\{b\_\{h\}:h\\in V\(\\ell\)\\\}satisfies𝙻⁡\(BV⁡\(ℓ\)\)=𝙻⁡\(V⁡\(ℓ\)\)\\mathtt\{L\}\(B\_\{V\(\\ell\)\}\)=\\mathtt\{L\}\(V\(\\ell\)\)\. Indeed, note that for anyx∈𝒳,h∈V⁡\(ℓ\)x\\in\\mathcal\{X\},h\\in V\(\\ell\)we havebh​\(x\)=h⁡\(x\)⊕yV⁡\(ℓ\)​\(x\)b\_\{h\}\(x\)=h\(x\)\\oplus y\_\{V\(\\ell\)\}\(x\)\. That is, forxxwithyV⁡\(ℓ\)​\(x\)=1y\_\{V\(\\ell\)\}\(x\)=1we havebh​\(x\)=1−h⁡\(x\)b\_\{h\}\(x\)=1\-h\(x\), and forxxwithyV⁡\(ℓ\)​\(x\)=0y\_\{V\(\\ell\)\}\(x\)=0we havebh​\(x\)=h​\(x\)b\_\{h\}\(x\)=h\(x\)\. Thus, any Littlestone tree forV⁡\(ℓ\)V\(\\ell\)can serve as a Littlestone tree forBV⁡\(ℓ\)B\_\{V\(\\ell\)\}by switching the labels on the left and right outgoing edges of every node labeled withx∈𝒳x\\in\\mathcal\{X\}for whichyV⁡\(ℓ\)​\(x\)=1y\_\{V\(\\ell\)\}\(x\)=1\. Therefore, the minimax Theorem[4\.2](https://arxiv.org/html/2609.21445#S4.Thmtheorem2)holds forBV⁡\(ℓ\)B\_\{V\(\\ell\)\}, and thus \([1](https://arxiv.org/html/2609.21445#S4.E1)\) implies that there exists a finite support distributionQQover𝒳\\mathcal\{X\}such that for anybh∈BV⁡\(ℓ\)b\_\{h\}\\in B\_\{V\(\\ell\)\}we have

Prx∼Q\[bh\(x\)=1\]\>1/T\.\\Pr\_\{x\\sim Q\}\[b\_\{h\}\(x\)=1\]\>1/T\.\(2\)Now, Theorem[4\.5](https://arxiv.org/html/2609.21445#S4.Thmtheorem5)implies that there exists a\(1/T\)\(1/T\)\-netNNforBV⁡\(ℓ\),QB\_\{V\(\\ell\)\},Qof sizeT3T^\{3\}\. Together with \([2](https://arxiv.org/html/2609.21445#S4.E2)\), this implies that for anybh∈BV⁡\(ℓ\)b\_\{h\}\\in B\_\{V\(\\ell\)\}there existsx∈Nx\\in Nsuch thatbh​\(x\)=1b\_\{h\}\(x\)=1, that is, for anyh∈V⁡\(ℓ\)h\\in V\(\\ell\)there existsx∈Nx\\in Nsuch thath​\(x\)≠yV⁡\(ℓ\)​\(x\)h\(x\)\\neq y\_\{V\(\\ell\)\}\(x\), as required\. ∎

###### Lemma 4\.8\.

Letℓ∈𝐓\\ell\\in\\mathbf\{T\}, and letNNas defined in𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)\. Then for everyx∈Nx\\in Nwe have

𝙻⁡\(Vx​\(ℓ\)\)<𝙻⁡\(V⁡\(ℓ\)\)\.\\mathtt\{L\}\(V\_\{x\}\(\\ell\)\)<\\mathtt\{L\}\(V\(\\ell\)\)\.

###### Proof\.

Suppose that for somex∈Nx\\in Nwe have𝙻⁡\(Vx​\(ℓ\)\)≥𝙻⁡\(V⁡\(ℓ\)\)\\mathtt\{L\}\(V\_\{x\}\(\\ell\)\)\\geq\\mathtt\{L\}\(V\(\\ell\)\)\. Then we can construct a Littlestone tree of depth𝙻⁡\(V⁡\(ℓ\)\)\+1\\mathtt\{L\}\(V\(\\ell\)\)\+1which is shattered byV⁡\(ℓ\)V\(\\ell\)\(which is of course a contradiction\), as follows: Let the root be labeled withxx\. By assumption and by definition ofVx​\(ℓ\)V\_\{x\}\(\\ell\), we have

𝙻⁡\(V​\(ℓ\)x→yV⁡\(ℓ\)​\(x\)\)≥𝙻⁡\(V​\(ℓ\)x→1−yV⁡\(ℓ\)​\(x\)\)=𝙻⁡\(Vx​\(ℓ\)\)≥𝙻⁡\(V⁡\(ℓ\)\),\\mathtt\{L\}\(V\(\\ell\)\_\{x\\to y\_\{V\(\\ell\)\}\(x\)\}\)\\geq\\mathtt\{L\}\(V\(\\ell\)\_\{x\\to 1\-y\_\{V\(\\ell\)\}\(x\)\}\)=\\mathtt\{L\}\(V\_\{x\}\(\\ell\)\)\\geq\\mathtt\{L\}\(V\(\\ell\)\),which concludes the proof\. Therefore,𝙻⁡\(Vx​\(ℓ\)\)<𝙻⁡\(V⁡\(ℓ\)\)\\mathtt\{L\}\(V\_\{x\}\(\\ell\)\)<\\mathtt\{L\}\(V\(\\ell\)\)for allx∈Nx\\in N\. ∎

###### Lemma 4\.9\.

Whenever𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)is executed, there existsk∈ℕ\+k\\in\\mathbb\{N\}\_\{\+\}, such that\|ℰ⁡\(ℓ\)\|=T3​k\|\\mathcal\{E\}\(\\ell\)\|=T^\{3k\}\. That is, Item[2](https://arxiv.org/html/2609.21445#S4.I2.i2)of𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿\\mathsf\{SplitLeaf\}does not return an error\.

###### Proof\.

We first have only the rootrr, and thus\|ℰ⁡\(r\)\|=T3​d\|\\mathcal\{E\}\(r\)\|=T^\{3d\}\. Each execution of𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)splitsℰ⁡\(ℓ\)\\mathcal\{E\}\(\\ell\)toT3T^\{3\}disjoint subsets\. Thus, it suffices to show that if\|ℰ⁡\(ℓ\)\|=1\|\\mathcal\{E\}\(\\ell\)\|=1, then𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿\\mathsf\{SplitLeaf\}will not be called withℓ\\ell\.

In other words, it suffices to show that𝐓\\mathbf\{T\}never reaches depthd\+1d\+1, in any of its branches\. Indeed, Lemma[4\.8](https://arxiv.org/html/2609.21445#S4.Thmtheorem8)establishes that for anyℓx\\ell\_\{x\}attached toℓ\\ellwhen𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)is called, we have𝙻⁡\(V⁡\(ℓx\)\)<𝙻⁡\(V⁡\(ℓ\)\)\\mathtt\{L\}\(V\(\\ell\_\{x\}\)\)<\\mathtt\{L\}\(V\(\\ell\)\)\. Therefore, if for someℓ∈𝐓\\ell\\in\\mathbf\{T\}we have\|ℰ⁡\(ℓ\)\|=1\|\\mathcal\{E\}\(\\ell\)\|=1, it is implied thatℓ\\ellis at depthdd, which due to Lemma[4\.8](https://arxiv.org/html/2609.21445#S4.Thmtheorem8)implies that𝙻⁡\(V⁡\(ℓ\)\)=0\\mathtt\{L\}\(V\(\\ell\)\)=0\. We can now observe that the condition that fires the execution of𝖲𝗉𝗅𝗂𝗍𝖫𝖾𝖺𝖿⁡\(ℓ\)\\mathsf\{SplitLeaf\}\(\\ell\)cannot be satisfied forℓ\\ellwith𝙻⁡\(V⁡\(ℓ\)\)=0\\mathtt\{L\}\(V\(\\ell\)\)=0, since𝙻⁡\(V⁡\(ℓ\)\)=0\\mathtt\{L\}\(V\(\\ell\)\)=0implies\|V⁡\(ℓ\)\|=1\|V\(\\ell\)\|=1\. ∎

###### Lemma 4\.10\.

There existse∈ℰe\\in\\mathcal\{E\}such that

∑t∈\[T\]ℓt,e≤𝙻⁡\(ℋ\)\+2\.\\sum\_\{t\\in\[T\]\}\\ell\_\{t,e\}\\leq\\mathtt\{L\}\(\\mathcal\{H\}\)\+2\.

###### Proof\.

Leth∈ℋh\\in\\mathcal\{H\}such thathhis consistent with the input sequence\. Letℓ∈𝐓\\ell\\in\\mathbf\{T\}such thath∈V⁡\(ℓ\)h\\in V\(\\ell\)in roundTT, which exists by Lemma[4\.6](https://arxiv.org/html/2609.21445#S4.Thmtheorem6)\. By Lemma[4\.9](https://arxiv.org/html/2609.21445#S4.Thmtheorem9), we also haveV⁡\(ℓ\)≠∅V\(\\ell\)\\neq\\emptyset, so lete∈ℰ⁡\(ℓ\)e\\in\\mathcal\{E\}\(\\ell\)\. In every roundtt, there are two possibilities forℓt,e\\ell\_\{t,e\}\. Ifyt=yV⁡\(e\)​\(xt\)y\_\{t\}=y\_\{V\(e\)\}\(x\_\{t\}\), thenℓt,e=2/T\\ell\_\{t,e\}=2/T\. Thus the total loss from such rounds is at most2T​T=2\\frac\{2\}\{T\}T=2\. In the other case, we haveyt≠yV⁡\(e\)​\(xt\)y\_\{t\}\\neq y\_\{V\(e\)\}\(x\_\{t\}\)and thenℓt,e=1\\ell\_\{t,e\}=1\. By definition ofyV⁡\(e\)y\_\{V\(e\)\}, the Littlestone dimension of the version space ofeewill decrease by at least11afterℓ⁡\(e\)\\ell\(e\)updates its version space to be consistent with the example\(xt,yt\)\(x\_\{t\},y\_\{t\}\)\. Therefore, this case can happen at mostddmany times, and the proof is completed\. ∎

We may now prove the following lemma that implies Theorem[4\.1](https://arxiv.org/html/2609.21445#S4.Thmtheorem1)\.

###### Lemma 4\.11\.

Algorithm𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}is a proper online learner such that for anyℋ\\mathcal\{H\}with𝙻⁡\(ℋ\)≥1\\mathtt\{L\}\(\\mathcal\{H\}\)\\geq 1and for anyT≥2T\\geq 2, we have𝙼⁡\(𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾,S\)=O⁡\(𝙻⁡\(ℋ\)​log⁡T\)\\mathtt\{M\}\(\\mathsf\{ClassHedge\},S\)=O\(\\mathtt\{L\}\(\\mathcal\{H\}\)\\log T\)for allS∈𝒮T​\(ℋ\)S\\in\\mathcal\{S\}\_\{T\}\(\\mathcal\{H\}\)\.

###### Proof\.

First,𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}is a proper learner since in every round it defines a distributionPtP\_\{t\}over proper learners, and thus proper itself\. We now prove its loss guarantee\.

Now, note that for any roundttand for anye∈ℰe\\in\\mathcal\{E\}we have

∑h∈ℋPt,e\(h\)1\[h\(xt\)≠yt\]≤ℓt,e\.\\sum\_\{h\\in\\mathcal\{H\}\}P\_\{t,e\}\(h\)1\[h\(x\_\{t\}\)\\neq y\_\{t\}\]\\leq\\ell\_\{t,e\}\.\(3\)Indeed, for the cases thatV⁡\(e\)=∅V\(e\)=\\emptysetoryt≠yV⁡\(e\)​\(xt\)y\_\{t\}\\neq y\_\{V\(e\)\}\(x\_\{t\}\)in roundttthis is trivial\. For the caseyt=yV⁡\(e\)​\(xt\)y\_\{t\}=y\_\{V\(e\)\}\(x\_\{t\}\), the definition ofPt,eP\_\{t,e\}implies thatPrh∼Pt,e\[h\(xt\)≠yt\]≤2/T=ℓt,e\\Pr\_\{h\\sim P\_\{t,e\}\}\[h\(x\_\{t\}\)\\neq y\_\{t\}\]\\leq 2/T=\\ell\_\{t,e\}\. LetEtE\_\{t\}be the distribution over experts that𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}uses in roundtt\. Now, by definition of𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}, its loss onSSis

M⁡\(𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾,S\)\\displaystyle M\(\\mathsf\{ClassHedge\},S\)=∑t∑h∈ℋPt\(h\)1\[h\(xt\)≠yt\]\\displaystyle=\\sum\_\{t\}\\sum\_\{h\\in\\mathcal\{H\}\}P\_\{t\}\(h\)1\[h\(x\_\{t\}\)\\neq y\_\{t\}\]=∑t∑e∈ℰEt\(e\)∑h∈ℋPt,e\(h\)1\[h\(xt\)≠yt\]\\displaystyle=\\sum\_\{t\}\\sum\_\{e\\in\\mathcal\{E\}\}E\_\{t\}\(e\)\\sum\_\{h\\in\\mathcal\{H\}\}P\_\{t,e\}\(h\)1\[h\(x\_\{t\}\)\\neq y\_\{t\}\]≤∑t∑e∈ℰEt​\(e\)​ℓt,e,\\displaystyle\\leq\\sum\_\{t\}\\sum\_\{e\\in\\mathcal\{E\}\}E\_\{t\}\(e\)\\ell\_\{t,e\},where the final inequality is by \([3](https://arxiv.org/html/2609.21445#S4.E3)\)\. Now,𝖢𝗅𝖺𝗌𝗌𝖧𝖾𝖽𝗀𝖾\\mathsf\{ClassHedge\}is the𝖧𝖾𝖽𝗀𝖾\\mathsf\{Hedge\}algorithm executed onT3​dT^\{3d\}experts, with the guarantee that there exists an expert with total loss at mostd\+2d\+2, due to Lemma[4\.10](https://arxiv.org/html/2609.21445#S4.Thmtheorem10)\. Theorem[4\.3](https://arxiv.org/html/2609.21445#S4.Thmtheorem3)implies that the quantity∑t∑e∈ℰEt​\(e\)​ℓt,e\\sum\_\{t\}\\sum\_\{e\\in\\mathcal\{E\}\}E\_\{t\}\(e\)\\ell\_\{t,e\}is bounded as

∑t∑e∈ℰEt​\(e\)​ℓt,e=O⁡\(log⁡T3​d\+d\)=O⁡\(d​log⁡T\)\.\\sum\_\{t\}\\sum\_\{e\\in\\mathcal\{E\}\}E\_\{t\}\(e\)\\ell\_\{t,e\}=O\(\\log T^\{3d\}\+d\)=O\(d\\log T\)\.This concludes the proof\. ∎

## 5The Lower bound

We prove the following lower bound\.

###### Theorem 5\.1\.

For anyd∈ℕ\+d\\in\\mathbb\{N\_\{\+\}\}, there exists a classℋd\\mathcal\{H\}\_\{d\}such that𝙻⁡\(ℋd\)=O⁡\(d\)\\mathtt\{L\}\(\\mathcal\{H\}\_\{d\}\)=O\(d\), and for anyT≥d2T\\geq d^\{2\}:

𝙼𝗉𝗋𝗈𝗉​\(ℋd,T\)=Ω⁡\(d​log⁡T\)\.\\mathtt\{M\}\_\{\\mathsf\{prop\}\}\(\\mathcal\{H\}\_\{d\},T\)=\\Omega\(d\\log T\)\.

Let us first define for everyddthe classℋd\\mathcal\{H\}\_\{d\}used in Theorem[5\.1](https://arxiv.org/html/2609.21445#S5.Thmtheorem1)\. The class is defined as a union ofdd\-hamming spheres over a block\[n\]\[n\], for all block sizen≥2​dn\\geq 2d\. The block of sizennis referred to as blocknn\. We need varying block sizes to handle all possible horizonsTTin a single class\. This is similar to the gluing technique used e\.g\. in\[[5](https://arxiv.org/html/2609.21445#bib.bib9)\]\.

Formally, for every block sizen≥2​dn\\geq 2ddefine

ℋd,n:=\{hn,S:S⊂\[n\],\|S\|=d\},\\mathcal\{H\}\_\{d,n\}:=\\\{h\_\{n,S\}:S\\subset\[n\],\|S\|=d\\\},andℋd\\mathcal\{H\}\_\{d\}is the union

ℋd:=⋃n≥2​dℋd,n\.\\mathcal\{H\}\_\{d\}:=\\bigcup\_\{n\\geq 2d\}\\mathcal\{H\}\_\{d,n\}\.The domainℋd\\mathcal\{H\}\_\{d\}is defined over is

𝒳d:=\{In:n≥2d\}∪\{xn,i:n≥2d,i∈\[n\]\}\.\\mathcal\{X\}\_\{d\}:=\\\{I\_\{n\}:n\\geq 2d\\\}\\cup\\\{x\_\{n,i\}:n\\geq 2d,i\\in\[n\]\\\}\.The role ofInI\_\{n\}is to indicate the block, and for everyn≥2​dn\\geq 2dthe instancesxn,1,…,xn,nx\_\{n,1\},\\ldots,x\_\{n,n\}form the block of sizenn\. We denote the set of instances used in blocknnas

𝒳d,n=\{In\}∪\{xn,i:i∈\[n\]\},\\mathcal\{X\}\_\{d,n\}=\\\{I\_\{n\}\\\}\\cup\\\{x\_\{n,i\}:i\\in\[n\]\\\},such that𝒳d=⋃n≥2​d𝒳d,n\\mathcal\{X\}\_\{d\}=\\bigcup\_\{n\\geq 2d\}\\mathcal\{X\}\_\{d,n\}\.

Let us formally defineℋd,n\\mathcal\{H\}\_\{d,n\}\. For alln≥2​dn\\geq 2dandS⊂\[n\]S\\subset\[n\]definehn,S\(Im\):=1\[m=n\]h\_\{n,S\}\(I\_\{m\}\):=1\[m=n\]for allm≥2​dm\\geq 2d, andhn,S\(xm,i\)=1\[m=nandi∈S\]h\_\{n,S\}\(x\_\{m,i\}\)=1\[m=n\\text\{ and \}i\\in S\]\. It is not difficult to verify the following

###### Observation 5\.2\.

We have𝙻⁡\(ℋd\)=d\+1\\mathtt\{L\}\(\\mathcal\{H\}\_\{d\}\)=d\+1\.

We may now prove the lower bound\. In the proof, it is convenient to use an adaptive adversary𝖠𝖽𝗏\\mathsf\{Adv\}that is allowed to choose the input sequence on the fly\. However, adaptive and oblivious adversaries are in fact equivalent since the distributionPtP\_\{t\}used by the learner in every roundttis a deterministic function of the input sequence up to roundt−1t\-1\.

In fact, using a somewhat more involved argument, one can prove that the same lower bound holds even if the adversary is*stochastic*, which is even weaker than an adversarial oblivious adversary\.

###### Proof of Theorem[5\.1](https://arxiv.org/html/2609.21445#S5.Thmtheorem1)\.

Fixd∈ℕ\+d\\in\\mathbb\{N\}\_\{\+\}andT≥d2T\\geq d^\{2\}\. The proof requires thatTTis larger than some universal constantC\>0C\>0\. We therefore assume thatd≥Cd\\geq\\sqrt\{C\}\. This does not invalidate the proof ford<Cd<\\sqrt\{C\}, as for such values ofddwe use the classℋd\\mathcal\{H\}\_\{d\}withd=⌈C⌉d=\\left\\lceil\\sqrt\{C\}\\right\\rceil\. We first fix the block size as

n:=Tlog⁡T,n:=\\frac\{T\}\{\\log T\},assuming for simplicity thatn∈ℕn\\in\\mathbb\{N\}\. We haven≥2​dn\\geq 2dfor sufficiently largeCC, thus a block of sizennexists\.

𝖠𝖽𝗏\\mathsf\{Adv\}uses only instances from𝒳d,n\\mathcal\{X\}\_\{d,n\}in the input sequence\. It maintains a setUt⊂\[n\]U\_\{t\}\\subset\[n\]of instances\{xn,i:i∈Ut\}\\\{x\_\{n,i\}:i\\in U\_\{t\}\\\}that were not yet labeled with00in the beginning of roundtt\. Crucially, as long as\|Ut\|\>d\|U\_\{t\}\|\>d,𝖠𝖽𝗏\\mathsf\{Adv\}is allowed to use any coordinate instancexn,ix\_\{n,i\}labeled with00as an example, while keeping the input sequence realizable\. InitiallyU1=\[n\]U\_\{1\}=\[n\]and we assume that\|Ut\|≥d\|U\_\{t\}\|\\geq dat all times\. To make this assumption hold, once\|Ut\|\|U\_\{t\}\|is exactlydd,𝖠𝖽𝗏\\mathsf\{Adv\}produces arbitrary examples that are consistent withhn,Uth\_\{n,U\_\{t\}\}, and we assume that the learner suffers no further loss\. We also denote the set of indicesiisuch that the example\(xn,i,0\)\(x\_\{n,i\},0\)already appeared in the input sequence up to roundt−1t\-1asUtc:=\[n\]\\UtU\_\{t\}^\{c\}:=\[n\]\\backslash U\_\{t\}\.

Fix the roundtt, and letPPbe the distribution used by𝖫𝗋𝗇\\mathsf\{Lrn\}in roundtt\. Letpb:=P⁡\(ℋd\\ℋd,n\)p\_\{b\}:=P\(\\mathcal\{H\}\_\{d\}\\backslash\\mathcal\{H\}\_\{d,n\}\)be the total mass ofPPoutside of the block’s functionsℋd,n\\mathcal\{H\}\_\{d,n\}\. We have two cases\. In the first case, which we call case 1, we havepb≥1/2p\_\{b\}\\geq 1/2\. In this case,𝖠𝖽𝗏\\mathsf\{Adv\}sets the example of roundttto\(In,1\)\(I\_\{n\},1\), and the learner suffers loss at least

pb≥1/2,p\_\{b\}\\geq 1/2,\(4\)without elimination of any element ofUtU\_\{t\}\. Thus, in this case we setUt\+1:=UtU\_\{t\+1\}:=U\_\{t\}\. In the complementing case, which we call case 2, the total mass of the functions inℋd,n\\mathcal\{H\}\_\{d,n\}, denoted aspg:=P⁡\(ℋd,n\)p\_\{g\}:=P\(\\mathcal\{H\}\_\{d,n\}\), is more than1/21/2\. For anyi∈\[n\]i\\in\[n\], letpip\_\{i\}be the total mass of functions giving11toxn,ix\_\{n,i\}:

pi:=P\(\{hn,S:S⊂\[n\],i∈S\}\)\.p\_\{i\}:=P\(\\\{h\_\{n,S\}:S\\subset\[n\],i\\in S\\\}\)\.By definition ofpip\_\{i\}and the assumptionpg\>1/2p\_\{g\}\>1/2we have

∑i=1npi=d​pg\>d/2\.\\sum\_\{i=1\}^\{n\}p\_\{i\}=dp\_\{g\}\>d/2\.Indeed, everyh∈ℋd,nh\\in\\mathcal\{H\}\_\{d,n\}appears in the set\{hn,S:S⊂\[n\],i∈S\}\\\{h\_\{n,S\}:S\\subset\[n\],i\\in S\\\}for preciselyddmany coordinatesii, thus∑i=1npi\\sum\_\{i=1\}^\{n\}p\_\{i\}in fact sums the total mass ofℋd,n\\mathcal\{H\}\_\{d,n\}for preciselyddmany times\.

We now handle two different cases that case 2 splits to\. In the first case, which we call case 2a, we have∑i∈Utcpi≥d/4\\sum\_\{i\\in U\_\{t\}^\{c\}\}p\_\{i\}\\geq d/4\. When this is the case,𝖠𝖽𝗏\\mathsf\{Adv\}identifiesi∈Utci\\in U\_\{t\}^\{c\}who maximizespip\_\{i\}and sets the example in roundttto\(xn,i,0\)\(x\_\{n,i\},0\)\. This example does not eliminate an element fromUtU\_\{t\}and thus we setUt\+1:=UtU\_\{t\+1\}:=U\_\{t\}\. By definition ofpip\_\{i\}the learner suffers loss at least

pi≥d4​\|Utc\|≥d4​n\.p\_\{i\}\\geq\\frac\{d\}\{4\|U\_\{t\}^\{c\}\|\}\\geq\\frac\{d\}\{4n\}\.\(5\)In the complementing case, which we call case 2b, we have∑i∈Utpi≥d/4\\sum\_\{i\\in U\_\{t\}\}p\_\{i\}\\geq d/4\.𝖠𝖽𝗏\\mathsf\{Adv\}identifiesi∈Uti\\in U\_\{t\}who maximizespip\_\{i\}and sets the example in roundttto\(xn,i,0\)\(x\_\{n,i\},0\)\. By definition ofpip\_\{i\}the learner suffers loss at least

pi≥d4​\|Ut\|\.p\_\{i\}\\geq\\frac\{d\}\{4\|U\_\{t\}\|\}\.\(6\)In this case, the indexiishould be eliminated fromUtU\_\{t\}, so we setUt\+1:=Ut\\\{i\}U\_\{t\+1\}:=U\_\{t\}\\backslash\\\{i\\\}\.

We now lower bound the total loss suffered by the learner\. We consider two cases\. In the first case, there existsT′T^\{\\prime\}such that\|UT′\|=d\|U\_\{T^\{\\prime\}\}\|=d\. This means that case 2b happened for all possible sizes ofUtU\_\{t\}:m∈\{n,…,d\+1\}m\\in\\\{n,\\ldots,d\+1\\\}\. The total loss originating only from case 2b rounds is thus at least

∑m=d\+1nd4​m≥18​d​log⁡nd=18​d​log⁡Td​log⁡T=Ω⁡\(d​log⁡T\),\\sum\_\{m=d\+1\}^\{n\}\\frac\{d\}\{4m\}\\geq\\frac\{1\}\{8\}d\\log\\frac\{n\}\{d\}=\\frac\{1\}\{8\}d\\log\\frac\{T\}\{d\\log T\}=\\Omega\(d\\log T\),due to \([6](https://arxiv.org/html/2609.21445#S5.E6)\), where the final equality holds sinced≥Cd\\geq\\sqrt\{C\}whereCCis sufficiently large\.

In the complementing case,\|UT\|\>d\|U\_\{T\}\|\>d, which means that at mostnnmany rounds were case 2b, and that at leastT−n≥T/2T\-n\\geq T/2rounds were case 1 or case 2a\. In both cases, the loss per round is at leastd4​n\\frac\{d\}\{4n\}due to \([4](https://arxiv.org/html/2609.21445#S5.E4)\), \([5](https://arxiv.org/html/2609.21445#S5.E5)\)\. Overall, this sums up to total loss of at least

T2​d4​n=T2​d​log⁡T4​T=Ω⁡\(d​log⁡T\),\\frac\{T\}\{2\}\\frac\{d\}\{4n\}=\\frac\{T\}\{2\}\\frac\{d\\log T\}\{4T\}=\\Omega\(d\\log T\),as stated\. ∎

## Acknowledgments

Idan Mehalel is supported by the European Research Council \(ERC\) under the European Union’s Horizon 2022 research and innovation program \(grant agreement No\. 101041711\), the Israel Science Foundation \(grant number 2258/19\), and the Simons Foundation \(as part of the Collaboration on the Mathematical and Scientific Foundations of Deep Learning\)\.

## References

- \[1\]P\. Auer and R\. Ortner\(2010\)UCB revisited: improved regret bounds for the stochastic multi\-armed bandit problem\.Periodica Mathematica Hungarica61\(1\-2\),pp\. 55–65\.Cited by:[§4\.2](https://arxiv.org/html/2609.21445#S4.SS2.p1.1)\.
- \[2\]S\. Ben\-David, D\. Pál, and S\. Shalev\-Shwartz\(2009\)Agnostic online learning\.InCOLT,Cited by:[§2\.1](https://arxiv.org/html/2609.21445#S2.SS1.p8.1)\.
- \[3\]O\. Bousquet, S\. Hanneke, S\. Moran, and N\. Zhivotovskiy\(2020\)Proper learning, helly number, and an optimal svm bound\.InConference on Learning Theory,pp\. 582–609\.Cited by:[§1\.2](https://arxiv.org/html/2609.21445#S1.SS2.p2.1)\.
- \[4\]M\. Braverman, R\. Livni, Y\. Mansour, S\. Moran, and K\. Nissim\(2026\)Learning from equivalence queries, revisited\.arXiv preprint arXiv:2604\.04535\.Cited by:[§1](https://arxiv.org/html/2609.21445#S1.p4.1)\.
- \[5\]Z\. Chase and I\. Mehalel\(2024\)Deterministic apple tasting\.arXiv preprint arXiv:2410\.10404\.Cited by:[§2\.2](https://arxiv.org/html/2609.21445#S2.SS2.p5.1),[§5](https://arxiv.org/html/2609.21445#S5.p2.1)\.
- \[6\]A\. Daniely and S\. Shalev\-Shwartz\(2014\)Optimal learners for multiclass problems\.InConference on Learning Theory,pp\. 287–316\.Cited by:[§1\.2](https://arxiv.org/html/2609.21445#S1.SS2.p2.1)\.
- \[7\]C\. Daskalakis and N\. Golowich\(2022\)Fast rates for nonparametric online learning: from realizability to learning in games\.InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing,pp\. 846–859\.Cited by:[§1\.1](https://arxiv.org/html/2609.21445#S1.SS1.p3.1),[Table 1](https://arxiv.org/html/2609.21445#S1.T1.3.3.3),[§1](https://arxiv.org/html/2609.21445#S1.p3.1),[Abstract](https://arxiv.org/html/2609.21445#abstract1.1)\.
- \[8\]Y\. Filmus, S\. Hanneke, I\. Mehalel, and S\. Moran\(2024\)Bandit\-feedback online multiclass classification: variants and tradeoffs\.arXiv preprint arXiv:2402\.07453\.Cited by:[§2\.1](https://arxiv.org/html/2609.21445#S2.SS1.p8.1)\.
- \[9\]Y\. Freund and R\. E\. Schapire\(1997\)A decision\-theoretic generalization of on\-line learning and an application to boosting\.Journal of computer and system sciences55\(1\),pp\. 119–139\.Cited by:[item 1](https://arxiv.org/html/2609.21445#S2.I2.i1.p1.1),[§4\.1](https://arxiv.org/html/2609.21445#S4.SS1.p2.1),[§4\.1](https://arxiv.org/html/2609.21445#S4.SS1.p2.2),[Theorem 4\.3](https://arxiv.org/html/2609.21445#S4.Thmtheorem3)\.
- \[10\]J\. Geneson and L\. Tang\(2024\)Bounds on the price of feedback for mistake\-bounded online learning\.arXiv preprint arXiv:2401\.05794\.Cited by:[§2\.1](https://arxiv.org/html/2609.21445#S2.SS1.p8.1)\.
- \[11\]S\. Hanneke, R\. Livni, and S\. Moran\(2021\)Online learning with simple predictors and a combinatorial characterization of minimax in 0/1 games\.InConference on Learning Theory,pp\. 2289–2314\.Cited by:[Table 1](https://arxiv.org/html/2609.21445#S1.T1.3.2.3),[§1](https://arxiv.org/html/2609.21445#S1.p2.1),[§1](https://arxiv.org/html/2609.21445#S1.p3.1),[item 2](https://arxiv.org/html/2609.21445#S2.I2.i2.p1.1),[§3\.2\.2](https://arxiv.org/html/2609.21445#S3.SS2.SSS2.p1.1),[§4\.1](https://arxiv.org/html/2609.21445#S4.SS1.p1.1),[Theorem 4\.2](https://arxiv.org/html/2609.21445#S4.Thmtheorem2)\.
- \[12\]S\. Hanneke\(2016\)The optimal sample complexity of pac learning\.Journal of Machine Learning Research17\(38\),pp\. 1–15\.Cited by:[§1\.2](https://arxiv.org/html/2609.21445#S1.SS2.p2.1)\.
- \[13\]D\. Haussler and E\. Welzl\(1986\)Epsilon\-nets and simplex range queries\.InProceedings of the second annual symposium on Computational geometry,pp\. 61–71\.Cited by:[item 3](https://arxiv.org/html/2609.21445#S2.I2.i3.p1.1),[Theorem 4\.5](https://arxiv.org/html/2609.21445#S4.Thmtheorem5)\.
- \[14\]N\. Littlestone\(1988\)Learning quickly when irrelevant attributes abound: a new linear\-threshold algorithm\.Machine learning2\(4\),pp\. 285–318\.Cited by:[§1\.1](https://arxiv.org/html/2609.21445#S1.SS1.p3.1),[§1\.2](https://arxiv.org/html/2609.21445#S1.SS2.p2.1),[Table 1](https://arxiv.org/html/2609.21445#S1.T1.3.5.3),[§1](https://arxiv.org/html/2609.21445#S1.p1.1),[§1](https://arxiv.org/html/2609.21445#S1.p4.1),[§3\.2\.1](https://arxiv.org/html/2609.21445#S3.SS2.SSS1.p2.1),[Theorem 3\.1](https://arxiv.org/html/2609.21445#S3.Thmtheorem1)\.
- \[15\]P\. M\. Long\(2020\)New bounds on the price of bandit feedback for mistake\-bounded online multiclass learning\.Theoretical Computer Science808,pp\. 159–163\.Cited by:[§2\.1](https://arxiv.org/html/2609.21445#S2.SS1.p8.1)\.
- \[16\]A\. Rakhlin, K\. Sridharan, and A\. Tewari\(2015\)Online learning via sequential complexities\.\.J\. Mach\. Learn\. Res\.16\(1\),pp\. 155–186\.Cited by:[Table 1](https://arxiv.org/html/2609.21445#S1.T1.3.2.3)\.
- \[17\]S\. Shalev\-Shwartz and S\. Ben\-David\(2014\)Understanding machine learning: from theory to algorithms\.Cambridge university press\.Cited by:[footnote 2](https://arxiv.org/html/2609.21445#footnote2)\.
- \[18\]V\. N\. Vapnik and A\. Ya\. Chervonenkis\(1971\)On the uniform convergence of relative frequencies of events to their probabilities\.Theory of Probability & Its Applications16\(2\),pp\. 264–280\.Cited by:[§1\.2](https://arxiv.org/html/2609.21445#S1.SS2.p2.1)\.
- \[19\]J\. von Neumann\(1928\)Zur theorie der gesellschaftsspiele\.Mathematische annalen100\(1\),pp\. 295–320\.Cited by:[item 2](https://arxiv.org/html/2609.21445#S2.I2.i2.p1.1)\.