OPTAMI: Global Superlinear Convergence of High-order Methods
Authors: Dmitry Kamzolov
Artem Agafonov
Dmitry Pasechnyuk
Alexander Gasnikov
Martin Takáč
Venue: ICLR 2025 Poster (2025)
Keywords: Second-order Optimization
High-order Optimization
Cubic Regularised Newton Method
Newton Method
Convex optimization
Superlinear Convergence
Primary area: optimization
TL;DR: We prove global superlinear convergence for high-order methods, introduce NATA, a superior accelerated optimizer, and release OPTAMI, a PyTorch library for high-order optimization, enabling broader adoption and research.

Abstract: Second-order methods for convex optimization outperform first-order methods in terms of theoretical iteration convergence, achieving rates up to $O(k^{-5})$ for highly-smooth functions. However, their practical performance and applications are limited due to their multi-level structure and implementation complexity. In this paper, we present new results on high-order optimization methods, supported by their practical performance. First, we show that the basic high-order methods, such as the Cubic Regularized Newton Method, exhibit global superlinear convergence for $\mu$-strongly star-convex functions, a class that includes $\mu$-strongly convex functions and some non-convex functions. Theoretical convergence results are both inspired and supported by the practical performance of these methods. Secondly, we propose a practical version of the Nesterov Accelerated Tensor method, called NATA. It significantly outperforms the classical variant and other high-order acceleration techniques in practice. The convergence of NATA is also supported by theoretical results. Finally, we introduce an open-source computational library for high-order methods, called OPTAMI. This library includes various methods, acceleration techniques, and subproblem solvers, all implemented as PyTorch optimizers, thereby facilitating the practical application of high-order methods to a wide range of optimization problems. We hope this library will simplify research and practical comparison of methods beyond first-order.

Published as a conference paper at ICLR 2025
OPTAMI: GLOBAL SUPERLINEAR CONVERGENCE OF HIGH-ORDER METHODS
Dmitry Kamzolov Artem Agafonov',, Dmitry Pasechnyuk',
Alexander Gasnikoy4.35, Martín Takáč"
Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE
2 Toulouse School of Economies, Toulouse, France
3 Moscow Institute of Physics and Technology, Dolgoprudny, Russia
4 Innopolis University AI Research Center, Kazan, Russia
5 Institute for System Programming RAS, Moscow, Russia
ABSTRACT
Second-order methods for convex optimization outperform first-order methods in terms of theoretical iteration convergence, achieving rates up to O(k for highly-smooth functions. However, their practical performance and applications are limited due to their multi-level structure and implementation complexity. In this paper, we present new results on high-order optimization methods. supported by their practical performance. First, we show that the basic high-orde methods, such as the Cubic Regularized Newton Method, exhibit global superlinear conver- gence for j-stronggy star-convex functions, class that includes j--strongly convex functions and some non-convex functions. Theoretical convergence results are both inspired and supported by the practical performance of these methods. Sec- ondly, we propose a practical version of the Nesterov Accelerated Tensor method, called NATA. It significantly outperforms the classical variant and other high-order acceleration techniques in practice. The convergence NATA is also supported by theoretical results. Finally, we introduce open-source computational library for high-order methods, called OPTAMI. This library includes various methods, acceleration techniques, and subproblem solvers, all implemented as Py PyTorch op- timizers, thereby facilitating the practical application of high-order methods to a wide range of optimization problems. We hope this library will simplify research and practical comparison of methods beyond first-order.
INTRODUCTION
In this paper, we consider the following unconstrained optimization problem:
min
f(x),
(I)
WEB
where E is a d-dimensional real value space and fxx is a highly-smooth function
Definition 1.1 Function f has Lp Lipschhit--oominnoor p-th derivative, if
[DP D2 f(y)llop S Lp all Vx, y E E,
(2)
where D fx) is a p-th order derivative, and || !lop is an operator norm.
In the paper, we primarily focus on three main cases: p = {1; 3/. We assume that the function is convex, although for some results, relax this assumption to star-convexity. By x= denote the minimum of f.
Second-order methods are widely used in optimization, finding applications in diverse fields such machine learning, statistics, control, and economics (Polyak 1987 Boyd & Vandenberghe! [004] Nocedal & Wright 1999 Nesterov] 2018). Historically, much of the research on second-orde -oddrr methods has focused on their local quadratic convergence. A well-known method achieving this rapid local rate the classical Newton method (Newton 1687 Raphson 1697 Kantorovich 1948b).
However, it can diverge if the starting point is far from the solution (Nesterov) 1983] Example 1.2.3). To address this divergence issue, the Damped Newton method introduces a step-size (damping
"Corresponding author, e-mail: @amzolov.ont@ gmmil.coom

---

Published as a conference paper at ICLR 2025
coefficient) ensure global convergence. However, the best-known global rate for the Damped Newton method is (TT-1/3) (Berahas et al. 2022), which is slower than the gradient method's convergence O(T-1). The Cubic Regularized Newton (CRN) method, introduced by Nesterov & Polyak (2006), was the first second-order method with a proper global convergence rate O(T outperforming the gradient method. Additionally,, for strongly convex functions, retains a quadratic local convergence rate, similar to the Newton method (Doikov & Nesterov 2022). The introduction of
CRN represented a significant milestone in the advancement of second order optimization methods.
Hessian approximations. In large-scate scale optimization problems, computing the (inverse) Hessian or solving a linear system can be computationally expensive. Thus, it is natural to consider inexact or stochastic algorithms to reduce these overheads. In convex optimization, several studies have explored globally convergent second-orde methods with inexact Hessians (Ghadimi et al." (017)) higher-order methods with inexact and stochastic derivatives (Agafonov al. [2024a b), and adaptive stochastic methods (Antonakopoulos et al. (022). Recently, Quasi-Newion (QN) Hessian approximations have
been integrated into global second-order methods, resulting in algorithms that outperform first-order methods - even when relying solely on first-order information (Kanzolov et al.) 2023b Jiang
ct al. 2023 Scieur 2023 Jiang et al., 2024). Furthermore, numerous second-order approximation techniques have been developed for training neural networks, often surpassing state-of-the-art first- order methods. Notable examples include Shampoo (Gupta et al., 2018). SOAP (Vyas et al., 2025),, and SOPHIA (Liu et al., (024),, which showcase the effectiveness of second-order approaches in practical applications and benchmarks (Dahl et al. 2023). Such potential motivates us to study second-order methods.
Accelerations. The Cubic Regularized Newton is the basic method in the line-up of second-order methods. There are two main directions for its improvement: accelerated second-order methods, including Nesterov-type acceleration (Nesterov) 22088] (021b), near-optimal acceleration Monteiro & Svaiter (2013); Gasnikov et al. (2019b), and optimal acceleration Kovalev & Gasnikov [2022);
Carmon et al. (2022); and third-order methods with superfast subsolver, which allows making third-order step without computation of third-order derivative (Nesterov 2021b
Kamzolov 2020
1.1 OPTAMI: PRACTICAL PERFORMANCE OF HIGH-ORDER METHODS
The theoretical results mentioned above highlight the sig- nificant potential of second-order methods in optimization. However, their practical adoption remains limited due to the computational cost of calculating second deriva- tives, the variety of acceleration techniques, and the use of different Hessian approximation methods to reduce it- eration costs. To address these challenges, we introduce OPTAME unified library implemented in PyTorch for corded-order and higher-order optimization methods.
Nesterow 3-rd order Lower-bound Function, u 0.001
Rbo)
Gradient Descent, La 10,0
Cubic Newton, 10.0
Dasic Tensor Method, L 10.0
One particular goal of this library is a direct compari- son of a wide variety of acceleration techniques, which include Nesterov acceleration (Nesterov) 2b2 with rate (pT-(p+)) Near-Optimal Monteiro-Svaiter Accel- eration (Monteiro & Svaiter 2013 Bubeck et al., 2019] Gasnikov et al. 2019b; Kamzolov 2020) with a rate
Iterations,
Figure 1: Third-order Nesterov's lower- bound function. Cubic Newton and Ba- sic Tensor method converge superlin- early. In contrast, GD demonstrates lin- ear rate.
O(T-(5p+1)) Near-Optimal Proximal-Point Acceler-
ation NNsttrovv] 20) with the rate Ó(T-(3p+1)/2) Optimal Acceleration (Kovalev & Gasnikov
2022 Carmon et al., 2022) with a rate (3T-(3p+1)/2 and more Nesterov| (2023). Despite the
theoretical advancements in these methods, the literature lacks comprehensive practical comparison, especially for higher-order methods with p 3.
In the process of developing the library, we encountered several open challenges.
Methods exceed linear convergence in practice. We observed in experiments that second-order and third-order methods often achieve superlinear convergence rates for j-strongly convex functions (Figure [.. From a theoretical standpoint, this is surprising. The lower bound is
https://gi http://hthhhbbccomm/////////////
2

---

Published as a conference paper at ICLR 2025
(( [ap)
2/7
+ log log
for & S ci
a
eir as established by Arjevani et al. (2019). 1
where r is the radius of quadratic convergence { :: Sor 02 and C12 0g are universal constants. The power 2/7 corresponds the optimal accelerated method. However, this lower bound applies only when é S cir, which corresponds to small values of E. In the case when & > C1r, meaning the desired accuracy exceeds the radius of the quadratic convergence region, may be possible to achieve faster global rates of Cubic Regularized Newton method than linear convergence.
890, Logistic Regression
Cubic N Newton,
Practical performance of accelerated methods. We also observed that the Nesterov Accelerated Tensor Method Nesterov b021b) performs worse or on par with its non- accelerated counterpart in practice. This contrasts with first-order methods, where acceleration is typically ben- eficial. These practical limitations lead the method being underutilized (Scieur 2023 Carmon et al. 2022
Nesterov ov Accelerated Cubic. 42 0.1
Basic Tensor Mothod, 1 0.1
Nesterov Accelarated Tensor,
Antonakopoulos et al. [2022]
In our work, alongside introducing the OPTAMI library, we aim to address these open challenges from both theo- retical and practical perspectives.
Iterations,
Figure 2: Comparison of Basic Methods Nesterov Accelerated Methods
Contributions. We summarize our key contributions as follows:
1. Global Superlinear Convergence of Second and High-order methods. Our main contri- bution is providing theoretical guarantees for global superlinear convergence of the Cubic Regularized Newton Method and the Basic Tensor Methods for μ-strongly star-convex functions. These theoretical results are validated by practical performance. These results are significant improvement over the current ofate-of-the-arr in second-order methods.
2. Nesterov Accelerated Tensor Method with A A;-Adaptation (NATA). We propose a new practical variant of the Nesterov Accelerated Tensor Method, called NATA. This method addresses the practical limitations of the classical version of acceleration for high-order methods. We demonstrate the superior performance of NATA compared to both the classical Nesterov Accelerated Tensor Method and Basic Tensor Method for 2 and 3. We also prove a convergence theorem for NATA that matches the classical convergence rates.
3. Comparative Analysis of High-Order Acceleration Methods. We provide practical comparison of state-of-the-art (SOTA) accelcration techniques for high-order methods, with a focus on the cases p 2 and = 3. Our experiments show that the proposed NATA method consistently outperforms all SOTA acceleration techniques, including both optimal and near-optimal methods.
4. Open-Source Computational Library for Optimization Methods (OPTAMI). We introduce OPTAMI, an open-source library for high-order optimization methods. It facilitates both practical research and applications in this field. Its modular architecture supports various combinations of acceleration techniques with basic methods and their subsolvers. All methods are implemented as PyTorch optimizers. This allows for seamless application of high-order methods to a wide range of optimization problems, including neural networks.
METHODS AND NOTATION
Notation. In the paper, we consider a d-dimensional real value space E. E is a dual space, composed of all linear functionals on E. For a functional y E E*, we denote by (g.z) its value at x E E. For p 2 1, we define D2 fx))(h1..... [iflll.....hp.... .hp] as a directional p-th order derivative of f 1, I. If all h, = h we simplify DP f()) hp] as DP f())[h]) So.
along h, E E, for example, D2 f())[h] = (Vf(x) h) and {x))(]] (V² f(r)), h). Note, that ff(z) E E., f(r(h E*. Now, we introduce different norms for spaces E and E*. For self-adjoint positive-definite operator B E - E", we can endow these spaces with conjugate Euclidian norms: |>|| = (Bx, 1/2 I E E.
||g||- = (g. B B)) 1/2
g E*.
So, for an identity matrix B = I, we get the classical 2-norm ||~|||2 = ||~|| = (2, 1/2, We denote E I as vector of all ones and 0 E Rd vector of all zeroes.
1/2,
3

---

Published as a conference paper at ICLR 2025
We introduce two types of distance measures between the starting point and the solution: for non-
accelerated methods, we consider the diameter of the level set C = fx E f(x) - f(o)
D max #E
|| x
and for accelerated methods, we use the Euclidean distance given by
R 220 2l
(4)
2.1 METHODS OPTAMI LIBRARY
In this subsection, we present detailed overview of the core methods implemented in the OPTAMI library. Second-order methods have a more complicated structure. The library's s design is structured into three hierarchical levels: basic methods, subsolvers, and accelerations. This modular architecture ensures flexibility, extensibility, and adaptability to a variety of optimization tasks. It allows users to combine multiple basic methods with various accelerations and subsolvers without the need to implement entire methods from scratch. We leave technical details of the subsolvers to Appendix C
BASIC METHODS. The Basic methods are the foundational building blocks of the library. These monotone, occeleceeee methods form the backbone for constructing more sophisticated acceler- ated algorithms. Below, we outline the primary basic methods available in the library. Newton method. The classical (Damped) Newton method is defined as follows:
Tt+1 = Iy - " [ [z:)]
(xz).
(5)
where "t E R4 is step-size or damping coefficient. The Newton step originates from the second- order Taylor expansion 22(x, x,)):
It+1 = argmin (12 xx) = + (V[())+(VV====))>>)))>>)) x.) + (V) - = x-),=-z)) -x,) (6)
=EE
The solution of this problem corresponds to 55) with "/- = 1. The Newton method lacks global convergence, while the Damped Newton method exhibits a slow global convergence rate of O(T 1/3). This is because the approximation 4b2 x1) is not guaranteed to be an upper bound for f. meaning it is possible that f(x)) > 22 (2,),))). v.).
Cubic Regularized Newton method. To address this issue, the Cubic Regularized Newton (CRN) method was proposed
Ft-1 argmin (x, = $2(2, x2.) + Ma || xz 18]
(7)
For the function f(x) with Tn-Lipschitz Hessian, the model 2M, (v. 2x)) is an upper bound of the function f(x) for M2 2 L2; hence 12M, (z, xx) 2 f(x). This method is the first second-order method
with global convergence rate of O MaDx)) ). which is faster than the Gradient Method (GM). Basic Tensor method. High-order Taylor approximation of function f can be written as follows: + (y) f(z) + Σx k D* f(x) [y -rj* x, y E E,
(8)
where, for 1. simplify notation (v). From ②). can get the next upper- bound of the
function f(x) (Nesterov 2018 2021b)
Ly (fv) + 2 (v)) S (pti)elly lly x1|=+1
(9)
which leads us to the high-order model
M, Dr,,, $ (v) + ( l1y 211
(10)
Now, we can formulate the Basic Tensor method
Zt41 argmin (2 My (v))
(11)
where M, 2 plpp- For p = 1 and M1 2 L,, is the gradient descent step F++1 = Ft Mi fxx)
with the convergence rate 0 M, R² Method from
for convex functions. For p = 2 and M₂ 2 Lz, it is a CRN
T
For p = and M3 3Ls, is a Basic Third-order Method (Nettervv) 20216):
Zz41 24 + argmin (zx) + ff(xx) [h] + 1 f(x)) M2D*)
[4]2 + f(x)( [b]² + Ma |b] (12)
with the convergence rate O (M²D* ). The step 12 can be performed with almost the same
hEE
computational complexity (up to a logarithmic factor) by using the Bregman Distance Gradient
Method subsolver (Nesterov) c02 The details are written in the Appendix C.I
ACCELERATIONS. Compared to first-order methods, second-order and higher-order methods achieve three types of acceleration rates: Nestrov-type acceleration with the rate O (T-(0++)) nearly- optimal acceleration Ô (2-(3p+1)/2). and optimal one O (T-(3p+1)/2) where Ô(-) means up to logarithmic factor. OPTAMI library includes four key variants of acceleration techniques:
4

