Papers › The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
Dmitry Kovalev, Alexander Gasnikov
In this paper, we study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. Arjevani et al. (2019) established the lower bound Ω(ϵ^(-2/(3p+1))) on the number of the p-th order oracle calls required by an algorithm to find an ϵ-accurate solution to the problem, where the p-th order oracle stands for the computation of the objective function value and the derivatives up to the order p. However, the existing state-of-the-art high-order methods of Gasnikov et al. (2019b); Bubeck et al. (2019); Jiang et al. (2019) achieve the oracle complexity 𝒪(ϵ^(-2/(3p+1)) log(1/ϵ)), which does not match the lower bound. The reason for this is that these algorithms require performing a complex binary search procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with 𝒪(ϵ^(-2/(3p+1))) p-th order oracle complexity.
In Syntology View this paper on Syntology: its repositories, every harvested function with whether it ran, its licence and the call to fetch it.
Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections