HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Linear regression with random projections

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^2), where d is the dimension of the input data and N is the number of data.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

Contributor : Odalric-Ambrym Maillard Connect in order to contact the contributor
Submitted on : Friday, October 29, 2010 - 3:47:46 PM
Last modification on : Thursday, January 20, 2022 - 4:16:24 PM
Long-term archiving on: : Sunday, January 30, 2011 - 2:59:00 AM


Files produced by the author(s)


  • HAL Id : inria-00483014, version 2



Odalric-Ambrym Maillard, Rémi Munos. Linear regression with random projections. [Technical Report] 2010, pp.22. ⟨inria-00483014v2⟩



Record views


Files downloads