A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees
Authors: Yuhao Zhou
Jintao Xu
Bingrui Li
Chenglong Bao
Chao Ding
Jun Zhu
Venue: NeurIPS 2025 poster ()
Keywords: smooth nonconvex optimization; regularized Newton method; worst-case complexity; adaptive algorithm
Primary area: optimization
TL;DR: A parameter-free regularized Newton-type algorithm that simultaneously achieves optimal global complexity and quadratic local convergence in nonconvex optimization.

Abstract: Finding an $\epsilon$-stationary point of a nonconvex function with a Lipschitz continuous Hessian is a central problem in optimization. Regularized Newton methods are a classical tool and have been studied extensively, yet they still face a trade‑off between global and local convergence. Whether a parameter-free algorithm of this type can simultaneously achieve optimal global complexity and quadratic local convergence remains an open question. To bridge this long-standing gap, we propose a new class of regularizers constructed from the current and previous gradients, and leverage the conjugate gradient approach with a negative curvature monitor to solve the regularized Newton equation. The proposed algorithm is adaptive, requiring no prior knowledge of the Hessian Lipschitz constant, and achieves a global complexity of $O(\epsilon^{-\frac{3}{2}})$ in terms of the second-order oracle calls, and $\tilde O(\epsilon^{-\frac{7}{4}})$ for Hessian-vector products, respectively. When the iterates converge to a point where the Hessian is positive definite, the method exhibits quadratic local convergence. Preliminary numerical results, including training the physics-informed neural networks, illustrate the competitiveness of our algorithm.

