Re: Computational complexity of finding MLEs?

In article <1132193333.359929.12880@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Yaroslav Bulatov <yaroslavvb@xxxxxxxxx> wrote:
>But how do we know that we even need to compute derivatives of the
>log-likelihood function? For instance, we can estimate the mean
>parameter of the Normal distribution by just averaging the observations
>together. As opposed to logistic regression, where we may have to
>compute derivatives and iterate several times. Are we able to rule out
>the existence of a a special purpose efficient algorithm (like for
>estimating mean of the Normal distribution) for cases where Newton-type
>methods are typically used?

This is a situation which occurs often in complexity. It
is generally the case that there are special cases of highly
reduced complexity. Rational exponents with small powers
are easier to compute; for A*exp(-b*|x-c|^q), the situation
becomes markedly worse for q not an integer, and worse for
q < 1, and even worse for q < .5.


--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@xxxxxxxxxxxxxxx Phone: (765)494-6054 FAX: (765)494-0558
.

Relevant Pages

  • Re: Article in Scientific American
    ... The basic theorems are not at all difficult, ... using one-sided derivatives. ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math)
  • Re: Goodness of fit measures for a distribution
    ... Whether the normal distribution gives good enough results ... it is of great importance. ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.stat.math)
  • Re: stochastic differential equation vs differentiation of probability function.
    ... derivatives of high order, are obtained by the usual methods ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math)
  • Re: Questions: the central limit theorem when n is a random variable.
    ... > The central limit theorem: ... > Does Sapproaches Normal distribution? ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.stat.math)
  • Re: Derivation as de Moivre did of the normal distribution
    ... >Does anybody know the derivation of the normal distribution as was ... Just as the sum is an approximation ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math)