Gauss-Newton vs gradient descent vs Levenberg-Marquadt for least squared method

Question

I need to clarify some idea I have in my mind about linear and non-linear regressions. Whatever I know about this topic comes from the book of Taylor "Introduction to error analysis": a set of measurements ${x_i}$ and ${y_i}$ for $i= 1, 2, \dots N$ are assumed to have a trend according to a specific function $y = f(x)$, the discrepancies between the measured value $y_i$ and the function $f(x_i)$ are assumed to follow a Gaussian statistics with variance $\sigma_{y}^2$. Applying the principle of maximum likelihood, the best estimation of the parameters that define $f(x)$ are that ones that minimizes the function.

$$ \chi^2 = \sum_{i = 1}^{N} \frac{(y_i - f(x_i))^2}{\sigma_y^2} $$

This is known as least squared method.

Now in the case of a straight line $f(x) = Ax + B$ the estimation of the parameters is a straightforward job: from a couple of derivatives you figure out $A$ and $B$ and you properly identify $f(x)$. In the more general case $f(x)$ is a polynomial of order $M$, the computation will be more elaborated, but the job is easy at least in principle. In both Matlab and Python there is an implemented function ( polyfit(x, y, M) and np.polyfit(x, y, M) ) that seems to be not difficult to theoretically understand and practically apply to experimental data.

However when the function $f(x)$ is not a polynomial then more complicated numerical methods are necessary in order to figure out the parameters that define $f(x)$. From some google researches I realized that the most popular techniques are

1. Gauss-Newton algorithm

2. Gradient descent algorithm

3. Levenberg-Marquadt algorithm

Matlab and Python have an implemented function called "curve_fit()", from my understanding it is based on the latter algorithm and a "seed" will be the basis of a numerical loop that will provide the parameter estimation.

I would like to know in which case it is better to use the first algorithm, in which case the second algorithm is better and in which case the third one is better.

I would be happy if you suggest me any book or other types of material that provide me a (not too) short explanation of those techniques so that each time I have to fit a curve I can understand which is the better method for me.

Finally I would like to know what you would do if you need to provide a Gaussian fit on a set of experimental data. Personally I did a polyfit of second order of the logarithm of the experimental data. I saw on many Matlab and Python webpages that people uses that "curve_fit" that is, from my understanding, the Levenberg-Marquadt method. Which is the best way to perform these fit from your point of view?

Answer 1

The Levenberg-Marquardt method is the most effective optimization algorithm, to be preferred over the methods of steepest descent and Gauss-Newton in a wide variety of problems. You might find this explanation by Henri Gavin instructive:

The Levenberg-Marquardt curve-fitting method is actually a combination of the two other minimization methods: the gradient descent method and the Gauss-Newton method. In the gradient descent method, the sum of the squared errors is reduced by updating the parameters in the steepest-descent direction. In the Gauss-Newton method, the sum of the squared errors is reduced by assuming the least squares function is locally quadratic, and finding the minimum of the quadratic. The Levenberg-Marquardt method acts more like a gradient-descent method when the parameters are far from their optimal value, and acts more like the Gauss-Newton method when the parameters are close to their optimal value.

The Levenberg-Marquardt algorithm may fail to converge if it begins far from a minimum. There exist ways to accelerate the convergence, as explained here.