When is logistic regression solved in closed form?

Question

Take $x \in \{0,1\}^d$ and $y \in \{0,1\}$ and suppose we model the task of predicting y given x using logistic regression. When can logistic regression coefficients be written in closed form?

One example is when we use a saturated model.

That is, define $P(y|x) \propto \exp(\sum_i w_i f_i(x_i))$, where $i$ indexes sets in the power-set of $\{x_1,\ldots,x_d\}$, and $f_i$ returns 1 if all variables in the $i$'th set are 1, and 0 otherwise. Then you can express each $w_i$ in this logistic regression model as a logarithm of a rational function of statistics of the data.

Are there other interesting examples when closed form exists?

Answer 1

As kjetil b halvorsen pointed out, it is, in its own way, a miracle that the linear regresion admits an analytical solution. And this is so only by virtue of linearity of the problem (with respect to the parameters). In OLS, you have $$ \sum_i (y_i - x_i' \beta)^2 \to \min_\beta, $$ which has the first order conditions $$ -2 \sum_i (y_i - x_i'\beta) x_i = 0 $$ For a problem with $p$ variables (including constant, if needed -- there are some regression through the origin problems, too), this is a system with $p$ equations and $p$ unknowns. Most importantly, it is a linear system, so you can find a solution using the standard linear algebra theory and practice. This system will have a solution with probability 1 unless you have perfectly collinear variables.

Now, with logistic regression, things aren't that easy anymore. Writing down the log-likelihood function, $$ l(y;x,\beta) = \sum_i y_i \ln p_i + (1-y_i) \ln(1-p_i), \quad p_i = (1+\exp(-\theta_i))^{-1}, \quad \theta_i = x_i' \beta, $$ and taking its derivative to find the MLE, we get $$ \frac{\partial l}{\partial \beta'} = \sum_i \frac{{\rm d}p_i}{{\rm d}\theta}\Bigl( \frac{y_i}{p_i} - \frac{1-y_i}{1-p_i} \Bigr)x_i = \sum_i \Bigl[y_i-\frac1{1+\exp(x_i'\beta)}\Bigr]x_i $$ The parameters $\beta$ enter this in a very nonlinear way: for each $i$, there's a nonlinear function, and they are added together. There is no analytical solution (except probably in a trivial situation with two observations, or something like that), and you have to use nonlinear optimization methods to find the estimates $\hat\beta$.

A somewhat deeper look into the problem (taking the second derivative) reveals that this is a convex optimization problem of finding a maximum of a concave function (a glorified multivariate parabola), so either one exists, and any reasonable algorithm should be finding it rather quickly, or things blow off to infinity. The latter does happen to logistic regression when ${\rm Prob}[Y_i=1|x_i'\beta > c] = 1$ for some $c$, i.e., you have a perfect prediction. This is a rather unpleasant artifact: you would think that when you have a perfect prediction, the model works perfectly, but curiously enough, it is the other way round.

Answer 2

This post was originally intended as a long comment rather than a complete answer to the question at hand.

From the question, it's a little unclear if the interest lies only in the binary case or, perhaps, in more general cases where they may be continuous or take on other discrete values.

One example that doesn't quite answer the question, but is related, and which I like, deals with item-preference rankings obtained via paired comparisons. The Bradley–Terry model can be expressed as a logistic regression where $$ \mathrm{logit}( \Pr(Y_{ij} = 1) ) = \alpha_i - \alpha_j , $$ and $\alpha_i$ is an "affinity", "popularity", or "strength" parameter of item $i$ with $Y_{ij} = 1$ indicating item $i$ was preferred over item $j$ in a paired comparison.

If a full round-robin of comparisons is performed (i.e., a pairwise preference is recorded for each unordered $(i,j)$ pair), then it turns out that the rank order of the MLEs $\hat{\alpha}_i$ correspond to the rank order of $S_i = \sum_{j \neq i} Y_{ij}$, the sum total of times each object was preferred over another.

To interpret this, imagine a full round-robin tournament in your favorite competitive sport. Then, this result says that the Bradley–Terry model ranks the players/teams according to their winning percentage. Whether this is an encouraging or disappointing result depends on your point of view, I suppose.

NB This rank-ordering result does not hold, in general, when a full round-robin is not played.