3
$\begingroup$

I'm looking to implement a coordinate descent solution to the Elastic Net (Friedman et al, 'Regularization paths for generalized linear models via coordinate descent') for logistic regression. The paper explicitly gives the coordinate update for the linear case, but I'm having difficulty understanding the solution for binomial Y.

Is there any literature/has anyone implemented coordinate descent for the logistic case? That is, outside their (unparseable to me) Fortran code?

Thanks

$\endgroup$
  • $\begingroup$ Have you looked here? (A link to this paper is provided in the glmnet documentation.) $\endgroup$ – cardinal Oct 18 '11 at 19:33
  • $\begingroup$ That's the same paper ;) $\endgroup$ – Scott Oct 18 '11 at 19:40
  • $\begingroup$ Ha! My eyes skimmed right over your reference, maybe because it was parenthetical. Apologies. :) Perhaps having the direct link will be useful, anyways. $\endgroup$ – cardinal Oct 18 '11 at 19:46
  • 1
    $\begingroup$ @Scott, could you be more explicit about exactly what the problem is? To me the cited paper is quite explicit in Section 3 on the algorithm for logistic regression. Maybe you just missed the point that it is not a simple coordinate descent update of the penalized minus-log-likelihood, but instead an outer iteration where $\ell$ is replaced by a quadratic approximation, and an inner iteration using the updates in formula (10). Does this help, or is there something else in Section 3 that is problematic? $\endgroup$ – NRH Oct 18 '11 at 20:42
  • 1
    $\begingroup$ @NRH: I understand how to form the quadratic approximation, but it is unclear to me how to take formula 10 and update it given z and w in formulas 16 and 17. Do I just replace $y_i$ with $z_i$? Is $y~_i^{(j)}$ formed in the same way as the linear case, or do I (re)compute $z~_i^{(j)}$ by zeroing $\beta_j$ and recalculating z? I am also confused by the comment just below formula 10: 'If the $x_j$ are not standardized, there is a similar sum-of-squares term in the denominator (even without weights).' [My X, in practice, are huge sparse matrices that I cannot standardize]. $\endgroup$ – Scott Oct 18 '11 at 21:02
2
$\begingroup$

This is an answer to the specific questions regarding the cited paper that the OP gave in a comment. This is on the details of the algorithm described in Section 3 in the paper.

For logistic regression the working response, called $z_i$ in the paper, works as the response, that is, as $y_i$, when using the quadratic approximation. So one just replaces $y_i$ by $z_i$ in the update formula (10) and proceeds as in a weighted least squares regression problem. In particular, one forms $y_i^{(j)}$ as in the linear case.

To understand the comment after formula (10), try to derive (5) from (4) and see how the assumed standardization yields the "1" in the denominator. The comment refers to the fact that in the general weighted case the weights enter in the numerator, and the "1" in the denominator in (5) has to be replaced by a weighted sum-of-squares. This sum-of-squares is actually always present, even without weights, but if one standardizes upfront (as they do it in the paper) and the weights are $1/N$, then the sum-of-squares equals 1.

Regarding that standardization for sparse $x$-values, the scaling does not alter the sparsity structure, and can be done upfront, but the centering does and has to be done "on the fly" to preserve sparsity, see also Section 2.3. The most obvious way to me is to precompute the column means and then in (9) include the centering explicitly. Then use the bilinearity of the inner products $\langle \cdot, \cdot \rangle$ in this covariance update to rewrite the update in terms of the uncentered $x$-variables and constants $N \bar{x}_j \bar{x_i}$ and $N \bar{x}_j \bar{y}$ where e.g. $\bar{x}_j$ is the mean of $x_j$. This should be doable without really affecting the efficiency of the algorithm for the unweighted least squares problem.

Note, however, that the centering is primarily a trick for the unweighted least squares problem to get rid of the intercept parameter, and it does not affect the values of the other parameters, only the computation, whereas the scaling does affect the whole solution. For logistic regression the centering does not remove the need for an intercept, and even if you center the $x$-variables upfront by the column mean, the intercept parameter will not disappear when computing a general weighted least squares solution. Hence, it is less clear that there is any reason to center, and in Section 3 the intercept parameter is also explicitly present in the formulas. The scaling is generally recommended as a default, but this can be done without the centering and one can, as mentioned above, scale the sparse matrix without changing the sparsity structure.

As a final remark, the naive updates are recommended over the covariance updates for the weighted regression updates because the weights constantly change, and the benefit of the covariance updates disappears.

$\endgroup$
  • $\begingroup$ Yes, the paper says you can center X in 'an obvious manner' - but it escapes me how to do this on the fly. Here is my final equation: $\endgroup$ – Scott Oct 18 '11 at 23:24
  • $\begingroup$ Please disregard above comment. I meant to say: Thanks, this helps... So keeping the sum of squares in the denominator means I don't have to scale X? And can you please elaborate on how to center on the fly? I know the paper says this can be done in 'an obvious manner', but it is not so obvious to me :). $\endgroup$ – Scott Oct 18 '11 at 23:34
  • $\begingroup$ @Scott, I have tried to give more details, but at the end of the day, for logistic regression, I see no need to center. $\endgroup$ – NRH Oct 19 '11 at 9:45
  • $\begingroup$ @NRH - Thanks for posting this response! I've had similar problems interpreting this paper. When you stated: "In particular, one forms $y^{(j)}_i$ as in the linear case", I'm assuming you mean recompute $z_i$ (Equation 16 in the paper) but exclude the $x_{ij}\beta_j$ term (including the $x_{ij}\beta_j$ term in the $p(x_i)$ formula). $\endgroup$ – RobertF Mar 27 '15 at 16:01
0
$\begingroup$

If you're looking for a solution, check out the glmnet package, which was written by the authors of that paper. It contains an implementation for logistic regression.

Even if you're looking to implement your own solution, it might be a good idea to look at their code, specifically the lognet R function and the lognet FORTRAN function.

$\endgroup$
  • $\begingroup$ Yes, I'm trying to look through lognet - but having no Fortran experience, I'm finding it very difficult to wade through. I'm hoping someone can post an equation to help clarify. $\endgroup$ – Scott Oct 18 '11 at 19:07
  • $\begingroup$ @Scott maybe make a post on stackoverflow along the lines of: who can help me parse this block of fortran code into a mathematical formula? $\endgroup$ – Zach Oct 18 '11 at 19:23

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.