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$
7
  • $\begingroup$ Have you looked here? (A link to this paper is provided in the glmnet documentation.) $\endgroup$
    – cardinal
    Commented Oct 18, 2011 at 19:33
  • $\begingroup$ That's the same paper ;) $\endgroup$
    – Scott
    Commented Oct 18, 2011 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
    Commented Oct 18, 2011 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
    Commented Oct 18, 2011 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
    Commented Oct 18, 2011 at 21:02

2 Answers 2

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$
5
  • $\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
    Commented Oct 18, 2011 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
    Commented Oct 18, 2011 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
    Commented Oct 19, 2011 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
    Commented Mar 27, 2015 at 16:01
  • $\begingroup$ A good question is if in (16) for $z_i$, whether yhats (probability for each record) $p(x_i)$ are calculated without $\beta_j$ being used in the linear predictor $x^\top\beta$ the way $y^{(j)}_i$ does. I don't think they are since $z_i$ is supposed to represent the full $y_i$ from the data. However, $y^{(j)}_i$ is essentially $p(x_i)$ determined by skipping the jth coefficient in $x^\top\beta$ $\endgroup$
    – user291323
    Commented Aug 7, 2020 at 21:42
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$
2
  • $\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
    Commented Oct 18, 2011 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
    Commented Oct 18, 2011 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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