Approximate Secular Equations for the Cubic Regularization Subproblem
Authors: Yihang Gao
Man-Chung Yue
Michael Ng
Venue: NeurIPS 2022 Accept (2022)
Keywords: cubic regularization subproblem
approximate secular equations
partial eigen information

Abstract: The cubic regularization method (CR) is a popular algorithm for unconstrained non-convex optimization. At each iteration, CR solves a cubically regularized quadratic problem, called the cubic regularization subproblem (CRS). One way to solve the CRS relies on solving the secular equation, whose computational bottleneck lies in the computation of all eigenvalues of the Hessian matrix. In this paper, we propose and analyze a novel CRS solver based on an approximate secular equation, which requires only some of the Hessian eigenvalues and is therefore much more efficient. Two approximate secular equations (ASEs) are developed. For both ASEs, we first study the existence and uniqueness of their roots and then establish an upper bound on the gap between the root and that of the standard secular equation. Such an upper bound can in turn be used to bound the distance from the approximate CRS solution based ASEs to the true CRS solution, thus offering a theoretical guarantee for our CRS solver. A desirable feature of our CRS solver is that it requires only matrix-vector multiplication but not matrix inversion, which makes it particularly suitable for high-dimensional applications of unconstrained non-convex optimization, such as low-rank recovery and deep learning. Numerical experiments with synthetic and real data-sets are conducted to investigate the practical performance of the proposed CRS solver. Experimental results show that the proposed solver outperforms two state-of-the-art methods. 

