5
$\begingroup$

I am not sure how is $\ell_q$-LASSO called, but here I am talking about LASSO regression, with $\| \beta \|_{\ell_q}$ regularization, $q< 1$. In popular literature, such as Elements of Statistical Learning or Statistical Learning with Sparsity by Hastie et. al., I am able to find only their rough definitions with some graphs, and comments about how their non-convexity makes estimating it troublesome and computationally inefficient.

However, I am interested in a deeper discussion of the approach, such as its Oracle Properties, asymptotic behaviour regarding variable selection and parameter estimation, and various cases when the method doesn't work. So far I've tested simple cases by hand in Monte Carlo experiments and find that it is able to outperform $\ell_1$ LASSO in various cases by a significant margin, hence I assume there should be strong properties at work there. That is, I'd like to understand why it works well for me.

My questions:

  1. Does this method have an official name for easier literature search?

  2. If you have any links to papers with proved properties, they would be very useful for further read.

  3. I am also very interested in counterexamples, that would be able to break the method. (Can't construct them by myself, as I wasn't able to find assumptions, under which, say, $\ell_q$-lasso would guarantee consistent variable selection). For example, with $\ell_1$-lasso, it is known that significant multicorrelation can easily break consistent variable selection. At the same time, I find $\ell_q$-lasso being able to deal with same examples without problems.

Note: I've mentioned variable selection in the questions only as an example, other properties are also of interest.

$\endgroup$
  • 1
    $\begingroup$ This framework with an $L_q$ penalty is sometimes called Bridge regression. $\endgroup$ – knrumsey Feb 8 at 0:39
  • 1
    $\begingroup$ @knrumsey thanks. While most papers seem to deal with $q > 1$, this is very useful! $\endgroup$ – Nutle Feb 8 at 10:28
  • 1
    $\begingroup$ One of the main difficulties with bridge penalties where $q<1$ is that they're nonconvex, so the optimization problem is harder to solve. But, some approximation schemes have been proposed. For example, see Park and Yoon (2011). Bridge regression: adaptivity and group selection. Their intro also gives a good overview of existing work on bridge regression. This thread might be of peripheral interest (comparing bridge regression to elastic net for $q>1$). $\endgroup$ – user20160 Feb 9 at 21:57
4
$\begingroup$

Frank & Friedman (1993) suggested the idea of bridge estimates, with penalty function $P_B=\lambda\sum_j|\alpha_j|^\gamma$, as a paradigm for understanding subset selection and ridge regression. The $\ell_0$-norm corresponds to subset selection methods, $\ell_1$ is the LASSO, and $\ell_2$ is ridge regression. They noted that it would be beneficial to estimate the parameters $\lambda$ and $\gamma$ simultaneously to widen the choice of possible models but did not develop the method any further. The $\lambda$ parameter controls the size of estimates ($\hat\alpha_j^B$) or the amount of shrinkage, while the $\gamma$ parameter determines the directions in which the parameters are aligned with respect to the coordinate axes.

When $\gamma\in(0,1)$:

  • The penalty function $P_B=\lambda\sum_j|\alpha_j|^\gamma$ is concave. The figure below shows the concave penalty functions (dotted) in comparison with the LASSO penalty function (solid). Penalty function

  • Some parameters are set to zero and the shrinkage is inversely proportional to the size of the parameters. The figure shows the thresholding function $\hat\alpha_j - sign(\hat\alpha_j)\lambda\gamma|\hat\alpha_j|^{\gamma-1}$, where $\hat\alpha_j$ are the OLS estimates. Here, with $\lambda=4$ and $\gamma=0.25$ or $\gamma=0.5$, large parameters remain fairly untouched by the shrinkage. With the LASSO (solid line), the shrinkage is constant. Thresholding function

  • Estimates are likely to occur on the axes. The figure shows norm balls in $\mathbb{R}^2$ (left) and $\mathbb{R}^3$ (right) for $\gamma=0.5$. Norm balls

Please see pages 118-119 and 126-127 of Kirkland (2014) for a comparison of these figures with other values of $\gamma$. This masters thesis also provides an overview of other shrinkage methods.

Knight & Fu (2000) showed that bridge estimates are consistent and have asymptotic normal distributions.

The main idea behind the concave penalty functions is that large parameters are penalized less so that the resulting estimates are nearly unbiased. I know of 2 other shrinkage methods which make use of concave penalties and may be of interest to you:

  • Fan & Li (2001) proposed SCAD, which was the first shrinkage method having the oracle property. Although the adaptive LASSO is oracle, the bias may decrease at a faster rate with SCAD.

  • Zhang (2010) proposed MCP, which follows a similar approach to SCAD but penalizes smaller parameters less.

Despite having concave penalties which are also non-differentiable at zero, they both provide efficient algorithms for computing the solution, even in high dimensional settings when $p\geq n$.

$\endgroup$
  • $\begingroup$ Thanks, excellent summary! I'll go through the literature for deeper discussion and examples, before accepting. Just a quick question - are there known cases when L1 lasso beats Bridge regression on simulation exercises? I'd imagine this might be the case with large estimates, as you say? $\endgroup$ – Nutle Feb 8 at 18:35
  • $\begingroup$ (+1) Really nice answer. Regularization with The Horseshoe prior (Polson, Scott, Carvahlo) also makes use of concave penalties and is a really nice method for a large class of problems. $\endgroup$ – knrumsey Feb 8 at 19:43
  • $\begingroup$ @Nutle From my simulation studies (see p168-179 of Kirkland (2014)), MCP and SCAD using CV perform better in terms of selection and estimation consistency regardless of the correlation structure. However, LASSO has lower MSE and similar probability of selecting the correct subset (although a very low 0.15) than MCP and SCAD when the sample size is small, the number of nonzero coefficients is sparse, the size of nonzero coefficients are not large and the correlation structure satisfies the compatibility condition, the restricted eigenvalue condition and the irrepresentable condition. $\endgroup$ – StatGrrl Feb 10 at 10:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.