We consider the problem of estimating a sparse linear regression vector β * 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 β * . We establish oracle inequalities for the prediction and ℓ 2 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 ≤ ∞. When p = ∞, this result implies that a threshold version of the Group Lasso estimator selects the sparsity pattern of β * 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 ℓ 2 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. An important application of our results is provided by the problem of estimating multiple regression equation simultaneously or multi-task learning. In this case, our results lead to refinements of the results in [22] and allow one to establish the quantitative advantage of the Group Lasso over the usual Lasso in the multi-task setting. Finally, within the same setting, we show how our results can be extended to more general noise distributions, of which we only require the fourth moment to be finite. To obtain this extension, we establish a new maximal moment inequality, which may be of independent interest. Over the past few years there has been a great deal of attention on the problem of estimating a sparse 1 regression vector β * from a set of linear measurements Here X is a given N × K design matrix and W is a zero mean random variable modeling the presence of noise. A main motivation behind sparse estimation comes from the observation that in several practical applications the number of variables K is much larger than the number N of observations, but the underlying model is known to be sparse, see [8, 12] and references therein. In this situation, the ordinary least squares estimator is not well-defined. A more appropriate estimation method is the ℓ 1 -norm penalized least squares method, which is commonly referred to as the Lasso. The statistical properties of this estimator are now well understood, see, e.g., [4, 6, 7, 18, 21, 36] and references therein. In particular, it is possible to obtain oracle inequalities on the estimation and prediction errors, which are meaningful even in the regime K ≫ N. In this paper, we study the above estimation problem under additional structural conditions on the sparsity pattern of the regression vector β * . Specifically, we assume that the set of variables can be partitioned into a number of groups, only few of which are relevant in the estimation process. In other words, not only we require that many components of the vector β * are zero, but also that many of a priori known subsets of components are all equal to zero. This structured sparsity assumption suggests us to consider the Group Lasso method [39] as a mean to estimate β * (see equation (2.2) below). It is based on regularization with a mixed (2, 1)-norm, namely the sum, over the set of groups, of the square norm of the regression coefficients restricted to each of the groups. This estimator has received significant recent attention, see [3, 10, 16, 17, 19, 24, 25, 26, 28, 31] and references therein. Our principal goal is to clarify the advantage of this more stringent group sparsity assumption in the estimation process over the usual sparsity assumption. For this purpose, we shall address the issues of bounding the prediction error, the estimation error as well as estimating the sparsity pattern. The main difference from most of the previous work is that we obtain not only the upper bounds but also the corresponding lower bounds and thus establish optimal rates of estimation and prediction under group sparsity. A main motivation for us to consider the group sparsity assumption is the practically important problem of simultaneous estimation the coefficient of multiple regression equations Here X 1 , . . . , X T are prescribed n × M design matrices, β * 1 , . . . , β * T ∈ R M are the unknown regression vectors which we wish to estimate, y 1 . . . , y T are n-dimensional vectors of observations and W 1 , . . . , W T are i.i.d. zero mean random noise vectors. Examples in which this estimation 1 The phrase "β * is sparse" means that most of the components of this vector are equal to zero. 1 problem is relevant range from multi-task learning [2, 23, 28] and conjoint analysis [14, 20] to longitudinal data analysis [11] as well as the analysis of panel data [15, 38] , among others. We briefly review these different settings in the course of the paper. In particular, multi-task learning provides a main motivation for our study. In that setting each regression equation corresponds to a different learning task; in addition to the requirement that M ≫ n, we also allow for the number of tasks T to be much larger than n. Following [2] we assume that there are only few common important variables which are shared by the tasks. That is, we assume that the vectors β * 1 , . . . , β * T are not only sparse but also have their sparsity patterns included in the same set of small cardinality. This group sparsity assumption induces a relationship between the responses and, as we shall see, can be used to improve estimation. The model (1.2) can be reformulated as a single regression problem of the form (1.1) by setting K = MT , N = nT , identifying the vector β by the concatenation of the vectors β 1 , . . . , β T and choosing X to be a block diagonal matrix, whose blocks are formed by the matrices X 1 , . . . , X T , in order. In this way the above sparsity assumption on the vectors β t translate in a group sparsity assumption on the vector β * , where each group is associated with one of the variables. That is, each group contains the same regression component across the different equations (1.2). Hence the results developed in this paper for the Group Lasso apply to the multi-task learning problem as a special case.
• Group sparsity: each row of the matrix is sparse and shares a common support, e.g., groupsparse regression REF .
Oracle Inequalities and Optimal Inference under Group Sparsity
Annals of Statistics 39(4): 2164-2204, 2011
Mathematics