Three Hundred Years Later, a Tool from Isaac Newton Gets an Update
quantamagazine.org
quantamagazine.org
That is, if using Newton's method one could start close to the solution but still not converge, while their method seems much more well-behaved.
I guess that might be a more attractive property than "just" being faster. However not an expert so not sure if other, cheaper alternatives also has this property.
That said, the whole point of their method is to use higher-order derivatives. Admittedly I don't do optimization problems that often, but when I do my function is seldom analytical, and so getting good higher-order derivatives are usually expensive at best and problematic at worst.
They do touch on this in the section about future work, wondering if a quasi-Newton method[2] could be created in a similar vein, using only sparse sampling of the higher-order derivatives.
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.
The illustration of the Newton method is wrong, isn't it? The approximating second order polynomials that were drawn are not really graphs of second order polynomials, they are not even functions... those are parables in the 2D plane, but Newton's method won't work like that... Besides, the convexity of the target function looks negative near to the first guess, the Newton method shall probably miserably fail here
If those are 2nd order functions in the 2d plane, then we don't agree on terminology.
The reason why I feel an expert is that it is clear at first sight to me that if you really implement the Newton method in that situation, the approximating functions that you will get are totally different from those that were drawn in the illustration.
The third parable from the left on the lower left figure, is definitely not a second order approximation to the target function: the convexity is reversed!
Anyways, it's a little graph to illustrate the idea of a second order approximation, I think it does the job.
An improvement on [1], which I vaguely remember using with pen and paper to find minimums of differentiable functions. The original algorithm runs "on a loop" (iteratively) and utilizes the first and second order derivative of a function (f', f''). From the article:
> Newton did it for degree 2. He did that because nobody knew how to minimize higher-order polynomials
The improved version looks a lot more complex but seems to sacrifice simplicity to converge faster to the minimum when implemented as a program.
Trivia: a "single loop" of the Newthon method is famously used in Quake's Fast InvSqrt() implementation [2].
--
1: https://en.wikipedia.org/wiki/Newton's_method
2: https://en.wikipedia.org/wiki/Fast_inverse_square_root#Newto...
I don't see what a decade or two will add to this technique.
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.
It was never the interesting to see the mathematical maneuver to massage the Taylor series into a more digestible form and prove the error bounds.
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...
Yes, weird of Quanta to not include such an example.
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.
Unfortunately not.
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")
Remember that semidefinite programming is often implemented via the interior point method, which is an application of Newton's method with inequality constraints.
Or is it like the unaware rediscovery of Simpson’s Rule:
https://diabetesjournals.org/care/article/17/2/152/17985/A-M...
?
Recently, there has been a body of work following this structure with Taylor expansions of order higher than two [40, 9, 12, 28, 29, 25]. Unlike our paper, these works are in the setting of convex optimization, do not study the complexity of minimizing the regularized Taylor expansion in each iteration [...]
To the best of our knowledge, no efficient algorithm for higher-order Newton methods of degree d > 3 has been presented. In fact, designing such an algorithm is referred to as an open problem in [23, Sec. 1.5] and [25, Sec. 5].
To our knowledge, the only works that establish superlinear rates of local convergence for higher-order Newton methods are [47] and [24] (and the related PhD thesis [23]), the latter of which came to our attention at the time of writing this paper.
Seems highly unlikely it's anything close to the example you posted.
Other iterative methods, like gradient descent, converge toward the true minimum at a linear rate. Newton’s method converges toward it... at an [exponential] rate...
The rate of convergence would scale with the number of derivatives used: Just as using two derivatives allowed Newton to approach the true minimum at a quadratic rate, using three derivatives enabled the researchers to approach it at a cubic rate, and so on.
I'm still confident that medium-term progress on deliberative cognition lies in the very uncool Neat/symbolic direction, but this is the first time I'm really thinking hard about what it would take to crack it the hard, more durable way (i.e. biological verisimilitude).
In terms of the paper itself (https://arxiv.org/html/2311.06374v2), this is by far the most interesting part for this novice, in 1.2:
We prove that our algorithm is well-defined in the sense that the semidefinite programs it executes are always feasible and that the next iterate is always uniquely defined...[, and that the program] has local convergence of order d. Compared to the classical Newton method, this leads to fewer calls to the Taylor expansion oracle (a common oracle in this literature...) at the price of requiring higher-order derivatives.
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.