Uniform regret bounds over $\mathbb{R}^d$ for the sequential linear regression problem with the square loss
[edit]
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:404432, 2019.
Abstract
We consider the setting of online linear regression for arbitrary deterministic sequences,
with the square loss. We are interested in the aim set by Bartlett et al. (2015):
obtain regret bounds that hold uniformly over all competitor vectors.
When the feature sequence is known at the beginning of the game, they provided closedform
regret bounds of $2d B^2 \ln T + \mathcal{O}_T(1)$, where $T$ is the number of rounds and $B$ is a
bound on the observations. Instead, we derive bounds with an optimal constant of $1$ in front of
the $d B^2 \ln T$ term. In the case of sequentially revealed features, we also derive an asymptotic
regret bound of $d B^2 \ln T$ for any individual sequence of features and bounded observations.
All our algorithms are variants of the online nonlinear ridge regression forecaster, either with a
datadependent regularization or with almost no regularization.
Related Material


