1
$\begingroup$

I have a function I'm minimizing. I'm using conjugate gradient descent and the Newton algorithm.

I am experiencing that the Newton algorithm is absurdly faster. Like, it finishes it 5-6 iterations, while the conjugate gradient takes 2000 iterations (and regular gradient descent takes 5000 iterations).

I know what's causing the problem too: the learning rate. In Newton's method, a learning rate of $\alpha = 1$ works. But I can't use this in the gradient descent methods, where such a choice of $\alpha$ diverges. In these methods, I am forced to use $\alpha = 0.01$.

But anyways, 5 iterations vs thousands of iterations is still an absurd difference. Is Newton's method really this good??!

$\endgroup$
1
$\begingroup$

The relative performance of different optimization algorithms depends a lot on the particular function you are minimizing. We certainly can't tell you whether it is really that good for your particular function without knowing what specific objective function you are looking at, but it certainly seems possible to me.

There are some functions where Newton's method will be vastly better. For instance, with a quadratic function, where a few iterations of Newton's method will suffice to get a very precise answer; yet gradient descent might take many iterations to get similar precision. This can be partly explained theoretically by understanding that Newton's method often converges quadratically or faster (though for some bad cases it can converge more slowly), while gradient descent typically converges sub-linearly for convex functions or linearly for strongly convex functions (and for bad cases it can converge much more slowly), so in a theoretical sense Newton's method often requires fewer iterations than gradient descent.

Conversely, there are also some functions where (conjugate) gradient descent will be better, for instance because one iteration of gradient descent is much faster than one iteration of Newton's method. One example would be training deep neural networks, where gradient descent works very well but Newton's method would be painfully slow due to the very high dimensionality and the time it takes to do a single iteration of Newton's method.

I would caution against drawing a conclusion about the performance of Newton's method on all functions, based on an empirical observation of its performance on one particular function (a sample size of $n=1$).

$\endgroup$
  • $\begingroup$ @seeit, I apologize for misunderstanding what you wanted to know. I have edited my answer; I hope that it is more helpful now. I would prefer if you could show me more patience in the future. We are all volunteers here, volunteering our time to help others. I don't always get it right the first time and I am happy to correct my mistakes when I am made aware of them. $\endgroup$ – D.W. Oct 3 '19 at 19:05
  • $\begingroup$ wow u are such a nice guy $\endgroup$ – seeit Oct 3 '19 at 20:33

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.