Iteratively Reweighted Least Squares

The algorithm that fits every generalized linear model, derived and analyzed. The score, the expected information and the observed information of any generalized linear model are computed; a Fisher scoring step is proved to be a weighted least squares fit of a working response, with weights that are inverse variances of a linearized model; Newton's method is proved equal to scoring for canonical links and different otherwise; the local rate of convergence is derived as the spectral radius of a matrix and checked on NHANES diabetes data; and step halving is shown to rescue steps that lower the likelihood, with two real cases where unmodified Newton steps go wrong and a third where the algorithm stalls at a boundary. Worked problems on the first step for the Challenger flights in exact arithmetic, the normal linear model, the Poisson log-linear model and the gamma model with log link.

Every fit in Link Functions and the Structure of a Generalized Linear Model came from one routine: five binomial links on the six groups of this unit's NHANES adults, four more on all 5,107 of them. Logistic Regression fitted the 23 Challenger flights by Newton's method and remarked in passing that each step "can be rewritten as a weighted least-squares regression on an adjusted response". Nelder and Wedderburn (1972) made the remark the basis of a whole class of models; their abstract opens: "The technique of iterative weighted linear regression can be used to obtain maximum likelihood estimates of the parameters with observations distributed according to some exponential family". Why does a weighted least squares fit, repeated, maximize the likelihood of any such model, what are the weights, and when does the repetition fail?

Iteratively reweighted least squares (IRLS) is the following loop. From the current coefficients, compute a working response $z_i$ and a working weight $W_i$ for every observation; regress $\mathbf{z}$ on the inputs $X$ by weighted least squares with those weights; take the result as the new coefficients; repeat until they stop changing. This article derives the working response and weights from the likelihood, proves that each pass is a step of Fisher scoring, and therefore of Newton's method when the link is canonical, and studies how fast and how reliably the loop converges.

First we compute the score and the two information matrices of a generalized linear model with any link. Then we prove that a Fisher scoring step is a weighted least squares fit, and compare it with a Newton step. Next we run the algorithm on the six groups, derive its rate of convergence, and see the two standard errors that the two information matrices give. Finally we treat steps that go wrong, and step halving. The article assumes the model and notation of Link Functions and the Structure of a Generalized Linear Model, the exponential dispersion form of Exponential Families, and weighted least squares as the generalized least squares of The Gauss–Markov Theorem.

The score and the information of a generalized linear model

Write the model as in the link functions article: independent $Y_i$ with natural parameter $\theta_i$, mean $\mu_i = b'(\theta_i)$, variance $\phi V(\mu_i)/w_i$; linear predictor $\eta_i = o_i + \mathbf{x}_i^{\mathsf T}\boldsymbol\beta$; link $g(\mu_i) = \eta_i$. Two quantities appear in every formula below:

$$W_i = \frac{w_i}{V(\mu_i)\,g'(\mu_i)^2}, \qquad s_i = \frac{w_i}{V(\mu_i)\,g'(\mu_i)}.$$

Both are functions of $\eta_i$ through $\mu_i = g^{-1}(\eta_i)$. Let $W = \operatorname{diag}(W_1, \ldots, W_n)$ and $G = \operatorname{diag}(g'(\mu_1), \ldots, g'(\mu_n))$.

Theorem 1 (score and information). The log-likelihood $\ell(\boldsymbol\beta)$ of a generalized linear model has

  1. score $\mathbf{U}(\boldsymbol\beta) = \dfrac1\phi\displaystyle\sum_{i=1}^n s_i(y_i - \mu_i)\,\mathbf{x}_i = \dfrac1\phi X^{\mathsf T}WG(\mathbf{y} - \boldsymbol\mu)$;
  2. expected (Fisher) information $\mathcal{I}(\boldsymbol\beta) = \operatorname{Cov}(\mathbf{U}) = \dfrac1\phi X^{\mathsf T}WX$, which also equals the expected value of $-\partial^2\ell/\partial\boldsymbol\beta\,\partial\boldsymbol\beta^{\mathsf T}$;
  3. observed information $J(\boldsymbol\beta) = -\dfrac{\partial^2\ell}{\partial\boldsymbol\beta\,\partial\boldsymbol\beta^{\mathsf T}} = \mathcal{I}(\boldsymbol\beta) - \dfrac1\phi\displaystyle\sum_{i=1}^n (y_i - \mu_i)\,\frac{ds_i}{d\eta_i}\,\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$.

Proof. Observation $i$ contributes $\ell_i = w_i[y_i\theta_i - b(\theta_i)]/\phi$ plus a term free of $\boldsymbol\beta$. Follow the chain $\boldsymbol\beta \to \eta_i \to \mu_i \to \theta_i$. First, $\partial\ell_i/\partial\theta_i = w_i(y_i - \mu_i)/\phi$, since $b'(\theta_i) = \mu_i$. Next, $d\theta_i/d\mu_i = 1/V(\mu_i)$ by Theorem 3 of Exponential Families, and $d\mu_i/d\eta_i = 1/g'(\mu_i)$ because $g$ is the inverse of $\mu_i(\eta_i)$. Finally $\partial\eta_i/\partial\boldsymbol\beta = \mathbf{x}_i$. Multiplying,

