Sparse Regression Learning by Aggregation and Langevin Monte-Carlo

Abstract

We consider the problem of regression learning for deterministic design and independent random errors. We start by proving a sharp PAC-Bayesian type bound for the exponentially weighted aggregate (EWA) under the expected squared empirical loss. For a broad class of noise distributions the presented bound is valid whenever the temperature parameter $\beta$ of the EWA is larger than or equal to $4{\sigma }^2$, where ${\sigma }^2$ is the noise variance. A remarkable feature of this result is that it is valid even for unbounded 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 ${\varphi }_1,...,{\varphi }_M$. We allow $M$ to be much larger than the sample size $n$ but we assume that the true regression function can be well approximated by a sparse linear combination of functions ${\varphi }_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 convergence of these algorithms and present numerical experiments that confirm our theoretical findings.

Short version published in COLT 2009

References in corpus (15)

• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional graphs and variable selection with the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• High-dimensional generalized linear models and the lasso
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• Fast learning rates in statistical inference through aggregation
• On optimality of Bayesian testimation in the normal means problem
• PAC-Bayesian Bounds for Randomized Empirical Risk Minimizers
• Optimal rates and adaptation in the single-index model using aggregation
• Sparse recovery in convex hulls via entropy penalization
• Graph selection with GGMselect

Cited by in corpus (31)

• Sparse recovery under matrix uncertainty
• On the Prediction Performance of the Lasso
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• On the properties of variational approximations of Gibbs posteriors
• User-friendly introduction to PAC-Bayes bounds
• Sparse Estimation by Exponential Weighting
• Sparse single-index model
• Probabilistic learning on manifolds constrained by nonlinear partial differential equations for small datasets
• Sharp Oracle Inequalities for Aggregation of Affine Estimators
• Mirror averaging with sparsity priors
• Bayesian methods for low-rank matrix estimation: short survey and theoretical study
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Pac-bayesian bounds for sparse regression estimation with exponential weights
• PAC-Bayesian Estimation and Prediction in Sparse Additive Models
• Optimal learning with $Q$-aggregation
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• PAC-Bayesian aggregation and multi-armed bandits
• Exponential weights in multivariate regression and a low-rankness favoring prior
• Adaptive Minimax Estimation over Sparse ${\ell }_q$-Hulls
• Probabilistic learning inference of boundary value problem with uncertainties based on Kullback-Leibler divergence under implicit constraints
• Linear regression through PAC-Bayesian truncation
• PAC-Bayesian High Dimensional Bipartite Ranking
• A reduced-rank approach to predicting multiple binary responses through machine learning
• From bilinear regression to inductive matrix completion: a quasi-Bayesian analysis
• High-dimensional sparse classification using exponential weighting with empirical hinge loss
• Concentration properties of fractional posterior in 1-bit matrix completion
• A Quasi-Bayesian Perspective to Online Clustering
• Misclassification bounds for PAC-Bayesian sparse deep learning
• Graph selection with GGMselect
• Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
• The exponentially weighted average forecaster in geodesic spaces of non-positive curvature