Researchers unlock new potential in Newton’s method, 300 years after its creation
For over three centuries, researchers have relied on a powerful algorithm developed by Isaac Newton to tackle complex problems in logistics, finance, computer vision, and even pure math.
This simple yet effective method provides a remarkable way to approximate solutions when direct calculations are too complex. But even a method devised by one of history’s greatest minds has its limitations — it doesn’t work well on all functions.
That, however, may be about to change.
A team of researchers has now expanded Newton’s method, making it more powerful than ever.
Last summer, Amir Ali Ahmadi of Princeton University, along with his former students Abraar Chaudhry (now at the Georgia Institute of Technology) and Jeffrey Zhang (now at Yale University), introduced the latest breakthrough.
Their work extends Newton’s method to efficiently handle the broadest class of functions yet, pushing the centuries-old technique to new heights.
“Newton’s method has 1,000 different applications in optimization,” Ahmadi said. “Potentially our algorithm can replace it.”
From Newton to Now
Mathematical functions take inputs and produce outputs, but finding the minimum value—the smallest possible output—has often been a challenge for mathematicians. Many functions have multiple variables and intricate shapes, making direct calculations impossible.
In the 1680s, Isaac Newton devised a method to tackle this problem using two key pieces of information: the slope of the function (first derivative) and how that slope changes (second derivative).
His approach involves approximating a complex function with a simpler quadratic equation, solving for its minimum, and repeating the process until reaching the true minimum.
Newton’s method is much faster than other techniques like gradient descent, which are widely used in today’s machine learning models.
Mathematicians have long tried to improve Newton’s method. In the 19th century, Russian mathematician Pafnuty Chebyshev introduced a version that used cubic equations (with an exponent of 3) to approximate functions, but it didn’t work for functions with multiple variables.
Most recently, Yurii Nesterov of Corvinus University of Budapest developed a method in 2021 that could handle multiple variables using cubic equations. However, extending it to more complex equations, like quartic or quintic, made it inefficient. Despite this limitation, his work was a major breakthrough in optimization.
A new take on Newton’s method
Ahmadi, Chaudhry, and Zhang built on Nesterov’s work to develop an algorithm that handles any number of variables and derivatives while staying efficient—something that was previously thought impossible.
However, this required the researchers to break down a complex mathematical challenge first.
Newton’s method had a major limitation—it lacked a fast, general-purpose way to find the minima of functions with high exponents.
However, some functions have specific characteristics that make them easier to minimize.
In their new work, Ahmadi, Chaudhry, and Zhang prove that it’s always possible to create approximating equations with these favorable characteristics.
The trio showed how to adjust these equations to run Newton’s method efficiently.
The trio discovered that an equation becomes easier to minimize if it has two key properties.
First, it should be bowl-shaped, or “convex.” This means it has only one valley instead of many, eliminating the possibility of mistaking an arbitrary valley for the lowest one.
Secondly, the equation can be written as a sum of squares.
In recent years, mathematicians have developed techniques to minimize equations with large exponents, as long as they meet these two conditions—convexity and sum of squares.
However, these techniques didn’t apply to Newton’s method because, in most cases, the Taylor approximation used in the process doesn’t naturally have these properties.
Using a technique called semidefinite programming, the researchers found a way to wiggle the Taylor approximation just enough to make it both a sum of squares and convex.
The trio simply added a fudge factor to the Taylor expansion, changing it into an equation with two desired properties.
“We can change the Taylor expansion a bit to make it simpler to minimize. Think of the Taylor expansion, but modified a little bit,” Ahmadi said.
Using this modified version of the Taylor expansion, Ahmadi and his colleagues showed that their algorithm would still converge on the true minimum of the original function even though it involved arbitrarily many derivatives.
They also discovered that the rate of convergence increases with the number of derivatives used.
Just as Newton’s method, using two derivatives converges at a quadratic rate.
With this method, Ahmadi, Chaudhry, and Zhang have created a more powerful version of Newton’s technique, enabling it to reach a function’s true minimum in fewer iterations than previous techniques.
However, each iteration of this new algorithm is still computationally more expensive than methods in practice today, making its implementation challenging.
However, as underlying computational technology becomes less expensive with time, the method devised by the teacher-students team could be used in sorts of applications, including machine learning.
“Our algorithm right now is provably faster, in theory,” Ahmadi said. He’s hopeful, he added, that in 10 to 20 years, it will also be so in practice.
Source: Interesting Engineering
Hofstadter’s Butterfly Lands at Last – A 50-Year Quantum Mystery Solved
Researchers unlock new potential in Newton’s method, 300 years after its creation/Researchers unlock new potential in Newton’s method, 300 years after its creation