Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

By default when we use a glm function in R, it uses the iteratively reweighted least squares (IWLS) method to find the maximum likelihood estimation the parameters. Now I have two questions.

  1. Does IWLS estimations guarantee the global maximum of the likelihood function? Based on the last slide in this presentation, I think it does not! I just wanted to make sure of that.
  2. Can we say that the reason for question 1 above is because of the fact that almost all the numerical optimization methods may stuck at a local maximum rather than a global maximum?
share|improve this question

2 Answers 2

When you are trying to estimate parameters, you always want there to be a closed form solution. However, one does not always exist (I suppose it is possible that in some cases there may be one but it is unknown at present). When a closed form solution does not exist, some heuristic strategy must be employed to search over the parameter space for the best possible parameter estimates to use. There are many such search strategies (e.g. in R, ?optim lists 6 general purpose methods). The IRWLS is a simplified version of the Newton-Raphson algorithm.

Unfortunately, the answer to your [1] is that no heuristic search strategy is guaranteed to find the global minimum (maximum). There are three reasons why that is the case:

  1. As noted on slide 9 of your linked presentation, no unique solution may exist. Examples of this might be perfect multicollinearity, or when there are more parameters to be estimated than there are data.
  2. As noted on slide 10 (that presentation is quite good, I think), the solution may be infinite. This can happen in logistic regression, for instance, when you have perfect separation.
  3. It can also be the case that there is a finite global minimum (maximum), but that the algorithm does not find it. These algorithms (especially IRWLS and N-R) tend to start from a specified location and 'look around' to see if moving in some direction constitutes 'going downhill' (i.e., improving the fit). If so, then it will re-fit at some distance in that direction and repeat until the guessed / predicted improvement is less than some threshold. Thus, there can be two ways to not reach the global minimum:

    1. The rate of descent from the current location towards the global minimum (maximum) is too shallow to cross the threshold and the algorithm stops short of the solution.
    2. There is a local minimum (maximum) between the current location and the global minimum (maximum), so that it appears to the algorithm that further movement would lead to a worse fit.

Regarding your [2], be aware that different search strategies have different tendencies to be caught in local minima. Even the same strategy can sometimes be adapted, or commenced from a different starting point to address the latter two problems.

share|improve this answer
    
Thanks gung. One more question, how we can select a good starting point when optimizing? –  Stat May 17 at 19:48
    
I don't know that there is necessarily a best way. Sometimes you have to try a couple of different starting points, if it fails to converge or if you aren't sure you're in the global minimum. I think a common way programs pick a starting point is to use the OLS estimates, even though they aren't appropriate & you know you'll have to move from there. –  gung May 18 at 2:49

You are correct that in general, IWLS, like other numerical optimization methods, can only guarantee convergence to a local maximum, if they even converge. Here's a nice example where the starting value was outside the convergence domain for the algorithm used by glm() in R. However, it is worth noting that for GLMs with the canonical link, the likelihood is concave, see here. Thus, if the algorithm converges, it will have converged to the global mode!

The last issue pointed out in the slide is a problem where the MLE for a paramter is at infinity. This can occur in logistic regression where there exists complete separation. In such a case, you will get a warning message that the fitted probabilities are numerically 0 or 1. It's important to note that when this occurs, the algorithm has not converged to the mode, thus this does not have to do with the algorithm being stuck in a local maximum.

share|improve this answer
    
Thanks a lot jsk. –  Stat May 17 at 19:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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