Sébastien Gerchinovitz
Adaptive and Optimal Online Linear Regression on L1-balls.
Mon, 05/23/2011 - 15:01 — SomNambulAuthors: Sébastien Gerchinovitz, Jia Yuan Yu
Subjects: Machine Learning
AbstractWe consider the problem of online linear regression on individual sequences.
The goal in this paper is for the forecaster to output sequential predictions
which are, after T time rounds, almost as good as the ones output by the best
linear predictor in a given L1-ball in R^d. We consider both the cases where
the dimension d is small and large relative to the time horizon T. We first
present regret bounds with optimal dependencies on the sizes U, X and Y of the
L1-ball, the input data and the observations.Sparsity regret bounds for individual sequences in online linear regression.
Thu, 01/06/2011 - 16:01 — SomNambulAuthors: Sébastien Gerchinovitz
Subjects: Machine Learning
AbstractWe 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$. In this framework we prove deterministic online
counterparts of the so-called sparsity oracle inequalities introduced in the
stochastic setting in the past decade. They indicate that the task consisting
in predicting almost as well as an unknown high-dimensional target vector is
still statistically feasible if this target vector has only few non-zero
coordinates.
User login
