A Comparative Framework for Preconditioned Lasso Algorithms
The Lasso is a cornerstone of modern multivariate data analysis, yet its performance suffers in the common situation in which covariates are correlated. This limitation has led to a growing number of Preconditioned Lasso algorithms that pre-multiply X and y by matrices P X , P y prior to running the standard Lasso. A direct comparison of these and similar Lasso-style algorithms to the original Lasso is difficult because the performance of all of these methods depends critically on an auxiliary penalty parameter λ. In this paper we propose an agnostic framework for comparing Preconditioned Lasso algorithms to the Lasso without having to choose λ. We apply our framework to three Preconditioned Lasso instances and highlight cases when they will outperform the Lasso. Additionally, our theory reveals fragilities of these algorithms to which we provide partial solutions.
The paper addresses preconditioned lasso estimators, 
      and studies their utility from a non-asymptotic, theoretical framework. 
      Their main result is a set of bounds (lower and upper) on lambda that are 
      necessary and sufficient for exact support recovery---they then apply this 
      result to study the effects of different preconditioning methods. I like 
      the general perspective of the paper (though I think the authors could 
      have given a better motivation for their approach). The work is generally 
      well-written, and as far as I can tell, novel. I do have two major 
      comments, given below. After that, I give several more minor comments. 
      ========== Major comments: - Lemma 1 seems like a 
      novel and interesting result. But at the same time, I'm suspicious of the 
      "if and only if" here. For this result to be true, it would need to hold 
      that \lambda_l and \lambda_u, as you've defined them, are knots of the 
      lasso solution path. From the LARS algorithm (homotopy algorithm) for the 
      lasso path, we know that the signed support of the lasso solution is 
      piecewise constant, and only changes at data-dependent knots \lambda_1 
      \geq \lambda_2 \geq \ldots \lambda_r. Hence it either \lambda_l or 
      \lambda_u did not coincidence with one of these knots, then we could slide 
      it to the closest knot (slide to the left for \lambda_l, and to the right 
      for \lambda_u), and we would know that the constructed support wouldn't 
      have changed. Generally, the formulae for these knots, \lambda_1 
      \geq \lambda_2 \geq \ldots \geq \lambda_r, are complicated since they 
      depend on the constructed support \hat{S} and signs of the lasso solution 
      along the lasso solution path. You've written down formulae for \lambda_l 
      and \lambda_u that depend on S, not \hat{S}, so at a high level, I don't 
      understand how this can be right. But at a lower level, skimming 
      through the proof of your Lemma 1 in the supplementary material, I don't 
      see any mistakes. Some comments/clarification on my concerns here would be 
      very helpful. UPDATE: I now believe that this result is correct. 
      Given the assumed conditions, we have \hat{S}=S (perfect recovery) so my 
      initial intuitive concerns are remedied. Furthermore, what you have 
      written down are actually knots in the lasso path, i.e., these can be 
      shown to coincide with "hitting times", the values of lambda at which 
      variables enter the model. - Section 3.2: It seems that the ratios 
      of the upper and lower lambda bounds, to compare the usual and 
      preconditioned lasso estimates, is not the right metric---instead you 
      would want to compare their relative widths: ( \lambda_u - \lambda_l ) / 
      \lambda_max, where \lambda_max is the smallest value of \lambda for which 
      all components of the estimate are zero. This has a closed form: 
      \lambda_max = \|X^T y\|_\infty, i.e., the largest absolute component of 
      X^T y. Clearly \lambda_max is going to be different between the two 
      problems (as X becomes P_X X and y becomes P_y y for the preconditioned 
      lasso). A simple example shows that using the ratios can give 
      somewhat undesirable answers: if \lambda_u = 4 and \lambda_l = 2 for the 
      lasso, and \lambda_u = 2 and \lambda_l = 1 for the preconditioned lasso, 
      then your metric would say they perform about the same. But if in this 
      case \lambda_max = 10 for the lasso and \lambda_max = 3 for the 
      preconditioned lasso, then the story is very different: with respect to 
      the full range of effective regularization parameter values, only 1/5 of 
      this range recovers the support for the lasso, and 1/3 of it recovers the 
      support for the preconditioned lasso. ========== Minor 
      comments: - Page 1, line 53: I think you mean sufficient (not 
      necessary) for support recovery - Page 2, line 80: I'm not really 
      sure what you mean by "asymptotic analyses ... provide limited theoretical 
      insight". Of course, an asymptotic analysis is entirely theoretical, and 
      so yes, it does provide such insight. You mean something like satisfactory 
      insight? - In motivating your approach on page 2, it seems to me like 
      your method is actually closely aligned with comparing the entire 
      regularization paths of (2) and (4), as done empirically in the reference 
      [4]. You are basically answering the question: "does the regularization 
      path contain the true model, at any point along the path?" But you are 
      doing this in an efficient way by deriving upper and lower bounds on 
      lambda. - Page 3, line 119: It seems strange to take the q 
      *smallest* singular vectors of U (by this, I assume you mean the singular 
      vector corresponding to the smallest singular values). Can you comment on 
      this? This is especially relevant in Theorem 1, where you impose the 
      condition span(U_S) \subseteq span(U_A). With this construction of A, we 
      would probably not at all expect the sets S and A to be close, so this 
      condition seems quite unreasonable ... - I'm not sure why you 
      don't present the deterministic result for JR (only one based on a 
      generative model)? For completeness in comparing the preconditioning 
      methods, this would have been helpful. - Equation (21) is 
      confusing: I think I know what you mean here, but this equation is 
      somewhat confusing without seeing context for \hat{\Sigma} (just calling 
      \hat{\Sigma} "unconstrained spectra" is not that informative) ... 
      - I'm confused about the setup in 5.3. Why have you changed the 
      number of observations to m, and what does it mean for m \rightarrow 
      \infty while n stays fixed?