Three Hundred Years Later, a Tool from Isaac Newton Gets an Update

I think the result is primarily relevant from a complexity-theory perspective, showing that this is possible at all in time polynomial in the number n of variables. A big hint is that the paper never explicitly states the degree of that polynomial, but it would need to be at least as large as the degree d of the Taylor expansion used.

The convergence speed depends in a complicated way on the Lipschitz constant of the d-th derivative, but if you ignore that, the number of iterations to reach a fixed target precision is proportional to 1/ln(d). So to halve the number of iterations, you would need to square d, which is bad news if the runtime is already at least exponential in d. It would only make sense if the function you're trying to minimize is extremely costly to compute but the cost of differentiating it d times is negligible in comparison. Even then, there'll be an optimal d beyond which further increases only slow it down.

In the univariate case, if you're doing 1 + d work per iteration for 1/ln(d) iterations, the optimal integer value of d is 4. So at least in that case, going a bit higher than Newton's method can be beneficial.

For late arrivals to this thread: note that the illustration being discussed has been updated (see the Wayback Machine for the old version). The new version probably still does not show the best second-order approximations, but the obvious qualitative errors have been corrected.

Perhaps the graphics designer didn't get the memo. You can see in the panels that it's the same parabola, they've just rotated it in the first panels so it seems to fit the shape of the local curve "better".

I'm not following your objection. To my eye those approximation graphs are indeed 2nd order functions in the 2d plane. But they are perhaps not parabolic for lack of symmetry?

When you say they are not even functions, are you saying because they are not everywhere bijective? Because they look like rotated parabolas to me which means they will have continuous first and second derivatives which is (I think) all you need for Newton’s method isn’t it?

There's actually a separate Wikipedia article about the variant/application of Newton's method being improved upon here: https://en.wikipedia.org/wiki/Newton%27s_method_in_optimizat... Note the italic text at the top of the "Newton's method" article!

I wish we could call the Quake algorithm "fast reciprocal square root". But it's far too late now.

This is highly problem dependent. Sometimes, you get second derivatives almost for free. It all depends on your cost function.

It also depends on your stopping tolerance. Computing a higher order derivative incurs a constant cost, whereas a higher order method converges faster, but not just by a constant. Hence, as you ask for more and more precise results, the ratio of cost of your high order to your low order method will go to zero.

The cost of Newton's method is not so much computing the second derivative anyways, but solving the resulting linear system... So, for small dimensional problems, Newton's method is still the go-to optimization method, it is stupidly efficient. (with a good line search, this partly answers your "I don't see what a decade or two will add")

Weirdly, the original algo is showcased visually, very easy to understand even by 9th graders. While the new one...can't be or quanta woulnd't show it to us just like that?

What I'm trying to state is that if the new algo is so much better, that it can't be explained visually, then the simplicity perhaps was sacrificed, which was what kept the original algo going for 300 years...

> My understanding is that the proposed method is faster in the sense of sampling efficiency (of the cost function to construct the Taylor series), but not in the sense of FLOPS. The higher derivatives do not come for free.

Sure, but as long as this remains cheaper than the process of computing the next convergence, this would still be a net win. For example the article talks about how AI training uses gradient descent and I’m pretty sure that the gradient descent part is a tiny fraction of the time spent training vs evaluating the math kernels in all the layers; therefore taking fewer steps should be a substantial win.

Each iteration is (much) more expensive, but you should be able to get to the final answer in fewer iterations.

Please check this excellent video describing and explaining on 200 years of logic, optimization and constraint programming since the pioneering work of George Boole [1].

Towards the end of the video you can also see Donald Knuth asking questions on the presentation.

[1] Logic, Optimization, and Constraint Programming: A Fruitful Collaboration (2023) [video]:

https://www.youtube.com/live/TknN8fCQvRk

The paper is about Newton's method in optimization.

Why did you replace "quadratic" with "exponential"? Quadratic isn't exponential.

People have tried applying Newton's method and other quasi-Newton methods to ML problems, and my understanding is that it isn't worth it for large problems.

In ML, you care about getting a few digits for a very large, very nonlinear, high-dimensional optimization problem. The cost function is gnarly, it's expensive to evaluate, computing derivatives is even more expensive, and there are many different optima. You don't even really care too much which optimum you get.

The theory of Newton's method (Kantorovich's theorem) says that you obtain quadratic convergence once you're in a small ball surrounding your optimum. How big this ball is depends on the smoothness of the cost function. E.g., if you try to minimize a positive definite quadratic function with Newton's method, you will converge to the minimum in one step (the basin is all of R^n), with the first order necessary equations being equivalent to solving a symmetric positive definite linear system. But if the function is more wild and crazy, the ball may be quite small; if you try to run an unadulterated Newton's method outside this ball, the iteration can easily diverge.

With this in mind, Newton's method is usually used when you want 1) lots of digits (or ALL the digits), 2) you have a good reason to believe you're within the basin of convergence, 3) you know your function has a single global optimum and you're willing to use a damped Newton's method and wait out some linear convergence until you get to the basin of contraction. At least if you're training a neural network, none of this is true. ($)

That said, even if you're minimizing a nice, smooth, univariate function with exactly one optimum, the secant method will get the same result with fewer FLOPs. So, although the order of convergence of secant is lower (in fact, the order is ~1.618), the fact that each iteration is more economic than Newton means that secant will deliver a target error with fewer FLOPs even though it will take more iterations. That said, in my experience, the distinction between "Newton" and "secant" (i.e. quasi-Newton) in low dimensions is less clear cut. Sometimes your Hessian is easy to evaluate and it's simpler to program and run Newton. The difference between these approaches is also pretty minimal in low dimensions... secant might be faster but not that much faster.

This last point also relates to the original paper. It seems likely that this algorithm will have a worse "iteration vs FLOPs" tradeoff even than Newton.

Now, I think the one place where Newton really shines is in interval arithmetic. There are interval Newton methods which can be used to not only compute but prove the existence and uniqueness of a zero for f(x) in R^n. For this reason, they get used for verified numerics and things like rigorously finding all zeros of a function in a compact domain (e.g. by combining with subdivision).

($): Although, actually, I've seen people train neural networks like this. I believe sometimes, if you have a very SMALL neural network (like, tens to thousands of parameters), you once again enter the regime of "modern" optimization and can train a neural network potentially very accurately using Gauss-Newton.