In order to design our algorithms, we have to consider the following setting.
We introduce the multiclass online learning game (fig:online-game) that has been studied extensively (see e.g., [1]}). In this game, there are two players, the adversary that chooses features and reveals them to the second player, the learner whose goal is to guess a label for the given example.
<FIGURE>