Self-Directed Linear Classification
Ilias Diakonikolas Vasilis Kontonis Christos Tzamos Nikos Zarifis
In online classification, a learner is presented with a sequence of examples
and aims to predict their labels in an online fashion so as to minimize the
total number of mistakes. In the self-directed variant, the learner knows in
advance the pool of examples and can adaptively choose the order in which
predictions are made. Here we study the power of choosing the prediction order
and establish the first strong separation between worst-order and random-order
learning for the fundamental task of linear classification. Prior to our work,
such a separation was known only for very restricted concept classes, e.g.,
one-dimensional thresholds or axis-aligned rectangles.
  We present two main results. If $X$ is a dataset of $n$ points drawn
uniformly at random from the $d$-dimensional unit sphere, we design an
efficient self-directed learner that makes $O(d \log \log(n))$ mistakes and
classifies the entire dataset. If $X$ is an arbitrary $d$-dimensional dataset
of size $n$, we design an efficient self-directed learner that predicts the
labels of $99\%$ of the points in $X$ with mistake bound independent of $n$. In
contrast, under a worst- or random-ordering, the number of mistakes must be at
least $\Omega(d \log n)$, even when the points are drawn uniformly from the
unit sphere and the learner only needs to predict the labels for $1\%$ of them.