Uniform regret bounds over R^d for the sequential linear regression problem with the square loss
We consider the setting of online linear regression for arbitrary deterministic sequences, with the square loss. We are interested in regret bounds that hold uniformly over all vectors in u ∈ R^d. Vovk (2001) showed a d ln T lower bound on this uniform regret. We exhibit forecasters with closed-form regret bounds that match this d ln T quantity. To the best of our knowledge, earlier works only provided closed-form regret bounds of 2d ln T + O(1).
READ FULL TEXT