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.
$\begingroup$
$\endgroup$
6
-
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. StoneJul 13, 2016 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$– TPArrowJul 13, 2016 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. StoneJul 13, 2016 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$– TPArrowJul 13, 2016 at 15:42
-
1$\begingroup$ Perhaps you should list the various penalties you are investigating. $\endgroup$– Mark L. StoneJul 13, 2016 at 15:46
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.
