Brownian Motions and Scrambled Wavelets for 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 ordinary (non penalized) least-squares regression where the regression function is chosen in a randomly generated sub-space GP \subset S of finite dimension P, where S is a function space of infinite dimension, e.g. L2([0, 1]^d). GP is defined as the span of P random features that are linear combinations of the basis functions of S weighted by random Gaussian i.i.d. coefficients. We characterize the so-called kernel space K \subset S of the resulting Gaussian process and derive approximation error bounds of order O(||f||^2_K log(P)/P) for functions f \in K approximated in GP . We apply this result to derive excess risk bounds for the least-squares estimate in various spaces. For illustration, we consider regression using the so-called scrambled wavelets (i.e. random linear combinations of wavelets of L2([0, 1]^d)) and derive an excess risk rate O(||f*||_K(logN)/sqrt(N)) which is arbitrarily close to the minimax optimal rate (up to a logarithmic factor) for target functions f* in K = H^s([0, 1]^d), a Sobolev space of smoothness order s > d/2. We describe an efficient implementation using lazy expansions with numerical complexity ˜O(2dN^3/2 logN+N^5/2), where d is the dimension of the input data and N is the number of data.
Liste complète des métadonnées
Contributeur : Odalric-Ambrym Maillard <>
Soumis le : mercredi 12 mai 2010 - 11:54:50
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 16 septembre 2010 - 14:17:43


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00483017, version 1



Odalric-Ambrym Maillard, Rémi Munos. Brownian Motions and Scrambled Wavelets for Least-Squares Regression. [Technical Report] 2010, pp.13. 〈inria-00483017〉



Consultations de la notice


Téléchargements de fichiers