Approximate Secular Equations for the Cubic Regularization Subproblem
Yihang Gao Department of Mathematics The University of Hong Kong Pokfulam, Hong Kong gaoyh@eonnect.. hku.
Man-Chung Yue
Michael K. Ng Department of Mathematics The University of Hong Kong Pokfulam, Hong Kong mngōmaths .ku. hk
Musketeers Foundation Institute of Data Science
The University of Hong Kong Pokfulam, Hong Kong mcyue@hku. hk
Abstract
The cubic regularization method (CR) is popular algorithm for unconstrained non-convex optimization. At each iteration, CR solves a cubically regularized quadratic problem, called the cubic regularization subproblem (CRS). One way to solve the CRS relies on solving the secular equation, whose computational bottleneck lies in the computation of all eigenvalues of the Hessian matrix. In this paper, we propose and analyze a novel CRS solver based on an approximate secular equation, which requires only some of the Hessian eigenvalues and is therefore much more efficient. Two approximate secular equations (ASEs) are developed. For both ASEs, first study the existence and uniqueness of their roots and then establish an upper bound on the gap between the root and that of the standard secular equation. Such an upper bound can in turn be used to bound the distance from the approximate CRS solution based ASEs to the true CRS solution, thus offering theoretical guarantee for our CRS solver. desirable feature of our CRS solver is that it requires only matrix-vecte multiplication but not matrix inversion, which makes particularly suitable for high-dimensional applications of unconstrained non-convex optimization, such as low-rank recovery and deep learning. Numerical experiments with synthetic and real data-sets are conducted to investigate the practical performance of the proposed CRS solver. Experimental results show that the proposed solver outperforms two state-of-the-as methods.
Introduction
The cubic regularization method (CR) is variant of Newton's 's method proposed by Griewank X and later independently by Nesterov and Polyak [12,, and Weiser et al. [6. gained significant attention over the last decade due its attractive theoretical properties, such convergence second-order critical [oints[[]] and quadratic convergence rate under mild assumptions [17]. Each iteration of CR solves problem of the following form, called the cubic regularization subproblem (CRS):
min XER
SA.b, (x) = bT x
Ax
||x||
where p > is the regularization parameter, b E Rn and A E R is symmetric matrix, not necessarily positive semidefinite. Many variants and generalizations of CR are developed, including
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the Adaptive Regularization Using Cubics (ARC) which allows for a dynamic choice of and inexact CRS solutions 3 4. accelerated CR using momentum [T5] and stochastic CR for solving stochastic
optimization [1]. Despite the theoretical success, the practicality of CR and its variants relies
critically on the CRS solver, topic that attracts considerable research recently 2 To 2 The goal
of this paper is to develop novel, efficient CRS solver along with theoretical guarantees.
popular approach for solving the CRS is via solving the so-called secular equation. We now review this approach. Towards that, we denote by λ I ... < An the eigenvalues of A and by Vi,... Vn the corresponding eigenvectors. In other words, we have the eigendecomposition A Ei=1 Li=1 AvV.v," = VAVT, where A = (ing(A........ eigenvalues X; are not necessarily positive due the indefiniteness of the matrix A. Also, we denote the Euclidean norm by -|-
and V [V1, vnl. Note that
Proposition
). vector x" solves the CRS ① if and only if it satisfies the system
{ [AA + p||x" [[xx + b 0, A + p||x |||
(2)
(3)
Moreover. if p||x*||I> O, then x" the unique solution (and hence a critical point).
Proposition 2 (II). Let x* be global solution of CRS ① and the eigendecomppssiion for A
E A = VAVT, where A diag(Ai..... .i....,;,] Xa) and V = =[v1,' ... Vnl. bf v1 F 0, then A + +lxx" |I > and the solution x' is the unique critical point (and hence the unique solution).
Conversely, bbv vi = 0, then the CRS [ has multiple optimal solutions.
From Proposition if bT v1 * then there is only one eritical point, which is also the optimal solution, and hence the gradient norm ffA. (x)] serves as an optimality measure. Throughout the paper, we assume bTvv * O, under which the CRS said to be in the casy case, This is without much loss of generality as this holds generically true in practice. Moreover, could easily avoid the
hard case (b V V1 = 0) by slightly perturbing the vector b, see 12
To introduce the secular equation, note that in the easy case, conditions and B can be written as
{ (A + oI) y = c,
Aι + t 0. where a =: -||x" [Vi, ... vnl = y = VTx and [er, == ==
VTb. Therefore,
I.....n
A +
Since the Euclidean norm is invariant to orthogonal transformation, we have
a² 0
x 1 Iy
o)2
Consequently, instead of solving the complicated nonlinear system by first finding the (unique) root > m 0} of the equation
we could solve the CRS
σ²
(a) =
Σ (A + 0)²
p2
called the secular equation, and then solves the linear system (A + +I)x -b. The first step be done efficiently by using existing root-finding algorithms (e.g., the bisection method and Newton's method etc.).
The disadvantage of the above CRS solver, based on the secular equation is that it requires the full spectrum of A. which costs Onz)). This approach is viable only for low- to moderate-dimensiionll problems. However, when n is large, computing all eigenvalues of A is prohibitive. Worse still, after the root is solved, we still need to apply iterative methods (e.g., Lanezos method) to solve the large-scale linear system P We are thus motivated to approximate the secular equation by using only some of the eigenvalues of A, opposed to all.
As our main contribution, we developed two different approximate secular equations (ASEs), both of eigenvalues of A. The cost for forming the approximate secular
which require computing

---

equations is only O(mn²), and hence the resulting CRS solver is much more efficient and scalable. On the theoretical side, for each of the proposed approximate secular equations, we first studied the existence and uniqueness of its root, and then derived an upper bound on the gap between the root and that of the standard secular equation O. This upper bound is in turn used to bound the distance from the approximate CRS solution based ASEs to the true CRS solution, thus offering theoretical guarantee for the proposed CRS solver. A desirable feature of our CRS solver is that it requires only matrix-vector multiplication but not matrix inversion, which makes it particularly suitable for high-dimensional applications of unconstrained non-convex optimization, such as low-rank recovery and deep learning. On the empirical side, we conducted experiments with both synthetic and real problem instances to investigate the practical performance of the proposed CRS solver and the associated CR. Experimental results showed that the proposed solver outperforms two state-of-the-art methods. The selection of m for the proposed ASEM is an interesting and crucial topic. We will discuss related issues in Section 4 and some numerical explorations are also presented in Section
2
The First-Order Truncated Secular Equation
We define the first-order truncated secular equation by
o²
wi(0; (a: p))
(5)
()+
(1 +
o)²
(=
where μ > Am is an input parameter that approximates the unobserved eigenvalues X Am+1," An
G = -b v; and Ei=m+1 of = |bbl2 E.=1 c². Note that only m eigenvalues A1, Am and their corresponding eigenvectors Vi. Vm are needed to form 51 which is computationally friendlier compared with 4 The name first-order truncated secular equation comes from the fact that (1, n1) is the first-order Taylor approximation
the function w((o). Below will first study the existence and uniqueness for the root of 5 Then, we derive an error bound for the root.
2.1 Existence and Uniqueness for the Root
In the easy case that b"'v, jf 0 (equivalently, ei * 0), the solution x* to the CRS is unique, which implies the existence and uniqueness for the root o² of 44. To show that our proposed CRS solver is also well-defined, prove the existence and uniqueness of the root of the first-order truncated secular equation (5)
Lemma 1. For any μ 2 Am the function wy wi(:; ()) as defined in 5 admits a unique root.
Proof. Existence. We first consider the case when x S 0. Then, for any fixed μ 2 Am
lim (- wi (0; +000 and o+to
lim
wi (a; (1) -00
By the intermediate value theorem, wi (z) has root in (-A1, +00). For A1 > O, we have
wi (0; 0 and lim wi (a; = -00 o
Therefore, wi (o) has root in (0, +00).
Uniqueness. Note that w (a; p)) is monotonically decreasing for a E (-Ar, +o0) and a e (0, +00) when êι < 0 and d > 0, respectively. Therefore, the uniqueness of the root for w ((: is guaranteed.
2.2 Error Analysis
In order to study the quality of the CRS solution based on our proposed solver using approximate secular equations, we need to study the quality of the root to the first-order truncated secular equation, denoted by a.. Towards that end, we provide an upper bound on the gap |oj o²I between of and the root of the exact secular equation 44)
Theorem 1. Let of and o² be the unique roots of wi (1) and w(a), respectively. Then
10¹- -0 S Cm
max. m+1SiSn
1A; 14/,
(6)

---

and 2 b/b where Cm > is a constant, upper bounded by (Am-A1))
min
(A++Br) d²
with B₁
2 bil"
2B
A1 Ap being upper bound for lot).
We clearly see that the right-hande side of inequality ① is decreasing m. This confirms that using more eigen information (i.e., larger m) helps to reduce the error oo o¹1. The proof of Theorem
technical and quite long and hence relegated Appendix A The approximation quality of our with the following proposition.
CRS solver is guaranteed by combining Theorem |
Proposition 3. Let and be solutions the equations (A + o'Ixx'
and (A xf
-b, respectively. Then, |* - xxxx O (( - o²1).
Proof. By definition, have
(1+ O v.v (-b) = Σ
()s -0)
t=1
i=1
x
(As + +oj
V.Vi (-b) Σ (A + too)= a v...
1=1
then
12
||x
x
Σ
(A: a
(1:
v.vi (-b)
(N: (di - (1i+ [|b]
max Isisn
0 (io) o²1).
This completes the proof.
Before ending this section, some remarks are in order. First, the parameter μ acts as an approximation to unknown eigenvalues Am+ An. An intuitive choice of that works well in practice and is computationally cheap is the average of unknown eigenvalues, i.e.,
Ei d (r(A)= Dm A
J41
m
m
Second, the error bound Cm max AA l4| in Theorem depends the distribution of eigenvalues A. If the unobserved eigenvalues Am+1, ... A, cluster around a small interval, then with suitable choice of u [Am+1. An.. maxm+1sisn [λ, - pul small. Conversely, the unknown cigenvalues spread over a large interval, then it is hard to make the error maxm+1sisn [A; - /4| small.
Third, it is instructive to study the error bound (6) under some random matrix model for A. Suppose that A A/V2n, where A is symmetric random matrix with i.i.d. entries on and above the diagonal. By the Wigner semicircle law [ + co, the cigenvalues of A distribute according to density of a semi-cirele shape. In particular, we can deduce that with probability of o(1).
max mI+ Si
|A -
(1--++1
m
2/3
2/3
m 1
2/3
(8)
n2
4v2
n
The detailed proof of and further discussions under random A can be found in Appendix
C
3
The Second-Order Truncated Secular Equation
Similarly to the equation 5 but with the second-order Taylor approximation, we define the second- order truncated secular equation by
m
-4 o²
= Σ
Σ
(9)
o)²
(p+
p
1=++1
1=m+1
where μ 2 Am is an input parameter that approximates the unobserved cigenvalues Am+1, An-

---

3.1 Existence and Uniqueness for the Root
The lemma blew shows the existence and uniqueness of the root of w2(:; (1).).
Lemma 2. With
2i=m+1 G X
84
(10)
Li=m+1 Of
the function (2) as defined in admits unique root.
Proof. When
1 2im++1 of A
E
Ei=m1 Cf
the third summation in the definition
2 vanishes, and hence w2 (1) becomes the same wi (o, pt) except with a specific choice μ. The desired conclusion then follows from Lemma
Unlike its first-order counterpart, we do not develop the existence and uniqueness of the root of the second-order truncated secular equation for arbitrary μ. The reason is that when Å > 0, (0; can potentially be positive or negative.
3.2 Error Analysis
Similar to that for the first-order truncated secular equation, we can also derive an error bound for the root of the second-order truncated secular equation.
Theorem 2. Let 02 and o² be the unique rool of w2 (a; and w())) respectively, and
G A
1
n i o7
Then,
102 - -0---11- S Om
max m+1sign
(): - -
(11)
where C.
0 is a constant bounded by
(Am (m min
3||b/
(An o² 2|
with B
-1 A being an upper bound for lož)-
The proof Theorem 2 can be found in Appendix We can similarly estimate the approximation quality by combining Theorem and Proposition 3 Again, the right-hand side of the error bound (II) decreasing in m. We should also point out that the CRS solver based on the recond-order secular equation outperforms the first-order counterpart only if maxm+1gism [ /4/lAmm A1 is small enough. The computation of μ here requires Cm+1, ... Cu. which seem be inaccessible. We
provide tractable form for in 133 and will discuss it in the next part.
4 Implementation Details
We now discuss the implementation details for solving the proposed first-order secular equation for CRS. First, we obtain the partial eigen information (.,,... Am) subspace methods. Note that only Hessian-vector products are required. This is computationally friendlier than other methods that rely on matrix inversions and is particularly suitable for modern, high-dimensional applications. Then, we solve the first-order secular equation (5) with μ defined in 7 or TOP. using any root-finding algorithm, such as Newton's method. Finally, we solve the linear system (A - o² o'')x = b by iterative algorithms, e.g., the Lanczos method and the conjugate gradient method. The resulting CRS solver, namely the approximate secular equation method (ASEM), is summarized as follows:
and [vi..... V.n) by Krylov
Step 1: obtaining the partial eigen information {AI,... Am) and (vi,.... vm. of A.
Step 2: solving the secular equation ( with y defined in 7 or 10 we get o².
Step iteratively solving the linear system (A T)x 0.
Output: the solution
5

---

Details for Step 1. The Krylov subspace is one of the most popular iterative methods in solving eigen problems with (mn?² computational cost The Lanczos decomposition for real symmetric matrix B satisfies
BU U& + BRUR+10
where Ug R is an orthonormal matrix (i.e., U = It), Ta E RR a symmetric tridiagonal matrix and C₁ E R is the k-th standard basis vector in IR Lanezos observed that even for comparatively small k, Tx approximates B very well in terms of eigenvalues and eigenvectors. Specifically, for suitable eigenpair (7. w) of Ts with T&W = y w, the pair (?; U&w) (.) is an approximate eigenpair of B, i.e., Bz 7-2 with 2 = UgW. Here, the Krylov subspace is constructed by un the first column of U = [ui," ".. Us]. i.e., (B, u1). Note that Tr approximates for eigenvalues with largest modulus (or absolute values) and the corresponding eigenvectors. Empirically, for calculating m eigenvalues of B with largest absolute values and the corresponding cigenvectors, we usually construct the Krylov subspace (B, u1) with dimension k max (2m, 20). The base vector u, is also essential for the Krylov subspace method. Moreover, restarting is adopted to iteratively update the base vector U1 To the best of our knowledge, the mentioned iterative method for partial eigen information is supported in many softwares, e.g., Matlab (eigs function) and Python (Scipy package) etc. For more details, please refer to ARPACK [II. Returning back to the proposed algorithm with A, instead of calculating the largest (in terms of the absolute value) m eigenvalues of A, aim get m (algebraically) smallest eigenvalues {'i,-.. .mm) and the corresponding eigenvectors (Vi.... Vm We first roughly calculate a shift value B 2 |||| by several steps of power iteration (Hessian-vector products). Then, let B B-I A, whose eigenvalues {3 An. 3 - } are non-negative and the corresponding eigenvectors are {vn, vi Applying the mentioned Krylov subspace algorithm, we first obtain an estimate of shifted eigenvalues {Ai...., : Am Jo and the corresponding eigenvectors {Vi,.... ) for A, since { Am, are largest eigenvalues of B. To further lower the computational cost, we may adopt k-dimensional Krylov subspace K₂ (B u1) for m eigenvalues without restarting in implementation with k = m.
3 }
Details for Step 2. Instead of directly solving 5 the equivalent equation:
Cartis et al.
G recommended to find the root for
n Σ i=m+1
(o:
(12)
(A: o))
(μ + o)²
p
which is convex (-λ1, foo). Moreover, under perfect initialization, Newton's method is proved to achieve (locally) quadratic convergence. However, we numerically find that it depends much on the
initialization and may converge point outside the feasible domain (-A1, +oo) if it has imperfect initialization. Here, we recommend to use the bisection method to find the root of 3 or (12 due to its linear convergence, stability and case of implementation. For the weighted average j defined in we can rewrite it as a more tractable but equivalent form:
10
En & >2
(T v.
Am VT
ATAb
>
m
A
1/2 Di=++1 &
b 2
b
-
m
(13)
11=1
Di=1
where Vn =
[V1,-.. -..= V and Am diag(A1. ... Am).
Details for Step 3. There many well-studied, efficient and reliable iterative methods for (real symmetric) linear systems, e.g., Krylov subspace (I (Lanczos) methods and conjugate gradient methods etc. We adopt the Lanezos method for solving the linear system (A + "T)x + b 0. where only few steps of Hessian-vector products are required.
In summary, the main computational cost comes from Step I and Step 3 for deessianvvectr products (O(m²))) since solving the root of w (o; μ1) is a I-dimensional problem in Step 2 and of cost On)). Therefore, the total computational cost for the proposed algorithm is O(m)²), much lower than the method based on full eigendecomposition (O(n3))
The selection of m. The choice of the parameter m is important to our CRS solver: a larger m yields a better CRS solution quality but incurs a higher computational cost. If is a Gaussian random matrix, by 8 we can achieve e-accuracy (i.e., | - o" S E) if m S satisfies
3m
2/3
m + 1
2/3
S..
4

---

However, the error bound 3 provides only conservative sufficient conditions for m. Moreover, for general problems without the Gaussian assumption on A, it is hard to choose m based on the e-accuracy, because the error bounds 6 and (TT) are implicit in m. Therefore, adaptive methods (or heuristic methods) for selecting mn are necessary in practice. suboptimality (gradient norm) in each step, and enlarge m by mo (i.e., we set m max (m mo; maxx where mmax is the maximal number of cigenvalues we adopt in ASEM), the output does not satisfy the given condition for suboptimality. Moreover, numerical experiments problems (see Experiment in Section 5 shows that m = is enough for most of the cases. We left the study for the selection of m as future work. To the best of our knowledge, the Krylov subspace method for CRS suffers from a similar issue of hyperparameter selection.
natural way is to check the
CUTEst
5 Experimental Results
Without the loss of generality (see Appendix D. assume that A is diagonal in the synthetic CRS instances, for simplicity and fair comparison. Furthermore, we also test the proposed ASEM on CUTEst library 77. All experiments were run Macbook Pro M1 laptop. For more experimental details, please refer to Appendix E
The distribution for eigenvalues of the matrix A. In the error analysis (Theorem 1 and Theorem 7. the error controlled by the approximation of ju to unobserved eigenvalues
Experiment 1.
ie., maxx 15445n [^g - Au] and maxm+1sism (A, - -x)2. It further implies that the distribution of eigenvalues {Ax fmm++ is essential for the proposed method. Intuitively, if eigenvalues (A, ) m cluster around a small interval, then the rough estimate (7) for je is enough to approximate the unknown eigenvalues well. Conversely, if eigenvalues {>; 1 fi-m+1 spread across large interval, then we cannot expect a single 4 to estimate all eigenvalues {>>H=m+1 Here, we have four specially designed cases for distributions of eigenvalues of the matrix A to illustrate our theoretical observations for the proposed method. Case 1 (evenly spaced): all eigenvalues {>:) are evenly spaced in [];, Case 2 (separated): half of eigenvalues are far away from the remaining, i.e., eigenvalues
{A: are evenly spaced in [-1, -4/5) and the remaining eigenvalues (Ar) are evenly spaced in [4/5, 1]: Case 3 (right centered): the minimal 2% of eigenvalues and the remaining 98% of eigenvalues gather together respectively, i.c., eigenvalues //55 and {A.) are spaced evenly in [/5] and [4/5, 1] respectively; Case 4 (left centered): the maximal 2% of eigenvalues and the remaining 98% of eigenvalues gather together respectively, i.e., eigenvalues { {A 40/)5=4 are evenly spaced in 1,54 and [4/5, 1) respectively. The vector b is proportional to [1, ... 11TT with ||b|| = 0.1. The remaining parameters are n = 5 x 10 and p= 0.1. Here we adopt the first-order ASEM (i.e., μ is defined in 7p. Figure validates our theories that the proposed algorithm converges fast if unknown eigenvalues { 1=111 are close. Morcover, without the need to compute all eigenvalues, partial eigen information is enough to achieve satisfactory solutions in
49/50n and
practice, except for the hard case (e.g., Case 4).
1.0
1.0
1.0
case 1: equally distr buted
case meat value
case 11 exact elgenvalues
0.8
case 2: seperated
0.8
neighted everage casa 3.an
0.8
case 2: approcmmateddd aigenvaluss
0.6
case 4; left centered
case 3: right contered
0.6
cark dia- 10
gratert sorm
0.6
0.4
0.4
0.2
0
2000
4000
0.0
0
2000
4000
0.0
250
500
750
1000
m
Figure 1: Trajectories of suboptimality (gradient norm |/ [V]A,,,,())] with different distributions for eigenvalues in Experiment 1.
Figure 2: Trajectories of suboptimality (gradient norm [|V/a,,, (x)ll) with different 1s in Experiment 2.
Figure 3: Trajectories of
suboptimality (gradient norm || [V with exact and approximated eigenvalues and eigenvectors in Experi- ment 3.
Experiment 2. The effect of the parameter y (first-order and second-order ASEMs). For the first- and second-order ASEMs, we define μ according to 7 and (10) respectively. Here, we test the effect of
7

---

10
10a
gradient norm
10-2
gradient norm
10-2
10-4
10-6
gradient descent
10
gradient descent
Krylov subspace
Krylov subspace
ASEM
ASEM
10-8 8
10-8 8
50
100
150
200
100
200
300
400
numbers of Hessian vector products
numbers of Hessian vector products
(a) Case I: 10
(b) Case 2: 10%
Figure 4: Trajectories of suboptimality (gradient norm [V (x)li for ASEM, the Krylov sub- space method and the gradient descent method in Experiment
u for the proposed method in solving the cubic regularized quadratic problem, with other parameters fixed. Case (first-order ASEM): μ is adopted the mean value of unknown eigenvalues, defined in 77) Case 2 -second-order ASEM); μ is selected as the weighted average of unknown eigenvalues with weights c, (sce (10); Case 3 (first-order ASEM);
observe; Am. the maximal eigenvalue Case 4: | 10,, much larger than the eigenvalues of A, as an approximation to +00. The vector b is proportional spaced in [-1, 1]. The remaining parameters are d = x 10 and p = 0.1. Figure shows the superiority of the second-order ASEM over the first-order ASEM that it more stable and converges faster when m is large, consistent with Theorem D and Theorem 2 Moreover, the results further imply the importance of the choice of μ.. There are several observations from Figure 2 Firstly, we cannot discard the residual term with the unknown eigenvalues { where they still contain much information, as is shown in Case and Case Secondly, the random selection of µ does not work well and may even cause divergence (c.g.. see Case 3 and Case 4). Furthermore, suitable choice of y leads well-hehaved algorithm (e-g., see Case and Case 2).
AA,]' ['1,...
with length |]b]| = 0.1. Eigenvalues of the matrix A are evenly
Experiment 3. Approximation capabilities of the Krylov subspace method for ASEM. As is in- troduced in Section 4 adopt m-dimensional Krylov subspace Krn (B, u1) to approximately calculate m algebraically smallest eigenvalues { }m and the corresponding eigenvectors {vI,--. ). We now investigate the performance of ASEM with estimated eigenvalues and eigen- vectors. The vector is proportional to the vector [1, 1 with length ||b|| = 0.1. Eigenvalues of 10 and p = 0.1. We adopt the first-order ASEM (i.e., μ is defined in 7 here. Trajectories for suboptimality with exact and approximated eigenvalues and eigenvectors are shown in Figure 3 The Krylov subspace Kr, (B, u, with relatively low dimension m for ASEM matches well with ASEM with exact eigen- values. This experiment justifies the use of the m-dimennional Krylov subspace for m eigenvalues and eigenvectors in ASEM.
the matrix A are evenly spaced in [-1, 1]. The remaining parameters are n
Experiment 4. Comparison of ASEM with the Krylov subspace method p and the gradient descent method [ on synthetic problems. For large-scale problems, the Krylov subspace method and the gradient descent method are two state-of-the-arr methods for CRS 1 In this experiment, compare the proposed ASEM against the Krylov subspace method and the gradient descent method. The dominant computation steps for these three methods are Hessian-vector products (O(mn?)). The vector b is proportional to the vector [1, 11.... 11 with length ||b]| 0.1. Eigenvalues of the matrix A are evenly spaced in [-1, 1). Similar to the setting in [2), we define the condition number for ( as A=tool|x* K xx+ A to Then, we have 0² Am- and
II -i Case 1: easy case that K = 100 Case 2: harder case that y 10 The remaining parameter n 5 x 103. We adopt the first-order ASEM (i.e., is defined in 7 As shown in Figure E ASEM outperforms both the gradient descent method and the Krylov subspace method when m is relatively large. is reasonable that ASEM underperforms when m is small since the m-dimensional Krylov subspace cannot well approximate eigenvalues and eigenvectors of A. The results further demonstrate the performance of the proposed ASEM method.
x-1
8

---

Experiment 5, Comparison of ASEM with the Cauchy point method [3]. the gradient descent method and the Krylov subspace method on the CUTEst problems 77]. The CUTEst library collects various unconstrained and constrained optimization problems that arise in real applications. In this part, we compare the numerical performances of the ARC algorithm 3 on four unconstrained optimization problems from the CUTEst library, where subproblems are solved by the Cauchy point method (ARC- CP), the gradient descent method (ARC-GD), the Krylov subspace method (ARC-Krylov(k), where k is the number of Lanezos basis vectors) and the ASEM method (ARC-ASEM(m)) where is the number eigenvalues for ASEM). The architecture of the ARC algorithm is provided in Appendix
E.2 Four unconstrained optimization problems (e.g.. TOINTGSS, BRYBAND, DIXMAANG, and TQUARTIC) in the CUTEst library are adopted for testing, where the dimensions are 1000, 2000, 3000, and 5000, respectively. We use the first-order ASEM (μ is defined in (7) here since found that the performances of the first-order ASEM and the second-order ASEM do not differ much for these problems. Numerical results reported in Table | where Xout- |/ [xxa))l)) Ill (v (xxum)), iter and time represent the output of the ARC algorithm, the suhoptimality (gradient norm), the minimal eigenvalue of the Hessian matrix, number of iterations for the ARC and CPU time, respectively. Here are several observations. Firstly, the proposed ASEM algorithm outperforms others in most achieves a worse suboptimality (gradient norms) or CPU time. Furthermore, only one eigenvalue is enough for the ASEM to perform well (i.e., ARC-ASEM(m) with 1), which surprising, For more experimental details, please refer to Appendix
and is comparable to the Krylov subspace method sometimes, where the ASEM
Table 1: Results on CUTEst problems in Experiment 5.
Problem
Method
f(Xour)
2v f(Xoor)
iter
time(s)
ARC-CP
3.60E+14
4.12E-05
1.40E-16
1000
6.08
ARC-GD
3.60E+14
1,42E-06
3,89E-16
100
6.98
TOINTGSS
ARC-Krylov(I
3.60E+14
4.12E-05
1.20E-15
300
6.75
(n = 1000)
ARC-Krylov(10)
3.60E+14
2.20E-08
1.29E-15
19
1.87
ARC-ASEM(1)
3.60E+14
8.01E-10
-1.63E-15
19
2.17
ARC-ASEM(10)
3.60E+14
8.17E-10
-7.67E-16
19
2.74
ARC-CP
7,49E+14
1.10E-03
5,40E+00
1000
8.27
ARC-GD
1,25E+05
4.93E+03
4.40E+02
100
11.05
BRYBAND
ARC-Krylov(10)
7,49E+14
6.60E-06
5,40E+00
100
9.85
(n 2000)
ARC-Krylov(30)
7.49E+14
1.14E-07
5.40E+00
14
2.37
ARC-ASEM(1)
7.49E+14
1.02E-07
5.40E+00
14
2.24
ARC-ASEM(10)
7,49E+14
1,01E-07
5.40E+00
14
3.83
ARC-CP
1,00E+00
3.13E-04
6.67E-04
2000
35.16
ARC-GD
1,00E+00
9.24E-05
6.67E-04
200
33,83
DIXMAANG
ARC-Krylov(10)
1.00E+00
3.44E-05
6.67E-04
500
32.18
3000)
ARC-Krylov330)
1.00E+00
9.06E-09
6.67E-04
46
6.65
ARC-ASEM(1)
1,00E+00
5.53E-09
6.67E-04
30
7.51
ARC-ASEM(10)
1. 1.00E+00
4.85E-09
6.67E-04
42
18.74
ARC-CP
8.04E-01
6.102-02
-5.41E005
500
71.92
ARC-GD
8.05E-01
2.77E-02
4.80E-05
100
98.14
TQUARTIC
ARC-Krylov(I)
8.05E-01
2.76E-02
4.71E-05
100
29.43
(n = 5000)
ARC-Kryl0v100)
5.05E-14
8,48E-09
4.00E-04
46
16.09
ARC-ASEM(1)
7.43E-14
9.62FF-09
4.00E-04
46
15.47
ARC-ASEM(10)
7.43F-14
9.62F-09
4.00F-04
46
16.18
Conclusion
We develop the first-order and the second-orde truncated secular equations as surrogates to the secular equation with full eigendecomposition in solving the CRS (T) The proposed ASEM an efficient alternative to existing methods for solving CRS since it reduces the computational cost from Onn)) to (mmr²) Our CRS solvers feature rigorous theoretical error bound, which is related amount of eigen information used. We also discuss in detail the implementation of our proposed algorithm ASEM. In particular, we show how only Hessian-vector products are needed, but not matrix inversion. Numerical experiments are conducted to further investigate the properties and performance

---

of the proposed ASEM and corroborate with the theoretical results. From our experiments, we find that the proposed ASEM is more efficient than the state-of-the the-art methods on synthetic and CUTEst problems.
Acknowledgement
We would like thank the anonymous reviewers and chairs for their helpful comments. Michael K. Ng is supported by Hong Kong Research Grant Council GRF 12300218, 12300519, 17201020, 17300021, C1013-21GE C7004-21GF and Joint NSFC-RGC N-HKU76921. Man-Chung Yue is supported by the Research Grants Council (RGC) of Hong Kong under the GRF project 15303321.
References
[1] Yair Carmon and John Duchi. Gradient descent finds the cubic-regularized nonconvex Newton step. SIAM Journal on Optimization, 29(3):2146-21) 2178, 2019.
[2] Yair Carmon and John C Duchi. Analysis of Krylov subspace solutions of regularized non- convex quadratic problems. Advances in Neural Information Processing Systems, 31, 2018.
[3] 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-225,, 2011.
[4] Coralia Cartis, Nicholas IM Gould, and Philippe Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evallattio complexity. Mathematical Programmingg 130(2):295-319 2011.
[5] Andrew R Conn, Nicholas IM Gould, and Philippe L Toint. Trust Region Methods. SIAM, 2000.
[6] Peter Forrester. Log-Gases and Random Matrices. Princeton University Press, 2010.
[7] Nicholas IM Gould, Dominique Orban, and Philippe Toint. Cutest: a constrained and uncon- strained testing environment with safe threads for mathematical optimization. Computational Optimization and Applications, 60(3):545-557, 2015.
[8] Andreas Griewank. The modification of newton's 's method for unconstrained optimization by bounding cubic terms. Technical report, Technical Report NA/12, 1981.
[9] Ru-Jun Jiang, Zhi-Shuo Zhou, and Zi-Rui Zhou. Cubic regularization methods with second- order complexity guarantee based on a new subproblem reformulation. Journal of the Operations Research Society of China, pages 1-36, 2022.
[10] Rujun Jiang, Man-Chung Yue, and Zhishuo Zhou. An accelerated first-order method with complexity analysis for solving cubic regularization subproblems. Computational Optimization and Applications, 79(2):471-506, 2021.
[11] Richard Lehoucq, Danny C Sorensen, and Chao Yang. ARPACK Users' Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM, 1998.
[12] Yurii Nesterov and Boris Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
[13] Gilbert W Stewart. A Krylov-Schup algorithm for large eigenproblems. SIAM Journal on Matrix Analysis and Applications, 23(3):601 1-111, 2002.
[14] Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cu- bic regularization for fast nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
[15] Zhe Wang, Yi Zhou, Yingbin Liang, and Guanghui Lan. Cubic regularization with momentum for nonconvex optimization. In Uncertainty in Artificial Intelligence, pages 313-322, PMLR, 2020.
[16] Martin Weiser, Peter Deuflhard, and Bodo Erdmann. Affine conjugate adaptive Newton methods for nonlinear elastomechanies. Optimisation Methods and Software 2333):413-431, 2007.
[17] Man-Chung Yue, Zirui Zhou, and Anthony Man-Cho So. On the quadratic convergence of the cubie regularization method under a local error bound condition. SIAM Journal on Optimization, 29(1):904-99) 9322, 2019.
10

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] As is mentioned in the last paragraph of section the proposed ASEM algorithm involves the selection of m, which balances the accuracy and computational cost of ASEM. We left the (adaptive and heuristic) methods for the selection of m future work.
(c) Did you discuss any potential negative social impacts of your work? [Yes] The proposed
ASEM is for general optimization problems, and it belongs to the foundational research. We do not expect it to involve negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We provide sketch of proof following thcorems and detailed proofs are available in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Our results are reproducible and we will share our code github later.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] Details of experiments are specified in the paper, see section 5.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [No] Our experiments do not involve random seeds.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] All experiments conducted MacBook Pro MI. Moreover, we also report the CPUs' time.
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Most of the works are reproduced by ourselves.
either in the supplemental material as a URL? [Yes] (d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] We mention that test the proposed algorithm on synthetic problems and open datasets.
(c) Did you include any
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] We mention that test the proposed algorithm on synthetic problems and open datasets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [No] Our paper does not involve research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [No] Our paper does not involve research with human subjects.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [No] Our paper does not involve research with human subjects.


Reviews:
[{"review_id": "iuj_MH2mEYE", "reviewer": "Reviewer_ZJXM", "summary": "This paper proposes an efficient and general scheme for finding approximate solutions to the cubic regularization subproblem (CRS) used in the classic cubic regualization method in nonconvex optimization. The main advantage of the scheme lies in the efficient computation of the unique root in a given truncated approximate secular equation (ABE) that scales as $O(mn^2)$ where $n$ is the dimension of the underlying problem and $m < n$ is a parameter that balances the accuracy of the scheme with the overall computational cost. Numerical experiments are given to demonstrate the behavior of the scheme on different parameter choices, different kinds of problem instances, and a subset of the well-known CUTEst optimization problem dataset.  ", "questions": "1. Line 36: Do you mean $V\\Lambda V^T$?\n\n2. Proposition 2: Make this slightly more self-contained, by re-iterating what $v_1$ and $x^*$ are.\n\n3. End of Section 1: A topic that might arouse more interest in the paper early on is a discussion on the choice of $m$ (which is discussed later, starting on line 211). Hence, it would be helpful to add 1-2 sentences at the end of Section 1 to say that this is a topic that will be discussed later in the paper.\n\n4. The choice of $\\mu$ in Theorem 2 does not seem to be immediately implementable, since it relies on $\\lambda_{m+1},\\ldots,\\lambda_{n}$. However, equation (13) later on gives a tractable form for $\\mu$. Perhaps a remark in (or after) the Theorem should be made to direct the reader to (13).\n\n5. Line 197: \"...if with imperfect initialization.\" Missing word?\n\n6. Line 183: Return <- Returning\n\n7. Line 289: \"The rest of the parameter...\" <- \"The remaining parameter...\"\n\n8. The words \"Krylov\" and \"Krylob\" are used interchangeably throughout. I would suggest picking only one of these spellings.", "limitations": "The authors have sufficiently addressed all limitations (assumptions) in this paper. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Disclaimer**: My review is limited to the material presented in the 9-page body of the paper, and does not consider the materials in the supplement.\n\n*Strengths*\n\n1. The numerical experiments are significant in their scope and quality. Specifically, they test the behavior of the proposed scheme (ASEM) with respect to its key parameter $\\mu$ and the distribution of eigenvalues in the CR subproblem. I also appreciate the inclusion of other well-known algorithms in the benchmarks, such as gradient descent, the Cauchy-point method, and the Krylov subspace method.\n\n2. The error bounds in Theorem 1 and 2 are highly appreciated, as they encapsulate the expected behavior of the scheme and do abuse asymptotic notation to hide any universal constants.\n\n3. The complexity improvement from $O(n^3)$ to $O(mn^2)$ is impactful both from a theoretical and practical point-of-view.\n\n4. The writing of the paper is both clear and concise. Moreover, the remarks following some of the more important results, e.g., Proposition 3, are both welcome and informative.\n\n*(Minor) Weaknesses*\n\n1. There are few places that could better with additional clarifying statements (see the *Questions* section below).\n\n2. There are few minor typos (see the *Questions* section below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Q_PtvDK2Wp", "reviewer": "Reviewer_QKHv", "summary": "The well-known cubic regularization of Newton's method proposed by Nesterov (2006) requires solving a \"cubic subproblem\" at each iteration:\n$\n\\min_{\\mathbf{x} \\in \\mathbb{R}^{n}} =\\mathbf{b}^{\\mathrm{T}} \\mathbf{x}+\\frac{1}{2} \\mathbf{x}^{\\mathrm{T}} \\mathbf{A} \\mathbf{x}+\\frac{\\rho}{3}\\|\\mathbf{x}\\|^{3}.\n$ \nThe cubic subproblem is equivalent to solving a \"secular equation\", which is a nonlinear equation that depends explicitly on the eigenvalues of $A \\in \\mathbb{R}^{n\\times n}$. Solvers for this secular equation run in $O(n^3)$.  \n\nIn this work the authors propose two \"approximate\" secular equations. Essentially the approximate secular equations are obtained by setting a parameter $m$ and replace all eigenvalues larger than $\\lambda_m(A)$ in the secular equation with a constant $\\mu\\geq \\lambda_m(A)$.  The advantage is that now we only need to compute the first $m$ eigenvalues of $A$, reducing the computational cost to $O(mn^2)$. The authors provide error analysis on the difference between the exact solution of the secular equation and the approximate solution. Furthermore, they provide numerical experiments to gauge the error of the approximate secular equation in a number of different scenarios. It is observed that the error depends on the distribution of the eigenvalues of $A$. ", "questions": "The paper is clear and easy to understand. My only question is how does the approximate solver work in practice when used in cubic regularization? If the authors can implement their method and compared to state of art algorithms such as Carmon and Duchi 2018, or Cartis et al. 2011 and demonstrate a clear advantage, I would consider increasing my overall evaluation. ", "limitations": "Yes. There is no direct negative societal impact. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThe ability to solve cubic subproblems efficiently is very important for the success of cubic regularization. The idea of solving an approximate cubic subproblem instead of an exact one can be useful in specific cases where the large eigenvalues of $A$ is concentrated in a small interval. The error bounds in this paper also become tighter in this regime. \n\n### Weaknesses\n- The main contribution of this paper is proposing two approximate secular equations and analyzing their errors. However, both the proposed equations and the error analysis are quite obvious and unsurprising. It basically boils down to the following idea: in the equation\n$\nw(\\sigma)=\\sum_{i=1}^{n} \\frac{c_{i}^{2}}{\\left(\\lambda_{i}+\\sigma\\right)^{2}}-\\frac{\\sigma^{2}}{\\rho^{2}} = 0,\n$\nwe can pick an index $m$ and replace all eigenvalues greater or equal to $\\lambda_m(A)$ with a constant $\\mu$, resulting in an approximate equation. The larger $m$ is, the smaller the approximation error. When $m=n$, the method is exact. The error analysis is also based on this idea. The overall theoretical contribution is weak because the tradeoff between $m$ and the accuracy is quite obvious. It is also clear that the resulting error will depend on $m$, $\\mu$ and the distribution of the eigenvalues. Using a small $m$, of course, will increase the error and reduce the running time, which is the gist of this paper. \n- The motivation for this work is that the approximate secular equations can be used to solve the cubic subproblem, resulting in more efficient iterates for cubic regularization of Newton's method. However the experimental section does not contain such an experiment where an actual optimization problem is solved with cubic regularization and the running time is compared with other methods for solving the cubic subproblem, either exactly or approximately. \n- In the end, there is neither a theoretical proof nor a convincing experimental section that demonstrate the advantage of the proposed method when it is actually used in cubic regularization. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4znGsKepf1j", "reviewer": "Reviewer_MvBV", "summary": "In the cubic regularization method, a key step is to solve the so called secular equation which may costs O(n^3) time.\nIn this paper, the authors consider two faster approximation to the secular equation which reduce the computing time to O(n^2 m).\nThe authors give some theoretical analysis of the proposed methods.\n", "questions": "line 41: Proposition 2. Is this proposition adapted from Claim 2.1 in [1]? Why A + rho ||x^*|| > 0? Can you provide a proof of Proposition 2?\nline 45: \"and hence the gradient norm serves as an optimality measure\" I do not understand this.\nline 49: \"lambda_1 + simga > 0\" Should it be >= 0?\nline 90: \"for any mu\". Should it be \"for any mu > lambda_m\"?\nline 109: What does the symbol big O mean in your context? From line 113, it seems tht ||tuilde x - x*|| has no absolute upper bound, for example, suppose |lmabda_i| and simga* are very small.\nline 122 -- 126: These discussions lack mathematical rigor.\n\nFrom the theoretical view, is it possible to improve the bound?", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed method reduces the computing time of secular equation, which may be novel.\nThe paper is relatively well-written and clear.\nThis paper is mostly a theoretical paper.\nIn my opinion, however, the theoretical results are not significant enough.\nIn fact, from the authors' theoretical results (Proposition 3 for example), the proposed method has an irreducible error.\nFrom the authors' experiments, it may be the case that the obtained theoretical bound is too loose.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1OL6YAbibWS", "reviewer": "Reviewer_CTtP", "summary": "The paper studies the cubic regularization technique and proposes two methods for approximating the secular equation based on the first-order and second-order Taylar expansions. Theoretical discussions including uniqueness and existence of the solution together with error analysis are provided. Five numerical experiments are conducted with comparable performance with the state of the art. However, the trade-off between accuracy improvement and computational reduction for these truncation-based approaches is not clear. Overall, the paper looks interesting with a variety of applications but with limited novelty. ", "questions": "1. In line 212, what does the \"computational waste\" mean here?\n2. In Table 1, it may not be fair to simply compare the overall running time. The running time per iteration could be compared as well. In addition, does the number of iterations depend on the selection of certain parameters in all methods being compared? If yes, please discuss which parameters are sensitive and provide guidelines for tuning if available. \n3. In Section 5, it would be better to describe the computing platform and computer configurations at the very beginning of the section rather than in an unnoticeable place in Experiment 5. ", "limitations": "Regularization techniques have been widely used in solving a lot of application problems, such as inverse problems and machine learning. But the paper does not show any such application experiment, which would limit the practical use and attraction. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper proposes to use simple Taylor approximations to approximate the secular equation, which intends to simplify the computation. Implementation details are provided, together with various numerical comparisons with the state of the art. \n\nWeaknesses: The Taylor expansion-based truncation seems intuitive and standard, which will bring inaccuracy for the approximation. It is not fully clear how this type of approximation will affect the accuracy and reduce the computational cost. The general high-order approximation could be discussed as well. In addition, in the numerical results, say Table 1, ARC-Krylov seems to outperform the proposed method in terms of running time. A comparison of computational complexity in the big-O notation could be given with theoretical discussions. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept