Reviews: Horizon-Independent Minimax Linear Regression

The problem of online linear regression is considered from an individual sequence perspective, where the aim is to control the square loss predictive regret with respect to the best linear predictor \theta \top x_t simultaneously for every sequence of covariate vectors x_t \in R d and outcomes y_t \in R in some constraint set. This is naturally formulated as a sequential game between the forecaster and an adversarial environment. In previous work [1], this problem was addressed in the "fixed-design" case, where the horizon T and the sequence of covariate vectors x_1 T is known in advance. The exact minimax strategy (MMS) was introduced and shown to be minimax optimal under natural constraint sets on the label sequence (such as ellipse-constrained labels). The MMS strategy consists in some form of least squares, but where the inverse cumulative covariance matrix \Pi_t {-1} is replaced by a shrunk version P_t that takes future instance into account.