Sparsity Regret Bounds for Individual Sequences in Online Linear Regression

Sébastien Gerchinovitz ; JMLR W&CP 19:377-396, 2011.

Abstract

We consider the problem of online linear regression on arbitrary deterministic sequences when the ambient dimension $d$ can be much larger than the number of time rounds $T$. We introduce the notion of sparsity regret bound, which is a deterministic online counterpart of recent risk bounds derived in the stochastic setting under a sparsity scenario. We prove such regret bounds for an online-learning algorithm called SeqSEW and based on exponential weighting and data-driven truncation. In a second part we apply a parameter-free version of this algorithm on {i.i.d.}\ data and derive risk bounds of the same flavor as in \citet{DaTsy08SEW,DaTsy10MirrorAveraging} but which solve two questions left open therein. In particular our risk bounds are adaptive (up to a logarithmic factor) to the unknown variance of the noise if the latter is Gaussian.