Compressed Least-Squares Regression

Odalric-Ambrym Maillard 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We consider the problem of learning, from K data, a regression function in a linear space of high dimension N using projections onto a random subspace of lower dimension M. From any algorithm minimizing the (possibly penalized) empirical risk, we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We show that solving the problem in the compressed domain instead of the initial domain reduces the estimation error at the price of an increased (but controlled) approximation error. We apply the analysis to Least-Squares (LS) regression and discuss the excess risk and numerical complexity of the resulting ``Compressed Least Squares Regression'' (CLSR) in terms of N, K, and M. When we choose M=O(\sqrt{K}), we show that CLSR has an estimation error of order O(\log K / \sqrt{K}).
Type de document :
Communication dans un congrès
NIPS 2009, Dec 2009, Vancouver, Canada. 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00419210
Contributeur : Rémi Munos <>
Soumis le : vendredi 30 octobre 2009 - 14:56:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 13:34:57

Fichier

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

Identifiants

  • HAL Id : inria-00419210, version 2

Collections

Citation

Odalric-Ambrym Maillard, Rémi Munos. Compressed Least-Squares Regression. NIPS 2009, Dec 2009, Vancouver, Canada. 2009. 〈inria-00419210v2〉

Partager

Métriques

Consultations de la notice

1300

Téléchargements de fichiers

588