A consistently adaptive trust-region method
Authors: Fadi Hamad
Oliver Hinder
Venue: NeurIPS 2022 Accept (2022)
Keywords: trust-region method
adaptive
optimization

Abstract: Adaptive trust-region methods attempt to maintain strong convergence guarantees without depending on conservative estimates of problem properties such as Lipschitz constants. However, on close inspection, one can show existing adaptive trust-region methods have theoretical guarantees with severely suboptimal dependence on problem properties such as the Lipschitz constant of the Hessian. For example, TRACE developed by Curtis et al. obtains a $O(\Delta_f L^{3/2} \epsilon^{-3/2}) + \tilde{O}(1)$ iteration bound where $L$ is the Lipschitz constant of the Hessian. Compared with the optimal $O(\Delta_f L^{1/2} \epsilon^{-3/2})$ bound this is suboptimal with respect to $L$. We present the first adaptive trust-region method which circumvents this issue and requires at most $O( \Delta_f L^{1/2}  \epsilon^{-3/2}) + \tilde{O}(1)$ iterations to find an $\epsilon$-approximate stationary point, matching the optimal iteration bound up to an additive logarithmic term. Our method is a simple variant of a classic trust-region method and in our experiments performs competitively with both ARC and a classical trust-region method.

A consistently adaptive trust-region method
Fadi Hamad
Oliver Hinder
Department Industrial Engineering University of Pittsburgh Pittsburgh, PA 15261 fah330pitt. edu
Department of Industrial Engineering University of Pittsburgh Pittsburgh, PA 15261 ohinder@pitt. edu
Abstract
Adaptive trust-region methods attempt to maintain strong convergence guarantees without depending on conservative estimates of problem properties such as Lip- schitz constants. However, on close inspection, one show existing adaptive trust-region methods have theoretical guarantees with severely suboptimal depen- dence problem properties such as the Lipschitz constant of the Hessian. For example, TRACE developed by Curtis et al. obtains a -3/22-33/2 eration bound where L is the Lipschitz constant of the Hessian. Compared with the optimal , - bound this is suboptimal with respect L. We present the first adaptive trust-region method which circumvents this issue and requires at most O 1, -/22) Ô(1) iterations to find an e-approximate stationary point, matching the optimal iteration bound up to an additive logarithmic term. Our method is simple variant of classic trust-region method and in our experiments performs competitively with both ARC and classical trust-region method.
3/2) + Ó(1) it-
Introduction
Second-order methods are known to quickly and accurately solve sparse nonconvex optimization problems that, for example, arise in optimal control [1], truss design [2], AC optimal power flow [3], and PDE constrained optimization [4]. Recently, there has also been large push to extend second-order methods tackle machine learning problems by coupling them with carefully designed subproblem solvers [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16. 17, 18, 19].
Much of the carly theory for second-order methods focused and (eventual) global convergence [20, 21, 22, 23, 24, 25, 26. 27, 28, 29]. These proofs of global convergence, unsatisfactorily, rested showing each iteration second-order methods reduced the function value almost as much as gradient descent [22, Theorem 4.5] [30, Theorem 3.2.]. this is despite the fact that practice second-order methods require far fewer iterations. In 2006, Nesterov and Polyak [31] partially resolved this inconsistency by introducing a new second-order method, cubic regularized Newton's method (CRN). Their method be used to find stationary points of multivariate and possibly nonconvex functions ʃ R + R. Their convergence results assumes the optimality gap
showing fast local convergence
A = f(z1) inf f(x) FER
finite and that the Hessian of is L-Lipschitz:
f(x) v² L| Va, o' R
(1)
where || is the spectral norm for matricies and the Euclidean norm for vectors. If L is known they guarantee their algorithm terminates with an e-approximate stationary point:
\
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

