Oracle Inequalities and Optimal Inference under Group Sparsity

By Karim Lounici, Massimiliano Pontil, Alexandre B. Tsybakov, Sara A. van de Geer. 2010

405 citations recorded by the source corpus.

We consider the problem of estimating a sparse linear regression vector s* under a gaussian noise model, for the purpose of both prediction and model selection. We assume that prior knowledge is available on the sparsity pattern, namely the set of variables is partitioned into prescribed groups, only few of which are relevant in the estimation process. This group sparsity assumption suggests us to consider the Group Lasso method as a means to estimate s*. We establish oracle inequalities for the prediction and l2 estimation errors of this estimator. These bounds hold under a restricted eigenvalue condition on the design matrix. Under a stronger coherence condition, we derive bounds for the estimation error for mixed (2,p)-norms with 1=p=8. When p=8, this result implies that a threshold version of the Group Lasso estimator selects the sparsity pattern of s* with high probability. Next, we prove that the rate of convergence of our upper bounds is optimal in a minimax sense, up to a logarithmic factor, for all estimators over a class of group sparse vectors. Furthermore, we establish lower bounds for the prediction and l2 estimation errors of the usual Lasso estimator. Using this result, we demonstrate that the Group Lasso can achieve an improvement in the prediction and estimation properties as compared to the Lasso.

Subfields: Computational Mechanics, Management Science and Operations Research, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/e3bd6e93288c00b45cb0b6fc1723cfa3f15161db

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 Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Least squares after model selection in high-dimensional sparse models (2009, neutral): “The second part of the corollary generalizes to the nonparametric case the lower bound obtained for Lasso by [15].”
Sparse PCA: Optimal rates and adaptive estimation (2012, background): “By the lower bounds in [36] for q = 0, the rates in Theorem 6 are optimal.”
Robust regression via mutivariate regression depth (2017, methodology): “ of multivariate linear regression without the group sparse structure, and the rates of Theorem 4.2 recover those of Theorem 4.1. The rates given by Theorem 4.2 are minimax optimal by Theorem 2.1 and [22]. 4.3 Reduced Rank Regression The ﬁnal application is for reduced rank regression. In the multiv”
A No-Free-Lunch Theorem for MultiTask Learning (2020, methodology): “…latent substructures, both as applied to classiﬁcation (Muandet, Balduzzi and Schölkopf, 2013; McNamara and Balcan, 2017; Arora et al., 2019), or to regression settings (Jalali et al., 2010; Lounici et al., 2011; Negahban and Wainwright, 2011; Du et al., 2020; Tripuraneni, Jordan and Jin, 2020).”
Tight conditions for consistency of variable selection in the context of high dimensionality (2011, background): “This proof can be found in Mazo and Odlyzko (1990), we repeat here the arguments therein for the sake of keeping the paper self-contained.”
Weakly decomposable regularization penalties and structured sparsity (2012, methodology): “1 then gives similar (but sharp) oracle results as those in Lounici et al. [2011] or Bühlmann and van de Geer [2011].”
Sparse coding for multitask and transfer learning (2012, methodology): “(Jenatton et al., 2011; Lounici et al., 2011) or other families of regularizers.”
Group Regularized Estimation Under Structural Hierarchy (2014, methodology): “It is widely acknowledged that the penalty parameter for a grouped `1 penalty should be adjusted by the group size (Yuan and Lin, 2006; Lounici et al., 2011; Wei and Huang, 2010).”
Group Lasso for high dimensional sparse quantile regression models (2011, methodology): “Bach (2008), Nardi and Rinardo (2008), Huang and Zhang (2010), Wei and Zhang (2010), Obozinski et al. (2010) Lounici et al. (2010) studied the statistical properties of the group Lasso estimator for linear regression models.”
Group Lasso with Overlaps: the Latent Group Lasso approach (2011, background): “The work of several authors shows that when the support can be encoded well by the groups defining the norm, support recovery and estimation are improved (Huang and Zhang, 2010; Kolar et al., 2011; Lounici et al., 2010, 2009; Negahban and Wainwright, 2011; Obozinski et al., 2010).”
Efficient multi-task feature learning with calibration (2014, positive): “Moreover, theoretical analysis in Lounici et al. [26] shows that, to achieve the optimal parameter estimation error bounds, the regularized parameter should be chosen in proportion to the maximum standard deviations of the noise for all tasks.”