Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods
Authors: Kimon Antonakopoulos
Ali Kavis
Volkan Cevher
Venue: NeurIPS 2022 Accept (2022)
Keywords: second-order methods
universal methods
adaptive methods
convex optimization
stochastic optimization
acceleration

Abstract: In this work, we propose a universal and adaptive second-order method for minimization of second-order smooth, convex functions. Precisely, our algorithm achieves $O(\sigma / \sqrt{T})$ when the oracle feedback is stochastic with variance $\sigma$, and obtains the improved $O( 1 / T^3)$ convergence with deterministic oracles. Our method achieves this rate interpolation without knowing the nature of the oracle a priori, which was enabled by a parameter-free step-size that is oblivious to the knowledge of smoothness modulus, variance bounds and the diameter of the constrained set. To our knowledge, this is the first universal algorithm that achieves the aforementioned global guarantees within second-order convex optimization literature.

EXTRA-NEWTON: A First Approach to
Noise-Adaptive Accelerated Second-Order Methods
Kimon Antonakopoulos EPFL (LIONS) kimon. www.nnaaoooollllssp.......
Ali Kavis" EPFL (LIONS) ali kaviss@pfppllc
Volkan Cevher EPFL (LIONS) volkan. cew.knneceeeere
Abstract
This work proposes universal and adaptive second-order method for minimizing second-order smooth, convex funetions. Our algorithm achieves O(o (TT con- vergence when the oracle feedback is stochastic with variance o². and improves its convergence to O with deterministic oracles, where T the number of iterations. Our method also interpolates these rates without knowing the nature the oracle apriori, which is enabled by parameter-free adaptive step-size that is oblivious to the knowledge of smoothness modulus, variance bounds and the diam- of the constrained set. To our knowledge, this is the first universal algorithm with such global guarantees within the second-order optimization literature.
Introduction
Over the last few decades, first-order (convex) minimization methods have gained popularity for modern machine learning and optimization problems due to their efficient per-iteration cost and global convergence properties. The literature on first-order methods is rather dense and extensive with concrete, thorough understanding of the optimal global convergence behavior. Focusing on the more relevant settings of smooth, convex minimization, the lower bounds have been well-established; O(a/VT) when the gradient feedback is noisy with variance o². and O(1/T²) under deterministic first-order oracles [51, 57]. Under slight variations of the aforementioned problem setting, there exists an extensive amount of work that enjoys the latter, "accelerated" rate [55, 56, 52, 64, 68, 39, 2. 41, 66, 19, 18, 35, 31, 44).
On the contrary to its first-order analogue, the literature on global convergence second-order, smooth methods notably sparse with many open questions standing even in the simplest problem formulations. Following the pioneering works of Bennett I]. Kantorovich [33], Newton's 's method and its variations [40, 46] are considered the staple of second-order methods in optimization. Although its powerful local convergence behavior has been repeatedly demonstrated [17, 38), studies on its global behavior are relatively limited. Prior attempts at tackling global convergence mostly make additional structural assumptions on the objective function [60, 47, 38] or assume extra regularity conditions on the Hessian [34] beyond the simplest smooth and convex setting. Over the last decade, second-
we have witnessed important progress towards more complete theory of globally-converge order methods (more on this shortly), and yet there remains many important questions unanswered, which we will delve into in this paper.
To motivate the perspective in our technical endeavour, we take small detour introduce the idea of universality, which we particularly characterize as adaptation to the level of noise in oracle feedback. Enabled by the recent advances in online optimization, universal first-order algorithms essentially attain the ( / /T 1/T²) convergence for convex minimization problems, interpolating between stochastic and deterministic rates. There exist a plethora of algorithms that enjoy this rate under
Alphabetical order, equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

different sets of assumptions for both minimization scenarios (for convex and non-convex settings,
we refer the reader [39, 35. 22, 31, 6] and [67, 42, 36, 45], respectively), and the more general framework of variational inequalities [8, 5, 65, 25, 3, 26, 4]. However, we observe that such universal results do not exist in second-order literature, hence, it only natural to ask,
Can we design simple second-order method that will achieve accelerated universal rates beyond (lo/V++//TT)
More recently, global sub-linear convergence rates for second-order methods have been characterized by [58] for second-order smooth and convex setting. Essentially, the so-called Cubic Regularized Newton's 's Method combines the quadratic Taylor approximation in the typical Newton update with cubic regularization term. At the expense of solving a cubic problem, this method achieves O(1/T²) convergence rate. Shortly after, Nesterov [54] proposes an accelerated version of the cubic regularization idea with (1) value convergence, pioneering a new direction of research in the study of boobally-convergene second-order methods [48]. This idea has been studied further for different settings in convex optimization [28, 29] with the same accelerated ( rate and extended to non-convex realm [14, 15], obtaining the analogous rates of (11/T2/3) and ((1/T)/3) for finding first-order and second-order stationary points, respectivcly, leading the way for further investigations [10, 21, 16).
Notice that accelerated cubic regularization sub-optimal such that recent studies prove a respective lower-bound for second-order smooth, convex problems as O(1/77/2) [1, 7J. The first line of research that shrinks the gap between the upper and lower bounds for achieving an almost-optimal (more on this shortly) convergence [59] is the so-called "bisection-type" methods. Pioneered by Monteiro and Svaiter [49], these class of algorithms propose a conceptual method where the step-size of the algorithm implicitly depends on the next iterate. To resolve, the authors propose a bisection procedure that simultaneously finds step-size/next iterate pair that satisfies the conditions of the iterative update, which enables the convergence rate of O(1/77/3), modulo the complexity of bisection procedure. This idea was very recently generalized for higher-order tensor methods [23]. Not so surprisingly. the same construction finds application in variational inequality (VI) and min-mac optimization literature [12, 30]. Very recently and concurrently to our work, [13] propose the first bisection free acceleration for second-order methods, that achieves the optimal O(1/T7/3). The authors define an explicit, deterministic procedure called MS oracle and compute the step-size using a standard line-search procedure enabling them to achieve optimal rates while adaptively computing the step-size without needing to know the smoothness constant.
Although there are promising results with increasing interest into second-order and also higher- order- methods, we identify three main shortcomings in the literature, which we will systematically address in the sequel. First, bisection-type methods achieve the optimal convergence rate however, the search procedure is computationally very prohibitive [59, 43] and the resulting algorithms are complicated with many interconnected components. On the other hand, cubic regularization-ban based ideas propose a simple construction that achieves acceleration beyond O(1 (1/T2) however, similar to previous methods, they either require the knowledge of smoothness constant or need to execute standard line-search procedure to estimate it locally. A common drawback for both approaches is that the algorithmic constructions are designed for handling only deterministic oracles and is an open question whether such frameworks could immediately accommodate stochastic first and second-orde information.
To address the aforementioned issues, we developed the first universal and adaptive second-order algorithm, EXTRA-NEWTON, for convex minimization. We summarize our contributions as follows:
Our contributions:
1. We prove EXTRA-NEWTON achieves the global convergence rate of 0 0 + fil that adapts simultaneously to the variance in the gradient oracle (a,,) and Hessian oracle (a achieving the first universal convergence result in the literature.
LD"
7"
2. Our method is completely oblivious to any problem-dependent parameters including smoothness modulus, variance bounds on stochastic oracles, diameter of the constraint set and any possible bounds on the gradient and Hessian.
2

---

Table 1: A survey first and second-order algorithms with key properties
Reg.
Accel.
Extra
AGD [55]
UniXGrad [35]
ANPE
OptMS
Newton
Cubic Reg.
Newton
[49]
[13]
[48]
[54]
[ours]
Rate
v
2a
T
71/2
y7/2
T
Bisection-free Adapts to L Noise-adaptive
x
/
x
Partial
x
7
X
X
x
x
3. We design the first adaptive step-size, in the sense of [20, 62], that successfully incorporates second-order information "on-the-fly". While doing so, we bypass any bisection or linesearch procedure, and propose a simple, intuitive algorithmic framework.
From a technical point of view, what will allow us to achieve these results is the combination of Extra-Gradien [37] that was originally designed for solving variational inequalities and min/max weighted iterate averaging scheme accompanied by an appropriate gradient rescaling strategy in the spirit of [66, 19, 35] which allows us to obtain an accelerated rate of convergence by means of generalized daline-to-bated conversion (Theorem 3.3), and (iii) the glue that holds these elements together is an adaptive learning rate inspired by [62, 35, 4] which automatically rescales aggregated gradients and second order information. In what follows, we shall explicate these arguments.
three principal ingredients: (i) proposing appropriate adjustments problems; (ii) an "optimistic"
2 Problem setup
Throughout the sequel, we will be focusing solving (constrained) convex minimization problems of the general form:
minimize
f(x)
(Opt)
subject to X.
Formally, in the above X' is a convex and compact subset of d- dimensional normed space V = Rd with diameter D = maxx,yex || - yll, and f V - IR U {+o)} is a proper, lower semi-continuous, convex function with domf= = {x E Rd f(x) < foo} C X. To that end, we make set of blanket assumptions for (Opt). Following the vast literature of constrained convex minimization [53, 9], consider "simple" constraint sets, i.e.,
Assumption 2.1. The constraint set X of (Opt) possesses favorable geometry which facilitates tractable projection operator.
In order to avoid trivialities, we also assume that the said problem admits least a solution, i.c.
Assumption 2.2. The solution set X arg min fx) of (Opt) is non-empty.
Furthermore, we assume that there exists a Lipschitz continuous selection x + f2f(x) E Raxd i.e.
| f(x) v² < L||= x'1l Va,
(H-smooth)
and in addition satisfies the second order approximation:
((x) = f(x)) + (VS(x'), x') (==
+0 01 -1 x' ='(3))
(Taylor)
To that end, combining (H-smooth) and (Taylor) we readily get the following inequality:
T. 1| 2'112 -f(x))V((x>> (/'')(z>>(>>>>>>>>0)0)>>>>>>>>)) =')ll
(I)
2
The above equivalences are well-established and hence we omit their proofs (we defer a panoramic
view to [69])
Note that the bisection procedure is computationally prohibitive, defer the reader [59], 30504-305

---

Oracle feedback structure From an algorithmic point of view, we aim to solve (Opt) by using methods that require access to (stochastic) first and second order-oracle. Before we move forward with the methodology. we shall introduce the definitions and notations for this oracle model which we will use in algorithm definitions and technical discussions. Let g(r, {) denote the stochastic gradient evaluated at x with randomness defined by & and ( <) be the stochastic Hessian at z with & describing the randomness of the oracle, such that
E (g( 2 fxx). E H () <) æ| = V (t)),
E [1lg(z,)) (=)) x S
(2)
- s0))) - | - o
E
Due space constraints, we will also define an operator that accommodates second-order information and its respective stochastic counterpart.
=(r:a')=V 1 V =2)
(3)
= H(r' x')
where F is essentially the gradient (with respect to x) of the second-order Taylor polynomial. By definition, the operator F satisfies the second-order smoothness property in Eq. (1)
3 Method
In this section, we shall establish our universal second-order framework. Our presentation evolves around three key components: choosing the appropriate algorithmic template with the key motivations behind it, solving implementability issues that commonly arise in higher-order methods and finally
designing a universal algorithm that can handle deterministic and noisy oracle feedback simultane- ously without having prior knowledge. Our point of departure is the popular Extra-Gradien (EG) template; originally introduced by Korpelevich [37] and further developed in Nemirovski [50],
X X 1 = Ix (X, 7 f(xz))
(EG)
X1+1 = xxx (X, - (X,-%VV (
where xx (x) = arg x || - 2|| is the standard Euclidean projection onto the set X. In terms of output, the candidate solution returned by (EG) after T iterations the so-called "ergodic average"
Ei=bbe be
X7
Σt b2
Then, taking b, = "t and assuming the method's 's step-size is chosen appropriately, Xy enjoys the following universal guarantee [32, 61]:
B(f(X)) f(=)) ( o VT
(5)
where signifies the effect of the noisy feedback. However, as it becomes apparent, the vanilla (EG) template is not capable of matching the iconic 1/T" for the smooth deterministic case. It is well-established in the literature of smooth, convex minimization that iterate averaging (or momentum in the sense of Nesterov [55]) essential for matching the (1/T²² lower bounds. In fact, plain uniform averaging is not sufficient; one needs to introduce new iterates with increasing weights. Precisely, this is equivalent to computing an average by taking b, Ott) However, we cannot fully characterize the acceleration machinery without what we like to call "gradient weighting". On top of (weighted) iterate averaging, gradients must be multiplied by the same order of weights to achieve accelcration, which is recurring theme in the literature of accelerated and universal optimization [64, 68, 39, 2, 41, 66, 18, 35, 31].
Going back to discussion on (EG), Wang and Abernethy [66] and Kavis et al. [35] provide useful insights into acceleration within the context of (EG). Wang and Abernethy [66] identifies a 2-player game with a particular structure called FENCHEL GAME framework, which essentially reduces to minimizing a smooth, convex function when the players cooperate. By introducing an "optimistic" weighted iterate averaging along with complementary gradient weighting strategy, the framework

---

recovers different acceleration schemes of Nesterov [55, 56, 52]. On related front, Diakonikolas and Orecchia [19] proposes the first acceleration of (EG) by appropriately integrating the optimistic
averaging idea [66] into the (EG) template as follows:
X; b,X1 E bx
X
(6)
E.=1b b
E b
where b, = (t) is the "iterate averaging" parameter. Later on, Kavis et al. [35] designs an adaptive, universal variant of accelerated Mirror-Prox following the same optimistic averaging idea in
Eq. (6). All in all. it is recurring theme among accelerated algorithms to adopt weighted iterate averaging (b; O(t) with proportionate gradient weighting, and not so surprisingly, prior work establishes clear connections between the degree of weighting and convergence rate. Cutkosky [18] designs black-box reduction that accelerates class of online algorithms and proves that the rate of convergence the reduction is O(1 Ei= by) for by E [1, In retrospect, we aim at answering the following question:
What algorithmic construction would enable acceleration beyond O(1/T²)?
3.1
Implicit algorithm
We give a first affirmative answer the above question by presenting our implicit accelerated algorithm which is constructed upon (EG), and establish its convergence properties. Note that the implicitness of the scheme serves as gentle introduction the actual explicit second order acceleration, which shall follow. Formally, our scheme is given via the following recursion:
X++ = xxx 1 Yeak FX x.))
= =arg ar (V)(X, } V2 X1), Xx) + || - Xell
2
(Implicit)
X441 = II (x.-
| Xell
-arg migminar (VS(X X.) xEx
27
with Ixx (x) denoting the Euclidean projection of onto X, average sequences X, and X defined as in (6) and the adaptive step-size 7 defined as (for some 7, Bo > 0):
7/t
30 Σ.=1
V
f 544)
F(X,, s X.)1
The implicit nature (Implicit) originates from X update (which we shall refer to as (corrected) extrapolation step at times) since X,+g depends upon X,+ itself. However, this scheme exhibits several key differences from the vanilla (EG), which constitute the fundamental parts of our second- order acceleration machinery. In particular, we have:
integration of second-ore order updates for sharper extrapolation steps first step of acceleration.
interplay between averaging (b.) and gradient weighting (a:) which allows more aggressive averaging second step of acceleration.
(iii) adaptive step-size in the sense of Rakhlin and Sridharan [62] key to adaptivity and universality.
Second-order updates: First, will consider the particular interpretation of (EG) as approx- imation to the Proximal Point method [63] which serves as motivation for the accommodation of second-order information in scheme.
(PP) In particular, (EG) tries to approximate X by generating the extrapolated point X, X and make use of the gradient at Xx+ to take step from X, to X Therefore, if the algorithm is able
X Xx Vt f((++1)).
5

---

to compute a sharper estimate in the extrapolation step, it should be able live up to the fame of (PP) and display faster convergence. To this end, we augment the extrapolation step by introducing second-order term. Essentially, our algorithm makes use of second-order Taylor approximation, as opposed to first-order expansion, only for the extrapolation step, trading-off sharper approximation with second-order information.
Iterate averaging and gradient weighting: Now, we turn our attention the second component in our acceleration machinery; averaging and weighting. Recall that the acceleration framework of Cutkosky [18] guarantees a value convergence rate of O(1/(P when weighting factor satisfies by = ((P) with p E [0, 1]. We take this result one step beyond in two fronts; our algorithm exploits higher-order smoothness in order to extend this bound for p E [0, 2]. implying the accelcrated rate of O(1/T9). Second, we observe that previous work restricts the choice of gradient weights and averaging weights by taking at z b, We decouple those weights by allowing the sequences d, and by to be different, which in turn equips us with more aggressive iterate averaging when necessary.
Adaptive step-size: As the final component, we study the adaptive step-size (7) from the param- eter adaptation perspective (i.e., adaptation to the Lipschitz modulus) and expand on its universal properties in the next section. The vast literature on adaptive methods predominantly rely on con- structions of AdaGrad-like decreasing step-size policies by accumulating the observed gradient norms in its denominator. The intuition behind this choice is that whenever the method approaches a solution, the vanishing gradients bring about stabilization, ensuring progress around the solution's 's neighborhood. However, this idea fails for (compactly) constrained problems; when the solution lies on the boundary. So inspired by [62], design constraint-aware step-size by accumulating [V + F (x 22 which converges to O as X x++ X, O; which in turn implies convergence of the algorithm. To our knowledge, this is the first adaptive step-size that accommodates second order information.
Having established the core components of our design, are in position to present the first acceler- ated convergence rate guarantee for (Implicit). Formally, this is given by the following.
Theorem 3.1. Let {X++3 3 IT be generated by (Implicit) run with the adaptive step-size policy (7) where = 22 by = to with 2 2. Assume that f satisfies (H-smooth) then, it is ensured that:
max V 30
D2
D4
f(x++)) f(x)) 50
73
(max [max(DD* .FDD
When y D. obtain the converge rate O
Remark 3.1. We emphasize that the above rate does not require any prior knowledge of problem paramaters such as L., D, time-horizon and any bounds on gradient/Hessian norms. In order to have better dependence on D one could set D, and our rate of 0(1/T3) holds irrespective of
3.2 Explicit algorithm
Despite the fact that (Implicit) improves upon the accelerated rate of O(1/T"), one may easily observe that it exhibits the following drawbacks:
1. (Implicit) a conceptual algorithm and therefore, not implementable in practice. A fortiori, it cannot provide rate interpolation guarantees as it does not have the machinery to simultaneously cope with deterministic and stochastic feedback.
As discussed earlier, a common strategy for overcoming this implicit construction is using bisection/lnee-carde procedure [30, 49, 12]. Depending on the context, this procedure serves two distinct purposes. Primarily, it tackles the implicit nature of the update rule by simultancously finding pair of (7t, X(+y) ) and secondly, it enables adaptation to the second-order smoothness. However, one may identify major setbacks with these approaches; first, stochastic oracles for executing the search procedure, so it is not capable of satisfying any universal guarantees. Moreover, yields rather complicated procedure as a byproduct that has many moving parts. To that end, we propose an alternative approach which not only yields simple scheme, but
not clear how to handle

---

also provides a universal algorithm that is able to handle noisy feedback on-the-fly. Without further ado, we display our explicit algorithm, EXTRA-NEWTON. with appropriate modifications. Having defined our main scheme, Algorithm 1, we will provide more detailed description of its components.
Algorithm 1: EXXTR-NEWTOO
Input: X1 E X, 0 t² and A, = E.-1 ag. b, to (p 2 2) and B, E.m D. 7 >> 0.5r ~ w.idd
for 1 to T do
7
2: 7t
VBu + E a ( 5. - F +
E,)1 E2)
3: X arg ei (x,, Et), +
aabe (1) (X,, Ex) - -X,), Xi) + 2y, X,
2B,
4: X++1 = arg min (agg( X Set ). + 2лh || - Xzll2
5: end for
Universal step-size We modify our step-size (see Eq. (2)) in order to operate in the stochas- tic regime while making it noise-adaptive for rate interpolation. Using the same weighted averaging scheme in Eq. (6), we define the universal counterpart of the adaptive step-size, Note that Yt is independent of any variable/randomness generated iteration t; it accumulates af "fllg(X 11, +, F(X++4 X5, Et)l up to / Therefore, the step-size is decoupled from the explicit update, a priori.
Now, what remains is a new algorithmic design that will retain the accelerated convergence properties demonstrated by (Implicit) while having an explicit construction that is capable of automatically adjusting to noise level in the oracle feedback. Before expanding upon the technical details of our strategy, let us take our time explain the consequences our explicit design compared to (Implicit).
From implicit to explicit To obtain the explicit algorithm, (i) we write the projection sub-problem in the arg min form; (ii) introduce stochastic oracle feedback; (iii for the second-order term, replace X, X in 3 with the free variable x; then, (iv) simplify as follows:
a: (H (H ((xx -X,), - -Xi)
2
bixe+ + E1= box
bi + E1- box st ) Xx)
4e &i) &i)
B₁
Br
$
dir Ee= N
beX, + Eo=1 box )
Qt (((
) xx Xx) -xx)
2
B.
B.
orhe (H,,,, X,), xx), 2B,
Given the bisection-type conceptual methods [49, 30, 12], it is surprising how smoothly could transition from implicit to explicit once we decouple the step-size from the current iteration apriori. Moreover, the resulting update rule for the extrapolation step retains the quadratic structure as the Xt+1 update rule. Having analyzed the components of the explicit scheme, we will first present the universal convergence rates then provide concise explanation of the proof strategy with particular emphasis on the principal components of the analysis.
Theorem 3.2. Let 1T= be sequence generated by Algorithm 1, run with the adaptive step-size policy (2) and as = t2, b, = t² with p 2 2. Assume that f satisfies (H-smooth), and that Assumptions (2) hold. Then, the following universal guarantee holds:
2 7
D*+
max D'+
V +²+
og
7 OH
(5x4)))((x'555
VT
73/2
T
7

---

When y D. we obtain the target rate
Dog vT
Da
RT(x*) max LD'....D) T3/2
+
7s
Remark 3.2. Similar to Theorem 3.1, EXTRA-NEWTON achieves the preceding convergence rate independent the knowledge problem parameters.
Compatible with the (HG)-based algorithmic design, our proof has the following main steps
1. We perform an offline regret analysis of Alg. and show adaptive regret bounds see Prop. 3.1.
2. We prove an anytime online-to-batch conversion framework, which generalizes that of Cutkosky [18], through decoupling iterate averaging from gradient weighting see Theorem 3.3.
3. Combining the adaptive regret bound with the conversion theorem immediately implies universal,
accelerated value convergence of O Dag VT
+
Daag max LD .BED) T3/2
Theorem 3.2.
T
Let us begin with clarifying what offline regret means for Algorithm 1. We define the (linear) regret considering the convention in both online learning [62, 18] and first-order acceleration literature [66, 35, 31J.
measure the performance of our decisions for the extrapolation sequence such that after playing X J our algorithm observes and suffers the linear (weighted) loss with respect to ag V (.Vx((x+)) ++ ). Hence, we define the regret as
RT(x) Σ a (IVI(X++)))
(Reg)
where we run the algorithm for rounds. Next up, we provide our generalized conversion result. Theorem 3.3. Let Rr(x*) denote the anytime regret for the decision sequence { } as in (Reg), and define two sequences of non-decreasing weights at and b, such that a,, by 2 1. As long as asf bb is ensured to be non-increut -on-iinceus,,
((x))-(x=)) v
Br
oT br
Remark 3.3. This conversion result holds independent of the order of smoothness of the objective as long as f is convex. Moreover, it allows averaging parameter b, to be asymptotically larger than gradient weights oe, enabling more aggressive averaging strategy when necessary.
To complement the lower bound to the regret Ry(æ"), ), we present an upper bound that helps us explain how we exploit second-order smoothness for a more aggressive weighting, hence the rate (
Proposition 3.1. Let {X++]] YE=1 be generated by Algorithm 1, run with non- non-increasing step-size sequence Nt and non-decreasing sequences of weights a, by 2 such that at/b; is also non- increasing. Then, the following guarantee holds:
3D2
|X - Xell2
ERT (x 1
Σ
2 (.43) -
TT+1
7++1
Observe that the inequality in Proposition 3.1 is agnostic to the design of our step-size in Eq. (2) as well as the selection of the weights as described Theorem 3.2. It essentially applies any non-increasing sequence of step-sizes and non-decreasing gradient weight sequence 2 1. To obtaín we neither used convexity nor the smoothness of the objective. fact, the structure of the objective function, i.e., its convexity, will not be needed for upper-bounding the regret expression, and required only for conversion in Theorem 3.3.
Now, let us explain how we make use of second-orde smoothness for enjoying faster rates, and give brief discussion of how the regret bound will look in its final form. First, we decompose the (X El) into deterministic feedback and noise. Then, argue that the noisy component grows O(0H13/2 f,/3) On the other hand, achicving the accelerated 0( component of the universal rate amounts to showing that the regret has constant, O(1), component. In the worst-case sense, however, the deterministic component itself grows as (77522). Fortunately, we identify that the negative term "large enough" magnitude to control the growth of the deterministic term, permitting constant component O(LD²) for the regret.
stochastic term ( (X+t)

---

Although the regret bound of O(D + D' + Do seems counter- intuutive from an online-learning perspective, it will make perfect sense when we discuss how second-order smoothness leads to "faster" conversion through more aggressive averaging. As a matter of fact, we will continue our discussion with how second-order smoothness helps us accelerate. (H-smooth), iterate averaging as in (6) and compactness of X, we can bound the negative term as,
turns out that using
1
x,I1 L2D
t ++ y(
Y+11
Observe that to seamlessly combine the positive and negative terms, our analysis enforces that a = O(P)) and b, = Q(()). Then, the conversion implies a convergence rate of (T hence the recipe for acceleration. Therefore, the constant component of the regret amounts to ( convergence rate, while the stochastic component of the regret implies ((nn/T8// /T3/2 + og/ VT) rate, giving us the first universal acceleration beyond first-order smoothness.
Let us conclude by discussing the intricate relationship between the universal step-size and the regret bounds. Simply put, growth of the summation in the denominator of % is of the same order as the regret bound. Under stochastic gradient and Hessian oracles, the regret bound of order ((T5/2), and we can trivially show using variance bounds that the step-size lower bounded by OTT-5/2). On the other extreme, the regret bound described in Proposition 3.1 is bounded by a constant under deterministic oracles, which implies that the summation the denominator of the step-size is in turn summable, i.e., the step-size has a positive, constant lower bound. This adaptive behavior of our step-size enables automatic adaptation to noise levels and thus the universal rates.
Experiments
In this section, we will present practical performance of EXTRA-NEWTON against set of first-order algorithms, e.g., GD, SGD, ADAGRAD [20]. ACCELEGRAD [41], UNIXGRAD [35]; and second- order methods, e.g., NEWTON'S, s, Optimal Monteiro-Svaiteer (OPTMS) [13], Cubic Regularization of Newton's 's method (CRN) [58] and Accelerated CRN (ACRN) [54] for least squares and logistic regression problems over a LIBSVM datasets, ala and a9a. Our main objective is three-folds. First, when the objective has a favorable structure as in least squares, second-order method has cheap oracle costs and display superior convergence behavior. Second, we want to demonstrate the improved rates of our algorithm against accelerated and non-accelerated first-order methods through the reguullard logistic regression problem. Finally, we compare our methods with respect to other second-orde methods that achieve (almost) optimal rates. In the plots, the statement # of oracle calls on the x-axis counts any gradient or Hessian computation as one oracle call. Also note that we consider the black-box oracle model in which the algorithms only have access to gradient and Hessians without knowing the actual objective function.
When the problem is suitable, second-order methods show promising performance with truly superior time. In Figure la, we display the result for least squares setting. Second-order methods are known to be suitable for quadratic problems, and our method exploits its hybrid construction to converge significantly faster than first-order methods, matching the behavior of NEWTON's For the logistic regression problem, we regularize it with g(x) = 1/2[|=]| , but use a very small regularization constant to render the problem ill-conditioned, making things slightly more difficult for the algorithms [47, 48]. Although we implement NEWTON'S s with line-search, we actually observed sporadic convergence behavior; when the initial point is close to the solution it converges similarly to NEWTON, however when we initialize further away it doesn't It converge. This non-convergent behavior has been known for NEWTON'S s, even with line-search present [27]. On the contrary, EXTRA- A-TTTNNENTO consistently converges; even if we perturb the initial step-size and make it adversarially large, it manages to recover due to its adaptive step-size. We complement our numerical tests by comparing EXTRA-NEWTON with a set of second-order methods. To that end, we implemented our method within the framework presented in [13]. Using the implementation and the experimental setup provided in their GitHub repository [24], we implemented our method in their code and compared against NEWTON'S, s, CRN, ACRN and OPTMS algorithms. Figure shows that EXTRA-NEWTON has comparable performance to OPTMS, which has the theoretically faster rate /2)/TT/2), and marginally outperforms with respect to number of linear system solutions since the linesearch procedure of OPTMS might require multiple system solutions per iteration. While CRN and ACRN has worse convergence than EXTRA-NEWTOR NEWTON'S ' seems to have the fastest.

---

107
10
10
107
10
10-
10
10
10-11
AcceleGrad
10
AcceleGrad
UniXGrad
UndXGrad
ExtraNewton
Newton
Newton
107
16
10a
16
10
167
10
10
16
oracle calls
oracio calls
(a) Least-squares regression ala
(b) Logistic regression ala
Figure 1: Comparison of value convergence for regression problems with deterministic oracle access
10
10
10
8 10
38 10
10a4
10
EstroNewton
ExtraNeewtnn
OptM5 Acaptive
Montairo-Svaiter
10
Rog
10
Cubic Reg
10
Act. Cubli Reg
Acc Cubic Reg
107
10a
Hession computations
systemn solutions
(a) Value convergence w.r.t Hessian oracle calls
(b) Value convergence w.r.t. linear system solutions
Figure 2: EXTRA-NEWTON second-order methods. Logistic regression with a9a dataset
Note that the initialization favors NEWTON'S as lies in close neighborhood of the solution, and NEWTON'S S performance sporadically deteriorates when initialized arbitrarily.
5
Conclusion
In this work, we present the first universal, second-order algorithm, EXTRA-NEWTON, which enjoys the value convergence rate of O(ag/vT + an /3/33/2 of bounded variance on stochastic gradients stochastic Hessian, we prove adaptation to the noise in first and second-order oracles, simultaneously, while showing accelerated rates matching that of Nesterov [54] under the fully deterministic oracle model. To that end, an important open question is whether could design a method that achieves improved rate interpolation guarantee Ola,/ VT + H F 322 + 1/T7/2) without depending any line-search/bisection mechanism. We defer this future work.
1/T*). 117T)) By extending the notion
Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n 725594 time-data) and the Swiss National Science Foundation (SNSF) under grant number 200021, 200021_205011. 205011.
10

---

References
[1] Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 774-792. PMLR. 06-09 Jul 2018.
URL https: httt:::/pprccedinngg mlr prwss/v7 5/ /aaargaaalllaa 18a. h8t.mml..
[2] Zeyuan Allen Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification gradient and mirror descent, 2016.
[3] Kimon Antonakopoulos, E. Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-prox algorithm for variational inequalities with singular operators. In NeurlPS 'I9: Proceedings of the 33rd International Conference Neural Information Processing Systems, 2019.
[4] Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra-gradient methods for min-max optimization and games. In International Conference on Learning Representations. 2021. URL https://openrevi// net/ forum? Add-RodkFRFF
[5] Kimon Antonakopoulos, Thomas Pethick, Ali Kavis, Panayotis Mertikopoulos, and Volkan Cevher. Sifting through the noise: Universal first-order methods for stochastic variational inequalities. In NeurlPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
[6] Kimon Antonakopoulos, Dong Quan Vu, Volkan Cevher, Kfir Yehuda I. Levy, and Panayotis Mertikopoulos. UnderGrad: A universal black-box optimization method with almost dimension- free convergence rate guarantees. In ICMI. '22 Proceedings of the 39th International Conference on Machine Learning, 2022.
[7] Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, pages 1-34, 2019.
[8] Francis Bach and Kîrr Yehuda Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. In COLT 19: Proceedings of the 32nd Annual Conference on Learning Theory, 2019.
[9] Amir Beck and Mare Teboulle. fast iterative shrinkage thressodiirn algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-22)))) 2009.
[10] Stefania Bellavia, Gianmarco Gurioli, and Benedetta Morini. Adaptive cubic regularization methods with dynamic inexact Hessian information and applications finite-sum minimization. IMA Journal of Numerical Analysis, 41(1):764-799, 2020. ISSN 0272-4979. doi: 10.1093/mmumm/4r7777 URL
https://doi. org/ 10. 1109///mmmm/////eee drr20
[11] Albert A. Bennett. Newton's 's method in general analysis. Proceedings of the National Academy of Sciences, 2110):522559, 1916. doi: 10.10733pmas...10.99 URL https://www. ppws. org/ hww//doi////////se// 1073/
pnas 10.
[12] Brian Bullins and Kevin A. Lai. Higher-order methods for convex-concave min max optimization and monotone variational inequalities, 2020. URL https://arxiv, https://axivvoor/abbbb wwt..oo//o////////// 0tt///20000000 045288.
[13] Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter accelcration. ArXiv, abs/2205.15377 2022.
[14] Coralia Cartis, Nicholas I. Gould, and Philippe L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part i: Motivation, convergence and numerical results. Math. Program,, 127 (2):245-295, apr 2011. ISSN 0025-5610.
[15] Coralia Cartis, Nicholas I. M. Gould, and Philippe Toint. Adaptive cubic regularisation methods for unconstrained optimization, part Worst-case function- and derivative-evaluation complexity. Math. Program.. 130(2):295-319, dec 2011. ISSN 0025-5610.
doi: 10.1007/510107-0000-03377 URL
https://doi. www.oorg//11/.. 100 1007 11017700990037771
[16] Xi Chen, Bo Jiang. Tianyi Lin. and Shuzhong Zhang. Accelerating adaptive cubic regularization of newton's method via random sampling. Journal of Machine Learning Research, 23(90):1-33, 2022. URL
http://jmlr.ow wwwpa/lrooorrrpppeerreeee wwtp:/ppprs//233333 022222099100002 910.html.
[17] Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint. Trust Region Methods. Society for Industrial and Applied Mathematics, 2000. doi: 10.1 79.77/9997888877988777 URI. https://epubs. siam. org/ doi doi/abs/10, 1137/1.97888983. 97888987198877..
[18] Ashok Cutkosky. Anytime online-to-batch conversions, optimism, and acceleration. the International Conference on Machine Learning (ICML), June 2019.
[19] Jelena Diakonikolas and Lorenzo Orecchia. Accelerated extra-gradient descent: A novel accelerated first-order method. In ITCS, 2018
[20] John Duchi, Elad Hazan, Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):121-2111 2011.
[21] Jean-Pierre Dussault and Dominique Orban. Scalable adaptive cubic regularization methods. 2021. doi: 10.13140/RG.2.2111 18242.1111111
111.1111188800 15680. URL http://rgdoi.. net/10. 13140/Roo /R.. 2.2. 18142. 15680.
11

---

[22] Alina Ene, Huy L. Nguyen, and Adrian Vladu. Adaptive gradient methods for constrained convex optimization and variational inequalities, 2021.
[23] Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, and César A. Uribe. Optimal tensor methods in smooth convex and uniformly convexopimization. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirry-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1374-1391. PMLR, 25-28 Jun
2019. URL sttps://prooeedinng
mlr. . ppwps/v99////// prress/v99gasiikov1999 //aggiionniaaa.../ html.
[24] Danielle Hausler. Optimal and adaptive monteiro- -varter acceleration. https://gi tewiittub.oooo
danielle- hawlleeraauleee/sssee wwwpleerrmsoootmmmlllla 2022.
[25] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous
games: Optimal regret bounds and convergence to Nash equilibrium. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[26] Yu-Guan Hsieh, Kimon Antonakopoulos, Volkan Cevher, and Panayotis Mertikopoulos. No-regret learning in games with noisy feedhack: Faster rates and adaptivity via learning rate separation, 2022. URL.
https://arxiv, wwwpriiiv.rrgraaio.oo wrgg//r//////a abs6 06015.
[27] Florian Jarre and Philippe L. Toint. Simple examples for the failure of newton's 's method with line search for strictly convex minimization. Math. Program.. (0:00112)233--0 34, jul 2016. ISSN 0025-5610. doi: URL https://dpo.ooo.o.. org 1007 /s00000 077777015-91111 0913-2.
10. 00.1007/110107-05--0993
[28] Bo Jiang. Tianyi Lin, and Shuzhong Zhang. A unified scheme to accelerate adaptive cubic regularization and gradient methods for convex optimization, 2017. URL ht http://aaaaw.....//a/////aaaaa// 11100. 04788.
[29] Bo Jiang, Tianyi Lin, and Shuzhong Zhang. A unified adaptive tensor approximation scheme to accelerate composite convex optimization. SIAM Journal on Optimization, 30(4))2877-2966, 2020. doi: 10.1137/
19M1286025. URL https://doi. http://ddioorgg///// 113771991186922
[30] Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex- saddle point problems, 2022. URL pettps://arxio wttps//.rgga/bb////eeee ht/p//bb2222220///...
[31] Pooria Joulani, Anant Raj, Andras Gyorgy, and Csaba Szepesvari. A simpler approach to accelcrated optimization: iterative averaging meets optimism. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4984-4993. PMLR, 13-18 Jul 2020. URL ttttp:::/proceeeiii joul ani html.
mlr. press/v119/
[32] Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[33] L. V. Kantorovich. Funetional analysis and applied mathematies. Uspekhi Mat. Nauk, 3:89- -85, 1948.
[34] Sai Pranceth Karimireddy, Schastian U. Stich, and Martin Jaggi. Global linear convergence of newton's method without strong- strong-convexity or lipschitz gradients, 2018. URL https: http://wwwwwgga/a/////eeea aas////ss///// 1886.. 00413.
org
[35] Ali Kavis, Kfir Y. Levy. Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, F. Fox, and Garnett, editors, Advances in Neural Information Processing Systems 32, pages 6260-6269. Curran Associates, Inc., 2019.
[36] Ali Kavis, Kfr Yehuda Levy. and Volkan Cevher. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. In International Conference on Learning Representations, 2022. URL https://openreevex. www.wwwwweeeeeeeeeeeeeeeeeeeeeee met/forumm wwwtorrmmdddddddooo dd=dSS0QtRM)OO..
[37] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12: 747-756, 1976.
[38] Dmitry Kovalev, Konstantin Mishchenko, and Peter Richtárik. Stochastic newton and cubic newton methods with simple local tinear-quadree rates, 2019. URL https://arxiv.orgg wrtp/br////////// 01597.
[39] Guanghui Lan, An optimal method for stochastic composite optimization. Mathematical Programming. (33(1-2)3365-397 2012.
[40] Kenneth Levenberg. A method for the solution of certain non linear problems in least squares. Quarterly of Applied Mathematics, 2:1 166,, 1944.
[41] Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In Neural and Information Processing Systems (NeurIPS), December 2018
[42] Kfir Yehuda Levy, Ali Kavis, and Volkan Cevher. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL id=ytke6qKpxtr.
net/ net/forum? forum?
[43] Tianyi Lin and Michael. I. Jordan. Perseus: A simple high-order order regularization method for variational inequalities, 2022. URL attps:// :/aasiiv////////a/aa/aaaeaaaaaaa org/ wtt.///22.....22
12

---

[44] Zijian Liu, Ta Duy Nguyen, Alina Ene, and Huy L. Nguyen. On the convergence of adagrad on r Beyond convexity, non-asymptotic rate and acceleration, 2022. URL
http:iiv.or//b//////e/e/ .tt.//299991122.... 14827.
[45] Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy L. Ngugen, Meta-storm: Generalized fully-adaptive variance reduced sgd for unbounded functions, 2022. URI. J.R..httss://axivv.rrr///
2209. 14853.
[46] Donald W. Marquardt. An algorithm for least-squares estimation of nonlinear parameters. Journal of the Society for Industrial and Applied Mathematics, 11(2):311444 1963. doi: 10.1137/0111030 URL
attps://doi. www/orgg./00 10. 0113/001100
[47] Ulysse Marteau-Ferey, Francis R. Bach, and Alessandro Rudi. Globally convergent newton methods for ill-conditioned generalized self-concordant losses. In NewrlPS, 2019.
[48] Konstantin Mishchenko, Regularized newton method with global o(1/k²) convergence, 2021. URL
attps://arxix wwtreiiiii.gggaaoe (org/abbs/111 02089.
[49] 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 on Optimization, 23(2): 1092-1125, 2013. doi: 10.1137/1 10833786. URL https: httsss:/ddooooro/ org/10. 1tw.1113711111111 171/180333786.
[50] Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229 251, 2004.
[51] Arkadii Nemirovskii, David Borisovich Yudin, and ER Dawson. Problem complexity and method efficiency in optimization. 1983.
[52] Yu Nesterov. Smooth minimization of non-smooth functions. Math. Program.. 103(1)) may 2005. ISSN 0025-5610.
doi: 10..1007/110007-004--555222 URL https:/ //dp::://dd.... .ww.oi.orgggo orgg /00 1007/
s10107- 804 0552-5. 5.
[53] Yu. NESTEROV. Cubic regularization of Newton's method for convex problems with constraints. LIDAM Discussion Papers CORE 2006039, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE), April 2006. URL peatttss///ddass repec. ptggp//or///// //co//loocc//200033 html.
[54] Yu. Nesterov. Accelerating the cubic regularization of newton's 's method on convex problems. Mathematical Programming, 2008
[55] Yurii Nesterov. A method for solving the convex programming problem with convergence rate (1/k²). Dokl. Akad. Nauk SSSR, 269:543-547, 1983.
[56] Yurii Nesterov. On approach to the construction of optimal methods of minimization of smooth convex functions. Ekonomika Mateaticheskie Metody, 24(3):509-517, 1988.
[57] Yurii Nesterov. Introductory lectures on convex optimization. 2004, 2003.
[58] Yurii Nesterov and Boris Polyak. Cuhic regularization of newton method and its glohal performance. Math. Program., 108: 177-20, 08 2006. doi: 10.10077/1101077000--00666
[59] Yurii E. Nesterov. Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Applications. Springer, 2018.
[60] Boris Polyak. kewton-kantorovich method and its global convergence. Journal of Mathematical Sciences, 133:1513-1525 1523,, 2006.
[61] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In NIPS 11: Proceedings of the 27th International Conference on Neural Information Processing Systems. 2013.
[62] Sasha Rakhlin and Karthik Sridharan. Optimization, learning. and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
[63] R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877 898, 1976. doi: 10. 1177003144066 URL https://doo .org/10. /00 1137/ 031 0314056.
[64] P Tscng. On accelcrated proximal gradient methods for convex-concave optimization. submitted to SIAM Journal on Optimization, 01 2008
[65] Dong Quan Vu, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Fast routing under uncertainty: Adaptive learning in congestion games with exponential weights. In NeurIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
[66] Jun-Kun Wang and Jacoh D) Ahernethy. Acceleration through optimistic no-regret dynamics. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Basa-BBinchh,, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 3824-3834. Curran Associates, Inc., 2018.
[67] Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th Interna- tional Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 6677-6686. PMLR, 09-15 Jun 2019. URL http://proceeddigs mlr, wpwsss/vvviv http//////////////// html.. html.
13

---

[68] Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11(02)):543-2556 2010.
[69] NESTEROV Yurii. Implementable tensor methods unconstrained convex optimization. LIDAM Discussion Papers CORE 201 8005, Université catholique de Louvain, Center for Operations Research and Ecomometrics (CORE), March 2018. URL html.
repec.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2 and
Theorem 3.1, 3.3, 3.2
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URLY? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters. how they were chosen)? [Yes]
(c) Did you report enror bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] We provide mean and standard deviation on the curves over multiple runs
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [NA]]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica- ble? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on
participant compensation? [N/A]
14


