Exponential Screening and optimal rates of sparse estimation

By Philippe Rigollet, Alexandre B. Tsybakov. 2010

248 citations recorded by the source corpus.

In high-dimensional linear regression, the goal pursued here is to estimate an unknown regression function using linear combinations of a suitable set of covariates. One of the key assumptions for the success of any statistical procedure in this setup is to assume that the linear combination is sparse in some sense, for example, that it involves only few covariates. We consider a general, non necessarily linear, regression with Gaussian noise and study a related question that is to find a linear combination of approximating functions, which is at the same time sparse and has small mean squared error (MSE). We introduce a new estimation procedure, called Exponential Screening that shows remarkable adaptation properties. It adapts to the linear combination that optimally balances MSE and sparsity, whether the latter is measured in terms of the number of non-zero entries in the combination ($\ell_0$ norm) or in terms of the global weight of the combination ($\ell_1$ norm). The power of this adaptation result is illustrated by showing that Exponential Screening solves optimally and simultaneously all the problems of aggregation in Gaussian regression that have been discussed in the literature. Moreover, we show that the performance of the Exponential Screening estimator cannot be improved in a minimax sense, even if the optimal sparsity is known in advance. The theoretical and numerical superiority of Exponential Screening compared to state-of-the-art sparse procedures is also discussed.

Subfields: Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Sparse Partially Linear Additive Models (2014, background): “When all features are linear (N0 = ∅), this result reduces to the traditional slow rate bound for the lasso (up to constants) (Rigollet and Tsybakov 2011).”
Assumptionless consistency of the Lasso (2013, background): “The author thanks Alexandre Tsybakov, Peter Bickel, Peter Bühlmann, Peter Bartlett, Mathias Drton, Gilles Blanchard and Persi Diaconis for helpful comments.”
Estimation of high-dimensional low-rank matrices (2009, methodology): “For more details about optimal rates of sparse estimation in the vector case, see Rigollet and Tsybakov (2010).”
Prediction error of cross-validated Lasso (2015, methodology): “…on the smallest nonzero singular value of the design matrix looks a bit restrictive, especially since it has been observed in several recent papers that risk consistency in Lasso (with deterministic value of the tuning parameter) holds without any conditions on the design matrix [1, 3, 6, 27].”
Oracle Inequalities for High Dimensional Vector Autoregressions (2012, background): “Inequalities of the type (4)-(6) are not new, see e.g. Bickel et al. (2009) or Rigollet and Tsybakov (2011).”
On cross-validated Lasso in high dimensions (2016, background): “If λ is chosen appropriately, the Lasso estimator attains the optimal rate of convergence under fairly general conditions; see, for example, [13], [8], and [34].”
Oracle Inequalities and Optimal Inference under Group Sparsity (2010, methodology): “Note that this conclusion cannot be deduced from the lower bounds of [30] and [32].”
Sharp oracle inequalities for Least Squares estimators in shape restricted regression (2015, background): “lled adaptive oracleinequalities. Such trade-oﬀ is common in the context of sparse linear regression, where the right hand side of sparsity oracleinequalities balances approximationerror and sparsity [9, 21, 27]. This is opposed to the oracle inequality (7) where there is no trade-oﬀ, the right hand”
BAYESIAN LINEAR REGRESSION WITH SPARSE PRIORS (2014, methodology): “1), we borrow from the work on sparse regression within the non-Bayesian framework; see [1, 6, 9, 10, 13, 19, 29, 36, 49, 50].”
Minimax Rates of Estimation for High-Dimensional Linear Regression Over q -Balls (2009, result): “• Finally, in the special cases q = 0 and q = 1, subsequent work by Rigollet and Tsybakov [30] has yielded sharper results on the prediction error (compare our Theorems 3 and 4 to equations (5.”
Slope meets Lasso: Improved oracle bounds and optimality (2016, background): “This formulation might be of interest in the context of aggregation as explained, for example, in [23].”
Group Regularized Estimation Under Structural Hierarchy (2014, background): “y Stirling’s approximation, logjB1(J G;J e)j= log J2 G J e J elog(J2 G =J e) cJ elog(eJ 2 G =J e) for some universal constant c. Let ˆ( 1; 2) = k 1 2k 0 be the Hamming distance. By Lemma 8.3 in Rigollet and Tsybakov (2011), there exists a subset B10(J G;J e) ˆB1(J G;J e) such that logjB10(J G;J e)”
Restricted Strong Convexity Implies Weak Submodularity (2016, methodology): “These include using the Lasso, greedy selection methods (such as Forward Stagewise/Stepwise Regressions [35], OMP, and CoSaMP [38]), forward–backward methods [24, 31], Pareto optimization [43], exponentially weighted aggregation [45], and truncated gradient methods [23].”
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration (2017, methodology): “This powerful idea has been successfully applied to a variety of contexts not only as a statistical tool for model selection [JRT08, RT11, RT12] and online learning [CBL06], but also as an optimization gadget in ﬁrst-order optimization methods such as mirror descent and proximal methods [Bub15].”
Sparse PCA: Optimal rates and adaptive estimation (2012, background): “Koltchinskii, Lounici and Tsybakov [32] considered estimation of low-rank matrices based on a trace regression model which includes matrix completion as a special case.”
Linear and conic programming estimators in high dimensional errors‐in‐variables models (2014, background): “Indeed, this follows from the Varshamov–Gilbert bound (see lemma 2.9 in Tsybakov (2009)) if s − 1 > .p − 1/=2 and from lemma A.3 in Rigollet and Tsybakov (2011) if s−1 .p−1/=2.”
How Correlations Influence Lasso Prediction (2012, methodology): “Moreover, we ﬁnd both in theory and simulations that Lasso performs well for any degree of correlations if the tuning parameter is chosen suitably.”