Pac-Bayesian Bounds for Sparse Regression Estimation with Exponential Weights

We consider the sparse regression model where the number of parametersp is larger than the sample size n. The difficulty when consideringhigh-dimensional problems is to propose estimators achieving a good compromisebetween statistical and computational performances. The BIC estimatorfor instance performs well from the statistical point of view [11] but can onlybe computed for values of p of at most a few tens. The Lasso estimator issolution of a convex minimization problem, hence computable for large valueof p. However stringent conditions on the design are required to establish fastrates of convergence for this estimator. Dalalyan and Tsybakov [19] proposea method achieving a good compromise between the statistical and computationalaspects of the problem. Their estimator can be computed for reasonablylarge p and satisfies nice statistical properties under weak assumptions on thedesign. However, [19] proposes sparsity oracle inequalities in expectation forthe empirical excess risk only. In this paper, we propose an aggregation proceduresimilar to that of [19] but with improved statistical performances. Ourmain theoretical result is a sparsity oracle inequality in probability for the trueexcess risk for a version of exponential weight estimator. We also propose aMCMC method to compute our estimator for reasonably large values of p.