Uniform regret bounds over Rd for the sequential linear regression problem with the square loss

Pierre Gaillard, Sébastien Gerchinovitz, Malo Huard, Gilles Stoltz
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:404-432, 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 closed-form regret bounds of 2dB2lnT+OT(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 dB2lnT term. In the case of sequentially revealed features, we also derive an asymptotic regret bound of dB2lnT for any individual sequence of features and bounded observations. All our algorithms are variants of the online non-linear ridge regression forecaster, either with a data-dependent regularization or with almost no regularization.

Cite this Paper


BibTeX
@InProceedings{pmlr-v98-gaillard19a, title = {Uniform regret bounds over $\mathbb{R}^d$ for the sequential linear regression problem with the square loss}, author = {Gaillard, Pierre and Gerchinovitz, S{\'e}bastien and Huard, Malo and Stoltz, Gilles}, booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory}, pages = {404--432}, year = {2019}, editor = {Garivier, Aurélien and Kale, Satyen}, volume = {98}, series = {Proceedings of Machine Learning Research}, month = {22--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v98/gaillard19a/gaillard19a.pdf}, url = {https://proceedings.mlr.press/v98/gaillard19a.html}, 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 closed-form 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 non-linear ridge regression forecaster, either with a data-dependent regularization or with almost no regularization.} }
Endnote
%0 Conference Paper %T Uniform regret bounds over $\mathbb{R}^d$ for the sequential linear regression problem with the square loss %A Pierre Gaillard %A Sébastien Gerchinovitz %A Malo Huard %A Gilles Stoltz %B Proceedings of the 30th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Aurélien Garivier %E Satyen Kale %F pmlr-v98-gaillard19a %I PMLR %P 404--432 %U https://proceedings.mlr.press/v98/gaillard19a.html %V 98 %X 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 closed-form 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 non-linear ridge regression forecaster, either with a data-dependent regularization or with almost no regularization.
APA
Gaillard, P., Gerchinovitz, S., Huard, M. & Stoltz, G.. (2019). Uniform regret bounds over $\mathbb{R}^d$ for the sequential linear regression problem with the square loss. Proceedings of the 30th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 98:404-432 Available from https://proceedings.mlr.press/v98/gaillard19a.html.

Related Material