after at most
iterations. For sufficiently small 6, this improves on the classic guarantee that gradient descent terminates after at most ((A,Se=2) iterations for S-smooth functions, thereby partially resolving this inconsistency between theory and practice. Bound (2) is also known be the best possible for second-order methods [32].
However, CRN only achieves (2) if the Lipschitz constant of the Hessian is known. In practice, we rarely know the Lipschitz constant the Hessian, and if we do is likely to conservative estimate. With this in mind, many authors have developed practical algorithms that achieve the convergence guarantees of CRN without needing to know the Lipschitz constant the Hessian. We list these adaptive second-order methods in Table along with their worst-case iteration bounds.
Despite the fact that these algorithms match the e-dependence of (2), the majority of them are suboptimal due to the dependency on the Lipschitz constant T.. For example, only our method and [33, 34] are optimal in terms of L scaling. Whereas [35] is suboptimal as the bound scales proportional to L instead of //2 Moreover, all the trust-region methods have suboptimal L scaling. In particular, inspection of these bounds shows scaling with respect L of 1,3/2 for [36] and 2 for [37] instead of the optimal scaling of 1/2/2
ideal algorithm wouldn't 't ineur this cost for adaptivity. This motivates the following definition.
Definition A method is consistently adaptive a problem class without knowing problem parameters, achieves the same worst-case complexity bound as one obtains if problem parameters known, up problem-independent constant-factor and additive polylogarithmic term.
Clearly, based on our above discussion there does not exist consistently adaptive trust-region methods. Indeed, despite the extensive literature trust-region methods [9, 10, 22, 25, 27, 36, 38, 39, 40, 41] and their worst-case iterations bounds [36, 37, 42], none of these methods are consistently adaptive. As we mentioned earlier and according Table 1, [33, 34] are cubic regularization based methods which scale optimally with respect to the problem parameters. However, they are not quite consistently adaptive because dn appears outside the additive polylogarithmie term.
Table 1: Adaptive second-order methods along with their worst-case bounds on the number of gradient, function and Hessian evaluations. Omin (0) is the smallest regularization parameter used by ARC [35]. do e (0, oo) is the initial regularization parameter for cubic regularized methods.
Algorithm
type
worst-case iterations bound
ARC [35]
cubic regularized
1 g- - 3/2 A Ayo 1/2 (322) min
min
Nesterov et al. [33, Eq. 5.13 and 5.14) 2
cubic regularized
O(A, max 1/2
0(1)
ARp [34, Section 4.1]
cubic regularized
O(A, max L, 1/2 1/2 3/2) Ó(1)
TRACE [36, Section 3.2]
trust-region
O 1 3/22) a
Toint et al. [37, Section 2.2] Our method
trust-region
Ô (Ay max (1,1422))-377
trust-region
0 L/2 3/2 O(1)

---

Our contributions:
1. We present the first consistently adaptive trust-region method for finding stationary points nonconvex functions with L-Lipschitz Hessians and bounded optimality gap. In particular, we prove our method finds an e-approximate stationary point after most ,AA + Ó(1) iterations.
2. We show our trust-region method has quadratic convergence when enters a region around point satisfying the second-orde sufficient conditions for local optimality.
3. Our method appears promising in experiments. We test our method on the CUTEst test set [43] against other methods including ARC and a classic trust-region method. These tests show how competitive we are against the other methods in term of total number of required iterations until convergence.
Paper outline The paper is structured as follows. Section 2 presents our trust-region method and contrasts it with existing trust-region methods. Section 3 presents our main result: convergence bound for finding c-approximate stationary points that is consistently adaptive to problems with Lipschitz continuous Hessian. Section shows quadratic convergence of the method. Section 5 discusses the experimental results.
Notation Let N be the set of natural numbers (starting from one), be the identity matrix, and R the set of real numbers. Throughout this paper we assume that N and f RR + R is bounded below and wice-diffeerentiabl.. We define f. == inføeR" f(r) and D, == f(x1) f..
2 Our trust-region method
2.1 Trust-region subproblems
As is standard for trust-region methods [22] each iteration & of our algorithm we build second- order Taylor series approximation at the current iterate Tx:
(& d' ( ff(x))
1
(3)
and minimize that approximation over a ball with radius rk > 0:
min (d) s.t. ||d]| S тк
deRt
to generate a search direction d,. One important practical question is given candidate search
direction dg, how can we verify that it solves (4). For this one can use the following well-known Fact.
Fact 1 (Theorem 4.1 [44]). The direction de exactly solves (4) if and only there exists 8, [0, oo) such that:
V Ma (x(dk) + d4 =0
(5a)
6RT S 5r
(5b)
|| rk
(5c)
V f(x)) + 6
(5d)
'Obtaining this bound does require carefully inspection of Cartis. Gould and Toint [35] (who highlighted only on the e-dependence of their bound). For simplicity of discussion we assume the ARC subproblems are solved exactly (i.c., C' = 0, Ke 0), and that the initial regularization parameter satisfies da = O(L + Fmin) (the bound only gets worse otherwise). We also consider only the bound on the number of Hessian evaluations, inclusion of the unsuccessful iterations (where cubic regularized subproblems are still solved) makes this bound even worse. Finally, we ignore groblen-independent parameters Y),, 12, 73 and 771-
"Since by our assumption the function has L-Lipschitz Hessian, only consider the when the Hölder exponent 1. Note also that the algorithm description [33, Eq. 5.12]. requires that the initial regularization
parameter do (Ho using their notation) satisfies Ho E (0, (v)] where (v) is defined [33, Eq. 2. Technically this condition is not verifiable as Hv) is unknown in practice. However, one can readily modify [33] by redefining H to be the maximum of Ho and the RHS of [33, Eq. 2.1] to remove the requirement that Ha E (0, H (v)]. This gives the bound stated in Table 1.
We only consider the case for the cubic regularized model when p = and r = p + 1 3. Also, since by our assumption the function f has L-Lipschitz Hessian, we only consider the case when the Hölder exponent
82
3

---

