The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
Authors: Dmitry Kovalev
Alexander Gasnikov
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
tensor methods
high-order optimization
optimal algorithms

Abstract: 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 $\Omega\left(\epsilon^{-2/(3p+1)}\right)$ on the number of the $p$-th order oracle calls required by an algorithm to find an $\epsilon$-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 $\mathcal{O}\left(\epsilon^{-2/(3p+1)} \log (1/\epsilon)\right)$, 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 $\mathcal{O}\left(\epsilon^{-2/(3p+1)}\right)$ $p$-th order oracle complexity.

The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
Dmitry Kovalev KAUST
Alexander Gasnikov MIPT IITP RAS, HSE
dakovalev10gmail com
gasnikov@yandex. .ru
Abstract
In this paper, we study the fundamental open question of finding the optimal high- order algorithm for solving smooth convex minimization problems. (Arjevani al. (2019) established the lower bound Ω (e 2/(3++1)
the number of the p-th order oracle calls required by an algorithm to find an e-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. (2019h); Bubeck et al. (2019); Jiang et al. 2019) achieve the oracle complexity O (3p+1) log
which does not match the lower bound. The reason for this is that these algorithms require performing complex binary search procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with (e 2/( p-th order oracle complexity.
Introduction
Let Rdd be finte-ddimensional Euclidean space and let f(x): Rd - TR be convex, p times continuously differentiable function with Ly-Lipschitz p-th order derivatives. Our goal is to solve the following convex minimization problem:
="= f(x). zER
In this work, assume access the p-th order oracle associated with function f(z). That is, given an arbitrary point x E Rdd, we can compute the function value and the derivatives of function f(x)) up to order p.
First-order methods. When 1, first-order methods, such gradient descent, are typically used for solving problem ( The lower bound Q(c-1/2) the number of the gradient evaluations required by these algorithms to find an e-accurate solution was established by Nemirovskij and Yudin (1983); Nesterov (2003), while the optimal algorithm matching this lower bound is called Accelerated Gradient Descent and was developed by Nesterov 1983).
Second-order methods. In contrast the first-order methods, the understanding of the second- order methods (p 2) was developed relatively recently. Nesterov and Polyak (2006) developed the cubic regularized variant of Newton's method. This algorithm achieves global convergence with
Kiin Abdullah University of Science Technology, Thuwal, Saudi Arabia
Moscow Institute of Physics and Technology. Dolgoprudny, Russia
I Institute Information Transmission Problems RAS, Moscow, Russia
National Research University Higher School of Economics, Moscow, Russia
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Comparison of the first-order, second-order and high-order methods for smooth convex optimization the oracle complexities (see Definition 3 which depend on the smoothness constant Lp (see Assumption T.. the distance to the solution R (see Assumption 2p, and the accuracy (see Definition
Algorithm Reference
Oracle Complexity
Order
Nesterov 1983
o
(1118/66 1/2)
First-Order Methods (p = 1)
Lower Bound (Nemirovskij and Yudin
1983
Ω
(11122/6
Nesterov and Polyak
2006
o
(12210/0))22
Nesterov 2008
o
(L2)))))1 1/3
Second-Order Methods (p = 2)
Monteiro and Svaiter 2013
/c)2/ log(1/c) (L211 /c) 2/7
Algorithm This Paper)
o
(L22111))277
Lower Bound Arrevani et
2019
(c12R%/c)//7
Nesterov 2021a
(11pR111/0) (ompl1/)) 11)
Nesterov 2021a
o
(L, 1/(t1//)
High-Order Methods (p 2
o RL, /e) 3/(3p1111 log(1/e)
Gasnikov al. 2019b
Algorithm
This Paper)
o (L,110+1 (2)2((001111
f (Lp /c) 12)2((80tt))
Lower Bound AArjevani et al. 2019
the oracle complexity Occ-1/2), which cannot be achieved with the standard Newton's method. Nesterov (2008) also developed accelerated version of the cubic regularized Newton's method with O (E 173) second-ordes oracle complexity. A few years later. Monteiro and Svaiter (2013) developed the Accelerated Hybrid Proximal Extragradient (A-HPE) framework and combined it with trust region Newton-type method. The resulting algorithm, called Accelerated Newton Proximal
Extragradient (A (A-NPE), achieved the second-order oracle complexity of O (E-2/7 log(1/e)). In 2018, Arjevani et al. 2019) established the lower bound Ω (e -277 on the number of the oracle calls required by algorithm to find c-accurate solution which is almost achieved by the A-NPE algorithm of Monteiro and Svaiter (001)). up to the logarithmic factor (og(1/e) However, the optimal second-order algorithms for solving smooth convex minimization problems remain be unknown.
High-order methods. the case when p > 2, the situation is very similar to the second-order case. [Nsterov]e (2021a) developed the generalization of the cubic regularized Newton method to the high-order case and called them tensor methods. [Nsterov (2021a) provided both aonaaccleedteed and accelerated p-th order tensor methods with the oracle complexity O (E 1/p) and O (e-1/(++1) respectively Later, three independent groups of researchers (Gasnikov al. 2019a, Bubeck et al. 2019 Jiang et al. 2019) used the A-HPE framework to develop the near-optimal tensor methods with the oracle complexity O (c-2/(3p+1) log(1/e)). Similarly to the case 2, these algorithms match the lower complexity bound Ω (e-2((pp+)) of Arjevani et al. 20119). up to the logarithmic factor log(1/c).
Nesterov)(202la)
'There is also work of Agarwal and Hazan 2018). which provides the lower complexity bounds for high-order optimization. However, their lower bounds are worse than the lower bounds Arjevvvi et al. (2019) Nesterov aa) also provided the lower complexity bounds that coincide with the lower bounds of Arjevani 2019).

---

1.1 Main Contribution: Optimal Second-Order and High Order Methods
The review of the second-order and high-order methods that we made above identifies the following fundamental open question:
Can we design an optimal p-th order algorithm (p 2 for solving smooth convex minimization problems with the oracle complexity matching the lower bounds?
The lack of an answer to this question reveals significant gap in the understanding of the high-order optimization compared to the first-order optimization. We give a positive answer to this question. That is, we provide the first optimal high-order algorithm with the y-th order oracle complexity O (e (=2/(9)+2) that matches the lower bounds of Arjevani et al. 2019). This is the main contribution of our work.
1.2 Related Work
High-order and second-order methods have attracted lot of interest recently. Relevant works include but are not limited to superfast recdnd-order methods (Nesterov 2021c), second-order methods
with gradient regularization (Mishchenko) 202 Doikov et al. 2022 Doikov and Nesterov 202I).
high-order methods for non-smooth optimization via smoothing technique (Bullins) 22000), and ball-constrained optimization Carmon al. (2020 2021). 1) A more detailed review of recent advances
in high-order optimization can be found in the work of Kamzolov et al. (2022).
High-order methods for variational inequalities. Monteiro and Svaiter (2012) also developed second-order methods for solving monotone variational inequalities and inclusions problems for operators with Lipschitz continuous derivatives, which were generalized to the high-order setting by Bullins and Lai 2022); Jjann and Mokhtari (2022). However, similarly to the near-optimal high-order methods for minimization problems (Monteiro and Svaiter] 2013) Gasnikov et al. (019b)), these algorithms have additional logarithmic factors in the complexity that appear due to the requirement of performing the binary search procedure.
Recently, Lin et al. (022);; ; Adil et al. (2022) removed the extra logarithmic factors and provided high-order methods for solving monotone variational inequalities and inclusions problems without any binary search procedures. Moreover, [in et al. (2022) established lower complexity bounds that matched the proposed algorithms. Hence, the problem of finding optimal high-order algorithms for solving variational inequalities and inclusions problems is solved.
In our paper, we solve similar problem of finding optimal high-order methods for solving smooth convex minimization problems. Note that this problem is much more challenging because optimal algorithms for solving variational inequalities and inclusion problems are typically much simpler and do not require utilising acceleration techniques.
Concurrent work of Carmon et al. (2022). The question of finding optimal high-order methods for solving smooth convex minimization problems solved recently in the concurrent work of Carmon et al. (2022). However, their approach is substantially different from the approach used in this work, and their paper appeared arXiv 11 days later than ours.
1.3 Paper Organization
Our paper is organized as follows: (i) in Section 2 we briefly introduce the tensor approximations and provide necessary assumptions and definitions; (ii) in Section 3] we describe the existing near-optimal high-order methods and identify their main flaws that prevent them from being optimal and practical algorithms; (iii) in Section 4 we describe the development of our optimal high-order algorithm and provide its theoretical convergence analysis.
Preliminaries
By ||: Rd R and R x - R, denote the standard Euclidean norm and scalar product on ddd Given a p times continuously differenniable function g(x): Rd - IR and index

