Optimal High-Order Tensor Methods for Convex Optimization

120 concepts58 papers1 proposal

When we minimize a convex function, we typically rely on local approximations. First-order methods like gradient descent approximate the function as a flat plane, while second-order methods like Newton's method approximate it as a quadratic bowl.

High-order optimization, often called tensor methods, extends this logic to its natural mathematical conclusion. If a function is highly smooth—meaning its higher-order derivatives exist and do not change abruptly—we can construct a local model using a $p$-th order Taylor expansion. By capturing more structural information about the function's local geometry, these methods can take much larger, more effective steps toward the optimum.

However, simply building a higher-degree polynomial is not enough. For years, a significant gap existed between the theoretical speed limits of what higher-order derivatives should achieve and the actual performance of the algorithms we had. Closing this gap required a fundamental rethinking of how we regularize polynomial approximations, how we accelerate steps, and how we solve the resulting subproblems.

The Speed Limit of High-Order Smoothness

To understand why high-order tensor methods are powerful, we must look at their iteration complexity. For a convex function with a Lipschitz continuous $p$-th derivative, the fundamental mathematical lower bound dictates that no deterministic algorithm can converge to an $\epsilon$-accurate solution faster than:

$$\mathcal{O}\left(\left(\frac{1}{k}\right)^{\frac{3p+1}{2}}\right) \text{ or equivalently } \mathcal{O}\left(\epsilon^{-\frac{2}{3p+1}}\right)$$

As the derivative order $p$ increases, the exponent improves dramatically. For example, while first-order accelerated gradient descent ($p=1$) converges at a rate of $\mathcal{O}(k^{-2})$, a third-order tensor method ($p=3$) can theoretically converge at a blistering $\mathcal{O}(k^{-5})$.

Crucially, as Agarwal et al. demonstrated, even with access to infinitely differentiable functions and arbitrarily high-order derivatives, optimization algorithms are still bound by polynomial complexity relative to the target error. We cannot achieve dimension-free, exponentially fast (logarithmic) convergence for general convex functions using local Taylor oracles alone. This reality makes finding algorithms that exactly hit the polynomial lower bound a primary goal of optimization theory.

Why Greedy Taylor Expansion Fails

The most intuitive way to design a $p$-th order method is to be greedy: construct the $p$-th order Taylor expansion at your current point and minimize it to find the next point.

This naive approach fails for two reasons:

  1. Unboundedness and Non-Convexity: A Taylor polynomial of degree 3 or higher is generally not convex, and it often plunges to negative infinity far away from the expansion point. A greedy optimizer would simply jump to infinity.
  2. The Acceleration Bottleneck: Even if the expansion happens to be well-behaved, greedy minimization does not yield the optimal accelerated convergence rate.

To fix the first problem, we must regularize the Taylor expansion. As explained by Gasnikov et al., we add a higher-order power term—typically of degree $p+1$—to the Taylor polynomial. This penalty term acts as an anchor. It tames the wild oscillations of the high-degree polynomial, guarantees that the overall subproblem remains strictly convex, and ensures that the algorithm never steps outside the local neighborhood where the Taylor expansion is a trustworthy guide.

To fix the second problem, we must move away from explicit, greedy steps. As Bubeck et al. pointed out, achieving optimal acceleration requires an implicit step framework. Instead of choosing the next iterate based solely on the derivatives at the current point, the next iterate must be defined implicitly by its relationship to the gradient at the future point.

The Mechanics of Optimal Acceleration

To operationalize these implicit steps without getting stuck in an infinite computational loop, researchers embedded regularized tensor updates into proximal and extragradient frameworks.

Parallel breakthroughs by Bubeck et al., Jiang et al., and Gasnikov et al. showed that Nesterov-style momentum and the Accelerated Hybrid Proximal Extragradient (A-HPE) framework could be systematically generalized to higher-order derivatives.

Instead of taking a single explicit step, these frameworks maintain multiple sequences of iterates (such as a look-ahead point, a conservative point, and a momentum point). At each iteration, the algorithm solves a proximal subproblem based on the regularized Taylor expansion. This multi-point feedback loop ensures that the massive steps enabled by high-order smoothness are perfectly balanced, preventing oscillations and unlocking the optimal $\mathcal{O}(\epsilon^{-2/(3p+1)})$ convergence rate.

[Current Iterate] ---> Compute p-th Order Derivatives
                             |
                             v
                 Construct Taylor Expansion 
                 + (p+1)-th Order Regularizer
                             |
                             v
                 [A-HPE / Extragradient Framework] 
                 Balances momentum and implicit steps
                             |
                             v
                       [Next Iterate]

Early iterations of these optimal algorithms were bogged down by a major practical flaw: they required an expensive binary search procedure at every single step to find the correct step size, adding a logarithmic complexity factor to the runtime. Kovalev et al. eliminated this overhead by introducing a high-order generalization of the Korpelevich extragradient method as an inner loop. This allowed the algorithm to satisfy the strict proximal requirements using only a constant number of derivative evaluations on average per main iteration, making the acceleration truly optimal.

Making Tensor Subproblems Tractable

The elephant in the room for high-order optimization is the cost of the subproblem. Minimizing a regularized 3rd or 4th-order polynomial at every step sounds nightmarishly expensive, potentially wiping out any gains from a lower iteration count.

Several key insights have made these methods computationally viable:

  • Dynamic and Inexact Accuracies: You do not need to solve the complex tensor subproblem perfectly. Nesterov proved that you can solve subproblems with surprisingly low accuracy early on, dynamically tightening the precision only as you get closer to the global optimum. This "contracting proximal" strategy preserves the fast global convergence rate while slashing per-iteration costs.
  • Reduction to Linear Systems: For specific problem structures, minimizing a high-degree polynomial can be simplified. Bullins demonstrated that third-order optimization subproblems can be solved efficiently by reducing the minimization of high-degree Taylor polynomials to a short sequence of standard linear system solves, making them highly effective for smoothing non-smooth objectives.
  • Specialized Subproblem Solvers: Instead of generic optimization routines, modern implementations use tailored inner-loop solvers. Kamzolov et al. utilized the Bregman Distance Gradient Method to handle higher-order derivatives, bringing the practical per-iteration cost of third-order methods down to a level competitive with standard second-order Newton methods while unlocking global superlinear convergence.

Emulating High-Order Speed with Lower-Order Data

Perhaps the most surprising twist in this research direction is that you can sometimes reap the benefits of high-order convergence without actually calculating high-order tensors.

For instance, Hanzely et al. revisited the classical second-order Newton method. They showed that by applying a clever step-size schedule based on local Hessian norms—a method called "Root Newton"—an algorithm can achieve a global convergence rate of $\mathcal{O}(k^{-3})$. This matches the speed of a third-order tensor method while completely avoiding the grueling task of computing or storing third-order derivative tensors.

By combining the geometric precision of Taylor expansions with the stability of regularized proximal frameworks, high-order tensor methods map out the absolute limits of optimization speed, proving that smoothness can always be translated into algorithmic acceleration.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_iteration_complexity_6065ba73,
  title = {optimal iteration complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-iteration-complexity/rdr_6065ba734767456e81b70bb4cfd2ff78},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimal_iteration_complexity_6065ba73_v1,
  title = {optimal iteration complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-iteration-complexity/rdr_6065ba734767456e81b70bb4cfd2ff78/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake