Horizon Independent Minimax Linear Regression

We consider a linear regression game: at each round, an adversary reveals a covariate vector, the learner predicts a real value, the adversary reveals a label, and the learner incurs the squared prediction error. The aim is to minimize the difference between the cumulative loss and that of the linear predictor that is best in hindsight. During the information theory program, we presented work showing that the minimax optimal strategy is easy to compute under various constraints on the adversary's labels, provided that the sequence of covariate vectors is known in advance. These optimal predictions depend on the full covariate sequence. Here, we present a strategy that can be efficiently computed and show that it is minimax optimal for an adversarially chosen covariate sequence, provided that the sequence satisfies a certain total covariance budget constraint that is known in advance.  This strategy is horizon-independent, that is, no matter how long the game runs, this strategy incurs no more regret than the optimal strategy that knows in advance the number of rounds of the game.