Pac-bayesian bounds for sparse regression estimation with exponential weights

Abstract

We consider the sparse regression model where the number of parameters $p$ is larger than the sample size $n$. The difficulty when considering high-dimensional problems is to propose estimators achieving a good compromise between statistical and computational performances. The BIC estimator for instance performs well from the statistical point of view \cite{BTW07} but can only be computed for values of $p$ of at most a few tens. The Lasso estimator is solution of a convex minimization problem, hence computable for large value of $p$. However stringent conditions on the design are required to establish fast rates of convergence for this estimator. Dalalyan and Tsybakov \cite{arnak} propose a method achieving a good compromise between the statistical and computational aspects of the problem. Their estimator can be computed for reasonably large $p$ and satisfies nice statistical properties under weak assumptions on the design. However, \cite{arnak} proposes sparsity oracle inequalities in expectation for the empirical excess risk only. In this paper, we propose an aggregation procedure similar to that of \cite{arnak} but with improved statistical performances. Our main theoretical result is a sparsity oracle inequality in probability for the true excess risk for a version of exponential weight estimator. We also propose a MCMC method to compute our estimator for reasonably large values of $p$.

19 pages

References in corpus (23)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Simultaneous analysis of Lasso and Dantzig selector
• On the conditions used to prove oracle results for the Lasso
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation
• The Dantzig selector and sparsity oracle inequalities
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• Learning by mirror averaging
• Rejoinder: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• PAC-Bayesian Bounds for Randomized Empirical Risk Minimizers
• Mirror averaging with sparsity priors

Cited by in corpus (9)

• Sparse Estimation by Exponential Weighting
• Kullback-Leibler aggregation and misspecified generalized linear models
• Sharp Oracle Inequalities for Aggregation of Affine Estimators
• Bayesian methods for low-rank matrix estimation: short survey and theoretical study
• A Bayesian Approach for Noisy Matrix Completion: Optimal Rate under General Sampling Distribution
• PAC-Bayesian Estimation and Prediction in Sparse Additive Models
• Optimal learning with $Q$-aggregation
• PAC-Bayesian High Dimensional Bipartite Ranking
• A Quasi-Bayesian Perspective to Online Clustering