Optimal High Order Tensor Methods for Convex Optimization

This direction is merged into another direction: optimal iteration complexity. Its last version stays readable and citable here.

Version 1 of 117 papers25 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_high_order_tensor_methods_for_co_a95c68b8,
  title = {Optimal High Order Tensor Methods for Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-high-order-tensor-methods-for-convex-optimization/rdr_a95c68b891ab43e2a166ec86fc036337},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimal_high_order_tensor_methods_for_co_a95c68b8_v1,
  title = {Optimal High Order Tensor Methods for Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-high-order-tensor-methods-for-convex-optimization/rdr_a95c68b891ab43e2a166ec86fc036337/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}