---

Published as a conference paper at ICLR 2025
Nesterov Accelerated Tensor Method (Algorithm I with rate O ()+
Nesterov 2021b;
(3p+ Near-Optimal Tensor Acceleration (Algorithm 5) with rate ((T-(3p+1)))) 1)2
(Bubeck et al. 2019
Gasnikov et al. 2019b Kamzolov 2020);
Near-Optimal Proximal-Point Acceleration Method with Segment Search (Algorithm 6 with the
rate ((7-(3p+11)2) (Nesterov 202
Optimal Acceleration (Algorithm with rate O(T-33++1)2 (ooalevv & Gasnikov 2022
These methods are presented in detail Section 3.1 for Nesterov acceleration, and in Appendix D for the remaining algorithms.
IMPROVING PRACTICAL PERFORMANCE OF ACCELERATED METHODS
While accelerated second-order and higher-order methods provide provable theoretical advancements over their non-accelerated counterparts, a detailed comparison of their practical performance seems to be underexplored the literature. Notably, techniques like Nesterov acceleration, which are highly effective for first-order methods, can slow down second-order and higher-order methods, particularly in the initial stages (Scicur) [0233] Carmon et al. 2022 Antonakopoulos et al. (022). To illustrate this, we present a practical example using the logistic regression problem (Figure 2D. The accelerated versions appear slower, which contradicts the theoretical expectations.
In this section, we first introduce a novel algorithm, NATA, that enhances the practical performance of the Nesterov Accelerated Tensor Method while maintaining the same theoretical guarantees. We then provide a comprehensive computational comparison of five different acceleration techniques for second-order and higher-order optimization.
3.1 NESTEROV ACCELERATED TENSOR METHOD WITH A--ADAPTATION (NATA)
Algorithm 1 Nesterov Accelerated Tensor Method
1: Input: 30 vo is starting point, constant Mp. v/(2)) p41 || xo p+1 total number of iterations T, and sequence Ag.
2: for t 2 0 do
3: at+1 A441 At
4: Yt = A++1 xt
ast1
Act1
5: T++1 argminger (R (v)}
6: (2) = (b)(2) + a a ( + + (V)()4))) -x++)))
7: Gr+1 = arg (2)
8: end for
9: return 2r+1
In this subsection, we investigate the causes of the under- performance of Nesterov Accelerated Tensor method and propose solution. We begin by revisiting Algorithm I with further details provided in Appendix D.I According to the theoretical convergence result f(x)) - f(x")
a9a, Logistic Regression. La
Nettery ACCI enaedd CAtE
SATA adactia
Teaor Hithed
Medtarz Acci anted learr
[='-=o||P=1 from (Nesterov 2021c, Theorem 2.3), the (++1)A,
Tema NATS with kind v-33
sequence A, directly connected with the method's per- formance the larger the A,, the faster the convergence. Therefore, our goal maximize A,. Theoretically, A, should be defined as A, L. 1p+1, where 1/2 सा for
Hossian computations Figure 3: Basic and Nesterov Acceler- ated Methods vs new NATA Methods.
M2 Le and values of Un appear to be quite small, which limits the speed of convergence. Can these values be increased? The answer is yes. We propose the Nesterov Accelerated Tensor Method with A Ar-Adaptation, which selects these parameters more aggressively, leading to faster convergence.
5 for M3 6L.. However, the 3024
Theorem 3.1 For convex function ff with Le--Lpsshitz-contieee that ((T) [(x") & e, it suffices to perform no more than T 2 iterations of the Nesterov Accelerated Tensor Method with A, A--Aapptatoon (NATA) with M, 2 plap (Algorithm 2 where
p-th derivative, to find Fr such
(
1
==
(M
p+1
+ logo
(13)
5

---

Published as a conference paper at ICLR 2025
Algorithm 2 Nesterov Accelerated Tensor Method with A,-Adaptation (NATA)
1: Input: 20 = vn is starting point, vD(z) = p+I || xollet1, constant Mp, total number of iterations T, Ao O, y Up, wiua Up maximal value of v, 0 is scaling
parameter for v, and Po S v is starting value of v.
2: for 2 0 do
3: D¹ v²
4: repeat
5:
V¹ max
8
6:
v¹ θe+1 Mr
((t + 1) - 12t1) and A,- = As az+1
A xx + ax+1
7:
V1 As+1
Act1
Ut
8:
21+1 argmin (R (v)}
9:
(z+1(=) = v1(2) ac+1 (f (Vf(zz41); ret1)l
10:
U++1 argmin (1+1(2)
11:
until (144)) < (441((042))
12:
y²+ min (v'0, ymaa
13:
end for
14:
return 27+1
The proof is presented in the Appendix D.2 The established convergence rate of NATA matches (uam the original method, with an additional factor of loga gamn accounting for the adaptation of vt. Next, we demonstrate the practical improvements of NATA compared to the classical methods. As shown in Figure one can see that the Cubic and Tensor variants of NATA significantly outperform the classical Basic and Nesterov Accelerated Methods. We also included versions of Cubic and Tensor NATA with fixed D' = 10 and D' = 0.5, respectively, where y' is an additional tunable aggressive variant of NATA exhibit even faster practical performance,
hyperparameter. This though it may diverge if Df is not chosen carefully.
3.2 COMPUTATIONAL COMPARISION OF ACCELERATION METHODS
We now present practical comparison of various acceleration techniques for tensor methods in convex optimization, including Nesterov acceleration, near-optimal and optimal accelerations, as well the newly proposed algorithm, NATA. Specifically, our experiments focus on logistic regression, defined as:
f(x) E log (1 + e=bi(a)a))) + # 1|x:1
(14)
2
where a; Rd are data features and b, {-1; 1} are data labels for i 1, ..... We evaluate performance on the a9a dataset Figure with regularizer and = 10 Figure
a9a, Logistic Regression, # 0.0, Lg 0.1
a9a, Logistic Regression, μ 0.1
Cusic Nawion
Tenser Mathos
Nedharov Acce wrated Gubre
Medtero Accelerated
NATA
with cuned
Cupic Prox. Po Sogment Soarch
Neer-Optimal Gudle
10-
Tonsor Paint Segment Search
Optima Cutse
Optimal Terwar
10-
16-1
15
Hessian computations
Hessian computations
Figure 4: Comparison of different cubic and tensor acceleration methods on Logistic Regression for a9a dataset from the starting point To = 3e, where is vector of all ones.
Let now discuss the performance of the methods. The new NATA acceleration outperforms all other methods. We attribute this to NATA's strategy of maximizing â and A,, which enables even faster convergence in the later stages. The second-bes performer is the Near-Optimal Acceleration method. Although it struggles initially due large number of line-search iterations per step,

---

Published as a conference paper at ICLR 2025
gradually requires fewer line-search iterations - less than two per step on average parameters from previous line-search steps become well-suited for the current iteration. With fewer line-search iterations, the method accelerates and outpaces the remaining competitors. A promising direction for improving this method would be to refine the line-search process through an advanced line-search strategy. Next, the Nesterov Accelerated method starts off slower than the basic method without acceleration. Eventually, the method accelerates and overtakes the basic version but only for the Cubic version, as V3 is too small for tensor methods. Near-Optimal Proximal-Point Acceleration Method with Segment Search performs very similarly to Basic Methods with only improvement in strongly convex case. It has much fewer iterations, but does safe segment search with an average 3 Basic steps per search. Lastly, the Optimal Acceleration method performs the worst in practice. We believe the main issue lies in the internal parameters, which need tuning and adaptation, as we used the theoretical parameters in our implementation. This leads to many inner iterations without significant global progress, Improving these parameters presents an open question for future research. More details can be found in the Appendix [
In Figure 5) both basic optimization methods and certain accelerated variants appear to exhibit global superlinear convergence, accelerating with each iteration even when far from the solution. This observation naturally raises an important question: Can we theoretically prove that second-order methods achieve global superlinear convergence? We address this question in the following section.
99, Logistic Regression, μ 0.0001, L2 0.1
a9a, Logistic Regression, | = 0.0001, L3 D.1
Cutic Newton Accelorstid
3014
Tensar Methre
Accelerated
Near Optimal Cuaic
Noar Ootimal Tonsor
Cusic Pres. Po Segment Search
Tenwar Frez. Point Segmert Search
Optime Cutec.
mae (x*))
Optimal Tensar
ap-
30-7
226
203 25 3.50
Ldo
252
220
2.0
Hesslan computations
Hessian comporatiors
Figure 5: Comparison of different cubic and tensor acceleration methods on regularized Logistic Regression for a a dataset and μ = 10-4 from the starting point zg- = =3e.
GLOBAL SUPERLINEAR CONVERGENCE OF HIGH-ORDER METHODS FOR STRONGLY STAR-CONVER FUNCTIONS
In this section, we establish the global superlinear convergence of high-order methods for strongly star-convex functions. We begin by defining global superlinear convergence.
Definition 4.1 A method is said to exhibit a global superlinear convergence rate with respect to the functional gap if there exists sequence for all E (O....,T) .T) such that
[(141)-f < St. f(x))--
1> S. > G(+1 Vt E {O....,T), .). and Ce + 0 for t + +00.
(15)
The essence of this definition lies in the fact that the scaling coefficient & decreases with each iteration. If Çe remains constant, the method achieves linear convergence. Con- versely, if G, increases over time (i.e., & Se+1), the con- vergence becomes sublinear. Additionally, we introduce the values a, = K((+t)>f"
390, Logisti Regression, p.0000
f(xx)-f" < 1, which typically rep- resent the per-iteration convergence rate from f(++11 f < (1 - ox) (frz) f*) The larger a; means faster convergence. As for constant S ar, the method takes total number of T = O (a- log
Gradient Descent, L -.25
Oubi Newton G. 0.25
Basic Tonsor Method, Ly- 0.25
iterations to reach E-solution, where f(TT+1) - ft < E. For exam- plc, gradient descent exhibits global linear convergence for P strongly convex functions with G = a = bitp"
[(x0)=f-
Harations
Figure 6: Cubic Newton and Basic Ten- sor method have areas of superlinear convergence. In contrast, GD demon- strates linear rate.
Now, to get some intuition on the performance of the methods, we begin with two simple and classical examples: the lz-regularized logistic regression problem and the lz-regularized Nesterov's
7

---

Published as a conference paper at ICLR 2025
lower-bound function. The lz-regularized third order Nesterov's lower-bound function from Nesterov (2021b) has the next form
- 12 xx+11 (2: (
+ -1
(16)
Figures 6 illustrate that both the Cubic Newton method and Basic Tensor method have areas of superlinear convergence where the graphics going down faster with each iteration (concave downward). In contrast, gradient descent demonstrates linear convergence. To verify the behavior of these methods, plot the values a₂
(((41)) 1.
[(x))
a9a, Logistic Regression, 0.0001
Nesterov 3-rd order Lower bound Function, 0.000
Grad lent Descent, L; 0.25
Gradient Descent, 4; 10.0
Cubic 0.25
Cubic Newton, 1 10.0
Dasic Tersor Method, =
Tençor Mathod, L. 10.0
Rerations,
Iterations.
(a) Logistic Regression for a 9a dataset starting from the point zo 3e with μ 10 regularizer.
(h) Third-order Nesterov's lound-bound function start- ing from the point 0 with μ 10 regularizer.
Figure 7: Comparison of the basic methods by the relative value -
](x))
In Figure 7 we observe that at the beginning, methods slow down for both cases. This phase functions out-
corresponds to the region where the function's decrease guarantee for performs the function's 's decrease guarantee for strongly (star-) Jconvex functions. For example, in the case of gradient descent, this occurs when the guarantee f(x++1 f(xx) zi. [V )) is
xttbi (f(a)) f*). Despite this region, gradient descent still has global linear convergence for strongly (star-)convex function. As iterations proceed, gradient descent stabilizes around a, = 10 which corresponds to the theoretical convergence rate s. The Cubic Newton method and the Basic Tensor method, however, start to accelerate and switch superlinear convergence rate. This practical performance gives the intuition for the global superlinear convergence of high-order methods.
better than [(+++1) - < (1 (1--a 1=
Now, we present the theoretical results demonstrating that basic high-order methods indeed have global superlinear convergence for p-strongly star-convex functions.
Definition 4.2 unuuniorrlly star-conver of degree q with respect to x² for all x E Rdd and Vo E [0, 1]
Let x² be minimizer of the function f. For g 2 2 and pa 2 0, the function f is
f (ax + (1-a)=²) S af(x) + =(1-aff(x") a(1-a)iig | x 1=1
(17)
If =fq=2 = 2 then the function f is μ-strongly star-convex with respect to x² If pa 0 then the function f is star-convex with respect to x". From this definition, we can additionally get the next useful inequality sometimes called q-order growth condition
Pe || x 111 S fxx)-f(x")
(18)
q
We start with simplified version of the theorem which includes the linear convergence and then present the full version.
Theorem 4.3 For u-stroonlyy star-convex Cubic Regularized Newton Method from
function f with L=-LLpschitte Hessian with M2 2 L2 converges with the rate
f(I(+1) f < (1 an) (f(xt) -)
(19)
for all
04 E [0; where a; This range includes the classical linear rate
1++1+ and Rig (Ma Lg) x1-501 2nr
(20)
3/
f(x)) - f(x") I (1 - Jowy' (f(zo) - f(x")) for a Jow min {1.
(21)
2i 4(M2+1a)
8

---

Published as a conference paper at ICLR 2025
Proof. We start the proof by using upper-bound bound
((++1) Po (2 + l ||ae++1 xzll
yEar { ( (v))(()) + A/2 11111 xx1133
min
22 1ly 1= v=mitanl"" xx,) min (f(y) yERn
f((1 01) axx") + at M M 1| - rell
- fz) + onf(x") a.l1-ai1 ||| - x²'l 1| + oz Mo || x² =²
From the second inequality, we get that the method monotone and f(x++1) S f(x)). Now, by subbing f(x*) from both sides, get
(( az) (f(x)) - [(x')) 2 110 x ((1 -ae) oz Mo
l00 x= II)
3
By choosing Or such that
a M | - z²1 + μa, - 50
(22)
we get (19). By solving the quadratic inequality (22). we get that the method converges with the
rate 19 for all (20). Next, we present Lemma 4.4 with the useful properties of ož from (0) The
more general Lemma B.2maBB.2winn the detailed proof is in Appendix B
Lemma 4,4 For > 0, the function
a a²(2) 1+yT+4 2s
(23)
is bounded by the following lower and upper bounds
[1. {1. } > a (z) > min
min
(24)
2 2V2
and it is monotonically decreasing
Y2,y >
2 <
a (2) a (3).
(25)
The convergence rate well-defined as of S from 24 As fow < a by 24 we get the linear convergence rate 21
||
x²1l S from and
Now, we move the second theorem and prove the global superlinear convergence. The main idea
of the proof is to observe that || - x=I || in (20) decreases for j-Strooggy star-convex functions. This
property allows us to show that N₂ decreasing, and hence at is increasing from (5)). leading to
superlinear convergence.
Theorem 4.5 For u--strongly star-convex Cubic Regularized Newton Method from defined in (5) with G = 1 - aa
function f with L--Lipschitz- coapcchitz-conimmuus Hessian
with M2 2 L2 converges globally superlinearly as
f(x+11) f S (1 (f(z)) - f*).
(26)
where
11--111+40 1+4m 2nst' for K² = (M2+La 3/3/2
(1 a lou/)/22 (f(zo) -
(((0)){((a1) f(z)))
(27)
The aggregated convergence rate for T 2 equals to
((xT) - S(x*) (f(z)) f(x (aa)))[[- azl).
(28)
Proof. From p-strongly star-convexity I7 we can upper-bound ||=r x²1 in 20 by
||, 1 S (2 (f(xz) f(x'))
1/2
((==) (((0)) 1/2
So, we got that || - x=1 is linearly decreasing to zero. From that, we get new superlinear oj S aj
from (27). As xe is getting smaller within each iteration nid > k we get that (xx,") < a(xtt1)
sesl
from 25 Finally, for G. = 1 a(!!), we get & > S++1 in 26 This finishes the proof of global superlinear convergence. The aggregated convergence rate is equal to (28).
Similar results hold for Basic Tensor methods from in general for p 2 2. Next, we present the theorem for global superlinear convergence of Basic Tensor methods.

---

Published as a conference paper at ICLR 2025
Theorem 4.6 For My uy-uniformly star-convex 17 function of degree q with Lp Lipschitz-
contimuous p-th derivative (p 2 q 2 2) (2), Basic Tensor Method from (II) with Mp 2 pLp converges
converges globally superlinearly as defined in (15) with St.p = ai
f(x(+1) f
f s (1 (f(xi) - fr)
(29)
at where Olp.p is such that
Dxt, (att)) O, where ha(aa) = a² 1, ap low = min 1. (p+1)le
1/0
2 (yMpthy)De-tt)
and
sl KLP
(Mpthp)g(oot7/) (0003//00 [p+1)lal94376 (1 ap lownyt/ (f(2o) f(xx))) 1/9
(30)
The aggregated convergence rate for T 2 1 equals to f(xT) f(r)) f(x*) - (f(z)) - ((²")) at,
(31)
To sum up, we present a unified table for μ-strongly (star-)convex functions.
Method
Per-Iteration Rate ar
Glob. Superlinear
Gradient Descent Nesterov
2004
Cubic Newton Method Nesterov.
2008
L
Basic Tensor Method
1/(pi1)
Doikov & Nesterov 2022
DP-T
Cubic Newton Method (NEW)
2/4
1 -
1/2
A," 1/4
Basic Tensor Method (NEW)
1/p
1
L,
1/2p
Table Comparison of per-iteration convergence for different basic methods, where Ag f(zo) [(x") ). To enhance clarity and simplicity, we removed universal constants and simplified 27 and (30p for the case where K₁ 2 1.
We established the global superlinear convergence of Cubic Regularized Newton Method for μ strongly star-convex functions, as well as Basic Tensor Method for -n-ufforrmly star-convex functions. Comprehensive details and proofs are provided in Appendix B
5 CONCLUSION
Limitations. This paper primarily focuses on high-order methods which come with certain limitations. First of all, they have computational and memory limitations in high- nigh-dimensional spaces, due to the need for Hessian calculations. There are, however, approaches to overcome this, such as using first-order subsolvers or inexact Hessian approximations like Quasi-Newton approximations (BFGS, L-SRI). In this paper, focus the exact Hessian to analyze methods' peak performance. Another limitation arises from the specific function classes and the theoretical results considered. Nonetheless, many of the proposed methods be practically applied a broader set of problems. For instance, the CRN performs competitively from general non-convex to strongly convex functions.
Conclusion and Future work. In the paper, we introduced OPTAMI, an open-source library designed to make high-order optimization methods more accessible and easier to experiment with. We plan to expand this library cover wider range of settings and optimization methods in the future. In the first part of the paper, we proposed NATA, a practical acceleration technique. NATA employs a more aggressive schedule adaptation for A,, enabling faster convergence. Our experimental results show that NATA significantly outperforms both basic and accelerated methods, including near-optingg optimal and optimal methods. This opens up another interesting question: Could other high-order methods be optimized by addressing practical issues that arise due to overly conservative theoretical guarantees? Finally, we demonstrated that the basic high-order methods exhibit global superlinear convergence for u-strongly star-convex functions. This result is significant because it shows that high-order methods accelerate with each iteration, in stark contrast to first-order methods, which typically have a steady linear convergence rate. This raises intriguing questions: Can global superlinear convergence be established for accelerated high-on order methods as well? What the best possible global per-iteration decrease that we can theoretically guarantee?
10

---

Published as a conference paper at ICLR 2025
6 ACKNOWLEDGEMENTS
The work of Dmitry Kamzolov in this paper has been partially funded by the Agence Nationale de la recherche under grant ANR-17-EURE-ON (Investissement d' Avenir program), Toulouse School of Economics, Toulouse, France. We sincerely thank the reviewers for their thoughtful feedback and valuable insights, which have helped improve this paper.
REFERENCES
Artem Agafonov, Pavel Dvurechensky, Gesualdo Scutari, Alexander Gasnikov, Dmitry Kamzolov, Aleksandr Lukashevich, and Amir Daneshmand. An accelerated second-order method for distributed stochastic optimization. In 2021 60th IEEE Conference on Decision and Control doi: 10.1009/DDC4444422201..8888 9683400
(CDC), pp. 2407-2413, 2021. ISBN 2576-2370.
URL
Artem Agafonov, Dmitry Kamzolov, Rachael Tappenden, Alexander Gasnikov, and Martin Takáč. FLECS: A federated learning second-order framework via compression and sketching. arXiv
preprint arXiv:2206.02000 2022.
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky, Alexander Gasnikov, and Martin Takáč. Inexact tensor methods and their application to stochastic convex optimization. Optimization Methods and Software, (9())422-8,, 2024a. doi: 10. wa..080001056755 202..2266..22200 URL https:
//doi.org///i http:/100110001155557777 222157788822223888828 22626266660 604
Artem Agafonov, Dmitry Kamzolov. Alexander Gasnikov, Ali Kavis, Kimon Antonakopoulos, Volkan Cevher, and Martin Takáč. Advancing the lower bounds: an accelerated, stochastic, second-order method with optimal adaptation to inexactness. In The Twelfth International Conference on Learn- ing Representations, 2024b. Sellaatpss//opeeeee//e http://wwweeeeoooraaaaaattttttt.
Artem Agafonov, Petr Ostroukhov, Roman Mozhaev, Konstantin Yakovlev, Eduard Gorbunov, Martin Takáč, Alexander Gasnikov, and Dmitry Kamzolov. Exploring Jacobian inexactness second- order methods for variational inequalities: Lower bounds, optimal algorithms and quasi-newton approximations. arXiv preprint arXiv:2405.1 15990, 2024c.
Kimon Antonakopoulos, Ali Kavis, and Volkan Cevher. Extra-newton: A first ap- proach to noise-adaptive accelerated second-order methods. In S Koyejo, S Mo- hamed, A Agarwal, Belgrave, K Cho, and A Oh (eds.), Advances Neural In- formation Processing Systems, volume 35, pp. 29859-2988 Curran Associates, Inc., 2022. URL ht /ttpps//ppooeeeddnnn...eeeee www.:::ss....rri........... co/ httpa//eeeeeppeeeeeeeeeeaaaeaaea files//pape:/2022/
Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second -oddrr methods for smooth
convex optimization. Mathematical Programming, 178:327-360, 2019. ISSN 1436-4646. doi: 10. 1007/s10107-018 1293-1. URL https:://oii.
org http://ddoo.og/11.10101.0000 wtw.:1000////00---11 01 -18-0193-111111111
Michel Baes. Estimate sequence methods: extensions and approximations. Institute for Operations Research, ETH, Zürich,, Switzerland, 2(1), 2009.
Albert A Bennett. Newton's 's method in general analysis. Proceedings of the National Academy of Sciences, 2(10):592-598, 1916.
Albert S. Berahas, Majid Jahani, Peter Richtárik, and Martin Takáč. Quasi-newton methods for machine learning: forget the past, just sample. Optimization Methods and Software, 37:1668- 1704, 2022. doi: 10. 000800005667882221.1199999 10556788 10211.977880
URL htttts::/doi.orr///000 1080/
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near-optimal method for highly smooth convex optimization. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty- Conference on Learning Theory, volume 99, pp. 492-507, PMLR, 2019. URL https: http:s://pooceeeeieeoo wttp:/ml.......peee wwtpps//e////atee www.k////bbbbcbb/.... html

---

Published as a conference paper at ICLR 2025
Yair Carmon, Danielle Hausler, Arun Jambulapati. Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter acceleration. In S Koyejo, S Mohamed, A Agarwal, D Belgrave, K Cho, and A Oh (eds.), Advances in Neural Infor- mation Processing Systems, volume 35, pp. 20338-20350 Curran Associates, Inc.,
2022. URL https: ptttpps://proceeedings neur www.wee....ppppppeeeeee wwtpsaeeeepppppppppaeaeaee wwweerrfffeeeepeeeee wttpf//aeesppaae/22/////2 Flle/EESAATTT2eeebaaaoooeasssss Soneee
Conference pdf
Chin-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM
transactions on intelligent systems and technology (TIST), 2()): 2011.
George E. Dahl, Frank Schneider, Zachary Nado, Naman Agarwal, Chandramouli Shama Sastry, Philipp Hennig, Sourabh Medapati, Runa Eschenhagen, Priya Kasimbeg, Daniel Suo, Juhan Bae, Justin Gilmer, Abel L. Peirson, Bilal Khan, Rohan Anil, Mike Rabbat, Shankar Krishnan, Daniel Snider, Ehsan Amid, Kongtao Chen, Chris J. Maddison, Rakshith Vasudev, Michal Badura, Ankush Garg, and Peter Mattson. Benchmarking neural network training algorithms. 2023. URL.
https://arxiv. org/ als /230 07179
Amir Daneshmand, Gesualdo Scutari, Pavel Dvurechensky, and Alexander Gasnikov. Newton method over networks is fast up to the statistical precision. In International Conference on Machine Learning, pp. 2398-24000 2409. PMLR, 2021.
Nikita Doikov and Yurii Nesterov. Local convergence of tensor methods. Mathematical Programming. 193:315-336, 2022. ISSN 1436-4646. doi: 1011007//10100-0000011666x URL https://ddoi 000:/10.1007.0 00t0000//11110000 10100-000000000 01107-020001666-
Nikita Doikov and Yurii Nesterov. Gradient regularization of Newton method with Bregman distances.
Mathematical Programming, 2023, ISSN 1436-4646, doi: 10. 10.10077/10100--03-09944777 URL
Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularized newton method. SIAM Journal on Optimization, 34:27-56, 2024. doi: 10.1137/22M15194444 URL
https://do::
519444
Pavel Dvurechensky. Dmitry Kamzolov, Aleksandr Lukashevich, Soomin Lee, Erik Ordentlich, César A Uribe, and Alexander Gasnikov. Hyperfast second-order local solvers for efficient statisti- cally preconditioned distributed optimization. EURO Jourmal Computational Optimization, 10: 100045, 2022. ISSN 2192-4406. doi: httpp///c/c............////////.
100045. URL htttss
// 1/www.co www.ssccieceeiiccccm rect. cwm/
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Se- likhanovych, and César A Uribe. Optimal tensor methods in smooth convex and uniformly convex optimization. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty- Second Conference on Learning Theory, volume 99, pp. 1374-1391. PMLR, 5 2019a. URL htttpss:/prrcceedings .ll press wttpprssss///// w9tp//99/g////ovm
9a. htmi
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Se- likhanovych, César A Uribe, Bo Jiang, Haoyue Wang. Shuzhong Zhang, Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near optimal methods for minimizing convex functions with Lipschitz p-th derivatives. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pp. 1392-1393, PMLR, 2019b. mlr wtt.::ss.w...rppes/eeess/..m
URL
9b. html
Saeed Ghadimi, Han Liu, and Tong Zhang. Sccond-order methods with cubic regularization under inexact information. arXiv preprint xrXIv:1710005782,20000 2017.
Andreas Griewank. The modification of Newton's 's method for unconstrained optimization by bounding cubic terms. Technical report, Technical report NA/12, 1981
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor op- timization. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. volume 80 of Proceedings of Machine Learning Research. pp. 1842 1850. PMLR, 10-15 Jul 2018. URL gupt al 8a. html
mlr. press/v80/ wtt.s//s//........////./.
12

---

Published as a conference paper at ICLR 2025
Slavomír Hanzely, Dmitry Kamzolov, Dmitry Pasechnyuk, Alexander Gasnikov, Peter Richtárik, and Martin Takáč. A damped Newton method achieves global O / vergence rate. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 25320-25334, Curran Asso- ciates, Inc., 2022. URL URL. meurip neuri cC wwtpppppppppppettpetep wttppperrr_llseppppeeeeeep Paper Cowfrrroooeeeeececemm Poreeeeeeeeeeeeeeeeeeeeeeeeeeee
and local quadratic con-
Bo Jiang. Haoyue Wang, and Shuzhong Zhang. An optimal high-order tensor method for convex optimization. In Conference Learning Theory, pp. 1799-1801. PMLR, 2019.
Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approximation: A quasi-newton method with global non-asympiotic superlinear convergence. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1962-1992. PMLR, 2023.
Ruichen Jiang, Parameswaran Raman, Shoham Sabach, Aryan Mokhtari, Mingyi Hong, and Volkan Cevher. Krylov cubic regularized newton: A subspace second-order method with dimension- free convergence rate. In International Conference on Artificial Intelligence and Statistics, pp- 441 14119, PMLR, 2024.
Dmitry Kamzolov. Near-optimal hyperfast second-order method for convex optimization. In Yury Kochetov, Igor Bykadorov, and Tatiana Gruzdeva (eds.), Mathematical Optimization Theory and Operations Research, pp. 167-178. Springer International Publishing, 2020. ISBN 978-3-030- 58657-7.
Dmitry Kamzolov, Alexander Gasnikov, and Pavel Dvurechensky. Optimal combination of tensor optimization methods. In Infernational Conference on Optimization and Applications, pp. 166-183. Springer, 2020.
Dmitry Kamzolov, Alexander Gasnikov, Pavel Dvurechensky, Artem Agafonov, and Martin Takáč. Exploiting Higher Order Derivatives in Convex Optimization Methods, pp. 1-13. Springer Inter- national Publishing, 2023a. ISBN 978-3-030-546222 URL https:tt/co....ooo org http://ttoo..g....o/oo
doi: 10.
030 54621 10222-22 2 858-85811
Dmitry Kamzolov, Klea Ziu, Artem Agafonov, and Martin Takáč. Accelerated adaptive cubic regularized Quasi-Newton methods. arXiv preprint arXiv:2302. 022.33...447.2222 2023b.
Leonid Vitalyevich Kantorovich. Functional analysis and applied mathematics. Uspekhi Matematich- eskikh Nauk, 3(6))89-185, 1948a. (In Russian). Translated N.B.S Report 1509, Washington D.C. (1952).
Leonid Vitalyevich Kantorovich. On Newton's 's method for functional equations. Doklady Akademii Nauk SSSR, 1977)122771124,, 1948b. (In Russian).
Leonid Vitalyevich Kantorovich. On Newton's method. Trudy Matematicheskoge Instituta imeni VA Steklova, 28: 104-144, 1949. (In Russian).
Leonid Vitalyevich Kantorovich. Some further applications of principle of majorants. Doklady Akademii Nauk SSSR, (066):49-852. 1951a. (In Russian).
Leonid Vitalyevich Kantorovich. Principle of majorants and Newton's method. Doklady Akademii Nauk SSSR, 76(1):17-20, 1951b. (In Russian).
Leonid Vitalyevich Kantorovich. approximate solution of functional equations. Uspekhi Matem- aticheskikh Nauk, 11(6)99-116,, 1956. (In Russian).
Leonid Vitalyevich Kantorovich. Some further applications of Newton's method. Vesinik LGU, Seriya Matemetika Mekhanika, 0(7):68-103, 1957. (In Russian).
Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high-order
methods in smooth convex optimization. In S Koyejo, S Mohamed, A Agarwal,
D Belgrave, K Cho, and Oh (eds.), Advances in Neural Information Process-
Curran Associates, Inc., 2022. URL ing Systems, volume 35, pp. http:///aaanp..ieeeee/////////// e56f http:ssse.iiir..ceeeeeeeeeeeeeee
13

---

Published as a conference paper at ICLR 2025
Tianyi Lin, Panayotis Mertikopoulos, and Michael I Jordan. Explicit second-order min-max opti- mization methods with optimal convergence guarantee. arXiv preprint arXIv:2210.12866, 2022.
Hong Liu, Zhiyuan Li, David Leo Wright Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. In The Twelfth International Conference on Learning Representations, 2024. URL httpps::/openeeieew...es. wwwp:/rwwwwwwwwwee.r..eeee
idd DeNNN1
Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28:333-383 354, 2018. doi:
10.1137/161009944. URLhttps::///// :/ org/10. 11370/1133/11 099546
Konstantin Mishchenko. Regularized Newton method with global O ((²) convergence. SIAM
Journal Optimization, 33:1440 14622 2023. doi: 0.1137/22M14887555 URL https?
//doi.org/// 1137 1ww..11117/28228888
Renato D C Monteiro and B F Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimiza- tion, 13:1092-1125, 2013. doi: 10.1137/110833786 URL
110833786
Jorge Moré. The levenberg -aanuurrrr algorithm: implementation and theory. In Conference on Numerical Analysis, University of Dundee, Scotland, 7 1977. (RLhttps: /top:::://www../// osti
gov/biblio/725e6
Yurii Nesterov. A method for solving the convex programming problem with convergence rate 0 ). Dokiady Akademii Nauk SSSR, 269(3):543-547 1983. (In Russian).
Yurii Nesterov. Introductory Lectures on Conver Optimization. Science & Business Media, edition, 2004. ISBN 378-1-4613-4661-3- doi: 10. 10.1007/978- 1-419798---1111-889----
Yurii Nesterov. Accelerating the cubic regularization of Newton's method on convex problems. Math-
ematical Programmingg, 12:1111:111111 11: 2008. ISSN 1436 4646. doi: 00000///10000000000085000
Yurii Nesterov. Lectures Convex Optimization. Springer Cham, 2 edition, 2018. ISBN 978-3-319-
91577-7. doi: 00.1007/978-3-319-915577
Yurii Nesterov. Inexact high-order proximal-point methods with auxiliary search procedure. SIAM Journal Optimization, 31:2807-288 2828, 2021a. doi: 10.1137/20M1347055X | https
//doi. 0ttp//10..1377/2011333 34705X
Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical
Programming, 186:157-183, 2021b. ISSN 1436-4646. doi: 10.1007/510100-0099-444449 URL
01 0144141111
Yurii Nesterov. Superfast second-order methods for unconstrained convex optimization. Journal of Optimization Theory and Applicattonns, 191:1-30, 2021c. ISSN 1573-2878, doi: 10.1007/ s10957-021-01930-1
Yurii Nesterov. Inexact accelerated high-order proximal-poin methods. Mathematical Programming, pp. 1-26, 2023.
Yurii Nesterov and Boris T Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108:177-205: 2006. doi: 12..0077/10117--00-077700 URL https:
Isaac Newton. Philosophiae naturalis principia mathematica. Edmond Halley, 1687.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer New York, NY, I edition, 1999. doi: 10.1007/698874.
Boris Teodorovich Polyak. Introduction to optimization. Optimization Software, Inc., Publications Division, 1987.
14

---

Published as a conference paper at ICLR 2025
Boris Teodorovich Polyak. Newton's method and its use in optimization. European Journal of Opera- tional Research, 181:1086-1000 2007. ISSN 0377-2217. doi: http:///oo..og///..000/.....o 2005.06.076. URL https: /www www.ecedieenn...ccc.. http:///ceceeeee//rrttt/e///////
20377221706017
Roman Polyak. Complexity of the regularized Newton method. arXiv preprint arXiv:1706008883, 2017.
Roman Polyak. Regularized Newton method for unconstrained convex optimization Mathematical Programming, 120:125-1433 2009. ISSN 1436-4646. doi: 1011007/5000770007044433 URL
007-0143-3
Joseph Raphson. Analysis Aequationum Universalis Seu Ad Aequationes Algebraicas Resolvendas Methodus Generalis & Expedita, Ex Nova Infinitarum Serierum Methodo, Deducta Ac Demonstrata. Th. Braddyll, 1697.
Sashank Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint arXiv: 066779998.087, 2016.
Damien Scieur. Adaptive Quasi-Newton and anderson acceleration framework with explicit global
(accelerated) convergence rates. arXiv preprint vrXiv:2305.19199 2023.
Ohad Shamir, Nati Srebro, and Tong Zhang. Commumication-efficii distributed optimization using an approximate newton-type method. In International conference on machine learning, pp- 1000-1008. PMLR, 2014.
Thomas Simpson. Essays on several curious and useful subjects, in speculative and mix' d mathemat- icks. Illustrated by a variety of examples. H. Woodfall, 1740.
Nikhil Vyas, Depen Morwani, Rosie Zhao, Itai Shapira, David Brandfonbrener, Lucas Janson, and Sham M. Kakade. SOAP: Improving and stabilizing shampoo using adam. The Thirteenth International Conference Learning Representations, 2025. URL htttps://operreviee
Yuchen Zhang and Xiao Lin. Disco: Distributed optimization for self-concordant empirical loss, In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 362 -700, Lille, France, 07- 09 Jul 2015. PMLR. (ttp:tttss/:/ssotott
.mb.r.gsss.rrrrrmmrr.....r...mmr www....peee/vvvvv 2ttps//33/////gg////1 html
15

---

Published as a conference paper at ICLR 2025
A RELATED WORKS
The origins of Newton method trace back to the foundational works on root-finding algorithms Newton (1687), Raphson (1697), Simpson (1740), and Bennett (1916). The next breakthrough in applying Newton method to optimization and proving its local quadratic convergence rates was done by Kantorovich (1948b a 1949 1951b 1956: 1957p. Over the following decades, Newton's method have been studied in depth, modified and improved in works of Moré (1977) Griewank (T98T); Nesterov & Polyak (2006). Today, Newton's s method is widely used in industrial and scientific computing. For a more detailed history of Newton method, see Boris T. Polyak's 's paper (Polyak) 2007
Recently, second-order methods have taken a new direction in development with the introduction of globally convergent methods achieving convergence rates of O(T-²) (Nesterov & Polyak, 2006) and ( (Nesterov) 2008) convergence rate, surpassing the performance of first-order methods (Nes. (tensor) methods by [aess (2009). However, the tensor subproblem in these methods is nonconvex, leading to implementa-
terov 2018). These advancements were later extended to higher-
tion challenges. This issue was addressed by the introduction of the (Accelerated) Tensor Method in Nesterov (2021b), which resolved the nonconvexity by increasing the scaling coefficient of the reg- ularization term, making the subproblem convex. The basic p-th order Tensor Method achieves a rate of (T-7) while the accelerated version improves this to O (T-(p+1) Earlier work by Monteiro & Svaiter (2013) demonstrated that even faster convergence for second-order methods is possible with the Accelerated Proximal Extragradient method (A-HPE), achieving a rate of Ô (TT-//2) Lower bounds for second-order and higher-order methods of Ω (3p++))))22 were established in (Arjevani itt al. 2019; Nesterov 2021b), demonstrating that the A A-HPE method is nearly optimal for second order convex optimization. Subsequently, three independent research groups (Gasnikov et al.) 2019a Bubeck et al., 2019 Jiang et al. 2019) extended the A A-HPE framework to develop tensor methods with convergence rate of O (T- (3p+1//2)) achieving near-optimal complexity for these higher-order methods. Truly optimal methods with rate of 0 13)+))))) were later proposed in (Kovalev & Gasnikov] 2022. Carmon et al. 2022). Moreover, when assuming higher levels of smoothness,
second-order methods (Nesterov] [202 a Kamzolov 2020) Doikov et al. 2024) have been shown to
exceed the established lower complexity bounds for problems with Lipschitz-continuuus Hessians. For an in-depth exploration of higher-order methods, see the review in (Kamzolov et al. 2023a)
Since second-order and higher-order methods generally incur greater computational costs due to the need for calculating higher-order derivatives, it is natural consider inexact or stochastic algorithms to reduce these overheads. In convex optimization. several studies have explored globally convergent second-order methods with inexact Hessians (Ghadimi et al. (017)), higher-order methods with
inexact and stochastic derivatives (Agafonov et al. 2024a] Kamzolov et al., (020). and adaptive stochastic methods (Antonakopoulos et al. (022).. In (Agafonov et al. 2024b), a lower bound of established for stochastic globally convergent second-order methods,
Ω ( 7 + 7773
where T1 and d2 represent the variances of the stochastic gradients and Hessians, respectively. Addi- tionally, the Accelerated Stochastic Cubic Newton method was introduced. achieving a convergence
rate of O /T +
f3 ) which, to the best of our knowledge, represents the state-of-the -hrt result.
Inexact second-order derivatives also studied for min-max problems and variational inequalities Lin al. (2022) ; Agafonov et al. (2024c). Inexact second-order methods enable the use of Quasi-Newton Hessian approximations, w which are well-regarded for their strong practical performance. Although classical Quasi-Newton (QN) methods are known for local superlinear convergence but lack global convergence, their integration with cubic regularization has led to globally convergent methods that also feature relatively inexpensive subproblem solutions (Kamzolov et al. 2023b [cieer 2023 Jiang
et al., 2023). Second-order methods with inexact or stochastic derivatives also hold promise for distributed optimization Shamir et al. (2014); Reddi et al.
(2016); Zhang & Lin (2015); Daneshmand
et al. (202I); Agafonov et al. (2021): I): Dvurechensky et al. 2022 Agafonov et al. (2022), offering an
effective way to manage the computational demands typically encountered in distributed settings.
One actively developing direction relies the constructions of Cubic Newton with explicit step in
order to reduce the complexity of solving methods' subproblems Polyak (2009) 2017); Mishchenko
(2023); Doikov & Nesterov (003): Doikov al. (2024): Hanzely al. (0022)
16

---

Published as a conference paper at ICLR 2025
B GLOBAL SUPERLINEAR CONVERGENCE
In this section, we show the theoretical global superlinear convergence of high-order methods (p 2 2) for j-strongly star-convex functions.
Theorem B.1 For Hy-uniformly star-convex 17 finction f of degree 2 2 with Lp L.ipschitz-
continuous p-th derivative (p 2) (2). Basic Tensor Method from 11 with M, (p L)
converges with the rate
(x(+1) l S (1 ((ai)))
(32)
for all ai.p 2 kttp 2 0 such that
hecp (at.) S 0 and Kun.p (ai =0, where (a)a) a2k-a-1 and Kt,p
(x+1)
(33)
This range includes the classical linear rate
[1.1 (0+13
1/p
((x)) - f(xx(((==)))))))())) 0g tow
(f(z)) - [(x")) for Now min
2:2
(34)
Proof. We start the proof from an upper-hound (
[(1++1) =
Dz (1 + (ptty) |1aet] - 24 1ptl
min
T (z,,(()) +
Mr (p+1x) lly xea sallpti]
yER"
lyy - xell (1ttt]] yeestanlee -xx)
min yERn
f(y) + My+he [I+I]]
f((1 at.p) + at. x* + oh. To+iyl
My
1x 21110
(1 - (1.o - an. a1p(1- - aep)) l x" l| +
p+l dlttLp ||,0" - xeel xelpptt dtp (ptI)!
From the third incquality, we get that the method monotone and f(1++1) S f(x1). Next, we subtract f(x") from the both sides and get
(((")))(((") (1-or.)) (J(x)) - f(x))) are x01e==111" (11 -a)) )
g(Mp+ta)) ar [p+1]!
|is xx 2'1ptt10))
If we choose a such that
a p (p+1)!
(Mo+Lp)
||,e x 20110-0t1 + parp S
equivalent version
g(M++Lp) o 1p+1)|mg
| x'11p-0t1 otp - 150,
we get (2). To understand the solutions of such inequality, we present Lemma B.2 with the useful
properties. From this Lemma, the convergence rate is well-defined as 0 < ai < from (36. As
||0 x² < D from and a.ow S aol by (36), get the linear convergence rate 34
Lemma B.2 For z > O, the solution a² (z) of
h2 (z)) = O, where
h2(a) = -a
(35)
has the next constant lower and upper-bound
min } a" (z) min 1 22-70
1
(36)
This bounds show that, for 2 1, the solution a' (z) is similar to z -1/ up to constant factor as - >> a (z) > 0.5z-1/2
1/2
For S we get the next improved upper and lower-bound - 2 a² (2)
(37)
which means that for z + +0 we have (z) 1
The solution a2) monotonically decreasing
V2,y> 0:
y
7 a a=())> > >(()))) a²())
(38)
17

---

Published as a conference paper at ICLR 2025
Proof. We start the proof from the upper-bound inequality. Note, the function h2 ha) a + a 1
is monotonically increasing for a 2 O, as ha))) = pa. 2 + 1 > O. As hg) -1 and h1( = 2 > 0, we get that the solution is unique and a (2(2) E [0: 1]. Next, for 207p we have
h
- शोे
2 0,
which means that min (1, g3/6 } > a" (z) and we proved the upper-bound.
Next, we move to the lower-bound inequality. For 2 2, 2 and 2217p we have
h2 (2())))))) ~ 2 + 2
Σ + + 2
- O,
where the first inequality is coming from 2 1. The second part of lower- bound holds for 0 < 2 < 1 because
h+) 27 + 1 1 < 27 2 < 0.
We proved 35 Now, to understand the behavior of x² (z) for 0 < 2 S 1, we improve the upper and
lower-bound for 0 < 2 S 1. For < = S and a = - 2, we get the improved lower-bound
(1 - 2) = (1 - 2) +
- 1= (1 - 2)²²
((1 -01-21 2)² - 1)2 < O.
For 2,0 < = - and a = p+I. we get the improved upper-bound
h1 (1
p+i
=
11
p+1
=
++1
p+1
=
(1
p+1
2
2
p+1
2 2> 0
(39)
(p+1)"
where use the last inequity or p 2 we need to use some additional analysis. We introduce an additional function and its derivatives
s(x) z log(z)) (x log(x + 1),
s(x) 2
Itx + log (1-11 (1-++)).
1-z s(x)" =(1+2))
It is clear that s(x)" < 0 for > 1. It means that s(x)' is monotonically decreasing. s(1)'
1- (2) > 0 and the limit lim s(x) = 0, hence s(x) 2 and s(x) is a monotonically
increasing function. s(1) = O, hence s(x) > 0 for 1 and finally x.' (x +)== for > 1,
which proves (39) and finishes the proof of the improved upper-bound (37.
Finally, we show that the solution a'(a) (2) is monotonically decreasing with Let 0 y and a (z) and a (y) are such that (a (z)) = and (x)) = 0, then
a" a")""y + a (=)-1
351
a ( (=)²== - 1 = a² (3) 0,
which proves that a* a(x2)))) (z) a" (y) and hence the solution a" (z) is monotonically decreasing.
Now, we proceed the second theorem to establish the global superlinear convergence of high- order methods. The key idea behind the proof is to observe that [2r -x"| in (33) decreases for 16 uu-uunifomlly star-convex functions. This allows us to notice the fact that Kt,p also decreasing, hence Ot.p increases according to 38 ultimately leading to superlinear convergence.
Theorem B.3 (Copy of Theorem 4.6 For uniforrly star-convex 17) function I of degree q 2 with Lp Lipschitz-comtimouus continuous p-th derivative (p 2 q 2 2) (2), Basic Tensor Method from 11 with
M, 2 (p L) converges converges globally superlinearly as defined in 15 with Ct,p 1 o
[(x+1)) - s (1- a (f(x))
(40)
where ot, is such that
1/p
hagt, (art)) 0, where h₂(a) = a + - ap
low = min
1. 1
(p+
2: (TM,,tL DDV -+
(M and k (p+ 1p+1)/a/7177 (1 a lowst/9 (f(2o) f(x")))1/4
(41)
The aggregated convergence rate for T 2 1 equals to [(TT) - f(x') < (f(zz) f f(x (x=))) -
(42)
18

---

Published as a conference paper at ICLR 2025
Proof. From j-uniform star-convexity 17
we can upper-bound || x²1 in 333
|| - x"11 - (at -(==))
1/9
a1--aa0 louy ( - f(x")) 1/4 1 ((11-
So, got that || x²Il is linearly decreasing zero. From that, get
superlinear Cp S 0tp from (41) As riç" is getting smaller within each iteration Ki,p > kt+1,p we get that
aal
Kel
a(<ip)) < ax from (38). Finally, for Stp =1 a(st,p) we get St.p > (e+1,p in (40) This finishes the proof of global superlinear convergence. The aggregated convergence rate equals to (42)
C SUBSOLVERS
C.I SUBSOLVER FOR BASIC TENSOR METHOО
In this section, we introduce the subsolver, called Bregman Distance Gradient Method (BDGM), for the Basic Tensor Method of order 3
122
Tz4-1 3t + argmin
{1(x)) (f(..)) [4] + f(x)) [n] + (D [b]* |b] { (43)
hEE
The first effective subsolver was introduced by Nesterov in Nesterov 2021b, Section 5) and later improved in (Nesterov 2021c). Next, we describe the BDGM subsolver by following the (Nesterov
2021ch.
Relatively inexact p-th order solution. of
First, we introduce the relatively inexact p-th order solution
NM,, (1) {u E E: I, (v)ll S [
(44)
where E 10,1) is an accuracy parameter. Then from (Nesterov 2021c any point y E NNM, (a) satisfies
Theorem 2.1), for and Mp
Le such that y M,
f(x) - f(v) M, |+ where Mg
[1-
1
Note, that for the exact solution, we get the same improvement guarantee with 0. For p 3 and we choose ? 1/6 and M3 6L3, then (2, Arl/ (x) and the method
J++1 E (#1
converge with the same rate up constant as an exact version (Nesterov 2021e Theorem 2.2).
Note, M3 2 3L3 is also required for the convexity of the subproblem (43). In our implementation. all third-order basic steps are solved with this relative inexactness and M, = 6Lg. This approach creates practical and parameter-free stopping criteria for the subproblem solvers.
Relative smoothness and relative strong convexity. Now, we move on to the concept of relative smoothness and relative strong convexity proposed in (Lu al. 2018). Similarly to classical smoothness and strong convexity, we say that function Φ(h) is relatively smooth and relatively Pe strongly convex with respect scaling function p(h) if
Hp 2 p(h) P(phh) = v2)(h) = L.
In classical regime, p(h) ||4 and p²p(h) ) an identity matrix. For the scaling function p(h). we introduce its Bregman distance
(p, v) p(y) p(h) (Vp(h), y- h)
Now the gradient method with respect to this Bregman distance is called Bregman Distance Gradient Method (BDGM) and has the next form
het1 argmin yEE
(egmin((Voln ((Vo(ha), ha) + (1kks
The convergence rate of such method is
Le Po
log (((ho)-o(h")
19

---

Published as a conference paper at ICLR 2025
Bregman Distance Gradient Method (BDGM) for (43
Let's apply this approach the solution
of subproblem (43) with Ms = 6Lz. In (Nesterov
2021c Section 4), it was shown that the
subproblem function (h)) = (xx) ) [t] + f(a)) [ (xx4 [M] + La [|A]] is relatively
smooth and relatively strongly convex with respect to
p(h) = / 2 (ax) [n] + 4 4 |/|
with constants T,p 1
and Mp
It means that the method has an incredibly fast The details and more formal convergence results
V2
/2
convergence rate 0 are presented Nesterov 2021c).
.2+1 V2-1
log o(ha)-o(kh)
)
Now, we present the explicit formulation of the BDGM for (43 First, we have the general form ( ((Vo(h+), h&) + p yEE
ha+1 = argmin
(45)
Let us calculate Vo((s) first. It equals to
Vo(hx) = ff(=)) + f(ri)h, + f(x)) [hx]² 2=1++ + La Lallhallhh.
In (Nesterov) 2021c). the universal approximation for Dd fzz) [hy] 2 is presented by using the finite
differences approach. However, in practice, we recommend using autogradient computation of (xx) [ha] if it is possible. The computation by autogradient is much more precise while having
the computational complexity. The computation complexity of D2 (are) [ by autogradient
similar to calculating three gradients as D fax [h]² V. ((>))())))))) V(V (V (z)( [h]). Also, autogradient computations are commonly used in modern frameworks such as Py PyTocch, Jax, and others. So, essentially we still have access to third-order information but with the complexity of gradient computation.
Now, let us calculate explicit (p(hx. y)
Bp v) p(y) p(h) (Vp(h),y-1 h)
= f [y] + 11vll fxx, [ha]2
4 |
(z))(z) [hv] + L3 1 h4 hx)
Note, that the constant terms are useless for finding the argminimum them. We also can divide all parts of (45) by 2Lp = 2 + /2 for simplicity and unite the linear parts together
45
hence we can remove
gk 2+v2 Vo(ha) f(x) [ha] Lss Lss1hal12tu
2-v2 (Vf(z))
+ f(z)()) + 1 [14l + Lall Lsllhallhha) V2 f(xe)) [ha]] - Las hall
2 2-
Dス ((x)) (km) [mml²)
L (v² [ma] + 2all/ee1111
So, we finally get the next explicit BDGM step
h argmin { (gk. v) + / (xx) |0]² La
(46)
yEB
This step doesn't 't require the computation of a full third-order derivative and is similar to the Cubic Regularized Newton step. Hence, we count it as second-order method. So, the total complexity of
Basic Tensor Method for convex functions is Ō LaD" steps of (46). where Ö(-) means number of iterations up to a logarithmic factor.
Inner subsolver for (46). The last part is to solve 46). We solve it similarly to the Cubic Regularized Step by ray-search with eigenvalue decomposition (EVD). First, we apply eigenvalue decomposition to fxx))
[xx) = USUT.
(47)
20

---

Published as a conference paper at ICLR 2025
where S E Rdxd is diagonal matrix with eigenvalues and U Raxd is an orthoganal matrix such that UUT = I. Then, we denote = y and 9 = U gk- Now we can formulate a dual one-dimensional problem.
min yEE
{ (9x, v1) + (V2 (1 w) + - l1vl1*
min { (UT) 9h U v) (USU ツ. + 11 y1**}
wEB
min
{ (g. 0) + (Sv, 6) + - ||]|
wEE
min max wEE r20
(g.0) + (Se, + v2La ||:11 1
max min 720 vEE
(g. u) + (Sv. v) + V ||:1| - 7
( -1 0.9 2
max r20
1
(48)
where 7" solving (48) with oie-dimensional ray-search, we find optimal 7" then we can calculate e and y. which we found the solution for subproblem (46). In our code, we use eigenvalue decomposition for efficiency of the ray-search, but it also possible to just inverse the regularized matrix multiple times in 48 apply some efficient first-order method for quadratic problems such conjugate gradient.
22La
|||2 for the third equality and - (S+
in the last equality. By
To finalize, in this section we presented the subsolver which allows us to efficiently implement the Basic Tensor Method for p = 3 with the complexity same up to logarithmic factor as Cubic Regularized Newton Method.
D METHODS
D.1 NESTEROV ACCELERATED TENSOR METHOOS
In this section, we present Nesterov Acceleration for tensor methods proposed in (Nesterov) 202 c First, let us introduce the main parts of the method. The key part of such acceleration is the estimated sequences technique. It is based on linear approximations of function f(z) in sequence of points Ie, which allows to construct the estimating function (x) for a scaling sequence a, E R4:
14 (=) = (x(=) + a (f()) + (V/(z), =)),
where vo(2)
p.r || - zollpt1 (49)
Additionally, we introduce the sequence
A41 A + ac.
(50)
Now, we ready present the accelerated method.
Algorithm Nesterov Accelerated Tensor Method
Input: 2g is starting point; constant Lp, total number of iterations T. and sequence A,, where
An = O.
2: Set objective function
vo(2) = -+1l1= xo Pt
3: for > do
4: Choose 1/1 A.1
As + ac+1 Ut2
Ar11
5:
Compute I++1 E NLt (y:)
6: Compute a++1 = A++1 A
7: Update v (x) = vi (2) + aa41lf(( + (Vf(#41); 2(41)].
8: Compute 1141 = argmin (2)
9: end for
10: return #7+1
21

---

Published as a conference paper at ICLR 2025
For the convergence results, the sequence A, should be defined in the following way
2p-1 A "e 1 where Up (p+1)(2p11 Lp
(p-1)) 1
(51)
(2p)
Then, 0c+11 theorem from (Nesterov
#z (tt + 1) - (.+1). With such parameters, we can present the convergence
Lp
2021c Theorem 2.3)
Theorem D.1 Let sequence (2a)22 be generated by method
Then, for any T 2 1, we have
f(rr)-f(x*) 50
TolI
D.2 NESTEROV ACCELERATED TENSOR METHOD WITH A,- ADAATATTOI (NATA)
In this subsection, present the proof of Theorem 3.1
Algorithm 4 Nesterov Accelerated Tensor Method with A--dapttiion (NATA)
Input: 2g og is starting point, constant Mp. total number of iterations T, Åo 0, ymin Upp mmax 2 Vp is a maximal value of v, f > is a scaling parameter for v, and vmax is starting value v.
2: Set objective function
v0(()) = -+ 1| z0o woolptt
3: for t 2 0 do
4: repeat
V' max s'
5:
0 Vunin
6:
de+1 In 12111 + 1)pt2 -opt1-10 -P-1) and Aot = À, + Øe+1
A.Te + Bet2
7:
V1 A111 Ac11
8:
21+1 = =Ni, (yt)
9:
+ (+) = [+((2) (12)+ ăc+1lf (allooi)++(////aiiii (Vf(1++1); - r(+1)l
10:
U141 argmingeg (2)
until (1+1())44) A441f(2441)
12:
D=+1 min 2'' Mmax }
13:
end for
return 3T+1
Theorem D.2 (Copy of Theorem 3.1 For convex function f with Ln--Lipshhteecomtiinee p-th derivative, to find IT such that f(Tr) f(x") I s, it suffices to perform no more than T 2 1 iterations of the Nesterov Accelerated Tensor Method with A, Adaptation (NATA) with Mp 2 pLp (Algorithm 2), where
(
(L
T T= 0
p+l
logo fmm!
(52)
Proof.
Let present the convergence analysis of Algorithm 2 (Nesterov] 2021c).
The proof is based on the proof from
First of all, by convexity and definition of thy (z). it is easy to show that
S Azf(x*) + -|~"" zoll=-1 $
(53)
Now, 1et us assume that the condition on Line 10 is satisfied for every step. Then, we get
(x) & (v(())) ve(x*)) < Ār((x")
- xo 1o1
(54)
22

---

Published as a conference paper at ICLR 2025
where in the second inequality the definition of Ug. Next, by simple calculations, we get the convergence result
f(x,) f(x)) I 112- 11l
(55)
(p+1)A+
From that inequality, we want to have a more aggressive â and start the search of from the maximal value. Now, we need show that the condition in Line 10 is always be satisfied.
that the larger A, means the faster convergence. That is the reason,
Let us prove it by induction of the following relation:
1/ (1)) 2 (z)( 12 0.
(56)
For 1 = O, we have v/ = and Ao = 0. Hence, 56 is valid.
Assume it is valid for some & 0. Then,
0 = (1(14+1) + āet1 (f(x441) + + (Vf(=41)) (144 u141 xx-1)) (++))2F-T ||u++1
1/ 12|1 + θe+1 (f( + (Vi(xe+)), U241 - x)+1)))
where the last inequality is coming from uniform convexity of || I|ptt. Now, we can use the structure of the method in previous inequality and get
48+1
(p+1)20- 1041 w/ I| Acs(x:) + āzt1 (J( (VI(121)) xx+1))
A411((141)) + (V (44/241),0444(000 (1141 T1+1) + Ae 0(+1))
A (* + (V (V]((++)) ( - vz) + A (3t - x(+1));
where, for the second inequality, we use convexity and, for the last equality, we use the definition of from Line 6 of the Algorithm 2
Further, we use inequality p+I r Br 2 have
p4I a -//0////011 2 0. for all xr E E and we
p
(p+1)2 [1241
vrl wtllpt pp ăzfi (V[(s())) U141 - vo) 2 p.pp
(ār+1 (/+++//((0+++)))))
(57)
Next, for #++1 E ENL, (VK), from Nesterov 2021c
Theorem 2.1), we get
(Vf(ze+1) m+41) 2 ([( 211
1/p for relative inexact p-th order solution.
where Co
2p-1 1p(2p+1] Lp
p!
Putting all these inequalities together, we obtain
R-1
p+1
at1
th+1 2 AA41f(0441) - p-12 ( (((et)ll)))
+
g+1
p- R+1
=Anns(0e))) [V ALticp- - p 0,41
Finally, by the choice of of Algorithm vt 2 Up and āeạ1 2 0141, where ax+1 Pp ((1
I
1)s+1 - 1P+1) the theoretical value of d1+1. Hence, Årt1 2 A where A = "r (1 + 1)
Ip
the theoretical value of A441. So. in the final inequality, prove that there exists v/¹ Up such that
p+1 1
Am1o 2 A+110 2 P
where the last inequality holds from (Nesterov 2021c induction step.
Equation 25). Thus, we have proved the
23

---

Published as a conference paper at ICLR 2025
The search of y² takes maximal total of loge
+ T additional steps, where 1
[aX] U² S y and ui = mi of 2 yuun = Up. The 7 term in the sum coming from Line 11 in Algorithm If we want make the Algorithm less aggressive, Line then v' will only decrease.
2
remove this
The total number iterations hence is equal T O -0((etett) p+1
logo
which
finishes the proof.
D.3 NEAR-OPTIMAL TENSOR METHODS AND HYPERFAST SECOND-ORDER METHOD
Near-optimal Tensor methods. Monteiro & Svaiter (013) demonstrated that the global conver-
gence rate of second-order methods be further improved from O (e-1/3) O (e-2/7 log (1 (1/e) This improvement was achieved through the development of the Accelerated Hybrid Proximal Extragradient (A-HPE) framework, which, when combined with a trust-region Newton-type method, resulted in the Accelerated Newton Proximal Extragradient (A-NPE) method that achieves the im- proved rate. A lower bound of O (s-2/7) was established by Arjevani et al. 2019 rendering that the A-NPE method is nearly optimal.
Near-optimal tensor methods Gasnikov et al. 22019a) Bubeck et al. (2019): Jiang et al. (2019). with a convergence rate of O 2/(3++1] log (1/=)). are based on the A-HPE framework. Similar to A-HPE, these tensor methods require additional binary search procedure each iteration. The cost of these procedures introduces an extra O (log(1/e)) factor in the overall convergence rate.
Algorithm Inexact p-th order Near-optimal Accelerated Tensor Method (Kamzolov rithm 1)
2020 Algo-
1: Input: 20 = is starting point, constants Mp. Y E [0, 1), total number of iterations T, Ao 0.
2: Set Ao 0, to
3: for t 2 do
4: Compute pair det1 > 0 and T++1 R such that
1
Mp || yellp-1 5 p+1
S A++1
(58)
2
(p - 1)!
where
J++1 E Nr p.M,
NM,MM, (11)
(59)
and
det1 + / x2 + 4d
A
a++1
0++1
AA41 = A, + ac+1
and ye = A,
+
Ut
2
A
(60)
5: Update U1+1 = Ut 0141 vf(+41)
6: end for
7: return УK
One version of the near-optimal tensor methods is presented in Algorithm 5 This version was initially proposed by Bubeek et al. (2019) and later improved by Kamzolov (2020), who introduced the handling of inexact solution to subproblem (59) Note that line (4) of AlgorithmmJrequin the pair (I1+1, which in turn depends y through (59) Furthermore, Ye depends d1+1, which itself depends on A++1 as per (60). This recursive dependence implies that A441 relies on itself, making it impossible to solve in closed form.
finding which canmot be done explicitly. Specifically, A depends on Ø141 via (58).
24

---

Published as a conference paper at ICLR 2025
To find the pair (I(+1. \(+1), binary search procedure is employed. Below, provide the approach A
used by Bubeck et al. (2019). Let denote 0
[0, 1]. Thus, both yr and I++1 depend on 6,
A++1
yr (0)
Ozt + (1 0)Ux,
F++1 (0) == I++1
No. (O).
02-1 we have that de+1 (1-0)² 8 A.. Thus, in terms of 0, 58 can be rewritten
Since Ac+1 Act1
2 S ((0) S p+1' where ((0) = (1 -0-03 0)2 A.Mp
1
| (0) y1 (0)
(61)
0
(p 1)!
Note that ((0) + +o0 and ((1) = 0. Hence, one can use binary search to find such that 661 holds true. The complexity of this procedure O (1og(1/E)), and theoretical analysis of binary search procedure can be found in Bubeck et al. (2019). Below we present the total complexity of Algorithm
Theorem D.3 (Kamzolov, 2020, Theorem 1)) For convexffuctionn f with innpLiipchittt-comiuuus p-th derivative, to find Fr such that ((TT) f S e, it suffices to perform no more than T 2 iterations of Algorithm with H, LLp, where & and 7 satisfy 12 27 E[p-1j and
Ō= T H2 (
Hyperfast Second-order method. Interestingly, the lower bound for second-order convex op- timization, 0 (6-7,, can be surpassed under higher smoothness assumptions on the objective. Nesterov (202Tc) showed that, under the assumption of an L3-Lipschitz third derivative, Algorithm T can be implemented using only second-order oracle, with the third-order derivative approximated via finite gradient differences. This results in a second-order method with O (c (-1/4) calls to the second-order oracle. The same idea be applied to Algorithm improving the convergence rate of the second-order method to Ô -1/5) Kamzolov 2020)).
Theorem D.4 (Kamzolov) 2020 Theorem 2)) For convex function with an La-Lipschitzz continuous third derivative, to find xT such that f(тT)-fe < it suffices to perform no more than Ni gradient calculations and N2 Hessian calculations Algorithm with BGDM as the subsolver for the subproblem 59 Hp = 3Lpp22 2, 7 1/6, and
L
G + H
N₁ Ō
log
(((Lett)))
(L
t
N2 =
where G and H are the uniform upper bounds for the norms of the gradients and Hessians computed at the points generated by the main algorithm.
D.4 PROXIMAL POINT METHOD WITH SEGMENT SEARCH
Another approach for constructing near-optimal tensor methods involves high-order proximal-point type methods Nesterov (2033 202 which are based on the p-th-order proximal-pone point operator:
prox,, (v) = argmin { (fup.n(()= = f(x) + 2E3
H p+1 ||
yl p+1
(62)
Nesterov 2023) demonstrated that using a single step of p-th-order tensor method to solve 62
results in convergence rate of O(c-1/p), and moreover, this approach can be accelerated to achieve a rate of ((c O(<-1/(++1)) 1/(++1)). Another significant contribution of Nesterov (023) is the introduction of proximal-poie operator with segment search:
Sprox (y, u) argmin
{f(z)
H || y Tu|l=+1] 1 + p+1
(63)
rEE, 7E(0.1
25

---

Published as a conference paper at ICLR 2025
Assuming that (63 be solved exactly, Nesterov (2023) showed that convergence rate of O ((e--/((p+1)) can be achieved via different acceleration scheme.
more practical algorithm was introduced Nesterov (021a). Following Nesterov (2023) the authors assumed that the problem (62) can be solved under the following approximate condition:
12 (v) fo E E: Vf.p. (x))l= - B / [
where y E [0, 1) is tolerance parameter. Furthermore, specific approach for approximating the solution to subproblem (63) was proposed. The resulting method, called the Incxact p-th-order Proximal Point Method with Segment Search, is presented in Algorithm Lines o4 Algorithm detail the steps for the approximate solution of 633
Algorithm 6 Inexact p-th-order Proximal Point Method with Segment Search Method (3.6)
(Nesterov
202 a
Input: zo vo starting point, constants H y E [0, 1). total number of iterations T.
An = 0.
2:
for 0 do
3:
Set
Tt.
4:
Compute z E A
p. (2z).
5:
if (=)()) ux) 2 0, then
6:
Define (2) = f(x)) (Vf(z)), 24), 0411 -1.90=1V((+)1
[Vf('))
7:
else
8:
Compute ot A (wz).
9:
(Vf(z)), u1) I 0, then
10:
Define (z) = f(x!) +
= x/. 9: [
else
12:
Find values 0 S Tł. < + < 1 with points 1/ E Ap. (xt + T/ w+) and
wi A7 (5+ u.) satisfying
8 505 Br and ar(T! - -,) 5 1-7
1/p
9t
where 88 = (Vf(w)) w+) 3 (V](wv u1) at - E [0, 11. and
p+1
9: = aull [vll + a1-
Set
(b(2) = 0n (f(w)) (VS(w)); - + (1 ar) ( = -w?)),
Ft+1 an + (1 an w/
13:
end if 14: end if
a?_1 1- 1/v 1-2
Compute a++1 > 0 from equation Acto,:1 2 [
Di ?
16: Set A = A₁ 0++1 and update (x+1(2) = (2(2)) + ()-1
Set U141 argmin (2)
=EE
18:
end for return 2T
19:
Theorem D.5 (esterov 2021a, Theorem 2)) For smooth convex function f to find vT such that
f(xT) f < c, it suffices to perform no more than 2 1 Literations of Algorithm where
H 1
3p+T
==
26

---

Published as a conference paper at ICLR 2025
(estteovv 2021 Theorem 4). This results the following upper bound for the number evaluations of w A Ap (T)
Line 12 requires additional bisection search with complexity of O HDD
during the execution of Algorithm 0
@ (1
MD
HDDt1
log
Under the additional assumption of an Ly LypLiisscitzz continuous p-th derivative of f. the inclusion E Ap.H (z) can be achieved by performing one inexact tensor step with specific choice of
parameters 3 and Mp: w E A p.Mr, (z) (Nesterov 2023, Section 3) (Nesterov 2021a, Section 5.1).
This makes Algorithm 6 a near-optimal Tensor method, comparable to Gasnikov et al. (2019b);
Bubeck et al. (2019): Jiang et al. (2019). However, it differs in nature: while the latter methods are based on A A-NPE-type approaches, Algorithm| follows an anterior-point-yype framework.
For the case when p = 3, the tensor step can be efficiently performed using BDGM in O (log 1/s) iterations. As demonstrated in Nesterov (2021c); Kamzolov (2020), a second-order implementation of a third-order tensor method can be achieved by approximating the third-order derivative using finite gradient differences. However, in practice, this approximation may suffer from numerical instability. For Algorithm [ anotter approach is available: the interior-point subproblem (62) can be solved using a second-order method [ (2021a), which provides more reliable alternative finite gradient differences. Under the assumption of an L3 Lg-Lisschitz continuous third derivative of f. Algorithm 6 achieves convergence Ô (s-1/5).
D.5 OPTIMAL TENSOR METHOD
An Optimal Tensor Method was recently proposed by Kovalev & Gasnikov (2022) Carmon 2022), improving upon the convergence of near-optimal tensor methods Gasnikov et al. (2019a): ; Bubeck et al. (2019;; Jiang et al. (2019). The convergence rate was enhanced from 0 (3p+1) log (1/=)) to ( 2/(3+11)). matching the lower bound Ω (s 2/(((())) Arjevani
al. 2019). Similar to near-optimal methods, the Optimal Tensor Method is based on the A-HPE
framework proposed by Monteiro & Svaiter (2013).
Before describing the Optimal Tensor Method, we introduce some necessary notations. Let o denote the p-th order Taylor approximation of the function
(g y) = p(v) +
DJ )())( y)*
(64)
1=1
Additionally, note that (, v) = $,(2, y) as defined in fx) + 1= 2/
We also define the function ga (x.,))) y) =
The main distinction from near-optimal methods lies in the procedure used to find the pair (Iz+1, 1.+1). Instead of first computing Zx++11 and then using binary search to determine A as done in previous approaches, Kovalev & Gasnikov (2022) first select the parameter Ae+1 and then compute 2++1. This procedure, known the Tensor Extragradient Method, is shown in lines 6 I0 of Algorithm| 7 This method converges in a constant number of iterations, lcading to the optimal convergence rate of O (e -2/(3++)) for Algorithm 7
Theorem D.6 ( (Kovalev & Gasnikov, 2022 Theorem 5)) Let Mp Lp and 1/2. Let
(3p (M, O)
1
V
1-0
PdM (1+
where Cp(Mp,0)= = pl(pM, - Lp) L,)p + Lp)p/2211
Then, for convex function f with Lyg-Lipschitz-cee ciipschitz-coniiuuuss p-th derivative, find rr such that f(xr) - - S c, it suffices to perform no more than 2 1 literations of Algorithm where
T= 5D, (T.p
J + 7,
27

---

Published as a conference paper at ICLR 2025
Algorithm 7 Optimal Tensor Method (Kovalev & Gasnikov 2022, Algorithm 4)
1: Input: To is starting point, constants Mp. (0, 1), total number of iterations T, Ao sequence a₁ 11(3-11//2 for some 0.
2: for 2 0 do
a1+1
3: A++1 = A, at+1, d4t1 A+41
4: Vt At+1 2t As+1 Ut
4111
5: vi 1/,, k=
6: repeat
7:
of argmin yEE
$ Te (rste)
(ys (v,
(p+1y] 11y u A1ptt1
pddp
8:
V1
k+1 yt
V Varce (ak.31) 31)
(p-1))
9:
k 1 +1
10:
until Vggeas (at Hclll |1 S oxt 11107 - well
11:
Ft++1 2t
Update 04+1 ut - a4+1 (8(+1))
13:
end for
14:
return 27
with Dp is defined as follows:
3 (3p 1)pt (p- 1) Dp
T
20+2 /ppl(p2 - 1)
E EXPERIMENTAL DETAILS
Setup. All methods and experiments were performed using Python 3.11, PyTorch 2.2.2, on a 13- inch MacBook Pro 2019 with 1,4 GHz Quad-Core Intel Core i5 and 8GB memory. All computations are done torch.double. All methods are implemented as PyToorch optimizers.
Logistic Regression.
The logistic regression problem can be formulated
f(x) 1 - log (1 1 (-(b(aaa)))) + 1
(65)
where E Rdd are data features and b; E (11;1} are data labels for 1,...,
We present results on the a9a dataset (d 123, n 32561) and w8a (d = 300, n 49749) from LibSVM by Chang & Lin (201T). We choose the starting point
3c, where is a vector of all ones. This choice of zg allows us to show the convergence of the methods from far point. For Figures
and 7al we choose the regularizer μ 10 get strongly-convex function f. For Figures and 8, we choose the regularizer μ = to get convex function f. For the better conditioning, normalize data features ||a,]| 1. For the normalized case, choose theoretical
6
5
L2 0.1. We set L3 = L2 = 0.1 to demonstrate the convergence rates for the same constants Note, that actual Lag is smaller than 0.1.
28

---

Published as a conference paper at ICLR 2025
wBa, Logistic Regnession
w8a, Logistic Regressio
191
191
10a
20
10-4
10-2-
Newinn w01.11
10-3-
Accolorated TencorMettedd Ly
400.11
Ly
Near- Cubic -01
NeanCpttmal Temer 4-101
Cubic frox. Paint Segment Search. 0.
Terser Prox. Point Sugman: Search, L,-0.11
Optimal Cubic. 1a 0.1
Optinall Tensor La 8.1
60 compucations
200
compubatorn
Figure 8: Comparison of different cubic and tensor acceleration methods on Logistic Regression for wBa dataset from the starting point 2g = 3e, where e is vector of all ones.
Third-order Nesterov's power-bound function. The lz-regularized third order Nesterov's lower- bound function from Nesterov 202Ib) has the next form
f(r)
- (zz x++1)* x1 + 1111113
(66)
For Figures 1 and 7b we set d = 20, = 10-3, we've tuned L3 = L = 10..
Poisson regression. Poisson regression a type of generalized linear model used for analyzing count data and contingency tables. It assumes that the response variable b, follows Poisson distribution, and the logarithm of its expected value can be expressed as a linear combination of unknown parameters. The Poisson regression function has the next form
f(x) = E
by (a,,
(67)
where ag Rd are data features and by E (0, 1, ,,....,.. ..,...) are countable targets.
We present results for synthetic data: d 21, = 6000. We set I, = L22 = Lıg = 1 and To = e is all ones.
Poisson Regression
Poisson Regression, p-3
Cubic Nowtan, 1a 1.0
105
6 Grodlet Descent. 1
109
Acodierttdd 1y
Cubic NA-A.1-=1.0 4. Dubic 1.0
18-1
10
20
30
10
18:2
Tercor Method, Lym 1.0
Gescient Bescem, 3.0
Accolurated TensorMetied,
1.0
Torsor NATA, L, =10 w 1.0
Oolmal Temor 2 1.0
10'7
1017
5.0
Figure 9: Comparison of different cubic and tensor accelerated methods on Poisson Regression.
The Cubic Regularized Newton (CRN) method and NATA with tuned parameter demonstrate the best performance in Figure (Left) Notably, CRN exhibits rapid superlinear convergence, likely due to the strong convexity properties of the loss function. Interestingly, NATA with the tuned manages to match CRN's 's convergence rate. While Optimal Acceleration is slower than both CRN and NATA, it also achieves global superlinear convergence. In Figure (Right) for p = 3, the Tensor Nata method is the fastest, followed by the Basic Tensor Method, with the Optimal Tensor method ranking third. All three methods exhibit global superlinear convergence. The classical Nesterov
29

---

Published as a conference paper at ICLR 2025
Tensor Acceleration method is the slowest. likely due to its small default v. Notably, the tensor-basee methods outperform their cubic counterparts.
Polsson regression
1-1hbed-- Aa N0090- 19971)
Gradent Descent.
1.0 12
10
14
narations,
Figure 10: Comparison of the methods by the relative value
f(x+11) -(x))
The global superlinear performance these accelerated second-orde order methods in Figure raises the hope of establishing theoretical results global superlinear convergence for accelerated second-order methods.
30


Reviews:
[{"review_id": "57OiMi4wFk", "reviewer": "Reviewer_BoHs", "summary": "The paper focuses on the analysis of high order methods for nearly convex functions (i.e. star-convex or convex) with additional growth properties. The authors leverage a strong star-convexity and a uniform star-convexity assumption to prove the global superlinear convergence of the Cubic Regularized Newton Method and the Basic Tensor Method. In addition, they introduce an adaptive variant of Nesterov Accelerated Tensor Method called NATA (for Nesterov Accelerated Tensor Method with $A_t$-Adaptation) which solves the problem of having too conservative parameters. Theoretical convergence guarantees are given as well as numerical experiments highlighting good performance. The authors also provide OPTAMI, a python library for high order methods.", "questions": "How do the theoretical results proved in the paper compare to the literature? Was this setting already studied?\n\n* Minor comments/typos:\n    - p.3, l.140: $c_3$ is never introduced before.\n    - p.4, l.188,196,201: \"the function $f(x)$\" should be \" the function $f$\"\n    - p.5, l.263: $e$ is both the vector of all ones and $1e-4=10^{-4}$\n    - p.6, l.283: idem\n    - p.6, l.287: the bigger $\\rightarrow$ the larger\n    - p.6, l.288: repetition \"first, the first...\"\n    - p.6, l.293: I think the paragraph is a bit too long especially the explanation on gradient descent.\n    - p.6, l.321: I understand but I think it is not very clear.\n    - p.7, l.331: \" has next constant\" is a bit odd to me\n    - p.7, l.338: \"second Theorem\" $\\rightarrow$ \"second theorem\"\n    - p.7, l.338: the sentence is too long and contains two times \"hence\"\n    - p.18, l.930: \"subsolover\"\n    - p.24, l.1274: \"Optimal\" seems to be a typo.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I think that the contributions of the paper are valuable and the technical content would be sufficient for publishing the paper in ICLR. Moreover, I did not find any major mistake in the proofs. The library seems to be qualitative and the numerical experiments are satisfactory to me.", "weaknesses": "I am not convinced by the structure of the paper and the way it is written. It seems to me that the authors try to answer too many questions for a 10 pages paper. Also, I think that the theoretical claims are not discussed enough. Detailed comments can be found below. The main problem I have with the current version of the paper is that it lacks a clear unified story and it seems  an aggregation of results. In my opinion, this could be improved by modifying the structure of the paper.\n\nThe OPTAMI library is only mentioned but never properly introduced. I think that at least a paragraph should be dedicated to it or else, that it should be removed from the title.\nAbout the structure:\n\n   1) I believe that the introduction is already too technical although it is well explained. It also states too many problems and, due to a lack of structure, it can confuse the reader. This is highlighted by the fact that there are three questions at the end of the introduction. My suggestion is to keep the detailed discussions for later sections and do a way shorter and high-level introduction. Also, I would try to use as few equations as possible.\n\n    2) It is related to the previous comment but I think that the second section \"Basic methods\" could be enriched with some comments from the introduction.\n\n    3) I think that the third section is interesting with intuitive proofs. However, I regret that there is no discussion on the stated theorems: is there any similar result in the literature, was it expected, is it tight?\n\n    4) The fourth section seems to come bit out of nowhere and lacks a proper introduction. As a reader, it can seem odd to come from superlinear convegence rates (which is in the name of the paper) to adaptive techniques and a new method without a paragraph that bridges both sections. As said before, Theorem 4.1 should be commented and I would have expected a comparison with the results ensured by vanilla NATM.\n\n    5) I believe that the fifth section should be merged with the fourth one or defined as a subsection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "md5YA2I2D8", "reviewer": "Reviewer_WM8N", "summary": "This paper first establishes the global superlinear convergence rate for second-order methods in optimizing strongly star-convex functions, and its higher-order extension for optimizing uniformly star-convex functions, then proposes a variant of Nesterov accelerated tensor method which demonstrates superior performance in numerical experiments consistent with the theoretical faster convergence rate, and finally presents a systematical numerical comparison across mainstream second-order methods.", "questions": "1. How do the authors interpret this trade-off between accuracy and rate of convergence? If the requirement on accuracy is relaxed and the conditions are different, how can the superlinear convergence rate be seen as an improvement compared to previous results?\n2. In addition to the first question, Song et. al. 2021 proposed an acceleration framework that matches the lower bound established by Arjevani et al. 2019. Shouldn't that be seen as the optimal rate for this setting of optimizing strongly convex functions with second-order methods?\n\nChaobing Song, Yong Jiang, and Yi Ma. Unified acceleration of high-order algorithms under general holder\ncontinuity. SIAM Journal on Optimization, 31(3):1797–1826, 2021.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The proposed acceleration variant of tensor method achieves better empirical performance than the existing (near)-optimal accelerated second-order methods.\n2. All methods are systematically implemented and released as a library.", "weaknesses": "1. The global linear rate is established by relaxing the required accuracy to exceed the radius of the quadratic convergence region.\n2. Some typos: \n- line 143 \"$\\epsilon \\leq c_3 r$\" --> $\\epsilon > c_3 r$ \n- Eq (20) $t \\rightarrow 0$ --> $t \\rightarrow \\infty$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "WY9nbYS2pD", "reviewer": "Reviewer_Pnwc", "summary": "In this work, the authors studied the convergence rate of high-order methods, e.g., the cubic regularized Newton method and the basic tensor method. The authors proved the global superlinear convergence of both methods for $\\mu$-strongly star-convex functions and $\\mu_q$-uniformly star-convex functions, respectively. In addition, a variant of accelerated high-order method, named NATA, was proposed and compared with other accelerated high-order methods.", "questions": "I have a few other minor comments for the authors to consider:\n\n- Line 143: I think it should be $\\epsilon > c_3 r$?\n\n- Line 295: \"where the sublinear rate outperforms the linear rate\" is a little confusing. Maybe the authors meant the high-order methods have not entered the linear convergence region and the convergence rate is sublinear at the beginning?\n\n- For the CRN method, did the authors prove the superlinear convergence for $\\mu_q$-uniformly star-convex functions? If so, it may be better to state the results in Theorem 3.2. Currently, I cannot find the results for $\\mu_q$-uniformly star-convex functions and the CRN method.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-organized and easy to follow. The results are novel and should be interesting to the audience from machine learning and optimization fields. The problems studied in this work are important and applicable to certain practical problems where the computational time is not a critical constraint. The proof in the main manuscript should be correct, while I do not have time to check the proofs in the appendix due to the time limit.", "weaknesses": "The main problem with the paper is that the first part (superlinear convergence rate of high-order methods) and the second part (NATA algorithm) seem to be independent and can be separated into two papers. I feel that these two parts considered two different topics. The first one is mostly theoretical and is about non-accelerated methods, while the second one is about accelerated methods and their empirical performance. I would suggest the authors split the paper into two and include more details to the content. For example, the intuition behind the design of NATA.\n\nIn addition, I think the current introduction section is too lengthy. Considering the page limit of the conference, the background knowledge can be simplified and moved to the appendix, since it can be easily found in textbooks and literature. \n\nFinally, I think the authors could include more details to the experiments. For example, in Figure 3, I wonder if the Tensor NATA converges faster with a carefully chosen $v_t$? This is not discussed. Also, it would be better if the authors could provide more intuition behind the current design of searching $v_t$ in sub-iterations instead of fixing $v_t$ to be a constant. Since the performance of a fixed $v_t$ is better than that of a adaptive $v_t$, I wonder if this design is unnecessary. Furthermore, I think it will be helpful if the authors could provide the running time comparison. This is because the solving time of the sub-problem in each iteration may be non-negligible and comparable to the computation time of the Hessian matrix. Especially, for the NATA method, the sub-problem needs to be solved several times in each iteration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "LC2f8vGfK1", "reviewer": "Reviewer_TJTR", "summary": "The paper presents two main results: the first shows that the basic high-order methods (the Cubic Regularized Newton Method and Basic Tensor Method) achieve global superlinear convergence for μ-strongly star-convex functions. \nSecond, it proposes a technique for choosing the parameters of an existing method (Nesterov Accelerated Tensor Method), evaluates its convergence speed, and shows its usefulness in numerical experiments. \nFurthermore, the paper introduces an open-source computational library called OPTAMI for high-order methods.", "questions": "1) What are the total computational complexities for the Cubic Regularized Newton Method and Basic Tensor Method if the costs of solving the subproblems in each iteration can be evaluated? How attractive are they compared to the total computational complexities of other algorithms? \n\n2) If the subproblems of the Cubic Regularized Newton Method and Basic Tensor Method are to be solved iteratively, can't we allow them to be solved inexactly and include the errors in total computational costs?\n\n3) About the proposed algorithm, Newterov Accelerated Tensor Method with At-Adaptation (NATA). Can the authors show anything about the iteration complexities for the strongly (star-)convex case? If it is difficult, show us the best iteration complexity for the classical Nesterov accelerated tensor method when the function $f$ is strongly convex, and tell us why it is difficult to derive the complexity for NATA. \n\n4) For the strongly (star-)convex case, how does NATA perform in numerical experiments? More precisely, what would Figure 3(b) look like in the case of strongly convex (21) with positive $\\mu$ (perhaps the horizontal axis might need to be the iteration number)?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "It is great to show that cubic Newton and Basic Tensor methods can achieve superlinear convergence for strongly convex functions.\nThis paper also includes the necessary equations and propositions for following the proof of superlinear convergence in the main text, and explains the proof strategy leading to the most important theorem, Theorem 3.4, in an easy-to-understand manner. \n\n I also think that providing an open-source computational library for high-order methods would be very helpful to subsequent researchers.", "weaknesses": "[Structure of the paper]\nSection 3 and Section 4 are not well connected, and the paper seems to contain two disparate contents; it would be better to divide the paper into two papers, and strengthen the contents of each, for example, in the following ways. The algorithms and classes of functions are different between Sections 3 and 4.\n\nFor example, for the contents of Section 3, if the cost of solving the subproblem in each iteration can be evaluated, what is the total computational complexity? How attractive is it compared to the total computational complexities of other algorithms? Even if the number of iterations (i.e., the worst-case iteration complexity) is reduced, on the other hand, if the computational complexity at each iteration explodes, it will not be attractive as an algorithm, so it would be better to provide the total computational complexity. If the subproblem is to be solved iteratively, can't we allow it to be solved inexactly and include the error in the iteration complexity and total computational cost?\n\nFor example, for the contents of Section 4, if we consider strongly star-convex, how can the theoretical guarantee given in Theorem 4.1 be changed? As future work, the authors wrote this type of question, but what trends do you see, at least in numerical experiments? More precisely, what would Figure 3(b) look like in the case of strongly convex (21) with positive $\\mu$ (perhaps the horizontal axis might need to be the iteration number)?\n\n----------\n\n[Various unclear descriptions]\nThere are unclear descriptions and various minor errors, giving the impression that this paper was written in haste.\n\nFor example, lines 62-74 introduce the existing studies and describe their global convergence rates, but the assumption of the function $f$ is not clearly stated. Before that, there is a definition of star-convex, etc., but I do not think that those existing studies assume star-convex. This is because the Hessian matrix in (7) is not necessarily positive definite when the function is nonconvex. \nThe others are line 80: upperbound --> upper bound, NPE in line 109 should be written as Newton Proximal Extragradient (NPE), in line 123 the methods performs --> the method performs, etc. Line 193 defines the norm $||x||$ using a matrix B, but which kind of matrices are specifically used in your claims? If we always assume $B=I$, why use $B$ to define the norm? I won't point out any more, but I would like the authors to review the paper again and and reduce this type of typo.\n \n----------\n\n[Insufficient reference]\nThe survey of existing studies does not seem to be sufficient. For example, in line 97, the authors write “poor global convergence” for the quasi-Newton method, but I do not think they are aware of the following paper. The paper also shows “Global Non-Asymptotic Superlinear Convergence” as well as this paper.\n\nQiujiang Jin, Ruichen Jiang, Aryan Mokhtari, \"Non-asymptotic Global Convergence Rates of BFGS with Exact Line Search\",\narXiv:2404.01267, 2024.\n\n Although the authors mention the Jiang, Jin, and Mokhtari paper (COLT 2023) in Appendix A, I think the global convergence rates of quasi-Newton methods should be mentioned around lines 97-98, including the above-mentioned papers. Can it no longer be called “poor global convergence”?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)