which solves (4).
In practice, it not possible to exactly solve the trust-region subproblem defined in (4), instead we only require that the trust-region subproblem is approximately solved. For our method, it will suffice find direction dę satisfying:
(M + d 1 7/ V fx + dx)ll
(6a)
720RT I 6 6x||deel
(6b)
|dxll S rk
(6c)
M&(dk) S 73 δR [|d&
(6d)
where 6g denotes the solution for the above system and 7i [0, 12 E (1/w, 11, 7s E (0, l]. Setting "n = 0, = 1, 7/3 = represents the exact version of these conditions. As Lemma shows, exactly solving the trust-region subproblem gives solution the system (6). However, the converse it not true, an exact solution to (6) does not necessarily solve the trust-region subproblem. Nonetheless, these conditions are all need prove our results, and are easier verify than relaxation of (4) that includes a requirement like (5d) which needs a computationally expensive eigenvalue calculation.
Lemma 1. Any solution to (5) is solution (6) with " 0, 72 1, 73 1.
Proof. The only tricky part is proving (6d). However, this can be shown using standard arguments:
(x = z de [xrx ) + (=x du = _2 (v² f(xx) + 26 I)d S 6 ||d where the second equality uses (5a) and the inequality (5d).
2.2 Our trust-region method
An important component of a trust-region method is the decision for computing the radius Tk at each iteration. This choice is based on whether the observed function value reduction f(xx) - f(xx + de) comparable to the predicted reduction from the second-order Taylor series expansion Mg. In particular, given search direction da existing trust-region methods compute the ratio
f(x) - f(ax + de)
Pk
(dx)
and then increase FA if Pk 2 B or decrease Fı if Pk < , [22]. Unfortunately. while intuitive, this criteria is provably bad, in the sense that one can construct examples of functions with Lipschitz continuous Hessians where any trust-region method that uses this criteria will have convergence rate proportional to e [45, Section 3].
Instead of (7), introduce variant of this ratio by adding the term f(z + dx)ll | to the predicted reduction where e (0, oo) is a problem-inee -ndeenddneendnnttt hyperparameter (we use 0 = 0.1 in our implementation). This requires the algorithm to reduce the function value more if the gradient norm at the candidate solution # + dg. and search direction norm are big. In particular, we define new ratio as:
f(xx) - f(ax + dx) P = (d+) + f d ddl
(8)
Our trust-region method is presented in Algorithm 1. The algorithm includes some other minor modification of classic trust-region methods [22]: we accept all search directions that reduce the function value, and update the T using ||d&]] instead of ты (see [46, Equation 13.6.13] for a similar update rule). We recommend contrasting our algorithm with [36, Algorithm 1] which trust-region method with iteration bound proportional 3322 but more complex and not consistently adaptive.
For the remainder of this paper zy and de refer to the iterates of Algorithm 1.
3 Proof of full adaptivity on Lipschitz continuous functions
This section proves that our method consistently adaptive for finding approximate stationary points on functions with L-Lipschitz Hessians. The core idea behind our proof is to get a handle the size

---

Algorithm 1: Consistently Adaptive Trust Region Method (CAT)
Input requirements: ri E (0, 21 E R
Problem-independent parameter requirements: E (0, 8 e (0,1), E (1, 80
71 E [0, 1), 72 (1/w, 1), Ys (0, 1], (a(1-8) B) 71 1;
for & = 1,... Do do
Approximately solve the trust-region subproblem, iee, obtain dj that satisfies (6)
Fk + dx
[(x + dx) E ((x
Uk+1
Itk
otherwise
w wlldxll
iu 2 B otherwise
rk+1
||dell/w
of |d In particular, if we can bound | from below and Ds 2 3 then the I Vf + de))lllda |[ term guarantees that iteration i the function value is reduced by large amount relative to the gradient norm
V (Tx + dx]]l-
Lemma guarantees the norm of the gradient for the candidate solution .y + dg lower bounds the size of ||d&|] under certain conditions. Note this bound on the gradient, i.e., (11) holds without us needing to know the Lipschitz constant of the Hessian L. The proof of Lemma 2 appears in Section A. and heavily leverages Fact 2.
Fact 2 (Nesterov & Polyak 2006, Lemma [31]. If V is I-Liischiitz
f + d+)ll < V Mx (d+)l + _ ||dy 1|
(9)
L f(xx dx) S f(xx) + Ma(as)) |d 1s.
(10)
Lemma 2. Suppose 22 f is I-L.ipschit. If |||dd < <2Tk or Pa S B then
V (Tr dx)ll ci Llddal
(11)
where ej > 0 is problem-indeeendeeee constant:
5 5 33
1
max
6(77(1 - (3) 2(1 m)
For the remainder of this section we will find the following quantities useful,
de = 72w
C
1//2
d = 2w A
30
As will show shortly in Lemma 4, after short warm up period de and d, represent lower and upper bound on [|d]]| (i.e., de < ||dd|]| S d,) as long as | + d4) 2 6. But before presenting and proving Lemma we develop Lemma 3 which is stepping stone proving Lemma 4. Lemma shows that if [d& || is almost above de then the trust-region radius will shrink, and if [|d&] || is almost
below de then the trust-region radius will grow (recall from Algorithm that E (1, oo)).
Lemma 3. Suppose 2 is L-Lipschitz. Let oo) and V + dx)ll 2 e then
1. If [dd|] de/w then ||dell/w- Tk+1-
2. If |dx]]| < wh, de then 72Tk S ||dx|| S Tb w wildk|| = Tk+1-
Proof. Proof for 1. We have
A,
2 2 (zx) f((++1)
||d]|| de/w
(12)
S0c
g0c
5

---

where the first equality uses the definition of de and the second inequality uses f(xx+1) 2
inf (x) and f(x1) 2 f(zx). Furthermore,
f(xx) - f(a + dx)
f(zx) f(2x+1)
{(ER) - -f(Ix+1) < B
Pu (da + 2 V [Tx + dx) ( ||
I (Tx + dx) de)]lldeel
0e 0el|dkll
2
where the first inequality follows from (Ma(da)) > and f(x++1) I f(xx + dx), the second
inequality follows from the fact that V + dx) || 2 and the third inequality uses (12). By inspection of Algorithm
Pu < B, then |// = 1--1-
Proof for 2. We will prove the result by contrapositive. In particular, suppose that ((27% S |d S
T&) or |d ||w # rk-1- Let us consider these two cases. If (12rk S ||dx S rs)) then as || S rk
we have 727h > ||&||-- If |dd * rk+1 then by inspection of Algorithm we have P S B.
Therefore, in both these cases the premise of Lemma 2 holds. Now, by | f + de)ll 2 and
Lemma 2 we get
V f"* dx)ll c1 T/|d211
which implies ||d]|| 2 G 1/2 1-1/222 = 7/2
----dd c, 1/ 1-12 = 7/ wwe..
Now we show that the norm of the direction dg, after some finite iteration &s. will be bounded below and above by de and de respectively. For that we first define:
K, = min E N V/ fix + dx)ll S (oo}}
as the first iteration for which V (zx d S c, and we also define:
k. := min {1: E N de S || S {K - 1}}
as the first iteration for which de S ||dyl|| d. An illustration of Lemma 4 is given in Figure 1. In particular, after a certain warm up period the direction norms can no longer rise above de or below de. Broadly speaking, the idea behind the proof is that if |dd is above de /ww then at the next iteration ||d&|| || decreases and conversely if ||de|| is bellow dow72 -1 then at the next iteration must increase.
Lemma 4. Suppose V f is T-Lipschitz and let e E (0, oo). Ifd, S |d&lll S de then de S ||d, s de for all j E Ke) n N. Furthermore, b. S 1 + log (max (1, d./r1, rd/d.))
Proof. We begin by proving de S ||d&|| S de then de S ||d I de for j E [k, K.) n.. We assume that k- < Ke otherwise desired conclusion clearly holds. We split this proof into two claims.
Our first claim is that |d&ll < de implies ||4-=1|| S de. We split ||dg]| S d, into two subcases. If ||de| < d /w, then inspection of Algorithm 1 shows that [| S TA+1 < ||dı|lw S d. If d./w= I || d ll S d,, then Lemma 3.1 implies that ||dx+1ll S rk+11 S |dæll/w S de.
Our second claim is that d, < ||d&/| || implies de < ||d++I]l. We split de < ||da|l into three subcases. If [[dg+11 < 1, 1, then the contrapositive of Lemma 3.2 implies that [|dx+1| 2 de. If 7271+1 S ||dx+a|| S Tk++1 and de S ||d < 1/2 wwe. then de < r2wd. I 7/w/| d&el = 727k+1 S ||detall where * uses Lemma 3.2. If 727k+1 S ||d++]|| < r and down. I ||dell, then de S relldell S.
727k+1 S [[de+11| || where * is from the update rule for rk+1 in Algorithm 1.
By induction on the previous two claims we deduce if de S ||dull S de then de S ||d,|| S de for j E [k, K.)NK, N.
Next, we prove that if
2 + 10% (de/ri)
then ||d+|| > de. If de < ||رل|| for some j < k. then the result holds because as we already
established de S |d = de S ||dx+1l|. On the other hand, if ||d, < de for all j S k. then Lemma 3.2 implies that ry+1 = w||d,|| 2 w72r, which by induction gives ||dx|| 2 (w72)* - 2
(wry)) JoR (dr/r1)), = d..
Finally, we prove that if
2 + (rg
then |dhll S de. If [|d, < de for some j < k. then the result holds because as we already established
||dx|| |I I de + ||db+1| || I d. On the other hand, if ||dz]| > de for all j < k then Lemma 3.1 implies

---

|| |
Maximum ||de & S k
de
de/w
| always decreases on next iteration above this line while
||dx always increases on next iteration below this line while
de
Minimum ||4 || for be S K.
k
Figure 1: An example of plausible sequence of iterates and the norms of their directions. Each red dot represents an iterate and its search direction norm. This illustrates Lemma
that ry+1 = ||d,ll/ I Ts/W which by induction gives ||dall S wl kol-ky, I w log (rs///))))) de.
Let
2, S K.}
which represents the set of iterations, before find an e-approximate stationary point, where the function value is reduced a large amount compared with our target reduction, i.e., Åu 2 3. Lemma shows that there threshold The proof of Lemma 5 appears in Appendix A.2. Roughly, the idea of the proof is to use that, due our definition of Åk. when Pk 2 we always reduce the function value by at least 90 V fxxx + de [e]lll and ||de]] can be lower bounded by de using Lemma 4. As we cannot reduce the function value by a constant value indefinitely, we must eventually have || f(x + +dx)l S
finite number of these iterations until the gradient drops below the target
Lemma 5. Suppose 42 f is L- L-Lipschitz and E (0, oo) then (Pel <
de +
2we/ 39
+ +1.
e-a/a
With Lemma 5 in hand we provided bound on the length of the warm up period, & (Lemma 4) and on the number of points with A 2 B. Therefore, the only obstacle is to bound the number of points with ~k B. However, on these iterations we always decrease the radius by at least w (see update rules Algorithm 1), and therefore as ||da is bounded below by de, there must be iterations where increase the radius rx. which by definition of Algorithm only occurs if B > Pu. Consequently, the number of iterations where 3 < ir can be bounded by the number of iterations where 2 Pa plus a Ö(1) term. This is the crux of the proof of Theorem which appears Section A.3.
ready to prove main result, Theorem 1. We have already
Theorem 1. Suppose that V2 f is L--ippshittz and f is bounded below with D f(x)) - Sw, then for all (0, 20) there exists iteration with V f(r dx)ll S and
0 D + logg
TIE Ds
+1
+1
Lar
where O(-) hides problem-indepenee constant factors and rı is the initial trust-region radius.
One drawback of Theorem 1 is that it only bounds the number of iterations to find first-order stationary point. Many second-order methods the literature show convergence to points satisfying the second-order optimality conditions [47, 35, 36, 18). Of course, these methods are not consistently adaptive. Therefore, the future, it would be interesting to develop method that provides consistently adaptive convergence guarantee for finding second-order stationary points.
7

---

4 Quadratic convergence when sufficient conditions for local optimality hold
Theorem 2. Suppose f is twice differentiable and for some I. E R the second-order sufficient conditions for local optimality hold (x.) = 0 and V² [(x==) > 0). Under these conditions there
exists a neighhorhood N around I,, and constant > 0 such that x; E N then there exist Fgg N
such that for all lo 2 k we have || - x- 1 c|| ==11² - 2 =| - x-ll-
The proof of Theorem appears in Section B. It is a little tricker than typical quadratic convergence proofs for trust-region methods because in our method we have lim 73 + O whereas classical trust-region methods have ты bounded away from zero [22. Proof of Theorem 4.14]. Fortunately, one can show that asymptotically т5: 2 w|| x. so the decaying radius does not interfere with quadratic convergence. In particular, the crux of proving Theorem 2 is proving the premise of Lemma 6 (as the conclusion of Lemma is rk 2 w w||ar I.l)). For this Lemma we define diam(X) X) := S'X | z'1l-
Lemma Let N be bounded set such that for all a& E N we have Ib+1 E N, Pk 2 B, and min(727k: | - I. [1} S ||dx |l S wYz = x. ||- Suppose there exists 2t E N and let i be the smallest index with x; E N, then r'k 2 w|| x. for all ks + i log yog
/diam(N)
[1d.
Proof. Let k 2 i. By induction zy E N. By P 2 and inspection of Algorithm I we have Tk+1
wl|dell- Suppose that [|dxll 2 72 for all i S k S i f then diam(N) 2 ||dx+1 || 2 72 = I2w|lde //w/||dd]] Rearranging gives l < log
[d.ll (a.1
(diam(N) ). Next observe that if ||d&]l |l < 722k
then ||dx+]|| S wy2 [| Tx+1 æ. S wyz ||d&|l = / = Tk+1- By induction ||d&|l < 72'k
for all k > L. Finally, observe that if ||d& 727h then rkt1 w||dk|| 2 w w|| x=1l-
5 Experimental results
We test our algorithm on learning linear dynamical systems [48], matrix completion [49], and the CUTEst test set [50]. Appendix D contains the complete set of results from our experiments. Our method implemented in an open-source Julia module available at atttps://iite Madihamad94/AA-
com/
NeurIPS. -CA-- approach to solve the trust-region subproblems (i.e., satisfy (6)). We perform our experiments using Julia 1.6 on Linux virtual machine that has 8 CPUs and 16 GB RAM. The CAT code repository provides instructions for reproducing the experiments and detailed tables of results.
The implementation uses a factorization and eigendecomposition
For these experiments, the selection of the parameters (unless otherwise specified) is as follow: r1 = 1.0, B = 0.1, 8 0.1, w 8.0, 7 0.0, 722 0.8, and 7/ 1.0. When implementing Algorithm 1 with some target tolerance e, we immediately terminate when we observe a point Iς with f + d S This also includes the case when we check the inner termination criteria for the trust-region subproblem. The full details of the implementation are described in Appendix C.
5.1 Learning linear dynamical systems
We test our method learning linear dynamical systems [48] to see how efficient our method compared to a trust-region solver. We synthetically generate an example with noise both in the observations and also the evolution of the system, and then recover the parameters using maximum likelihood estimation. Details are provided in Appendix D.
On this problem we compare our algorithm with Newton trust-region method that is available through the Optim.jl package [51]. The comparisons are summarized Table 2.
5.2 Matrix completion
We also demonstrate the effectiveness of our algorithm against a trust-region solver on the matrix completion problem. The matrix completion formulation can be written as the regularized squared error function of SVD model [49, Equation 10J. For our experiment, we use the public data set of Ausgrid, but we only use the data from a single substation. Details are provided in Appendix D.2.
Again we compare our algorithm with Newton trust-region method [51]. The comparison are summarized in Table 3.
8

---

Table Geometric mean for total number iterations, and evaluations of the function and gradient. solver on 60 randomly generated instances with c = 10 termination tolerance. Failures counted as the maximum number of iterations (10000) when computing the geometric mean.
#iter
#function #gradient
Newton trust-region [51]
480.1
482.3
482.3
Our method 95% CI for ratio
308.1
309.6
309.6
[1.24, 1.95]
[1.24, 1.94]
[1.24, 1.94]
Table 3: Geometrie mean for total number of iterations per solver on 10 instances by randomly generating the sampled measurements from the matrix D using data from Ausgrid with 10 termination tolerance. Failures counted as the maximum number of iterations (1000) when computing the geometric mean.
#iter
Newton trust-region [51]
1000
Our method
216.4
5.3 Results on CUTEst test set
The CUTEst test set [50] a standard test set for nonlinear optimization algorithms. run the bench- marks we use https://githu:: httbbb/ooo/uuaaaaaeeeeeeeeee hat.aaaamootttppiiimeerr///SESS j1 (the License can be found at https: https://github: com/ buliissmoottotiiiiieeeee/rrrerre jl/bll/ ht//bobb/mann/LICESSS
md). We will be comparing with the results for ARC reported in [52, Table 1J. As the benchmark CUTEst that we used has changed since [52] was written we select only the problems CUTEst that remain the same (some of the problem sizes have changed). This gives 67 instances. A table with our full results can be found the results/CUTEst subdirectory in the git repository for this paper. Catris et.al [52] report the results for three different implementations of their ARC algorithm. We limit our comparison to the ARC g-rule algorithm since it performs better than the other ARC approaches. We also run the Newton trust-region method from the Optim.jl package [51].
Our algorithm stopped as soon V fxx + dæ)ll is smaller than 10-5, 5, For the Newton trust-region method [51] we also used as stopping criteria value of 10 for the gradient termination tolerance. We used 10000 as an iteration limit and any run exceeding this considered a failure. This choice of parameters is to be consistent with [52].
As we can see from Table 4, our algorithm offers significant promise. requiring similar function evaluations (and therefore subproblem solves) to converge than the Newton trust-region of [51] and ARC, although the number of gradient evaluations is slightly higher than ARC. In addition, the comparison between these algorithms in term of total number of iterations and total number of gradient evaluations is summarized in Figure
5.4 Convergence of our method with different theta values
To demonstrate the role of the additional ||d V f(* dx)il term we run experiments with different values. particular, we contrast our default value of = 0.1 with 0 = which corresponds not adding the f(= + d term Ωa (recall the discussion in Section 2.2).
Table 4: Number of failures, geometric mean for total number of iterations and function and gradient evaluations per solver on unconstrained instance from the CUTEst benchmark instances. Failures counted as the maximum number of iterations (10000) when computing the geometric mean.
#failures #iter #function #gradient
Our method
3
41.5
44,4
44.4
ARC with the g-rule [52] Newton trust-region [51]
38.1
38.1
26.6
4
44.5
47.2
47.2

---

Fractio of problemm solves
Fractan of probleme SOO solieed
Cerrmiieed Neetto regitn
gracient
Figure 2: Fraction of problems solved on the CUTEst benchmark.
Our mattrd 0.21
0.
Gradien: rorm
of
0.4
Da redied ocloull 9.11
10
10' Tatal number of iterations
1d'
122
117
38'
15
Total number of iterations
(a) Fraction of problems solved versus total number (b) Gradient norm versus total number of iterations on the example [45] with r1
of iterations CUTEst test
1.5
Figure 3: Performance of our algorithm based on different values.
In Figure 3a rerun the CUTEst test set (as per Section 5.3) and compare these two options. One can see the algorithm performs similarly with either 0 = 0 or 0 = 0.1.
In Figure 3b we test the hard example from [45] which is designed to exhibit the poor worst-case complexity of trust-region methods (i.e., a convergence rate proportional to e= if the initial radius r1 chosen sufficiently large (to achieve this set 71 1.5). We this example with 10 One can see that while for the first zs 10 iterations the methods follow identical trajectories, thereafter 0 0.1 rapidly finds stationary point whereas 0 0.0 requires orders of magnitude more iterations to terminate. This crystallizes the importance of 0 in circumventing the worst-case -2 convergence rate of trust-region methods.
Acknowledgments and Disclosure of Funding
The authors were supported by the Pitt Momentum Funds. The authors would like to thank Coralia Cartis and Nicholas Gould for their helpful feedback on a draft of this paper. The authors would also like to thank Xiaoyi Qu for finding errors in the proof of an early draft of the paper and for helpful discussions.
10

---

References
[1] John T Betts. Practical methods for optimal control and estimation using nonlinear program- ming. SIAM, 2010.
[2] Klaus Schitkkoski, Christian Zillober, and Rainer Zotemantel. Numerical comparison of nonlinear programming algorithms for structural optimization. Structural Optimization, 7(1):1 19, 1994.
[3] Stephen Frank, Steffen Rebennack, et al. A primer on optimal power flow: Theory, formulation, and practical examples. Colorado School of Mines, Tech. Rep, 2012.
[4] Lorenz Biegler, Omar Ghattas, Matthias Heinkenschloss, and Bart van Bloemen Waanders. Large-scale PDE-constrained optimization: an introduction. In Large-Scale "DE-Constraiied Optimization, pages 3-13. Springer, 2003.
[5] Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization. In International Conference on Machine Learning, pages 1895-1904. PMLR, 2017.
[6] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularized Newton methods. In International Conference on Machine Learning, pages 5990-5999. PMLR, 2018.
[7] Ching-pei Lee, Cong Han Lim, and Stephen Wright. A distributed quasi-Newton algorithm for empirical risk minimization with nonsmooth regularization. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1646-1655, 2018.
[8] Frank E Curtis, Michael J O' O'Neill, and Daniel P Robinson. Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization. arXiv preprint arXiv:21 14799, 2021.
(9] Frank E Curtis and Rui Shi. A fully stochastic second-order trust region method. Optimization Methods and Software, pages 1-34, 2020.
[10] Frank E Curtis, Katya Scheinberg, and Rui Shi. A stochastic trust region algorithm based on careful step normalization. Informs Journal on Optimization, 1(3):200-220, 2019.
[11] Vipul Gupta, Avishek Ghosh, Michat Dereziński, Rajiv Khanna, Kannan Ramchandran, and Michael W Mahoney. LocalNewton: Reducing communication rounds for distributed learning. In Uncertainty in Artificial Intelligence, pages 632-642. PMLR, 2021.
[12] Peng Xu, Fred Roosta, and Michael W Mahoney. Newton-type methods for non-convex optimization under inexact Hessian information. Mathematical Programming, 184(1):35770, 2020.
[13] Chih-Hao Fang. Sudhir B Kylasa, Fred Roosta, Michael W Mahoney, and Ananth Grama. Newton-ADMM: A distributed GPU-accelerated optimizer for multiclass classification prob- lems. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-12. IEEE, 2020.
[14] Shusen Wang. Fred Roosta, Peng Xu, and Michael W Mahoney. Giant: Globally improved approximate Newton method for distributed optimization. Advances Neural Information Processing Systems, 31, 2018.
[15] Sen Na, Michal Derezinski, and Michael W Mahoney, Hessian averaging in stochastic Newton methods achieves superlinear convergence. arXiv preprint arXiv:2204.09266 2022.
[16] Peng Xu, Jiyan Yang, Fred Roosta, Christopher Ré, and Michael W Mahoney. Sub-sampled Newton methods with non-uniform sampling. Advances in Neural Information Processing Systems, 29, 2016.
[17] Rixon Crane and Fred Roosta. DINO: Distributed Newton-type optimization method. In International Conference Machine Learning, pages 2174-2184, PMLR, 2020.

---

[18] Junyu Zhang, Lin Xiao, and Shuzhong Zhang. Adaptive stochastic variance reduction for subsampled Newton method with cubic regularization. INFORMS Journal on Optimization. 4(1):45-64, 2022.
[19] Dmitry Kovalev, Konstantin Mishchenko, and Peter Richtárik. Stochastic Newton and cubic Newton methods with simple local linear- quearart rates. arXiv preprint 2019.
[20] Philip E Gill and Walter Murray. Newton-type methods for unconstrained and linearly con- strained optimization. Mathematical Programming, 7(1):31 1974.
[21] Jorge Moré and Danny C Sorensen. On the use of directions of negative curvature in modified Newton method. Mathematical Programming, 16(1):1-20, 1979.
[22] Danny Sorensen. Newton's method with a model trust region modification. SIAM Journal on Numerical Analysis, 19(2):409 426, 1982.
[23] Stefan Ulbrich. On the superlinear local convergence of filter-SQP method. Mathernatical Programming, 100(1):217-245, 2004.
[24] Luís N Vicente and Stephen Wright. Local convergence of primal-dual method for degenerate nonlinear programming. Computational Optimization and Applications, 22(3):311-333 2002.
[25] Richard H Byrd, Jean Charles Gilbert, and Jorge Nocedal. A trust region method based on interior point techniques for nonlinear programming. Mathematical Programming, 89(1):149- 185, 2000.
[26] Lifeng Chen and Donald Goldfarb. Interior-point (2-penalty methods for nonlinear programming with strong global convergence properties. Mathematical Programming, 108(():1-36, 2006.
[27] Andrew Conn, Nicholas IM Gould, Dominique Orban, and Philippe L. Toint. primal-dual trust-region algorithm for non-convex nonlinear programming. Mathematical programming, 87(2):215-249, 2000.
[28] Nicholas IM Gould, Dominique Orban, and Philippe I. Toint, An interior-point Ex-penalty method for nonlinear optimization. Citeseer, 2002.
[29] Andreas Wächter and Lorenz Biegler. Line search filter methods for nonlinear programming: Motivation and global convergence. SIAM Journal on Optimization, 16(1):1-31, 2005.
[30] Stephen Wright and Jorge Nocedal. Numerical optimization. Springer Science and Media, 2006.
[31] Yurii Nesterov and Boris Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
[32] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 2020.
[33] Geovani Nunes Grapiglia and Yu Nesterov. Regularized Newton methods for minimizing functions with Hölder continuous Hessians. SIAM Journal on Optimization, 27(1):478-508 2017.
[34] Coralia Cartis, Nick Gould, and Philippe Toint. Universal regularization methods: varying the power, the smoothness and the accuracy. SIAM Journal on Optimization, 29(1):995-615, 2019.
[35] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. part ii: worst-case function-and derivative-evaluation complexity. Mathematical programming, 130(2):295-319, 2011.
[36] Frank E Curtis, Daniel Robinson, and Mohammadreza Samadi. A trust region algorithm with worst-case iteration complexity of ((e (3/2) for nonconvex optimization. Mathematical Programming, 162(1-2):1-32, 2017.
12

---

[37] Frank E Curtis, Daniel P Robinson, Clément W Royer, and Stephen J Wright. Trust-region Newton-cg with strong second-order complexity guarantees for nonconvex optimization. SIAM Journal on Optimization, 31(1):518-555 2021.
[38] Andrew R Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.
[39] MJD Powell. On the global convergence of trust region algorithms for unconstrained minimiza- tion. Mathematical Programming, 29(3):297-303, 1984.
[40] Richard G Carter. On the global convergence of trust region algorithms using inexact gradient information. SIAM Journal on Numerical Analysis, 28( 28(1):251-265 1991.
[41] Michael JD Powell. On trust region methods for unconstrained minimization without derivatives. Mathematical progrumming, 97(3):605-623, 2003.
[42] Frank E Curtis, Zachary Lubberts, and Daniel Robinson. Concise complexity analyses for trust region methods. Optimization Letters, 1213):11131172,, 2018.
[43] Nicholas IM Gould, Dominique Orban, and Philippe L Toint. CUTEst: a constrained and uncon- strained testing environment with safe threads for mathematical optimization. Computational optimization and applications, 5055)544--557, 2015.
[44] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
[45] Coralia Cartis, Nicholas IM Gould, and Ph L Toint. On the complexity of steepest descent, New- ton's 's and regularized Newton's 's methods for nonconvex unconstrained optimization problems. SIAM journal on optimization, 2036):2833 2010.
[46] Wenyu Sun and Ya-Xis Ya-ni Yuan. Optimization theory and methods: nonlinear programming, volume 1. Springer Science & Business Media, 2006.
[47] Ernesto Birgin and José Mario Martínez. The use of quadratic regularization with a cubic descent condition for unconstrained optimization. SIAM Journal Optimization, 27(2): 1049 1074, 2017.
[48] Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. arXiv preprint arXiv:1609.05193 2016.
[49] Chijie Zhuang, Jianwei An, Zhaoqiang Liu, and Rong Zeng. Power load data completion method considering low rank property. CSEE Journal of Power and Energy Systems, 2020.
[50] D. Orban, A. Siqueira, and contributors. CUTEst,jl: Julia's CUTEst interface. https: //githut com/ wttiiaammottppiiiiieee/////ssss
October 2020.
[51] Patrick Kofod Mogensen and Asbjøm Nilsen Riseth. Optim: A mathematical optimization package for julia. Journal of Open Source Software, 3(24), 2018.
[52] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization, part motivation, convergence and numerical results. Mathematical Programming, 127(2))245-295, 2011.
[53] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and trends in machine learning, 2015.
[54] Yehuda Koren. Factorization meets the neighborhood: multifaceted collaborative filtering model. Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 426 2008
13

---

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] The comparisons with other
algorithms show the limitations of work.
(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]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? (Yes) See Sections and 4
(b) Did you include complete proofs of all theoretical results? [Yes] See Sections and
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] Code and instructions reproduce the results are attached in the supplementary materials.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use CUTEst.jl and Optim.jl. For both we cite the creators.
(b) Did you mention the license of the assets? [Yes] See Section 5.3 and Appendix D.I.
(c) Did you include any new assets either the supplemental material or as URL? [Yes] Our code is attached in the supplementary materials.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "Jgbzf0coQAc", "reviewer": "Reviewer_ctCf", "summary": "This paper proposes a new adaptive variant of the classic trust region method, named FLAT. The proposed scheme preserves the strong convergence guarantee without requiring the knowledge of problem dependent constants like the Lipschitz constant. To achieve a first order stationary point, when compared with previous adaptive second order methods, FLAT enjoys a better depends on the Lipschitz constant and removes the dependence on a regularization parameter which potentially makes the previous guarantees vacuous. ", "questions": "It would be great if the authors can comment on the intuition of the newly constructed adaptive rule in Eq. (9). It seems that the additional term $||\\nabla f(x_k + d_k)||\\cdot||d_k||$ is specifically tailored to quickly achieve a first order stationary point. Is this the reason why the second order guarantee of FLAT is absent? Is it possible to revise the adaptive rule to also include the second order information in order to establish the second order guarantee?", "limitations": "There is no potential negative societal impact.\n\nAs a second order method, the proposed method lacks the guarantee of converging to the second order stationary point. This drawback is acknowledged by the authors as well.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper is well written and the major contribution of this work is well articulated: The proposed FLAT method, as an adaptive method, is able to achieve the same dependence on key parameters $(L, \\epsilon)$ as methods that have the exact information of the Lipschitz constant of the Hessian. Moreover, it removes the dependence on $1/\\sigma_\\min$ which is a potentially unbounded quantity present in previous approaches.\n\nWeaknesses:\n\nThe weakness of this work is also pretty clear: As a second order method, it lacks the guarantee of converging to the second order stationary point which is the key advantage when compared against the significantly more efficient first order method. This drawback is acknowledged by the authors as well.\n\nAlso, the experiments in Figure 2. seems to suggest that ARC has a better performance than FLAT, in all regards.", "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": "6iQuOr9HXK6", "reviewer": "Reviewer_mz9Z", "summary": "This manuscript studies adaptive trust-region methods and makes an argument that a large bulk of existing literature has an underlying dependency on an arbitrarily small parameter that renders available bounds vacuous. Moreover, dependency on problem parameters is suboptimal, e.g., the Lipschitz constants. The result lies in a modified threshold or ratio for the search direction. Quadratic convergence is shown when the iterates are sufficiently close to the optimal point. Some numerical results are provided.", "questions": "Can the developed techniques be applied to other adaptive methods beyond cubic regularization?\n\nIs there a function class for which the advantage of the proposed method is more evident than existing approaches? ", "limitations": "No potential negative societal impact", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- A weakness of existing methods is clearly identified and solved.\n- The originality lies in the definition of new search parameters.\n- The paper is well written and the result can serve as the base of future work in adaptive methods.\n- Some minimal numerical results are shown\n\nWeaknesses\n- At the core of the main argument is the suboptimality of existing approaches. However, the discussion and subsequent argument about it are relegated to a footnote, with very limited discussion.\n- Contributions 2 and 4 do not read as contributions.\n- The numerical section is very limited. The argument is that the provided method is better than the literature but the provided numerical evidence only explores some minimal examples rather than a comprehensive exposition of the computational advantages. ", "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": "2hZl3wQTahv", "reviewer": "Reviewer_VLHh", "summary": "The paper presents an adaptive trust method region whose complexity in terms of iterations matches that of non adaptive trust region methods. Crucially, this method has the right exponents in terms of the Lipschitz constant of the Hessian and the error. \n\nMore specifically, the introduction of a factor controlling the size of the direction and gradient in the update rule allows to not pay the regularisation parameter and to control more finely the different stages of the algorithm. \n\nThe proof of convergence towards and epsilon approximate stationary point is divided into different phases. \n\nAdditionally, a proof of quadratic convergence near a local optimum is given.\n\nExperiments to support the fact that this method compares with existing methods while having better theoretical guarantees are given, ", "questions": "\n- I believe in lemma 2, typo between $\\gamma_1$ and $\\gamma_2$ in the second term of the constant (first bound in the appendix). Also, another typo is that lemma 2 applies if the inequality is strict, while in the next proofs it is used for large inequality (but OK since in the algorithm the case distinction implies that the inequality is strict.\n- In the proof of lemma 5, I believe the third term should be an inequality and not an equality ? \n- Are there cases where ARC fails because of the sigma problem, where you could show that your method is better ? \n", "limitations": "Exposed by the authors.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "    * Originality:\n\nThe method is new in the introduction of the term controlling the size of $d_k$ in this context. \n\n\n\n    * Quality: I read most of the proofs and they are sound. Globally, I think the paper is very thorough. One thing missing from the main paper is perhaps how to get the trust region solution to satisfy 7 (it is mentioned in the references and in the appendices) but I am not a specialist. \n\n\n\n    * Clarity: \n\nRelatively clear. I just believe the part about $\\rho_k < \\beta$ or $>= \\beta$ should be made slightly clearer in the discussion about the different phases. Otherwise, super clear. \n\n\n\n\n    * Significance: For me, the work is significant theoretically, and is backed by good experiments. ", "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