In standard optimization, we usually think in terms of first or second derivatives. Gradient descent uses a linear approximation of a function, while Newton’s method uses a quadratic one. But if a function is sufficiently smooth—meaning its higher-order derivatives don't change too wildly—we can theoretically build even better local models using higher-order Taylor expansions.
Recent research has focused on high-order tensor methods, which utilize the $p$-th order derivative to achieve convergence rates that were previously thought to be purely theoretical. By moving beyond the Hessian, these methods provide a roadmap to the fundamental "speed limits" of convex optimization.
The Intuition of Higher Order Smoothness
The core idea, as explored by Dmitry Kamzolov, Alexander Gasnikov, and colleagues in Exploiting higher-order derivatives in convex optimization methods, is that a $p$-th order Taylor expansion provides a much tighter "envelope" around a function than a simple parabola.
If we know the $p$-th derivative is Lipschitz continuous, we can construct a local polynomial model of degree $p$. By adding a regularization term (similar to cubic regularization for Newton's method), we ensure that we don't move too far into regions where our $p$-th order approximation becomes unreliable. This allows the algorithm to take significantly larger, more informed steps toward the minimum than a first-order method ever could.
Hitting the Theoretical Speed Limit
For decades, there was a gap between the best known algorithms and the theoretical lower bounds for optimization complexity. For a function with Lipschitz $p$-th derivatives, the fundamental limit of how fast any algorithm can converge is $O(\epsilon^{-2/(3p+1)})$.
In 2019, two independent groups—Alexander Gasnikov et al. in Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives and Bo Jiang, Haoyue Wang, and Shuzhong Zhang in An Optimal High-Order Tensor Method for Convex Optimization—closed this gap.
They demonstrated that by integrating $p$-th order information into an accelerated framework, one can achieve this optimal rate. This means that as $p$ increases, the number of iterations required to reach a certain precision $\epsilon$ drops dramatically. For example, while a first-order accelerated method ($p=1$) converges at $O(\epsilon^{-1/2})$, a third-order method ($p=3$) converges at $O(\epsilon^{-1/5})$.
Eliminating Computational Overhead
While these "optimal" methods were theoretically perfect, early versions were computationally expensive. They often required a "binary search" or an inner loop to find the next point, adding a logarithmic factor to the complexity.
Dmitry Kovalev and Alexander Gasnikov addressed this in The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization. They integrated high-order derivatives into the Accelerated Hybrid Proximal Extragradient (A-HPE) framework. This approach achieved the optimal $O(\epsilon^{-2/(3p+1)})$ rate without the overhead of binary searches, making high-order methods not just a theoretical curiosity but a more practical tool for high-precision optimization.
Beyond Simple Minimization
The power of high-order information isn't limited to standard convex minimization. Researchers have extended these principles to more complex landscapes:
- Saddle Point Problems: Petr Ostroukhov and Pavel Dvurechensky developed $p$-th order methods for strongly convex-strongly concave saddle point problems, achieving global linear convergence.
- Non-Convex Landscapes: In Recent Theoretical Advances in Non-Convex Optimization, Eduard Gorbunov and others highlight how tensor methods can escape saddle points and find second-order stationary points more efficiently than gradient-based approaches.
- Stochastic Settings: Artem Agafonov and Dmitry Kamzolov have extended these methods to handle inexact or stochastic derivatives, showing that even with noisy data, the benefits of higher-order geometry can be preserved.
By matching the oracle complexity lower bounds—as confirmed by Site Bai and Brian Bullins in Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity—this line of research effectively defines the ultimate efficiency of optimization for smooth functions.