Universal Multiclass Transductive Online Learning

We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class $\mathcal{H}$ is learnable if there is a learning algorithm $\mathcal{A}$, such that for every realizable sequence, the number of mistakes made by $\mathcal{A}$ grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called "Level-Constrained-Littlestone-Littlestone (LCLL) tree", which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.

In the online learning setting, the predictor is required to predict the label of an instance chosen by the adversary every round and make as few mistakes as possible. The adversary can choose both the next instance and the true label after each prediction. We want to understand how the number of mistakes increases with the time horizon per adversary if the adversary only has the flexibility to choose the true labels. Thus, we introduce the learning model called universal transductive online learning, where the adversary needs to show the sequence of instances to the predictor in advance. We show that when the label space is non-binary, for example, the handwriting number detecting task, there are three possible increasing types of the number of mistakes as a function of the number of rounds. We provide the characterization of these three types and give brand new methods to design algorithms to utilize the distinct properties of our characterization. Our results further prove the separation between transductive online learning and online learning. We also provide a new method to design learning algorithms by utilizing a specific property, which was considered not relevant to algorithm design.