Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness
Authors: Artem Agafonov
Dmitry Kamzolov
Alexander Gasnikov
Ali Kavis
Kimon Antonakopoulos
Volkan Cevher
Martin Takáč
Venue: ICLR 2024 poster (2024)
Keywords: Second-order methods
convex optimization
stochastic optimization
Cubic Newton Method
high-order methods
tensor methods
lower bounds
Primary area: optimization

Abstract: We present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, typical in machine learning. We establish theoretical lower bounds and prove that our algorithm achieves optimal convergence in both gradient and Hessian inexactness in this key setting. We further introduce a tensor generalization for stochastic higher-order derivatives. When the oracles are non-stochastic, the proposed tensor algorithm matches the global convergence of Nesterov Accelerated Tensor method. Both algorithms allow for approximate solutions of their auxiliary subproblems with verifiable conditions on the accuracy of the solution.

Published as a conference paper at ICLR 2024
ADVANCING THE LOWER BOUNDS: AN ACCELERATED, STOCHASTIC, SECOND-ORDER METHOD WITH OPTIMAL ADAPTATION TO INEXACTNESS
Artem Agafonov 1.2, Dmitry Kamzolov', Alexander Gasnikov 244,5 Ali Kavis 3
Kimon Antonakopoulos 3, Volkan Cevher", Martin Takáč"
I Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE
2 Moscow Institute of Physics and Technology. Dolgoprudny, Russia
3 Laboratory for Information and Inference Systems, IEM STI EPFL., Lausanne, Switzerland
Innopolis University, Kazan, Russia
5 Skoltech, Moscow, Russia
ABSTRACT
We present a new accelerated stochastic second-order method that robust to both gradient and Hessian inexactness, which occurs typically in machine learning. We establish theoretical lower bounds and prove that our algorithm achieves optimal convergence in both gradient and Hessian inexactness in this key setting. We further introduce a tensor generalization for stochastic higher-order derivatives. When the oracles are non-stochastic, the proposed tensor algorithm matches the global convergence of Nesterov Accelerated Tensor method. Both algorithms allow for approximate solutions of their auxiliary subproblems with verifiable conditions on the accuracy of the solution.
INTRODUCTION
In this paper, we consider the following general convex optimization problem: min fæx)
#ER
where fxx is a convex and sufficiently smooth function. We assume that solution x² Rd exists and we denote f : f(x"). We define R ||=ا x= as distance to the solution.
Assumption 1.1. The function f(x) C has L2 La-Lipxchit--omtinnon Hessian for any x, IR [)z - v f())l < Lg|lz - yll-
Since the calculation of an exact gradient is very expensive or impossible in many applications in several domains, including machine learning, statistics, and signal processing. efficient methods that can work with inexact stochastic gradients are of great interest.
Assumption 1.2. For all x E IRd, we assume that stochastic gradients g {) E Rd satisfy E[g(,, <) x] = Vz(x), E [1lg(x, E) {)(²) x] < o².
Extensive research has been conducted on first-order methods, both from a theoretical and practical perspective. For Ts-smooth functions with stochastic gradients characterized by variance of
of. lower bound Ω
a. /
1, has been established by Nemirovski & Yudin (1983). For
T
f(x) = E Frr, {) the stochastic approximation (SA) was developed, starting from the pioneering paper by Robbins Monro (195I). Important improvements of the SA were developed by Polyak
1990); Polyak& & Juditsky (1992): Nemirovski et al. 2009). where longer stepsizes with iterate
averaging and proper step-size modifications were proposed, obtaining the rate O
R + L
The optimal method matching the lower bounds has been developed La (012) with convergence
VT T22 However, the literature on second-order methods is significantly limited for the study of provable, globally convergent stochastic second-order methods for convex minimization. Second-order methods, Although second-order methods have been studied for centuries (Newton) 1687 Raphson 1697 Simpson 1740 Kantorovich 1949) Moré 1977 Griewank 1981), most of the
rate O Et LI

---

