Sparse regression learning by aggregation and Langevin Monte-Carlo

We consider the problem of regression learning for deterministic design and independent random er-rors. We start by proving a sharp PAC-Bayesian type bound for the exponentially weighted aggre-gate (EWA) under the expected squared empirical loss. For a broad class of noise distributions the presented bound is valid whenever the temperature parameter β of the EWA is larger than or equal to 4σ2, where σ2 is the noise variance. A remarkable feature of this result is that it is valid even for un-bounded regression functions and the choice of the temperature parameter depends exclusively on the noise level. Next, we apply this general bound to the problem of aggregating the elements of a finite-dimensional linear space spanned by a dictionary of functions φ1,..., φM. We allow M to be much larger than the sample size n but we assume that the true re-gression function can be well approximated by a sparse linear combination of functions φj. Under this sparsity scenario, we propose an EWA with a heavy tailed prior and we show that it satisfies a sparsity oracle inequality with leading constant one. Finally, we propose several Langevin Monte-Carlo algorithms to approximately compute such an EWA when the number M of aggregated functions can be large. We discuss in some detail the conver-gence of these algorithms and present numerical experiments that confirm our theoretical findings.