A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees
Yuhao , Jintao Xu", Bingrui Li', Chenglong Bao".4, Chao D Jun Zhu 1+ Department of Computer Science and Technology. Tsinghua Al Institute, BNRist Lab, Tsinghua-Boose BBochhhh-BBohh-e--ee Joint Center for MI., Tsinghua University Department of Applied Mathematics, The Hong Kong Polytechnic University 3 Yau Mathematical Sciences Center, Tsinghua University
'Bejjing Institute of Mathematical Sciences and Applications
AAcademy of Mathematics and Systems Science, Chinese Academy of Sciences 1br22@mails tsinghua. edu.
yuhaoz. cs@gmail. com xujtmath0163
cl clbao@mail. tsinghua. edu. en dingchao@amss. ac. cn dcsz @ts wtw.uttinnnnnnnnt edu, cn
Abstract
Finding an c-stationary point of a nonconvex function with Lipschitz continuous Hessian is a central problem in optimization. Regularized Newton methods are classical tool and have been studied extensively, yet they still face trade-off between global and local convergence. Whether parameter-free algorithm of this type can simultaneously achieve optimal global complexity and quadratic local convergence remains open question. To bridge this long-standing gap, we propose a new class of regularizers constructed from the current and previous gradients, and leverage the conjugate gradient approach with negative curvature monitor to solve the regularized Newton equation. The proposed algorithm is adaptive, requiring
prior knowledge of the Hessian Lipschitz constant, and achieves global complexity of O(e 2) in terms of the second-order oracle calls, and Ö(c- f) for Hessian- products, respectively. When the iterates converge to point where the Hessian is positive definite, the method exhibits quadratic local convergence. Preliminary numerical results, including training the physics- informed neural networks, illustrate the competitiveness of our algorithm.
Introduction
Nonconvex optimization lies the heart of numerous scientific and engineering applications, in- cluding machine learning [34] and computational physics [46]. In such settings, the objective is to minimize smooth nonconvex function & R" - R with globally Lipschitz continuous Hessian. Given the intractability of finding a global minimum in general nonconvex problems, a more practical goal is to find e-stationary point x² satisfying V (x* Il for a prescribed accuracy 0.
The Newton-type method is one of the most powerful tools for solving such problems, known for its quadratic local convergence near solution with positive definite Hessian. The classical Newton method uses the second-order information at the current iterate Ig to construct the following local model my and generate the next iterate Ik+1
Tk + dy by minimizing this model:
1 d Vap(ou)d where & 2 0.
min dER"
mx(d)= = d Vip(ax) +
(1.1)
"The corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Although this method enjoys quadratic local rate, it is well-known that it may fail to converge globally (i.e., converge from any initial point) even for a strongly convex function. Various globaliza- tion techniques have been developed to ensure global convergence by introducing regularization or
constraints in (1.I) to adjust the direction ds. including Levenberg- Marquardt regularization [35 39],
trust-region methods [8], and damped Newton methods with linesearch procedure [4]
However, the original versions of these approaches exhibit slow O(E-2) worst-case perfor-
mance 8 3 leading to extensive efforts to improve the global complexity of second-order methods. Among these, the cubic regularization method 42 overcomes this issue and achieves an iteration complexity of ((c-)), ), which has been shown to be optimal A while retaining the quadratic local rate. Meanwhile, Levenberg- Aevenberg-Marquarde regularization, also known as quadratic regularization, with gradient norms as the regularization coefficients pk= has also received several attentions due to its simplicity and computational efficiency [36] 45) This method approximately solves the regular- ized subproblem mina (m) + 2 [d]]²] to generate de and the next iterate 22+1 = I2 + dgdgg where og is either fixed or one selected through linesearch. When the regularized subproblem is strongly convex, it is equivalent to solving the linear equation (V2y(xx))) + ( )d4 - - -Ve((r)s) which is simpler than the regulareee subproblem and can be efficiently implemented using iterative methods such as the conjugate gradient (CG). Furthermore, each CG iteration only requires
a Hessian vector product (HVP), facilitating large-scal scale problem-solving [53 38 37 55].
While such gradient regularization can preserve the superlinear local rate, the fast global rate has remained unclear for some time. Recent studies have achieved such iteration complexity for convex problems [4] Nevertheless, the regularized subproblem may become ill-defined for nonconvex functions. Consequently, modifications to these methods are necessary to address cases involving indefinite Hessians. A possible solution is to apply CG as the Hessian is positive definite, and choose a first-order direction if evidence of indefiniteness is found 44), although this may result in a deterioration of the global rate. In contrast, Gratton et al. [24] introduced a method with a near- optimal global rate of O(c log !) and a superlinear local rate. Instead of relying on a first-order direction, their method switches corresponding eigenvector when indefiniteness is encountered.
direction constructed from the minimal eigenvalue and the
On the other hand, Royer et al. [49 proposed the capped CG by modifying the standard CG method to monitor whether a negative curvature direction is encountered during the iterations, and switching to such a direction if it exists. is worth noting that this modification introduces only one additional HVP throughout the entire CG iteration process, avoiding the need for the minimal eigenvalue computation used in Gratton et al. [24]. Furthermore, when the regularizer is fixed, an O(c global rate can be proved 49 Building this method, He et al. (29 [30 improved the dependency of the Lipschitz constant by adjusting the linesearch rule, and generalized it to achieve an optimal global rate for Hölder continuous Hessian, without requiring prior knowledge of problem parameters. Despite the appealing global performance, it is unclear whether the superlinear local rate can be preserved using these regularizers. Along similar lines, Zhu and Xiao (56) combined the gradient regularizer with capped CG and established superlinear local convergence rate, assuming either the error bound condition or global strong convexity. However, remains unclear whether this holds for nonconvex problems that exhibit local strong convexity.
Motivated by the discussions above, our goal is to figure out whether the optimal global order can be achieved by a quadratic regularized Newton method (RNM) without incurring the logarithmic factor, while simultaneously achieving quadratic local convergence. Since the Hessian Lipschitz constant Lu is typically unknown and large for many problems, we design our algorithm to avoid both the computation of minimal eigenvalues and the reliance on prior knowledge of Lut yet still attain optimal dependence on LH in the global complexity bound. In this work, we develop a new class of regularizers and a parameter-free RNM that answers this question affirmatively and close this long-standing gap in RNMs. Our approach demonstrates competitive performance against other second-order methods on standard nonlinear optimization benchmarks, as well as in training medium- scale physics-infome informed neural networks for solving partial differential equations [4)..
The remaining parts of this article are organized as follows: We list the notations used throughout the paper below. Background and our main results are provided in Section 2 Techniques of our method outlined in Section 3 with detailed proofs deferred the appendix. Finally, we present some preliminary numerical results to illustrate the performance of our algorithm in Section 4 and discuss potential directions in Section
We also provide further discussions of related work Section[A] 5
2

---

2 Background and our results
Notations We use N. [d], and I to denote the set of non-negative integers, {1,..., ,.), and (t,..jj-1 1..j-11,, 1}, respectively. For a set S, |S] denotes its cardinality, and 1 (jes} = 1f E S, and o otherwise. For a symmetric matrix X, X > (E) Ami and || denote the positive (semi- Xdefiniteness, minimal eigenvalue and spectral norm, respectively. I, E R=** is the identity matrix. The Big-O notation f()) = ((g(z)) means that there exists C' > O such that [f()) s Clg(()) for sufficiently large æ, and f(x) = ((((z)) has the same meaning, except that it suppresses polylogarithmic factors in x. Similarly, f(x) ((g(x)) denotes there exists
0 such that [f(x)] 2 cl((x) for suffciently large x. |>||| is the Euclidean norm of z E R". For sequence h22 generated by the algorithm, we define g [[Vp(=))] ek minjss 9j. and Ap (p(2)) inf p, Up (UP((s))(((oo) V/)])))
Capped CG The capped CG proposed by Royer et al. 49 solves the equation Hd = -9 using the standard CG, where H H + 2pI,.- It also monitors whether the iterates generated by the algorithm are negative curvature directions, or the algorithm converges slower than expected. If such an evidence is found, the algorithm will output negative curvature direction. Specifically, the algorithm outputs pair (d_ dd_ype, d) with d d_type {SOL, NC). When d_type NC, d is a negative curvature direction such that d Hd S -plla]]: and when d_type SOL, d approximately satisfies the equation. In both cases, the solution can be found within min(n, ((p=a) HVPs. We provide the algorithm and its properties in Section B
Complexity of RNMs Continuing from Section 1 we further discuss RNMs. The key to proving a global rate is the following descent inequality, or variants 12 49
30
29
56
24
((xx+1)) - ((=x)====+))))))>))<<))) S -O min (9 PL) where k 2 O.
(2.1)
The dependence the future gradient Ga++1 arises from the inability to establish a lower bound on ||c]]| ll using only the information available at the current iterate, since once the iterations enter a superlinear convergence region, the descent becomes small. If we were able to choose pI such that the descent were least à then by telescoping the sum would obtain (p(xx) <((x)) I -Cke..
The optimal global rate O(e 8) would follow from -Cke 2 p(**)) ((xx) 2 -Ap Therefore, the regularizer Pk: plays a central rule in the global rate. In the thread of work starting from Royer al. (4 Pk x Ve, and the required descent is guaranteed as long as U e; otherwise, Tk+1 is solution. Another line of works related to Mishchenko [41] and Gratton et al. [24 use Pk: O VDk-
With this choice, gh descent is achieved when 9k++1 2 9k- However, when 9k+1 9s. the descent
becomes o2 + but the control over 9k++1 is lost. To resolve this issue, the iterations are divided into two sets: successful set I, {A: 9++1 2 9k/2] and a failure set I, N Ig. It is shown that when !Iyl is large the gradient will decrease below c rapidly; and otherwise, sufficient descent is still achieved. The logarithmic factor in the complexity of Gratton et al. [24] can be understood as follows: a sufficient descent occurs at least once in every O(log !) iterations. Yet, as shown in Theorem 3.2 it actually occurs in every Ollog log 2) iterations.
Local convergence We say (ga has a superlinear local rate of order 1 + D gh+1 O for sufficiently large k, and a quadratic local rate corresponds to the case = 1. Assuming V²p(x*) O, then the classical Newton method achieves the quadratic local rate neighborhood of r", which we refer to as the local region in this paper. In the nonconvex setting, identifying whether an iterate lies within this region is challenging. as it requires knowledge of the solution
x². To assess whether a given regularizer is possible to attain quadratic local convergence, we can consider the quadratic function (xx) |x: 2: the fixed regularizer Pk: x ve of Royer et al. [49 yields linear convergence, while gradient-based regularizer Ps gf with V E (0. 1] achieves
superlinear rate of order 1 + 7 12 36
19
40 Hence, choosing 7 = 2 as in Gratton et al. 24
1
leads to a local rate of only 3.
3

---

2.1 Intuitions and results
We adopt the standard assumption from Royer et al. 49
which also guarantees Dg < oo and Up < co. While the Lipschitz continuity assumption can be relaxed to hold only on the level set (1p(2)) using techniques in He et al. [3). we retain this assumption for simplicity, as it is required for the descent. lemma (Theorem C.T and is orthogonal to our analysis.
Assumption 2.1 (Smoothness), The level set L. := far E R" :p(x) S ((xx)} is compact, and & is Lu -ipschhht continuous on an open neighhorhood of (To( containing the trial points generated in Algorithm 7 where No is the initial point.
The choice of regularizers The preceding discussion reveals a tension between global and local convergence in RNMs: near-optimal global rate requires Pk X vūk. whereas quadratic local convergence demands much smaller regularizer Pk S 9k- A principled approach to reconcile this trade-off is to dynamically adapt Pr to meet these requirements. Ideally, we may set Pt: = =gn where d% outside the local region to guarantee global complexity, and 6% X vgk within the local region to achieve quadratic convergence. However, this choice for dy is not practically implementable, as it presumes knowledge of whether the current iterate lies in the local region, which is typically unknown in the nonconvex setting. Instead, our adjustment scheme is motivated by the observation that, in the local region where superlinear convergence of order 1 + D occurs, the ratio 5e = 9 9t-1 / S -h-1 rapidly decays to zero. Hence, this ratio serves reasonable heuristic for reducing the regularizer and improving the convergence in the local region, though the extent of this improvement remains unclear. The technical analysis in Section reveals that achieving a quadratic local rate requires a refined choice, namely og = min(1, 1,, 96/9/////
with 0 > 1, which is smaller than the original ratio 9k/ 9t-1 Additionally, for 0 E (0, 1]. the local rate can still be improved, albeit aub-quadratically, illustrated in Figure I and formalized in Theorem 3.7
Outside the local region, although the convergence is typically linear or sublinear such that 6g = c E (0, and Pk Vo yitk for most itertaions, there may still be occasional sharp drops in gu that cause dR to become extremely small, unintendedly reducing the regularizer and thereby degrading the global complexity. To address this issue, we observe that necessary condition for entering the local region that the sequence } becomes monotonically decreasing. Based on it, we switch to the regularizer Pk= = vgk whenever this condition is not satisfied. Lines 5 of Algorithm I describe this procedure, where wi corresponds to the choice V for accelerating local convergence, and of Vgk serves as the fallback choice to maintain the global rate, and NewtonStep generates the next iterate based on these regularizers. In practice, 5% rarely exhibits sharp drops, allowing the fallback step to be relaxed or even omitted (see Section G.2p. Theoretically, as established in Theorem 3.2 at least one suitable PI can be identified within O(log log !) iterations, yielding
an O log log )) iteration complexity. Furthermore, our analysis reveals that the logarithmic factor comes from abrupt increases of /9: (Theorem 3.4). It also suggests that replacing I with 6 = minygk Ok the regularizer eliminates this factor, thereby achieving the optimal global rate. This alternative can be interpreted as a mechanism that retains historical information through 6y+ effectively preventing the growth of VEL.
Thus far, the structure of our regularizers has taken the form PI: = w = =wfof and our discussion has focused on complexity with respect to the tolerance parameter e. without addressing the dependence on the Hessian Lipsehitz constant Lg. To attain the optimal global complexity with respect to LH, we require PI= = VLHuf.- However, since La is typically unknown and may vary locally. we dynamically estimate via the sequence Mt using the subroutine LipEstimation and set Pk: = VMaw in 18. The update scheme for M2 is derived from thorough analysis of the algorithm (see Theorem C. Roughly speaking, if the actual descent As = (xxx)) - (((x*+ 1) is smaller than the predicted value from the analysis, this suggests that Me underestimates LH and we increase it; conversely, when the prediction is fulfilled, we attempt to decrease Mg. Our analysis shows that after Ó() iterations, it produces a desirable estimation of LH.
The design of NewtonStep The subroutine NewtonStep follows the version of Royer et al. (49 and He al. (30,, utilizing the CappedCG subroutine defined in Section to find a descent direction. The key modification in this subroutine is the linesearch rule in 11 15 for selecting the stepsize when the negative curvature direction is not detected, and the subroutine LipEstimate immtiini..io. The criterion 2.4 aligns with the classical globalization approach of Newton methods [17], and can be

---

shown to generate a unit stepsize (i.e., 1) when the iteration is sufficiently close to solution with a positive definite Hessian, leading to superlinear convergence (see Theorem E.3) However, as previously discussed, our regularizers may become small when a sharp drop of OA occurs, which also degrades the oracle complexity in terms of the function evaluations and HVPs. To address these issues, we introduce an additional criterion (2.5) to ensure that it remains uniformly bounded as the iteration progresses. In this criterion, the choice of & in 112 is motivated by the observation that selecting the stepsize according to the r.h.s. of (D.9) guarantees acceptance in the linesearch. The role of å is thus to approximate this stepsize, while leaving the unknown term on the r.h.s. to be determined adaptively by the linesearch procedure. Another modification is the introduction of the fifth parameter f and the additional TERM state of d_ d_type in CappedCG. This state is triggered when the iteration number exceeds 22pp- $) ), and is designed to ensure non-degenerate oracle complexity in terms of HVPs.
Complexity Combining all these components, we are able to obtain the complexity results sum- marized in Theorems 2.2 and 2.3 Table also compares them with other RNMs for nonconvex optimization. All parameters aside from the regularizers can be chosen arbitrarily, provided they sat- isfy the requirements in Algorithm [ For the regularizers in Theorem [.. Theorem 2.3 shows that the
complexity in terms of HVPs (). matching the results in Carmon et al. B3, Royer et al. [49 Moreover, the complexity in terms of the second-order oracle outputting (1((2)), Vy(r), V2v(=))
O(c 9) + Ó(1), attaining the lower bound of Carmon et al. 4 up to an additive ((1) term coming
from the lack of prior knowledge about Lи. Notably, the v LH scaling in the iteration complexity is also optimal 44.
Theorem 2.2 (Iteration complexity, proof and the non-asymptotic version in Sections C.2 and
Let {xh 3x20 be generated by Algorithm |
Under Assumption [.n define e = minogisk Oi with 9-1 6-1 9o. the following two iteration bounds hold for achieving the e-stationary point for
2 0::
1. wf ghe w/ o6 and dR = min(1, -) then
Ue
Ug.
k オ A L ccc - log log
log LH log
(2.2)
2. 1f wh = Vel w/ = o% and 8y = C then
Up
k H D Life
log + log
(2.3)
Furthermore, there exists subsequence {xR, lizo such that limy- Tke xf with Vy((**= 0. If 0 > 1 and <²²((=")> > 0, then the whole sequence } converges to a local minimun x², and for sufficiently large k; quadratic local rate exists for both of these choices, i.e. Ik+1 S O(g
Theorem 2.3 (Oracle complexity, proof in Section C.3). Each iteration in the main loop of Algorithm [ requires al most 2(m + 1) function evaluations; and at most 2 gradient evaluations; and either T Hessian evaluation or at most min (n, (((()((())))))) +)) HVPs.
Finally, we note that the overall computational complexity can be viewed as the product of two factors: (i) the number of HVP evaluations required by the algorithm, and (ii) the cost of performing single HVP evaluation. Since the cost of an individual HVP evaluation typically fixed and does not vary across iterations, the complexity analysis reduces to counting the number of HVP evaluations, as given by the above theorem.
Overview of the techniques
We outline the key steps this section and defer the complete proofs to Sections C and D
The global iteration complexity Let A p(xx)) (((x+11) denote the objective function decrease at iteration k and define the index set Ar, S k: A, 2 I 1 3/23 to contain the iterations that achieve sufficient descent. As previously mentioned, key step in the complexity
5

---

Algorithm 1: Adaptive regularized Newton-CG (ARNCG)
Input :Initial point To R=", parameters μ E (0, 1/2), 8 E (0, 1), T- E (0.1), E (0, T E (0, 11, y E (1, oc), Mmax [1, 00), My E (0, oo), and S [0, 1], and regularizers
{w "k k220 S (0, oo) for trial and fallback steps.
for k = 0, 1,.. do
// the main loop // trial step
(#x+g) MR+1) -NewtonStep (Ik, why MR. w if (the above step returns FAIL) (0K+ > 96 and gk S 9k-1) then // fallback step // accept the trial step
(#8+1, Mx+1) NewwtnnStepp Wks wf) else Tk+1 x
Subroutine NewtonStep (z. M,@) i/+ f- min (n,, Mw)
(d [d_typee, d) + CappedCG p(2xz)) Vy((), VMw, Mw) // never reached if w // normal solution
// see Section
if d rype TERM then return FAIL
10
else if d_rype SOL then
11
Set d t d and a + 8m, where 0 S m S Mmax is the minimum integer such that
p(x+ + 8TH d) S ((x)) p d Ve((x).
(2.4)
if the above does not exist then
// switch to smaller stepsize
Set å +- min(1, - - Set a <- âB where 0 S m S mmax the minimum integer such that
13
14
*lx 663 d) S ((t) + pā Vip(z). pa(rd"VVp(r)
(2.5)
15
if the above m does not exist then return (z, 7M)
16
else
// a negative curvature direction (d_type NC)
Set d +- ||d]| and adjust it to descent direction with length L(d):
17
d [d)ssign (d Vx((x)) d, where L(d) 1- V'p(z)d
(2.6)
18
Set + 8rm where 0 S m S mmax the minimum integer such that
p( + Tm d) S p(x) M 2. ||]]
(2.7)
19
the above m does not exist then return (x, (M) x +- x + ad
20
M LipEstimation(;, .T_. 7, 8, μr d type)
return (x+,
22
Subroutine LipEstimation TT, "4
rype)
24
M+ <- M
25
A + p(x) (0xx)
26
if d rype SOL and m satisfies (.4 then
if < 33 UT - min (I ([VV((++))))) [|| 1 w²) then M+ +- 7M
27
28
else if A > 3T M 3 then M -
else d d_yype = SOL and < 3pM 3س then M+ + + 7M
29
30
else if d_type
and A < ( ( then M+ c- M
else if A 2 pT M 3 then M + 7 M
return . +

---

Table 1: Comparison of regularized Newton methods for nonconvex optimization. The parameter Mj estimates Li and is independent of w and w in Theorem 2.2 For details, see arguments of CappedCG in Algorithm I We define It [Vx(=)) and e, minggA 9k. The additive ((1) terms in some algorithms come from Lu estimation. "EPS" in the last column indicates that e is used in the regularization coefficient, and "ME" means the method needs to compute the minimal eigenvalue to determine its parameters.
Algorithm
Iteration Complexity
Order
Regularization Coellicient
Requirements
Royer et al.
Theorem 3]
OLLie- R)
1
Zhu and Xiso 56
Theorem 51
OLLge-1)
17
2n for log "ooo Fe, vd
EPS
He
Theorem 1]
1
Gratton et al
Thorem 3.5]
Ofmax F2 Li)e 1 log 9) 0())
1.5
MMea + (-Aata(V (iaa)))))
ME
Theorem
2.2
OfLie log log !) 0(1)
21r0
MMag min/1, do22.) 1
Theorem
O t) 0())
2
Miee 4. for 2
Zhu and Xiao [56] Lemma 11] with 5 = 1 gives a linear rate.
I The local rate is not mentioned in the original papers, see the discussions in Section 2
analysis is to establish a lower bound on [Wel For example, since Ap 2 (((0) - pp(x))) 2
Ejsr A, Z |W / 23/2, then it follows that x [W&] & 2 as long as | 2 k.
To obtain such a lower bound, we first identify the conditions under which the dependence of A on LH is valid. Let the index sets J = { M++1 = > where M₁ is decreased, unchanged, or increased, respectively. Our analysis in Theorem C.T in
} for i = -1, 0, represent iterations
appendix shows that for k E J U JJ- the descent satisfies 4 Z Mr 1/2//2p, where Dj captures the descent amount independent of Mr and will be discussed subsequently, Therefore, establishing lower bound on [W&]] reduces to counting the number of iterations where M₁. X LH and D& 2 3/2 hold.
Theorem further establishes that if k E Jt, then Ms S LH holds. Since M3 is only increased when & E J we can conclude that Ms S max(Mo. ).). As the bound also depends on the initial value Mo. the incquality M2 3 LH does not hold when Ms 2 LH is overestimated. However, in this case, we find that Ms will be decreased (i.c., & E J as long as ge does not exhibit a sharp drop. Building on this, Theorem 3.5 establishes that satisfactory estimate of Mj can be obtained within O(1) iterations. It remains to analyze how frequently the event D₁ 2 e/2 occurs throughout the iterations. Since under the choices of regularizers, we have either w/ = V 2 ve or w/ v 2 v2, then ensuring sufficient descent can be reduced to counting the occurrences of the event D2 (w()3
Throughout this section, we partition N into a disjoint union of intervals N = U/21 Teg, such that 0 = & and l, < let1 for j 2 1, where I,j = fi....j - 1} is defined in the notation section. These intervals are constructed such that the following conditions hold for every j > 1:
ge, 2 90,+1 2 11, and gt,+1-1 < g6,41
(3.1)
In other words, the sequence {=*]=20 is divided into subsequences where the gradient norms are non-increasing. The following lemma shows that sufficient descent occurs during the transition between adjacent subsequences, provided that & - 1 & J The fallback step is primarily designed to ensure this lemma holds. Without the fallback step, sudden gradient decrease (i.e., a small ōg) could result in small regularizer, causing the sufficient descent guaranteed by this lemma to vanish.
Lemma 3.1 (Transition between adjacent subsequences, see Theorem C.2 in Theorem 2.2 with 0 2 O, we have wi,, -1 wi, -1r each j >> 1, and
Under the regularizers
p(xxe) - pp(r, 1)) -M, 1e, (60
(3.2)
Moreover, if M LH, then lg -1 J-1
The following lemma characterizes the overall decrease of the function within subsequence. "1 iterations with insufficient descent in the It roughly states that there are at most 0 log log ge subsequence Le, 1544 since otherwise the gradient decreases superlincarly below gk.
7

---

Lemma 3.2 (Iteration within subsequence, see Theorem C.3 with 0 O, then for 2 and e Es+1. we have
Under the regularizers in Theorem 2.2
((xx) - (((re))) - -Ci,, (H4,, n J
1--1-1111 +1 max (0, Me no - -Te,, -5) (w)))
(3.3)
where Ct, minggies Mi² and T.. 2 log log (w))
Combining Theorems 3.1 and 3.2 we have the following proposition about the accumulated function descent, and find that there are Eg iterations with sufficient descent. Under the choices of Theorem 2.2 with
Proposition 3.3 (Accumulated descent, see Theorem C.4) 0 2 0. for each k 2 0, we have
(((x)) p(zo)= 2 -oo.
max (ISs n JT 1J -v= - 5.)b) )oz (3.4)
(6+ 1}, and Ju max :g k.. where Vv - E F15. + Te ds and Sx U/
The difference of the logarithmic factor in the iteration complexity of Theorem 2.2 arises from the following lemma, which provides an upper bound for Vi- This lemma shows that the choice
w -V&& leads better control over Vx due to the monotonicity of cg. resulting in improved lower bound for Σx. as indicated by Theorem
Lemma 3.4 (See Section D.3p. Let Vk, Js be defined in Theorem 3.3 then we have (1). If Ifwf = V9k. then V& S Jx log log
Us, cx"
(2). If If VEL. then Va S log c6
+ Jn.
Finally, we need to determine the aforementioned hitting time kinit such that Ma S (T.H)) and apply Theorem 3.3 for {zx he2kur achieve the L dependence in the iteration complexity. The idea behind the following proposition is that when M₁ > (2(HH) but & E To, we will find that the gradient decreases linearly, implying that this event occur at most O Ilog U.e times.
chints
Proposition 3.5 (Initial phase, see Theorem C.5). Let kinit min : M2 S O(L))} and assume
M, > (LLH), then for the first choice in Theorem 2.2 we have kinit S O log
I.x ex ): and
Ma log Up
Ma. for the second choice, we have kinit 00011ggg log
+ log
Up Chipit
Lu
From the compactness of Tap in Assumption 2.1 we know there exists a subsequence {5i, Ju20 converging to some x" with Vip(z*) (see Theorem C.6 In the analysis of the local convergence rate, we need to assume the positive definiteness of V2 ), under which the whole sequence (ax h220 also converges to x* (see Theorem E.4p. Analyzing the local convergence of RNMs requires establishing that the Newton direction (V*p(xx) + ++( ++ (zp(z))) leads to superlinear convergence, and that it is eventually selected by the algorithm. Since the latter is algorithm-specific, we present its proof in Section F.T and state the main results below.
The local convergence order
Lemma 3.6. Assuming V V²(((=)) 2 aln if rype, SOL and m = O, and z is close enough to x², we have Dk+1 < O(gi + w..gk). Furthermore, under the choices of regularizers in Theorem 2.2 if Ty close enough to x we know the trial step is accepted, and d d_type, SOL and my
Remark on the local convergence neighborhood. We observe that when taking w wf 0 with P E (0. 1]. the gradient norm converges superlinearly with order 1 + D. For the choices in Theorem 2.2 we find max(wt, w < vgk so a local rate of order 3 can be achieved in the neighborhood U. independent of 6, after which the proof of Theorem (36 guarantees that the trial step is accepted at K₁ = O(lg log poly ( U&)) iterations. Then, the following technical lemma shows that the local order can be improved to arbitrarily close to 1 + Mo (3.2] for 0 > 0 with Vso defined in Theorem 3.7 (see Figure an illustration), and achieves quadratic convergence for 0 > after K₂ := 2 log 28-2 + steps. Hence, achieving quadratic convergence requires at most K1 + K2 extra iterations once the algorithm has entered the O-independent neighborhood Uo-
Lemma 3.7 (Local rate boosting, proof in Section
F.2 Let 0 > 0 and (Øk Ju2o S (0, oo). Suppose 3 and ge+1 < O + g 9 holds for each k > 1. and go is sufficiently small.
91 < Ogg)
8

---

2.0
1.9
log |log 0x
local order
1.8
1.7
1.6
0.0
0.2
0.4
0.6
0.8
1.0
0
6
number of lterations
Figure 1: The left plot illustrates the local order achievable by the regularizers in Theorem 2.2 for E (0, 1]. It can be made arbitrarily close to 1 Vee- The right plot illustrates the local order for different 9 using (xx) = x², and its slope reflects the local order and aligns with our predictions.
0.9
0.9
0.8
0.8
0.7
rete
0.7
0.6
6460888
0.8
0.5
ARC.K
ARC,K
ANRCO, 19 0.00
ANROO, 0.01
0.4
ANRGO,
0.2
ANBOO,
0.3
0.1
10"
10a
10a
10
10a
10a
10a
10
10
10
elapsed lime (s)
Hessian evaluetions
Figure 2: Comparison success rates as functions elapsed time and Hessian evaluations for CUTEst benchmark problems. ARNCG ARNCG and "Fixed" correspond to Algorithm with the first and second regularizers from Theorem 2.2, and a fixed W/ = ve. respectively. For Hessian evaluations, since algorithm accesses this information only via fressian-vectr products, count multiple products involving V2(((1) at the same point x as a single evaluation.
Then, (1). 1f0 E (0, 11, let Voe be the positive root of the equation 1/2 + I-Ve
8i = Vsa then we have
g++1 S 0 0gk (10/99)))) ) ie., 9k has local order Voe 5 for any 5 0; (2). IfO and + 1, then g S O(g)), i.e. gt converges quadratically.
log 2--
4 Preliminary numerical results
In this section, we present some preliminary numerical results to provide overall sense of our algorithm's 's performance and the effects of its components, and to illustrate the potential application in training physics-informed informed neural networks. Detailed results are deferred to Sections GatdionnSGanII Gnd
CUTEst benchmark Since the recently proposed trust-region-yye -ttpe method CAT has an optimal rate and shows competitiveness with state-of-the-art solvers [26), we adopt their experimental setup and compare with it, as well as the regularized Newton-type method AN2CER proposed by Gratton et al. 24 and the recently proposed adaptive cubic regularization method ARC, [6]. The experiments are conducted on the 124 unconstrained problems with more than 100 variables from the widely used CUTEst benchmark for nonlinear optimization (22]. The algorithm is considered successful if terminates with < = 10-5 such that A: 10S. If the algorithm fails to terminate within 5 hours, is also recorded as a failure.
The detailed oracle evaluations and HVP computations are reported in Tables 3 and 5 in Section G from which we observe that the fallback step has insignificant impact on performance yet increases computational cost, suggesting it can be relaxed or removed. Furthermore, 0 E [0.5, 1] balances computational efficiency and local behavior and a small m preferable. Finally, the second linesearch step (2.3) and the TERM state of CappedCG are rarely taken in practice. Figure 2 shows our method without the fallback step. It is comparable to ARC, and slightly faster than CAT and AN2CER, each iteration uses only a few Hessian-vectts vector products, whereas CAT relies on multiple Cholesky factorizations and AN2CER involves minimal eigenvalue computations. Meanwhile, our method requires similar number of Hessian evaluations as CAT, and slightly fewer than AN2CER and ARC,K. We also note that using a fixed Wi = Ve in Algorithm I may lead failures when gk >> resulting in deteriorated performance. Additionally, method requires significantly less

---

Adam
LeFOS
NNCG NNNGC
MNGG,
Convection
Reaction
Waver
training loss
10-1
NNCB ARNOS,
Training Loss
VNCGiu
NNCGo.1
1.15 10
10-
1.32 10
1.11 x 10
9.23 x 10
10-9
ARNOG,
2.72 x
5.48
10
10-4
NNCG..
5.63 x00
1.69 x 10-3
5.14 10-2
Test L2RE
NNCGam
2:27 10-4
2.52 x 10-3
1.51
10-2
10-7
ARNOG,
1.38
10
10-
Running Time Badget Peak GPU Meroory
7.5 bours
hoous 3,3GB
18 hours 10.2GB
4.7GB
2000 1000
8030
8000
number iterations
Table 2: Best training loss and test lg relative error (I.2RF) training PINNs over 8 runs. We termi- nate training based on a fixed time budget. The time limit is chosen such that ARNCG, performs approx- imately 2000 iterations. The peak memory usages of two methods are similar.
Figure 3: Loss curves for training PINN on the reaction problem. Thin lines are 8 independent runs; the bold line shows the average. The subscript in NNCG denotes the regularization coefficient.
memory (~6GB) compared to CAT (~74GB) for the largest problem in the benchmark with 123200 variables, as it avoids constructing the full Hessian.
Physics-informee neural networks Physics-Informn Neural Networks (PINNs) parameterize
partial differential equations (PDEs) in physical problems using neural networks, and train the network by using the residuals of the equations as the loss function [46). These PDEs often lead to a poor condition number for the PINN loss 47 33 50), making it difficult for first-order optimization methods like Adam to achieve high-precision solutions. To address this issue, a strategy to use Adam first and then switch to quasi-Newton methods such as L-BFGS [27 However, Rathore et al. [47] observed that L-BFGS is still insufficient for effectively training PINNs. To address this, they proposed the NNCG method and further demonstrated that switching to NNCG after the L-BFGS phase can lead to additional loss reduction and improved solution quality. However, this approach relies fixed regularizer and does not fully resolve the challenges arising from the non-convexity of the objective function and still requires hyperparameter tuning for regularizers.
Our goal here is to demonstrate that is applicable to medium-size PINNs and offers improved stability and ease of use, owing to its globalization and adaptivity. The PINN used in our experiments consists of 8 81201 parameters in double precision. Since our method only relies on HVP, Table Se showw the peak GPU memory usage is at most 10.2GB, whereas storing the full Hessian would require 49. 19.IGB of memory. As shown in Figure 3 ARNCG, outperforms NNCG in both iteration complexity and runtime. Further details are provided in Section H
5 Discussions
In this paper, we present the adaptive regularized Newton-CG method and show that two classes of regularizers achieve optimal global convergence order and quadratic local convergence. Our techniques in Section can be extended to Riemannian optimization, as only Theorem C.I Inedds to be modified. For the setting with Hölder continuous Hessians, a variant of this lemma can be derived following He et al. [29), and the subsequent proof may also be generalized (see Section F22 for local rates). However, this case presents additional challenges since the Hölder exponent is also unknown and requires estimation. It would also be interesting to investigate whether these regularizers are suitable for the convex settings studied in Doikov and Nesterov [13), Doikov et al. [15) and whether they can be extended to inexact methods such Yao al. [54) and stochastic optimization.
Acknowledgments and Disclosure of Funding
Y. Zhou and Zhu are supported by the National Natural Science Foundation of China (Nos. 62550004, 92270001), Tsinghua Institute for Guo Qiang, and the High Performance Computing Center, Tsinghua University; J. Zhu was also supported by the XPlorer Prize. C. Bao is supported by the National Key R&D Program of China (No. 2021 YFA 1FF10011300 300) and the National Natural Science Foundation of China (No. 12271291). J. Xu is supported in part by PolyU postdoc matching fund scheme of the Hong Kong Polytechnic University (No. 1-W35A), and Huawei's Collaborative Grants
10

---

"Large scale linear programming solver" and "Solving large scale linear programming models for production planning". C. Ding supported part by the National Key R&D Program of China (No. 2021 YFA 10000003,0, No. 2021 1000301) and CAS Project for Young Scientists in Basic Research (No. YSBR-034).
References
[1] El Houcine Bergou, Youssef Diouane, and Vyacheslav Kungurtsev. Convergence and complexity analysis of a Levenberg-Marquardt algorithm for inverse problems. Journal of Optimization Theory and Applications, 185:927- -94,, 2020.
[2] Ernesto Birgin and José Mario Martínez. The use of quadratic regularization with cubic descent condition for unconstrained optimization. SIAM Journal Optimization, 27( 1049-1074, 2017.
[3] Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. "Convex until proven guilty": dimension-free acceleration of gradient descent on non-convex functions. In International Conference on Machine Learning, pages 654-663. PMLR, 2017.
[4] Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184(1):71-120, 2020.
[5] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems. SIAM Journal on Optimization, 20(6):2333-2822, 2010.
[6] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Mathematical Programming, 127(2):245- 295, 2011.
[7] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evallatioo complexity. Mathematical Programming, 130(2):295-31) 2011.
[8] Andrew R Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.
[9] Frank E Curtis and Qi Wang. Worst-case complexity of trace with inexact subproblem solutions for nonconvex smooth optimization. SIAM Journal on Optimization, 33(3):2191 -2211, 2023.
[10] Frank E Curtis, Daniel Robinson, and Mohammadreza Samadi. A trust region algorithm with worst-case iteration complexity of O for nonconvex optimization. Mathematical Programming, 162:1-32, 2017.
[11] 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, 3185545185544, 2021.
[12] Hiroshige Dan, Nobuo Yamashita, and Masao Fukushima. Convergence properties of the inexact method under local error bound conditions. Optimization Methods and Software, 7744):605-625 2002.
[13] Nikita Doikov and Yurii Nesterov. Minimizing uniformly convex functions by cubic regulariza- tion of Newton method. Journal of Optimization Theory and Applications, (89(1):377333) 2021.
[14] Nikita Doikov and Yurii Nesterov. Gradient regularization of Newton method with Bregman distances. Mathematical Programminy, 204(1):1-25, 2024.
[15] Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularzzed Newton method. SIAM Journal on Optimization, 34(1):27-56, 2024.
[16] Jean-Pierre Dussault, Tangi Migot, and Dominique Orban. Scalable adaptive cubic regularization methods. Mathematical Programming, 207(1-2):191-225, 2023.

---

[17] Francisco Facchinei. Minimization of SC' functions and the Maratos effect. Operations Research Letters, 17(3):131-377, 1995.
[18] Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and com- plementarity problems. Springer, 2003.
[19] Jin-yan Fan and Ya-xiang Yuan. On the quadratic convergence of the Levenberg-Marquarrt method without nonsingularity assumption. Computing, 74:23-39, 2005.
[20] Zachary Frangella, Joel A Tropp, and Madeleine Udell. Randomized nyström preconditioning
SIAM Journal on Matrix Analysis and Applications, 44(2):718 7521 2023.
[21] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics, pages 249-256, 2010.
[22] 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, 60:545-557 2015.
[23] Geovani Nunes Grapiglia and Yu Nesterov. Regularized Newton methods for minimizing functions with Hölder continuous Hessians. SIAM Journal on Optimization, 27(1):478-500 2017.
[24] Serge Gratton, Sadok Jerad, and Philippe L Toint. Yet another fast variant of Newton's 's method for nonconvex optimization. IMA Journal of Numerical Analysis, 2024.
[25] Fadi Hamad and Oliver Hinder. A consistently adaptive trust-region method. Advances in Neural Information Prucessing Systems, 35:6640-6653, 2022.
[26] Fadi Hamad and Oliver Hinder. simple and practical adaptive trust-region method. arXiv preprint Att.:2422.02099 2024.
[27] Slavomír Hanzely, Dmitry Kamzolov, Dmitry Pasechnyuk, Alexander Gasnikov, Peter Richtárik. and Martin Takác. A damped Newton method achieves global O (x²) and local quadratic convergence rate. Advances in Neural Information Processing Systems, 35:25320 2022.
[28] Slavomír Hanzely, Farshed Abdukhakimov, and Martin Takáč. Damped Newton method with near-optimal global O (k-3) convergence rate. arXiv preprint arXiv:2405.18922 2024.
[29] Chuan He, Heng Huang, and Zhaosong Lu. Newton-CG methods for nonconvex unconstrained optimization with Hölder continuous Hessian. arXiv preprint arXiv:2311.1309447 2023.
[30] Chuan He, Zhaosong Lu, and Ting Kei Pong. A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimiza- tion with complexity guarantees. SIAM Journal on Optimization, 33(3):1734-1766, 2023.
[31] Yuntian Jiang, Chang He, Chuwen Zhang. Dongdong Ge, Bo Jiang, and Yinyu Ye. A universal trust-region method for convex and nonconvex optimization. arXiv preprint 2rXiv:2311.11499 2023.
[32] Elham Kiyani, Khemraj Shukla, Jorge Urbán, Jérôme Darbon, and George Em Karniadakis. Which optimizer works best for physics-informed neural networks and Kolmogorov-Anol networks?, 2025.
[33] Aditi Krishnapriyan, Amir Gholami, Shandian Zhe, Robert Kirby, and Michael W Mahoney. Characterizing possible failure modes in chysics-informe neural networks. Advances in Neural Information Processing Systems, 34:26548 14:26548-26560, 2021.
[34] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436-444 2015.
[35] Kenneth Levenberg. method for the solution of certain non-linear problems least squares. Quarterly of Applied Mathematics, 162):164-168 1944.
12

---

[36] Dong- Dong-Huile Li, Masao Fukushima, Liqun Qi, and Nobuo Yamashita. Regularized Newton methods for convex minimization problems with singular solutions. Computational Optimization and Applications, 28: 18:131-147, 2004.
[37] Xudong Li, Defeng Sun, and Kim-Chuan Toh. On efficiently solving the subproblems of level-set method for fused LASSO problems. SIAM Journal on Optimization, 18(2):1842-186, 2018.
[38] Xudong Li, Defeng Sun, and Kim-Chuai Toh. A highly efficient semismooth Newton augmented Lagrangian method for solving LASSO problems. SIAM Journal on Optimization, 28(1):433- 458, 2018.
[39] Donald W Marquardt. An algorithm for least-squares estimation of nonlinear parameters. Journal of the Society for Industrial and Applied Mathematics, 11(2):431-441, 1963.
[40] Naoki Marumo, Takayuki Okuno, and Akiko Takeda. Majorization-minimizztoonn method for constrained nonlinear least squares. Computational Op- rimization and Applications, 84(3):833-88) 874, 2023.
[41] Konstantin Mishchenko. Regularized Newton method with global convergence. SIAM Journal on Optimization, 33(3):1440-1460 2023.
[42] Yurii Nesterov and Boris T Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
[43] Yurii Nesterov al. Lectures on convex optimization, volume 137. Springer, 2018
[44] Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 2006.
[45] Roman Polyak. Regularized Newton method for unconstrained convex optimization. Mathe- matical Programming, 120:125-145, 2009.
[46] Maziar Raissi, Paris Perdikaris, and George Em Karniadakis. Machine learning of linear differential equations using Gaussian processes. Journal of Computational Physics, 348:683- 693, 2017.
[47] Pratik Rathore, Weimu Lei, Zachary Frangella, Lu Lu, and Madeleine Udell. Challenges in training PINNs: A loss landscape perspective. In International Conference on Machine Learning, 2024.
[48] Clément W Royer and Stephen Wright. Complexity analysis second-order line-search algorithms for smooth nonconvex optimization. SIAM Journal Optimization, 28(2):1443 1477, 2018.
[49] Clément W Royer, Michael O'Neill, and Stephen J Wright. A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Mathematical Programming, 180:451-488, 2020.
[50] Tim De Ryck, Florent Bonnet, Siddhartha Mishra, and Emmanuel de Bézenac. An operator preconditioning perspective training in physics-informed machine learning, 2023.
[51] Defeng Sun, Kim-Chuan Toh, Yancheng Yuan, and Xin- Yuan Zhao. SDPNAL+: A MATLAB software for semidefinite programming with bound constraints (version 1.0). Optimization Methods and Software, 35(1):87-115, 2020.
[52] Jorge Urbán, Petros Stefanou, and José A. Pons. Unveiling the optimization process of physics informed neural networks: How accurate and competitive can PINNs be? Journal of Computational Physics, 523:1 13566, 2025.
[53] Liuqin Yang, Defeng Sun, and Kim-Chuan Toh. SDPNAL+: A majorized semismooth Newton- CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Mathematical Programming Computation, 7(3):331-36,, 2015.
13

---

[54] Zhewei Yao, Peng Xu, Fred Roosta, Stephen J Wright, and Michael W Mahoney. Inexact Newton-CG algorithms with complexity guarantees. IMA Journal of Numerical Analysis, 43(3): 1855-1897, 2023.
[55] Yangjing Zhang, Ning Zhang, Defeng Sun, and Kim- Toh. An efficient Hessian based algorithm for solving large-scale sparse group LASSO problems. Mathematical Programming. 179:223-263 2020.
[56] Hong Zhu and Yunhai Xiao. A hybrid inexact regularized Newton and negative curvature method. Computational Optimization and Applications, pages 1-22, 2024.
14

---

Contents
Introduction
2
Background and our results
3
Intuitions and results
3 Overview of the techniques
Preliminary numerical results
Discussions
10
Additional discussions
16
Related work
16
2 Limitations
17
A.3 Broader impact
17
Details and properties of capped CG
19
Main results for global rates
20
Details in Section
20
Proof of the global rates in Theorem 2.2
24
Proof of Theorem 2.3
26
D
Technical lemmas for global rates
26
D.1 Descent lemmas and their proofs
26
D.2 Proof of Lemma
29
D.3 Proof of Lemma 3.4
31
D.4 The counting lemma
32
D.5 Technical lemmas for Lemma
33
Main results for local rates
34
Proof of local rates in Theorem
35
Technical lemmas for local rates
36
Standard properties of the Newton step
36
F2
Local rate boosting lemma
39
Additional numerical results on the CUTEst benchmark
G.
Implementation details
41
2 Results on the CUTEst benchmark
42
Additional numerical results on plysics-informed neural networks
43
15

---

Problem setup
43
H.2
Results
47
A
Additional discussions
A.1 Related work
Relationship to previous RNMs Our primary contributions lie in the introduction of a new type of regularizers, established in Theorem 2.2 which enable smooth transition from the global to the local convergence phase, and in the design of a parameter-free algorithm built upon these regularizers. As illustrated in Table I and discussed in the introduction, the works most closely related to ours are Royer et al. 49 and Gratton et al. [4]] and we elaborate on the differences below.
The basic framework of NewtonStep consists of three components: using capped conjugate gradient (CG) to compute the search direction, a linesearch procedure to determine the stepsize, and an estimation scheme for the Lipschitz constant. The first two components are similar to the capped CG framework proposed by Royer et al. [49], and a similar structure is adopted in He et al. (DD and Zhu and Xiao [56]. However, these methods are not adaptive and exhibit worse dependence on the
Hessian Lipschitz constant LH in their iteration complexity. Specifically, Royer et al. [49] employs cubic linesearch rule for both SOL and NC states, resulting in L2 dependence, while He et al. 30 improves this to L by adopting a quadratic linesearch strategy. Subsequently, He et al. [29] proposed an adaptive algorithm that achieves the optimal vL dependence in iteration complexity. However, it remains unclear whether the number of function evaluations arised from the linesearch procedure may grow unbounded as iterations proceed or how depends on the tolerance parameter e, leaving the overall complexity in terms of recond-order oracle calls unclear. In our analysis, find that to ensure the number of function evaluations remains bounded, it is necessary to incorporate a secondary linesearch condition (2.5). enforce an upper bound Mmma the number of linesearch steps, and increase Mg whenever this limit is reached. The combination of these algorithmic components guarantees that the total number of function evaluations remains bounded, and removing them results in Ollog& {) function evaluations per iteration. Furthermore, the regularization strategies employed in this line of work are proportional e, which requires a prescribed tolerance parameter e and limits the local convergence rate to be merely linear.
Gradient-basse regularizers in RMNs have also been studied by Gratton et al. [24] Rather than employing the capped CG method, they explicitly test for negative curvature using the condition Amin (V (V*((Ix)) - - MMgi When this condition holds, the magnitude of the minimal eigenvalue is sufficiently large, the corresponding eigenvector is used directly to construct a sufficient descent direction. Otherwise, they switch to regularizer of the form P VM + - ---
( (xxx)( oc
/Mag and solve the regularized Newton equation to compute the direction. These two cases correspond conceptually the NC and SOL states in the capped CG framework, respectively. Their method adopts a unit stepsize and uses an acceptance ratio to decide whether to accept the new iterate and how update the Lipschitz estimate Mg. based on the accuracy of the local model. However, although their algorithm incorporates a mechanism for updating Mr. the dependence on LH in the complexity remains max(L VLH) ), and it is unclear whether the optimal order /L can be achieved. Furthermore, their regularizers are proportional to v Vgk. which, as discussed in Section 2 limits the local convergence rate to 3/2. On the other hand, incorporating the acceleration factor 8% could potentially improve the local convergence rate of their methods, but this may lead to increased HVP complexity due to possible sharp drops in Ik- This issue is addressed in our method through the introduction of the TERM state in CappedCG.
Finally, we note that the proof in Gratton et al. 124 applics only to gl bbsbd regularizers instead of the eg-based ones, while the proof in Royer et [49] not applicable to gı- ones. Our partition 3.1 is new in RNMs and unifies the two regularizers into the same analysis.
Other second-order methods with fast global rates The trust-region method is another important approach to globalizing the Newton method. By introducing a ball constraint |[d]] S Tk to (.I).
"Gratton et al. (24] also proposed a variant that replace V²((zz) with an approximation detined over the Krylov subspace to reduce computational cost. For notational simplicity, we focus on the full-space version in discussion.
16

---

provides finer control over the descent direction. Several variants of this method have achieved optimal or near-optimal rates [TO BT]. For example, Curtis al. [T, Jiang al. [3] incorporated a Wrrenberg-Marquaar coefficient Pk. these regularized trust-region methods introduce an additional free parameter: the trust-region radius rik which provides extra flexibility to attain quadratic local convergence. For instance, regarding the local convergence rate, Jiang et al. [31] Tab. 2] first examine whether the smallest eigenvalue of the Hessian is sufficiently large. If this condition holds, they set P = 0 and employ the trust-region constraint purely as a globalization mechanism. Under a local convexity assumption, the method then effectively reduces to the classical Newton scheme in a neighborhood of the solution, thereby achieving quadratic convergence. However, this strategy requires an additional eigenvalue check and cannot be directly extended to RNMs, which rely only on the regularization parameter Pk- As a result, achieving quadratic rate is more challenging for RNMs.
regularizer into the trust-region subproblem. Except for the regularization
Hamad and Hinder [25 26 introduced an elegant and powerful trust-region algorithm that does not modify the subproblem, achieving both an optimal global order and a quadratic local rate. In contrast, our results show that the RNM can also achieve both, while using less memory than Hamad and Hinder (26), as shown in Section 4 Interestingly, the disjunction fast gradient decay and sufficient loss decay, as discussed above in the context of RNMs, is also reflected in several of these works. They also partition the iterations into failure and success sets, which leads to an additional logarithmic factor [31] Our partition based on non-increasing subintervals of the gradient norm, as defined in (3.I. may also be used to improve this factor. It is worth noting that, previous to Royer et al. [49], linesearch method with negative detection
proposed by Royer and Wright [88] For convex
problems, damped Newton methods achieving fast rates have also been developed 27 and the method of Jiang et al. 31 also be applied.
For adaptive cubic-regularization methods such as Dussault et al. [16], the core step consists of minimizing cubically regularized subproblem, which can equivalently be interpreted solving the regularized Newton equation (V²g(x)) + pl )d
V where p x or|cd]] depends on the solution d. A central component of Dussault et al. [16] is the search for an appropriate value of In contrast, our method employs a prescribed regularization coefficient that is independent of d, thereby eliminating this search phase.
Adaptive and universal algorithms Since the introduction of cubic regularization, adaptive cubic regularization attaining the optimal rate without using the knowledge of problem parameters (i.e., the Lipschitz constant) were developed by Cartis et al. 6 7), and universal algorithms based on this regularization that applicable to different problem classes (e.g., functions with Hölder continuous Hessians with unknown Hölder exponents) are studied by Grapiglia and Nesterov [23], Doikov and Nesterov [3. Additionally, some adaptive trust-region methods have also been introduced [31 26). Recently, several universal algorithms for RNMs have also been proposed, including those by He et al. 229] Doikov et al. 11). Gratton et al. (24]. As discussed earlier, Doikov al. [15] focus on convex problems, the I.H dependence in the complexity of Gratton et al. 24 is suboptimal, and the local convergence rate of He al. (29] is not quadratic. Therefore, none of these methods achieve our goal of parameter-free approach with both optimal global complexity and quadratic local convergence.
A.2 Limitations
Despite achieving optimal global complexity and quadratic local convergence, as well demonstrat- ing competitiveness with other second-order methods in numerical experiments, our methods for training neural networks still require multiple CG iterations to find descent direction. would be desirable to develop better preconditioners or alternative strategies to further reduce the cost of each iteration. Furthermore, the Lipschitz continuity of the Hessian is assumed, which may not hold for nonsmooth activation functions such as ReI.U.
A.3 Broader impact
Our work primarily focuses on the theoretical properties of RNMs and proposes a new algorithm. We do not anticipate any potential negative societal impacts.
17

---

Algorithm 2: Capped conjugate gradient 44
Algorithm 1]
Input :A symmetric matrix H E IRdxd a vector 9 E RR, regularizer E (0, oo), parameter p E (0, 2o) used decide whether to terminate the algorithm earlier, and a tolerance parameter & (0, 1).
Output: (d_type, d) such that d_ d_type E SOL, TERM) and Theorem B.2 holds.
Subroutine CappedCG (H, 9: p: P)
(yo, To. Po. j) +- (0,g. 0)
H -- H + 2pIn
M + ||H
I|Pall
Po Hpo pllpoll? then return (NC,p)) po)
while True do
// Beginning of standard CG || ag
Hp
M yı + ORPK
Fk+1 rk tag
||r+1112
Be+1
11
Pk+1 & -Tk++ + 1
// End of standard CG
12
+ ++1
13
M + max (M,
[[Hp
[[rell
[[rull
|
Ivell
// Estimate the norm of H
E,, T,, T) - M+
&
J Ax
14
3R
VRFI (I-VF)=
15
if U/g Hyk pllyx|1 then return (NC, yk)
else if' || || - Ellro|l then return (SOL, 3kk
16
17
else if pk Hy < pllpxl 1| then return (NC,
18
else if
||rw|] v /T ||rol| then
I|re11
19
OC PK Hpt
20
Mc++1 < yk + 0&PP
Find E (0...., 1) such that
(yk+1 n.) T H (gxx41 - y1)
(B.I)
|1 22
22
return (NC, Mk+1 y:)
23
else if l: 2 J(M, P.C {) + then
return (TERM, Vk
11 JMM is defined in
B.2
18

---

B Details and properties of capped CG
The capped CG in Royer et al. 499 is presented in Algorithm 2 with an additional termination condition 2 (M, p, <) + and type TERM. Note that in Algorithm | we will take p = VMw. The following lemma states the number of iterations for the original version of capped CG.
Lemma B.1 (Lemma 1 of Royer et 49
When the termination condition for TERM is removed,
Algorithm 2 terminates in min (n, JM, p. E)) + min (n. O(p b)) iterations, where
V
144 144 + 1) 66
M P
P, = +
log
(B.2)
The additional termination condition indicates that the regularizer p may be too small find solution within the given computational budget.
For the oracle complexity, each iteration of Algorithm 2 requires only Hessian- product, since the quantities yy. Hp, and Hr used in the negative curvature monitor can be recursively constructed from Hp generated in the standard CG iteration. When the residual decays slower than expected, one more CG iteration is performed, and if the historical iterations are stored, only one additional Hessian-vector product is needed.
The properties of our version with the TERM state are summarized below.
Lemma B.2. Invoking the subroutine CappedCG H, 9, p. &, P) obtains (d_type, d), then we have the following properties.
1. When d_lype SOL, is an approximated solution of (H + 2pIn)dd = -g such that
d' (H 2pI,. à 2 p||d||
(B.3)
d Hd 2 -
(B.4)
| - 2p 119l1:
(B.5)
1
[I + 2pl, )d + gll v 2 p$|||| s Ells|l.
(B.6)
d d (H 2plm)d - ?
(B.7)
2. When d_type = NC, d a negative curvature direction such that d Hd < -
(B.8)
3. When d d_type = TERM, then p < p. In other words, i S p the algorithm terminates with d type {SOL, NC}.
4. Suppose there exist a, b 0 such that H 2 al S hp and S 1, then the algorithm terminates with d d_type SOL when & = = PSS C(a, a, H|), where
C(a,a, min (1, 60
1/
24a
12a
Tamz
(1
17 VUUUU 2)
b7
Proof. The first two cases directly follow from Royer et al. 449 Lemma 3] The third case follows from Theorem B.I and the monotonic non-increasing property of the map p J (M,
The fourth case follows from the standard property CG for positive definite equation, since H al, the capped CG reduces the standard CG. Specifically, let {yk, rk rkh220 be the sequence generated by Algorithm then Nocedal and Wright [4]] Equation (5.36) gives that
k |eell 5 2exp
Vn(HI) -1
-2k
||elll 22
||eoll
Vx(I)++ +1
R(H))
'This lemma assumes that H V²p(z). V(((x), and oo has Lipschitz Hessian. However, the statement of this lemma and the capped CG involve only the Hessian of to at a single point a, and hence the assumption be removed.
19

---

where ||ex|] = ex He and s(H) (a + 2p) [ + 2p) is the condition number, and
eg yb + 11 1 H ' TM and H H + 2pIn. Then, the above display becomes
4k:
[ + 2p ||x|| 1 r2 H 1 rk S cxxp
(v((H)
To
H
rd
4k
I 4exp
a + 2p ||rlll?.
(ve(H)
Let M, Hi, E be the quantities updated in the algorithm. Then, we have M 2 a and S p
||| +
and & &. 3x 3p 1[ Hence, when the TERM state is removed, and suppose Algorithm
terminates at k,-th step with SOL. Then, we have
k. - 2 log log 6 (V 2
(B.9)
Since x(H) $ [|| and p I 1, we know
k. H log
6V H
[ + +2
+1 K(p,)).
Varp
When incorporating the TERM state, and suppose is triggered at the k-tth step, then
kpp 2 k. > k (M 12 p.)
(B.10)
However, when bpd 2 D. we have
J(M, 2 J(a, J(, b)
a
log
144a
V bp
e²b² 2²p2pan
Hence, when { = P C(a,,, a, b, [HII), we have bp 2
# 2 and
144n
6
|| +)
Vap²
144a and p'p'u12 2 12. Then,
B0
J P. K(.
a log
144a
1
6V
H [| + 2)
log
bpa 67 pa+22
2V
a
Vap²
1
H
144a
log 12
log
1>
1>>0 0,
2V
a
67 7777
2
which leads contradiction. Therefore, the algorithm will terminate with SOL.
C Main results for global rates
Throughout this section, follow the partition 3.1 defined in Section and provide detailed proofs for the global rates in Theorem 2.2 and corresponding lemmas described in Section 3 For the sake of readability, restate the lemmas mentioned in Section 3
C.1 Details in Section 3
As discussed at the beginning of Section 3 the following lemma summarizes key properties of Algorithm| I and plays central role in estimating the number of iterations that yield sufficient descent. Its proof is technically involved and deferred to Section D.I
Lemma C.I (Summarized descent lemma, proof in Section D.2 Let {ar, Mr. d d_type m2)220
be the sequence generated by Algorithm / and denote We = w if the trial step is accepted and
We = wf otherwise. Define the index sets J = {k: M = 7 Mr) for = -1, 0, 1, and the constants O₁ max (93))3, r (38(111 -1) and Cs min(2, 3 64) then
20

---

1. 1fk J' then Ms S ČZLH:
2. For the regularizers in Theorem k J- where a max(2230) 30).
2.2 if Mr CLLH and T_ S min (6g 8 82+1), then
Moreover, we have 11=-1,0, n lo,k) = lo, and
1J Lo,al S 1 0 Lo + [log, (r03Mo Lu)l+,
(C.1)
k = Ho, s 2 n + 11 no + [log, (n03M LH)l+,
(C.2)
and the following descent inequality holds:
0,
isk J. JUUT!
p(xx+1) - -((xx))= -
Ci 1 M DR,
(C.3)
where C₁ = min (9 - 2p1)2 31,5mu111111 - 122 4u/33). and
(w))
ifk J-1,
D₁=
min ( w/: o 1ht1w ) min (wf) wxk) (ux)
if d d_pppe SOL and m& 0 and k & J-!
(C.4)
otherwise.
Lemma C.2 (Restatement of Theorem 3.1
Under the regularizer choices of Theorem 2.2 we have
wi,- w/ - for each j 2 2, and
p)wx,)) - (((xe-11) - 1
(C.5)
where Či C' are defined in Theorem
C.1 Moreover, Mr;-1 CaLHs then Ej -
Proof. Let = é, 1.--. If the fallback step is taken, then w/ wf. holds. We consider the case where the trial step at k-th iteration is accepted, then we know Ik+ Ik+1 > by the partition rule 3.1 However, the acceptance rule of the trial step in Algorithm [aroommggiiee gives that ya > - and hence
min 11 (1,99-11) 1. Moreover, we have gk-1 6k-1 1 and then
min(ex-1,gu) 2 min 6k-1 2 Ej-
Therefore, ccc-1 1. Combining these discussions, know Wy wf, for the two choices of regularizers.
It remains to show that D; 2 (wf) 3 for Da defined in Theorem C.1 which holds since we know Ik+1 > by the partition rule B.1... and Ou 2 (wf)2 by the choice of regularizers, and therefore,
C4 Dp 2 min((w) ) ( min((wh) ..... ((())) 2 (wf))
(C.6)
Finally, when M₁ > CLLH, we use Theorem D.5 to show that k E J- For the first case in that corollary, since T- < then we = =wf w. then the corollary gives k E J-1, For the second case, the results follows from (C.6) and min(w 1
(wL) > (wh)3
Lemma C.3 (Restatement of Theorem 3.2). Under the regularizer choices of Theorem 2.2 we have (wf) 1+20 (w(_1)-20 20 wk S w/ for each k 2 Moreover, for j 2 and l, < k: < l
((xx)= - ,((x,) 5 -Ce,. (Me,, nig ---nl111- max (0, (0, (. T - -Te, - 5)) (w{),
(C.7)
where Ci. Č₁ minsgies M 2 Tt,5 = 2oo log (3(w))((wcf)-) -2). and Ō₁ is defined in Theo-
rem
Proof.
Under the regularizers choices, we know for each k E N, D3 defined in C.4) satisfies that Dj 2 min ((wf)² - w wx) = min ( w > min ( (wh)) 3+)) (wk -00).
(C.8)
21

---

Case 1 For the first choice of regularizers, we have wf = V and Ti, = 2og log
30. and 93
min (52+197 -
91
8 4:3
91-1 9
-30 30
if J-1
((1++1) - (p(x))
Cig.
if
where C = C,M, 3/
When A > O, for any Eg < l S fJ+ - 1, using Theorem D.9 with
D.9with
+ 30, 30, gk. Mr, k - Ej - 1, lega no))
(p1,41,P, P2, 02, a, A, K,S) =
2: 2 2
(C.9)
we see that
((xx)) p(ze,)
Öi Σ
M, M 9i
1 3 -
Σ
M
min 2
" 99.
+30 -30
9i-1
Sick SEJ-
4iick
IEJ
< CC Σ
Di
-Ceyk
Σ
min (gi+191 3 39; 9i-1
2:30 36
Giic 1EJ-1
kiSic
iEJo
Cej. (Iee, Iilee,nnn- - max (0, [e 1 - -Te,k - 5)) gk.
(C.10)
On the other hand, when 0 - O, we know (((x+11)= - p((p)) S -Cisi+10 - for I-1, and CC
also holds by applying Theorem D.8 D.8 with
1 (, (k. 90, - 1 - 1, 1e, 1, noo).
Case 2
For the second choice of the regularizers, have wf V and Ti, 2 log log Lt,
Since Eg is non-increasing and wg S VER for each A E N, then for fixed such that lg S i f-+1 1, we know 9: 2 Gi+1 and have the following two cases.
1. If gi+1 2 4-1, we know & min(e)11.9t) 2 min(e
61-1 EG. Then,
D2 min (oe 4 $
C8
39
30
(a+t1 2)
min (2--G -t :9
++30
-30 (e:= 1)
G-11)
2. If gi+1 < 6i-1, then using gi+1 2 min(gi+1, Ei41, we have
D min (o- - c
+33
330
(04+12041)
2 min (c
- $ ;9
4+39 -30
G-11
G-11
Thus, from Theorem C.1 we know for e siic Siillt11 1.1-1,1 -1, holds that
C min
(2214
- 2+30 30
if J-1 and gi+l < G-11
p(1i+1) (xx;)
C.a.
if J- or gi+1 2 G--1.
Define Jh = J fi: 9:-1 2 3-13 and J = -o For any lg < k S l++1 - 1 and 0 > O. can apply Theorem D.9 with the parameters a, A, and (osJosigk+1 therein chosen ck Ct,- and (eiJe, sisk, respectively, and other parameter choices remain the same as (C.9) Then, we know
(((x)) - pl(22)
Cee d
Σ
Cei. Σ min min
(c:1 -1 6 [
++3 30
6,-1
SSii VET-'UP
SySisk iEJ0
Ce (I4e, A n (a--((T-U-0 (UTI + max (0, 14, A n nT - Te, k - -)) ck
Ct & (He,, nJ max (LIe, n Jal, [e, n 1- -Te,,k - 5)) c
< CCya (Me 0 nJ J--111110 max (0. Me, n n - Te, - 5)) c
(C.11)
Similarly, when 0 0 we can invoke Theorem D.8 to obtain the same result.
22

---

Proposition C.4 (Restatement of Theorem 3.3 Under the regularizer choices of Theorem 2.2 for each k 2 0, we have
((xx)) - p(za)= I -Co,t [Haxnn-) + max (ISk n n 1o. - Vv -5.kk) c::
(C.12)
where Co, is defined in Theorem }}, and Ju = max : Eg S k).
C.3 and V = E Teyes + +Te and Sy = U {1z+1-
Proof. For each j 2 0 such that f - lg 2 2, using C.7 with k: ls+1 1 and C.5 and
1KK0 = (KET 1) - [[kE we find
((((ttt)) - (x(ee) )- = (((()),1)) - (( + (f( - +p(xe,+1))
S -Cee,1s411 (Mee, n n max (1 1ej+1-1e E5+
n - 5)) (w)
where T, = Teg. and Js.j Tzg; Ci. are defined in Theorem
C.3 On the other hand, when C.5)
f++1 Ej 1, then the above inequality also holds since it reduces to
Define JR max {j= lj S kj. then L.x, S k fiu+1, and the following inequality holds by noticing that for each E N. either wf /tz orwwr wf = V 2 Ves.
J--
plax)) - (p(10)) = (((x)) ((()))))) )
Σ (((()es)1)) - ()(xe,))
S Cen (Tesy O n + max (0, (ee1 O gT - Tess v - 5)) c
J-1
Σ Cegisi (175,1511 0 nT max (1(0)))1650) 1 1,5 n 5)) 1-111
S -Co (oo n + max (1Sa J 1o, n 1 -55+k)))
(C.13)
where Vs Σ T3 + Te,, k. Sp Uド= max(a, b) + max(c, d) 2 max(a + +c,b+ d).
1--1pp (l++1 - -1 and the last inequality follows from
Proposition C.5 (Restatement of Theorem 3.5 Let kinit = min(j: : M, S CCtt M > ČALHH and kinit = 0 otherwise, then for the first choice of regularizers in Theorem 2.2 we have
kiitt S log,
yMu
(ōslog
Up
+3
+2,
(C.14)
CaLH
Ekinis
2 (2.30 log - > 0 and Ö4 is defined in Theorem For the second choice of regularizers, we have
where Orgg
C.1
and [x]- denotes max(0, x).
Mo
Up
kuit S log, C
+ +O2 Özlog log
+ 2.
(C.15)
Ekinit
Proof. Using Theorem
C.1 and observing that the constants therein satisfy C4 2 Ös. then we know Mj is non-increasing for l kinit. Hence, CaLo Mr Mo Hon 31 and equivalently,
log,, (CaLH) < log, M₁ log, Mu 1T n-
(C.16)
By definition of 8 in Theorem 2.2 we know 82 = wi (w( < 1.
Let Itjj = {l E Itj
oy < T-}, and I = {l E L
8ft1 < J.). From Theorem C.I when M2 > C,LH and
T_ < min (8gg dg 2) we have J -1 Equivalently, we have (Ji IT ( (Tt) -
for < j < kinit- Then,
14. J
[44, Iz,)) n (4, \ \ - 14, (Iz, UItT) > |را - ( + | > /4ا - - 15ا1
(C.17)
where the last inequality follows from I,, = 1 C - Reformulating (C.17)
obtains
| 2 (1i+1 14411 nJ 1) v0. iis kinit
(C.18)
23

---

Case 1 We consider the first choice of regularizers, i... o5 = min(1, 949h-1) Following the
partition (.1). for any ; S 1 f++1 and < Kinit
know g++1 gi and d1+1 = 91+19;
Therefore, since log 01+1 - and log T- < 0, it holds that
log
g1+1
log 8:41 <
Σ
log 82+11
ge,
sisS
log T-
C
E
A( 11,+111111-=- +1,,+1441 n nT
(C.19)
a
where A = 2a log 1
0. Let k < kinit 1 and J3 max (j: S k: 1). then
__
f/ log
1
2
log
16,11-1
+ loog 9k+1
Up
g1;
gl
==1
Jx-1
c.19
A Σ (11e++1,055111 -1eg-ll111e nT
A(I +1,++1| - +1,++ 0 n
< --A( 25, - | 0 J 1),
(C.20)
where the last inequality follows from |4, |4, -2 and 11,+11,4111123 11 g
11y+1,84++11 n
For S S J2. we have E - k < Aimit 1, then Theorem C.2 gives Ej - 1E --ET- Therefore,
1o.4+1 n 2 J& and (C.16) yields log, (CaLn) < log, Mo Jr. That is, Jn I log, C,L.
M
From (C.16) we know
Ug
k 11,411
Jk A
log
+2
+ 14184115-1)
EK+l
Jk
A
log
Up
+2)
+log
Mu ČLL
I log,
MMo ( A- log Uz
+3) 3).
Ek+1
CaLH Ek+1
Case 2
E for each is e N. For any l kinit 1, we know similar version of (9.99) holds since log 8:41 I O):
When d3
ck+1 log
log 0:0 S
Σ
log 8:41
EU
velo,
TET,)
<
T
0,6+1
-A( - 1T 1J
Therefore, we have
1: = 11,41 S - log
6o
+ +1 0 1
C,16
log
6o
+
log
MMo
Ek+1
Ek+1
Finally, the proof is completed by setting kinit and noticing that the conclusion automatically holds when Mo < C2LH.
C.2 Proof of the global rates Theorem 2.2
The following theorem provides a precise version of the global rates in Theorem 2.2 It can be translated into Theorem 2.2 by using the identity [logLn]] Lnl+ + [log 1 |+ = log L
Since the right-hand sides of the following bounds are non-decreasing an e-stationary point is encountered such that ég S 9k S 6, the two inequalities below hold with < replaced by Hence, the iteration bounds in Theorem 2.2 are valid.
é;: decreases, whenever
24

---

Theorem 0.6 (Precise statement of the global rates in Theorem 2.2 Let faat be generated by
Algorithm I with 0 2 Under Assumption 2.1 and ler C max 7 Ca) T C1 Og, Cg defined in Theorem C.I and let C3. Kinit be defined Theorem
with the constants we have
C.S
1. w
V and w w min(1, (,, then
t: 2 log, MM
(cs108 Ue +3)
CaI-H
Ek
+5
CApLit
-3
1og,,
CzL# Mo
+2
(log
log Ue
+7
+ 2.
6k
2. If wf Ek, and w w W then
ČsL Mo
A: 40
CApLite ir
+ log,
+2
Mo
Up 6%
+ log, C4LH
+ (24 + Cog
+
Moreover, there exists subsequence { 3:20 such that lim Tke = x² with Vip(x*) = 0.
Proof. Let kmit be defined in Theorem C.5 without loss of generality, we can drop the iterations {z, hisuin and assume Mo I C4LH, where C4 defined Theorem C.1 By Theorem C.I we
know k E T implies M₂ S CRLH, and hence sup,20 Mj S max(C4, 7 Ln.
By applying Theorem C.4 we have
-Ap S (p(x)) (2(0))
Co - (max((a,, -b
which implies that Σg CL A FE with C proved by find lower bound over Σx.
and the theorem can be
Case For the first choice regularizers, Theorem 3.4 shows that V2 S J3 log log Li and hence, ex
J I- +|+ max (S 1o, nJ (Toglog Up + +5 5))
Eg 2 To,
D.25
ÖsLh Mo
log,
2,
log log Ug 7)
where Theorem D.7 is invoked with W; 0 and Up inequality and incorporating the initial phase in Theorem 3.5
log log ex yields
U2
+ 5. Reorganizing the above
U +7) (ooglog
k Kinit 5
log
+
Mo
eN
Case
For the second choice of regularizers, Theorem 3.4 shows that Vi I log
Up
+ Jk. and
en
Σg 2 To O IT max (1Se [IsenJ-1 1,
Up 6J²
To, n J log 6
Using Theorem D.7 with U3 and W3 = log
Us
we know either log eu
Un > k/24, or
ÖgLH Mo
Σx
log,
- 2.
40
By incorporating the case A 24 log ev
Us
and the initial phase in Theorem 3.5 the proof is completed.
25

---

The subsequence convergence From the global complexity we know lim 0. Since <R = min(<x-1: Is),, we can construct subsequence {0x; J220 such that Jt, = Cky Note s((xx, - (((0)) and the compactness of the sublevel set (20) Assumption 2.1 we know there is further subsequence of } converging to some point x². Since Vp is a continuous map, we know Vy((=)== =0.
C.3 Proof of Theorem 2.3
Proof. The two gradient evaluations come from Vp((z)) and Vy(2; + dg). The number of function value evaluations in linesearch criterion upper bounded by Mmax + In the SOL case, at most two criteria are tested, in the NC case one criterion is tested. Thus, the total number of function evaluations is bounded by mmx + 2. The number of Hessian-vector product evaluations can be bounded using Theorem B.2
D Technical lemmas for global rates
D.1 Descent lemmas and their proofs
In this section we provide the descent lemmas for the case (Theorem D.2) and the SOL case (Theorem D.33.. The lemma for the NC case is the same He et al. [30 Lemma 6.3], and we include the proof for completeness. However, the linesearch rules for the SOL case are different, so we need a complete proof.
The following lemma transfers Theorem 2.1
two useful inequalities.
Lemma D.1 (Nesterov et al. (43). Under Theorem 2.1 we have the following inequalities:
LH
VV + d) Vy((x) ((r)d <
|d]
(D.1)
2
p0 + d) 5 ((x) + V d
2 d V (xx)d 6
LH
1d|.
(D.2)
Lemma D.2 (Descent lemma for the NC state). Suppose d typee, d, d, m be the those in the subroutine NewtonStep of Algorithm 7 and x. w. M be its inputs. Suppose d_type NC and let m, be the
smallest integer such that 227 holds. 1f < m. S M we have
gm. 3M 2p)
(D.3)
LH ς( + 8m d) p(x))= < 9,32 2 21 Maww
(D.4)
L
When m. = 0, the linesearch rule gives
6(x + d) - x(xx S -uM -
(D.5)
Finally, when m, Mmaax we have M S (3 6p)) L
Proof. Let H (2)(2), from 2.6 we can verify that ||d||
L(d) = M- Hd.
where d = ||d]| and d is the direction satisfying Theorem B.2 Then, d Hd M ||
and d V((()) < O. When m. let < m, - 1. then (2. fails to hold with m = j. and
D2
La 30d llll
- M|dl| < ạ(x + 3'd) p(x)
3'vp(z) d
d Hd+
2
321 d Hd +
LH 3
3
(D.6)
g2j
LH زقو |d]
M 3|d]3
(D.7)
2
6
Dividing both sides by 828 [d]s we have
M
Lu gi.
-Mp <
+
(D.8)
2
6
26

---

Lu 2 Therefore, rearranging the above inequality gives D.3
From B.8 and 2.6 we know d' Hd -VlWlldll and hence ||d]] M- ld Hd
2 M M-ha -w [d]l?
By the linesearch rule 2.7 we have
9,3² (1 22x 1 M
fo + gm d) - (xxx) - p1/2mm Mld| v -1332m. M w--2w 3
L
When m. (D5) can be also proven using the above argument.
Finally, when m, > Mmax 2 O, we know
(27 fails to holds with m = 0, and then (D.)) holds with
j 0. Therefore, have M 6p)) LT..
The following lemma summarizes the properties of NewtonStep for SOL case. Its first item is the necessary condition that the linesearch (2.4) or (2.5) fails, which will used by subsequent items.
Lemma D.3 (Descent lemma for the SOL state). Suppose d d_type, d, m, m, be the those in the subroutine NewtonSter of Algorithm 7 and v, w. M be its inputs. Suppose d_type SOL, and let
m, 2 0 be the smallest integer such that (2.4) holds, and m. 2 0 be the smallest integer such that
2.5 holds, then we have
1. Suppose ur d Vip(x) g(x + 735d) (p(x) for some T E (0,0 and j 0, then
6(1 p)M V2CMw
B
(D.9)
L [dd]
|
where Cm == 311-WM Ii
Lx
2. If Mmax 2 m2 > then a = 3mm and
gm. > max (hil==lC//VVooooll-tt
(D.10)
p(r ad) (p(x) < 36,3μ(1 11)2 Mawa.
(D.11)
L2d
3. If m. > mmax but Mmax 2 m. > then gú. V20
4. If m, Mmax but mmax 2 m. 2 then a with à min(1, M [|d[) -
and
p(x ad) w(x) < -13th C3 min (OM, 1) M M- 3
(D.12)
5. If both m. Mmax and m. Mmax. then M <
6. m. = 0 (iee, the stepsize = 1), then
4pM
p(x d) p(())= < 25 8L min (IV + =1 ww.). (D.13)
Proof. = (zz)z) We note that in the SOL setting, the direction d is the same as d returned by CappedCG, so Theorem B.2 holds for d.
(1). By the assumption we have
LB
p d V((()) < p(z -8 ((x)
T d Vp(z) + 2 d Hd
+
7 - 33
6
Rearranging the above inequality and dividing both sides by 7,35, we have
-(1 =1dd VVp()) < T d Hd + Lu , 3 ||d|
(D.14)
2
6
27

---

From Theorem B.2
we know that d' Vy(x) = -d" Hd - 2/ Mww | | then since (0,1/2).
j 2 0 and B E (0. T (0, 11, we have 1 - 41 1/2 / TB3 and
Lu 73
D.14
TBO
d' #Id+2/Mu(1 ,>]ld|1?
2
(1- TB80
MM
||d]2 + 2V Ww pd]
7B30
VMw
1-
||d|2.
2
Therefore, have
6 6v p1 TB3122
6v -M)
(D.15)
L |d||
L
which proves D.9
(2). In particular, when m, > O, we know (.4 is violated for m = O, then D.9) with T = 1 and
j 0 gives lower bound of d:
||||| Mv u)
C2. bw..
(D.16)
LH
Note that 2.4) is also violated for m. - 1, then D.9 holds with (j, = (m. - 1, 1), and we have
D.9
6v 6v - 11)
BS
3(1 1))
Mw²
gm
Cm Cx(]VV Fw,
(D.17)
Lu ||]]
LH [Ve(t)]
which yields (.10
Moreover, the descent the function value can be bounded as follows:
flx + 3m d) ((x)
14,3 d (T(()())
mmmm d (H + 2V Md Hu -UV Mw ||d]]
6v GWMM(11 - 14)
6(1 - p)
143v Mw Mdl
mB( (alp-uB(iMM (Mlll))
Lu|ld|
LH
D.16
36,3p(1 12)2
L3 M Maw3
(D.18)
(3). The linesearch rule 2.5 can be regarded as using the rule in 2.4 with a new direction åd, where
á min(1, + M i ||d]]
*) Since m. O, then (2.5) is violated for 0 S m.. and (.9) with
7 gives
g2d 6VMw(1- p)
6M 1)
20
(D.19)
LHd2l|d||
Lh
Thus, the result follows from setting m. 1
(4). Since m. > Mmax 2 0. then the linesearch rule (.4 is violated for m such that (D.16)
holds. Hence, following the first two lines of the proof of (.18), we have
(0x a. d) x(x)= < -u M 3 wa ||]]
m. M dow min [Id] w # - #[dl|$
D.I6
mg.. M me min (C M -w M--
m Cs min (CM, 1) 3
(5). Since m. > mmax 2 0, then D.19 holds with j 0, which implies that 202, i.e.
2M <. LH-
28

---

(6). When m, = 0, by the linesearch rule and Theorem B.2 we have
p(x+d) (p()) I nd V((()) S -WVMilld]
(D.20)
It remains to give a lower bound of ||d]] in (D16), which is similar the proof of He al. 30 Lemma 6.2] with their en and ( replaced with our v MM and 1j. Since special care must be taken with respect to M, we present the proof below. Note that
VVp( + dIلl - V[ + d) Vp(x) - (xx)dl
+ [[)()( + (V))(x) - 2V Mww,)) + 2 Mwlld]
B.6
LH
|d| + VM (~0) 2w ||d]l-
2
Then, by the property of quadratic functions, we know
|d]| 2 - ( + 4) + i + 4) + 8L ( (MM)) + diil
MM
n1
2 co v Mw min (w ? V + d))l.
where co 1= 4+ (4+))((8-))8M)M11110 1M
1M
2M
2M and we have used the
+8M
(4+ 48M
-2548M-
inequality -a + v bs 2 (-a
Va² + b) min(s s. 1) from Royer and Wright 48 Lemma 17],
with
4 S 5, b 8L M
and w- Vip(= + d)|l. Combining with (D200), get
(DI33.
D.2 Proof of Lemma C.1
In this section, we provide the proof of Theorem C. It is highly technical but mostly based on the descent lemmas (Theorems D.2 and D.3 and the choices of regularizers in Theorem 2.2
First, we give an auxiliary lemma for the claim about ls J-1 in Theorem C.I
Lemma D.4. Suppose the following two properties are true:
1. Suppose d_iype; * SOL or my > O. Mf > ČaLu and wr 2 T- then k: E J-1;
2. Suppose d_type; SOL and my If Mr > Lu and min (2 T- (wf)² then k E TJ-
where 8% w)(wh)- is defined in Theorem 2.2 Then, if Me > T.L and T_ S min (og, 81+1) know 1 E J-1
Proof. Let = max(2,30), We consider the following two cases:
1. Note that r- < If wh < <_w then we know the trial step is accepted since We * wf. and hence, w/ wh and r_ > 5% z og since 6, E (0, 1] and A I a.
2. If min (9h41 W w < T (w we use the choice wf. = /ga as an example, the case for w/. VEL is similar and follows from 9k+1 CR+1- In this case, we have 6 (min(1.g49. When the fallback step is taken, we have we w and
T 9x min (o 19 (. -
Since dF E (0. 1] and a, have > dg. On the other hand, when the trial step is taken, we have 3 v oz and
T > 0k min ( b/2 50
#
0k
(1+51)
2 9k min (1 - 2
gh 6%0
= min (
2 ,0000 min (02
30 min 02).
11+1
29

---

Conversely, we find when 7- < min (6% 8% 8 the assumptions of this lemma give that l E
J-1.
We will also show that the two properties listed Theorem D.4 hold in the proof of Theorem below, and leave this fact as a corollary for our subsequent usage.
Corollary D.5. Under the regularizers in Theorem 2.2 the two properties in Theorem D.4 hold.
Proof of Theorem C.1 Define A =((x)) ((x++1) We denote wi = w if the trial step is taken,
and Wis = w/ otherwise.
2h + de. we define Er Case 1 When d_ypeeg = SOL and me 0, i.e., Tn+1 min (g w w.)).
1. When & E i.e. M++1 -yM,, we have
Ap
4uM &
T4 M
E& 2 A
Eks
33
25 8L M
where the first inequality follows from the condition for increasing Ms in Algorithm 1 The above display implies 25 - ML 2 33T 2 33 T4 1, and hence, My S LH.
2. When Fg 2 T- (wf)3 and M& > I.HI, we have J-1 since
M Es 25 8L M
4 + (w
4
A
- HT M₁ (wf)3
+
33
which satisfies the condition in Algorithm for decreasing Me since a therein is w Thus, the second property of Theorem is true.
Case 2
When d t_yye, SOL, and let m, and m. be the smallest integer such that (.4) and 2.5
hold, respectively, as defined in Theorem D.3 We also recall that Cha
3(1-4)Ma
2 Zn
Me
Ln
Since the previous case addresses m, increasing Ms in Algorithm 1 is
0, we assume m, > here. Then, the condition for
A S T4. BuM W
(D.21)
The condition for decreasing Ms is
D 2 μT MT_MM (wot)3
(D.22)
1. When l E J and mmax 2 m. > 0, i.e., m. m., and dx++1 = 3k = m de. we have
T+ TuB w
D.21
b.Il
36,3μ(11 - 1²)² M w 2
93μ
M wg
k
2
It
Since T4 I 1, then we know Mr S - LH /3 < LH/3.
2. When Mmxx 2 m, > 0 and M, 2 -- (93) L1 and W/ 2 T then
98p
w/ = 193 M M } ww NT 2M,, à (r2 = Mr (wf))
A
M
L2
I3
which satisfies D.22). and hence J-1.
3. When l E I and m. > mimax and mimax 2 m. 0, then we know
11. C... min (OMe, 1) M ww.
which implies 3 > BT+ grt. C33 Mr min (CMLID 1). If Cas I 1, then its definition
implies that M₁ < 2LH/3 /3. Otherwise, we have 2 g C When m. 0. we
know C%, < < and hence Mr I 22HH33 /3; when m. > 0, Theorem D.3 shows
gm. 22 > CM2s and hence Cte, 1, leading to Mr < 2LH/3.
30

---

4. When m. Mmax and Maxx 2 m. 2 0, and Mr 2 LH. we have Cи. 2 and by Theorem
D.3 m. = 0, since otherwise we have 2 B V2CM, 1, leading to
a contradiction. Then, D.12) gives AR 2 HM, & wh. and therefore & E J-1 long as
2 T-
5. When > Mmax and m maxx then Theorem D.3 shows that M2 S LH 12, and the algorithm directly increases Mg so that E J
The above arguments show that when & E J., we have Mr S LB S CsLnn and when 2 T_wy, and Mr C4LH 2 max(L,-_'993)) LH, we have k E J-1, i.e. the first property of Theorem D.4 true for SOL case.
Case 3 When d_type; NC, let m. be the smallest integer such that 2.7 holds, as defined in Theorem D.2 In this case, the condition for decreasing Mr is also D.22) and the condition for
increasing is
A S 22) ww
(D.23)
1. When & E T and m, > 0, we can similarly use (D.4) in Theorem D.2 and (D23 to show that M₁ LH/3.
2. When m, > 0 and Ms 2 shows that (.22 holds. Therefore, to E J
- 244)) LH and T- s wk, then Theorem D.2
3. When m, 0, show that M,+1 will not increase, since otherwise D.5 and D D.23
imply that 1 (1 3d 2 leading to a contradiction.
4. When 0 and =_ wk, know D.22 holds from D.5) and
1, and hence
k E ET!
5. When > Mmax and m, maxx then Theorem D.2 shows that Mj s LH/(3 6μ4. and the algorithm directly increases Mg so that J
The above arguments show that when J1, we have Mj S LH/ min(1,3 6p)) S ÖgLH and when W/ 2 T_w and Mş > CgLH 2 r_ (33((1 24)) 2 we have k E J ie., the first property of Theorem i. true for NC case.
The cardinality of J By the definition of J we have
log, M₁ log, Mo Io, n J41 1T, nJ-+
For each we know Mp+1 > Ma only if Mr S CgLH, then sup, Mr. < max(Mo, )0² and hence (C.I) holds. Adding Lo. \ J to both sides of (C.I) we find holds.
The descent inequality The Dj dependence in (C.3) directly follow from Theorems D.2 and D.3 For the preleading coefficients, we consider the following three cases. (1). When
the result also follows from the two lemmas and the fact that M, 2 1. We also note that the L dependence only comes from the case where d d_type- = SOL and m does not exist, and for other cases the coefficient is of order L (2). When i E J-1, the result follows from the algorithmic rule of decreasing MR: (3). When Jo, we know the rules in the algorithm for increasing Mj fail to hold, yielding M, dependence of the coefficient.
D.3 Proof of Lemmal 3.4
Proof of Theorem 3.4 When w/f = Te. the upper bound over V, follows from the monotonicity
of log log 34 On the other hand, when wf. VER, know 3Es,-1 2ct,-1 2 22t,+1-1 since
31

---

fes is non-increasing. Then, we can apply Theorem D.6 below with a = 3 to obtain
J
36e,-1 + log log
3et
log log
1
6k
12224
(1-1 + Ju log log 3 S log +
co
log
Jk.
log 3
Fk
6
where we have used the fact that log 2 and log log S
Lemma D.6. Lel (11521 S (0, oo) be sequence, and a 2 3, ab; 2 2b5+1, then have for any
k 121 1,
ab,
1
bi bx+1
log log
S
log
+ log log a.
(D.24)
bs+1
log
a
j=l
Proof. Using the fact (x)) S x for > 11, and log - log bj+1 2 - log a > - llgg 0,
have
k
abj
log bj log bj+1
log log
Σ
log 1+
+ k log log
bi+1
loga
j=1
log b, bogb
+ log log
log
j=1
log b log bk+1 + k log log a,
log a
which completes the proof.
D.4 The counting lemma
Lemma D.7 (Counting lemma). Let J-1,111 least one of the following inequalities holds:
",,J,, N be the sets in Theorem C.1 then have at
k
[log, (o - 2,
(D.25)
5(Uk + +
k
W& 2 Uk + +)²
(D.26)
where Σg = 1o, J- max (IS& n Jo), 1T, n Jo|
We UkJ and Sy S Jo,kr Us
J3 1 = 1Sk and We E I, and CG is defined in Theorem C.1
Mo is the input in Algoritim
Proof. Denote B = (U&- + 2) n J and Ts = (7C5,, following five cases, where the first three cases deal with Js < Bg, and the last two cases are remaining parts. We also note that the facts Ho = k and 1 > U. are frequently used.
We consider the
Case 1 When Js < Ba and We < BR, we have
To. 0 n
E 2 1o, n 1- 14, n - - W3 > 14,6 1o-11
Unds
Us +
To n ---1+++++ Lo, no
12 k: T
U4 2
Uk +
Case When J4 Br < Wv, and
1o. n
< $. then by C.2 we know S 2/ n
+ Tk. and hence, E, 2 To, n J
2 3
2 T
Case 3 When Js < Bg < Wg. and To,
n Jo
f/4 then We 2 Bg > 3U++2
32

---

Case 4
When SS n > Bx/2, we have
Σ* 10, n n J + n oo nJ + 10.0 n
k k- Tx 2(Uxx - 2)
2(U +
Case
When J4 2 BB and SS: n
< B2/ we have
By 1 - JR |Sa|
SS n J
+ 14 n J4| + 1
B₁
+ To.: n + 1o. n ng-
B
+ 2/,6 |
+l
Therefore, have
Σx 2 Lo. n
4
5 1o.k n n
1o,6 ng-1
5
1 811,,1 n
Bk
Ps
+
5
4(Ux + +2)
5
4
2
2
1
8
To. ng
+ 4
nTT
-2 - --2
= 5
4(U' +2)
1
T -2 - - 2
5
Up +2
Summarizing the above cases, we conclude that
k
2
k
Σg 5(U + 2)
I&
(lgg,(csMM LL LH)) 11+ 2,
5
5(Uk + 2)
and the proof is completed.
D.5 Technical lemmas for Lemma 3.2
This section establishes two crucial lemmas for proving Theorem 3.2
(a.k.a. Theorem C.3 in the
appendix). Theorem D.8 mentioned in the "sketch of the idea" part of Theorem 3.2 is specifically applied the case / O. For 0 > we employ a modified version of this result as detailed in Theorem D.9
Lemma D.8. Given K E N. p q > and 2 > O, and let (g:Josisk+1 be such that A = 2 ... 2 9K 2 9K+1 a. Then, for any subset S S [K], we have
P41
max(0.1S) Ru 2)=-
(D.27)
9
ES
where Ra : log log
34 a
log log
< log log 34
Proof. It suffices consider the case where A = since for general cases, can invoke the result
of = with gj. replaced with gj/A A, a a/A, respectively. Let T p/q and In {i E [K]
exp(>*)a S 9j < exp(7*+1)a) )a] with 0 < k & R2 and I_ = {j E [K] a S gj < ea). Let
Sa exp(7*) for l 2 0 and Ç-1 = 1, then we have C 2 c cm Note that (Ia } -ISKER is
partition of [K], then we have
R_
R.
Σ
Σ JES
1
9
NES
k=-1
jES JJttley
Ra
(Sea)"
9- - 9 Isle 9 9ap-9
(D.28)
(Sx+1a)*
k=-1
jES
JES 1d+IETT
33

---

where Is == k, there exists most one I& such that j + 1 & Ig. Hence, [Zsl 2 |S| (R, 2).
- 1,
R.). By the monotonicity of gj. we know for each
Lemma D.9. Given E N, P1 > > 0, > 42 > and A 2 a > O, and let (gg Josssk+1 be
such that A go 2 91 2 2 9K 2 9K+1 a. Then, for any subset S C [K], we have
Σ iES
min -
Ji+ A Jr
9,
9
max(0, |S|
R R 4) min (AA-'))"~- ()
(D.29)
where Ra,
log log 34 - log 4.
I log log 3A for 1,2.
Proof. Similar to Theorem D.8 suffices show that (D.99) is true for A Let 7; P:/q: for i 1,2 and I = {i [K] exp(rf) a S 9j < exp(T1 )a} with < k S Ra, and I_ = [j [K] S 9g ea). Note that (IA RgASSR.. is partition of [K]. then similar to
(D28 we have
R Σ
Σ
min
min
n =1
g
g
g
9
JES j.j JitleI,
gfd²
Σ min
21 a 11--1
g
where Is = E
Ra,1} and have used the fact that min(a1, 8) 2 1
min(022,3 3) if a1 2 az- Moreover, we can also conclude that [Is] 2 |S| Ra,1
Next, we consider the partition of Is and lower bound the summation in the above display. Let Jr
{j E Is exp(T a $ 9j < exp(72 k+1 }a} with 0 < k < Ru.2, J-1 [j E Is S 9j < ca).
and Js = (j E S j.j- 1E Js, -
R Then, similar to (D.28) we have
Ra
Σ min e 21 41
g
Σ
min 2e- at Pip--1 _
92 2-
22
JEIs
k=
Jss min (e m -1 0 a2a2-
Therefore, the proof is completed by noticing that Jsl 2 [Tsl Ra,2 2.
E
Main results for local rates
In this section, we first provide the precise version of Theorem 3.6 Theorems E.2 and E.3 and then prove the main result of the local convergence order. The proofs for technical lemmas are deferred to
Sections E. and [2
Assumption E.1 (Positive definiteness). There exists a > 0 such that V²i((=") m al,-
Let C(a, a, b, U) be the constant defined in Theorem B.2 a defined in Assumption E. and 7's n, Mo, 77 be the inputs of Algorithm I and 0 be defined in Theorem 2.2 We define the tollowing
34

---

constants which will be subsequently used in Theorems E.2 and
UM max LsyLH), 2LH
Ly = (((((=)) )11 + LHdO.
UUM 1-or1 Lzg
č= (1 28) -1 rU -
01 = min
(0) min(n; ())
4
[II10] 20U (.g) (1 1.g))
C1 max
a
(1 2
82
min
6 201 gl (c10) + 1) + 32I
C2 = 4a
max
2a Lااي (2+ a a))
a² (Im + 2U T + (.g)) 12g))
63 = min
62, 1 2 (0
+ +1) 1 4
Lemma E.2 (Newton direction yields superlinear convergence). Let x, d, M and w be those in the subroutine NewtonStep ee of Algorithm 7 with d d_rype SOL. Let be such that Vip(=*) 0 and (²p(=") = al,, then for E B5, we have the following inequalities
|| - (x + 4)1 5
LHIlæ x² +M :+w(1 + Lg) - -
(E.1)
بطويع [+((2)]1 (2
V + d)l s a
M / /
(E.2)
a²
The lemma below shows that the Newton direction will be taken when iterates are close enough to the solution.
Lemma E.3 (Newton direction is eventually taken). Let x² E RRn be such that Vip(=") = 0
and Assumption E. holds. If max(wt, w I Vgk. then d_rype; = SOL and my = exists for Ik E B5g (x*). Moreover, the trial step using wt. is accepted for I E (2y(=*).
E.1 Proof of local rates in Theorem 2.2
The following proposition is the non-asymptotic statement of Theorem
2.2
Proposition E.4. Let {2 be the points generated by Algorithm
7 with the regularizer choices
{[=k,3520 in Theorem 2.2 and 0 2 O; and x", 20, {{ 3520 be those in Theorem C.6 such that limy- Ik, = x² and Vip(=") = 0 and suppose Assumption E. holds, i.e., <²'p(="" al,
Then, there exists jo such that Cjo 9Go <222(1((2c)-)) and T. E Bs,(x*) and
1. limg Ft x".
2. When 0 (0, and 2 have
[[ S (2oz) (
(10/9)*
where Voc E [t. 1] is defined in Theorem E33 and illustrated in Figure 7
3. When 0 and j log2
28-1
we have
20
[V < (2e2) 20+2 [
Proof. Since lim Iky = x and V = 0, we know jo exists. We define the set
I I= Li 91 = ej and xy Bag (x*)).
(E.3)
By the existence of jo. we know jo E I. Suppose k E I. then we will show that k: + E I. Since
the choices of bi and wi in Theorem 2.2 fulfill the condition of Theorem E.3 we know the trial step is taken and Øb+1 T& + dg, where dy the direction in NewtonStep with w wh.
35

---

From Theorem E.2 and Theorem F.2 we have 9N - Lglla x²1l S Lgd3, w S Vhh and
gh+1 C29 + czwige S c2 + (Lgda)²) U I 0z (L L 00 au S gk.
(E.4)
Hence, EK+1 = (in(Ee:: = 9k-1- Moreover, since M₁ S UM, then
|a++1 x"I
E1
2
LLHd + 2U 03) (1 + 1g)
Lu 2U h L (1 + 1.gg) 5 S 8z.
Thus, we know k + E I. By induction, k 6 I for every k 2 jo: which also gives the convergence of the whole sequence {2x} since Theorem E.2 provides superlinear convergence with order à of the sequence {|| 1 x² =l
+8 Furthermore, the regularizer wt reduces to g 9k-1 for k: 2 jo + and the premises Theorem F3
and Theorem F.4 are satisfied, with the constants co, and v therein chosen as C2 C2, and respectively. Then, the conclusion follows from Theorem F.3 and Theorem
Technical lemmas for local rates
F1 Standard properties of the Newton step
This section provides the proofs of Theorems
H.2 and
which are the detailed version of Theo-
rem 3.6
The following lemma is used to show that <²)((>) 0 neighborhood of It can be found in, e.g., Facchinei and Pang [18 Lemma 7.2.12].
Lemma F1 (Perturbation lemma). Let A, B E
R with ||~ S a If B $ B and
aB 1, then
B BB 1 a-a3"
(F.1)
Corollary F.2. Under Assumption E.1 we have the following properties:
1. When x E B&g (x*), we know (2((x)) = L. and [(V2>p(z)) s 2
2. g| - y/l [Vvp(x) Vy(y)) & T.glI y for r, E Bag (x*))
Proof. The first part directly follows from Theorem F.1 Since 2 is L -ipsschhi,, then
sup -E B (x*)
[((())) < V p(x")| + Lu = Lg
implying that V is L Lipschitz on Ba, (I*). Then, the second part follows from Nesterov et al. Section 1].
Proof of Theorem E.2 From Theorem F22 we know L and ||
< for every x (x and H = 22p(z). Then, let Mew and note that by the choice in Algorithm
S M we have
|| - (xr dd d)ll < |[H + 2eI,,) ) Vv(()) + (x* x)1l + ||d (H + 2eI..) -
[1( + 2TT..) (1V + H(a"
((="-=x)) - + 2e|1 - xll V+))(
(IVvp(1) + H(s -x)ll + 2e||=* - =11 + 2c (+(x)))
0
D. 2 (Ln|l>* - x||² + 2e|1 - x|| + v<l\V>(<>)l))
(F2)
From Theorem F2 we know - |<(())| < Lg x²1| yiclding E..l
36

---

Furthermore, we have
2Lg
VVpa d)ll S Lg]1æ² - (x + d)ll
(LHl|=* - 2²12 + +2ee|=" =|1 + 2e 2e|[V
2hg
(4LH
4 2a
[V((a)]
a2
a
Proof of Theorem E.3 Let = || - Il. the proof is divided to three steps.
Step We show that d_type; = SOL for Ia E Bs, (x*) regardless of whether the trial step or the fallback step is taken. By Theorem F.2 we have V > I for E Bg (x*). From Theorem B.2] when the fallback step is taken, then d type, = SOL. On the other hand, if the trial step taken, we will also invoke Theorem B.2 as follows. Let (1 + 20) E (0, 1], we have
1. When wi = 인 1iin,,9965"0 we know (wz) 2 96 U o w up
2. When w = t +0
6k-1, still holds that (w)) 2 u
Therefore, let p = T Mzu and p = Mauke and note that from Theorem C.1 we have Mj. S UM-
then let -Ug UN know
(aS1)
~² = (w))" Mτ = - M p
2 T
U
UN b=b-1p
Since the map U C(a, a, b. U) defined in Theorem B.2 non-increasing, know
inf Bog (x*)
Cla/2,a, x 2 Cla/2,,,,b (1
From Theorem
F2
we know for I E Bs, (x*),
p MMat UZ s UR < min (n, ē)
Thus, CappedCG is invoked with 5 = p and the premises of the fourth item in Theorem B.2 are satisfied, which leads to d t_type, SOL.
Step 2
This is standard step showing that the Newton direction will be taken (see, e.g., Facchinei 17]. Facchinei and Pang (8]).
We show that m. 0 for taken. Define wi = w if the k-th step is accepted and W = wf otherwise, and denote de as the direction generated in NewtonStep with such Wj. By the assumption and Theorem E.2 we have for
Bs, (a*) regardless of whether the trial step or the fallback step is
Ie E B5, (x*), it holds that We I ot
< L r
and sup (w-) [[=)) < Lg. and
E.
THur + 2M (1 + (uy)) S cir
| + dz
(F33
where have used Theorem C.I to obtain Ms. < UM. Using the mean-value theorem and noticing that V<p(x*) = O. there exist ç.S E (0, 1) and He = V2plx" + c(( x*)), He = <2p(x* + E(I du x²)) such that for 2y (z*).
1
v(xx)= x0x*) = (d - x²) Hạ( - x²),
1
Lg 2 rk.
(xxx + dx) -((x)) = ( + d2 - x²) Hę + dg -x)
2
37

---

Combining them, we have for 2 E Bo, (x"),
1
c( dx) - -p(xx)
2 V(p(Ex) ds
L 3
1
x²)² H5 - -x") 1 [)p(xx)) d2
(ok
Tdxx
2
c 3
1
(Tk + dx - x²) H5( - -x") 1 (V - -H - x²)) dk.
(F.4)
2
2
Let x² + <(0b x²) and note Vy((=)) = then
[)p((>)) 5 Vv((a)] = [(Vx((r)) - vi((x)) - -- - vx(x")]]
//' Vip(z" + + (x)) - x²' zd)dt 5-1 / Fap(z* + +((3 x'' x¹)) x )dt
1.. (V2upla* + 1(xx x²)) - v2p(<"" + +(( x (z)) x yae
S L [/ t||2x E||radt- = Ln ( t(1 12 x lrxd S Lnri.
Therefore, we have for Ik E B8, (x*))
[)p(a))) - Hς - x²" z²)l
< V - Hạ( - x²) x²'| + 11 - V
= 1 Vp(x") - Hc x')|| (p(t) v>((xx)]
S <C 11 + LHT? (C+ 1)L < 2L < 22Hōôr1
(F.5)
We also note that by the definition 63 < 12c)) Hence, c > 1/2 and for Ix E (x*),
|| < || + dy - x= || + || - I=1
CITE + S (c + 1)rx S 2rk:
(F.6)
||d 2 || - x. || - || + d2 - x.ll
Tk
c
2 N (1 - c3 )rx N //2
(F.7)
Combining the above two inequalities, we find for æg E Bs, (x*),
(V)((z)) He - -x,)) dxl
Tdpl
4L 8 Tk
(F.8)
1(x + d2 2,) Hy x.)l
LOcTT k
(F.9)
Since d_ typpe,, = SOL, then using Theorem B.2 and note that 22p(1x)) -
I., we know
V)(())) T de
B77
(V2 (xxx) + 2M wkTh Dd S - a
||d
a
2
8"
Substituting them back to and note that μ E 1/2), we have for ohk Ba, (x²),
(
de)
(p(xx)))=)))))))()))) (((())))) de
1
V Td + (((TR de) - (((x))) 1 V Tdh
2 μ
1
+ 1 2/2 (T + L + AIHOO) r
#
2
We can see that the above term is negative as long as nk I 82. and therefore, the linesearch (24 holds with my O.
Step 3
We show that the trial step (i.c., the step with using wi) is accepted. Since d_type; = SOL, then NewtonStep will not return FAIL state, so it suffices to show 9k+ V|V dx)ll < gk.
where de the direction generated by NewtonStep with w wt S Vgk- Then, by Theorem E.2 and E.4) we have 9x+1 S 9% for 2 B6, (x*).
38

---

F.2 Local rate boosting lemma
In this section, we establish generalized version of Theorem 3.7 in Theorem F:3 and Theorem F:4 which extends to the case of v-Hölder continuous Hessian and reduces the Lipschitz Hessian in Assumption 2.1 when // = 1. The results in Theorem [33 primarily characterize the behavior for 0 E [0, vl. while the case of 0 > is analyzed separately in Theorem [.4 This division into two cases is mainly a technical necessity, as merging them could result in the preleading coefficient Cj in (F.12 becoming unbounded.
Lemma F.3. Let {gx) E (0, 20), co 2 21, c, 1,12 0, uo = = 14 and 0 2 0. If
logg1 g1 < log co + (1 + vo) log 90 and the following inequality holds for k 2
L+D g
9k+1 S cOk
14v + cgk
+og
(F.10)
Ih-
and go < min (2c) b, ,, ). then we have gh+11 S gk and the following inequality holds for
every k 2 0:
log Ik+1 S log C. + (1 + 1/,) loggs. gk.
(F.11)
where we define 0 = min(0, v) and Voe 31 1 0) + (1 0)2 47 E [0, v) is the
positive root of the equation a + dv = Voc. and"
1tv0
0
log ca = log(2c) + 1 1K-1
log Ck-1
1 log(2c) + log co.
(F.12)
OVk-1
0h (Vo0- -D) Voc (1+
gh
1k min 1, +
1/0
(F.13)
+ Vx-1
(1 + D)2k
In particular, when 0 2 v, we have = and Uk N2
[1+0)2E.
Proof. We first show that Voc E v]. Define the map T(a) + da a for a v). By 1ta
reformulating it as T(a) = i + 0 + - ( (14e + (1 (1+a)) we see that T is strictly decreasing
whenever + a 2 VO, which holds since 1 2 1 2 2 0. Then, there exists a unique Voo E [2, v] such that T(vss) = 0 because T(p)
00 I+F
2 0 and T(p) -(0-v) < 0.
Let C N be the set such that 1e E I if and only
Ik+1 S gk. Ck 2 1, S V/2,, and
F.13 hold,
1 (1 + カ) k
and log c₁ < 1 (1 1)
log( (c) log co.
First, we show that 0 E I. Since vi- = v and gā S c we have 91 S cogo 1+0 < 9o. The other parts hold by assumption, and we have used Voc 2 1 and the definition that w-1 in (F.13 for k = 0.
Next, we prove I N by induction. Suppose o.....j - for some j 2 1, we will show that j E I. Since j - E I, from (1.1)) we have 9j S C3-19 1+2, and equivalently, 97-1 S (cT119)) 140/-1 Note that cj-1 2 1 and gj S Ij and 3
for 1 2 0, we have < 99-1
9j+1
cgj
+v
+ cg,
140 g
< cgj
14
+ 00 9j
144
8eg 1+ 1+
-H-1
(erg 121)
1+04 dvg-1
20c 200
I+
max 9T ,,t,,
,9j
'We define セ-1 0.
39

---

Therefore, we find that
0
0v3-1 log cj-1 min [1+ + D+
log 1g (og(2c)
loggi.
(F.14)
Vý-1
+ Uj-1
loges
l44
Thus, F.1 holds for k = j. and lo 2 log(2e) 2 log 2 2 0, i.e., Cj 2 1.
Since [ - 1] E I, we know (gi is non-inereasing, 0f - g I (2c) -1 and gj S 9j-1. Note
that D I y and Øj S 90 1, then 0y+1 ogj cgj +0 (0,9パ-1) S 2eg] 1 + 99-
By 13 Vi-1 2 min(i, (i, v) = E and we have
0
lo & log(22) +
9j-1
1+2 1
(0=1)
1 11 (1-1 (1(1+0)----)
(2c)
+ 1+1 1
1 - (1+ log(2c) + log Co
< (1 + 1)
(1 + 0)-1 log(2c) 2c) + log co-
Finally, we show S V/o and (.133 holds for k j. Define the map F(a) = & + 80
Ita We
know F(a) is non-decreasing for a > 0. and ( ) Vioe by its definition. Since V/ S V/c and
F(UG-1) S F(Vxo) Voo I v. then V, min(v, F(v; 1)) F(v,-1) S 2/ Moreover, we have
01100 12-1) (1 + Vo (1 12-1)
0 10 =-= F(Ux)) F(ug-1)
OV - (/-1)) (1+ (1+ D)2
0 (1 17)
(1 + D)25
where the last inequality follows from the induction assumption. Thus, we have E I and by induction I N.
log
Corollary F.4. Under the assumptions of Theorem then 9k converges superlinearly with order +
F33
i > and l 2 ko =
2log(1+0)
log 9k - (1 1 1+0++ 0+ +++ log(20) + 0 log co + (1 + v) log 9k-11
(F.15)
Proof. Since the assumptions are the same as those in Theorem F3
the results therein are all valid.
Furthermore, note that in the proof of Theorem F33 the following stronger variant of (F.14) can be obtained from 10.00::
Ovj-1
log 91+1 1og(2c) + log cj-1 + min 1 v. D+
logg).
(F.16)
fj-1
1 Vÿ-1
1+0,
Let a = (16 = ( 1)
Since A > v, then a > 0 and
9.
1
1
up
ie., a E (0,v). When Vz-1 2 a, we have
0
b/
min min
= min
v. D +
1 2/-1
U
+
2 min
v a- +1
=
40

---

From Theorem F33 we know Voc and when k -1 2 ko 1 2
log
(v- a) =
(1+o/2
(o)(u-n) the following inequality holds since E (0, 1| and
+ 17 > 1.
(1+2))))
( D) (1 + 2)((1
(1+ 11 2
Thus, for any k 2 ku, we have 8/ V, and
F16
log 9k
log(2c) + 0 blog ck-1 + (1 + v) loggk-1 9k-1
1 1+ ) log(2c) + flog cu + (1 2) log 91-1
Finally, the proof is completed by noticing that
up A-20
v(0-v) カーツĐ
G Additional numerical results on the CUTEst benchmark
This section provides a detailed description of the experimental setup and additional results on the CUTEst benchmark to supplement Section We implement our algorithm in MATLAB R2023a and denote the variant using the first regularizer in Theorem 2.2 as ARNCG g. and the variant using the second regularizer
ARNCG. We use the official Julia implementation provided by Hamad and Hinder [26] for their method CAT and Dussault et al. [16]ss 's official implementation for their method A ARC, K As the code for AN2CER is not publicly available, we investigate several ways to implement it in MATLAB and report the best results, as detailed in Section G.1
Our experimental settings follow those described by Hamad and Hinder 26 we conduct all ex- periments in a single-threaded environment on a machine running Ubuntu Server 22.04, equipped with dual-socket Intel(R) Xeon(R) Silver 4210 CPUs and 192 GB of RAM. Each socket is installed with three 32 GB RAM modules, running at 2400 MHz. The algorithm considered successful if terminates when c I 10 such that le < 10 If the algorithm fails to terminate within 5 hours, it is also recorded as a failure.
We evaluate these algorithms using the standard CUTEst benchmark for nonlinear optimization [22] Specifically, we consider all unconstrained problems with more than 100 variables that are commonly available through the Julia and MATLAB interfaces of this benchmark, comprising a total of 124 problems. The dimensions of these problems range from 100 to 123200.
G.1 Implementation details
ARNCG The initial point for each problem is provided by the benchmark itself. Other parameters of Algorithm | are set as follows:
# = 0.3, 3 0.5, - 1.0, 5, Mo and 7 0.01.
We consider choices for mmaxx
1. Setting m'mxx = so that at most 4 function evaluations per each iteration.
2. Setting Mimax = [log 10- $J to be the smallest integer such that (MT +1 > 10
In experiments, find that M/max works well, and the algorithm is sensitive to the above parameters, so we do not perform further fine-tuning. In the implementation of CappedCG, we do not keep the historical iterations to save memory. Instead, we evaluate (B.1) by regenerating the iterations. In practice, we observe that step (B.I) is triggered very infrequently, resulting in minimal computational overhead. The TERM state primarily designed to ensure theoretical guarantees
"See httttttss///gteee how.//aaaaaaaa///4/4/// CaA-0///AAT-Juuuaa
Adagrivelegularizzaiio... method
'See the ARCqKOp
in
https: http://hhhbbcoooo/uuuueetotttttp
for the Julia interface, and https
[gg.taa...co//ntccueeee///ttttte the MATLAB interface.
41

---

for Hessian-vector products in Section termination condition of CappedCG using the error ||ra|| < Ellll may not be appropriate for large |rol], we instead require satisfy |r=||| S min(g])roll, 0.01).
C3
and we find it is not triggered in practice. Since the
The fallback step in the main loop of Algorithm Tis mainly designed for theoretical considerations, as described in Theorem 3.1] It ensures that an abrupt increase in the gradient norm followed by a sudden drop does not compromise the validity of this lemma but results in a wasted iteration. However, we note that this condition can be relaxed to the following to enhance practical performance:
- > 9k and gl S >gk-1, for À E (0, 1)
(G.1)
When A = 1, this condition reduces to the original one. In our experiments, we explore the choices of X- = 1, À 0.01, and the impact of removing the fallback step (i.e., À = 0). Moreover, we note that when = O, the fallback step and the trial step are identical so the choices of A do not affect the results. In practice, we suggest setting a small À or removing the fallback step.
We also terminate the algorithm and mark as a failure if both the function value and gradient norm remain unchanged for 20 iterations or if the current search direction satisfies ||d& < x 10 or if the Lipschitz constant estimation satisfies Mr 2 10 as these scenarios may indicate numerical issues. Figure in the main text is generated under the above settings with À = 0 and mmax = 1.
For the Hessian evaluations, we only access it through the Hessian- products, and count the evaluation number as the number of iterations minus the number of the linesearch failures. Since when linesearch failure occurs, the next point is the same as the current point and does not increase the oracle complexity of Hessian evaluations.
AN2CER Our implementation follows the algorithm described in Gratton et al. [24] Section 2]. with parameters adopted from their suggested values. The algorithm first attempts to solve the regularized Newton equation using the regularizer VK,Ma If this attempt fails, the minimal eigenvalue Amin ( (V2 (V²))(x))) is computed. The algorithm then switches to the regularizer /Ma.ge |- 1-Amia(V><<xz )] when (V > KoVMMg.. and directly uses the corresponding cigenvector otherwise.
In AN2CER, the authors suggest using Cholesky factorization to solve the Newton equation and invoking the full eigendecomposition (i.e., the eig function in MATLAB) to find the minimal eigenvalue when the factorization fails. We observe that, in the current benchmark, it is more efficient to use CappedCG as the equation solver and compute the minimal eigenvalue using MATLAB's eigs function when NC is returned. This modification preserves the success rate and oracle evaluations of the original implementation while significantly reducing computational cost. We also note that there are several variants of AN2CER in Gratton et al. [24] and we find that the current version yields the best results among them.
G.2 Results on the CUTEst benchmark
Following Hamad and Hinder 26 we report the shifted geometric mear Hessian, gradient and function evaluations, well as the elapsed time in Tables 3 and [ In our algorithm, we define normalized Hessian-vector products as the original products divided by the problem dimension n, which can be interpreted as the fraction of information about the Hessian that is revealed to the algorithm; the linesearch failure rate is the fraction of iterations that exceed the maximum allowed steps maxx and the second linesearch rate measures the fraction of times the linesearch rule (D.12) is invoked. The medians of these metrics are provided in Tables 4 and 6 The success rate as a function of oracle evaluations is plotted in Figures 5 and 6 When an algorithm fails, the elapsed time is recorded as twice the time limit (i.c., 10 hours), and the oracle evaluations are recorded as twice the iteration limit (i.e., 2 x 10º). We note that the choices for handling failure cases in the reported metrics of these tables may affect the relative comparison of results with different success rates, although they follow the convention from previous works. Therefore, suggest that readers also focus on the figures for a detailed analysis of each algorithm's 's behavior.
'For dataset (a.) (a.)ejn) the shifted geometric mean is defined as exp (1 E log(as + 11). which accounts for cases where a;- 0.
42

---

The fallback parameter From Tables and 4 and Figure 5 we observe that the choice of the fallback parameter in (G.I) does not sigmihcantly affect the success rate, and the overall performance remains similar across different values of X. For larger X, the fallhack step is generally triggered more frequently (as indicated by the "fallback rate"), leading to increased computational time and oracle evaluations. Interestingly, ARNCG, with max = 1 seems an exception that À 1 is beneficial for specific problems and gives a slightly higher success rate.
The regularization coefficients Tables 5 and 6 and Figure 6 present comparisons for different values of 0. As increases, the performance initially improves but then declines. Larger 0 imposes stricter tolerance requirements on CappedCG (as indicated by the number of Hessian-vector products in these tables), and increases computational costs, while smaller may lead to slower local convergence. Thus, we recommend choosing [0.5, 1] to balance computational efficiency and local behavior.
We also note that this tolerance requirement is designed for local convergence and is not necessary for global complexity, so there may be room for improvement. For example, we can use a fixed tolerance when the current gradient norm is larger than threshold, and switch to the current choice min v MMgwk) otherwise. We leave this for future exploration.
Although ARNOG, has a slightly higher worst-case complexity (by double-logarithmic factor) than ARNCG,, they exhibit similar empirical performance, and in some cases, ARNCG, even performs better.
A potential failure case in practice for ARNCG, occurs when the iteration enters neighborhood with a small gradient norm and then escapes via a negative curvature direction. Consequently, ex stays small while gl may grow large, making the method resemble the fixed scenario. Interestingly, this same condition is also what introduces the logarithmic factor in ARNCG, theoretically.
The linesearch parameter Since our algorithm relies linescarch step, it requires more function evaluations than CAT for large mmax- evaluating the target function expensive, we may need to set a small mmax. even mmax O. Under the latter case, at most two tests of the line search criteria are performed, and the parameter M₁ is increased when these tests fail. Our theory guarantees that M3 O(LH). this choice remains valid. In practice, we observe that using relatively small Mmax gives better results.
Case studies for local behavior We present two benchmark problems that exhibit superlinear local convergence behavior. As illustrated in Figure 4 a larger gives faster local convergence. We only show the algorithm using the second regularizer in this figure, and note that the two regularizers
have similar behavior since in the local regime they reduce to Dt. ++0 -8 94-1- as shown in the last paragraph of the proof of Theorem E.4 Generally, it is hard to identify when the algorithm enters the
neighborhood for superlinear convergence. For HIMMELBG, the algorithm appears to be initialized near the local regime. For ROSENBR, the algorithm enters the local regime after approximately 20 iterations.
H Additional numerical results on physies-informeet neural networks
This section provides detailed description of the experimental setup and additional results on PINNs to supplement Section Our experimental settings follow those described by Rathore al. (47. and the code is adopted from their codebase, developed with Python 3.10.12. 12. All experiments are conducted on NVIDIA P100 GPUs with 16 GB of VRAM.
H.1 Problem setup
For a given domain Ω C CR", we can define the following partial differential equation (PDE):
{ Du = 0, x Ω, Bu = 0, x E 0n
(H.1)
where и denotes the solution to the equation, D differential operator, and B represents the boundary or initial condition operator. PINNs approximate the solution of the above PDE using
43

---

10a
10
10
gradient norm
10
gradient norm
10-26
10"
10
10
ARNOG, 10 = 0.0)
ARNOG, (0 0.0)
10-46
ARNCO, 10 = 0.3)
10-10
ARNCG, (0 0.5)
1.0)
20
30
number of iterations
number of iterations
Figure 4: Illustration of the local behavior of method the HIMMELBG (left plot) and ROSENBR (right plot) problems from the CUTEst benchmark for X = and max = 1. All methods converge the same point.
0.9
0.9
0.8
0.8
0.7
success rale
0.7
success rate
0.6
0.6
GAT
CAT
AN2CER
0.4
AN2CER
0.5
ARC,K
ARC,
ARNOG, (0 1.0, À 0.00)
0.3
ARNOO, (0 1.0, 0.00)
0.4
ARNOG, 10 1:0, 0.01)
ARNOG, (0 1.0, 0.01)
0.2
ARNOG, 00 1.0, 1.00)
ARNOG, (0 1.0, 1.00)
0.3
0.1
10
10a
10a
10
10
10a
10*
10P
elapsed time (s)
Hessian evaluations
0.8
0.8
0.7
success rate
sUccess rate
0.6
0.6
0.5
0.5
0.4
AN2CER
0.4
AN2CER
ARC,
ARC,K
0.3
ARNOG, (8 1.0, À 0.D0)
0.3
ARNOG, (0 1.0, 0.00)
ARNOO, (0 = 1.0, 0.01)
ARNOO, (0 1.0, 0.01)
0.2
ARNOG, 10 1.0. 1.00)
ARNOO, (0 1.0 1.00)
0.1
0.1
10'
10a
103
10
10
10'
10a
10a
10
10a
gradient evaluations
function evaluations
Figure 5: Comparison of success rates as functions of elapsed time, Hessian evaluations, gradient evaluations and function evaluations for solving problems the CUTEst benchmark. The fallback parameter À in G.I varies, and Mamax 1.
44

---

Table 3: Shifted geometric mean of the relevant metrics for different methods in the CUTEst benchmark. The fallback, second linesearch and linesearch failure rates are reported as mean values. The fallback parameter À in G varies.
Elupeed Time
Hessian Evaluations
Gradient Evaluations
Function Evaluations
Hessian-vector Products (normalzied)
Success Rate (%)
Linesearch Failure Rate (%)
Second Linesearch Rate (%)
Fallback (%)
AN2CER
36.70
170.10
172.02
176.80
31.38
81.45
N/A
N/A
NIA
CAT
23.34
88.47
96.61
125
N/A
85:48
NIA
NIA
NIA
A
119.51
Results for Muys
and 0
ARNCG, (A 0.00)
16.71
90.85
$6.41
119.51
13.77
87.10
16.08
1,38
0.00
ARNCG, (A- 0.01)
17.01
$1.46
87.31
120.48
13:90
87.10
15.98
1.31
0.33
ARNCO, (A 1.00)
99.01
14.52
ARNCG, (A 0.00)
18.28
85.03
90.78
125.29
14.91
86.29
16.89
0.43
0.00
ARNCG, (A 0.01)
18.39
85.03
90.78
125 125.29
14,91
86.29
16.89
0:43
0.00
ARNCG, (A 1,00)
18.04
78.40
89.41
122.41
14.22
87.10
16.03
0.46
6.10
Resulls for Plaas
[Joga 10
and 1.0
ARNCG, (A 0.00)
22.89
113.82
121.08
184.09
19.14
83.87
0.08
0.00
0.00
ARNCG, (A 0.01)
23.81
117.02
125.50
189.01
19.77
83.87
0.08
0.00
0.90
ARNCO, (A 1.00)
147,89
218.05
ARNCG, (A 0.00)
22.58
105.95
112.68
176.50
17.81
84.68
0.10
0.00
0.00
ARNCG, (A 0.01)
22.47
105.90 95
112.68
176. 176.50
17.81
84.68
0.10
0.00
0.00
ARNCG, (A 1.00)
25.80
118.41
137.31
214.58
20.79
83.06
0.29
0.00
9,94
Table 4: Median of the relevant metries for different methods in the CUTEst benchmark. The fallback parameter À in (G.I varies.
Klupoed Time (5)
Hessdan Evaluations
Gradient Evaluations
Function Exaluations
Hessian-vector Products (normalzied)
Success Rate (%)
Länesearch
Failure Rate (%)
Second Linesearch Rate (%)
Fallbnek Rute (%)
4.75
N/A
CAT
2,13
21.00
22
34.50
N/A
85.48
N/A N/A
N/A N/A
NIA
ARC,K
1,71
28.50
28. 50
32.00
0.62
87.10
N/A
Results for
and
ARNCG, (A
ARNCG, (A 0.01)
2.00
20.50
21.50
35.50
1.52
87.10
10.70
0.00
0.00
ARNCO, (A 1.00)
2.12
22.00
25.
40.00
1.92
87.10
6.75
0.00
0.00
ARNCG, (A 0.00)
1.72
21.50
22.50
38.00
1.62
86.29
10.26
0.00
0.00
(A 0.01)
22.50
1.62
ARNCG, ( 1.00)
1.99
21.00
24.50
38.00
2.01
87.10
9.92
0.00
0.00
Resalts for
[log, * and 1.0
ARNOG, (A 0.000
2.13
ARNOG, (A 0.01)
2.89
25.00
26.00
$3.00
2.34
83.87
0.00
0.00
0.00
ARNCG, (A- 1.00)
3.28
24.00
30.50
61.50
2.34
83.87
0.00
0.00
9.09
ARNCG, (A 0.00)
2.49
26.00
27.00
55.50
1.40
84.68
0.00
0.00
0.00
ARNOG, (A 0.01)
2.44
1.40
ARNEG, (A- 1.00)
2.90
25.00
30.50
69.00
1.58
83.06
0.00
0.00
8.33
neural network fe parameterized by 0, which is trained on the following residual-based loss function:
(0)) = [(Pfe(z)))
+ Tbb > (Bfooz)))
(H.2)
Tlyes 2m1
where { )rr C Ω and {at) tbe the domain, respectively.
i=1 C O2 denote points sampled from the interior and boundary of
Following Rathore et al. [47], the solution to the PDE is approximated using a fully connected neural network fo with width 200 and 3 hidden layers, comprising total of 81201 parameters in double precision. The activation function set to tanh, and Xavier initialization is applied [21]. The training data consist of Tlres 10 points uniformly sampled from mesh over the domain, where the mesh contains 101 and 257 uniformly spaced points along the t-axis and r-axis, respectively. The test data contains all points in this mesh. Since Rathore al. [47] adopted the randomized Nyström method 20 to construct preconditioners and accelerate the CG computation, we also incorporate ensure fair comparison.
We consider the three types of problems for training PINNs as in Rathore al. forms are given below:
47 Their specific
45

---

0.9
0.8
0.8
0.7
0.7
success rate
0.6
success
0.6
0.5
AN2CER
ANZCER
0.5
ARC,K
ARC,
ARNOG, (8 0.0)
0.3
ARNOG, (6 0.0)
0.4
ARNOO, 10 0.5)
ARNOG, (8 0.5)
ARNOG, (0 1.0)
ARNOO, (6 1.0)
0.3
0.1
10a
10a
10a
10a
10
10a
10a
10a
10
10
elapsed time (s)
Hessian evaluations
0.9
0.9
0.8
0.8
0.7
0.7
success rale
sUccess rate
0.6
0.5
GAT
0.5
CAT
0.4
AN2CER
AN2CER
ARC,K
ARC,K
0.3
ARNOO,
0.3
ARNOG,
0.0)
ARNCG,
ARNOG,
0.2
0.2
ARNOG,
ARNOG,
0.1
0.1
10a
10a
103
10
10
10a
10a
10a
10*
10a
gradient evaluations
function evaluations
Figure 6: Comparison of success rates functions of elapsed time, Hessian evaluations, gradient evaluations and function evaluations for solving problems in the CUTEst benchmark. The parameter 0 in Theorem 2.2 varies, and the fallback step is removed, i.e., À in (G.I. and mmmx 1.
Table 5: Shifted geometric mean of the relevant metrics for different methods in the CUTEst benchmark. The linesearch failure rate is reported as mean values. The parameter 0 in Theorem 2.2 and the linesearch parameter m'aa vary, and À 0.
Hessian-vector Products (normalzied)
Linesearch
Second
Elapsed Time (9)
Gradient Evaluations
Function Evaluations
Success Rate (%)
Evaluations
Failure Rate (%)
Lineserch Rate (%)
AN2CER
36.70
170,10
172.02
176.80
31.38
81.45
NIA
N/A
CAT
23.34
88.47
96.61 113.84
125.56
N/A
85.48
NIA
N/A
A
113.21
119.51
11.97
87.10
N/A
Resulls for Menn and
Fixed (w) v
48.10
215.60
228.47
386.84
43.97
80.65
26.12
4.73
ARNOG,
0.0)
ARNOG, (0 0.5)
18.62
87.10
92.89
126.92
14.85
$6.29
15.48
1.31
ARNCU,
13.77
ARNCG, (0 1.5)
19.22
87.83
93.84
129.00
15.29
86.29
15.38
1.58
ARNCG, (0 0.0)
129.71
15.28
15.49
0.50
ARNCG, (0 0.5)
18.84
90.44
96.42
129.85
15.73
85.48
15.69
0.31
ARNCG, 1.0)
ARNCG, (0 1.5)
22.65
104.83
111.81
151.03
18.83
83.87
16.05
0.42
Results for Whnase
[log, 10
and
(2)
ARNOG, (9 -8=00 0.0)
27.64
143.93
152.
213.62
23.
83
0.13
0.00
ARNOG, 0.5)
ARNOG, (0 1.0)
22.89
113.82
121.08
184.09
19.14
83.87
0.08
0.00
ARNCU, @0
84.68
ARNCG. @0 0.0)
22.09
113,33
120.03
179.29
18.35
83.87
0.09
0.00
ARNCG, (9 0.5)
23,12
122.82
184.87
19.58
ARNCG, (0 1.0)
22.58
105.95
112.68
176.50
17.81
84.68
0.10
0.00
ARNCG, 1.5)
46

---

Table 6: Median of the relevant metrics for different methods in the CUTEst benchmark. The
parameter 0 in Theorem 2.2 and the linesearch parameter Mmxx vary, and X = 0.
Elapsed Time (8)
Hessian
Gradient Evaluations
Function Evaluations
Hessian-vector Products (normalzied)
Success
Linesearch
Second Linestarch Rate (%)
Failure Rate (%)
ANZCER CAT ARC,K
4.75
4.24
81.45
2.13
21.00
22.00 28.50
34.50 32,00
N/A
85.48
NIA
N/A
1.71
28.50
0.62
87.10
NIA
N/A
Results for Whmax and À 0
Fixed Cale vT)
10.75
7.29
80.65
0.00
ARNOG, (0 0.00
2.04
22.50
23.50
37.00
1.52
84.68
1.72
0.00
ARNCU, (0 0..5)
1.77
20.00
21.00
34.00
1.52
86.29
9.52
0.00
ARNOG, (0 1.0)
1.89
20.50
21.50
35.50
1.52
87.10
10.82
0,00
ARNCG, 1.5)
86.29
ARNCG, (0 0.0)
1.81
20,00
21,00
35,00
1.61
85,48
3.65
0.00
ARNCG, (0 0.5)
191
20.00
21.00
35.00)
1.74
85.48
7.12
0.00
ARNCG, (0 1.0)
1.72
21.50
22.50
38.00
1.62
86.29
10.26
0.00
ARNCG, (# 1.5)
22.00
1.93
83.87
10.00
Results for Manas
[logg 10 and
Fixed (e) v23)
12.27
39.50
40,50
323,50
7,59
80.65
0.00
0.00
ARNOG, (0 -0 0.00)
3.49
25.50
26.50
53,50
1.95
83.06
0.00
0.00
ARNOG, 00 0.5)
2.37
24.00
25,00
52.50
1.35
85.48
0.00
0.00
ARNCO, (0 1.0)
2.84
25.00
26.00
53.00
2.13
83.87
0.00
ARNCG, (0 1.55
2.73
26.00
27.00
54,00
2.10
84.68
0.00
0.00
ARNCG, (0 0.0)
2.74
23.00
24.00
49.00
1.44
83.87
0.00
0.00
ARNCG, (0 0.5)
2.31
24.00
25,00
$3.50
1.43
83.06
0.00
0.00
ARNCG, (0 1.0)
2.49
26.00
27.00
55.50
1.40
84.68
0.00
0.00
ARNCG, (0 1.5)
2.86
25.50
26.50
55.50
2.10
83.06
0.00
0.00
Convection problem defined
This equation models physical phenomena such as heat conduction, and
0.u + 30,u u = 0, u(x,, 0) = sin I m(0,t) u(2 t),
(ær, I) E (0, 2T) x (0,
x E [0, 2m), E [0, 1].
In the experiments, the convection coefficient is set to 40.
Reaction problem
This equation models chemical reaction dynamics, and is given by:
8,u - pu(1 u) = O, u(x, 0) = exp 8(z-x)} (0, = uu2TT,t E),
(x, t) E (0, (m,)m) x (0, 1).
x E 2m).
t E [0, 1].
The parameter is set to 5 in the experiments.
Wave problem This equation commonly used describe wave phenomena such acoustic and electromagnetic wave propagation:
og 482 u(x, 0) sin(xT) + (in()))))
(x, E (0, 1) x (0, 1),
x E [0, 1].
0,m(2, 0) = 0,
x E [0, 1).
uu0,t)) = u(1,t) =
te 0. 1).
In the experiments, the parameter is set to B 5.
H.2 Results
As suggested by Rathore et al. 47 we adopt the following training strategy: the neural network
first trained using Adam for / iterations, followed by L-BFGS for 12 iterations, and finally switched to NNCG or ARNCG,- Since the per-iteration cost of RNMs varies significantly, we terminate training based fixed time budget rather than fixed iteration count. The time limit is chosen
47

---

Table Average training loss and L2RE on training PINNs over runs.
Convection
Reaction
Wave
NNCG,.
3.35 x 10-7
3.03#0.76 x 10-7
4.52 x 10-3
Training Loss
N1
8.90 x 10
5.20#1.11 x 10-
2.79
10
ARNCG,
7.57 4..93 x 10 10
2.04 x 10
1.75.0.50 x 10
NNCGg.1
2.85+0.37
10-3
1.09#0.12
10-2
1.26#0.26
10
Test L2RE
NNCG
1,42#0.21 x 10
4.81
x 10-3
8.82+241
x 10
ARNCG
6.82+2.31
10-5 5
8.54 x 10
6.96#0.61 x 10
such that ARNCG, performs approximately 2000 iterations. We set 1000 and 12 2000 for the wave and reaction problems, and 1 11000 and 12 1500 for the convection problem. The corresponding time budgets are reported in the captions of Figure Each experiment is repeated times with different random seeds.
For NNCG, we evaluate two regularization coefficients, E (0.1,0.01) 0.01), and denote the correspond- ing variants as NNCG,, which were shown to perform best in practice [47]. The parameters for ARNCG, follow the setup described in Section G.1 with 6 1, [log, mmax 10-4, and 7 This adjustment to the linesearch parameter is motivated by the relatively high computational cost of each iteration; using a smaller Mmax would result in several wasted effort during updates of the Lipschitz estimate M..
The training loss curves shown in Figure while the average and best performance across are summarized in Table 7 ARNCG, consistently outperforms NNCG by a large margin across all problems. We also emphasize that these RNMs do not require storing the full Hessian matrix or any matrix of comparable size, resulting in significantly lower memory usage compared to quasi-Newton methods such BFGS and the Broyden method [52]. For example, the peak GPU memory usage for the convection, reaction and wave problems is 4.7GB, 3.3GB and 10.2GB, respectively.
"The L2RE in these tables means the relative error. Given prediction y R and the groundtruth
E IR" this emror is defined by 1-=
48

---

ARNCS
NNCG, NNCG. ARNOG,
NNCQ..1
10
10
NNCO..01
training loss
training loss
ARNOG,
10
10
10-6
10-9
10-9
10-9
5000
10000
15000
20000
25000
5000
10000
15000
20000
elapsed time (s)
number of iterations
Convection problem. Adam (1Ik) L-BFGS (1.5k) NNCG ARNCG (7.5 hours)
L-8FOS
NNCG /RNCG
10a
10a
NNCG,.1 ARNOG,
NNCG
on
NNCG..0
training loss
10-1
training loss
10
ARNOG,
10-7
10-7
2000
4000
6000
2000
4000
6000
SU00
elapsed time (s)
number iterations
(b) Reaction problem. Adam (Ik) B-GSS (2k) NNCG ARNCG hours)
Adam
L-FGS
NNCG/ ARNOO
10
10"
NNCG
NNCG,.
NNCG...)
NNCG..0L
training loss
ARNOG,
training loss
ARNOG,
10-2
10-2
20000
40000
60000
1000
2000
3000
4000
5000
elapsed time (s)
number iterations
(c) Wave problem. Adam (1k) L-BFGS (2k) NNCG/ ARNCG (18 hours)
Figure 7: Loss curves for training PINNs. The numbers in parentheses for Adam and L-BFGS indicate the number of iterations, while those for NNCG / ARNCG denote total wall-clock time, which is selected such that ARNCG performs approximately 2k iterations. The subscript in NNCG denotes the regularization coefficient. Thin lines are independent runs; the bold line shows the average.
49

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: They discussed in the abstract and the introduction. Further discussions are also presented in Section A. for interested readers.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Section A.2
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
50

---

Answer: [Yes]
Justification: Please see Section 3 for an overview and the appendix for the complete proofs. The assumption can be found in Section 2.1
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Sections and
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
51

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code will released when the paper becomes publicly available, either as arXiv preprint upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ httpppscccppbllccguuudoooo Coaee///ddeSSbbbmmma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Sections G and
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Experiments on the CUTEst benchmark are deterministic; experiments on PINNs report the standard deviation in Table 7
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
52

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Sections Hnd
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We confirm it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Section A.3
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
53

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not see such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have cited the original paper and related GitHub links.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
54

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will provide it together with the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
55

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
56


Reviews:
[{"review_id": "6joikCuU99", "reviewer": "Reviewer_MUHH", "summary": "In this submission, the authors propose a novel regularized Newton’s method and demonstrate that two classes of regularizers can achieve both optimal global convergence rates and quadratic local convergence. These new regularizers are constructed using current and historical gradient information, and the authors employ the conjugate gradient method with negative curvature to solve the regularized Newton equation. Notably, the proposed algorithm requires no prior knowledge of the Hessian Lipschitz constant while simultaneously attaining optimal global complexity and quadratic local convergence. Empirical results from numerical experiments align well with the theoretical analysis.", "questions": "Could the authors conduct numerical experiments on simpler or toy objective functions, in addition to the more complex non-convex problems? Currently, the results focus on challenging benchmarks such as the CUTEst suite and physics-informed neural networks. While these are valuable examples of non-convex problems, the reviewer is interested in seeing how the proposed algorithm performs on much simpler non-convex functions—for example, a quadratic function with an indefinite Hessian matrix. Such experiments would provide clearer intuition about the behavior and effectiveness of the proposed regularized Newton’s method, complementing the results on more complicated deep neural network models.", "limitations": "The authors has presented some limitations in last discussion section of this submission. Please check the other weakness section for all limitations of this submission.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This is a high-quality theoretical optimization submission with a clear structure and well-written language. It offers two notable theoretical contributions to second-order Newton’s methods:\n\n1. The proposed algorithm is adaptive and parameter-free, meaning it does not require any prior knowledge of the Hessian Lipschitz constant or other parameters. All assumptions are clearly stated in Assumption 2.1, which is relatively simple. This provides a practical advantage over other algorithms that require parameters of the objective function, which can be difficult to estimate in real-world applications.\n\n2. The proposed regularized Newton’s method simultaneously achieves optimal global complexity and quadratic local convergence rates, making it a standout contribution. Combined with its parameter-free nature, this algorithm is both theoretically significant and practically applicable to general non-convex optimization problems.\n\nFurthermore, the authors validate their theoretical claims through numerical experiments on problems such as physics-informed neural networks, with empirical results consistent with the theoretical analysis.\n\nWeaknesses:\n\n1. Although the iteration complexity is clearly stated, the paper should provide more detailed analysis of the computational complexity per iteration, particularly regarding the computational cost of the capped conjugate gradient method used in the algorithm. While the oracle complexity is presented in Theorem 2.3, some of the oracle complexity discussion currently in the appendix should be moved to the main text to improve accessibility.\n\n2. The authors should clarify and be more specific in Theorem 2.2 regarding the local quadratic convergence rates. Instead of the Big-O notation $g_{k + 1} = \\mathcal{O}(g_k^2)$ it would be helpful to present the exact form of the local quadratic convergence rate. Additionally, the precise size of the neighborhood where quadratic convergence occurs and the number of iterations required to reach this neighborhood should be clearly stated.\n\n3. In the numerical experiments, it is recommended that the authors compare the proposed Adaptive Regularized Newton-CG method against established quasi-Newton methods such as BFGS, DFP, SR1, and L-BFGS. Moreover, conducting experiments on both convex and non-convex problems would provide a more comprehensive assessment of the algorithm’s performance across different settings.\n\nIn summary, this submission is a high-quality optimization paper and deserves a publication.", "was_revised": true, "final_justification": "Based on the rebuttal, I retain my current score.", "rebuttal": "We thank reviewer MUHH for the valuable comments.\n\n> Weakness 1: the computational complexity and oracle complexity\n\nThank you for the helpful suggestions. The overall computational complexity can be viewed as the product of the number of HVP evaluations (Thm 2.3) and the cost of each HVP evaluation, which is typically fixed and does not vary across iterations. We will clarify this point and move the discussion of oracle complexity accordingly in revision.\n\n> Weakness 2: the exact version of local convergence and the size of the neighborhood\n\nThe non-asymptotic statement of the local convergence is presented in Prop E.4 in appendix. We will move it to the main text. For the size of the local convergence neighborhood, some discussions are presented before Lem 3.7. Its size depends on two factors: (1). the assumption of the solution, i.e., $L_H I \\succeq \\nabla^2 \\varphi(x^*) \\succeq \\alpha I$. Since our regularizer is at most $g_k^{0.5}$, the local convergence rate is at least 1.5 and its neighborhood does not depend on $\\theta$; (2). the parameter $\\theta$. When entering the neighborhood with 1.5 local rate, it can be boosted to 2 within $O(\\log\\log poly(L^\\theta_H, U_\\varphi^\\theta))+ 2\\log \\frac{2\\theta-1}{2\\theta-2}$ steps.\n\n> Weakness 3 and Question: the comparsion with simper problems and quasi-Newton type methods.\n\nThanks for your suggestions. The CUTest benchmark also includes a subset of simple functions, e.g., the Rosenbrock's banana function $f(x, y) = (a - x)^2 + b(y - x^2)^2$. There is an illustrative figure in Fig. 4 in p.42. We will clarify this point in the text surrounding the figure. \n\nWe note that in prior work on Newton-type methods evaluated on the CUTEst benchmark, quasi-Newton methods such as BFGS, DFP, and SR1 are typically not included for comparison, as they represent a different class of algorithms with distinct convergence properties and design goals. In our case, the focus is on methods that explicitly leverage second-order information.\n\nNevertheless, we do compare against L-BFGS in the PINN experiment, where it is commonly used in practice. Other quasi-Newton methods such as BFGS and SR1 are less applicable in this setting due to their high memory requirements, as they need to store dense matrices of the same size as the Hessian, which becomes impractical for large-scale problems like PINNs."}, {"review_id": "UmmVOHSgGM", "reviewer": "Reviewer_hnj5", "summary": "This paper seeks to create a parameter-free algorithm that achieves optimal convergence rates, both locally and globally.  They propose a new class of regularizers based on gradient information and leverage a CG approach with potential early exit if negative curvature information is detected.  Their algorithm leverages the “Capped CG” approach that is essentially CG that additionally exits with negative curvature conditions either if detected explicitly or convergence rates are detected to be too slow, in which case the CG iterates are regenerated to find negative curvature (B1 page 17).  It may also terminate if the convergence of CG exceeds the theoretical threshold denoted by $J(M, \\bar\\rho, \\xi) + 1$.  An addition LipEstimation function is used to improve the estimate of the Lipschitz factor M that is either increase by a factor of $\\gamma$ or decreased by a factor $1/\\gamma$.\nTheir algorithm is described in “Algorithm 1” where the function NewtonStep is called potentially twice, first with a trial step and if the step returns FAIL, a fallback step is used.  The heart of NewtonStep is CappedCG based on Royer [49].  Additionally, it provides the choice regularized based on the estimate of $ L_H$,$ M$, as well as $\\omega_k$ based on past gradient norms.  They seek to balance the need for the regularization to be proportional to $\\sqrt(g_k)$ far from the solution but smaller than $g_k$ when close.  That is, unmodified Newton’s method without a regularizer would ideal if near a positive-definite solution point.  So in a sense the regularize must converge at a much slower rate until sufficiently close to a solution.  So the magic is to detect that the algorithm is behaving like it is sufficiently close or far while balancing that fact that the estimate of $L_H$ itself maybe part of the problem.\nAfter CappedCG, post processing handles the CG converged cases, versus max iteration and/or negative curvature found. They provide the option for a back-tracking like line search to find $\\beta^m$ where $m$ is an integer as close to $0$ as possible to get the desired decrease.  In practice, it seems that $m_{max} = 1$ works, indicating the machinery of the algorithm is correctly balancing the step.  (If larger values of $m$ were needed, this would hint that the direction was too large and the system was not sufficiently regularized for the current location.)\nThey provide comprehensive theoretical convergence proofs as well as numerical results with some CUTEr problems and a physics-informed neural network.", "questions": "Is it possible to clarify the algorithm and make it easier to follow, as done by some of the earlier links?  I needed to jump around a lot to follow.\n\nFor the CUTEr problems, I think it is important to compare to a simple shifted Steihaug-Toint variant and explicitly report the number of iterations, evaluations, and matrix-vector products in a table, or reference such tables from similar papers.  \n\nI think the paper has a lot of strong results, but it is just too long for an article of this length.  Is it possible to lay out the information for better clarity, making it less necessary to flip back and forth from the appendix to the starting page?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Weakness and Strength\nThe paper has an impressive amount of theory backing and seems to achieve its goals of proving desire convergence theoretical bounds for the proposed algorithm.  The numerical results hint that the method is competitive against similar algorithms in this genres.  It provides sound/comprehensive algorithms for generating steps, determining the regularization sequence sizing, accounting for negative curvature, and improving the estimate for $L_H$.  It is sufficiently balanced in that, according to page 40, 1123, the choice of $m_{max}=1$ seems to work well, implying that the algorithm often can take full steps along the generated direction.  The algorithm has a good number of hyperparameters; it appears that very little tuning was needed, and good default values are known.\n\nUltimately, I think this is a great paper for an optimization journal where significantly longer lengths are permitted.  The algorithm and ingredients is sufficiently complex and interdependent that paper is not comprehensible without going deep into the appendix. Algorithm 1 is itself based on CappedCG and LipEstimation, defined in the appendix, which are critical players to understand the algorithm. The Appendix itself ends on page 48 and the material is not supplemental but critical to the entire paper.  Thus this is not a 9 page paper but a much larger optimization paper that has essentially moved its body to the index.\nLastly, the algorithm seems overly complex for what it is attempting.  It is essentially using CG algorithm with early exits if negative curvature is detected.  It seems a cubic regularized variant of shifted Steihaug-Toint algorithms that behave very similarly: https://optimization-online.org/wp-content/uploads/2004/09/960.pdf and work well for the CUTEr problems, as does Steihaug-Toint itself: https://epubs.siam.org/doi/10.1137/0720042.  The method seems similar in nature to papers like this: https://arxiv.org/pdf/2311.11489 .", "was_revised": true, "final_justification": "The ST method is simple to implement and I think important to compare to. Also detailed tables s hard to beat and I would still need to see detail results as suggested: explicitly report the number of iterations, evaluations, and matrix-vector products in a table, or reference such tables from simil\"ar papers.\"", "rebuttal": "We thank reviewer hnj5 for the valuable comments.\n\n> Q1: the clarity of this article.\n\nThank you for the valuable suggestions. If the paper is accepted, an additional page becomes available. We plan to include the `LipEstimation` procedure in the main text. The `CappedCG` component is a slight modification of the method by Royer et al., so we can present a brief (informal) version to convey its main idea. We believe these changes, along with the intuitive explanations and high-level overview in Sec 2.1, would improve clarity and make the algorithm easier to follow.\n\n> Q2: the comparsion with the shifted Steihaug-Toint variant in the CUTest benchmark\n\nThank you for the suggestion. In our experiments, we selected recent methods from the categories of trust-region methods (CAT), cubic regularization methods (ARCqK), and quadratic regularization methods (AN2CER). According to the results reported in  ARCqK, it is “more efficient than a classic Steihaug–Toint trust-region method.” We believe this comparison is representative, and we will clarify it in the revised version.\n\n> Q3: The method seems similar in nature to papers like this: [https://arxiv.org/pdf/2311.11489](https://arxiv.org/pdf/2311.11489)\n\nThere are some notable differences. Jiang's method is a trust-region type algorithm with a quadratic regularization parameter $\\sigma_k$ and an additional free parameter: the trust-region radius $r_k$.\n\n- For the local convergence rate, as shown in their Tab 2, they first check whether the scale of the minimum eigenvalue of the Hessian is sufficiently large. If so, they set $\\sigma_k = 0$ and use the trust-region constraint purely as a globalization mechanism. Under a local convexity assumption, this effectively reduces to the classical Newton method near the solution, allowing for a quadratic convergence rate. However, this strategy requires an additional eigenvalue check and is not directly applicable to regularized Newton methods (RNMs), which rely solely on a regularization parameter. As a result, achieving a quadratic rate is more challenging for RNMs.\n- For the global convergence rate, their global analysis relies on partitioning iterations into successful and unsuccessful sets, similar to the approach described in our Sec 2. This leads to an extra multiplicative $\\log(1/\\epsilon)$ factor in the complexity bound. In contrast, our new partitioning technique introduced in Sec 3, along with the second choice of regularization coefficients in Thm 2.2, eliminates this additional factor. We believe our new partitioning rule can also improve their log factor to $\\log \\log (1/\\epsilon)$."}, {"review_id": "GflUWzLQUi", "reviewer": "Reviewer_9yAV", "summary": "This paper introduces an adaptive Newton’s method that achieves both global and local convergence. In general, optimization algorithms require different hyperparameter settings to ensure global versus local optimal convergence, and these settings are often heuristic and not known in advance. The proposed method addresses this challenge by introducing a regularization term delta_k, which adaptively monitors the algorithm’s behavior to balance global and local convergence. This adaptive scheme enables the algorithm to achieve optimal performance in both regimes, in contrast to previous methods that rely on fixed hyperparameters.", "questions": "**Questions:**\n\n(1) When training deep neural networks, how to handle the Hessian matrix? In general, the exact computation of Hessian on the full batch is difficult. Do you use Hessian-free (Hessian-vector products) methods or quasi-Newton methods that does not use the exact Hessian? Or do you adopt lazy Hessian?\n\n(2) Can the algorithm be extended to be stochastic? Most of machine learning problems may require mini-batch sampling. What is the theoretical convergence guarantees?\n\n(3) In Figure 2, ARC and ANRCG performs comparably. Can you please explain? I think ARC is an adaptive version of CR, which also enjoys the (optimal) global and local convergence. The idea of ANRCG should be similar to ARC, am I correct? I also know another parameter-free Newton’s method (https://arxiv.org/abs/2311.11489) that enjoys global and local convergence, can you discuss? I guess the core idea should be very similar.\n\n(4) What are the theoretical convergence results if without Lipschitz smoothness? Is it possible?", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength:**\n\n(1) The algorithm is an adaptive Newton-CG, which is both locally and globally convergent. The technique is intuitively convincing.\n\n(2) Theoretical analyses are thorough and rigorous, including the results in the main content and appendices.\n\n(3) Experiments are comprehensive, including CUTEst and PINNs.\n\n**Weaknesses:**\n\nThe method requires the computation of exact Hessian matrix.", "was_revised": true, "final_justification": "I recommend borderline accepting the paper.", "rebuttal": "We thank reviewer 9yAV for the valuable comments.\n\n> Q1: When training deep neural networks, how to handle the Hessian matrix? In general, the exact computation of Hessian on the full batch is difficult. Do you use Hessian-free (Hessian-vector products) methods or quasi-Newton methods that does not use the exact Hessian? Or do you adopt lazy Hessian?\n\nOur algorithm only relies on the Hessian-vector products (HVPs), which makes the computational and memory costs relatively modest (see Tab 2). Besides, PyTorch supports HVP computation well, so it does not introduce many implementation overhead.\nWe do not adopt the lazy Hessian, but it may be a promising direction for future work.\n\n> Q2: Can the algorithm be extended to be stochastic? Most of machine learning problems may require mini-batch sampling. What is the theoretical convergence guarantees?\n\nThanks for your questions. We think it can be applied to stochastic settings empirically without theoretically guarantees.  The main challenge lies in the estimation of the Lipschitz constant and the line search procedure, both of which require evaluations of the full objective function. It is not immediately clear how the method behaves when these are replaced with their stochastic counterparts. As discussed in Sec 5, we leave it as a future work.\n\n> Q3: ARC and ARNCG, and Jiang's TR (2311.11489)\n\n1. Relationship to ARC: ARC is an adaptive CR, but there are important differences to our method. The core step of ARC is to minimize a cubically regularized subproblem, which can also be viewed as  solving a regularized Newton equation $(\\nabla^2\\varphi(x) + \\rho I)d = -\\nabla \\varphi(x)$, where $\\rho \\propto \\sigma \\| d \\|$ depends on the solution $\\|d\\|$. A key step of ARC is to search an appropriate value of $\\rho$, while our method uses a prescribed coefficient $\\rho$ that does not depends on the solution $d$, which avoids the search step.\n\n2. Relation to Jiang's trust-region method: Jiang's method is a trust-region type algorithm with a quadratic regularization parameter $\\sigma_k$ and an additional free parameter: the trust-region radius $r_k$.\n\n   - For the local convergence rate, as shown in their Tab 2, they first check whether the scale of the minimum eigenvalue of the Hessian is sufficiently large. If so, they set $\\sigma_k = 0$ and use the trust-region constraint purely as a globalization mechanism. Under a local convexity assumption, this effectively reduces to the classical Newton method near the solution, allowing for a quadratic convergence rate. However, this strategy requires an additional eigenvalue check and is not directly applicable to regularized Newton methods (RNMs), which rely solely on a regularization parameter. As a result, achieving a quadratic rate is more challenging for RNMs.\n   - For the global convergence rate, their global analysis relies on partitioning iterations into successful and unsuccessful sets, similar to the approach described in our Sec 2. This leads to an extra multiplicative $\\log(1/\\epsilon)$ factor in the complexity bound. In contrast, our new partitioning technique introduced in Sec 3, along with the second choice of regularization coefficients in Thm 2.2, eliminates this additional factor. We believe our new partitioning rule can also improve their log factor to $\\log \\log (1/\\epsilon)$. \n\n> Q4: What are the theoretical convergence results if without Lipschitz smoothness? Is it possible?\n\nIt may be possible to relax the assumption to $\\nu$-Holder continuous one. Under this assumption our Lem 3.7 and its refined version in App F.2 guarantees that $\\theta > \\nu$ gives a best possible local rate $1 + \\nu$. However, to obtain an optimal global rate we may need to modify the Lipschitz estimation rule and dynamically estimate the Holder exponent $\\nu$, which needs further efforts and we leave it as the future work."}, {"review_id": "46WIZuburI", "reviewer": "Reviewer_cCif", "summary": "The authors focus on regularized Newton methods, which are widely studied yet still face a trade-off between global and local convergence. A key open question is whether a parameter-free algorithm can achieve both optimal global complexity and quadratic local convergence. To tackle this issue, the authors propose a regularizers using current and previous gradients, and apply a conjugate gradient approach with a negative curvature monitor to solve the regularized Newton equation. The algorithm is adaptive and does not require prior knowledge of the Hessian Lipschitz constant. The proposed method achieves a global complexity of $O(\\epsilon^{-\\frac{3}{2}})$ in terms of second-order oracle calls and $\\tilde{O}(\\epsilon^{-\\frac{7}{4}})$ for Hessian-vector products. When the iterates converge to a point where the Hessian is positive definite, the method demonstrates quadratic local convergence. Preliminary numerical results highlight the competitiveness of the proposed algorithm.", "questions": "- In Table 1, why is the $\\tilde{O}(1)$ term missing from the iteration complexity corresponding to He et al. [29, Theorem 1]? From the regularization coefficient, it seems they also assume a lack of prior knowledge about $L_H$ and make an estimate accordingly. Additionally, the phrase \"$\\epsilon$ is used in the regularization coefficient or minimal eigenvalue computation\" is unclear. Could the authors briefly explain why $\\epsilon$ is involved in these two places? A simple clarification here might enhance the readability.\n- In line 13 of Algorithm 1, is there any theoretical guarantee for the value of $\\alpha$? Could the authors provide more insight into this?\n- Another point of interest is whether the value of $\\theta$ in the algorithm could be adaptively selected rather than using a constant value throughout the entire algorithm? This could potentially improve performance.\n- It appears that ARC$_q$K shows excellent time efficiency in most experiments. However, while the authors mention using slightly fewer Hessian evaluations in line 306, it does not seem to result in a better time efficiency. Could the authors further emphasize the practical advantages of the proposed algorithm compared to other methods, particularly in real-world applications? Highlighting these advantages will help readers understand the practical utility of the algorithm better.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- The overall structure of the paper is clear and well-organized, with a thorough literature review.\n- The explanation of the overall algorithmic process is comprehensive, allowing readers to clearly follow the algorithm's workflow. Additionally, although I have not thoroughly checked every step of the proof, it appears that the theoretical justifications are detailed and rigorous, providing solid theoretical guarantees.\n- The paper introduces an adaptive Newton-CG algorithm, which cleverly detects the local region in practice. This enables the algorithm to adaptively balance the trade-off between global convergence and local convergence.\n- The design for solving the Newton equation for subproblems is innovative, allowing for a cost-effective way to determine the presence of negative curvature directions.\n- The experimental setup is detailed, with numerous experiments conducted to validate the effectiveness of the proposed algorithm.\n\n### Weaknesses:\n- Some of the symbols in the paper need clearer explanations. For example, the meaning of the symbol $\\lesssim$ is not explained. Although line 87 mentions \"The notations... are used in their standard sense to represent asymptotic behavior,\" a more detailed explanation would help readers who are not familiar with complexity theory.\n- On line 260, \"lemma\" should be \"proposition\". Additionally, on line 272, the definition of $\\alpha$ should be provided. On line 303, there is a missing space before the final \"and\" in the sentence. Lastly, on lines 951 and 956, the formulae should end with a comma instead of a period.\n- The paper is somewhat lengthy. Although this is done for theoretical completeness, it makes the review process for a conference submission more difficult.", "was_revised": true, "final_justification": "The authors have addressed my concerns, and I will keep my initial score.", "rebuttal": "We thank reviewer cCif for the valuable comments.\n\n> Weakness 1. Some of the symbols in the paper need clearer explanations. For example, the meaning of the symbol  is not explained. Although line 87 mentions \"The notations... are used in their standard sense to represent asymptotic behavior,\" a more detailed explanation would help readers who are not familiar with complexity theory.\n\nThanks for your suggestions, we will add these explanations in revision.\n\n> Weakness 2. On line 260, \"lemma\" should be \"proposition\". Additionally, on line 272, the definition of  should be provided. On line 303, there is a missing space before the final \"and\" in the sentence. Lastly, on lines 951 and 956, the formulae should end with a comma instead of a period.\n\nThanks for your suggestions, we will fix them in revision.\n\n> Weakness 3. The paper is somewhat lengthy. Although this is done for theoretical completeness, it makes the review process for a conference submission more difficult.\n\nThank you for the feedback. While we acknowledge that the paper is somewhat lengthy due to the theoretical completeness, we have made an effort to highlight the main ideas and intuitions in the main text. The technical details and extended discussions are deferred to the appendix to maintain the flow of the core narrative. We believe this structure strikes a balance between accessibility and rigor. We are also open to reorganizing or condensing the material further in the final version to improve readability. For example, moving the key ingradient `LipEstimation` of the algorithm to the main text.\n\n> Q1: Clarification about Tab 1.\n\n1. In their method, the Lipschitz constant estimator $M_k$ is determined through an inner iteration. However, in Table 1, we report only the number of outer iterations of their algorithm, which is why the $\\tilde{O}(1)$ term is omitted. Each inner iteration involves solving a regularized Newton equation, and as shown in their Theorem 4 (specifically Eq. (29)), this introduces an additive $O(\\log L_H)$ factor due to the constant $T = O(\\log L_H)$ (see their Eq. (25)). In contrast, each iteration of the other compared methods solves only one regularized Newton equation.\n\n2. As an example, in Royer's method they choose the regularizer to be fixed $\\sqrt{\\epsilon}$, which directly gives a sufficient descent $O(\\epsilon^{1.5})$ _at every iteration_, but such a choice is not adaptive and may degrade  empirical performance when the tolerance parameter $\\epsilon$ is small (as shown in the \"fixed \\omega$ case of our experiemnt). The advantage of this choice is that it may simplify the theoretical analysis and give an iteration complexity without a multiplicative log factor. On the other hand, \"ME\" represents the algorithm needs to compute the minimal eigenvalue to determine some parameters, e.g., the regularizer. We will clarify them in the table.\n\n\n> Q2: The choice of $\\alpha$ in Alg 1, L13.\n\nIt is based on a observation that in Lem D.3(1), choosing the stepsize as the r.h.s. of (D.9) would lead to a linesearch accepted, and the choice of $\\alpha$ is designed to track this stepsize, and leave the unknown part $C_M$ in the r.h.s. determined by the linesearch.\n\n> Q3: Whether $\\theta$ can be adaptively chosen？\n\nThis is an interesting question. However, adaptively choosing $\\theta$ would require a principled selection rule. We suspect that relaxing the Lipschitz continuity assumption on the Hessian to a $\\nu$-Hölder condition may offer insights into such a rule, as in this case, setting $\\theta > \\nu$ yields the best possible local convergence rate.\n\n> Q4: It appears that ARCqK shows excellent time efficiency in most experiments. However, while the authors mention using slightly fewer Hessian evaluations in line 306, it does not seem to result in a better time efficiency. Could the authors further emphasize the practical advantages of the proposed algorithm compared to other methods, particularly in real-world applications? Highlighting these advantages will help readers understand the practical utility of the algorithm better.\n\nThanks for your suggestion. The differences of ARCqK and our methods in the CUTest benchmark are not quiet significant. ARCqK is a cubic regularization method, but their implementation also solves a regularized Newton equation but they need to search the corresponding regularization coefficient to make the solution satisifies the optimal condition of the cubic regularized subproblem. In contrast, our method can give the descent direction directly and may be helpful when solving the equation is expensive as in the PINN example."}]

Author rebuttal:

Meta-review: The paper studies quadratic regularized Newton methods, focusing on trade-off between global and local convergence. The authors propose a parameter-free variant that uses new gradient-based regularizers and a modofied conjugate gradient solver with negative curvature detection. The method avoids dependence on the Hessian Lipschitz constant while achieving optimal global complexity and quadratic local convergence. Empirical results on CUTEst benchmark problems and several physics-informed neural network models suggest the approach is competitive with related second-order methods.

While the contributions are novel and interesting, the paper could be significantly improved by following the reviewers’ suggestions, and the authors are strongly encouraged to implement these in the next revision.
Decision: Accept (poster)