Published as a conference paper at ICLR 2024
results are connected with local quadratic convergence. The significant breakthroughs regarding global convergence have been achieved only recently, starting from the paper on Cubic Regularized Newton (CRN) method by Nesterov & Polyak (2006), the first second-order method with global convergence rate O
Laft T
Following this work, Nesterov 2008 proposes an acceleration mechanism on top
of CRN and achieves the convergence rate of O
Laft T
going beyond the (2(/TT) lower bound
for first-order methods. Another cornerstone in the field is the work by Monteiro & Svaiter (2013)
which achieves lower complexity bound ?
L
Agarwal Hazan 2018
Arjevani al. 2019
TM/
up to logarithmic factor, for the first time in the literature. The gap between upper and lower bounds
was closed only in 2022 subsequent works of Kovalev & Gasnikov (2022 Carmon et al.
(022).
One of the main limitations of the second-order methods is high per-iteration cost as they require computation of exact Hessian. Therefore, it is natural to approximations of derivatives instead of their exact values. In (Ghadimi et al. 2017). CRN method with ò2-inexact Hessian information
and its accelerated version were proposed, achieving convergence rate O
7 +
LLR" This
algorithm was later extended by Agafonov et al. (2023) to handle 51-inexact gradients (and high- order derivatives) with a resulting convergence rate of O (6, R
6,8² + 73 7
L2R² A recent paper
by Antonakopoulos et al. ) proposes stochastic cdaptive second-order method based on the
extragradient method without line-search and with the convergence rate O
[glll
+
aaJl" L 7в/ T
VT
when gradients and Hessians are noisy with variances of and ož. In the light of these results, we identify several shortcomings and open questions:
What are the lower bounds for inexact second-order methods? What is the optimal trade-off between inexactness in the gradients and the Hessian?
In this work, we attempt to answer these questions in systematic manner. Detailed descriptions of other relevant studies can be found in Appendix A
Table I:
Comparison of existing results for second-order methods under inexact feedback. T denotes the number of iterations, and Le represents the Lipschitz constant of the Hessian.
Gradient convergence
Hessian convergence
Exact convergencee
Algorithm
Inexactness
Acceleruted Inexact Cubic Newton
Ghadimi et al. 2017
ineinexatt Hessian
exact gradient
X
La
Accelerated Inexact Tensor Method
6y di-inexatt gradient
O R)
Agafonov al. 2023
6g-inexuct Hessian
Extra-Newton
stochastic gradient
Antonakoooulos et
2022
unbiased stochastic Hessian
T
Accelerated Stochastic Second-order method
stnchastic gradient
2
[This Paper]
stochastic Hessian
Lower bound"
stochastic gradient
[This Paper]
stochastic Hessian
Contributions. We summarize our contributions as follows:
'82-inexact Hessian: & - H. - v² V 821
is worth noting that the Accelerated Inexact Tensor Method can also be applied to the case of stochastic derivatives. Specifically, when p = 2, the total number of stochastic gradient computations is on the order of
( 7/3) while the total number of stochastic Hessian computations is the order of O(s -(/-3/3) Agafonov all (203)) In our work, propose an algorithm that achieves the same number of stochastic Hessian computations but significantly improves the number of stochastic gradient computations O(e -2)
8, -i-inxx gradient: ||g,- V [I] < òn
"Sz-inexact Hessian: (H,- - f()) (y - x)|l S 8zlly æll
Unbiased stochasic Hessian: E (z, x) = fxx), E -
' Under assumption of 82-inexact Hessian the convergence is O
2

---

Published as a conference paper at ICLR 2024
1. We propose accelerated second-order algorithm that achieves the convergence rate of R
+ aa et al.) (022) (see Table
O a.R
LaR" for stochastic Hessian with variance ož and O R 5
L 7
vT
T T
7
for 82-inexact Hessian, improving the existing results (Agafonov al. 2023
Antonakopoulos
2. We prove that the above bounds are tight with respect to the variance of the gradient and the Hessian by developing a matching theoretical complexity lower bound (see Table
3. Our algorithm involves solving a cubic subproblem that arises in several globally convergent second-order methods (Nesterov & Polyak, 2006; Nesterov| (2008). To address this, propose criterion based on the accuracy of the subproblem's 's gradient, along with a dynamic strategy for selecting the appropriate level of inexactness. This ensures an efficient solution of the subproblems without sacrificing the fast convergence of the initial method.
4. We extend our method for higher-order minimization with stochastic/inexac oracles. We achieve
the O R
R.R'
1 T++
rate with ò.-inexact i-th derivative.
5. We propose a restarted version of our algorithm for strongly convex minimization, which ex- hibits linear rate. Via mini-batch strategy, demonstrate that the total number of Hessian computations scales linearly with the desired accuracy E.
PROBLEM STATEMENT AND PRELIMINARIES
Taylor approximation and oracle feedback. Our starting point for constructing second-order method is based primarily on the second-order Taylor approximation of the function f(x) (v)
def f(z) + (Vf(=), y z) + 1 (y
V f(z)(v - x)), y E Rd
In particular, since the exact computation of the Hessians can be a quite tiresome task, we attempt to employ more tractable inexact estimators ((x) and Hxx) for the gradient and Hessian. These estimators are going to be the main building blocks for the construction of the "inexact" sedend-order Taylor approximation. Formally, this is given by:
(1) = f (x) + (g(x), y x) + 1 (y x. (x) - x)), y EER.
(3)
Therefore, by combining Assumption with the aforementioned estimators, we readily get the following estimation:
Lemma 2.1 (Agafonov et al. 2023 Lemma 2)). Let Assumption 1.1 hold. Then, for any x. E Rd.
we have
If(w) (x)) S (119(2) vf(=)]
- -+(())))(() (y =)l) l1 x|| La |yy 1
[V/()) - (eil < [b(()) [=())|+++1| (1 v (xx)
(v - =:)l + 4/2 By - =11
Now, having established the main toolkit concerning the approximation of f in the rest of this section, we introduce the blanket assumptions regarding the inexact gradients and Hessians (for a complete overview, we refer to Table [ In particular, we assume that our estimators satisfy the following statistical conditions.
Assumption 2.2 (Unbiased stochastic gradient with bounded variance and stochastic Hessian with stochastic bounded variance). For all x E , gradient g(x, satisfies 22) and stochastic Hessian H (x,E) satisfies
(4) Assumption 2.3 (Unbiased stochastic gradient with bounded variance and inexact Hessian). For all E Rd stochastic gradient (xx {) satisfies 2 For given u, y Rd inexact Hessian Hxx) satisfies [| (x) V f(z) x) < 1 x||.
E [II vz)
< o².
(5)
Assumptions 2.2 and 2.3 differ from Condition in (Agafonov et al. (023) by the unbiasedness of the gradient. An unbiased gradient allows to attain optimal convergence in the corresponding term O(1/VT), while an inexact gradient slows down the convergence to (1) since a constant error can misalign the gradient. Note, that we do not assume the unbiasedness of the Hessian in all assumptions. Finally, note that Assumption 2.3 does not require (5) to be met for all x, y E Rd. Instead, we only consider inexactness along the direction y - x. which may be significantly less than the norm of the difference between Hessian and its approximation (x))
Auxiliary problem. Most second-order methods with global convergence require solving an auxiliary
subproblem at each iteration. However, to the best of our knowledge, existing works that consider
3

---

Published as a conference paper at ICLR 2024
convex second methods under inexact derivatives do not account for inexactness in the solu- tion of the subproblem. To address this gap, we propose incorporating a gradient criteria for the subproblem solution, given by
(6) where war (v) is the objective of subproblem and 2 is tolerance parameter. We highlight that this criterion is verifiable at each step of the algorithm, which facilitates determining when to stop. By setting a constant tolerance parameter т, we get the following relationship between the absolute
min (y) such that [v>x ST.
accuracy required for the initial problem and = O ( to use a very small accuracy in the beginning. Later, we will discuss strategies for choosing the sequence of 72 based on the number of iterations /.
In practice, it may not be necessary
3 THE METHOD
In this section, we present our proposed method, dubbed as Accelerated Stochastic Cubic Regularized Newton's s method. In particular, extending on recent accelerated second-order algorithms (Nesterov 2021b Ghadimi et al.) 2017, Agafonov al.] (023). we propose new variant of the accelerated cubic regularization method with stochastic gradients that achieves optimal convergence in terms corresponding to gradient and Hessian inexactness. Moreover, the proposed scheme allows for the approximate solution of the auxiliary subproblem, enabling a precise determination of the required
level of subproblem accuracy.
We begin the algorithm description by introducing the main step. Given constants ā >> 0 and M 2 L2, we define model of the objective
wi ()) == (x( + -1Il x y/1 + M
6 - - y/l
At each step of the algorithm, we aim to find E argmin w (1)) However, finding the respective minimizer is a separate challenge. Instead of computing the exact minimum, we aim to find a point Rdd with small norm of the gradient.
Definition 3.1. Denote by 8 M,,, (x) a --inexact solution of subproblem, ie. a point s == g M,5r (1) such that
IV S
Next, we employ the technique of estimating sequences to propose the Accelerated Stochastic Cubic Newton method. Such acceleration based on aggregating stochastic linear models given by
[(x, y) fv) + (g(y, E), y)
in function (x)
The method is presented in detail Algorithm
Algorithm 1 Accelerated Stochastic Cubic Newton
1: Input: yo = æ is starting point; constants M 2 2T; non-negative non-decreasing sequences (ōrh22, De (21 (Káhezo, and
A
IT (1 aj):
Ao = 1,
(7)
vo(x)) ==
| zo || xo
(8)
2: for > 0 do
3:
1/ (1 - ax)xz + actt
I1+1 s M M,3..T(ee)
4: Compute
Ve+1 arg min rERt
(x)))(²) == (x() + مدديععد || xall
(9)
3
- | xoll' + 1e (14,))))))))))
+ >
2
Theorem 3.2. Let Assumption 1.1 hold and M 2 2L2
Let Assumption 2.2 hold. After T 1 with parameters
xd+1_
26.02
Ae
Riz
8M ait1
Ar41
d - (1+3) 8, =200 t (t+ (3))),
(10)
we get the following bound
(((er)_((>")) S 2 +
R2
MR 75
(11)
VT
14
4

---

Published as a conference paper at ICLR 2024
Let Assumption
2.3 hold. After T 2 1 with parameters defined in 10 and we get the following bound
02 = 82 Am T
max 6e
-((T))-(<>))
MR T
(12)
This result provides an upper bound for the objective residual after T iterations of Algorithm | The last term in the RHS of (TT) and (12) corresponds to the case of exact Accelerated Cubic Newton method (Nesterov 2008). j. The remaining terms reveal how the convergence rate is affected by the imprecise calculation of each derivative and by inexact solution of subproblem. We provide sufficient conditions for the inexactness in the derivatives to ensure that the method can still obtain an objective residual smaller than Specifically, this result addresses the following question: given that the emrors are controllable and can be made arbitrarily small, how small should each derivative's ' error be to achieve e-solution?
Corollary 3.3. Let assumptions of Theorem 3 3.2
hold and let > O be the desired solution accuracy.
Let the levels of inexactness Assumption
2.2
be:
T == ( M 12
01
O
02 0
(0(E))) M
Let the levels of inexactness in Assumption
2.3
3
be:
==
01
M R
82 0
g M
And let the number of iterations of Algorithm satisfy T 0 problem ① i.e. f(xT) f(x*)((==>>)))))>) S.
MR²
Then Dr an e-solution of
In practice, achieving an excessively accurate solution for the subproblem on the initial iterations is not essential. Instead, dynamic strategy can be employed determine the level of accuracy required for the subproblem. Specifically, we can choose a dynamic precision level according to T po/z, where As a result, the convergence rate term associated with the inexactness of the subproblem becomes 0 (T)) which matches the convergence rate of the Accelerated Cubic Newton method.
4 THEORETICAL COMPLEXITY LOWER BOUND
In this section, we present novel theoretical complexity lower bound for inexact second-order methods with stochastic gradient and inexact (stochastic) Hessian. The proof technique draws inspiration from the works (Devolder al., 2014 Nesterov 2021b 2018). For this section, we assume that the function fxx is convex and has L fi--Lischitzzcontiimu gradient and L--Lischhitz- continuous Hessian.
To begin, we describe the information and structure of stochastic second-order methods. At each point dy the oracle provides us with an unbiased stochastic gradient 9t = g <) and an inexact (stochastic) Hessian H,- H (I², E). The method can compute the minimum of the following models:
hit1 argmin, {Øe ( (h) an (gt. h) + H,h.h h) + by ||A1| + by bh1l)
Now, we formulate the main assumption regarding the method's 's ability to generate new points.
Assumption 4.1. The method generates recursive sequence of test points It that satisfies the following condition
T1+1 x0 Span (hi...., h
Most first-order and second-order methods, including accelerated versions, typically satisfy this assumption. However, we highlight that randomized methods are not covered by this lower bound. Randomized lower bound even for exact high-order methods is still an open problem. More details on randomized lower bounds for first-order methods are presented (Woodworth & Srebro 2017 Nemirovski & Yudin, 1983). Finally, we present the main theoretical complexity lower bound theorem for stochastic second-order methods.
Theorem 4.2. Let some second-orde method M with exactly solved subproblem satisfy Assumption
4.1 and have access only to unbiased stochastic gradient and inexact Hessian satisfying Assumption
2.2 or Assumption 2.3 with 02 = 82 max 5, 1:a, Assume the method M ensures for any
t=I...,7
function f with L -Lipschizz-comiinuuuu gradient and L Ln-Lipschitt--comiimon Hessian the following
convergence rate
min E (f(,)) f(x*)] S 0(1) max 05tT
a R.R.
La
(13)
5

---

Published as a conference paper at ICLR 2024
Then for all T 2 we haven
(i( VT,
E2(T) <
Es(T) S TT/2
(14)
Proof. We prove this Theorem from contradiction. Let assume that there exist the method M that satisfies conditions of the Theorem 4.2 and it is faster in one of the bounds from 14
The case, EI) VT or E2(T) 72. Let us apply this method for the first-order lower bound R S
function. is well-known, that for the first-order methods, the lower bound is
vT
72
(Nemirovski & Yudin 1983). Also, the first-order lower bound function has O-Lipschitz-contnnunn Hessian. It means, that the method M can be applied for the first-order lower-bound function. We fix stochastic Hessian oracle as (ar, With such matrix H (z. f) = 2L,1, the method M has only the first-order information and lies in the class of first-order methods. Hence, we apply the method M the first-order lower bound function and get the rate min 0S1ST
21, 7. It means that Ø2 27. for such inexact Hessian.
[f{()) f(x))] O(1) max {
R 0.12 (i(TT) Ea(T) j. where ET > VT or
(T) > 7². It means that we've got a faster method than a lower bound. It is a contradiction, hence the rates for the method M are bounded as (T) s 3T) I T The second case, (T( > T7/2, It is well-known, that the deterministic second-order lower bound is L TVE
Let us apply the method .M for the second-order lower bound function, where the oracle give us exact gradients and exact Hessians, then = 0, d2 = 0 and the method M is in class of exact second-order methods but converges faster than the lower bound. is a contradiction, hence the rate for the method M is bounded as (T) - TT/2.
5 TENSOR GENERALIZATION
In this section we propose a tensor generalization of Algorithm We start with introducing the standard assumption on the objective f for tensor methods.
Assumption 5.1. Function f is convex, P times differentiable R&, and its p-th derivative is Lipschitz continuous, iee. for all x. y E IRd
V" S Lp]1> -yl.
We denote the i-th directional derivative of function f at along directions 81, , E IR" as V (' [x)([s)...... st]. J.. If all directions are the same we write V ffx((() [z)[s] For a p-th order tensor U, we denote by ||U||| its tensor norm recursively induced (Cartis et al. 2017) by the Euclidean norm on the space of p-th order tensors:
|
max
( spll),
| |=..-=11pp 1=1
where || is the standard Euclidean norm.
We construct tensor methods based on the p-th order Taylor approximation of the function f(x),
which can be written follows:
(v) del f(x) + Ei V'f(z)lu-st) - x)',
y E
Using approximations (z) for the derivatives V f (x) create an inexact p-th order Taylor series expansion of the objective
(x) f + EL H G,
Next, we introduce counterpart of Lemma 2.1 for high-orde order methods.
Lemma 5.2 (Agaaonnvv et al. we have
2023 Lemma 2)). Let Assumption 5.1 hold. Then, for any x, Idd,
1f(v) (v) s
p
Ill -j---
(p+1)) I1y x p+1
Lg
(V - Vou. < "--])) - x| + f lly - IP.
where we use the standard convention 0! = 1.
Following the assumptions for the second-orde method we introduce analogical assumptions for high-order method.
Assumption 5.3 (Unbiased stochastic gradient with bounded variance and stochastic high-order derivatives with bounded variance). For any i R stochastic gradient Gi (I,{) and stochastic

---

Published as a conference paper at ICLR 2024
high-order derivatives (z. E), i 2..... (r, xj = (z)), E (1,) -V/<)) | soi
........ satisfy
(15)
E - o2,
Assumption 5.4 (Unbiased stochastic gradient with bounded variance and inexact high-order deriva- tives). For any E R stochastic gradient G1(2, {) satisfy (15). For given 2, y R inexact high-order derivatives (;) i 2. 2.....P' satisfy
(z) - V f()) y -| S 6, 11 =0|'
To extend Algorithm 1 to tensor methods, we introduce p-th order model of the function:
M. (y) = (v) + 2 || - v/1² + n. | wlI* + - || yl|
where 7/ 00 issp p. Next, we modify Definition 3.J for the high order derivatives case Definition 5.5. Denote by Sp S.M.b.T (x) a point := Sp S (x) such that V (8)]l S T. Now, we are prepared to introduce the method and state the convergence theorem.
Algorithm 2 Accelerated Stochastic Tensor Method
1: Input: yo = zo is starting point; constants M 2 2 Lpi 1 2 4, 3 S p starting inexactness
6o 2 0; nonnegative nondecreasing sequences { [+/ for = 2,..., P 1, and
ag 1+p+I
p+1
A
11 (1 az), Ao =
(16)
vo(x)) = to
||
xoll
j=]
+ 2 स!
p
| - xo ll
2
2: for t 2 do 3:
(1 -ox)) + Orthe,
J++1
Sp Ma, (vz)
4: Compute
91+1 = arg min
DER" {
(1+1(xx) = ve(x)) + Aلليد ||38 - zoll
p R - | zoll' + 21 21 (11,)
Theorem 5.6. Let Assumption
5.1 hold and M 2 3 Tpp
Let Assumption
5.3 hold. After T 2 with parameters
O
8 Ae
R
R1+1 O
(inn))
), Rtt1 =0
[ Ac-1
Act1
(17)
X 0 (g/t01/2))
8, 5.=0 (00 cutztt
get the following bound
E
[[((r)) - f(x S +it
Ei
Rt Mn++1
VT
T
T=+1
Let Assumption
5.4 hold. After T with parameters defined in II0 and 8 - 1, we get the following bound
a =
8,
max
I=.....
[[f(xr) - f(x)) < o
TR
VT
R R
V
+
2
5
MR
Tp+1
STRONGLY CONVEX CASE
Assumption 6.1. Function f is u-strongly convex, times differentiable on Rd, and its p-th derivative Lipschitz continuous, i.e. for all xr E TRd
[[() f"f(l)) < -,p| 1iiz-yll. vll.
To exploit the strong convexity of the objective function and attain linear convergence rate, we introduce restarted version of Restarted Accelerated Stochastic Tensor Method (Algorithm 2 In each iteration of Restarted Accelerated Stochastic Tensor Method (Algorithm 3). we execute Algorithm 2 for predetermined number of iterations as specified in equation (18). The output of
this run is then used as the initial point for the subsequent iteration of Algorithm I which resets the parameters, and this process repeats iteratively.
7

---

Published as a conference paper at ICLR 2024
Algorithm 3 Restarted Accelerated Stochastic Tensor Method
Input: 2o E Rd, strong convexity parameter 1r > 0, M 2 Lp, and Ro > 0 such that || - x²1 S Ro.
For s 1, ...
1. Set No 23-1, 1=1
Ro 2--1 and Rg-1 || x=1l.
2. Run Algorithm
2 for f, iterations, where
6:R
Lp 1
t, = ma1)max 1, p
max =2
(18)
p
3. Set 2, = x²
Theorem 6.2. Let Assumption 6. hold and let parameters of Algorithm (22) be generated by Algorithm and R be such that =| x² S R. Then for any s 2 we have
7 be chosen as in (17 Let
E1|2, x=11 <
Ef(z,)
f(x") S 2-
UR² URR
(19)
Moreover, the total number of iterations to reach desired accuracy c f(2,) - f(xx)) S E in expectation is
(rto))² JE
12 +1) log (1so)-$(a"") (V
Ei=s
(o:R'~2
L (2
Now, let make few observations regarding the results obtained in Theorem 6.2 For simplicity let solution of the subproblem be exact and p = 2. i.e. we do the restarts of the Accelerated Stochastic Cubic Newton, so the total number of iterations is
O
ci
2 21) log f(zo)-((x') + Laft
$
(20)
P
Next, let's consider solving the stochastic optimization problem min F(x) = Eif(a, E)] using zE
the mini-batch Restarted Accelerated Stochastic Cubic Newton method (Algorithm 3 with 2. In this approach, the mini-batched stochastic Hessian is computed Ta E (²f(x, where T1 and r2 represent the batch sizes for gradients and Hessians, respectively.
stochastic gradient is computed as 1 Σi Vf ( Ei) and the
From the convergence estimates in 19 and (20). we can determine the required sample sizes for computing the batched gradients and batched Hessians. Specifically, we have ri Ô 64-77 and
12 = 0 (1.Ta) Consequently, the overall number of stochastic gradient computations is O CHa/3
which is similar to the accelerated SGD method (Ghadimi & Lan 2013). Interestingly, the number of stochastic Hessian computations scales linearly with the desired accuracy E, i.e., O n.773 log !
This result highlights the practical importance of second-order methods. Since the batch size of the Hessian is constant, there is no need to adjust it as the desired solution as accuracy increases. This is particularly useful in distributed optimization problems under the assumption of beta similarity (Zhang
& [.in 2015). In methods with such assumption (Zhang & Lin 2015 Daneshmand et al.) 2021 Agafonov et al. 2023). the server stores a Hessian sample that provides a "good" approximation the exact Hessian of the objective function. Algorithms utilize this approximation instead of exchanging curvature information with the workers. The constant batch size allows for accurately determining the necessary sample size achieve fast convergence any desired accuracy.
7 EXPERIMENTS
In this section, we present numerical experiments conducted demonstrate the efficiency of our proposed methods. We consider logistic regression problems of the form:
fzx = E [log(1 + exp(- 0g x))]
where (ag,bg the training samples described by features ag E IRd and class labels b, E 1-,, 1).
Setup. We present results on the a9a dataset (d = 123) from LibSVM by Chang & Lin 201 I). We demonstrate the performance of Accelerated Stochastic Cubic Newton in three regimes: de-
terministic oracles (Figure []. stochastic oracles with the same batch size for gradient and Hes-
sians (Figures 2a 2b), and stochastic oracles with smaller batch size for Hessians (Figures 2c 2d
8

---

Published as a conference paper at ICLR 2024
The final mode is especially intriguing because the convergence component of Algorithm sociated with gradient noise decreases as 1/v2 Vt, while the component related to Hessian noise decreases as 1/t². This enables the use of smaller Hessian batch sizes (see Corollary 3.3
For stochastic experiments, we randomly split the dataset into train- ing (30000 data samples) and test (2561 data samples) sets. The methods randomly sample data from the training set and do not have access to the test data. In this case, the training loss repre- sents finite sum minimization properties, and the test loss represents expectation minimization. We compare the performance of the SGD, Extra-Newton (EN), and Accelerated Stochastic Cubic New- ton (ASCN), We present experiments for fine-tuned hyperparameters in Figures 1 2 For SGD, we've fine-tuned parameter Ir. For EN, we we've ve fune-tuned 2 parameters: and Bo. For ASCN, we' ve fine- tuned 2 parameters: M and 21 (only for stochastic case) as the entity, also r = 0 and Ø2 = 0 as they are dominated by . To demonstrate the globalization properties of the methods, we consider the starting point Zo far from the solution, specifically Io = 3 where is the all-one vector. All methods are implemented as Py Torch 2.0 optimizers. Additional details and experiments are provided in the Appendix C
SG0
10% 10-
Iteraaiio
Figure 1: on a with deterministic or- acles
Logistic regression
Irain
train loss
test loss
AGCM
ASCY
ASC4
900
560
5G0
SCD
teratin
(a) Train loss.
Gradient (b) Test loss. Gradient (c) Train loss. Gradient (d) Test loss. Gradient
and Hessian batch sizes and Hessian batch sizes are batch size 10000, Hes- batch size is 10000, Hes- 1500
1500
sian batch size is 150 sian batch size is 150
Figure 2: Logistic regression on 9a with stochastic oracles
The ASCN method proposed in this study consistently outperforms Extra-Newton and SGD across all experimental scenarios. In deterministic settings, ASCN exhibits a slight superiority over Extra-Newton. In stochastic experiments, we observe notable improvement as well. However, it's worth noting that in stochastic regime as we approach convergence, all methods tend to converge to the same point. This convergence pattern is primarily influenced by the stochastic gradient noise #t term, which dominates in rates as we converge to solution. Furthermore, experiment with different batch sizes for gradients and Hessians support the theory, confirming that the Hessian inexactness term in ASCN ez 7 has faster rate than the corresponding term in Extra-Newton ox 75/2. To conclude, the experiments show that second-order information could significantly accelerate the convergence. Moreover, the methods need significantly less stochastic Hessians than stochastic gradients.
Results.
VT
CONCLUSION
In summary, our contribution includes a novel stochastic accelerated second-order algorithm for convex and strongly convex optimization. We establish a lower bound for stochastic second-order optimization and prove our algorithm's 's achievement of optimal convergence in both gradient and Hessian inexactness. Additionally, we introduce a tensor generalization of second-order methods for stochastic high-order derivatives. Nevertheless, it's essential to acknowledge certain limitations. Like other globally convergent second-order methods, our algorithm involves a subproblem that necessitates an additional subroutine find its solution. To mitigate this challenge, we offer theoretical insights into the required accuracy of the subproblem's 's solution. Future research could involve enhancing the adaptiveness of the algorithm. Additionally, there is potential for constructing optimal stochastic second-order and tensor methods by incorporating stochastic elements into existing exact methods. These efforts could further improve both practical and theoretical aspects of stochastic second-orde and high-order optimization.
9

---

Published as a conference paper at ICLR 2024
Acknowledgments. This work supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier (0000D730022P550000) and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00138. This work was supported by Hasler Foundation Program: Hasler Responsible Al (project number 21043). This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 200021_20501 1. Research was sponsored by the Army Research Office and was accomplished under Grant Number 1-11INF-4-1-0000
Ethics Statement. The authors acknowledge that they have read and adhere the ICLR Code of Ethics.
Reproducibility Statement. The experimental details are provided in Section 7 and Appendix C The Py PyTorch code for the methods is available on https:///itth// com/ OP TAMI /OPP/OPAAA OPTAMI
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 (CDC), pp. 2407-2413, 2021. ISBN 2576-2370. doi: 00.1109CDDC444442221..66633 btttps://do..oqg/ http:////.oo.or.........o///////
URL
2021. 9583406840
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky, Alexander Gasnikov, and Martin Takáč. Inexact tensor methods and their application stochastic convex optimization. Optimization Methods and Software, 0(0): 2023, doi: 10. 2023. 2266604
URL https
//doi. 10. 1110010005000
Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.). Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 774-792. PMLR, 06-09 Jul 2018. URL tattps:: httptt::::/pcceeee http:///ooeediiccccooooo ngs www.pppees/ee
V www.///////aaaaaa agarwa 11allBaa.. Ba.hmll
Kimon Antonakopoulos, Ali Kavis, and Volkan Cevher: Extra-newton: A first ap- proach to noise-adaptive accelerated second-order methods. In Koyejo, S Mo- hamed, A Agarwal, D Belgrave, K Cho. and A Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp- 29872. Curran Associates, Inc., 2022. URL https:: neu neur www..rrsp..oooo cc/ wwleffflesspppp pttppppperrpiieeeepppp/////22 [1220000442222000003331111111110
Yossi Arjevani. Ohad Shamir, and Ron Shiff. Oracle complexity of second-orde methods for smooth сonvex optimization. Mathematical Programming, 178:327-360, 2019, ISSN 1436-4646. doi: 10. 1007/s10107-018- 1293-1. 1. URL
Michel Baes. Estimate sequence methods: extensions and approximations. Institute for Operations Research, ETH, Zürich, Switzerland, 2(1). 2009.
Stefania Bellavia and Gianmarco Gurioli. Stochastic analysis of an adaptive cubic regularization method under inexact gradient evaluations and dynamic Hessian accuracy. Optimization, 71(1): 227-261, 2022.
Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, and Ph L Toint. Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives. Journal of Complexity, 181501,, 2022.
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near-optimal method for highly smooth convex optimization. In Conference on Learning Theory, pp. 492-507. PMIR, 2019.
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter acceleration. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: net met//ooummiddnss r7ddbbD
10

---

Published as a conference paper at ICLR 2024
Coralia Cartis and Katya Scheinberg. Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Mathematical Programming. 169:337-375, 2018.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization, part i: motivation, convergence and numerical results. Mathematical Programming, 127(2)245-295,, 201
Coralia Cartis, Nicholas IM Gould, and Philippe Toint. Adaptive cubic regularisation methods for unconstrained optimization. part ii: worst-case function-and derivative-evaluatio complexity. Mathematical programming, 130(2):295-313 20
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Improved second-order evaluation complex- ity for unconstrained nonlinear optimization using high-order regularized models. arXiv preprint arXiv: 1708. 04044, 2017.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
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-2409, PMLR, 2021.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth con- Vex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014. ISSN 1436-4646. doi: 10.1007/110007-013-6677-5 URL /tttp:://do..orgg/
910107-013-0677-
Nikita Doikov and Yurii Nesterov. Gradient regularization of Newton method with Bregman distances. Mathematical Programming, 2023. ISSN 1436-4646. doi: 10. 10007//011070003-09944--- URL
https: http://o...rgg.... www.ooggg//... http:/0001107/11111111001
Nikita Doikov and Yurii E Nesterov. Inexact tensor methods with dynamic accuracies. In ICML, pp-
2577-2586, 2020.
Nikita Doikov, El Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy Hessians. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 8138 8161. PMLR, 9 2023. URL httpps::/ppcccce..ngg... ml press/ v202/doikov2 httm
Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularized newton method. SIAM Journal Optimization, 34:27-56, 2024. doi: 10.1137/22M1519944 URL
Pavel Dyurechensky, 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 Journal on Computational Optimization, 10: 100045, 2022. ISSN 4492-4406. doi:
100045. |R https / //www. www.:scceecee..commm rect. com/ http://cc.c.............ooaaaa/.
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Se- likhanovych, and César A Uribe. Optimal tensor methods in smooth convex and uniformly convexoptimization. In Conference on Learning Theory, pp. 1374-1391. PMLR, 2019a.
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 Secrny- Conference on Learning Theory, volume 99, pp. 1392-1393. PMLR, R, 5 2019b. URL https:
httph/ppss//rroceeeinnnee http://pcccceegg..ee///. mllr. www.ssrsspppee wtt wttp/////////...///. 9b html
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: shrinking procedures and optimal algorithms. SIAM Journal
Optimization, (((4):2061-2088) 2013.
11

---

Published as a conference paper at ICLR 2024
Saeed Ghadimi, Han Liu, and Tong Zhang. Second-order methods with cubic regularization under inexact information. arXiv preprint arXiv:1710.05782, 2017.
Hiva Ghanbari and Katya Scheinberg. Proximal Quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates. Computational Optimization and Applicationns, 69:597-621 2018. ISSN 1573-2894, doi: 10.1007//10889.007799644. URL
htttp:://do..orge
Geovani Nunes Grapiglia and Yu Nesterov. Tensor methods for minimizing convex functions with hölder continuous higher-order derivatives. SIAM Journal on Optimization, 30(4):2750-2799, 2020.
G.N. Grapiglia and Yu. Nesterov. On inexact solution of auxiliary problems in tensor methods for convex optimization. Optimization Methods and Software, 36(1):145-170, 2021. doi: 100800005566888220000777777 1731749
httpss:::///oo /ttp////s////aaa..rr//....////0.
Andreas Griewank. The modification of Newton's 's method for unconstrained optimization by bounding cubic terms. Technical report, Technical report NA/12, 1981.
Slavomír Hanzely. Dmitry Kamzolov, Dmitry Pasechnyuk, Alexander Gasnikov, Peter Richtárik, and Martin Takáč. A damped Newton method achieves global O and local quadratic con- vergence rate. 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 htLphtttp///prreeeddiie a 2022 F http://ll////ooocccaaaaaaee www.cddcaaa48355aaa3c.... 2oce
cc wwwpppppppppp....ppppp..pppepe.. files/paper pddf
K Н Hoffmann and H J Kornstaedt. Higher-order necessary conditions in abstract mathematical programming. Journal of Optimization Theory and Applications, 26:533-566 568, 1978. ISSN
1573-2878. doi: 10. (0.1007/BF009333551 URL htt.ttts:: / orrg/0 1ttp:///111.000///0333333
Bo Jiang, Haoyue Wang. and Shuzhong Zhang. An optimal high-order tensor method for convex optimization. In Conference on Learning Theory, pp. 1799-1801. PMLR, 2019.
Ruichen Jiang and Aryan Mokhtari. Accelerated Quasi-Newton proximal extragradient: Faster rate for smooth convex optimization. arXiv preprint arXiv:2336.002//2 2023.
Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approximation: A qeasin method with global non-asymptotic superlinear convergence. CoRR, abw/2302.08580. 2023. doi: 10. 100445550/22XX..23220088
URL https::/doi..oo 0ttp:///oo...01110.455555/5////.
23C2.08580 08580
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- 58667-7.
Dmitry Kamzolov, Alexander Gasnikov, Pavel Dvurechensky, Artem Agafonov, and Martin Takáč. Ex- ploiting higher-order derivatives in convex optimization methods, arXiv preprint arXiv:2208. 13190, 2022.
Dmitry Kamzolov, Klea Ziu, Artem Agafonov, and Martin Takáč. Accelerated adaptive cubic regularized Quasi-Newton methods. arXiv preprint arXiv:2302.0499 2023.
Leonid Vitalyevich Kantorovich. On Newton's method. Trudy Matematicheskogo Instituta imeni VA Steklova, 28: 10:1044144, 1949. (In Russian).
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex opti- mization. In International Conference on Machine Learning, pp. 1895-1904, PMLR, 2017.
Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high- ordh- meth- ods in smooth convex optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances Neural Information Processing Systems, 2022. URL https:://ppnnest net wwwp:nnnnnooeeoeeeeeeoeoo 00 T.20r01P
12

---

Published as a conference paper at ICLR 2024
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Pro-
gramming, 133:365 397, 2012. ISSN 1436-4646. doi: 10. 10.1007/111107-00004444... URL
atttps://dos /ttp://.........../000000000-000
Aurelien Lucchi and Jonas Kohler. A sub-sampled tensor method for nonconvex optimization. IMA Journal Numerical Analysis, 43:2856-28911 10 2023. ISSN 0272-4979. doi: 10.1093/imanum/
drac057. /Bt.pcctess///....oro///1/111///
Konstantin Mishchenko. Regularized Newton method with global ((1/k²) convergence. SIAM
Journal on Optimization, 33(3): 1400)41440-146,, 2023. doi: 10.1137/22M14888 URL https
77doi .rr. 10. 1.. 1
Renato D C Monteiro and B F Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications second-order methods. SIAM Journal Optimiza-
tion, 10:2--111 2013. doi: 10.1 10.1137/118333786
URL https: htttttt////ol// http::/://aoi..or/0000011111
110833786
Jorge J. Moré. The levenberg-marquard algorithm: implementation and theory. In Conference on Numerical Analysis, University of Dundee, Scotland, 7 1977. URL https: /tt:://wwww /www.w.... osti
gov/bablio/72556
A Nemirovski, A Juditsky, G Lan, and A Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19:1574-1600 2009. doi: 10.1137/ 070704277.
Arkadi Semenovich Nemirovski and David Borisovich Yudin. Problem Complexity and Method Efficiency Optimization. A Wiley- Iitey-Interscience publication. Wiley, 1983.
Yurii Nesterov. Accelerating the cubic regularization of Newton's method on convex problems. Math- ematical Programming, 1 12:159 181, 2008. ISSN 1436 4646. doi: 10.1007/510107-006-00883 URL
008900
Yurii Nesterov, Lectures on Convex Optimization. Springer Cham, edition, 2018. ISBN 978-3-319-
91577-7. doi: 10. 10.1007/978-33319-915573
Yurii Nesterov. Inexact high- proximal-poin methods with auxiliary search procedure. SIAM Journal Optimization, 31:2807-2828, 2021a. doi: 10.1137/20M134706XX URL (tLhtt
0//b0..org/10..113770000.
Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical
Programming, 186:157-183, 2021b. ISSN 1436-4646. doi: 10. 101100777100007-01990414491111 URL
01449-11114111
Yurii Nesterov. Superfast second-order methods for unconstrained convex optimization. Journal of Optimization Theory and Applications,, 191: 2021c. ISSN 1573-2878. doi: 10.1007/
Yurii Nesterov and Boris T Polyak. Cubic regularrtto of Newton method and its global performance.
Mathematical Programming, 108: 108: 177-205,, 2006. doi: 10.100774110007-000-077000 URL https
/
Isaac Newton. Philosophiae naturalis principia mathematica. Edmond Halley, 1687.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging.
SIAM Journal on Control and Optimization, 30:838-855, 1992. doi: 10.1137/033004.. URL
https: /ttp:::////o..oor000111.17. wwt.///.....3/33000000.
Boris Teodorovich Polyak. A new method of stochastic approximation type. Avtomatika i Tele-
mekhanika, 51798-107, 1990.
Roman Polyak. Complexity of the regularized Newton method. arXiv preprint arXiv:1706.08483 2017.
13

---

Published as a conference paper at ICLR 2024
Roman A Polyak. Regularized Newton method for unconstrained convex optimization. Mathematical
Programmingg 120: 120:125-14:3 2009. ISSN 1436-4646. doi: 10.10077/-01007007--011333 URL
Joseph Raphson. Analysis Aequationum Universalis Seu Ad Aequationes Algebraicas Resolvendas Methodus Generalis & Expedita, Ex Nova Infinitarum Serierum Methodo, Deducta Ac Demonstrata. Th. Braddyll, 1697.
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, 22:400-407, 1951. ISSN 0003-4851, URL http: // wwtp://wwwww// jitorrsstrr....o org/ stable/ 2236626
Katya Scheinberg and Xiaocheng Tang. Practical inexact proximal Quasi-Newton method with global
complexity analysis. Mathematical Programming, 160:495-5220 2016. ISSN 1436-4646. doi: 10.
1007/s00107-066-0997-3. URL httpts:s/sppiooooooooooo ottp:///o......11111/01110000000
007 016 0097-3
Damien Scicur. Adaptive Quasi-Newton and anderson acceleration framework with explicit global (accelerated) convergence rates. arXiv preprint arXiv:2305. /9179, 2023.
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.
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael I Jordan. Stochas- tic cubic regularization for fast nonconvex optimization. In S. Bengio, H. Wal- lach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31, pp. 2899-2908. Curran Asso-
ciates, Inc., 2018. URL /ttpss//prooeeeeeee.... neurips wwteriis.cccppppeeeeee cc/paaper/233/EEel dbl (a031100222011711336386666663333
pdf
Blake Woodworth and Nathan Srebro. Lower bound for randomized first order convex optimization.
arXiv preprint 1rXiv:1709.00 0035949 2017.
Peng Xu, Fred Roosta, and Michael W Mahoney. Newton-type methods for non-convex opti- mization under inexact Hessian information. Mathematical Programming, 184:35-70, 2020. ISSN 1436-4646. doi: 1010007/110007-009944444444 URL 110107-01900105-2
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-370, Lille, France, 07
09 Jul 2015. PMLR. itL http://:/pcccceeecnss.//m mlr wwwppppsssss......... vv7 pttss//33//haappl//// zhangb15 html
14

---

Published as a conference paper at ICLR 2024
A RELATED WORK
The idea of using high-order derivatives in optimization has been known for a long time Hoffmann & Kornstaedt (1978). In 2009, M. Baes extended the cubic regularization approach with recond-orde derivatives (p = 2) from Nesterov & Polyak] (2006) to high-order derivatives (p 2) in Baes (2009). However, the subproblem of these methods was non-convex, making them impractical. In 2018, Yu. Nesterov proposed the implementable (Accelerated) Tensor Method Nesterov (2021b), wherein the convexity of the subproblem was reached by increasing a regularization parameter. Hence, the convex subproblem could be efficiently solved by appropriate subsolvers, making the algorithm practically applicable. In the same work, a lower complexity bound for tensor methods under higher- order smoothness assumption was proposed. Shortly after, near-optimal Gasnikov et al. (2019b a); Bubeck et al. (2019); Jiang et al. (2019) and optimal Kovalev & Gasnikov (2022); [armmnn et al. (2022) high-order methods were introduced. Furthermore, under higher smoothness assumptions, second-onler methods Nesterov (2021c a): |Kamzolo] (2020); Doikov et al. (2024) can surpass the corresponding lower complexity bound for functions with Lipschitz-continune
Hessians. For more comprehensive information high-order methods, one refer to the review Kamzolov al. (2022).
In general, second and higher-order methods are known for their faster convergence compared to first-order methods. However, their computational cost per iteration is significantly higher due to the computation of high-orde -oder derivatives. To alleviate this computational burden, it is common to employ approximations of derivatives instead of exact values. While there a wide range of second-order and tensor methods available for the non-convex case, assuming stochastic or inexact derivatives Cartis et al. (201 la b); Cartis & Scheinberg (2018); Kohler & Lucchi (2017);
7 Xu et al.
(2020); Tripuraneni et al. (2018) 8); Lucchi & Kohler (2023); Bellavia & Gurioli 2022); Bellavia
ct al. [2022]; Doikov et al. (2023), the same cannot be said for the convex case. In the context of convex problems, there have been studies
high-order methods such as second-order methods with inexact Hessian information Ghadimi et al. (2117) tensor methods with inexact and stochastic derivatives Agafonov al. (2023), and Extra-Newton algorithm with stochastic gradients and Hessians Antonakopoulos et al. (2022). As a possible application of methods with inexact Hessians, methods. Such methods approximate second-order derivatives using the history of gradient feedback. Quasi-Newton methods are known for their impressive practical performance and local superlinear convergence. However, for the long period of time, the main drawback of such methods was a slow theoretical global convergence, slower than gradient descent. First steps to improve the global convergence of such methods were done in (Scheinberg TTang 2016 Ghanbari & Scheinberg 2018) but the methods could be still slower than gradient descent. The first global Quasi-Newton methods that provably matches the gradient descent were reached by cubic regularization in two consecutive papers Kamzolov et al. (2023): Jiang al. (2023). It also opened possibility for accelerated QN Kamzolov et al. (2023) that theoretically matches fast gradient method and first-order hoonds. This direction were further explored for different methods in Scieur
we highlight Quasi-Newton((M)
(2023): y: Jiang & Mokhtari 2023). Another possible application for high-order methods with inexact or stochastic derivatives is distributed optimization Zhang & Lin (2015) Daneshmand et al. (021))
Agafonov et al. (2021); Dvurechensky et al. (2022).
One of the main challenges of tensor and regularized second-order methods is solving the auxiliary subproblem to compute the iterate update. In both second-order and higher-order cases, usually requires running subsolver algorithm. The impact of the accuracy, up to which we solve the auxiliary problem, on the convergence of the algorithm has been studied in several works Grapigla & Nesterov (2021 2020); Doikov & Nesterov (2020). One actively developing direction relies on the constructions of CRN with explicit step Polyak] (2009) Mishchenko (2023); Doikov &
Nesterov );023); Doikov al. (2024); : Hanzely al. (2022)
B ON THE INTUITION BEHIND THE ALGORITHM
Model. For the second-order case the model wh wa, (1) comprises three key components: an inexact Taylor approximation oz (y): cubic regularization M I| - e and additional quadratic regularization ن || 2 The combination of Taylor polynomial and cubic regularization is the standard model for exact second-order methods, as they create a model that is both convex and upper bounds the objective (Nesterov 2008) (see (Nesterov) 2021b) for high-order optimization). However, inserting
6
15

---

Published as a conference paper at ICLR 2024
inexactness to the Taylor approximation leads the necessity of additional regularization (Agafonov ct al. 2023).
The first reason to add quadratic regularization is to ensure that the Hessian of the function is majorized by the Hessian of the model:
0 = V2 f(v) 3 V. + 521 L2 =|| = (v) + 52 + M z|| = V Moreover, this regularization is essential for handling stochastic gradients correctly. Note, that we add quadratic regularizer with the constant 6, 2d2 + 7 (t 1)8/2. Here, 82 accounts for a Hessian majorization, while nt (t + 1)3/2 is crucial for achieving optimal convergence in gradient inexactness. From our perspective, this regularization can be viewed as damping for the size of stochastic Cubic Newton step, as stochastic gradients may lead to undesirable directions.
For further clarification, please refer Lemma the step. Take a look at the right-hand side of equation (29). Without proper quadratic regularization, won't capture the correct term related to Hessian inexactness 82. Consequently, the desired
This lemma serves bound the progress of
convergence term, T cannot be achieved. Moving on to the left-hand side of (29). we encounter the term ( V fx))). Here, choosing the appropriate is crucial to compensate for stochastic gradient errors and achieve optimal convergence in the gradient inexactness term.
6,
Estimating sequences. Estimating sequences are a standard optimization technique to achieve acceleration (Nesterov) 2018) (Section 2.2.1]. As far as knowledge extends, the application of estimating sequences to second-order methods was first introduced in (Nesterov) (0088.. The concept involves adapting acceleration techniques traditionally applied first-order methods to the realm of second-order methods. In this work, we make slight modifications to the estimating sequences derived from (Nestervv 2008) to preserve the customary relationships inherent in accelerated methods:
f(z1)
f(x") + 02 l2l zoll2 + callæ* xool + erTup:
erriow S 1/
A,-1
A-1
where A, and 022 are scaling factors, common for acceleration (Nesterov 2018 2008).
For simplicity, let erriow = 0, erTup 0, c2 0. That is the case for exact derivatives and subproblem solutions. Then, one can get the convergence, with a specific choice of scaling factors:
f(x) f(x") ) < A1-10y/|=* =uul"
In our case, errors and C2 are non zero and stay for gradient, Hessian and subproblem inexactness. By
applying estimating sequence technique get rates
(12).
The choice of parameters. The cubic regularization parameter M 2 2L represents the standard choice for second-order methods (Nesterov & Polyak 2006). The quadratic regularization parameter 8, 20g + - (t 1)3/2 consists of 202 for compensating Hessian errors, and ( (1 1)3/2 for compensating stochastic gradient and subproblem solution errors. The regularization parameters R5 Kgg Ar utilized for the second step of the method. The R's are chosen in 44)). (42) to uphold the
inequality (34) for acceleration. A &/ (t 1)5/2 serves to compensate for stochastic gradient errors in the estimation functions vh. The specific choice for ō and X is made the proof of Theorem E.7 to achieve optimal convergence rate.
C ADDITIONAL EXPERIMENTS
After tuning we got the following hyperparameters. For deterministic oracles: Ir = 20 for GD, y 5 and (8 0.5 for Extra-Newton, . 0.01 for ASCN. For stochastic oracles:
20 for SGD, 7 5 and Bo = 0.05 for Extra-Newton, M = 0.01 and 1 7 for ASCN. For stochastic oracles with different batch sizes: Ir 20 for SGD, 7 = and 3g = 1.0 for Extra-Newton, M = 0.01 and 1e 7 for ASCN.
On Figures 4 we present additional experiments with different batch sizes for gradients and Hessians, and Figures 5 6 we present Figure with increased size. Moving forward to Figures [ a comparison in running time illustrated for two distinct setups: the gradient batch size is set at 10000, and Hessian batch sizes configured to be 150 and 450. Specifically, one iteration of SGD consumes 16 seconds, while the execution times for EN and ASCN are approximately 0.33 seconds for both scenarios.
16

---

Published as a conference paper at ICLR 2024
Extra-Newton
Extra-Nevion
Acteterated Stachastic Cubic Newtor
Accelerated Stochastic Cubic Newton
10'
107
N90 (68))
20m2
10-2
1012
10
20
30
40
50
60
70
80
20
30
40
50
iteration
iteration
(a) Train loss
(b) Test loss
Figure 3: Logistic regression on a aa. Gradient batch size is 10000, Hessian batch size is 450
tra loss
test loss
107
101
Accelerated Stochastic Cubic Neator
Accelerated Stochastic Cubic Newton
SGU
5GU
(x0) -xx*
2011
10-2
(50)
10'7
10"1
10
20
30
40
50
60
70
30
40
50
Rteration
(a) Train loss
(b) Test loss
Figure 4: Logistic regression on aa. Gradient batch size 10000, Hessian batch size is 900
D PROOF OF LEMMAS 2. AND 5.2
Lemma 5.2. Let Assumption 5.1 hold. Then, for any æ. IR4, we have
( 2x.p <
- xIl +
Ln
I1 xr r1|
(p+iy
[V) Von.p
(-))))))(()))))) - x]]=
La pf
lyy x IP..
The proof of that lemma is the same as proofs of Lemmas 2 from Agaaonov et al. (2023). Lemmal 2.1 is a special case of the Lemma 5.2 for 2.
E PROOF OF THEOREM
The full proof organized as follows:
Lemma
E.1
provides an upper bound for the estimating sequence (z);;
Lemmas
E.2
E.6
present the efficiency of Inexact Cubic Newton step # SM.6. (v:).
Lemma
E.6
provides lower bound on (z) based results of technical Lemmas E.5
E.4
Everything is combined together in Theorem H.7 in order to prove convergence and obtain convergence rate.
The following lemma shows that the sequence of functions (x(x) can be upper bounded by the properly regularized objective function.
Lemma E. For convex function f(x) and th (x), we have
vx(x²) < [(x"
+ X ||0"
Rg
roll
+
|
xoll3 + upr
(21)
A,
2
6
17

---

Published as a conference paper at ICLR 2024
101
Extra-Newton
Extra-Nevion Accelerated Stochastic Cubic Newton
Acteterated Stachastic Cubic Newtor
SGD
10'
102
(900 (62))
20
20-2
10-2
1012
10
20
30
40
50
60
70
80
10
20
30
40
50
60
1 Iteration
iteraaion
(a) Train loss
(b) Test loss
Figure 5: Logistic regression on a aa. Gradient and Hessian batch sizes are 1500
test
101
Extre- Newton
Extra- Newton
Accelerated Stachastic Cubic Nowton
Accelerated Stachastic Cubic Newton
SGD
10'
10a
Mad -(2))
30-1
10-2
10-2
10a4
10a2
2 hooattio
Iterrtion
(a) Train loss
(h) Test loss
Figure 6: Logistic regression on a.a. Gradient batch size is 10000, Hessian batch size is 150
where
erri" up = Σ aj j= A,
(g(x)+1)
(f(Iz+1), x² - zz41)
(22)
Proof. Fort 0, let us define A_1 such that 1
0 then [(x") 0 and
A-1
A-1
+
Ao
Ry
vo(x*) 5
2 ||x0
xo 1 +
3 || -mol
From
Ve+1(x) == vx( + dc-1-
||
xol12
+
Σ
R
Ri
||x
xoll* + (2,,0,))1,,
(23)
1=2
we have
vr(x") Rig + 21 || xol1 +
Re
| - vo 1| +
Σ 110" xz41)-
(24)
2
3
From
we have that, for all j 2 1, A; Aj (1 ay), which leads to a; A A3 A, Hence,
we have
I and, using the convexity of the objective f. we get A=j Te-i
1
= Tt-1
1-1
Σ 0 11 x2411)
<
+
a (g(0)41)
Vf -2)+1
(25)
A
Aj
1=0
1=0
1=
$ f(x*)
Σ
(-1
a2j
+
err
up f(x*)
+ erri"
up
(26)
Ag
A
0=
18

---

Published as a conference paper at ICLR 2024
Extra-Newton
Extra-Nevion
Acteterated Stachastic Cubic Newtor
Accelerated Stothastic Cubic Newton
10'
10a
N90 (68))
20m2
10-2
1012
10-3
5
10
15
20
25
30
25
time (s)
C. Litee (s] Test loss
(a) Train loss
(b)
Figure 7: Logistic regression on a aa. Gradient batch size is 10000, Hessian batch size is 150
Extra- Newton
Extra- Newvon
Accolerates reaad Stachastic Cubic
Acceleratod Stachastic Cubic Newton
10'
10a
-1(2))
nac) (62))
2013
10-2
10-2
10
15
20
25
30
time [s)
C. t.time (S] (h) Test loss
(a) Train loss
Figure 8: Logistic regression on a9. Gradient batch size is 10000, Hessian batch size is 450
where ((2,8) f(y) + (V)) y). Finally, combining all the inequalities from above, we obtain
4/ (x(aa)
26
f(**)
R4 + de
||
xoll
Ri |2-
zoll + err
(27)
A
Lemma E.2. For the function f(x) with LngLLipschizz-continuuu Hessian and H (xx) is 82- -i-innxact Hessian for Ut, 1e Bd we have
L2
Vo f((41)) s 8/111441 - v.ll + 2 11 1 +1g((,)) f(()))l. (28)
where we denote 84 = 8 ge. to simplify the notation.
Proof. [VVon (I++1) - v((+++1)]
Vov. (21+1) 4,, (x++1) + 2, (2(41) V (x++1)
< (Z1+1)
D,, (2<+1)] + 1r, (I1+1) - V Vf f(
= 1(V2 ((x)) - Br,)(1 - -z)il + $r, (I++1) v
(1o(v:) vs(v:))l
L2
<6b1 - vell
|| 0.1 (lg(v.)) vf(x)))
2
The next Lemma characterizes the progress of the inexact cubic step SM, (vx) in Algorithm
19

---

Published as a conference paper at ICLR 2024
Lemma E.3. Les {2i, ve be generated by Algorithm 7 Then, for any 85 482, M 2 4Lg and
Tt-1 = S,, (1t), the following holds
7² 2
+
Ilo((e)) +
(V Ix-1)
6e
5,
(29)
min [IV]((=+))I| (1h). [V (aM)
Proof. For simplicity, denote r++1 | Uz and
M
S+1 8c + By Definition 3.1 for T++1 S.M.i..T
| - rrll
(30)
2
Vov, (Ic+1) + (x 0z) + M
2 x141 - ub)l
(31)
V &v (I++1) + (x - -z)]1-
We start with getting an upper bound for Vov, (I1+1) - vf(z++1)]l La rit (19(1)) vf(wi)l-
VV, (#++1)
(((++)) 83441 +
(32)
From inexact solution of the subproblem get
| [[V + S4+1 (F++1 - 1))1
< V (16+1) - (f(=++1) - V0, - - u1]1
-
(33)
< dr, (#++1)
V [ 2 (x)+11 S0+1 r))l
Def
Ve, (#1+1) - (((+++1) 1( +
Next, from the previous inequality and 32.p we get
41lg(e)) vf(())) 4 + rz 2 1+1 2o - vf(+++1)]
[vf((t+1) + + -1)1 -27
| Vf(2+11]|| + G2t1l1re+1 2
Hence,
72
2
1
G+1 Ge+1 [lo[(v)) ((()))1 (V/()1)) x141) 2
[[((+)))
(Gi+1 4(62 + 12 12) ret1
2(++1
2G++1
and finally by using defenetion of Ç++1, we get
2 2 (bo(v)) - V[(m))]1 + (V/(s))) - -x+1) 2
+ o,
[V/((++)]||
(Git1 4(85 + La 12 r
8,
2G+11
2G++1
Next, we consider 2 cases depending on which term dominates in the C411-
If 2 M 72 2
2 || we/l, then we get the following bound
(lo(vr)
2(()))1 + (Vi(z++)) .). Ie+1)
(5et1 4(85 + (2(r11))) r
8, 6
26++1
2G++1
If
<
M
2
|,+11
vell. then similarly to previous case, we get
2²
2
+ (Vf(x++1), -f(c))
z+41)
5,
be
V
f((+11)1 + ((,, + = 4 (8) + 1 ?)
r241
26(+1
25.41
[+(
r2
((3: 25,
M M--2aarz4) (5, - 20 2لط re+1))
20++1
2
26,41
20

---

Published as a conference paper at ICLR 2024
2 [+
M
412 ri+1
|V [++(1++))]
2M
2 2Mr
+
rit1 2
[V
2Mr++1
4
2M
32
3M
where for the last inequality, we use
a + 3
3r
2 /31/4
We use the following lemma (Agafonov et al. 2023 Lemma 7).
Lemma E.4. Let h(x) be a convex functiin. 20 E R", 0, 2 for ......PP +1111 and p+1
I arg min (m(x)= h(x) + O,di( - -xo)): wER"
where d((x)= = |||=]| ' a power-proxs function. Then, for all IR"
p+1 i-2 0, T).
M(x) 2 h(T)
+
We will also use the next technical lemma Nesterov (2008): conjugate for the p-th power of the norm.
Ghadimi et al. (2017) on Fenchel
Lemma E.5. Let g(2) p I||=| for p 2 2 and be its conjugate function i.e. g²(v) sup=((e,2) (), -)- g(z)}. Then, we have
g (v) p p-1 1
|0|| p-1
p 0
Moreover. for any 0, R", we have g(2) g" (v)
(2, 2) 2 0.
Finally, the last step is the next Lemma which prove that f(m) I min (e(()) v.. 1r-1
Lemma E.6. Let {Ii, Vt Jeg be generated by Algorithm
7 Then
f(z))
v min vx(xx) >
A err? eert-eere -err
(34)
where
t-1 2
err Σ
(1g(b,) - Vf(x))1
(35)
A5
1-1 72
err! = Σ
(36)
j=0 Azōj
and
1-1
af
[-1
err?
Σ 1=0
-
(1(()511)
Vf(a++1)11
aj (g(و,-1) V[(1)))) -
((()))))--a=)-))))) xz-1) (37)
2452
Ag
1=
Proof. We prove Lemma by induction. Let us start with t = 0, we define A_ such that _Σ, = 0.
Then [(ao) 0 and V/ 0, hence, v/ > f(ao), Let us assume that 34 is true for L and show that 34) true for + 1. By definition,
A_1
v \ Rd
200l 2 +
R3
æol
(1 2z41).
2
3
1-1
Next, we apply Lemma E.4 with the following choice of parameters: M(x) = Σ
(I,
d,
3=0
0g d + Rb, and 0g R3-
21

---

Published as a conference paper at ICLR 2024
By 23
Yt argmin h(x), and we have
=ERd
R22
R2
de (1(+1)
2 2//
+
|| - yell2
+
|1 yell
2
6
f(x)) A,1 2
22 + X || y211
R3 || 1/113 errü err -err?
6
where the last inequality follows from the assumption of the lemma.
By the definition of ())+ the above inequality, and convexity of f. we obtain
A++1 A
R2 R2
11+1 (B6+1) = 1 +
11 xoll² + 2
1 zoll
2
R
at
yt+1 zoll3 +
(1(+11
3
At
f(x))
R2 + A1
||
yol1
R2
|lt+1
1s
at
[J1++1, erri -rr -
Ar-1
2
A:
f(x))
R3 +
A
+
|1 3e11 112
+
1/+1 1r11 1| -erri -erri -
A
6
01 (f(x++1) + (V (Vf(xt+1) 11+1 xz+1) - (g(((+1) v f((++1)) 3e+1 1.1++11)661111 vi) + (g((x++1) - V V.((x+11) - z(+1))
A
f(t)
R2
R3
+
|1 - 3ell? +
|1t+1 - well3 - Erri - -Err -err
A,-1
2
6
+
0n
(f(r441) + ( Bt++ - -x+1))
2A7 [19(I(+1) vf(x++1)
a
an (g(xx+1) - vf(x411) x141)
A,
Ar
[(x)
62
R1 || - -vl133 Err -rri+1--00 -rrr + ai (f(x44) + (V((041)) - -x++1))
+
|1++1 3/1l2
A,-1
2
6
A.
Rt
11 - yell? 11 +
|it1 - yell 11 erri - erri+1-er1
2
6
(f(x++1) (Vf(=++1), x(+1)) + at (f(z441) (Vf(2++1) yt+1 =(+1)).
Ar-1
As
Next, we consider the sum of two linear models from the last inequality:
1
(f(I++1) + (V((#+1)) x(41)) A,
(f(x441) (1
Ar-1
ai
- x++1) + at + (Vf(I(+1). f(1(+1)
at
f(1+11) + ai (V 86+1 - Det1) A,
A₁
A
A,
[(x+11)
1 - at
(Vf(1++1),
(V
- 013
a- x(41) A
(Vf( 0t+1 l2t1)
A
A
f(1+11)
+ Ar
(Vf((=+)), - -
+
at (V ( U1+1 9t))
Ar
A,
As result, by 23
, we get
2 [(x--1)
K2
rit1 vhe+i (8++1)
12 - + (V
- +
|| - yell
A
A
2
(38)
|1++1
vell3
+ an (V
Met1 y6) -err errit1-err?
A
To complete the induction step, we show, that the sum of all terms in the RHS except non-negative (except err).
f( 1ll is
A.
Lemma E.3 provides the lower bound for (V v4- #2+1). Let us consider the case when the minimum in the RHS of (29 is attained at the first term. By Lemma E.3 with the following choice of the parameters
Ot V f(141))
0= =RR],
y/- Vt+l,
A
22

---

Published as a conference paper at ICLR 2024
have
22 v1+1l12+
1
21 V
1/
(V (V) -vb) 2
(39)
2
A.
R2
Hence,
V 0z xx+1) +
|1 3e11 1
at
(Z 36+1 me)
A
2
A.
11 V f
(V((241)) x(+1)
A
2n
1
D1 (f+41)l
2
l1a((e)) - [[()))]] 7²
(I(+))l
Ae
A
46,
2
Aqd:
A,dg
2
72
2
(lg(v)) vf(n))1
A.d;
A
where the last inequality holds by our choice of the parameters
R 25,a,
(40)
A.
Next, we consider the case when the minimum in the RHS 29 is achieved on the second term.
Again, by Lemma E.5 with the same choice of 2, V and with 0
R
have
1 let1
Oi
11 31) 2
2
2
at V
A.
11
(41)
A
3
R3
Hence, we get
Rd well +
at
V [V(()))), 0z xc+1) +
|1
Ue+1 me)
A
6
A,
1
[ 1 -x++1)
2
2 aL
As
V ff
3
3/2
V
1
2
2 0:
A,
(f(
2
(19(v))
V 72
At
3M
4
4
2
72
(1g(v.) (s(2))11
1,5,
A,5,
where the last inequality holds by our choice of RzJ:
8.M 3 A.
R
(42)
As result, unite both cases and get
f(1++1)
Vis
2
+
(V
(2f((1411)))) - +
|| 1/
A.
A,
2
R
+ at
+
Mi+1 - yoll
(V Mo+1 - -y1) -err - -err -
6
A
111411)
2
22 72
[lg(v)))
err err
As
A
A,d,
f(x(-1)
err (+1 err -
A,
To sum up, by our choice of the parameters nt, i = 2,3, we prove the induction step.
Finally, we are in position prove the convergence rate theorem The proof uses the following technical assumption. Let R be such that
||
x11 S R.
(43)
23

---

Published as a conference paper at ICLR 2024
Theorem E.7. Let Assumption 1.1 hold and M 2 4L2. Let Assumption 2.3 hold. After T z 1
with parameters defined in (10) and 02 = 82 = max 6, -0 we get the following bound for the objective residual
t- cl,...
10
19 18
20L2H
([((z))-((x))
VT +
+
VT
(T + 3)2
(T + 113
Proof. First of all, let us bound Ar.
3
04
12 1.
(44)
t 3
Then, have
T az)
T
T13!
6
AT
II
(1
=
t +
(T 33!
(T + ()(T + 2) +3
(45)
t=1
t=1
And from Agalonov al.
(2023
we get
Apa
3
(46)
A
(T' 3)
From Lemmas E.6 and
E.1
we obtain that, for all t 2> 1,
1
err
erT
-err i+1
thtt S (x")
A,
f(x*)
+
A
R ||
|| roll
+
roll + err up
A,
2
Next, we apply expectation
T
Ax
+
R3 6
E [ff(TT+1)
f(x")] ATE
R²
+
R²
ETT + erri+1 + +err++1 + +err741
(47)
Let us choose
T + 0
8, = 82 +
R (1 (1+3)332
(48)
d R (t + 3)5/2.
(49)
Then, bound terms in 47
step by step.
We start from deterministic terms.
AT
K2
+
XT
R²
R3
18 R2
GÅT
72M R2
2
3)
(T 3)3
(T + 3)3
48
18rR R
18
18
6o
72M R3
(T + 3)2 + (T+ + 33))11/2
(T + 3/2
(T + 3)122
(T + 3333
Now, we bound expectation of all error terms. Firstly, consider err
AT [+
ATE E
aj Aj
- x)+1) O.
Next, we bound A [err
T AT
Ar [1
55
ArE
Σ
2
(1((1,)
- vs(;)\1
S 20
Σ
+1
A
1=
1=
R
T
Aroz
3/2
46
2 R
33/2
Aj
(T + +321
1=0
Now we calculate ArE [err++1]
T
ArE Jerra
ATE
10(2)+1)
+
aj (g(05+1) V[(z41) -xz+1)
2
Ag
1=
24

---

Published as a conference paper at ICLR 2024
OR
T
Araj
44
oR
T
Ara
9/2
oR
T
Aroj
9/2
S
Ú + 3)5/2
35/22
A
35/22A1
A
j=0
j=0
==
3
oR
2AT (T' + 3)7/2
4(T + 3)1/2
Finally, we consider er77+1
ATT²
TR
ATo A
3/2
TR
A7 B [erri
33/2
(T + 331/22 3)1/2"
Combining all bounds from above achieve convergence rate
19
27oR
1862R²
72MR (T+
E [[((xT+1) - f(x))
+
(T 331
(T+3)1/2
The case of stochastic Hessian (Theorem 3.2 under Assumption 2.3 by taking expectation in Lemma E.3
can be obtained in the same way
F PROOF OF THEOREM 5.6
Algorithm| 2 is the tensor generalization of Algorithm So, we will follow the same steps as in The proofs directly follow the
Appendix E
First of all, we provide tensor counterpart of Lemmas proofs of Lemmas for 2-nd order case.
Lemma F.1. For convex function f(x) and the (2x), we have
f(x))
R + X
(b(xx))
|x"
11
1000 zoll + terri
(50)
A
where
1-1 aj (g(zz+1) Vf(I)41) xx++1)
erri
(51)
1=0 A
Lemma F2. For the function fzx) with Ly-Lipschitr-comiiuuus Hessian and G((ze) is -iiexccct i-th order derivative for Ut, 1t+1
E R2d we have
p
5
Iup |:+411 - wel w +1lg(1e) f(x))l
[VVor -V S Σ
|0411-
-vell'+
p!
(52)
where we denote 83- = - ger to simplify the notation.
Lemma F.3. Let {xe, Ut 2121 be generated by Algorithm Then, any 8, 2 451, n 2 4, M 2 L
and T++1 SM.. (Vz). the following holds
?
2
+
ll((t))
[f( + (Vf( - I
8,
(p (P-1)1) #
2 min
p+1
1/. [f
(53)
p
M
(d ((-11))
[V +
min
i=
Proof. For simplicity, denote r++1 ||ae41 vell and
P
n
M
S4+1 = 5,
+
| - -veli 2 +
(p 1) |11411 ve1p--
(54)
(i - 1)!
25

---

Published as a conference paper at ICLR 2024
By Definition 5.5 for r4+1 Sp SM..h.TTo))
?22 2 V (1np(((tt1) + (x -16) + Σ
|5--1 0x11"=2 (32+11 ve))
1)!
1=3
+ M 1)!
| 1/ 11 - v2)) |2
(55)
V Vou.. p S4+1 -v))l?
From inexact solution of subproblem we get
[[4(())1) + (441 2/ $ V ( (oe,p( (11+1
(56)
S 2 Vou. (1)+1) - (f(+++)))) )1 + P + S441(114 - utll
$ V (I++1) v + +272
Next, from previous inequality and Lemma
F22
2
P
8
Lg p,ptt
4llg(e)) - vf(o))] +
'(1 +
p! [+1
p+1
+ +
ii 1)!
2 2| V - | +
(57)
2 + =1)
> [
+ 2 1), uz) + 122111244 1el1?
Hence,
72
2
+
[lg((tt)) - vf(1:)) + (VS(E++1), x(+1) 2
G+1
Se+1
2)
1 Vf((+++)]1
1
G4 - -4 Σ
+ Lp p-1 1
26
2G++1
1)!
p! t+1
and finally by using definition of Çet1, we get
7²
2
(l((ve))
[[(m)]]1++ (VI(E+1),, 1et1)2
80
d2
2
1
[V
1
G.. - (
Lp p-p
p-1
2G++1
2ç(+1
p! r+1
Next, we consider p cases depending on which term dominates C++1.
If 1,
M
1 then we get the following bound
(p-1)1
72
2
+
(g(ve)
[((e))11 + ()(++1), vr - xz41)
5,
5,
2
1
V
(f 2|
1
G2t1 -4 Σ
8
Le pp p-1
1
26+41
2G++1
c+1
pl 2+1
V f
2pd
If
no
d +
Σ
[--1
j-1
2+1
+
M
b+1
for i, 3 35isp p. we get
-²
2
+
(g(vz)
+ (V ()(r))]1 2
-
- xx+1)
5,
2
1
[ ||
+ 1
Got1
Σ
8 Lp p+1
)
r
2G1+1
2G++1
(i 1)
r+1
p! ret1
26

---

Published as a conference paper at ICLR 2024
1)1| V (2(41)1
3 28 + Σ
p
n=0 28
PM
22p
r'+1 +
r01
11:0 i+1
(i - 1)!
p'
i=
x
8, + 20
+
p
no0 + 26
(i - 1)!
r++1 +
PM + 20
pd
p-1
x+1
r
Ge+1
1=3
1 / (x++1) 1|
7/0 - 2 no + 26
rit1
(2
1)!
(i - 1)!
(i 1)!
(1
(( 1)
17.5
r
(i 1)1p
2 2/(6
(i 2)
1) (
1/o-15
in:0
2(111
pm:0;
1)lp/
2
(i - 1)!
T-T
2
V
vf(+++1)| -
noo
D
where we used (1-2)r
Ar
2
aa
3 15.
M If
1p-
1p-1y-
1-1 2 8,
+
p
[t-
n,0
1yp i+i
then similarly to previous case, we get
-²
2
+
(l((e))
{(ve))] + (V((x++)),
0r - -21+1)
5,
Lp p+l 2)
2G(+1
1
[V 1)1 + 1
|
2G++1
Gi+1 4
Σ
P
(i
8
1)!
i+1
p! e+1
)
)
rtt
(p- - 1)!
PM 2p(p!)
|V [[
ppt1
PMr
1-1
1+1
2
[[(++))] =
(p 1)!
> p
M
Next will need technical Lemmas
E.4 E.5
Lemma E4, Let (1e, Mchea1 be generated by Algorithm 2 Then
f(z)) erry" errf-errj
v min v2(xx) 2 Ar-
(58)
where
2 llg(0z)) (1b3))1
err Σ
(59)
-= O,
t-1 72
erri
Σ
(60)
3=0
and
1-1
o3
err?-
Σ 1=0
(o(est))
+
Σ
aj
(g(
V V - xz-1). (61)
24²2,
Proof. We prove Lemma by induction. Let us start with t = 0, we define A_ such that - = 0.
Then A_1
f(ao) 0 and 10 = O, hence, vे > A_1
f(xo),
Let us assume that (58) is true for t and show that
(58) is true for + 1.
27

---

Published as a conference paper at ICLR 2024
Following the steps of Lemma E.6 for p-th order case, we get
[x++1) + (VS(12+1); - r241)
Vi+1 = 4'+1 (1--1) 2
A
A
(62)
p+1
2-2
R (i 1)! d(( - vi) + at
(V (Vf(I(+)). Mi+1 - ye) - -erri - 1
A.
To complete the induction step we will show, that the sum of all terms in the RHS except error terms is non-negative.
[( A
and
Lemma F33 provides the lower bound for (V (x(()))), 2 x(+1)- Let us consider the case when the minimum in the RHS of (53) is attained at the term with particular i 3,....P. pp. By Lemma E.3 with the following choice of the parameters
Vf( 0= (2)
Ut ye+1,
U2
A
(i 1)1²
we have
2-2
R (1-1)1
at (V [V 1,:4++1),,+1111 -1h)
V Il (2) (2)=~2 (i-1))
11
yr 111
W1) 2 i
2
A.
(63)
Hence, [1(41)
1 i-2
+
1
(V [V((++)) 0 - x +
dilve+1 - -w1) + ar
(V De)
At
A.
2
(i - 1)!
A,
(((+11
1 (V - ret1)
1 V ||
+
At
At
i
(2) 1-2 R
[أ-1
f(2+11
2 2 (((++1))1
(i- 1)!
i-1
(
1 1-2 Rf
+
A. p
ni0?
i
(5)
f(14+1)
Ar
where the last inequality holds by our choice of the parameters
p² of
R
2 A n:8.
(64)
Let us consider the case when the minimum in the RHS of 53 is achieved on the second term Following similar steps, we get
2pa d.
RS
(65)
A
Next, we consider the case when the minimum in the RHS of (53) is achieved on the first term. Again,
Rt-1
by Lemma E.5 with the same choice of 2, and with 0 (1)
we have
(p-1)!-
1y!
V
(
p+1
1 + ai (VS( 91 -v)) 2 A,
llue Dc+1
p
2 p!
p +
(p-1) 1)1
(66)
Hence, we get
f(1(41) + (Vf(I441)) 1 ( +
1
1 kptl
(0-11-11--10 -
at (V (Vf( Me41 y6)
As
As
20-1 p!
A
66
f(1++1)
1
0 4.
( p+1
+ (V 1 xe41)
A.
A,"
p +
R p-
28

---

Published as a conference paper at ICLR 2024
38
f
1 2 +
V (x++1) 2t
(oT
1)!
p
[1 (f((((+))) ||
At
A.P p
M
p
(4) (4)
At
where the last inequality holds by choice of Rp+1;
(p 11+t)
g+1
M.
(67)
p+1
2
A,
To sum up, by our choice of the parameters ni. i 2, .... P. we obtain
f(r(+1)
1++1 2
erri-1 er err
Ag
Theorem F.5. Let Assumption
5.1 hold and M 2 Lp. Let Assumption 5.4 hold. After T 2 1
with parameters defined in 17 and 02 = =ō objective residual
max 8, ---11 we get the following bound for the
t=l...,
2(p + 1)8
3(p + 110RR
2(p 1) 1,
(p ()+1)2(0+1)
M RP+1 (T + p + 1)pt1
(((=T)-f(x=)) (T (++++1)12
+ (T (T+ 1)112
+ 1)¹ (p+1)) 1)!
Proof. First of all, let us bound Ar.
p+1 1 t ++pp+ t 1.
04
(68)
Then, we have
11! (T + 1)pt1'
S AT S
(69)
+++p+ 1)ptI
And from
Agafonov et al.
2023
we get
T
Ara
(p+ + 1)¹ (1' 1)i-1
(70)
A
From Lemmas F4 and
Fl
obtain that, for all t > 1,
[x+++]
ert - ETT -rr i+1
S 0it S (x")
A
50
f(x*)
R
+
||
xall
2
- -
rol 3 + err(
A,
2
Next, we apply expectation
p+1
B[((0441) S(x))) s ArE
+
XT
R²
+
Σ
k i!
R²
+
+ +err++1 err7+1 + +erT++1
(71)
Let us choose
8, 82 +
T + 0
(1 + p 1)3/2
(72)
R
X - (1 + 1/2+1/2
(73)
R
Then, we bound terms in 71 step by step.
We start from deterministic terms.
29

---

Published as a conference paper at ICLR 2024
Ar
R2
+
AT
R²
+
p
R²
kp+1
R
2
1!
(p-
i=
p + Σ
4p'-1
(p+ 1)p+1
LP
5 R²
(p+1)! d
+ MR**1
i2
(p (r
(p+ 82
P 2(p+1) R
(p 1)+1)2(o+t)) M
(T+p+ 1)
(T (T+p+1) 1)
i( + p + 1)¹
(p 1)!
(T + p p 1)++1*
up Now, we bound expectation of all enror terms. Firstly, we consider err
E E [err 1+r
A
Σ dj A
(0(x)+1)) Vf(=st)), =z+12) 0.
Next, we bound A [erry+1)
S 20² Σ AT j=0 2
A [1r A
Σ
((g(1;) vf(1;)]
i=0
68
20
Ara;
3/2
70
R
(p + 1 1)3/2
Aj
(T + p++++1)1?
Now we calculate A [erri+1]
T
Ar
(err7+1)
ATE
Σ
0
|1(()411)
- -V(()=)121
+
Σ aj (g(0)+1) Vf(es+1)) 21 -2541)
2A²xj
3=0 Aj
j=0
ooR
Araz
oR
ATa p+5/2
oR
Aroz 24522
A + 3) 1/2
(p+ 1)5/22
A3
(p+ 1)5/22A1
A
j=0
5=
1=0
(p + 1)
(p + 1)²aR
2Ar (T + p 1)p+3/2
2(T p + 1)
Finally, we consider erri+1
ArE [errr+al=
T
AvT²
72
RR
Aya
3/2
TR
Azo;
1D+1)3/2
Aj
(T + + 1)1/2"
/=0
Combining all bounds from above we achieve convergence rate
2(p + 1
3(p OR
2(p + 1)2i R,
(p 1p+11 1)+1)2(0+1)
MR
[[((ET+)) f(=)){ <
(T + (T+p+1)12
(T + p +p+ 1)²
(p+1))
(T+p+ 1)p+1
Again, the case of stochastic Hessian (Theorem 5.6 Lnddr Assumption 5.3) can be obtained in the same way by taking expectation in Lemma F3
G RESTARTS FOR STRONGLY-CONVEX FUNCTION
Theorem 6.2 Let Assumption 6.1 hold and let parameters of Algorithm be chosen as in (77. Let
{2s s20 be generated by Algorithm 3 and R > 0 be such that ||=0- - x" < R. Then for any 2 0
we have
E| x²1 2 < <
(74)
Ef(z.) f(x") < 2 20-1 R.R
(75)
30

---

Published as a conference paper at ICLR 2024
Moreover, the total number of iterations to reach desired accuracy E f(z)) - f(x²) expectation is
in
O
(rto))² ME
T (1*+1) log f130)-
+
L
p+l
(76)
11
1
Proof. We prove by induction that EB| - x²1 I 10
x²1 = R-
x
For s = 0 this
obviously holds. By strong convexity and convergence of Algorithm 2
C.
C10RR C Cpt1Lp
E [[((r) - [(x))]
+ VT
VT
T
To+1
we get
2
E pass1 Rac tm0 x²113
B Blsstallommool (o))))))))) f(x)))
2
CtR
CiaiR
Carlt
Cptilppett
1
VT
VT
T
To+1
1=2
2
pC,0l123 - =="l
pC10 - x2"l
11
8(p 2)C 2/ x=
8(p 2) x="
&C,&&l12,
xx1
pCpt1 p 2s - x= x11|
+
8(p + 0 20 x=1
8(p + 2)C p+ 4 26 x* 1|pt1
S 4(p + 2)
p
|| x 11
+
2
Vs 1| x=11.
4(p + 2)
Then by taking full expectation we obtain
2
E E1 x= 11 4
E x=
112
r. r.BBl x=1 S 4 Rg
4(p + 2)
Thus, by induction, we obtain that
74 hold.
Next we provide the corresponding complexity bounds. From the above induction bounds, we obtain that after S restarts the total number of iterations of Algorithm
S S
(((+2)).r))
2
S(p++))Cso
((p+2)C.5
(1
ET
max
1,
pP--1
M
max II.....P
s=1
S
C1 मे.
8(p+2))orr 2
1(p+2))1m
1+
+
pTT-1
pr.-1
8=1
SS+ +
(8(p+2)Cr7 RRo
2
48 + (8(p+))C1o
45
8(p+2)C2262
S+
8(p+2)C;A
+
(8(pt2)Cp+1 by 15
RiRe
1
14
log f(20) - f(x*)
(8(p+2)r
[(20) f(xx))((x=)) +
(Mipt2]Cion
[(z0) uRo
pRu
+ -( ((p++))C262) log (100) [(x")
+
Σ
(1P+2))C)8)
t +
(8p442) Ro
1) 17I
1=3
Therefore, the total oracle complexities are given by (76).
For the case of stochastic high-order derivative the proof remains same w.r.t. change 8; to d..
H ON THE SOLUTION OF SUBPROBLEM 9 IN ALGORITHM I
The subproblem (9) admits closed form solution, which we will derive in the following steps. First, note that the problem is convex. Let us write optimality condition
0 Vole(v)) (de + マड + Ralle, xoll) Foll)(v:
xo) +
Σ a
g(
1= A
31

---

Published as a conference paper at ICLR 2024
Thus,
t-1 aj - =
(Ae + R2 + Agllye 1oll) -
g(
j=0 A
(-1
Let us denote rt = 11(ye - ro)il and S: = 1|
Σ
aj A, g ))|- Then, we get
j=0
p + (Ne + Ru)r: St =0
Next, we get the solution of quadratic equation
v(,, + 22 + 4ngS, - (A++1 + R32)
2
Finally, we get explicit solution
Σ 1=
(((
== d + + Right
We use the explicit solution in our implementation of the Algorithm
32


Reviews:
[{"review_id": "LQz2F23yUJ", "reviewer": "Reviewer_KkLj", "summary": "This paper present a stochastic second-order method  based on nesterov acceleration and cubic newton, which is proven to be robust to gradient and Hessian inexactness. The faster convergence rate of this algorithm is established for stochastic Hessian and inexact Hessian compared with previous work. The lower bound for the stochastic/inexact second-order methods for convex function with smooth gradient and Hessian is also established, verifying the tightness of their convergence upper bound. The inprecision produced by solving the cubic subproblem is also taken account of in the analysis. The method is also extended to higher-order minimization with stochastic/inexactness, and a restrated accelerated stochastic tensor method is also proposed for strongly-convex function.", "questions": "1. In section 3, the subproblem you defined is $\\omega_{x}^{M,\\bar{\\delta}}=f\\left(x\\right)+\\left\\langle g\\left(x\\right),y-x\\right\\rangle +\\frac{1}{2}\\left\\langle y-x,H\\left(x\\right)\\left(y-x\\right)\\right\\rangle +\\frac{\\bar{\\delta}}{2}\\left\\Vert x-y\\right\\Vert ^{2}+\\frac{M}{6}\\left\\Vert x-y\\right\\Vert ^{3}$. Compared to the original cubic regularized subproblem, in addition to the modification of the inexactness and stochasticity, your formulation has an additional quadratic term $\\frac{\\bar{\\delta}}{2}\\left\\Vert x-y\\right\\Vert ^{2}$. Are there any reason or intuition for this term?\n\n2. Could you bring more insights for the aggregation of stochastic linear models above algorithm 1?\n\n3. The gloabal convergent (accelerated, cubic newton type) second-order methods, while they have accelerated global convergence, they usually can be proven to have superlinear local convergence rate. Is the parallel local characteristic worth to be mentioned and investigated in your stochastic/inexact setting?\n\n4. The open question mentioned, \"what's the optimal trade-off between inexactness in gradients and the Hessian?\", where in the article is intuitively investigated? \n\n5. Regarding Algorithm 3, you mentioned the 'Restarted Accelerated Stochastic Tensor Method'. Could you further elaborate on the specific mechanism and necessity of this 'restarting'? Under what circumstances should a restart be performed?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The author of this article considers several interesting questions that naturally arise for the inexactness in practice, and are therefore valuable, especially the proposed algorithm and its tight convergence rate, and the lower bounds for inexact second-order methods. \n2. The article follows a natural logic in exploring the questions,  progressing in a layered manner.\n3. The proof techniques the authors used seem solid and sound.", "weaknesses": "1. While I grasp the overarching concept of the algorithm and the principal steps in the proof, the exposition doesn't offer much in the way of intuitive understanding. Could the authors elucidate the rationale behind the algorithm's design and the parameter choices? Enhancing the exposition with additional intuitive insights into the algorithm would be highly beneficial.\n2. The assumptions (2.2 and 2.3) of stochacity and inexactness differ but seem highly related, as they lead to two quite similar convergence rates and proof for your algorithm. In this paper the way of discussing the stochasticity and inexactness settings seems a bit nesting.  Maybe it could be better if their highlevel relations  are set forth in a proper manner. \n3. Clarification: O(1/T^2) ->\\Omega(1/T^2) in P2 line 2; bounded variance stochastic Hessian ->stochastic Hessian with bounded variance; formatting issues such as sequence numbers in the algorithm list.", "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": "yze1PETABz", "reviewer": "Reviewer_S1GY", "summary": "The authors present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, typical in machine learning. It looks to achieve the lower bounds.", "questions": "How does the algorithm work in step 4 of the proposed algorithm?  Does it work in practice?", "limitations": "", "rating": 1, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "None", "weaknesses": "The algorithm of step 4 also includes another optimization problem.", "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": "XqVEWIEUj6", "reviewer": "Reviewer_2pJU", "summary": "The paper proposes an accelerated stochastic second-order algorithm using inexact gradients and Hessians, demonstrating nearly optimal convergence rates.", "questions": "1) The paper lacks an intuitive explanation of the proposed algorithm. It is suggested to explain the motivation and impact of parameters such as $\\alpha_t$, the choice of the model $\\omega_x^{M,\\bar{\\delta}}$, and the technique of estimating sequence on the algorithm's performance and convergence. \n2) When comparing computational time, is the proposed algorithm better than existing methods?\n3) The figures in the paper are too small, making it difficult for readers to interpret the results.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes an accelerated stochastic second-order algorithm using inexact gradients and Hessians, demonstrating nearly optimal convergence rates.", "weaknesses": "see questions.", "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": "Tpqs0wK2Kd", "reviewer": "Reviewer_xECU", "summary": "This work studies the unconstrained minimization of convex and strongly convex functions with continuously differentiable gradients through second-order methods with access to inexact gradients and Hessians. Further with the assumption of unbiased gradients they show a faster convergence rate of their proposed algorithm than the state of the art. Also, they show the worst-case complexity lower bound for their problem. Then, the proposed method is extended to tensor analysis and a restart scheme is proposed for strongly convex functions. Experimental results confirm the superiority of the proposed method to Extra-Newton and SGD methods.", "questions": "1- Is the $\\boldsymbol \\Phi_x$ defined at the beginning of Section 2 used? Same question holds for $\\boldsymbol\\Phi_x$ defined under Assumption 5.1.\n\n2- Lemma 2.1 seems like a special case of a similar lemma in Agafonov et al 2020. Is there a reason you did not cite their work when you present the Lemma? Same question holds for Lemma 5.2. \n\n3- How did you find the dynamic strategy for the precision level $(\\tau_t=c/(t^{3/2}))$\n\n4- According to your investigation and results, does it make sense to analyze inexactness in Hessian (or higher order information of the objective function) when gradients are inexact? This question mainly concerns the $O(1/\\sqrt{T})$ convergence rate related to the inexactness of the gradients which dominates the convergence rate as $T\\rightarrow \\infty$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1- Good flow in introduction and problem setup.\n\n2- With additional assumption on the unbiasedness of the gradient, they show the lower bound on convergence rate of inexact Hessian & gradient plus proposing a method which achieves the lower bound exept for the last term.\n\n3- They did a relatively thorough analysis by extending their analysis to tensor methods and special cases like strongly convex cases.", "weaknesses": "1- Though the text has a good flow in terms of the context, there is still room for improvements: e.g. \n\n(a) In page 2 there are two loose sentences in the middle of the page. They can be integrated with the previous paragraph or just in a new independent paragraph. \n\n(b) Below assumption 1.2: $E[g(x,\\xi)]$ or $E[F(x,\\xi)]$?\n\n(c) **\\citet** was used wrongly in many places. Please consider replacing the wrong ones with **\\citep**.\n\n(d) function $\\psi_t(x)$ above algorithm 1 is not defined (I think it is in the algorithm so you should refer to that or simply introduce it)\n\n(e) The definition of $f$ in section 7 page 8 is an abuse of notation: $f(x)=E[f(x,\\xi)]$\n\n(f) I suggest larger font size on Figures 1,2\n\n(g) Large gap in the appendix after (26)\n\n2- I think contributions 3 & 1 should be integrated.\n\n3- Table 1 might lead to misunderstanding. Your result is based on the asssumption of unbiased gradients. The rate by Agafonov does not have this assumption. Thus, it seems like an unfair comparison.\n\n4- The title of the section “Lower Bound” is very generic and also the description is vague. For example, the first sentence of this section is vague.", "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)