Logistic Regression is a popular and effective technique for modeling categorical outcomes as a function of both continuous and categorical variables. The question is: how robust is it? Or: how robust are the common implementations? (note: we are using robust in a more standard English sense of performs well for all inputs, not in the technical statistical sense of immune to deviations from assumptions or outliers.)

Even a detailed reference such as “Categorical Data Analysis” (Alan Agresti, Wiley, 1990) leaves off with an empirical observation: “the convergence … for the Newton-Raphson method is usually fast” (chapter 4, section 4.7.3, page 117). This is a book that if there is a known proof that the estimation step is a contraction (one very strong guarantee of convergence) you would expect to see the proof reproduced. I always suspected there was some kind of Brouwer fixed-point theorem based folk-theorem proving absolute convergence of the Newton-Raphson method in for the special case of logistic regression. This can not be the case as the Newton-Raphson method can diverge even on trivial full-rank well-posed logistic regression problems.From a theoretical point of view the logistic generalized linear model is an easy problem to solve. The quantity being optimized (deviance or perplexity) is log-concave. This in turn implies there is a unique global maximum and no local maxima to get trapped in. Gradients always suggest improving directions. However, the standard methods of solving the logistic generalized linear model are the Newton-Raphson method or the closely related iteratively reweighted least squares method. And these methods, while typically very fast, do not guarantee convergence in all conditions.

If you do not like Newton-Raphson techniques, many other optimization techniques can be used:

• stochastic gradient descent
• conjugate gradient
• EM (see “Direct calculation of the information matrix via the EM.” D Oakes, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 1999 vol. 61 (2) pp. 479-482).

Or you can try to solve a different, but related, problem: “Exact logistic regression: theory and examples”, C R CR Mehta and N R NR Patel, Statist Med, 1995 vol. 14 (19) pp. 2143-2160.

A dominating problem with logistic regression comes from a feature of training data: subsets of outcomes that are separated or quasi-separated by subsets of the variables (see, for example: “Handling Quasi-Nonconvergence in Logistic Regression: Technical Details and an Applied Example”, J M Miller and M D Miller; “Iteratively reweighted least squares for maximum likelihood estimation, and some robust and resistant alternatives”, P J Green, Journal of the Royal Statistical Society, Series B (Methodological), 1984 pp. 149-192; and FAQ What is complete or quasi-complete separation in logistic/probit regression and how do we deal with them?). Most practitioners will encounter this situation and the correct fix is some form of regularization or shrinkage (not eliminating separating variables- as they tend to be the most influential ones). In fact most practitioners have the intuition that these are the only convergence issues in standard logistic regression or generalized linear model packages. This is not the case.

The Newton-Raphson/Iteratively-Reweighted-Least-Squares solvers can fail for reasons of their own, independent of separation or quasi-separation. Consider the responses to the following request for help: Whassup with glm()?. Professor Andrew Gelman asks why the following R code diverges:
y <- rep (c(1,0),c(10,5)) glm (y ~ 1, family=binomial(link="logit"), start=5)

Clearly some of the respondents are thinking in terms of separation and numeric overflow. But the problem was to merely compute an average (the data as a function only of the constant 1!) and the start point of 5 is so small a number that even exp(5) will not trigger over-flow or under-flow. What went wrong is: the Newton-Raphson style solver merely, for reasons of its own, refused to work. 5 is a numerically fine start estimate- but it is outside of the Newton-Raphson convergence region. This is a surprise to many practitioners- but Newton-Raphson style methods are only guaranteed to converge if you start sufficiently close to the correct answer. It is likely the case that for most logistic regression models the typical start (all coefficients zero: yielding a prediction of 1/2 for all data) is close enough to the correct solution to converge. But without additional theorems and lemmas there is no reason to suppose this is always the case.

The “Whassup” example demonstrates the problem is present in R‘s standard optimizer (confirmed in version 2.15.0). The take-away is to be very suspicious if you see any of the following messages in R:

• “glm.fit: fitted probabilities numerically 0 or 1 occurred”
• any “failed to converge” message
• astronomical coeffcients
• residual deviance larger than null deviance.

