A Trichotomy for Transductive Online Learning

We present new upper and lower bounds on the number of learner mistakes in the `transductive' online learning setting of Ben-David, Kushilevitz and Mansour (1997). This setting is similar to standard online learning, except that the adversary fixes a sequence of instances x1,dots,xn to be labeled at the start of the game, and this sequence is known to the learner. Qualitatively, we prove a trichotomy, stating that the minimal number of mistakes made by the learner as n grows can take only one of precisely three possible values: n, Thetaleft(log (n)right), or Theta(1). Furthermore, this behavior is determined by a combination of the VC dimension and the Littlestone dimension. Quantitatively, we show a variety of bounds relating the number of mistakes to well-known combinatorial dimensions. In particular, we improve the known lower bound on the constant in the Theta(1) case from Omegaleft(√log(d)right) to Omega(log(d)) where d is the Littlestone dimension. Finally, we extend our results to cover multiclass classification and the agnostic setting.