The Gain from Ordering in Online Learning

We study fixed-design online learning where the learner is allowed to choose the order of the datapoints in order to minimize their regret (aka self-directed online learning). We focus on the fundamental task of online linear regression: the learner is given a dataset X with n examples in d dimensions and at step t they select a point x t ∈ X, predict a value y t , and suffer loss ( y t -w * • x t ) 2 . The goal is to design algorithms that order the examples and achieve better regret than randomor worst-order online algorithms. For an arbitrary dataset X, we show that, under the Exponential Time Hypothesis, no efficient algorithm can approximate the optimal (best-order) regret within a factor of d 1/poly(log log d) . We then show that, for structured datasets, we can bypass the above hardness result and achieve nearly optimal regret. When the examples of X are drawn i.i.d. from the uniform distribution on the sphere, we present an algorithm based on the greedy heuristic of selecting "easiest" examples first that achieves a log d-approximation of the optimal regret.