In any of these cases model fitting has at least partially failed and you need to take measures (such as regularized fitting).

R’s optimizer likely has a few helping heuristics, so let us examine a trivial Newton-Raphson method (always takes the full Newton-Raphson step, with no line-search or other fall-back techniques) applied to another problem. In this case (to make prettier graphs) we will consider fitting y as a function of the constant 1 and a single variable x. Our data is given by the following four rows:

The unique optimal model is to admit y is independent of x and set all coefficients to zero (R solves this correctly when given the command: glm(y~x,data=p,family=binomial(link='logit'))). This model has a residual deviance of 5.5452 (which is also the null deviance). The following figure plots the perplexity (the un-scaled deviance) of different models as a function of choice of wC (the constant coefficeint) and wX (the coefficient associated with x):

The minimal perplexity is at the origin (the encoding of the optimal model) and perplexity grows as we move away from the origin (yielding the ovular isolines).

For our next figure we plot the behavior of a single full step of a Newton-Raphson method (generated by a deliberately trivial implementation of The Simpler Derivation of Logistic Regression). For each point in the plane we initialize the model with the coefficients represented by the point (wC and wX) and then take a single Newton-Raphson step. Plotting the single step behavior lets us draw some conclusions about the iterated optimizer without getting deep into the theory of iterated systems. If the step does not increase the perplexity (as we would expect during good model fitting) we color the point red, otherwise we color the point blue. The intuition is that most of the blue points represent starts that would cause the fitter to diverge (they increase perplexity and likely move to chains of points that also have this property).

Divergence is easy to show for any point that lies outside of an isoline of the first graph where this isoline is itself completely outside of the red region of the second graph. These points show an increase in perplexity (as they are outside of the red region) and thus stay outside of their original perplexity isoline (and remain outside of the red region) and therefore will never decrease their perplexity no matter how many Newton-Raphson steps you apply.

So, the acceptable optimization starts are only in and near the red region of the second graph. Starts far outside of this region are guaranteed to not converge to the unique optimal point under Newton-Raphson steps. R confirms the problem with the following bad start: glm(y~x,data=p,family=binomial(link='logit'),start=c(-4,6)). Sufficiently sophisticated code can fallback to gradient-alone methods when Newton-Raphson’s method fails. The problem is fixable, because optimizing logistic divergence or perplexity is a very nice optimization problem (log-concave). But most common statistical packages do not invest effort in this situation.

And most practitioners are unfamiliar with this situation because:

1. They rightly do not concern themselves with the implementation details, as these are best left to the software implementors.
2. They are very likely to encounter issues arise from separation, which will mask other issues.

The good news is that Newton-Raphson failures are not silent. You will see a large residual deviance and many of the other diagnostics we called out. The fix for a Newton-Raphson failure is to either use a more robust optimizer or guess a starting point in the converging region. This is not hopeless as coefficients from other models such as linear regression and naive Bayes are likely useable. Also one can group variables and levels to solve simpler models and then use these solutions to build better optimization starting points.

Some comfort can be taken in that: the reason statistical packages can excuse not completely solving the optimization problem is: Newton-Raphson failures are rare in practice (though possible). It would be nice if all packages included robust fallback code (such as not accepting Newton-Raphson steps that degrade solution quality and switching to gradient alone methods in this case) but that is not the current state of the market.

Really what we have done here (and in What does a generalized linear model do?) is treat statistical modeling as a college math exercise. What we have done and what we recommend: is try trivial cases and see if you can simplify the published general math to solve the trivial case directly. Usually nobody fully understands the general case (beyond knowing the methods and the proofs of correctness) and any real understanding is going to come from familiarity from working basic exercises and examples. Instead of appealing to big hammer theorems- work some small examples.

Extra credit: find a simple non-separated logistic regression that diverges on the first Newton-Raphson step from the origin, or failing that a proof that no such problem exists. We don’t have such an example (though suspect there is a divergent example) and have some messy Java code for experimenting with single Newton-Raphson steps: ScoreStep.java.

Related posts:

1. The equivalence of logistic regression and maximum entropy models
2. Learn Logistic Regression (and beyond)
3. The Simpler Derivation of Logistic Regression