---

E by V'g(=)[h]" R + R we denote the following homogeneous polynomial:
O'g
V'g(>)[['= Σ
(x)
his ...
(2)
Jzy Jzy,
where x = (21,.... E Rd, = (h1...... ha) E R and
0'g
Jzi ... Dz (x)
(3)
the i-th order partial derivative of function g(x) at point a with respect to variables ........ J. For instance, i = 1, then V [x)))[] = (Vg(z), h), where Vg(a) E IRd the gradient of function g(x); if 2, then [M] = (()),, h),, where f² E Rdxd is the Hessian of function f(x). We can write the p-th order Taylor approximation of function (xx) at point g4:
(e .(=) + Σ V'g(=)[<=>) x =],
(4)
It is well known that the Taylor polynomial (2 2) approximates function g(æ), if point r is close enough to point 2:
(xz) = (2; 2) + Rg 2)|| - =
(5)
where ()): IR + R is a function that satisfies lim + 12 2) = O.
As mentioned earlier, we assume that the objective function (xx of the main problem IT is p times continuously differentiable and has Lp-Lisschizz p-th order derivatives. It is formalized via the following definition.
Assumption 1. Function f(x) is p-times continuously differentiable, convex. and has Ly- Lipschitt p-th order derivatives, i.e., for all Iı, E Rd the following inequality holds:
max V (( [4] V f(z))[b]] h E Rd, || s 1} S Lpl|=1 - x2l.-
Theorem 1 of Nesterov 2021a implies that under Assumption function f(z) has the following convex upper bound:
PM
f(z) s (1;2)
=||
(6)
(p+ 1)!
where M 2 Lp and 2 E Rdd Hence, an obvious approach to solving problem I is to perform the minimization of this upper bound instead of minimizing the function f(:). This approach naturally leads to the following iterative process:
pM
A+1 Arg min (x; DERd
11
2+1 11
(p+ 1)!
In the case p 2, this iterative process is known the cubic regularized Newton's 's method of Nesterov and Polyak (2006), and in the case > 2, it is known as the tensor method of Nesterov (2021a). Minimization procedures similar 7 widely used in high-order optimization methods. will also be used in the development of our optimal algorithm.
We also have the following assumption which requires problem ( to have at least a single solution x² E Rdd is a standard assumption for the majority of works on convex optimization.
Assumption 2. There exists a constant R > O and at least a single solution x" to problem (I) such that I|xe0 - x=1l S R, where x E Rdd the starting point that we use as an inpul for given algorithm for solving the problem.
Finally, we have the following definitions that formalize the notions of e-accurate solution of problem, p-th order oracle call, and oracle complexity of an algorithm. Definition 1. We call vector å E Rdd an c-accurate solution of problem ① ffr a given accuracy <> 0 satisfies f(t) - Sc.
Definition 2. Given arbitrary vector E Rd by the p-th order oracle call x, we denote the computation of the function value fxx and the derivatives V v= 5 (x))(.
Definition 3. By the p-th order oracle complexity of p-th order algorithm for solving problem (1)
we denote the number of p-th order oracle calls required by the algorithm to find an e-accurate solution of the problem for given accuracy 0.

---

Algorithm A-HPE Framework
1: input: x0 = = E R
2: parameters: o E [0, K (1,2,
3: 8-1 =1
4: for h = 0, 1,.......
K ,
do
5: compute f k+1
E R A > 0 such that
|VS + X (x) xg)1| S x 1 -xygl
(8)
where a IRd and og (0, 1] are defined
oy ogat + (1 on)ay = = 13/B2
(9)
and Th > and Bx > 0 are defined by the following system:
Bk-1 + mhs = Be, BEdx - The
(10)
6:
k+1 = x² f(
7: end for
8: output: z
Near-Optimal Tensor Methods
In this section, we revisit the state-of-the--ee art high-order optimization algorithms that include the A-NPE method of Monteiro and Svaiter (2013) the p = 2 case and the near-optimal tensor methods Gasnikov et al. (2019a); Bubeck et al. (2019); Piing et al. (2019) in the general p > 2 case. We start with describing the key ideas behind the development of these algorithms understand how they work. Then, we identify the main flaws of the algorithms that prevent them from being optimal and practical.
Note that the A-NPE method and near-optimal tensor methods have the following substantial similar- ities: (i) both the A-NPE and near-optimal tensor methods are based on the A-HPE framework of Monteiro and Svaiter (2013); 3); (ii) the oracle complexity of the near-optimal tensor methods recovers the oracle complexity of the A-NPE method in the case p 2; (iii) these algorithms have the same issue: the requirement to perform the complex binary search procedure at each iteration which makes them neither optimal nor practical. Hence, we will further leave out the description of the A-NPE method of Monteiro and Svaiter (2013) and consider only the near-optimal tensor methods of
Gasnikov al. (2019a); Bubeck et al. (2019) Jiang et al. (2019)
3.1 A-HPE Framework
The main component in the development of the near-optimal tensor methods of Gasnikov al. (2019a): Bubeec et al. (2019): Jiang et al. (2019) is the Accelerated Hybrid Proximal Extragradient (A-HPE) framework of Monteiro and Svaiter (2013). This algorithmic framework can be seen as a generalization of the Accelerated Gradient Descent of [Nsterov (1983). It is formalized as Algorithm T
Next, we recall the main theorem by Monteiro and Svaiter 2013), which describes the convergence properties of Algorithm [
Theorem 1 (Monteiro and Svaiter (2013)). The iterations of Algorithm 1 satisfy the following inequality:
2 0²)
a 11
1/l R².
(11)
0
Note that Algorithm rewritten as follows:
requires finding 2/ satisfying condition 8 line
This condition can be
V VA (ot+1 1 AoA= 11a 2
(12)
5

---

Algorithm 2 Near-Optimal Tensor Method
1: input: x0 = 2 E Rd
2: parameters: > 0, K
E (1,
3: B-1
4: for h = 0, 1, K - do
A > 0
satisfying
17
k+1 ERd
satisfying
15
5: compute
E
Rd
Org [0,
satisfying
Te 3x
satisfying
(10)
6:
x²
nhe (x())t)
7: end for
8:
output: zf
where function Ax(32): Rd E for x > 0 and Rd is defined
1 2Λ
Ax f(x)
+ 211².
(13)
3.2 Application to High-Order Minimization
need find x/+1 Rd that In order perform the computation line 5 of Algorithm equivalent to (12). which involves satisfies condition 18. As mentioned earlier, condition
the gradient norm A (:xz)]l point I k+1 Function Ax (:: (=1zg) has Lp-Liscchitz p-th order
derivatives for p 2 2 due its definition (13) and Assumption Hence, has the following upper
bound, thanks to Theorem of Nesterov 2021a):
Axa (x: m S T Ax, (1aa)) (z; mny + pM
+ 1)! || 2 1ptt1
(14)
(p
turns that x can be obtained by minimizing this upper bound:
PM
arg min o
Axy (:ag)) (r; (1;=)))))
+
(p 1)! || 11/ptt
(15)
ZER
where M Lp 8 Indeed, by Lemma of Nesterov 2222aa, we have
PM +
Lp
| x 1z)) <
|
k+1 x
(16)
p!
Hence, to satisfy condition
12 we choose d the following way:
op!
op!
x
< Ao S
1 k+1 -0-xx111
1
(17)
2(pM + Lp)
(pM Lp)
Here, the upper bound on A ensures condition being small, which would hurt the convergence rate. The resulting near-optimal tensor method is formalized as Algorithm 2 It has the following convergence rate:
12 while the lower bound prevents stepsize A from
const
1 |1t
f(a))
(18)
K
where K is the number of iterations. The proof of this convergence rate involves condition (17) and Theorem I It is given in the works of Gasnikov et al. (2019a): Bubeck al. (2019) Tiang al. 2019))
V A(=; v² [x)[AA when p > 2, and V A(; a [M] 'We require the strict inequality to ensure the uniform convexity of upper bound (4). which implies the uniqueness and the existence of the minimizer in [5
+

---

3.3 The Problems with the Existing Algorithms
each iteration. According to line of Algorithm A depends on zf via (17p. which depends on z via (15). which depends on Tik .k via (.. which depend on As via (10). Hence, computation of stepsize 0g depends A itself and there is no explicit way to perform the computation on line 5
Algorithm requires finding 2ς satisfying condition
The algorithms Gasnikov al. 2: Bubeck al. 2011): Jiang al. (2019) various binary search procedures to find A and perform the computation on line However, such procedures are costly and require many iterations to converge. For instance, [Bubeck et al. (2019) show that their variant of binary search requires the following number of p-th order oracle calls to find A satisfying condition (17
o (og
(105 Lpp R
(19)
The same complexity (up to constant factors) for similar binary search procedures was established in the works of Nesterov] (2021b); [Jangg et (2019), and in the work of Monteiro and Svaiter (2013)
for the p = 2 case. Hence, the total oracle complexity of Algorithm 2 is O ( 2/(3p+ (1/c))
which does not match the lower bound of Arrevann al. (2019).
The additional logarithmic factor in the oracle complexity of Algorithm Saashmm@@risse rraises the question whether it is superior the accelerated tensor method of Nesterov (2021a) in practice. On the one hand, Gasnikov et al.] (2019)) provided an experimental study that showed the practical superiority of Algorithm 2 over the algorithm of Nesterov] (2021a). However, this experimental comparison is utterly unfair because it considers only the iteration complexity of the algorithms, which does not take into account the oracle complexity of the binary search procedure.
4 The First Optimal Tensor Method
In the previous section, we described the main issues with the existing high-order methods that prevent them from being optimal and practical algorithms for solving problem (Ι). In this section, we will show how to construct an algorithm that does not have those issues. More precisely, we will develop the first optimal p-th order algorithm (p 2 2) for solving main problem
4.1 The Key Idea
Gasnikov et al. (019a); Bubeck et al. (2019): Jiang et al. (2019) used the following approach while creating their near-optimal algorithms: they fixed the procedure of computing xx on line 5 of Algorithm using formula (15) and then developed the procedure for computing λt, which turned out to be inefficient. We will go the opposite way. That is, we choose parameters A in advance in such a way that they ensure the optimal convergence rate and then provide an efficient procedure for finding a k+1 satisfying condition
(8.
Let T/s: be defined as follows:
7 7 k)) 3
(20)
where 77 > 0 is a parameter. Using IT). we can compute Br and N as follows:
A 17(1 10)001
Bx (1+1)
(21)
Σt 11) ب
The following lemma provides lower bound on 34 and an upper bound on A Lemma 1. Parameters By and > defined by (2I) satisfy the following inequalities:
Ba 2 (3p +
2n
(K: +
3p
d S (3p 1) (1 + 3i--1
(22)
2
Lemma and Theorem immediately imply the convergence rate O11 ((1/((pp+)/2)) which matches the lower bound Arjevani et al. (201)). Hence, the only remaining question is how to compute zf k++1 satisfying (8) efficiently. To be precise, we need to develop a procedure that can perform this computation using ((1) of p-th order oracle calls.
7

---

Algorithm 3 Tensor Extragradient Method
1: input: z4.0 x² ER' (*) Axc
2: parameters: M > 0
3: 1=-1
4: repeat
5: 1=1+1
6: compute #141/2 TRd follows:
+ PM
x //11/22 = arg min o (2, (z)
|| -kk.1ptt
(23)
#E3 AA
(p 1)!
7:
x1.ft1 xhit
VA (22.111/22
(m-1))
8: until | (z o 11 12h
9: T =-
k+1 -1/2
10: output: z
4.2 Tensor Extragradient Method for Gradient Norm Reduction
In this subsection, we develop an efficient procedure for computing zf A+1 satisfying condition (8) As we mentioned earlier, condition ( is equivalent to (12). which is an upper bound on the gradient norm Ax, (-i xzgi at point / Hence, we need an algorithm for the gradient norm reduction in the following smooth high-order convex minimization problem:
k arg min Axy Ax; x);)
(24)
rERd
In this subsection, we provide such an algorithm. We call the algorithm Tensor Extragradient Method. It is formalized as Algorithm 3 In the case 1, this algorithm recovers the extragradient method of Korpelevich (1976). Algorithm
3 can be seen as generalization of the extragradient method for
high-order optimization.
One can observe that due to line of Algorithm 3 - - satisfies condition 12 where
-1/2 is the output of Algorithm 3 This is exactly what we need. The following theorem provides an upper bound on the number of iterations T required by Algorithm to terminate and produce the output x
Theorem 2. Let M satisfy
M 2 Ly.
(25)
Then step (23) on line of Algorithm 3 is well defined and the number of iterations' T performed by Algorithm 3 is upper- capper-bouneed as follows:
T - (A&C,(M, o)1l2 I x - +1,
(26)
where Cp is defined as
O C,(M,o)= pl(pM L/. L/2p/-
(27)
Algorithm 3 and Theorem will further be used for the construction of the optimal high-order algorithm for solving problem (T) It is worth mentioning the potential alternatives to Algorithm that we could use for gradient norm reduction. For instance, we could use the tensor method of Nesterov a2) However, the upper bound the number of iterations for this method would involve the diameter the level set function Ax, (+= rather than the distance to the solution ||a - 2 | This would be an obstacle towards development of the optimal algorithm. Alternatively, we could use the accelerated tensor method Nesterov (2021a). turns out that it would work as we need. Moreover, the upper bound on the number of iterations would be even better than (26). However, we find the accelerated tensor method of Nesterov (2021a) to too complicated, which could make the resulting optimal high-order method hard to implement. On the other hand, it would not give us any benefits for the construction of the optimal high-order method compared to Algorithm 3

---

Algorithm 4 Optimal Tensor Method
1: input: xº = 2 Rd
2: parameters: > 0, 20 0, (0,1), K (1,2....)
3: B-1
4: for k 0,1,2, .,.,, K do
5:
πlk =1(1 + (3(3p-1)/2
6:
By 34-1 1 + Iik, b
2/ Bk. ag T// Br
7:
Jg = ag + +(1 (1- -0x)) ox
8:
z..0 r... t ==
9:
repeat
1+1 x. g,,++1/2 = arg minl $
11:
(sett (2; skil) + PM
[x+1]]
12:
xe++ zle
M Alll
(p-1)) -pilppp -1
VAxe (It:tt1/2;
13:
until | (2 1/2 x S o 1l - 24.0
14:
Th
= t 1
x = T -1/2 -1/2
15:
16:
xkt x² TJs V 12)
17:
end for
18: output: 2
4.3 Modification of the Analysis of A-HPE Framework
Unfortunately, cannot Theorem for the analysis of our optimal algorithm. This is because inequality (IT) involves the distances | y + on the right-hand side. Hence, inequality (T]
does not allow us to estimate the iteration complexity T of Algorithm 3 using Theorem 2 Further, provide a new theorem that includes the analysis of the A-HPE framework and provides an upper bound on the distances || zf.1||.
Theorem 3. The iterations of Algorithm 7 satissyy the following inequality:
K
23x-1([(x))) 8)
ak 11
1 1..
(28)
K=U
4.4
The First Optimal Tensor Method
Now, we are ready to provide the first optimal high-order algorithm for solving problem (T). In order to construct this algorithm, we use our Tensor Extragradient Method (Algorithm 3) to perform the computations on line [ of the A-HPE Framework (Algorithm [T]. We also use our choice of
parameters 7/,. 3e and 2 which is provided by 20 and (21 The resulting algorithm is formalized
as Algorithm 4
Now, we are ready to prove that Algorithm is an optimal algorithm. First, we need to establish an upper bound the number of iterations T performed by the inner repeat-loop of Algorithm This done by the following theorem.
Theorem 4. Let M satisfy
25
Then, the following inequality holds for Algorithum
K-1
<kt (1+
113p + 113,+ R-
+
(29)
0
where Cp is defined by
Theorem 4 iiplies that with proper choice of the parameter 7), Algorithm 4 performs O(1) p-th order oracle calls per iteration on average. Indeed, let be chosen as follows:
(3p + (M, R
+
17 =
(30)
2P 2p

---

Then, Theorem immediately implies
K-1
S 2K +
(31)
k=
Finally, the following theorem establishes the total p-th order oracle complexity of Algorithm 4
Theorem 5. Let M Lp and o = 1/2. Let be defined by (30). Then, to reach precision [(a7) 1" S Algorithm 4 requires no more than the following number of p-th order oracle calls:
5Dp (L /c) 3o+2 +7.
(32)
where Dy is defined as follows:
3 3 (3p + 1) pp 1)
Jf
D2 =
(33)
2 /ppl(p2 1)
Theorem 5 shows that the total p-th order oracle complexity of Algorithm iss o ((Lptett//e) an
This oracle complexity matches the lower bounds of Arjevani et al. (201)) up to a universal constant that does not depend on R. Lpp and c. Hence, Algorithm is indeed the first optimal high-order algorithm for solving smooth convex minimization problems.
4.5 Practical Performance
In this paper we provide an experimental comparison of the proposed optimal high-order algorithm for solving smooth convex minimization problems (Algorithm 44 with the existing near-optimal high-order method of Gasnikov et al. (2019a); Bubeck et al. (2019): Jiang et al. (2019) (Algorithm 2
In summary, the experiments show that the proposed optimal Algorithm indeed practical
algorithm which significantly outperforms the existing near-optimal Algorithm The details can be found in Appendix
Acknowledgments
The work of Alexander Gasnikov supported by the strategic academic leadership program Priioriyy 2030' (Agreement 075-02-2021-13116 30.09.2021).
10

---

References
Adil, D., Bullins, B., Jambulapati, A., and Sachdeva, S. (2022). Line search-free methods for higher-order smooth monotone variational inequalities. arXiv preprint arXiv:2205.06167.
Agarwal, N. and Hazan, E. (2018). Lower bounds for higher-order convex optimization. In Conference Learning Theory, pages 774-792. PMLR.
Arjevani, Y., Shamir, O., and Shiff, (2019). Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, (78(1):32-336)
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C.. Maclaurin, D., Necula, G., Paszke,
A., VanderPlas, J., Wanderman-Milne S., and Zhang, Q (2018). JAX: composable transformations of Python+NumPy programs.
Bubeck, S., Jiang, Q. Lee, Y. T., Li, Y., and Sidford, A. (2019). Near-optimal method for highly smooth convex optimization. In Conference on Learning Theory, pages 492-507. PMLR.
Bullins, (2020). Highly smooth minimization of non-smooth problems. In Conference on Learning Theory, pages 988-1030. PMLR.
Bullins, B. and Lai, K. A. (2022). Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal Optimization, 32(3):2208-25) 22299.
Carmon, Y., Hausler, D., Jambulapati, A., Jin, Y., and Sidford, A. (2022). Optimal and adaptive monteiro-svaiee acceleration. arXiv preprint arXiv:2205.1537
Carmon, Y., Jambulapati, A., Jiang, Q. Jin, Y., Lee, Y. T., Sidford, A., and Tian, K. (2020). Acceleration with ball optimization oracle. Advances in Neural Information Processing Systems, 33:19052-19063.
Carmon, Y., Jambulapati, A., Jin, Y., and Sidford, A. (2021). Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference Learning Theory, pages 866-882, PMLR.
Chang, C.-C. and Lin, C.-J (2011). 1). Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27.
Doikov, N., Mishchenko, K., and Nesterov, Y. (2022). Super-universal regularized newton method. arXiv preprint arXiv:22088 220.00888....
Doikov, N. and Nesterov, Y. (2021). Gradient regularization of newton method with bregman distances. arXiv preprint arXiv:211..02952.
Gasnikov, A., Dvurechensky, P., Gorbunov, E., Vorontsova, E., Selikhanovych, D., and Uribe, C. A. (2019a). Optimal tensor methods in smooth convex and uniformly convexopimization. In Conference on Learning Theory, pages 1374-1391. PMLR.
Gasnikov, A., Dvurechensky, P., Gorbunov, E., Vorontsova, E.,, Selikhanovych, D., Uribe, C., Jiang, B., Wang, H., Zhang, S., Bubeck, S., et al. (2019b). Near optimal methods for minimizing convex functions with lipschitz p-th derivatives. In Conference on Learning Theory, pages 1392-1393 PMLR.
Jiang, B., Wang. H., and Zhang, S. (2019). An optimal high-order tensor method for convex optimization. In Conference on Learning Theory, pages 1799-1801, PMLR.
Jiang, R. and Mokhtari, A. (2022). Generalized optimistic methods for convex-concave saddle point problems. arXiv preprint arXiv:2202.09674.
Kamzolov, D., Gasnikov, A., Dvurechensky, P., Agafonov, A., and Takáč, M. (2022). Exploiting higher-order derívatives in convex optimization methods. arXiv preprint 22X1v:2208.13190.
Korpelevich, G. M. (1976). The extragradient method for finding saddle points and other problems. Matecon, 12:747-756.
Lin, T., Jordan, M., et (2022). Perseus: A simple high-order regularization method for variational incqualities. arXiv preprint 2rXiv:2205.03200.

---

Mishchenko, K. (2021). Regularized newton method with global O(1/k²) convergence. arXiv preprint 12..0:2112.02089.
Monteiro, R. D. and Svaiter, B. F. (2012). Iteration-ompleextty a newton proximal extragra- dient method for monotone variational inequalities and inclusion problems. SIAM Journal on Optimization, 22(3):914-95
Monteiro, R. D. and Svaiter, B. (2013). An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 1322):09221125..
Nemirovskij, A. S. and Yudin, D. B. (1983). Problem complexity and method efficiency in optimiza- tion.
Nesterov, (2003). Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media.
Nesterov, Y. (2008). Accelerating the cubic regularization of newton's method on convex problems. Mathematical Programming. 112(1):159-181.
Nesterov, Y. (2021a). Implementable tensor methods unconstrained convex optimization. Mathe- matical Programming, 186(1):157-183.
Nesterov, Y. (2021b). Inexact high-order proximal-point methods with auxiliary search procedure. SIAM Journal on Optimization, 31(4):2807-2828.
Nesterov, Y. (2021c). Superfast second-order methods for unconstrained convex optimization. Journal of Optimization Theory and Applications, 191(1):1-30.
Nesterov, and Polyak, B. T. (2006). Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177-205.
Nesterov, Y. (1983). A method for solving the convex programming problem with convergence rate O(1/k²). In Dokl. akad, nauk Sssr, volume 269, pages 543-547.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No]
(c) Did you discuss any potential negative societal impacts of your work? [No] This is theoretical work with no forseeable negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of theoretical results? [Yes] Assumption
(b) Did you include complete proofs of all theoretical results? [Yes] see Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "hh5TZ--J9IF", "reviewer": "Reviewer_Z7D2", "summary": "In this work, the authors propose a new accelerated high-order method for convex optimization. They prove that the global complexity of their method matches the lower complexity bound, thus the method is *optimal*. In the previous approaches, it was required to do some extra line search at each iteration, solving a one-dimensioanal nonlinear equation, which resulted in much more sophisticated algorithms with additional logarithmic factors. In the new method, the line search is not needed. Therefore, this is the first method having the pure *optimal* rate without extra logarithms.", "questions": "1. Could you, please, make the difference between Algorithm 1 and 2 more transparent? I found no information in the text why the second algorithm is needed (it seems to be the same as the first one).\n\n2. Line 171: 'the crucial mistake' -- I would propose to use slightly more polite wording, since there is no evidence of mistakes (the old algorithms still have some benefits as it seems, e.g. no need to know R).\n\n3. I think it worths to add some references regarding Tensor Extragradient Method and high-order methods minimizing gradient norm.", "limitations": "--", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The contribution is the new optimal accelerated high-order method and its analysys. I found these results interesting and significant. To the best of my knowledge, this is the first accelerated (high-order, p >= 2) method that does not use any line search, and matches the lower bounds without extra logarithms.\n\nThe main idea of their construction is to use the standard accelerated framework (from the works of Nesterov, 1983, 2018; Monteiro-Svaiter, 2013, Gasnikov et al. 2019) but with a predefined sequence of parameters which provides the method with a required rate of convergence (knowing in advance the optimal rate). Then, to ensure an actual convergence, they propose to solve a prox-point type subproblem by iterations of the basic high-order method (in their case, Tensor Extragradient Method). The main novelty of the analysys is to prove:\n1. the convergence of the inner method to a reasonable stationary point in a certain amount of iterations.\n2. the boundedness of the total number of inner steps.\nWhile in the previous near-optimal high-order methods, it was required to do high-order step just once, but with solving a complicated nonlinear equation alongside.\n\nIn my opinion, this is a solid result which must be of interest for the optimization community.\n\n\nThe weaknesses of the paper are a little bit technical presentation and the lack of any practical evidence (experiments or at least a discussion).\nThe paper containts a lot of details comparing different analysis techniques with some unnecessary redundancy (e.g. Algorithm 1 and Algorithm 2), however almost no information about how to use their methods in practice. In particular, the following questions seem to be unanswered:\n\n1. How to choose parameter $\\nu$ in practice. The formula (30) contains both the Lipschitz constant and the radius R. Is it possible to use some line search? Is it possible to eliminate some of these parameters?\n\n2. How many steps of the inner method are needed in practice, and what happens in case p = 1 (first-order accelerated methods)? \n\n-------------------- \nAfter rebuttal:\n--------------------\nI am happy to increase my score, since I believe that the main theoretical contribution of the paper is very significant for the optimization community.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NWXCtGorE6D", "reviewer": "Reviewer_drXo", "summary": "This paper studies the question of minimization of convex functions with $p$-order smooth derivatives, given access to an oracle that can minimize the regularized $p$-th order Taylor expansion of the function at a given point. \n\nRecent works (Gasnikov et al, Bubeck et al., Jiang et al.) had previously established an oracle complexity of $O(\\epsilon^{-2/(3p+1)}\\log 1/\\epsilon)$ extending the rate of $O(\\epsilon^{-1/2})$ by Accelerated Gradient descent (Nesterov, 1983) for $p=1,$ $O(\\epsilon^{-2/7})$ by Montero-Svaiter (2013) for $p=2,$ and Nesterov's accelerated tensor method (2021a) that achieved $O(\\epsilon^{-1/(p+1)}).$ \n\nA lower bound of $\\Omega(\\epsilon^{-2/(3p+1)})$ is known from Arjevani et al. (2019). Thus, the known rates were off by a logarithmic factor. \n\nThis paper gives an algorithm that achieves a tight bound of $O(\\epsilon^{-2/(3p+1)})$ calls to the $p$-th order oracle, thus settling the complexity of $p$-th order smooth convex minimization.", "questions": "Am I correct in pointing out that your algorithm does not provide an efficient procedure to compute the next iterate on line 11 in Algorithm 4? If yes, I strongly suggest reflecting this in the definition of Oracle complexity. The current definition of oracle complexity in the paper (Definition 2) only assumes that the oracle returns the higher order derivatives.", "limitations": "I have listed the limitations above under weaknesses of the result.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\nThe key strength of the result is immediate since it establishes the best-possible oracle complexity of solving $p$-th order smooth convex problems.\n\n**Weakness**:\n1. My primary concern is whether shaving off a log factor from the oracle complexity is that significant a question after all. The 3 independent papers that first achieved the almost-optimal complexity had achieved a significant improvement in the oracle complexity. While it is nice to achieve the exactly optimal bound in terms of epsilon, the logarithmic factor seems inconsequential in my opinion.\n2. All these papers rely on making calls to an oracle that can not only compute $p$-th order derivatives, but can solve a regularized $p$-th order problem, see Algorithm 1, step 5, eq 15 and Algorithm 3, step 6 or Algorithm 4, line 11. (To the best of my knowledge) We do not know how to solve these problems efficiently for $p > 2$ even given access to the higher order derivatives. In my view, this hides the real complexity of being able to solve highly smooth problems. \n3. The notation of the paper is difficult to parse. e.g. in Algorithm 4, $x_g$ is a funny notation that gives no hint to what it means. It relies on $x_f$ which is again not so easy to see where it's defined. In line 11 in Algorithm 4, the notation for $\\Phi$ has three(!!) orders of subscript.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8BIDaT4_pd", "reviewer": "Reviewer_9tdw", "summary": "In this work, the authors propose a p-order method for optimizing a p-times continuously differentiable objective. They prove that the convergence rate matches the theoretical lower bound and is better than the previous works. ", "questions": "See the weakness points. ", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Designing a high-order optimization method that matches the theoretical lower bound on the iteration complexity is indeed a contribution. \n2. The theoretical results are complete and solid. \n\nWeakness:\nIn the abstract, it seems that one of the motivations is that the previously proposed high-order methods are not practical. But in this paper, there are still no numerical experiments. Can you provide some experiments to verify that the proposed method is practical? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-6WDLgLzubB", "reviewer": "Reviewer_U1kW", "summary": "The paper studies highly smooth convex optimization and provides the first optimal acceleration method under oracle model. A function is said to be p-th order smooth if its p-th order gradient is Lipschitz. The previous best known methods for high-order smooth function finds an $\\epsilon$-approximation solution using $O(\\log(1/\\epsilon)\\epsilon^{-2/(3p+1)})$ gradient oracles and follows the Monteiro and Svaiter framework, and a lower bound of $\\Omega(\\epsilon^{-2/(3p+1})$. The paper closes this gap and provide an algorithm using $O(\\epsilon^{-2/(3p+1)})$ gradient oracle calls.\n\nTo summarize in very short words, the paper still utilizes the Monteiro and Svaiter framework (as previous work), but instead of performing some complex binary search for a fix point problem as a subroutine, the paper gives the explicitly parameter and an explicit high-order extra gradient for searching the ``middle'' point.\n\n", "questions": "Some additional reference.\n\n[1] Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss. COLT'2021\nYair Carmon, Arun Jambulapati, Yujia Jin and Aaron Sidford \n\n[2] Acceleration with a Ball Optimization Oracle\nYair Carmon, Arun Jambulapati, Yujia Jin, Qijia Jiang, Yin Tat Lee, Aaron Sidford and Kevin Tian ", "limitations": "No", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength. The paper is very well-written, easy to read and give a nice summary on previous work. On the technical side, the removal of binary search and an explicit method for high order smooth optimization is very nice and could be beneficial for practical implementation.\n\n\nWeakness. There is no major weakness, but personally I think providing some experiments for the methods could make the paper more promising. Though I found the pure theoretical result is already very interesting.\n\nIn summary, I think this is a solid paper and could benefit the community. I would suggest to accept the paper.\n\n--------------------------- Post rebuttal ---------------------------\n\nI have read the author's response keep my evaluation, and I vote for acceptance of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept