If my understanding is correct, Newton's method and Nesterov accelerated gradient descent have the same "convergence rate"*.

But Newton's method requires more information about the function than does gradient descent, and also requires us to compute the action of the inverse Hessian on the gradient (which costs $$N^3$$ in the general case).

So in what circumstances should we expect Newton's Method to be superior to Nesterov Accelerated Gradient Descent?

*(I know there are various definitions of convergence, like local vs global, one norm vs another, maybe this is where my misunderstanding lies?)

There are two different meaning of 'quadratic convergence': These accelerated gradient methods have quadratic convergence in the sense of $$f(x_k) - f(x^*) = O(k^{-2}),$$ for instance, $$f(x_k) - f(x^*) = 1, 1/4, 1/9, 1/16 ...$$. The achievement here is the achieved faster convergence when compared to plain gradient descent at basically the same computational cost.

The quadratic convergence of Newton method is: there is $$c>0$$ such that $$\|x_{k+1}-x^*\| \le c \|x_k-x^*\|^2$$ for all $$k$$ large enough. For instance, $$\|x_k-x^*\| = 10^{-1}, 10^{-2}, 10^{-4}, 10^{-8},10^{-16}$$.

If Newton method converges it will converge much faster.

• perfect thanks! is there a term we can use to distinguish between these kinds of convergence? Commented Jan 13, 2023 at 19:39
• there is this en.wikipedia.org/wiki/Rate_of_convergence but this is different from the $1/k^2$ thing
– daw
Commented Jan 13, 2023 at 19:42

There are a number of confusions here that are common, especially among people in the computer science and machine learning community.

Already another poster explained the confusion between different meanings of the term "quadratic convergence." This is indeed true, but it is a surface-level issue. Asymptotic convergence rates are nearly irrelevant in practice, because one typically terminates algorithms before the asymptotic regime is reached.

There are deeper reasons for preferring Newton-type methods over Nesterov-type methods. But first, it is important to understand the following points:

1. The $$O(N^3)$$ theoretical cost is irrelevant because practical Newton methods do not build and factor the Hessian. Typically one uses an inexact Newton-Krylov method, in which the Newton linear systems are approximately solved with a Krylov method. This only requires the application of the Hessian to vectors.
2. Applying the Hessian to a vector may be done using automatic differentiation, at a cost roughly equal to evaluating the gradient.
3. The primary difficulty is ill-conditioning, which all algorithms must deal with in some way or another. In Nesterov methods, ill-conditioning increases the number of Nesterov iterations. In Newton-Krylov methods, the ill-conditioning increases the number of (inner) Krylov iterations, but the number of (outer) Newton iterations remains roughly the same.
4. For practical tolerances, a general rule of thumb is that the total number of Hessian-vector products across all Newton iterations will be approximately the same as the total number of Nesterov iterations required to achieve the same accuracy.

With this understood, the real advantages of Newton-type methods are as follows:

• Ability to address ill-conditioning: In Newton-type methods, one has an avenue to address the ill-conditioning: build a preconditioner for the Hessian matrix. In Nesterov methods the ill-conditioning slows down the algorithm and there is little one can do about it.
• Shift burden from nonlinear to linear operations: Hessian vector products are linear operations, whereas evaluating the cost function typically requires nonlinear operations which can be more expensive. Hence it is desirable to shift the computational burden from the nonlinear (Nesterov) iterations, to the linear Krylov iterations.
• Ammortize setup cost: Often there is a set-up cost to evaluating the objective function, gradient, and performing Hessian-vector products at a new point. By doing less outer iterations (each of which requires this set-up cost) and more inner iterations (which don't), one better ammortizes the setup cost.
• Increased opportunities for parallelism: Nesterov iterations are inherently sequential because you have to do one iteration after another. In Newton-type methods, you have less outer sequential iterations, but each of them costs more. This opens up more opportunities for parallelism within each Newton iteration.

This topic is the subject of Chapter 3 of my Ph.D. dissertaion, https://repositories.lib.utexas.edu/handle/2152/75559

• thanks so much for adding this context; as someone "self-learning" most of optim this kind of stuff is hardest to figure out so many thanks. And your 3rd chapter looks really good (much better than mine lmao), I'll go through it carefully soon (after the ICML deadline :)). Commented Jan 13, 2023 at 20:49
• (and ye you caught me as an ML guy ;)) Commented Jan 14, 2023 at 4:10
• PS: can you clarify, is this answer made in the context of convex objectives, or have you had good experience getting Newton-like methods to work on nonconvex problems? Commented Oct 16, 2023 at 13:44