Reviews:
[{"review_id": "sN7PW8lb3Vs", "reviewer": "Reviewer_9RHq", "summary": "This manuscript proposes an algorithm for constrained smooth optimization that achieves simultaneously $O(1 / \\sqrt{T})$ convergence rate for stochastic gradient and Hessian estimators and $O(1/T^3)$ convergence rate in the deterministic setting. The keys are a combination of the extragradient and the Newton method as well as a carefully chosen adaptive step size scheme.\nThe general idea is interesting and it leverages techniques from online learning/optimization so the context is indeed relevant to machine learning.\nThe manuscript is well-motivated with a clear explanation of its derivation, but the idea of adding a constraint set actually makes the algorithm non-implementable in practice, and thus, although interesting in theory, I doubt the usefulness of the proposed method.\nThere are also some unclear technical definitions in the theorems that need to be clarified. See the detailed comments.\nAnother concern is that the amount of experiments is far from sufficient to sufficiently support the performance of the proposed algorithm. I also have some concerns with the experimental results.", "questions": "1. My biggest concern is about line 2 of Alg. 1. When there is a constraint, clearly this subproblem is in general difficult to solve, especially since H(X) is in general nondiagonal. Thus it looks to me that this algorithm is still not implementable, just like the conceptual one in sec 3.1.\n\n2. Another issue is surely the applicability of this algorithm and how to do a fair evaluation. The authors selected only low-dimensional problems, surely because the cost to invert the Hessian will otherwise be too high. In a more practical setting, usually the Newton step is obtained through an iterative algorithm like CG that queries the 2nd-order oracle n times (assuming that the exact Newton step is needed), where n is the problem dimension. I wonder how the convergence figure would change in that setting.\n\n3. I also would like to know about the running time comparison of these algorithms, especially in the setting of higher-dimensional problems.\n\n4. I am very confused about the results of Newton for least-square. Shouldn't the classical Newton's method take only 1 iteration to find the optimal solution? (And this also shows how this oracle call evaluation for least square is pointless.)\n\n5. Thm 3.1 mentioned $\\sigma$ in the assumptions, but the bound seems to be irrelevant to any stochasticity or expectation. I am thus wondering if there are any typos or missing things.\n\n6. I don't quite see where the 1st equation after L. 236 is from. What does it mean and why out of nowhere this thing \"to be simplified\" appears.\n\n7. Starting from Alg. 1, there suddenly is a quantity $B_t$ that is never defined in the text. What exactly is this?\n\n8. Surely it is appealing theoretically to have a universal algorithm for all settings, but in what real-world application does one face such a situation such that we don't know whether the oracle is noisy or not?\n\n9. This is not directly relevant to the evaluation of this work, but I am also curious about what would happen if the variance changes over iterations. Would it be possible to get a better rate in terms of the sum or so of the iteration-wise variances?\n\n10. After reading others' reviews, I realized that I previously missed the point that this method does not apply to unconstrained optimization, and thus my first comment becomes vital, so I am lowering the evaluation. Also D is not defined in the main paper.\n\n---\nI am happy that the authors are willing to make the assumption on the constraint set explicit, so I'm increasing my score to 4.", "limitations": "As mentioned in the comments, the authors did not mention at all that solving a constrained second-order optimization problem to optimality is actually something difficult and thus also not implementable, just as the existing work they criticized.\n\nThey then went on to ignore this fact and conducted experiments on unconstrained problems, which is deceptive.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The work is well-motivated with a detailed explanation of its derivation.\n2. The result seems to be novel up to my knowledge and of certain importance.\n\nWeakness:\n1. Insufficient numerical results\n2. The algorithm is nonimplementable\n3. There are key symbols used in the text that are undefined and hindered understanding of the results", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YvCI0jQ-GPA", "reviewer": "Reviewer_2XcJ", "summary": "The authors propose an accelerated second-order method interpolating between global convergence rate of $O(\\sigma/\\sqrt{T})$ and $O(1/T^3)$ for minimizing Hessian-smooth, convex functions with stochastic / deterministic oracles, while being oblivious to knowledge of problem parameters. This is achieved by (1) extra-gradient framework incorporating second-order information; (2) careful iterate and gradients averaging for the updates that keeps memory of past iterates; (3) an adaptive step-size scheme that can automatically adapts to noisy feedback and bypass any potentially complicated line-search procedure needed for estimating relevant problem-dependent parameters. Numerical experiments are also presented showing speedup and stability compared to alternatives. ", "questions": "Minor comments / typos: (1) it's a bit unclear what line 115 \"the operator F satisfies eq (1)\" means here; (2) after line 122 (EG): I assume you mean $x_t -> X_t, x_{t+1/2} -> X_{t+1/2}$? (3) Cubic-regularized Newton might be another nice addition to benchmark for the numerical section, considering it is also a second-order method that is both implementable and stable.", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and relevant work thoroughly surveyed. As a practical globally convergent second order method that is both universal and adaptive, it is of clear significance and relevance. In terms of the technical contribution, I find the construction of the policy for the adaptive step-size particularly interesting and similar ideas might find application in other second-order methods as well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ml3w3gl1-M6", "reviewer": "Reviewer_o7wn", "summary": "The paper proposes a second-order method for minimizing second-order smooth and convex problems, based on an extra-gradient template (thus term it as ExtraNewton). The key feature of this method is that it uses a new stepsize rule that is independent of the smoothness modulus, variance bounds and the diameter of the compact set, which, as the authors claimed, makes the proposed method adaptive and universal. By introducing an optimistic weighting strategy for the decision variables as well as the gradients, they show that the proposed method can enjoy an accelerated rate of O(\\sigma/\\sqrt{T} +1/T^3) for a stochastic oracle so long as the sequence of weights are properly chosen and the above stepsize rule is employed. Numerical experiments have illustrated the performance of the proposed method in comparison to several existing well-known methods.", "questions": "- Will it be possible to remove the assumption of a set being compact, and what the rate will become if the assumption is void.\n- How does the performance of the proposed method compared to those accelerated methods using cubic regularization for deterministic cases. The reviewer did not see such comparison in this paper.\n- Except for the choice of a_t and b_t in this work, is there any other choice that may leads to better convergence performance (numerically)?\n- In Figure 3, it can be observed that AcceleGrad outperforms others, including ExtraNewton in both least-square and logistic regression problems; is there any proper explanation on this since it should be better according to the theorectical rate obtained for the stochastic oralce?\n- Since the algorithm employs second-order information, the reviewer would like to know (just for curiosity) if it is scalable to high-dimensional problems and if the analysis can be extended to stochastic problems with finite sum structure involving a great number of samples?  \n", "limitations": "- The authors are suggested to make comparison (at least via numerical experiments) to the closely related accelerated method such as those relying on cubic regularization. \n- The part of transiting implicit algorithm to explicit one (line 234- line240) lack of some intuitition and the authors are suggested to elaborate on this.\n- In the statement of theorem 3.1 and 3.2, the reviewer guess that the Taylor condition and H-smoothness are both need to ensure (1), which most of the proofs rely on. Besides, the proofs for these above two theorems share a lot of similarity, thus it is suggested to, if possible, properly combine them.\n- It would be of great interest if the authors can remove the assumption of compact sets and extend their analysis, if possible, to account for finite-sum problems.\n\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The algorithm is new to the reviewer and it is a very nice property that the stepsize can be adaptive to the smoothness modulus which is usually hard to estimate. In addition, the algorithm is shown to enjoy a rate of O(\\sigma/\\sqrt{T}+1/T^3) for a stochastic oracle, which is not obtained before for existing second-order methods to the best of the reviewer’s knowledge.\n- The paper is technically sound and some proof techniques seems interesting. The reviewer have checked most of the proofs which seems correct.\n- The paper is well written and organized in a way that is very easy to follow; and the authors have demonstrated an excellent understanding of the existing literature on second-order optimization. \n\n\nWeakness\n- In the proof for the main results, the diameter of the compact set “D” seems very important to obtain the O(1/T^3) rate. However, this is quite restrictive for smooth problems, especially when the Hessian is also smooth.\n- It follows from Fig. 3 that numerical performance of the proposed method seems not working very well when it comes to stochastic problems.\n- The design of the adaptive stepsize rule lacks some intuition. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DG1z9NT8SAW", "reviewer": "Reviewer_fZEZ", "summary": "In this work, the authors propose a new accelerated second-order method for\nconvex optimization. The convergence rate of this algorithm on the standard\nclass of convex functions with Lipschitz continuous second derivative is $O(1 /\nT^3)$, which is exactly the same as that of the standard Accelerated Cubic\nNewton Method. However, in contrast to the latter, the new method neither\nrequires the knowledge of the Lipschitz constant, nor uses any \"line search\"\nfor estimating it. Instead, the method accumulates certain quantities, that\nmeasure the deviation of the gradients from their linear approximations, and\nuses this information for computing the next iterate. The main feature of the\nnew method is that it can work not only with a deterministic oracle but also with a\nstochastic one. Moreover, the method is \"universal\" in the sense that it\nautomatically adapts to the actual variance of the oracle, and therefore\nrequires no changes in its algorithmic scheme compared to the deterministic\ncase.", "questions": "Major remarks:\n\n1. The notation $g(x)$ and $H(x)$ for stochastic gradients and Hessians is\n   confusing as it does not highlight the randomness in the stochastic oracle.\n   For example, it is not clear whether you use the same random variable for\n   generating $g(\\\\tilde{X}\\_t)$, $H(\\\\tilde{X}\\_t)$ and $g(\\\\bar{X}\\_{t + 1/2})$ in\n   Algorithm 1, or different ones. A better notation would be $g(x, \\\\xi)$ and\n   $H(x, \\\\xi)$, where $\\\\xi$ is a random variable from a certain distribution\n   $\\\\mathcal{D}$. In this case, you can explicitly state in Algorithm 1 that you\n   sample, e.g., $\\\\tilde{\\\\xi}\\_t, \\\\bar{\\\\xi}\\_{t + 1/2} \\\\sim \\\\mathcal{D}$, and then\n   compute $\\\\tilde{g}\\_t \\= g(\\\\tilde{X}\\_t, \\\\tilde{\\\\xi}\\_t)$, $\\\\tilde{H}\\_t \\=\n   H(\\\\tilde{X}\\_t, \\\\tilde{\\\\xi}\\_t)$ and $\\\\bar{g}\\_{t + 1/2} \\= g(\\\\bar{X}\\_{t + 1/2},\n   \\\\bar{\\\\xi}\\_{t + 1/2})$.\n\n2. I do not see the purpose of presenting the \"implicit algorithm\". To me, it\n   looks rather confusing. Furthermore, as far as I understand, it is completely\n   identical to Algorithm 1 (considering the deterministic oracle). If this is\n   indeed the case, then what is the need for introducing such redundancy in the\n   paper (1 extra page in the main part, and 6 extra pages in the supplementary\n   material)? In my opinion, Algorithm 1 is sufficiently simple in itself.\n   Therefore, I would suggest to completely remove the \"implicit algorithm\" (and\n   its convergence analysis), and use the free space to better describe\n   Algorithm 1 and its convergence analysis. To make the method easier to\n   understand, instead of splitting it into \"implicit\" and \"explicit\" versions,\n   it might be reasonable to first discuss the deterministic case and then\n   quickly describe what becomes different in the stochastic case.\n\n3. I suggest incorporating the updates of $\\\\tilde{x}\\_t$, $\\\\bar{x}\\_{t + 1 / 2}$,\n   $\\\\gamma\\_t$ and $B\\_t$ directly into Algorithm 1 to make it easier to\n   understand. Otherwise, it is not clear that there are no cyclic dependencies\n   in the definitions.\n\n4. Algorithm 1, line 2: It would be better to add some comments about the\n   complexity of this step, as this is no longer the standard Euclidean\n   projection. For example, in the important case, when the set $\\\\mathcal{X}$ is\n   a Euclidean ball, this step can be efficiently computed using a tridiagonal\n   factorization of the Hessian; the complexity is then similar to that of the\n   standard Cubic Newton step. Another interesting case is when $H(\\\\tilde{X}\\_t)$\n   has low-rank structure.\n\n5. Eq. (8): Why is there \"$1 + \\\\ldots $\"? Can we have there any other constant\n   instead of $1$? The problem with $1$ is that it is a \"wrong\" constant, as it\n   does not correctly interact with the squared gradient terms (they have\n   different physical dimensions). More precisely, in its current form, eq. (8)\n   makes Algorithm 1 not scale-invariant. Indeed, if we multiply the objective\n   function by some positive constant $\\\\tau > 0$, then all the gradients and\n   Hessians will also be multiplied by $\\\\tau$, but $\\\\gamma\\_t$ will not be\n   divided by $\\\\tau$, and therefore the method will construct a completely\n   different trajectory $x\\_{t + 1 / 2}$ (although the problem did not really\n   change). Note that we would not have this issue if there was, e.g., \"$0 +\n   \\\\ldots$\".\n\n6. Theorem 3.2: There are some typos in the formulas. In any case, I suggest\n   presenting the complete 3-term guarantee which appears between lines 769 and 770.\n   It would be good to emphasize that the first- and second-order noise\n   terms decrease at different rates.\n\n7. Why do we take $b\\_t \\= t^3$ in Theorem 3.2? If I understand correctly, a\n   simpler choice $b\\_t \\= t^2$ also works.\n\n8. Theorem 3.3 and Proposition 3.1: As far as I understand, we do not need the\n   part \"non-decreasing weights $a\\_t$ and $b\\_t$ such that $a\\_t, b\\_t \\\\geq 1$\".\n\n9. Why do we not choose explicitly $a\\_t \\= (B\\_t / b\\_t)^2$? As far as I\n   understand, this is exactly what is needed in the proofs (plus the fact that\n   $a\\_t / b\\_t$ is decreasing, which can be easily ensured by taking $b\\_t \\= t^p$\n   with $p \\\\geq 2$).\n\n10. Experiments: 1) What $f$ and $\\\\mathcal{X}$ do you use in the experiments?\n   Please specify them using formulas. 2) Please clarify whether the methods use\n   the stochastic oracle (and which), or not. 3) What is the point in doing\n   regression and classification on the same data set (a1a)? 4) Why does Newton\n   method not convergence in one iteration in Figure 1a)? Is it not a quadratic\n   problem? 5) It is surprising that ExtraNewton exhibits superlinear\n   convergence, as it is not common for accelerated second-order methods to\n   possess such a property (e.g., Accelerated Cubic Newton does not have\n   superlinear convergence). Do you have any explanation for this? 6) It might\n   be reasonable to add Cubic Newton and its accelerated variant to your\n   comparison.\n\nMinor remarks:\n\n1. The convergence rate of the new method should be $L D^3 / T^3$, not $L D^2 /\n   T^3$. There are multiple such typos throughout the paper, see, e.g., lines\n   78, 247, 255, etc.\n\n2. Line 78: Please clarify what the constant $L$ is.\n\n3. Line 81: It is not exactly true that the method is oblivious to the diameter\n   of the constraint set since the \"correct\" value of the parameter $\\\\gamma$\n   depends on the diameter. Please clarify this. The same applies to the\n   Abstract.\n\n4. Lines 97--102: You should assume that you work either in an abstract\n   $d$-dimensional Euclidean space $\\\\mathcal{V}$, or in $\\\\mathbb{R}^d$; there is\n   no point in mixing them up by stating that $\\\\mathcal{V} \\= \\\\mathbb{R}^d$.\n   Further, since you work with a smooth function $f$, instead of \"proper, lower\n   semi-continuous, ...\" and \"Lipschitz continuous selection ...\", you should\n   simply assume that $f$ is twice differentiable (over some open set containing\n   $\\\\mathcal{X}$). Finally, note that Assumption 2.1 is satisfied automatically\n   since $\\\\mathcal{X}$ is a compact set.\n\n5. Section 2: Please clarify that you use standard Euclidean and operator norms.\n\n6. Eq. (Taylor): I suggest removing it.\n\n7. Eq. (EG): There should be capital $X\\_t$ and $X\\_{t + 1/2}$.\n\n8. Eq. (5): Some constants ($L$ and $D$) are missing.\n\n9. Algorithm 1, line 2: The coefficient should be $\\\\frac{a\\_t b\\_t}{2 B\\_t}$. Also,\n   the definition of $B\\_t$ is missing.\n\n10. Eq. (8): I suggest denoting $\\\\| g(\\\\bar{X}\\_{s + 1 / 2}) -\n    \\\\tilde{F}(\\\\bar{X}\\_{s + 1 / 2}; \\\\tilde{X}\\_s) \\\\|$ somehow (e.g.,\n    $\\\\tilde{\\\\Delta}\\_s$), and then use $\\\\tilde{\\\\Delta}\\_s$ everywhere instead of\n    the long expression that appears in multiple places throughout the paper.\n\n11. Theorem 3.2: The definition of $D$ is missing.\n\n12. Theorem 3.3: There should be $\\\\bar{X}\\_{T + 1 / 2}$ instead of $\\\\bar{X}\\_T$.\n\n13. Proposition 3.1: The parentheses are missing after the sum sign. Also, it\n    might be reasonable to remove \"Let $\\\\{ X\\_{t + 1 / 2} \\\\}\\_{t \\= 1}^T$ be\n    generated by Algorithm 1\", or rephrase it.\n\n14. Eq. (11): In the first line, there should be no \"$2$\" in the denominator.\n\n15. Display between lines 617 and 618: Please simplify it, as everything\n    trivially follows from the fact that $\\\\mathbb{E}[ g(\\\\bar{X}\\_{t + 1 / 2}) |\n    X\\_{t + 1 / 2} ] \\= \\\\nabla f(\\\\bar{X}\\_{t + 1 / 2})$.\n\n16. Lemma F.1: There should be $\\\\alpha\\_T$ instead of $\\\\alpha\\_t$. Also, one\n    should additionally assume that $\\\\alpha\\_1 > 0$.\n\n17. Display between lines 732 and 733: Expectation sign is missing in the\n    right-hand side.\n\n18. Display between lines 735 and 736: It would be better to remove the negative\n    signs and rewrite everything in terms of positive quantities (reversing the\n    inequalities). Also, please specify what $c$ is.\n\n19. Eq. (20): There should be $-\\\\delta\\_t$ instead of $\\\\delta\\_t$.\n\n20. Display between lines 747 and 748: I suggest introducing some notation for\n    $\\\\min\\\\{ \\\\| \\\\tilde{\\\\nabla}\\_t \\\\|, \\\\| \\\\nabla\\_t \\\\| \\\\}$ to avoid repeating the\n    same long expression everywhere.\n\n21. Display between lines 756 and 757: Please clarify why $\\\\sqrt{1 + \\\\sum\\_{t \\=\n    1}^T a\\_t^2 \\\\min \\\\ldots} \\\\leq \\\\gamma^{-1} \\\\sum\\_{t \\= 1}^T \\\\lambda\\_{t + 1}\n    a\\_t^2 \\\\min \\\\ldots$.\n\n22. Display between lines 759 and 760: Can we guarantee that $T\\_0$ is always\n    finite? If not, please add some comments about the case $T\\_0 \\= \\\\infty$.\n\n23. Display between lines 769 and 770: Expectation sign is missing.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work presents a new approach for constructing accelerated second-order\nmethods. An unusual feature of this approach is that it does not rely on any\n\"line search\" and can be easily extended to the case of the stochastic oracle.\nDespite many similarities to the already existing acceleration techniques, the\nconstruction, proposed in this work, definitely has a few novel elements.\nOverall, I find this paper very interesting and believe that the ideas,\npresented there, could be useful in a broader context.\n\nThe main drawback of the new method is that it works only with a bounded\nfeasible set. In particular, it cannot be directly applied for unconstrained\noptimization problems. Also, the convergence rate $O(L D^3 / T^3)$ of the new\nmethod depends on the diameter $D$ of the feasible set, in contrast to the $O(L\nD\\_0^3 / T^3)$ rate of the standard Accelerated Cubic Newton Method which depends\non the distance $D\\_0$ from the initial point to the solution ($L$ is the\nLipschitz constant of the second derivative). Nevertheless, in my opinion, this\ndrawback is not really significant and can be addressed in future work.\n\nPlease see my detailed remarks in the next section. I will be happy to increase my score further if the authors address these remarks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept