Sparse regression learning by aggregation and Langevin Monte-Carlo

DOI10.1016/J.JCSS.2011.12.023zbMATH Open1244.62054arXiv0903.1223OpenAlexW1547983335MaRDI QIDQ439987FDOQ439987

Authors: Arnak S. Dalalyan, Alexandre B. Tsybakov 

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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 $$ of the EWA is larger than or equal to $4sigm{a}^2$, where $sigm{a}^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 $ph{i}_1,\mathrm{...},ph{i}_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 $ph{i}_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.

Full work available at URL: https://arxiv.org/abs/0903.1223

Recommendations

• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• On the exponentially weighted aggregate with the Laplace prior
• Aggregated estimators and empirical complexity for least square regression
• PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting
• Aggregation by Exponential Weighting and Sharp Oracle Inequalities

zbMATH Keywords

logistic regressionoracle inequalitiesregression estimationsparse learningsparsity prior

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Monte Carlo methods (65C05) Learning and adaptive systems in artificial intelligence (68T05) Generalized linear models (logistic models) (62J12)

Cites Work

• Graph selection with GGMselect
• Nearly unbiased variable selection under minimax concave penalty
• Least angle regression. (With discussion)
• Fast learning rates in statistical inference through aggregation
• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional generalized linear models and the lasso
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• High-dimensional graphs and variable selection with the Lasso
• Title not available (Why is that?)
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Title not available (Why is that?)
• Sequential prediction of individual sequences under general loss functions
• Regularization and Variable Selection Via the Elastic Net
• Prediction, Learning, and Games
• Learning by mirror averaging
• Sparsity oracle inequalities for the Lasso
• Empirical Bayes selection of wavelet thresholds
• The sparsity and bias of the LASSO selection in high-dimensional linear regression
• Langevin diffusions and Metropolis-Hastings algorithms
• Stable recovery of sparse overcomplete representations in the presence of noise
• Time-reversible diffusions
• Markov chains and stochastic stability
• Aggregation for Gaussian regression
• Information Theory and Mixing Least-Squares Regressions
• Aggregation and Sparsity Via ℓ1 Penalized Least Squares
• The weighted majority algorithm
• Title not available (Why is that?)
• Aggregating regression procedures to improve performance
• Optimal rates and adaptation in the single-index model using aggregation
• Statistical learning theory and stochastic optimization. Ecole d'Eté de Probabilitiés de Saint-Flour XXXI -- 2001.
• How to use expert advice
• On the Generalization Ability of On-Line Learning Algorithms
• On optimality of Bayesian testimation in the normal means problem
• Bayesian inference and optimal design for the sparse linear model
• An Empirical Bayesian Strategy for Solving the Simultaneous Sparse Approximation Problem
• PAC-Bayesian stochastic model selection
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Sparse regression learning by aggregation and Langevin Monte-Carlo
• Sparse recovery in convex hulls via entropy penalization
• Prediction of stochastic sequences
• On the optimality of the aggregate with exponential weights for low temperatures
• Mirror averaging with sparsity priors
• Aggregation by Exponential Weighting and Sharp Oracle Inequalities
• PAC-Bayesian bounds for randomized empirical risk minimizers
• Nonlinear estimation over weak Besov spaces and minimax Bayes

Cited In (38)

• Sharp oracle inequalities for aggregation of affine estimators
• Entropy-based closure for probabilistic learning on manifolds
• Title not available (Why is that?)
• Exponential screening and optimal rates of sparse estimation
• Noisy Monte Carlo: convergence of Markov chains with approximate transition kernels
• Optimal learning with \textit{Q}-aggregation
• The tamed unadjusted Langevin algorithm
• Approximate models and robust decisions
• Exponential weights in multivariate regression and a low-rankness favoring prior
• Non-convex penalized estimation in high-dimensional models with single-index structure
• Sparse regression learning by aggregation and Langevin Monte-Carlo
• Sharp oracle inequalities for low-complexity priors
• Entropic optimal transport is maximum-likelihood deconvolution
• Weighted multilevel Langevin simulation of invariant measures
• Mirror averaging with sparsity priors
• PAC-Bayesian high dimensional bipartite ranking
• On Stochastic Gradient Langevin Dynamics with Dependent Data Streams: The Fully Nonconvex Case
• Probabilistic learning inference of boundary value problem with uncertainties based on Kullback-Leibler divergence under implicit constraints
• Prediction error bounds for linear regression with the TREX
• Probabilistic learning on manifolds constrained by nonlinear partial differential equations for small datasets
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• PAC-Bayesian bounds for sparse regression estimation with exponential weights
• Approximation for the invariant measure with applications for jump processes (convergence in total variation distance)
• Statistical inference in compound functional models
• PAC-Bayesian estimation and prediction in sparse additive models
• Simple proof of the risk bound for denoising by exponential weights for asymmetric noise distributions
• Selection of KL neighbourhood in robust Bayesian inference
• A reduced-rank approach to predicting multiple binary responses through machine learning
• Functional inequalities for perturbed measures with applications to log-concave measures and to some Bayesian problems
• On the exponentially weighted aggregate with the Laplace prior
• Sparse recovery under matrix uncertainty
• Sampling from non-smooth distributions through Langevin diffusion
• Ergodicity of supercritical SDEs driven by \(\alpha \)-stable processes and heavy-tailed sampling
• PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting
• High-dimensional sparse classification using exponential weighting with empirical hinge loss
• A quasi-Bayesian perspective to online clustering
• Sparse estimation by exponential weighting
• User-friendly Introduction to PAC-Bayes Bounds

Uses Software

• GGMselect
• EBayesThresh

This page was built for publication: Sparse regression learning by aggregation and Langevin Monte-Carlo

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439987)