A Theory of Adversary-Directed Online Learning

We introduce the problem of *adversary-directed* online learning, in which the learner is aware of the set of instances in advance, and an adversary adaptively determines their ordering during the learning process. Surprisingly, this formulation has not been previously studied, perhaps due to its conceptual resemblance to the traditional adversarial online learning problem, despite related models, including the transductive, self-directed, and best-order, having been extensively explored. However, by utilizing novel techniques, we demonstrate that the landscape of adversary-directed online learning significantly diverges from that of traditional adversarial online learning. In the realizable setting, we establish a trichotomy of possible rates of the minimax number of mistakes. Specifically, for a learning horizon $\operatorname{T}$, the minimax number of mistakes can only be of the orders $\Theta(\operatorname{T})$, $\Theta(\log \operatorname{T})$, or $\Theta(1)$. To prove this, we introduce a new combinatorial complexity parameter, termed the perfect Littlestone dimension, whose finiteness distinguishes the $\Theta(\log \operatorname{T})$ rate from the $\Theta(\operatorname{T})$ rate. On the other hand, in the agnostic setting, we essentially show a dichotomy of possible rates of the minimax expected regret. In particular, if the learner plays for $\operatorname{T} \in \mathbb{N}$ rounds, its minimax expected regret can only be of the orders $\Theta(\operatorname{T})$, or $\widetilde{\Theta}(\sqrt{\operatorname{T}})$, which is also characterized by the finiteness of the perfect Littlestone dimension. Technically, a key ingredient in the proof of our $\mathcal{O}(\log \operatorname{T})$ and $\widetilde{\mathcal{O}}(\sqrt{\operatorname{T}})$ upper bounds is a novel online learning algorithm that leverages a new notion of shattering based on the perfect Littlestone dimension, which exploits the adaptive adversarial nature of the problem.