# An Optimal High-Order Tensor Method for Convex Optimization

arXiv: https://arxiv.org/abs/1812.06557 · HTML: https://mlsanity.com/paper/1812.06557/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2018.

## Built on by (most cited first, 12 of 12)

- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness](https://mlsanity.com/paper/2112.01118/) (2021)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [Understanding Riemannian Acceleration via a Proximal Extragradient Framework](https://mlsanity.com/paper/2111.02763/) (2021)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexity](https://mlsanity.com/paper/2409.10773/) (2024)
- [Non-Euclidean High-Order Smooth Convex Optimization](https://mlsanity.com/paper/2411.08987/) (2024)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)

## Abstract (arXiv)

This paper is concerned with finding an optimal algorithm for minimizing a composite convex objective function. The basic setting is that the objective is the sum of two convex functions: the first function is smooth with up to the d-th order derivative information available, and the second function is possibly non-smooth, but its proximal tensor mappings can be computed approximately in an efficient manner. The problem is to find -- in that setting -- the best possible (optimal) iteration complexity for convex optimization. Along that line, for the smooth case (without the second non-smooth part in the objective), Nesterov (1983) proposed an optimal algorithm for the first-order methods (d=1) with iteration complexity O( 1 / k^2 ). A high-order tensor algorithm with iteration complexity of O( 1 / k^{d+1} ) was proposed by Baes (2009) and Nesterov (2018). In this paper, we propose a new high-order tensor algorithm for the general composite case, with the iteration complexity of O( 1 / k^{(3d+1)/2} ), which matches the lower bound for the d-th order methods as established in Nesterov (2018), and Shamir et al. (2018), and hence is optimal. Our approach is based on the Accelerated Hybrid Proximal Extragradient (A-HPE) framework proposed in Monteiro and Svaiter (2013), where a bisection procedure is installed for each A-HPE iteration. At each bisection step a proximal tensor subproblem is approximately solved, and the total number of bisection steps per A-HPE iteration is bounded by a logarithmic factor in the precision required.