15
$\begingroup$

My questions are:

  1. Are generalized linear models (GLMs) guaranteed to converge to a global maximum? If so, why?
  2. Furthermore, what constraints are there on the link function to insure convexity?

My understanding of GLMs is that they maximize a highly nonlinear likelihood function. Thus, I would imagine that there are several local maxima and the parameter set you converge to depends on the initial conditions for the optimization algorithm. However, after doing some research I have not found a single source which indicates that there are multiple local maxima. Furthermore, I am not so familiar with optimization techniques, but I know the Newton-Raphson method and IRLS algorithm are highly prone to local maxima.

Please explain if possible both on an intuitive and mathematical basis!

EDIT: dksahuji answered my original question, but I want to add the followup question [2] above. ("What constraints are there on the link function to insure convexity?")

$\endgroup$
  • $\begingroup$ I think some restrictions must be required before that could be so. What is the source for the statement? $\endgroup$ – Glen_b Feb 24 '14 at 4:26
  • $\begingroup$ Several sites seemed to imply it however I couldnt find anything which mentioned it outright, so I also welcome its disproof! $\endgroup$ – DankMasterDan Feb 24 '14 at 14:59
  • $\begingroup$ as long as the likelihood is well defined everywhere on the domain (and ignoring some tangential numerical issues) I think yes. Under those conditions, the hessian is <0 everywhere on the domain so the likeihood is globally concave. Btw, the function are not 'highly non-linear' in the parameters and that's what matters. $\endgroup$ – user603 Feb 24 '14 at 15:30
  • $\begingroup$ @user603 what is your source/proof that the hessian is <0 everywhere? $\endgroup$ – DankMasterDan Feb 25 '14 at 21:10
  • $\begingroup$ Logistic, Poisson, and Gaussian regressions are often convex given a "good" link function. However, with arbitrary link function, they are not convex. $\endgroup$ – Memming Feb 25 '14 at 22:07
11
$\begingroup$

The definition of exponential family is:

$$ p(x|\theta) = h(x)\exp(\theta^T\phi(x) - A(\theta)), $$

where $A(\theta)$ is the log partition function. Now one can prove that the following three things hold for 1D case (and they generalize to higher dimensions--you can look into properties of exponential families or log partition):

  1. $ \frac{dA}{d\theta} = \mathbb{E}[\phi(x)]$

  2. $ \frac{d^2A}{d\theta^2} = \mathbb{E}[\phi^2(x)] -\mathbb{E}[\phi(x)]^2 = {\rm var}(\phi(x)) $

  3. $ \frac{ \partial ^2A}{\partial\theta_i\partial\theta_j} = \mathbb{E}[\phi_i(x)\phi_j(x)] -\mathbb{E}[\phi_i(x)] \mathbb{E}[\phi_j(x)] = {\rm cov}(\phi(x)) \Rightarrow \Delta^2A(\theta) = {\rm cov}(\phi(x))$

The above result prove that $A(\theta)$ is convex(as ${\rm cov}(\phi(x))$ is positive semidefinite). Now we take a look at likelihood function for MLE:

\begin{align} p(\mathcal{D}|\theta) &= \bigg[\prod_{i=1}^{N}{h(x_i)}\bigg]\ \exp\!\big(\theta^T[\sum_{i=1}^{N}\phi(x_i)] - NA(\theta)\big) \\ \log\!\big(p(\mathcal{D}|\theta)\big) &= \theta^T\bigg[\sum_{i=1}^{N}\phi(x_i)\bigg] - NA(\theta) \\ &= \theta^T[\phi(\mathcal{D})] - NA(\theta) \end{align}

Now $\theta^T[\phi(\mathcal{D})]$ is linear in theta and $-A(\theta)$ is concave. Therefore, there is a unique global maximum.

There is a generalized version called curved exponential family which would also be similar. But most of the proofs are in canonical form.

$\endgroup$
  • $\begingroup$ so does this mean that GLM have a unique global minima nomatter which link function is chosen (including the noncanonical ones)? $\endgroup$ – DankMasterDan Feb 26 '14 at 2:25
  • 1
    $\begingroup$ I will try to answer as far as I percieve it. $ p(x|\theta) = h(x)exp(\eta(\theta)^T\phi(x) - A(\eta(\theta)))$ is the case you are talking about. This still is concave in $\eta$ but may not be in $\theta$ so $\eta$ should be such that the whole log likelihood is concave in $\theta$. $\endgroup$ – dksahuji Feb 26 '14 at 5:17
  • $\begingroup$ Note that the question asks about convergence, rather than just existence, but with a few restrictions, that, too, may be doable. $\endgroup$ – Glen_b Feb 26 '14 at 6:22
  • $\begingroup$ @Glen_b Can you elaborate? I dont know any such restrictions. Maybe something like restrictions on stepsize in a gradient based optimizer to gaurantee convergence in case of concave function. $\endgroup$ – dksahuji Feb 26 '14 at 11:11
  • 1
    $\begingroup$ @Glen_b That might be true in general but I am not able to see any reason for concave function to not converge to optima within small tolerable value. But I would say that I dont have any practical experience with these and I have just started. :) $\endgroup$ – dksahuji Feb 26 '14 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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