Sparsity regret bounds for individual sequences in online linear regression

Sébastien Gerchinovitz 1, 2
2 CLASSIC - Computational Learning, Aggregation, Supervised Statistical, Inference, and Classification
DMA - Département de Mathématiques et Applications - ENS Paris, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt
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 to the stochastic setting (regression model with random design). This yields risk bounds of the same flavor as in Dalalyan and Tsybakov (2011) 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. We also address the regression model with fixed design.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2011, 14, pp.729-769
Liste complète des métadonnées

Littérature citée [48 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00552267
Contributeur : Sébastien Gerchinovitz <>
Soumis le : vendredi 12 avril 2013 - 12:10:25
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : samedi 13 juillet 2013 - 04:03:47

Fichiers

gerchinovitz13a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00552267, version 3
  • ARXIV : 1101.1057

Collections

Citation

Sébastien Gerchinovitz. Sparsity regret bounds for individual sequences in online linear regression. Journal of Machine Learning Research, Journal of Machine Learning Research, 2011, 14, pp.729-769. 〈inria-00552267v3〉

Partager

Métriques

Consultations de la notice

453

Téléchargements de fichiers

314