Compressed Least-Squares Regression - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Compressed Least-Squares Regression

Odalric-Ambrym Maillard
Rémi Munos
  • Fonction : Auteur
  • PersonId : 836863

Résumé

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}).
Fichier principal
Vignette du fichier
cls_nips.pdf (129.1 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00419210 , version 1 (22-09-2009)
inria-00419210 , version 2 (30-10-2009)

Identifiants

  • HAL Id : inria-00419210 , version 2

Citer

Odalric-Ambrym Maillard, Rémi Munos. Compressed Least-Squares Regression. NIPS 2009, Dec 2009, Vancouver, Canada. ⟨inria-00419210v2⟩
1155 Consultations
941 Téléchargements

Partager

Gmail Facebook X LinkedIn More