Estimating LASSO Risk and Noise Level
We study the fundamental problems of variance and risk estimation in high dimensional statistical modeling. In particular, we consider the problem of learning a coefficient vector θ 0 ∈ R p from noisy linear observations y = Xθ 0 + w ∈ R n (p > n) and the popular estimation procedure of solving the 1 -penalized least squares objective known as the LASSO or Basis Pursuit DeNoising (BPDN). In this context, we develop new estimators for the 2 estimation risk θ − θ 0 2 and the variance of the noise when distributions of θ 0 and w are unknown. These can be used to select the regularization parameter optimally. We establish high-dimensional consistency of our estimators for sequences of matrices X of increasing dimensions, with independent Gaussian entries. We establish validity for a broader class of Gaussian designs, conditional on a certain conjecture from statistical physics.
To the best of our knowledge, this result is the first that provides an asymptotically consistent risk estimator for the LASSO solely based on data. In addition, we demonstrate through simulations that our variance estimation outperforms several existing methods in the literature.
(*) The paper proposes new estimators for: (i.) 
      the risk of a lasso estimator (ii.) the noise-level in the lasso 
      model. Both estimators are purely from the data. Under some 
      conditions, it is proven that these are consistent estimators of the 
      quantities when the dimension p and the number of measurements n go to 
      infinity. There are also a few experimental results showing the 
      accuracy of the proposed estimators on simulated examples. (*) 
      The paper provides important results for a fundamental problem of 
      estimating the lasso risk from data, and thus offers potentially a 
      significant contribution. An important practical implication is that the 
      estimator could be used to optimize the regularization parameter \lambda 
      of the LASSO. However, the writing of the paper is not clear enough 
      and often sloppy. This makes it hard to follow the paper, and verify 
      the correctness (and sometimes even the meaning) of the results, and 
      prevented me from assigning a higher score for the paper. It looks 
      like more effort should have been devoted to presentation. (*) 
      The computer experiments part is encouraging but limited and not well 
      explained. What is the distribution for the non-zero values of x_0? 
      how was each point in the plot obtained? from a single run of the lasso? 
      if so, why not average over multiple runs, to see also the standard 
      deviation of the estimation error and of the estimators the authors 
      provide? (*) Many things are not explained: - What are 
      'irrepresentability conditions' in the introduction? - How does one 
      initialize y and z in the AMP algorithm in eq. (3.1)? - I don't 
      understand what is the joint empirical distribution of {\hat{y}_i, x_0,i} 
      (first defined in line 270). x_0 is the signal, with coordinates for 
      i=1,..,p. But \hat{y} is the the data, with i=1,..,n. Why is the same i 
      used here? - In line 198 it is said : \eta_t' is the derivative ...'. 
      Derivative with respect to what? y^t? - What is D in proposition 3.2 
      (line 297)? - The authors provide a general estimator for a general 
      design matrix, in definition 3. But when should one use each estimator? is 
      it assumed that the inverse covariance matrix \Omega is known? or 
      should one estimate it from the data? - It is often not clear when the 
      authors write Expectations E[..], over what are these expectations taken. 
      For example in equations (3.2), (3.4), (3.5). Is it over the choice of 
      elements of the matrix A? of error variables Z? of the signal X? all of 
      these together? (*) The authors provide estimators for the error 
      for one specific estimator: the lasso. But could it be that other 
      estimators give better MSE for the case of sparse vectors? what would a 
      comparison of the MSE to minimax lower bounds yield? (e.g. E. J. 
      Candès and M. A. Davenport. How well can we estimate a sparse vector? 
      Applied and Computational Harmonic Analysis, 2011) (*) I have 
      a problem in interpreting the main results. In theorem (4.1), the authors 
      provide a consistency result for the estimator of the lasso risk, as 
      both the dimension p and the number of measurements n go together to 
      infinity (with their ratio being fixed). But, first, it looks like the 
      result is given for a fixed iteration t - yet one would expect the 
      number of iterations required for convergence to depend on n and p (and 
      the data). How do the results apply to the actual LASSO solution? 
      Second, from eq. (4.1) it looks like n and p approach infinity 
      independently, which is confusing. Finally, it seems to me that in 
      this limit, the lasso risk itself approaches some limit (i.e. some 
      constant. For example in [Wai09] it is shown that under certain 
      conditions the error goes to zero). If this is true, then what is the 
      utility of the author's estimator in this limit if the error can be anyway 
      calculated as a function of the distribution of A and the noise? 
      (*) There are many typos and inaccuracies, some of which 
      really hinder the reading and understanding: The last section in 
      the abstract ('We compare our variance ..') is unclear and confusing. 
      What are 'two naive LASSO estimator'? estimators of the error? also, 
      why 'On the other hand'? Page 1, line 43: 'p < n' should be 'p 
      > n'? Page 2, line 69: 'the the risk' -> 'the risk'. 
      Page 2, line 82: 'data y,A' -> 'data y and A'? Page 2, 
      line 100: 'underbraccdelta' ??? Page 3, line 132: 'SURE' is 
      written before it was introduced/defined. Page 3, line 153: 'for 
      each lambda' Page 3, line 155: \delta is first written here but 
      defined only later. Page 4, lines 192-196: many indices in eq. 
      (3.1) are wrong/missing (e.g. when is t used, when t+1,t-1? the iteration 
      looks circular). Also, shouldn't the 2nd line be z+Ax? Page 5, 
      line 260: 'provides' -> 'provide' Page 6, line 295: 'for' 
      should be removed. Would be also good to define 'weakly differentiable' 
      Page 9, line 473: Reference is messed up