Self-Directed Linear Classification
This work provides a strong separation between worst-order and random-order learning for linear classification, addressing a fundamental problem in online learning theory with implications for algorithm design in machine learning.
The paper tackles the problem of self-directed online linear classification, where a learner can choose the order of predictions from a known pool of examples, and shows that this approach significantly reduces mistakes compared to worst- or random-order learning. Specifically, for random points on a unit sphere, it achieves O(d log log(n)) mistakes to classify all points, and for arbitrary datasets, it predicts 99% of points with a mistake bound independent of n, whereas worst-order requires Ω(d log n) mistakes even for 1% of points.
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 $Ω(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.