6
$\begingroup$

I am interested in the following constrained parameter estimation in linear regression, $$ \min_\beta\sum_{i=1}^{n}(y_i-x_i\beta)^2 + \lambda \sum_{j}^{p}f(\beta_j) $$ where the model is $y=x\beta+e$, $e_i\sim i.i.d. N(0,\sigma^2)$ and $f$ is a penalty function. As it is obvious from the minimization problem, $f(\beta)=|\beta|$ leads to lasso problem that there are some well-developed algorithm for it, e.g. LARS. I remember in a conference a person talked about using lars for general form of $f$. So my question is about the most efficient algorithm that I can implement (hopefully in R) to get the solution path of the minimization problem.

$\endgroup$
  • 2
    $\begingroup$ Do you have a specific function, $f(\beta)$ in mind? If someone in a conference talked about using lars for general form of $f$, there was probably some limitation in mind as to how general the form of $f$ was. $\endgroup$ – Mark L. Stone Jul 13 '16 at 15:29
  • $\begingroup$ This is exactly what I was thinking about. I asked the person and he said any constraint! He was a member of RSS and the conference was running by RSS. $\endgroup$ – TPArrow Jul 13 '16 at 15:32
  • $\begingroup$ Hmm, Royal Statistical Society, not Mathematical Optimization Society - not all statisticians really understand optimization In any event, I was not there, and don't know what was said, or in what implicit or explicit context. So what $f$ do you want to use? Is there some reason you want to use something other than LASSO? $\endgroup$ – Mark L. Stone Jul 13 '16 at 15:39
  • $\begingroup$ I want to test different functions to see the behaviour of different penalties on estimations. At the meantime, I use optim function in R that is slow and time-consuming. $\endgroup$ – TPArrow Jul 13 '16 at 15:42
  • 1
    $\begingroup$ Perhaps you should list the various penalties you are investigating. $\endgroup$ – Mark L. Stone Jul 13 '16 at 15:46
7
$\begingroup$

The so-called local linear approximation (LLA) algorithm described in One-step sparse estimates in nonconcave penalized likelihood models by Zou and Li solves the optimization problem for certain concave choices of $f$. Specifically, for $$f(s) = p(|s|)$$ and a concave function $p : [0,\infty) \to [0,\infty)$, which is differentiable on $(0,\infty)$.

The algorithm works by iteratively solving a weighted $\ell_1$-penalized optimization problem. In iteration $k+1$ the solution is given as $$\arg \min \sum_{i=1}^n (y_i - x_i^T \beta)^2 + \lambda \sum_{j=1}^p p'(|\beta_j^{(k)}|) |\beta_j|.$$ Each iteration can be solved using e.g. glmnet or lars in R or another standard implementation that computes the lasso solution and allows for weights.

The algorithm is an MM-algorithm (it can actually in some cases be interpreted as an EM-algorithm), and it is shown in the paper that it has the descent property. Precise convergence results are given.

The paper does, by the way, advocate a one-step estimator, where only one step of the algorithm is taken from the OLS solution. This is computationally cheaper but statistically as efficient as running the algorithm until convergence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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