$$\frac{\partial\ell_i}{\partial\boldsymbol\beta} = \frac{w_i(y_i - \mu_i)}{\phi\,V(\mu_i)\,g'(\mu_i)}\,\mathbf{x}_i = \frac{s_i(y_i - \mu_i)}{\phi}\,\mathbf{x}_i,$$

and summing over $i$ gives part 1; $s_i = W_ig'(\mu_i)$ gives the matrix form.

For part 2, the score has mean zero because $E[Y_i] = \mu_i$, and its terms are independent, so its covariance is the sum of the covariances of the terms:

$$\operatorname{Cov}(\mathbf{U}) = \frac{1}{\phi^2}\sum_i s_i^2\operatorname{Var}(Y_i)\,\mathbf{x}_i\mathbf{x}_i^{\mathsf T} = \frac{1}{\phi^2}\sum_i \frac{w_i^2}{V(\mu_i)^2g'(\mu_i)^2}\cdot\frac{\phi V(\mu_i)}{w_i}\,\mathbf{x}_i\mathbf{x}_i^{\mathsf T} = \frac1\phi\sum_i W_i\,\mathbf{x}_i\mathbf{x}_i^{\mathsf T}.$$

For part 3, differentiate $\frac1\phi s_i(\eta_i)(y_i - \mu_i)\mathbf{x}_i$ once more with respect to $\boldsymbol\beta^{\mathsf T}$, by the product rule:

$$\frac1\phi\Big[\frac{ds_i}{d\eta_i}(y_i - \mu_i) - s_i\frac{d\mu_i}{d\eta_i}\Big]\mathbf{x}_i\mathbf{x}_i^{\mathsf T}, \qquad s_i\frac{d\mu_i}{d\eta_i} = \frac{w_i}{V(\mu_i)g'(\mu_i)^2} = W_i.$$

Summing and changing sign gives part 3. Its expected value removes the term with $y_i - \mu_i$, which is the second statement of part 2. $\square$

Two consequences are used repeatedly.

Corollary 1 (the canonical link). If the link is canonical, $J(\boldsymbol\beta) = \mathcal{I}(\boldsymbol\beta)$ for every $\boldsymbol\beta$ and every sample.

Proof. With $\theta_i = \eta_i$, $\mu_i = b'(\eta_i)$, so $d\mu_i/d\eta_i = b''(\eta_i) = V(\mu_i)$ and $g'(\mu_i) = 1/V(\mu_i)$. Then $s_i = w_i/(V(\mu_i)\cdot V(\mu_i)^{-1}) = w_i$, a constant, and $ds_i/d\eta_i = 0$. $\square$

This is the matrix form of the statement in Exponential Families that in the natural parameter the observed information equals the expected information; the link functions article (Theorem 1, part 3) found the same matrix $X^{\mathsf T}\operatorname{diag}(w_iV(\mu_i))X/\phi$ directly.

Corollary 2 (only the mean and the variance function matter). The score and the expected information depend on the distribution of $Y_i$ only through $\mu_i$ and $V(\mu_i)$.

That is visible in the formulas: no other property of the family appears. Wedderburn's (1974) quasi-likelihood builds on exactly this, by solving the same equations when only a mean and a variance function are specified; Overdispersion and Quasi-Likelihood develops it.

Fisher scoring is weighted least squares

Fisher scoring is Newton's method with the observed information replaced by the expected information:

$$\boldsymbol\beta^{+} = \boldsymbol\beta + \mathcal{I}(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta).$$

Here is the idea in one sentence: $\mathcal{I}\boldsymbol\beta + \mathbf{U}$ is $X^{\mathsf T}W$ times a vector, so $\boldsymbol\beta^+ = \mathcal{I}^{-1}(\mathcal{I}\boldsymbol\beta + \mathbf{U})$ has the form $(X^{\mathsf T}WX)^{-1}X^{\mathsf T}W\mathbf{z}$ of a weighted least squares estimate.

Theorem 2 (the scoring step is a weighted least squares fit). Define the working response

$$z_i = \eta_i - o_i + (y_i - \mu_i)\,g'(\mu_i),$$

all evaluated at the current $\boldsymbol\beta$. Then the Fisher scoring step is

$$\boldsymbol\beta^{+} = (X^{\mathsf T}WX)^{-1}X^{\mathsf T}W\mathbf{z},$$

the minimizer of $\sum_i W_i(z_i - \mathbf{x}_i^{\mathsf T}\boldsymbol\beta)^2$. The dispersion $\phi$ cancels and does not affect any step.

Proof. By Theorem 1, $\phi\,\mathcal{I}\boldsymbol\beta + \phi\,\mathbf{U} = X^{\mathsf T}WX\boldsymbol\beta + X^{\mathsf T}WG(\mathbf{y} - \boldsymbol\mu) = X^{\mathsf T}W[X\boldsymbol\beta + G(\mathbf{y} - \boldsymbol\mu)]$. The vector in brackets has entries $\mathbf{x}_i^{\mathsf T}\boldsymbol\beta + g'(\mu_i)(y_i - \mu_i) = z_i$, because $\mathbf{x}_i^{\mathsf T}\boldsymbol\beta = \eta_i - o_i$. So $\boldsymbol\beta^+ = \mathcal{I}^{-1}(\mathcal{I}\boldsymbol\beta + \mathbf{U}) = (X^{\mathsf T}WX)^{-1}X^{\mathsf T}W\mathbf{z}$, the factors $1/\phi$ cancelling. The matrix $X^{\mathsf T}WX$ is invertible because $X$ has full column rank and every $W_i > 0$. The weighted sum of squares $\sum_i W_i(z_i - \mathbf{x}_i^{\mathsf T}\boldsymbol\beta)^2 = \lVert W^{1/2}\mathbf{z} - W^{1/2}X\boldsymbol\beta\rVert^2$ is an ordinary least squares problem in the matrix $W^{1/2}X$, whose normal equations (The Geometry of Least Squares) are $X^{\mathsf T}WX\boldsymbol\beta = X^{\mathsf T}W\mathbf{z}$. $\square$

Hastie, Tibshirani and Friedman (2009, Section 4.4.1, eqs. 4.26 to 4.28) carry out the same rearrangement for logistic regression, call $\mathbf{z}$ the adjusted response, and note that the algorithm is "referred to as iteratively reweighted least squares or IRLS, since each iteration solves the weighted least squares problem".

Why these weights. The working response is the first-order Taylor expansion of the link applied to the data: $g(y_i) \approx g(\mu_i) + (y_i - \mu_i)g'(\mu_i) = \eta_i + (y_i - \mu_i)g'(\mu_i)$, minus the offset. It is defined even when $g(y_i)$ is not, as for $y_i = 0$ under the logit link. Its mean is $\eta_i - o_i = \mathbf{x}_i^{\mathsf T}\boldsymbol\beta$ when $\mu_i$ is the true mean, so $\mathbf{z}$ follows a linear model in $\boldsymbol\beta$, and its variance is

$$\operatorname{Var}(z_i) = g'(\mu_i)^2\operatorname{Var}(Y_i) = g'(\mu_i)^2\frac{\phi V(\mu_i)}{w_i} = \frac{\phi}{W_i}.$$

The working weights are therefore the inverse variances of the working responses, up to the common factor $\phi$. For a linear model with uncorrelated errors of unequal variances, weighting by inverse variances is the Aitken (generalized least squares) estimator, which The Gauss–Markov Theorem proves best among linear unbiased estimators. So each IRLS step fits the linearized model the way the Gauss–Markov theorem says a linear model with those variances should be fitted, and then relinearizes at the new fit.

Computing the step. The step is an ordinary least squares fit of $W^{1/2}\mathbf{z}$ on $W^{1/2}X$, so it can be computed by the QR decomposition of The Geometry of Least Squares, without forming $X^{\mathsf T}WX$, at a cost of order $np^2$ operations per iteration. At convergence the same decomposition gives the estimated covariance matrix $\hat\phi(X^{\mathsf T}\hat WX)^{-1}$ and the hat matrix $H = \hat W^{1/2}X(X^{\mathsf T}\hat WX)^{-1}X^{\mathsf T}\hat W^{1/2}$ of the final weighted fit. Its diagonal entries are leverages, which by Theorem 2 of the geometry article lie between 0 and 1 and add up to $p$.

Newton's method and Fisher scoring

Newton's method uses the observed information: $\boldsymbol\beta^{+} = \boldsymbol\beta + J(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta)$. It solves the likelihood equations by replacing $\mathbf{U}$ with its linear approximation at the current point, as Maximum Likelihood Estimation explains in one dimension.

Theorem 3 (Newton and scoring). For a canonical link the Newton step and the Fisher scoring step coincide, and IRLS is Newton's method. For other links the two steps are $\mathcal{I}^{-1}\mathbf{U}$ and $J^{-1}\mathbf{U}$, where $J - \mathcal{I} = -\frac1\phi\sum_i(y_i - \mu_i)\frac{ds_i}{d\eta_i}\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$ is a matrix with mean zero.

Proof. Corollary 1 for the first statement, Theorem 1 part 3 for the second; the difference has mean zero because each $E[Y_i - \mu_i] = 0$. $\square$

The difference matters in three ways. Scoring needs only $V$ and $g'$, and its matrix $X^{\mathsf T}WX$ is positive definite at every $\boldsymbol\beta$, while $J$ can fail to be positive definite away from the maximum for a non-canonical link. Newton's method converges faster near the solution, as the next sections show. And the two matrices give two different standard errors at the estimate.

IRLS on the six groups

The six groups of the link functions article (age band by obesity, with 12 of 1,040, 22 of 640, 69 of 860, 140 of 697, 264 of 1,108 and 270 of 762 adults with diabetes) are fitted with the logit link, an intercept, two indicators for the older age bands and one for obesity. Start from $\boldsymbol\beta = \mathbf{0}$. Then every $\mu_i = 1/2$, the variance function is $V = \mu(1 - \mu) = 1/4$, the derivative of the logit is $g'(\mu) = 1/(\mu(1 - \mu)) = 4$, and with prior weights $w_i = m_i$:

  • the working weights are $W_i = m_i/(\frac14\cdot 16) = m_i/4$: 260, 160, 215, 174, 277 and 191 (the group sizes divided by 4);
  • the working responses are $z_i = 0 + 4(y_i - \frac12)$: −1.954, −1.863, −1.679, −1.197, −1.047 and −0.583.

The first step is the weighted least squares fit of these six working responses on the four columns. The table follows the iteration. Because the link is canonical, each row is at once a scoring step, a Newton step and a weighted least squares fit; the script checks all three at every iteration.

Iteration Intercept 40 to 59 60 and over Obese Log-likelihood
0 0.0000 0.0000 0.0000 0.0000 −1,703.04
1 −2.0524 0.4326 1.0520 0.3501 −182.09
2 −3.1437 1.0274 1.9597 0.6199 −47.73
3 −3.8610 1.6272 2.6225 0.7250 −24.47
4 −4.1710 1.9271 2.9256 0.7381 −22.14
5 −4.2237 1.9794 2.9780 0.7386 −22.09
6 −4.2250 1.9808 2.9793 0.7386 −22.09

From iteration 6 on, the coefficients agree with their limit to four decimals. The log-likelihoods of these grouped observations include the binomial coefficients $\ln\binom{m_i}{m_iy_i}$, which add 1,836.86 to the Bernoulli log-likelihood of the same adults; the log-likelihoods of the 5,107 individual records below do not, which is why the start $\boldsymbol\beta = \mathbf{0}$ gives $-1{,}703.04$ here and $-3{,}539.9$ there. Differences between fits to the same data are unaffected. The early steps are long, because the starting point, a probability of one half in every group, is far from the data. The last steps are short, and the number of correct digits roughly doubles each time, the signature of Newton's method near a solution.

At the estimate, the standard errors from $(X^{\mathsf T}\hat WX)^{-1}$, with $\phi = 1$, are 0.1796, 0.1890, 0.1812 and 0.0833, so the obesity coefficient is 8.87 standard errors from zero. The leverages of the final weighted fit, the diagonal of $H$, range from 0.476 to 0.828 and add up to 4, the number of coefficients. With six observations and four coefficients every group has high leverage, which is one reason the residual checks of Deviance and Inference for Generalized Linear Models are needed before the fit is trusted.

Starting values. The iteration needs a starting point. The table started from $\boldsymbol\beta = \mathbf{0}$, as the logistic regression article did. A start that works for every family and link is to start from a mean instead: take $\mu_i^{(0)}$ inside the allowed range and close to the data, for example $(m_iy_i + \frac12)/(m_i + 1)$ for a binomial proportion or $y_i + 0.1$ for a count, compute $\eta_i^{(0)} = g(\mu_i^{(0)})$, the working response and the weights from it, and let the first weighted least squares fit give $\boldsymbol\beta^{(0)}$. This start needs no coefficients at all, and it is the one used in the rest of the article.

How fast does it converge?

Here is the idea: near the estimate, one step of an iteration acts on the error like multiplication by a fixed matrix, so the error shrinks geometrically, at a rate set by that matrix's largest eigenvalue. For Newton's method the matrix is zero.

Theorem 4 (local rate of convergence). Suppose $\hat{\boldsymbol\beta}$ solves the likelihood equations, $\mathbf{U}$ and $\mathcal{I}$ are continuously differentiable near it, and $J(\hat{\boldsymbol\beta})$ is positive definite. Let

$$M = I - \mathcal{I}(\hat{\boldsymbol\beta})^{-1}J(\hat{\boldsymbol\beta}),$$

and let $\rho$ be the largest absolute value of its eigenvalues. Then:

  1. the eigenvalues of $M$ are real and less than 1;
  2. the scoring iteration satisfies $\boldsymbol\beta^{(t+1)} - \hat{\boldsymbol\beta} = M(\boldsymbol\beta^{(t)} - \hat{\boldsymbol\beta}) + r_t$ with $\lVert r_t\rVert/\lVert\boldsymbol\beta^{(t)} - \hat{\boldsymbol\beta}\rVert \to 0$ as $\boldsymbol\beta^{(t)} \to \hat{\boldsymbol\beta}$;
  3. if $\rho < 1$, then for every $\varepsilon > 0$ with $\rho + \varepsilon < 1$ there is a neighborhood of $\hat{\boldsymbol\beta}$ from which the scoring iteration converges to $\hat{\boldsymbol\beta}$, the error shrinking at each step by at least the factor $\rho + \varepsilon$ in the norm $\lVert\mathbf{v}\rVert_{\mathcal{I}} = (\mathbf{v}^{\mathsf T}\mathcal{I}(\hat{\boldsymbol\beta})\mathbf{v})^{1/2}$;
  4. for Newton's method the corresponding matrix is $I - J^{-1}J = 0$, so near $\hat{\boldsymbol\beta}$ the error shrinks by an arbitrarily small factor per step; for a canonical link $M = 0$ for scoring too.

Proof. (1) Write $\mathcal{I} = \mathcal{I}(\hat{\boldsymbol\beta})$ and $J = J(\hat{\boldsymbol\beta})$, both symmetric and positive definite, and let $\mathcal{I}^{1/2}$ be the symmetric square root. Then $\mathcal{I}^{1/2}M\mathcal{I}^{-1/2} = I - \mathcal{I}^{-1/2}J\mathcal{I}^{-1/2} = S$, a symmetric matrix, so $M$ has the real eigenvalues of $S$. The matrix $\mathcal{I}^{-1/2}J\mathcal{I}^{-1/2}$ is positive definite, so its eigenvalues are positive and those of $S$ are less than 1.

(2) The scoring iteration is $\boldsymbol\beta^{(t+1)} = F(\boldsymbol\beta^{(t)})$ with $F(\boldsymbol\beta) = \boldsymbol\beta + \mathcal{I}(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta)$, and $F(\hat{\boldsymbol\beta}) = \hat{\boldsymbol\beta}$ because $\mathbf{U}(\hat{\boldsymbol\beta}) = \mathbf{0}$. Differentiate $F$ at $\hat{\boldsymbol\beta}$. The derivative of $\mathcal{I}(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta)$ has two terms: one with the derivative of $\mathcal{I}^{-1}$, multiplied by $\mathbf{U}(\hat{\boldsymbol\beta}) = \mathbf{0}$; and $\mathcal{I}^{-1}$ times the derivative of $\mathbf{U}$, which is $-J$. So the derivative of $F$ at $\hat{\boldsymbol\beta}$ is $I - \mathcal{I}^{-1}J = M$, and the definition of the derivative gives (2).

(3) In the norm $\lVert\cdot\rVert_{\mathcal{I}}$, $\lVert M\mathbf{v}\rVert_{\mathcal{I}} = \lVert S\,\mathcal{I}^{1/2}\mathbf{v}\rVert \le \rho\,\lVert\mathcal{I}^{1/2}\mathbf{v}\rVert = \rho\,\lVert\mathbf{v}\rVert_{\mathcal{I}}$, because a symmetric matrix stretches no vector by more than its largest absolute eigenvalue. All norms on $\mathbb{R}^p$ are within constant factors of one another, so by (2) there is a radius $\delta$ such that $\lVert r_t\rVert_{\mathcal{I}} \le \varepsilon\lVert\boldsymbol\beta^{(t)} - \hat{\boldsymbol\beta}\rVert_{\mathcal{I}}$ whenever $\lVert\boldsymbol\beta^{(t)} - \hat{\boldsymbol\beta}\rVert_{\mathcal{I}} < \delta$. For such $t$, $\lVert\boldsymbol\beta^{(t+1)} - \hat{\boldsymbol\beta}\rVert_{\mathcal{I}} \le (\rho + \varepsilon)\lVert\boldsymbol\beta^{(t)} - \hat{\boldsymbol\beta}\rVert_{\mathcal{I}}$, which is again below $\delta$; by induction the errors shrink geometrically to 0.

(4) For Newton's map write $J(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta) = J(\hat{\boldsymbol\beta})^{-1}\mathbf{U}(\boldsymbol\beta) + [J(\boldsymbol\beta)^{-1} - J(\hat{\boldsymbol\beta})^{-1}]\mathbf{U}(\boldsymbol\beta)$. The first term has derivative $-J(\hat{\boldsymbol\beta})^{-1}J(\hat{\boldsymbol\beta}) = -I$ at $\hat{\boldsymbol\beta}$. The second is of smaller order than $\lVert\boldsymbol\beta - \hat{\boldsymbol\beta}\rVert$: $J^{-1}$ is continuous near $\hat{\boldsymbol\beta}$ because $\mathbf{U}$ is continuously differentiable and $J(\hat{\boldsymbol\beta})$ is invertible, so the bracket tends to 0, while $\lVert\mathbf{U}(\boldsymbol\beta)\rVert$ is at most a constant times $\lVert\boldsymbol\beta - \hat{\boldsymbol\beta}\rVert$ near $\hat{\boldsymbol\beta}$, since $\mathbf{U}(\hat{\boldsymbol\beta}) = \mathbf{0}$ and $\mathbf{U}$ is differentiable. So Newton's map $\boldsymbol\beta + J(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta)$ has derivative $I - I = 0$ at $\hat{\boldsymbol\beta}$, so (3) holds with $\rho = 0$ and any $\varepsilon > 0$. For a canonical link $J = \mathcal{I}$ by Corollary 1. $\square$

The theorem proves that Newton's method converges faster than any geometric rate near the solution. Under one more derivative the convergence is quadratic.

Corollary 3 (quadratic convergence of Newton's method). Under the conditions of Theorem 4, suppose also that $\mathbf{U}$ is twice continuously differentiable near $\hat{\boldsymbol\beta}$. Then there are a constant $K$ and a radius $\delta > 0$ such that $\lVert\boldsymbol\beta^{+} - \hat{\boldsymbol\beta}\rVert \le K\lVert\boldsymbol\beta - \hat{\boldsymbol\beta}\rVert^2$ for the Newton step $\boldsymbol\beta^{+} = \boldsymbol\beta + J(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta)$ from any $\boldsymbol\beta$ with $\lVert\boldsymbol\beta - \hat{\boldsymbol\beta}\rVert < \delta$.

Proof. Write $\mathbf{e} = \boldsymbol\beta - \hat{\boldsymbol\beta}$. Then $\boldsymbol\beta^{+} - \hat{\boldsymbol\beta} = J(\boldsymbol\beta)^{-1}[\mathbf{U}(\boldsymbol\beta) + J(\boldsymbol\beta)\mathbf{e}]$. Since $\mathbf{U}(\hat{\boldsymbol\beta}) = \mathbf{0}$ and the derivative of $\mathbf{U}$ is $-J$, the fundamental theorem of calculus along the segment from $\hat{\boldsymbol\beta}$ to $\boldsymbol\beta$ gives $\mathbf{U}(\boldsymbol\beta) = -\int_0^1 J(\hat{\boldsymbol\beta} + t\mathbf{e})\,\mathbf{e}\,dt$, so the bracket is $\int_0^1[J(\boldsymbol\beta) - J(\hat{\boldsymbol\beta} + t\mathbf{e})]\,\mathbf{e}\,dt$. Because $\mathbf{U}$ is twice continuously differentiable, $J$ has continuous derivatives on a closed ball around $\hat{\boldsymbol\beta}$, and by the mean value theorem applied to each entry along a segment there is a constant $L$ with $\lVert J(\mathbf{a}) - J(\mathbf{b})\rVert \le L\lVert\mathbf{a} - \mathbf{b}\rVert$ for $\mathbf{a}$, $\mathbf{b}$ in the ball. The two points differ by $(1 - t)\mathbf{e}$, so the bracket has norm at most $\int_0^1 L(1 - t)\lVert\mathbf{e}\rVert^2\,dt = \frac{L}{2}\lVert\mathbf{e}\rVert^2$. Finally $J$ is continuous and invertible at $\hat{\boldsymbol\beta}$, so $\lVert J(\boldsymbol\beta)^{-1}\rVert$ is at most some $B$ on a smaller ball, and $K = BL/2$ works. $\square$

The logit curve in the figure below illustrates it, with largest errors of 0.017, 0.00012 and 0.0000000061 in successive steps.

On the six groups, from the start described above, the number of iterations until every coefficient is within $10^{-8}$ of the estimate, and the factor $\rho$ computed from $\mathcal{I}$ and $J$ at the estimate, are:

Link Newton Fisher scoring $\rho$
Logit 2 2 0
Probit 2 3 0.012
Complementary log-log 3 3 0.015
Log 3 4 0.032
Identity 4 12 0.311

The factor $\rho$ is small when $J$ is close to $\mathcal{I}$, that is, when the term $\sum_i(y_i - \hat\mu_i)\,s_i'\,\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$ is small: when the residuals are small or the link is close to canonical. The identity link fits these data poorly and is far from canonical for the binomial, and scoring pays for it. Over iterations 6 to 16 its error falls by an average factor of 0.311 per step, matching $\rho$ to three decimals. The factor is an average: two eigenvalues of $M$, 0.311 and −0.307, nearly tie, so the error alternates between shrinking to about 0.26 and to about 0.37 of its size (part 1 of the theorem allows negative eigenvalues).

Largest coefficient error at each iteration for the six groups, from the same start, with Fisher scoring (left) and Newton's method (right), for the logit, log and identity links. Notice that scoring with the identity link falls along a straight line on this logarithmic scale, with the slope predicted by Theorem 4 (dashed guide), while every Newton curve bends downward ever more steeply, and that for the logit link the two methods are the same algorithm.
Largest coefficient error at each iteration for the six groups, from the same start, with Fisher scoring (left) and Newton's method (right), for the logit, log and identity links. Notice that scoring with the identity link falls along a straight line on this logarithmic scale, with the slope predicted by Theorem 4 (dashed guide), while every Newton curve bends downward ever more steeply, and that for the logit link the two methods are the same algorithm.

Two standard errors

Each information matrix, inverted at the estimate, gives an estimated covariance matrix of $\hat{\boldsymbol\beta}$. For a canonical link they are the same matrix. For other links they are not, and their square roots give two sets of standard errors. For the identity link on the six groups:

Information Intercept 40 to 59 60 and over Obese
expected 0.0028 0.0090 0.0110 0.0082
observed 0.0025 0.0097 0.0113 0.0095

The two differ by up to 16% here. For the log link they nearly agree: 0.1811 against 0.1813 for the 40 to 59 coefficient, and 0.0628 for the obesity coefficient under both, to four decimals. In the setting that Asymptotics of the Maximum Likelihood Estimator treats, one parameter and independent observations with a common distribution, it proves that the Wald interval has the right limiting coverage whether the information is evaluated as $J(\hat\theta)$ or as $nI(\hat\theta)$ (its Corollary 3). The corresponding statement for the coefficients of a generalized linear model, whose observations do not share a distribution, belongs to Deviance and Inference for Generalized Linear Models. In a finite sample they are two different approximations, and a report should say which one it used. An implementation of IRLS has the expected information at hand at convergence, since it is the matrix of the last weighted fit.

When a step goes wrong

Nothing so far guarantees that a step increases the log-likelihood. Far from the estimate the quadratic approximation behind each step can be poor, and the step can overshoot. Hastie, Tibshirani and Friedman (2009, Section 4.4.1) write of logistic regression that "convergence is never guaranteed", that the algorithm typically converges because the log-likelihood is concave, "but overshooting can occur", and: "In the rare cases that the log-likelihood decreases, step size halving will guarantee convergence." Part of that can be proved in a few lines: a scoring step always points uphill.

Theorem 5 (the scoring direction is an ascent direction). If $\mathbf{U}(\boldsymbol\beta) \ne \mathbf{0}$, then $\ell(\boldsymbol\beta + t\,\mathbf{d}) > \ell(\boldsymbol\beta)$ for all sufficiently small $t > 0$, where $\mathbf{d} = \mathcal{I}(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta)$. The same holds for the Newton direction $J(\boldsymbol\beta)^{-1}\mathbf{U}(\boldsymbol\beta)$ wherever $J(\boldsymbol\beta)$ is positive definite.

Proof. The derivative of $t \mapsto \ell(\boldsymbol\beta + t\mathbf{d})$ at $t = 0$ is $\mathbf{U}^{\mathsf T}\mathbf{d} = \mathbf{U}^{\mathsf T}\mathcal{I}^{-1}\mathbf{U}$, which is positive because $\mathcal{I}$, and hence $\mathcal{I}^{-1}$, is positive definite and $\mathbf{U} \ne \mathbf{0}$. A function with positive derivative at 0 exceeds its value at 0 on some interval $(0, t_0)$. The same argument applies to $J^{-1}$ when $J$ is positive definite. $\square$

Step halving uses this. If the full step $\boldsymbol\beta + \mathbf{d}$ gives a smaller log-likelihood, or invalid means, try $\boldsymbol\beta + \frac12\mathbf{d}$, then $\boldsymbol\beta + \frac14\mathbf{d}$, and so on. By Theorem 5 a scoring direction succeeds after finitely many halvings whenever $\mathbf{U} \ne \mathbf{0}$, so every accepted step raises the log-likelihood. That alone does not prove that the iterates reach the maximum, which is the part of the quoted claim this page does not prove.

Example (a Newton step that lowers the likelihood). Fit the log link to the six groups, starting from the intercept-only coefficients $(-2, 0, 0, 0)$, which put every group at $e^{-2} = 0.1353$, near the overall share. The log-likelihood there is $-346.78$. The full Newton step lowers it to $-538.36$. Halving the step once gives $-107.21$, and the halved iteration then converges. Fisher scoring from the same start rises at every step, to $-164.75$ after the first. The log link is not canonical, and away from the maximum its $J$ is a poor guide.

Example (Newton's method diverging for a concave log-likelihood). The logit link is canonical, so its log-likelihood is strictly concave and has a single maximum. That does not make unmodified Newton steps safe. Fit diabetes on age in years and obesity for all 5,107 adults, starting from $(5, -0.1, 0)$, a curve that falls with age from almost 1. The log-likelihood there is $-6{,}368.6$. The full Newton steps give $-3{,}161.3$, then $-9{,}554.7$ and $-15{,}918.4$, and the fourth step takes the age coefficient to $-32.35$ and the log-likelihood below $-2{,}000{,}000$: each step overshoots further, and the iterates run off. With step halving, the second step is halved once, its log-likelihood is $-2{,}139.3$ instead of $-9{,}554.7$, and the iteration reaches the maximum in 9 iterations in all.

Example (a stall at the boundary). For the identity link on all 5,107 adults, Link Functions and the Structure of a Generalized Linear Model (Theorem 4) proves that the maximum lies on the boundary of the allowed coefficients, where the score is not zero. IRLS with step halving cannot find a point where the score vanishes, because none exists among valid coefficients; run for 200 iterations, it creeps toward the boundary with ever shorter steps and stalls at a log-likelihood of $-1{,}904.7$, the value of the boundary maximum. An iteration that has not converged is a symptom to investigate, not a reason to raise the iteration limit.

All 5,107 adults

For the full data with the logit link, starting from $\boldsymbol\beta = \mathbf{0}$, where the log-likelihood is $-3{,}539.9$, IRLS needs 5 iterations for every coefficient to agree with its limit to five decimals. The estimates are an intercept of $-5.2876$, 0.05695 per year of age and 0.8051 for obesity, with log-likelihood $-1{,}873.56$ and standard errors 0.00281 for age and 0.0840 for obesity. A general-purpose quasi-Newton optimizer (BFGS, from SciPy) applied to the same log-likelihood with gradient tolerance $10^{-8}$ stops after 12 iterations (a count that depends on the tolerance and the software version) at a log-likelihood within $10^{-6}$ of the IRLS value, which checks the fit. Each IRLS iteration costs one weighted least squares fit with three columns.

Beyond generalized linear models

Green (1984) argued that the method reaches much further; his summary states that the scope of IRLS "extends beyond the exponential-family-type generalized linear models to other distributions, to non-linear parameterizations, and to dependent observations", and that criteria other than maximum likelihood, "including resistant alternatives", may be used. Within this collection, the same structure appears in three places. Overdispersion and Quasi-Likelihood runs the identical iteration with only a mean and a variance function (Corollary 2). For several categories, Hastie, Tibshirani and Friedman (2009, Section 4.4.1) note that Newton's method "can also be expressed as an iteratively reweighted least squares algorithm, but with a vector of K − 1 responses and a nondiagonal weight matrix per observation"; Multinomial and Softmax Regression takes up that model. And The EM Algorithm records that Dempster, Laird and Rubin (1977) listed iteratively reweighted least squares among the applications of their method.

What is proved, what is cited, what the experiment shows

Proved on this page: the score, expected information and observed information of a generalized linear model with any link (Theorem 1), with the equality of the two informations for canonical links (Corollary 1) and the dependence on the mean and variance function only (Corollary 2); the Fisher scoring step as a weighted least squares fit of the working response, with $\phi$ cancelling (Theorem 2); the variance of the working response, which makes the weights inverse variances; the relation between Newton and scoring steps (Theorem 3); the local rate of convergence, with real eigenvalues below 1, geometric convergence at rate $\rho$ in a weighted norm, and a zero matrix for Newton's method and canonical links (Theorem 4); quadratic convergence of Newton's method when the score has two continuous derivatives (Corollary 3); the ascent property of the scoring direction and of the Newton direction where $J$ is positive definite, which makes step halving terminate (Theorem 5).

Used from other pages: the derivative $d\theta/d\mu = 1/V(\mu)$ (Exponential Families); the normal equations, QR and the leverage bounds (The Geometry of Least Squares); Aitken's generalized least squares (The Gauss–Markov Theorem); the boundary maximum of the identity link (Link Functions and the Structure of a Generalized Linear Model); the Wald interval with observed or expected information (Asymptotics of the Maximum Likelihood Estimator).

Stated, not proved: the claim that step halving guarantees convergence to the maximum (quoted from Hastie, Tibshirani and Friedman, 2009); the wider scope of IRLS (Green, 1984, from the summary).

Computed on the unit's data: the iterations on the six groups and on all 5,107 adults, the iteration counts and rates for five links, the two sets of standard errors, and the three examples of steps going wrong. They describe these data from these starting points; other data and other starts give other counts. Every number is computed and checked against this page by tools/experiments/statistics/iteratively-reweighted-least-squares.py, which uses the reference fitter in glmdata.py; the figure is drawn by tools/figures/iteratively-reweighted-least-squares.py.

Worked problems

The problems were written for this article; the first reproduces the first row of the Newton table in Logistic Regression exactly. Each number is recomputed by the article's script.

Problem 1 (the first step for the Challenger flights, by hand). The 23 flights have launch temperatures $x_i$ with $\sum x_i = 1{,}600$ and $\sum x_i^2 = 112{,}400$; 7 of them had O-ring distress ($y_i = 1$), and the products of temperature and outcome give $\sum_i x_i(y_i - \frac12) = -354$. Starting from $b_0 = b_1 = 0$, compute the first IRLS step for the logistic model exactly.

Solution. At $\mathbf{b} = \mathbf{0}$ every $p_i = \frac12$, so every working weight is $W_i = p_i(1 - p_i) = \frac14$ (here $w_i = 1$) and every working response is $z_i = 0 + (y_i - \frac12)/\frac14 = 4(y_i - \frac12)$. With equal weights the weighted least squares fit is the ordinary one: the step is the least squares line of $z$ on temperature. Its ingredients are $n = 23$, $\sum x_i = 1{,}600$, $\sum x_i^2 = 112{,}400$, $\sum z_i = 4(7 - 11.5) = -18$ and $\sum x_iz_i = 4 \times (-354) = -1{,}416$. The determinant of the normal equations is $n\sum x_i^2 - (\sum x_i)^2 = 23 \times 112{,}400 - 1{,}600^2 = 25{,}200$. So

$$b_1 = \frac{23 \times (-1{,}416) - 1{,}600 \times (-18)}{25{,}200} = \frac{-3{,}768}{25{,}200} = -0.14952, \qquad b_0 = \frac{-18 - 1{,}600\,b_1}{23} = 9.61905,$$

exactly $-157/1{,}050$ and $202/21$. These are the values in row 1 of the Newton table of the logistic regression article, as Theorem 3 says they must be: for the canonical link the IRLS step is the Newton step.

Problem 2 (the normal linear model). Show that for a normal response with the identity link, IRLS reaches the least squares estimate in one step from any starting coefficients.

Solution. Here $V(\mu) = 1$ and $g'(\mu) = 1$, so $W_i = w_i$ does not depend on $\boldsymbol\beta$, and the working response is $z_i = \eta_i - o_i + (y_i - \mu_i) = y_i - o_i$, because $\mu_i = \eta_i$. The first step is the weighted least squares fit of $\mathbf{y} - \mathbf{o}$ on $X$ with the prior weights, which is the maximum likelihood estimate of the normal linear model (ordinary least squares when the weights are equal). The next step recomputes the same $\mathbf{z}$ and $W$ and returns the same fit, so the iteration has converged. The script checks this on a small example from the start $(10, -3)$.

Problem 3 (the Poisson log-linear model). Write out the IRLS quantities for a Poisson response with the log link and prior weights 1.

Solution. $V(\mu) = \mu$ and $g(\mu) = \ln\mu$, so $g'(\mu) = 1/\mu$ and $W_i = 1/(\mu_i\cdot\mu_i^{-2}) = \mu_i$. The working response is $z_i = \eta_i - o_i + (y_i - \mu_i)/\mu_i$. The link is canonical, so $s_i = 1$, the score is $X^{\mathsf T}(\mathbf{y} - \boldsymbol\mu)$, the information is $X^{\mathsf T}\operatorname{diag}(\mu_i)X$, and IRLS is Newton's method. Each step regresses $\mathbf{z}$ on $X$ with weights equal to the current fitted means: the working response has variance $g'(\mu_i)^2\mu_i = 1/\mu_i$, so observations with larger means have more precise working responses and count for more. Poisson Regression and Rate Models uses exactly this with the offset $o_i = \ln t_i$ for an exposure $t_i$.

Problem 4 (a gamma model with the log link). Show that for a gamma response with the log link, every IRLS step is an unweighted least squares fit, and that the dispersion $\phi = 1/\nu$ affects the standard errors but not the estimates.

Solution. For the gamma family $V(\mu) = \mu^2$, and the log link has $g'(\mu) = 1/\mu$. With $w_i = 1$, $W_i = 1/(\mu_i^2\cdot\mu_i^{-2}) = 1$ for every observation at every iteration. So each step is the ordinary least squares fit of $z_i = \eta_i + (y_i - \mu_i)/\mu_i$ on $X$; only the working response changes from step to step. By Theorem 2, $\phi$ does not enter any step, so the estimates are the same whatever the shape $\nu$; the script runs the iteration with $\phi = 1$ and $\phi = 0.2$ and finds identical iterates. The estimated covariance matrix is $\hat\phi(X^{\mathsf T}X)^{-1}$, so the standard errors scale with $\sqrt{\hat\phi}$. The log link is not canonical for the gamma family, so this iteration is Fisher scoring, not Newton's method, and the two standard errors of the previous section differ.

Summary

  • Score $\mathbf{U} = X^{\mathsf T}WG(\mathbf{y} - \boldsymbol\mu)/\phi$, expected information $\mathcal{I} = X^{\mathsf T}WX/\phi$ with $W_i = w_i/(V(\mu_i)g'(\mu_i)^2)$; observed information $J = \mathcal{I}$ minus a mean-zero term that vanishes for canonical links (Theorem 1).
  • Fisher scoring step = weighted least squares of $z_i = \eta_i - o_i + (y_i - \mu_i)g'(\mu_i)$ on $X$ with weights $W_i$; $\phi$ cancels (Theorem 2). The weights are inverse variances of the linearized responses.
  • Newton = scoring for canonical links; otherwise they differ, and give two different standard errors (Theorem 3).
  • Near the estimate, scoring's error is multiplied by $M = I - \mathcal{I}^{-1}J$ per step, with real eigenvalues below 1 and geometric convergence at rate $\rho$; Newton's matrix is 0 (Theorem 4). On the six groups $\rho$ ranges from 0 (logit) to 0.311 (identity).
  • The scoring direction always ascends; step halving makes each accepted step raise the log-likelihood (Theorem 5). Unhalved Newton steps can lower the likelihood or diverge even for a concave log-likelihood; at a boundary maximum the iteration stalls.

What we have learned

A generalized linear model is fitted by linearizing the link at the current fit, weighting each linearized observation by its inverse variance, and solving a weighted least squares problem, over and over. That is Fisher scoring, and for canonical links it is Newton's method, which is why it usually converges in a handful of iterations. What the algorithm returns, besides the estimates, is the matrix $X^{\mathsf T}\hat WX$, the basis of every standard error and test of the fitted model. Deviance and Inference for Generalized Linear Models builds Wald, likelihood ratio and score inference on it, and studies separation, the case in which the iteration runs off because no maximum exists.

References

  • Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1), 1–38. record · 6 pages
  • Green, P. J. (1984). Iteratively reweighted least squares for maximum likelihood estimation, and some robust and resistant alternatives. Journal of the Royal Statistical Society, Series B, 46(2), 149–170. https://doi.org/10.1111/j.2517-6161.1984.tb01288.x record
  • Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. Section 4.4.1, "Fitting Logistic Regression Models", pp. 120–121. record · 31 pages
  • Nelder, J. A., and Wedderburn, R. W. M. (1972). Generalized linear models. Journal of the Royal Statistical Society, Series A, 135(3), 370–384. https://doi.org/10.2307/2344614 record · 5 pages
  • Wedderburn, R. W. M. (1974). Quasi-likelihood functions, generalized linear models, and the Gauss–Newton method. Biometrika, 61(3), 439–447. https://doi.org/10.1093/biomet/61.3.439 record · 2 pages