Block Broyden's Methods for Solving Nonlinear Equations
Authors: Chengchang Liu
Cheng Chen
Luo Luo
John C.S. Lui
Venue: NeurIPS 2023 poster (2023)
Keywords: Broyden's method
nonlinear equations

Abstract: This paper studies quasi-Newton methods for solving nonlinear equations. We propose block variants of both good and bad Broyden's methods, which enjoy explicit local superlinear convergence rates. Our block good Broyden's method has faster condition-number-free convergence rate than existing Broyden's methods because it takes the advantage of multiple rank modification on the Jacobian estimator. On the other hand, our block bad Broyden's method directly estimates the inverse of the Jacobian provably, which reduces the computational cost of the iteration. Our theoretical results provide some new insights on why good Broyden's method outperforms bad Broyden's method in most of the cases. The empirical results also demonstrate the superiority of our methods and validate our theoretical analysis.

Block Broyden's Methods for Solving Nonlinear Equations
Chengehang Liu
Department of Computer Science & Engineering
The Chinese University of Hong Kong
7li suuchnngchang@gaii...
Cheng Chen'
Luo Luo
Shanghai Key Laboratory of Trustworthy Computing East China Normal University chchen@sei ecnu. ecnu.edu....... edu. cn
School of Data Science
Fudan University
luoluo@fudan. edu. cn
John C.S. Lui
Department of Computer Science & Engineering The Chinese University of Hong Kong calui@cse, cuhk, edu.hk
Abstract
This paper studies quasi-Newton methods for solving nonlinear equations. We propose block variants of both good and bad Broyden's methods, which enjoy ex- plicit local superlinear convergence rates. Our block good Broyden's method has faster ceciittionnumbe-fffiieee free convergence rate than existing Broyden's 's methods because it takes the advantage of multiple rank modification on Jacobian estima- tor. On the other hand, block bad Broyden's method directly estimates the inverse of the Jacobian provably, which reduces the computational cost of the iter- ation. Our theoretical results provide some new insights why good Broyden's 's method outperforms bad Broyden's method in most of the cases. The empirical results also demonstrate the superiority of our methods and validate theoretical analysis.
Introduction
In this paper, we consider solving the following nonlinear equation systems:
F(x) 0,
(1)
where x E dRd, F(x) del [ Rdd + Rd and each Fi(x) is differentiable. Solving nonlinear equations is one of the most important problems in scientific computing (38). has various applications including machine learning 3
game theory [18 39]. economics and
control systems 57
Newton's 's method and its variants Dwvenberg-Maqquaa method [7
16
25
26
such as the Gauss-Newttr method [19 38 the
28
34
36
and the trust region method 40 53] are widely adopted
to solve the systems of nonlinear equations. These methods usually enjoy fast local superlinear rates.
'The corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Newton's 's method takes iterates of form
X++1 = Xt (J(x))))F((())
where [x) E Rd is the Jacobian at x. Since computing the inverse of the exact Jacobian matrix requires (dd) running time. Newton's 's method suffers from expensive computation especially when
solving the large-scale nonlinear equations 220 47 [4].
Quasi-Newton methods have been proposed for avoiding the heavy computational cost of Newton-
type methods while preserving good local convergence behaviour 7711 13 31
32
43
45 [5]] Among these quasi-Newton methods, the Broyden's methods (6] including the good and
the bad schemes [ 30 35|, are considered to be the most effective methods for solving nonlinear
equations. The Broyden's 's good method approximates the Jacobian J(xx) by an estimator B, and
updates the Jacobian estimator in each round as B,+1 = B, + A Here A, is a rank-1 updating matrix constructed by the curvature information. Broyden al. [T]] Kelley and Sachs [27 proved that the good Broyden's 's method can achieve asymptotic local superlinear rates.
The bad Broyden's ss method approximates the inverse of the Jacobian by H, and updates the ap- proximate matrix directly. Although the bad Broyden's method enjoys less computational cost than good Broyden's method in each iteration, it does not perform as well the good method in most cases []] Lin et al. [29] show that both the good and bad Broyden's 's methods have superlinear rates of ((L/VE))) and provide some insights on the difference between their empirical performance.
Ye et al. 550 proposed a new variant of good Broyden's 's method by conducting A, with greedy or random strategy. Their method achieves better explicit convergence rate of O 1 1/d))(t-1)/4) However, remains unknown whether this convergence rate can be further improved by leveraging block updates which increase the reuse rate of the data in cache and take advantage of parallel computing [1]. Gower and Richtárik [21] studied several random quasi-Newtor updates including the Broyden's 's updates for approximating the inverse of matrices, but they only provide implicit linear rates for their methods. Liu et al. (33 established explicit convergence rates for several block quasi-Newton updates, but they focus on approximating positive definite matrices.
In this paper, we propose two random block Broyden's methods for solving nonlinear equations and provide their explicit superlinear convergence rates. We compare the theoretical results proposed methods with existing Broyden's 's methods in Table and summarize our contribution as follows:
We provide explicit convergence rates for the block good Broyden's udpate and the block bad Broyden's 's update proposed by Gower and Richtárik (21]. Our results show that the block good Broyden's update approximate a nonsingular matrix A with a linear rate of (1- k/d)' which
improves the previous rate of (1 1/d)* where k del rank At). We also show that the "bad" update can approximate the inverse matrix -- with an linear rate of (1 k/(dk²))* where
is the condition number of A. To the best of our knowledge, this is the first explicit convergence rate for the block bad Broyden's update.
We propose the block good Broyden's method with convergence rate O(11 k/d))(e-1)/z) where k is the rank of the updating matrix A, This rate reveals the advantage of block up- date and improves previous results. Our method also relaxes the initial conditions stated in Ye et al. (50].
We propose the block bad Broyden's 's method with convergence rate O (((1=k((dx)))) (()== We also study the initial conditions of two proposed block variants. Our analysis shows that bad Broyden's 's method is only suitable for the cases where the condition number of the Jacobian is small, while good Broyden's 's method performs well in most cases.
Paper Organization In Section we introduce the notation and assumptions the preliminaries of this paper. In Section we introduce the block good or bad Broyden's 's updates for approximating the general matrix. In Section 4 propose the block good or bad Broyden's 's methods with explicit local superlinear rates. In Section we discuss the behavior difference of the good and bad methods. We validate methods by numerical experiments in Section 6 Finally, conclude our results in Section 7 All proofs are deferred to appendix.
We use the names "good Broyden's method" and "bad Broyden's method" by following the previous
literature 10 22 35

---

Table 1: We summarize the properties of Broyden's 's methods for solving the Nonlinear equations
Methods
rank (A,)
Convergence Rate
Good/Bad Broyden's Method
o (1/1122)
16
29
Greedy/Randomized Good Broyden's Method
O - (111-11))00-1///
(50)
Block Good Broyden's Method
k E [d-1)
O(11 - (/d[-k/)Mt-1)///
Algorithm
Block Bad Broyden's Method Algorithm
k [d]
((1 k/x -
2 Preliminaries
We let [d] def (1......)) We use || ||r to denote the Frobenius norm of a given matrix, || ll2 to denote the spectral norm of vector and Euclidean norm of matrix respectively. The standard basis for I2d is presented by (c,....,c Ca) and Ia the identity matrix. We denote the trace, the largest singular value, and the smallest singular value of matrix by tr (-), m-in(-), and max (-) respectively.
We use x, to denote the solution of the nonlinear equation ① and J, to denote the Jacobian matrix T (xx)) and then define the condition number of J, def L/μ. We also use ñ Omax (ima((A)/ (A)/Omin (A) present the condition number of given matrix A.
X., i.e., J. def J(x.). We let μa mmin
def mmin (Jx.)), L del
def
Then present two standard assumptions the nonlinear equations I which is widely used in previous works [6 50
Assumption 2.1. The solution x, of the nonlinear equation is unique and nondegenerate, i.e.,
μ def
m (J.) O.
Assumption 2.2. The Jacobian (xx satisfies
[x(x J=l12 1|2 - M||x x. l|z for all Rd
(2)
The following proposition shows that if x is in some local region of x., the Jacobian matrix J(x) has a bounded condition number. Proposition 2.3. Suppose Assumptions 2.7 and 2.2 hold. For all satisfies 1x-x,112 S n² (6LM). we have
min (J()) 2
V2 and max (J(x)) S V
We present two notations for the block Broyden's Update.
Definition 2.4 (Block Good Broyden's Update). Let A. B E Raxd For any full column rank matrix U E pdxk,, we define
BlookeG- B, A, U) B + (A - U)U UT.
(3)
Definition 2.5 (Block Bad Broyden's Update). Let A, H E Rdxd For any full column rank
matrix U R4xk, we define
Block-B-Broyden(HH H. A, U) A H (L. A UU
(4)
3 The Block Broyden's Updates for Approximating Matrices
In this section, we provide the linear convergence rates of the block good and bad Broyden's 's updates for approximating matrices. The theoretical results is summarized in Table 2

---

Table 2: We summarize the properties of Broyden's updates for approximating given nonsingular
matrix A or A- -!
Improved Results
Updates
Previous Results
Measure
Theorem 3.2
Block Good Broyden's 's Update
(1 - 1 d)
21 50
4)²
E [I - A)
Block Bad
(1 p)
21 (h)
(1
(He -
Broyden's 's Update
dea
(a). the result holds for & 1 and unknown when k > 1.
Gower and Richtárik 21 only prove
[0, 2 not provide explicit
The block good Broyden's update, which aims to compute an approximation matrix A, can be written as:
B++1 Block-G- Block-G-Broyden(BBB (B,, A, U.).
The following theorem presents linear convergence rate of 11k/d) which better than the rate (1 11-1, 1/d) provided by Gower and Richtárik (21), Ye et al. 550
Theorem 3.1. Assume that A Ruxd and Bn Raxd we select U, (ei, Big."
Gi.
Baxk where ...,... ..n] are uniformly chosen from 21,2,... .d. without replacement at each round, then for any nonsingular matrix C E Rdxd, the block good Broyden' 's update satisfies
|[C[B++1 - -)] < |C - -A)l?a
(5)
and
k) E E| - A) & (1- |[CBo-AA[lo A)
(6)
On the other hand, the bad Broyden's 's update which targets to approximate A can be written as: HG+1 = Block-B- BBrk----BBodeHHHH A, U.).
Gower and Richtárik 21 provide implicit rate of (1 (1-p) p)" for the above scheme with p k/d,, but their analysis cannot guarantee an explicit p. In the following theorem, we show that the block bad Broyden's 's update approximate H, A with explicit linear rate of (1 (R)
Theorem 3.2. Assume that A Rdxd and Ho E Radxd If we select U, Cig, ... ,,,, Baxk where (ir,.... .ig] are uniformly chosen from 21,2.... ,d} without replacement at each round, then for any nonsingular matrix C Rdxd, the block bad Broyden's 's update satisfies
||C(H++1 A A- |ICHH, A )
and
k dR2
B[I[CHH, A 111 <
|CCH, - - 11
(8)
Remark 3.3. If we choose C = Ia in Theorem 3.1 and Theorem 3.2 then the measures in these two
theorems are exactly the same as the one in Section 8.5 and Section 8.3 of [21]. Besides, the rate
of Theorem 3.1 recovers the convergent rates of Section 8.5 in 21] and Lemma 4.1 in [50] when take 1.
4 The Block Broyden's Methods
In this section, we propose two block Broyden's methods for solving the nonlinear equation (T) We
present our algorithms in section 4.1 and the corresponding convergence results in Section 4.2

---

Algorithm Block Good Broyden's Method (BGB)
1: Input: Initial estimator Bo, initial point X and block size k.
2: for t = 0,
3: Xt+1 X B, Fx()..
4: Choose {i1, i2, i by uniformly select k items from {I, dd} without replacement.
5: U, l , E BR
6: B Block-G-Broyden/ff ((x+1),, U.).
7: end for
Algorithm Block Bad Broyden's 's Method (BBB)
1: Input: Initial estimator Ho. initial point and block size k.
2: for t = 1...
3: Xt+1 Xx HxF(x,).
4: Choose {11, ... , } by uniformly select items from {1,..,, ,d] without replacement.
5: U, le..... , E Rd
6: H4t1 Block- BookkB--royden(/1 H,, J (x++1), U.).
7: end for
4.1 Algorithms
By using the block Broyden's 's updates in Section 3 we propose two novel algorithms called Block Good Broyden's Method (BGB) and Block Bad Broyden's Method (BBB) for solving nonlinear equations.
We present the BGB algorithm in whhchhhhh[[hhhh updates the Jacobian estimator B, by the block good Broyden's 's update each iteration. Notice that the inverse of B, can be computed efficiently by adopting Sherman-Morrison -orrrsso--ooodbbbrry formula [46]. On the other hand, the BBB algorithm, which is presented in Algorithm [ approximates the inverse of the Jacobian directly by using the block bad Broyden's update. It usually has lower computational cost than the BGB algorithm in each round because the BBB algorithm does not need to compute the inverse the estimator H₃.
Remark 4.1. Algorithms 1 and 2 do not require full information of the Jacobian. We construct U, by subsampling the columns of the identity matrix. When updating the Jacobian estimator by the block updates, we need to calculate J++1 U, which is only the partial information of J++1 (columns of J 1. Since we have d, it is not expensive access the partial information of the Jacobian.
4.2 Convergence Analysis for the Block Broyden's Methods
We provide the convergence analysis for Algorithm D and Algorithm 2 in Section 4.2. and Sec- tion 4.2.2 respectively. We denote the Jabcobian matrix at X; as Jr. As previous works 16 29 [50] we make an assumption on the estimator matrices Algorithm and Algorithm 2 as follows:
Assumption 4.2. We assume the sequence (B,) generated by Algorithm (and {H gen- erated by Algorithm 2 are well-defined and nonsingular.
4.2.1 Analysis for Block Good Broyden's Methods
In this subsection, we use the following measures for our convergence analysis,
x.
ll2
and
ai def J J.)
The rt measures the distance between x, and the solution x. and a, measures how well does the estimator matrix B, approximate the Jacobian at x..
The following lemma provides upper bound of o, after one block Broyden's 's update.
5

---

Lemma 4.3. Performing Algorithm under Assumptions 2.7
2.2 and 4.2
we have
2M d
2M k
0++1 S
+
Tt=1
and
Eloc+i] S V 2or
(9)
14
/
Based on Lemma
4.3
we present the superlinear convergence rate for Algorithm
Theorem 4.4. Suppose Assumptions
2.7
2.2 and
4.2 hold and the initial condition of Algorithm
satisfies
2M dro
(1 () k)
q
< min
and 00 S 2(1 + 4)
(10)
1
4(1 q)d
4(1 + g)
for arbitary 9 E (0, 1). Then for any h E [d - 1]. the output of Algorithm
1 satisfies
(1
1/2
E [[JJ, (B. - -J.lla] S 20
and
[x++1
x.
k d
1/2
E
S 4e
X;
x. 1|
Theorem 4.4 implies the following high probability bound for Algorithm 1
Corollary 4.5. Performing Algorithm / under the same assumption and initial condition as Theo- rem 4.4 with probability least 1 ò, we have
4ed2
(
1/2
|J. (B. J.)]le 5
1
(11)
k25
d
+ k
and
Sed2 1:85
)
(
k
1(t-1)/4
Xx - x. 112
5
||xo - x. 112-
(12)
+
Compare Theorem 4.4 with Theorem 4.3 of (50,, we can find that the convergence rate of our BGB algorithm is better than greedy and randomized good Broyden's meth- ods (50) if we choose k > 1.
Comparison with [50
On the other hand, the initial condition of greedy and randomized good Broyden's methods 50 is
I|x0 x. x =
P and |Bo Joll= O (4),
(13)
Mvd.
while the condition of Theorem 4.4 can be reformulated as
|x X 0 (vaa and
/
- -Bo (1).
(14)
Since
J ( - J..) < (J. (J. Jo)ll + 1 (Bo Jo)l
M
|xx
x,l12 + - B Joll = 0(1,
condition (3) can implies condition can choose B, 1.5J, and suppose
14 However, the reverse is not always true. For example, we
Jo J.
10 10-10 10
Then we have J (B, - J.) = == while |Bo JollF
J > 10 μ.
Overall, compared with the greedy randomized good Broyden's method [50 Theorem 4.4 not only gives a faster convergence superlinear rate by leveraging the idea of block update, but also weakens the initial condition by using different measures in the analysis.

---

4.2.2 Analysis for Block Bad Broyden's Methods
This subsection gives the convergence analysis for Algorithm We use the following measures to describe the convergent behavior
Rs -xx
-
and
(H, - ll..
The R₂ measures the distance between and the solution and measures how well does the estimator H, approximate the matrix J_
Using the convergence results for the block bad Broyden's update in Theorem 3.2 we are able tackle the difference between the estimator H,, and the matrix J,1 after one block update in Algorithm
Lemma 4.6. Performing Algorithm 2 under Assumptions 2.1
2.2 and 4.2 and suppose the sequence S pz (6LM) we have
[x generated by Algorithm 2 satisfies that ||x Xx
4M
k
4M 4Mvd
T+41 S T
R and E[T-+]
Re+1-
(15)
4x2dd
n²2
We can establish the superlinear convergence of the block bad Broyden's method based on Lemma
Theorem 4.7. Suppose Assumptions 2.1 2.2 and 4.2 satisfies
hold and the initial condition of Algorithm
4M
q
q
Vd
191
and To
(16)
122
3x
for arbitrary E (0, 1). Then for ls [d], the output of Algorithml
satisfies
k
1/2
E [[. (H. -H,-J se
Adk²
and
J. [x - xx)Il Jx: x.)l12
k
1/2
E
< 2e
4ds2
Similar to Corollary 4.5
we can also obtain the high probability bound for Algorithm 2
Corollary 4.8. Performing Algorithm 2 under the same assumption and initial condition as Theo- rem 4.7 with probability at least 1 ô, we have
Sed? k²4 (1
1/2
[H, J, )1l 8k2
(17)
4dk2 +
and
16edPn' ) )
1(t-1)/1
[_, -
x.)
[J. -x.)12-
(18)
1.28
4dki + k
5 Discussion
In this section, we discuss the performance difference between the good and bad Broyden's 's methods which is considered as important open problem in the field of nonlinear equations [35]
We first discuss the different performance of the block Broyden's 's methods (Algorithm and 2p No-
tice that the "good" method enjoys a condition-number-ffe superlinear rate of O k/d)* (T/)/4 1)/4) and the initial conditions of B, and Xn are |J, - JJ) O(1) and
| x. 1|2
respectively. On the other hand, both the superlinear rate O(11 - k/(4d>))) (1-1)/4
MVa
and initial conditions [H, - J for Hg, Xo the "bad" method depend on x heavily. Thus we think these two block Broyden's methods are suitable for different scenarios:
((inn(1, vd/x)), Jx x.) O(1² (M/2/()V))
7

---

Table 3: Comparison between block good and bad Broyden's 's methods where ro X To = (Bu - J.) Ro [x, 12 and = [J, (Ho - F....
x, 112.
Block Good Broyden's Method Algorithm
Block Bad Broyden's Method
Algorithm 2
Initial Condition
Mydre
(()), 00 = 0(1)
MvaRa =0(1), TO =0 Ld
1
4
0 (11 1)(((-1)44
o ((1 adxx )11-1)/14)
Superlinear Rate
Suitable Scene
k >
= 0(1
The "good" method is more suitable for the cases of large condition number (x >>>>>>>>>>>> 1) because its convergence rate is condition-number-free and its initial condition has weaker dependency on k than the "bad"" method.
The "had" method may have better performance when = O(1) because under this case the convergence rates do not differ much between the "good" and "bad" method while the latter one usually has a cheaper computational cost per iteration.
The condition number is very large in most of the cases which means the "good" method generally outperforms the "bad" one. We summarize the different convergence rates, initial conditions and suitable scenes of the block good and bad Broyden's 's methods Table
The similar phenomenon also holds for the classical good and bad Broyden's 's methods 29 iterations can be reformulated as
whose
Xt+1 x, F
Bi+1 BlockG--roydde- [B,, u.) B, +
(y: B.
(19)
u, u,
and
X++1 X₁ (x,),
H H = Block-B- B-Broyden Hr, Je+1, u.) = H. + uu, H.ydY
(20)
y Yt
respectively, where u, X Xx. Jez1 = Io J(x; su, su,)ds and y: F(x++)) F(x,).
The different convergent behavior of the block Broyden's 's updates helps us understand the perfor- mance difference between the classical good and bad Broyden's methods for the similarity of their frameworks.
6 Experiments
We validate our methods on the Chandrasekhar H-equation which well studied in the previous literature [25 29 50) as follows
Fx(x) 22
(21)
2N
M4
+ W4
j=1
where x [x1,-... INl N and F(x) (x), Fx)] N. We denote GB-CI and
BB-CI as the classical good and bad Broyden's methods respectively 29 We denote GB-Gr and
GB-Ra as the greedy and randomized Broyden's methods (50] respectively. Our experiments are conducted on PC with Apple M1 and all algorithms are implemented in Python 3.8.12.
Our first experiment considers three cases: N = 200, = 300, = 400. set c 10 for the H-equation and choose the block size k N/10 for the proposed methods. In all cases, we use the same inputs B, = 0. (H, 10Ix) for all algorithms. We use classical Newton method the warm-up algorithm to obtain Xo which satisfies the local condition and take it the

---

10a1
88
10"
10
GB-Ra
10
10-5
10-
BGB
068
10
"0
10->
10-33
10-2
10-23
150
300
200
400
300
600
(a) . 200 (iteration)
(b) V 300 (iteration)
(c) N 400 (iteration)
10"1
10
10
10
10-5
10-3
10
10
10
10-13
10-22
10-22
0.0
0.1
0.2
0.0
0.2
0.4
0.0
0.3
0.6
(d) 200 (time)
(e)
300 (time)
(1)
400 (time)
Figure 1: We demonstrate iteration numbers vs. | [xx)ll2 and CPU time (second) vs. F [(x)]l2 for
H H-equation with different equation numbers N.
initial point for all methods. We compare the proposed BGB and BBB algorithm with baselines and present the results of iteration number against [|F(x)]l2 and running time against [[(x)]2 in Figure [ We observe that the proposed block good Broyden's method (BGB) outperforms the baselines in all cases, but the block bad Broyden's method (BBB) does not perform very well. This mainly because k is very large this setting (K R 10%). We also note that the classical Broyden's methods (GB-CI and BB-CI) are numerical unstable. Specifically, they do not guarantee the descent of [xx)) and encounter nan value during the iterations. The BB-CI algorithm even fails to converge after some iterations. Such instability of the classical Broyden's 's methods is also observed in the previous literature 22 50
Our second experiment explores the performance of the proposed block Broyden's methods with different block size. We also study whether BBB algorithm has good performance for the nonlinear equation which Jacobian of the solution small condition number. By fixing N 400 and setting
e = (1-10-1, 1-1003 1- }, we obtain different condition numbers of (1 as α = 2,31, 2,,1,227 327. We present the results in Figure 2 For each k, we also vary the block size k [1, 10, 100) for BGB and BBB algorithms. We observe that when x = (1), BBB outperforms BGB in terms the CPU time (Figure 2 (d). (c)). which matches our analysis in section 5 We also find that larger block size will lead to faster convergence in terms the iterations ((a), (b), (c) of Figure 2}. which verifies theoretical results in section 4
7 Conclusion
In this paper, we have proposed the block Broyden's methods for solving nonlinear equations. The proposed block good Broyden's method enjoys a faster superlincar rate than all the existing Broy- den's methods. We have also shown that the block bad Broyden's update approximates the inverse of the object matrix with an explicit linear rate and proposed the block bad Broyden's 's method ac- cordingly. The established convergence results for the block good and bad methods bring new understanding on the performance difference between the good and bad Broyden's methods. Espe- cially, they explain why good Broyden's 's method generally outperforms the "bad" one.
For the future work, it is possible to incorporate the safeguard mechanism in Wang et al. to re- move the assumption on the Jacobian estimator (Assumptionf 4.2). It will also be interesting to study the global behavior based on the recent advance in Jiang al. [2]] and design efficient stochastic or
sketched algorithms 48 49 52 for solving nonlinear equations.

---

10
888
10:2
10
208.5-19
10
10
10-
10-16
10-10
10-26
10-14
10-24
12
80
(a) (iteration)
(b) 31 (iteration)
(c) 327 (iteration)
-0
10-2
10
10
10"
10-10
10-10
10-20
10-14
10-14
10-34
0.000
0.008
0.016
0.00
0.05
0.10
0.0
0.1
0.2
(d)x (time)
(time)
(l)
(time)
Figure 2: We demonstrate iteration numbers vs.
| (x [x) and CPU time (second) vs. | [F()]l2 for
H H-equation with different condition number n.
Acknowledgement
We would like to thank Haishan Ye for valuable discussion. Cheng Chen is supported by National Natural Science Foundation of China (No. 62306116) and the Dean's fund Shanghai Key Labo- ratory of Trustworthy Computing. Luo Luo is supported by National Natural Science Foundation of China (No. 62206058) and Shanghai Sailing Program (22YF1402900), John C.S. Lui is supported in part by the Hong Kong GRC 14215722.
References
[1] Mehiddin AL- Al-Baali, Emilio Spedicato, and Francesca Maggioni. Broyden's quasi-Newton methods for nonlinear system of equations and unconstrained optimization: review and open problems. Optimization Methods and Software, 29(5):937-554, 2014.
[2] Lucian-Liviu Albu. Non-linear models: applications in economics.
Available at SSRN
1565345, 2006.
[3] Meysam Alizamir, Sungwon Kim, Ozgur Kisi, and Mohammad //ounemattKKrmaan A com- parative study of several machine learning based non-linear regression methods in estimating solar radiation: Case studies of the usa and turkey regions. Energy, 197:117239, 2020.
[4] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, 32, 2019.
[5] Eloise Berthier, Justin Carpentier, and Francis Bach. Fast and robust stability region estimation for nonlinear dynamical systems. In 202/ European Control Conference (ECC), pages 1412 1419. IEEE, 2021.
[6] Charles G. Broyden. A class of methods for solving nonlinear simultancous equations. Math- ematics of computation, 19(92):577-593, 1965.
[7] Charles G. Broyden. Quasi-Newton methods and their application to function minimisation. Mathematics of Compulation, 21(99):368-3811 1967.
[8] Charles G. Broyden. The convergence of class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 6(1):76-90) 1970.
[9] Charles G. Broyden. The convergence of a class of double-rank minimization algorithms: 2. the new algorithm. IMA journal of applied mathematics, 6(3):222-231, 1970.
10

---

[10] Charles G. Broyden. On the discovery of the "good Broyden" method. Mathematical pro- gramming, 87:209-213. 2000.
[11] Charles G. Broyden, E. Dennis, and Jorge J. Moré. On the local and superlinear convergence of quasi-Newton methods. IMA Journal of Applied Mathematics, 12(3):223-245 1973.
[12] Caterina Buizza, César Quilodrán Casas, Philip Nadler, Julian Mack, Stefano Marrone, Zainab Titus, Clémence Le Cornec, Evelyn Heylen, Tolga Dur, Luis Baca Ruiz, et al. Data learning: integrating data assimilation and machine learning. Journal of Computational Science, 58: 101525, 2022.
[13] Richard H. Byrd, Jorge Nocedal, and Ya-Xiang Yuan. Global convergence of a cass of quasi- Newton methods on convex problems. SIAM Journal on Numerical Analysis, 24(5):1171- 1190, 1987.
[14] Timothy A. Davis. Block matrix methods: Taking advantage of high-performance computers. Technical report, Technical Report TR-98-024, 1998.
[15] Alexandre Défossez and Francis Bach. Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pages 205-213. PMLR, 2015.
[16] John Dennis Jr and Robert B. Schnabel. Numerical methods for unconstrained optimization and nonlinear equations. SIAM, 1996.
[17] Jin-yan Fan and Ya-Xiang Yuan. On the quadratic convergence of the wwvebbeg--Maruarde method without nonsingularity assumption. Computing, 74:23-39, 2005.
[18] J. Frehse and A. Bensoussan. Nonlinear elliptic systems in stochastic game theory. Journal für die reine und angewandte Mathematik, 350:23-67, 1984.
[19] Philip Gill and Walter Murray. Algorithms for the solution of the nonlinear least-squares problem. SIAM Journal on Numerical Analysis, 15(5)9977-992, 1978.
[20] Nick Gould, Dominique Orban, and Philippe Toint. Numerical methods for large-scale non- linear optimization. Acta Numerica, 14:299-361, 2005.
[21] Robert M. Gower and Peter Richtárik. Randomized quasi-Newton updates are linearly conver- gent matrix inversion algorithms. arXiv preprint 1602.0160 2016.
[22] Andreas Griewank. Broyden updating, the good and the bad. Optimization Stories, Documenta Mathematica. Extra Volume: Optimization Stories, pages 301-315, 2012.
[23] Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approx- imation: A quasi-Newton method with global non-asympiotic superlinear convergence. In Annual Conference Computational Learning Theory, 2023.
[24] Qiujiang Jin and Aryan Mokhtari. Non-asymptotic superlinear convergence of standard quasi- Newton methods. Mathematical Programming, pages 1-49, 2022.
[25] Carl T. Kelley. Iterative methods for linear and nonlinear equations. SIAM, 1995.
[26] Carl T. Kelley. Solving nonlinear equations with Newton's 's method. SIAM, 2003.
[27] Carl T. Kelley and Ekkehard W. Sachs. A new proof of superlinear convergence for Broyden's method in Hilbert space. SIAM Journal Optimization, 1(1):146-150, 1991.
[28] Kenneth Levenberg. method for the solution of certain non-linear problems in least squares. Quarterly of applied mathematics, 142):664-166 1944.
[29] Dachao Lin, Haishan Ye, and Zhihua Zhang. Explicit superlinear convergence rates of Broy- den's methods in nonlinear equations. arXiv preprint arXiv:2109.01974 2021.
[30] Dachao Lin, Haishan Ye, and Zhihua Zhang. Explicit convergence rates of greedy and random quasi-Newton methods. Journal of Machine Learning Research, 23(162):1-40, 2022.

---

[31] Chengehang Liu and Luo Luo. quasi-Newton methods for saddle point problems. Advances in Neural Information Processing Systems, 35:3975-3987, 2022.
[32] Chengehang Liu, Shuxian Bi, Luo Luo, and John CS Lui. Partial-quasiNeewtor methods: Efficient algorithms for minimax optimization problems with unbalanced dimensionality. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1031-1041, 2022.
[33] Chengchang Liu, Cheng Chen, and Luo Luo. Symmetric rank-k methods. arXiv preprint arXiv:2303.16118, 2023.
[34] Donald W. Marquardt. An algorithm for least-squares estimation of nonlinear parameters. Journal of the society for Industrial and Applied Mathematics, 11(2):431 1411, 1963.
[35] José Mario Martinez. Practical quasi-Newton methods for solving nonlinear systems. Journal of computational and Applied Mathematics, 124(1-2)97-1221,200
[36] Konstantin Mishchenko. Regularized Newton method with global O11/²²) convergence.
arXiv preprint arXiv:2112.02089) 2021.
[37] Jorge J. Moré. A collection of nonlinear model problems. Technical report, Argonne National Lab., IL (USA), 1989.
[38] Yu. Nesterov. Modified Gauss-Newton scheme with worst case guarantces for global perfor- mance. Optimisation methods and software, 22(3):469-483) 4839 2007.
[39] Mojtaba Nourian and Peter E. Caines, e-Nash mean field game theory for nonlinear stochastic dynamical systems with major and minor agents. SIAM Journal on Control and Optimization, 5 514):3302-33311 2013.
[40] M.J.D. Powell. A hybrid method for nonlinear equations. Numerical Methods for Nonlinear Algebraic Equations, 1970.
[41] Anton Rodomanov and Yurii Nesterov. Greedy quasi-Newton methods with explicit superlin- ear convergence. SIAM Journal on Optimization, 31(1):755-81,,022
[42] Anton Rodomanov and Yurii Nesterov. New results on superlinear convergence of classical quasi-Newton methods. Journal of optimization theory and applications, 188(3):744-777) -66,, 2021.
[43] Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi- Newton methods. Mathematical Programming, pages 1-32, 2021.
[44] Damien Scieur, Edouard Oyallon, Alexandre d' Aspremont, and Francis Bach. Online regular- ized nonlinear acceleration. arXiv preprint 1xXiv:/805.09639, 2018.
[45] David F. Shanno. Conditioning of quasi-Newton methods for function minimization. Mathe- matics of computation, 24(11 (4(111):647-656 1970.
[46] Jack Sherman and Winifred J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. The Annals of Mathematical Statistics, 21(1): 124-127, 1950.
[47] Ph L. Toint. On large scale nonlinear least squares calculations. SIAM Journal on Scientific and Statistical Computing, 8(3):416-435, 1987.
[48] Xiao Wang, Shigian Ma. Donald Goldfarb, and Wei Liu. Stochastic quasi-Newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2):927-966, 2017.
[49] Xiaoyu Wang, Xiao Wang, and Ya-Xiang Yuan. Stochastic proximal quasi-Newton methods for non-convex composite optimization. Optimization Methods and Software, 34(5):922-948, 2019.
12

---

[50] Haishan Ye, Dachao Lin, and Zhihua Zhang. Greedy and random Broyden's methods with ex- plicit superlinear convergence rates in nonlinear equations. arXiv preprint arXiv:2110.08572, 2021.
[51] Haishan Ye, Dachao Lin, Xiangyu Chang, and Zhihua Zhang. Towards explicit superlinear convergence rate for SRI. Mathematical Programming, pages 1-31, 2022.
[52] Rui Yuan, Alessandro Lazaric, and Robert M. Gower. Sketched Newton- SIAM Journal Optimization, 32(3):1555-158; 2022.
[53] Ya-Xiang Yuan, Trust region algorithms for nonlinear equations. Information, 1:7-20, 1998.
[54] Ya-Xiang Yuan. Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical algebra, control & optimization, 1(1):15, 2011.
13


Reviews:
[{"review_id": "qehpN8Bj83", "reviewer": "Reviewer_N1wb", "summary": "The paper proposes variants of block Broyden's methods for solving nonlinear equations. Explicit convergence rates are established, and the numerical experiment validates the theoretical analysis.", "questions": "1. The Assumption 4.1 seems to be a strong assumption. Is it possible that the nonsingularity of the matrices is guaranteed by the iterative schemes themselves?\n\n2. The condition (10) and condition (16) require that the initial Jacobian approximation is sufficiently close to the exact Jacobian matrix. Is it a realistic assumption?", "limitations": "The biggest limitation of the proposed algorithms is the large memory usage and high computational cost, but there is no discussion of this issue. It is likely that these algorithms are not suitable for solving large-scale nonlinear equations in practice.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper provides explicit convergence rates of the proposed block Broyden's methods. The theoretical analysis is sound, and the results improve some previous results related to Broyden's methods. The claims are supported by the numerical results.", "weaknesses": "Although this paper makes a contribution to the theoretical study of Broyden's method, there are some outstanding weaknesses that may outweigh the strengths.\n\n1. The novelty of the proposed block Broyden's method is limited. The proposed methods are very similar to the ones given in [1] (Section 7 and Table 8.1 in [1]). The distinction should be clearly explained in the main paper.\n\n2. The theoretical analysis is limited. Only local convergence is established. There is no discussion about the global convergence.\n\n3. The implementation details of the algorithms are totally missing. It is likely that these algorithms cannot be efficiently applied to real-world applications. For example, each step in Algorithm 1 and Algorithm 2 needs information about the Jacobian matrix, which can incur significant overhead compared with the classical quasi-Newton methods based on secant equations (as shown in Figure 1).\n\n4. The memory cost can be one of the biggest obstacles for the proposed methods to solving high-dimensional problems since the approximate Jacobian matrix or the approximate inverse Jacobian matrix of dimension $d^2$ needs to be maintained. However, there is no discussion about this severe issue.\n\n5. The experimental part needs to be improved. The algorithms were only tested on a simple problem, so it is desirable to consider more different problems to make the claims more convincing. Besides, some well-known methods, e.g., the Jacobian-free Newton-Krylov method, were not compared.\n\nRegarding to the writing, it is better to reorganize the materials to focus on the main contributions. For example, it is rather strange to analyze the convergence of the Block Broyden's update first in Section 3, which is not the algorithm proposed in this paper.\n\nSome typos:\n1. Line 29: approximate → approximates, update → updates\n\n2. Line 150: better → better than\n\n3. Line 209: The book [31] has no content about the Chandrasekhar H-equation.\n\n4. Line 354: The equality is not correct.\n\n[1] R.M. Gower and P. Richtarik. Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms. SIAM J. Matrix Anal. Appl., 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and helpful comments.\n\n\n>  The novelty of the proposed block Broyden's method is limited. The proposed methods are very similar to the ones given in [1] (Section 7 and Table 8.1 in [1]). The distinction should be clearly explained in the main paper.\n\n**Response:** We present comprehensive comparison to Gower and Peter's work and clearly clarify the distinction. Please refer to the global response (Section 2).\n\n\n> The theoretical analysis is limited. Only local convergence is established. There is no discussion about the global convergence.\n\n**Response:**\nEven our paper only present the local convergence rate, we think such theoretical result is significant. We improve the local superlinear convergence of nonlinear equations. Specially, the state-of-the-art result is $\\mathcal{O}((1-1/d)^{t(t-1)/4})$, while ours is $\\mathcal{O}((1-k/d)^{t(t-1)/4})$ (See Table 2). We also improve the local condition of the state-of-the-art method (See line 149-157).\n\nOn the other hand, our method only assumes the non-degeneration of ${\\bf J}({\\bf x}\\_\\*)$ (Assumption 2.1) and the continuity of ${\\bf J}({\\bf x})$ along the path to ${\\bf x}\\_\\*$ (Assumption 2.2). Hence, we think it is reasonable to focus on the local behavior around the ${\\bf x}\\_\\*$. To the best of our knowledge, no global superlinear rate has been established for solving nonlinear equations under such mild assumptions.\n\nThough the global superlinear of quasi-Newton is established for convex optimization very recently [A], it is still unknown whether general nonlinear equation problems have similar results. We guess that it is possible to generalize the idea of [A] and use line search strategy to establish the global convergence for solving nonlinear equations. We will study it in the future.\nWe are happy to incorporate more discussion based on the above response in revision.\n\n> The implementation details of the algorithms are totally missing. It is likely that ...\n\n**Response:**\nThank you for your suggestion. We will add the implementation details of the algorithms in the revision. Actually, our algorithms **do not** require the full information of the Jacobian matrix. When updating the Jacobian estimator by the block updates (line 6 of Algorithm 1 and 2), we only need to calculate $k$ columns of the Jacobian matrix which is selected by the sampling matrix ${\\bf U}_t$. Since $k\\ll d$, it is cheap to obtain the partial information of the Jacobian. Using this partial information of the Jacobian can significantly improves the convergence rates compared to the classical Broyden's methods (see Table 1).\n\nThe efficiency of proposed methods are also validated in our experiments part. As a result, although our methods need to calculate a bit more information per iteration, they require less running time than classical ones (see Figure 1 (d), (e), (f)). \n\n> The memory cost can be one of the biggest obstacles for the proposed methods to solving high-dimensional problems since the approximate Jacobian matrix or the approximate inverse Jacobian matrix of dimension needs to be maintained. However, there is no discussion about this severe issue.\n\n**Response:**\nQuasi-Newton methods always require $\\mathcal{O}(d^2)$ space complexity to store the estimator of Jacobian (or the inverse of Jacobian) to achieve the superlinear convergence rates and efficient computation.\n\nTo reduce the space complexity, limited memory quasi-Newton methods are developed for solving convex optimization (a very special case of solving nonlinear equations). \nIt would be interesting to study limited-memory methods of solving nonlinear equations in the future work. We are happy to involve this discussion in revision.\n\n> The experimental part needs to be improved. \n\n**Response:** We have added experiments based on the reviewer's suggestion, please refer to the global response (Section 1).\n\n\n> The Assumption 4.1 seems to be a strong assumption. Is it possible that the nonsingularity of the matrices is guaranteed by the iterative schemes themselves?\n\n**Response:** We provide discussion on Assumption 4.1, illustrate that it is a reasonable assumption and give some potential ways to eliminate this assumption. Please refer to the global response (Section 3).\n\n>The condition (10) and condition (16) require that the initial Jacobian approximation is sufficiently close to the exact Jacobian matrix. Is it a realistic assumption?\n\nThe condition that the initial Jacobian approximation is sufficiently close to the exact Jacobian matrix is standard for establishing local convergence rates of Broyden's methods ([Theorem 11.5, 31], [Theorem 1, 24] and [Theorem 4.3, 38]). \nFurthermore, the initial condition of Algorithm 1 is weaker than that of the state-of-art method [38] (line 150-161) for solving the nonlinear equations. \n\nOn the other hand, we can use the matrix approximation technique in [18] to achieve a sufficient accurate initial estimator of ${\\bf J}({\\bf x}_0)$ (or $[{\\bf J}({\\bf x}_0)]^{-1}$). Since we assume that ${\\bf x}_0$ is closed to ${\\bf x}^*$, condition (10) (or condition (16)) is always satisfied and thus is a realistic assumption.\n\n\n\n**Response on the writing and typos:**\nWe will incorporate the reviewer's valuable suggestions on improving the presentation in the revision and also fix the typos.\n* For line 209, the reference should be [20] (see Section 5.6 of [20]) rather than [31].\n* For line 354, the equality should be fixed as \n\n$$\n        {\\bf J}\\_\\*^{\\top}{\\bf J}\\_\\* = {\\bf J}({\\bf x})^{\\top}{\\bf J}({\\bf x}) + ({\\bf J}\\_\\*^{\\top}{\\bf J}\\_\\* -{\\bf J}({\\bf x})^{\\top}{\\bf J}({\\bf x})).\n$$\n\n\n\n**References**\n\n [A]. Ruichen Jiang, Qiujiang Jin, Aryan Mokhtari. Online learning guided curvature approximation: A quasi-Newton method with global non-asymptotic superlinear convergence. Conference on Learning Theory, PMLR, 195:1962-1992, 2023."}, {"review_id": "hgJ2qkCIvI", "reviewer": "Reviewer_YNqM", "summary": "This paper studies block Broyden's methods for solving nonlinear equation systems and presents explicit local superlinear convergence rates. For the block good Broyden's method, the convergence rate is independent of the condition number of the Jacobian matrix at the solution, which that of the block bad Broyden's method depends on the condition number heavily. Numerical experiments validate the theoretical analysis. ", "questions": "- The rank $k$ is not defined in the contribution 1 when it is firstly used.\n\n- What is the definition of $\\hat{\\kappa}$ in line 51, equation (8) and Table 2?\n\n- I suggest to clarify the meaning of $\\kappa$ in line 59. \n\n- In line 78, $x^*$ is defined as 'the solution'. I suggest to clarify the uniqueness of the solution for the problem (1) considered. The nonlinear equation (1) may have multiple solutions.\n\n- What is the meaning of the bracket notation, for example that used in Table 1?\n\n- What is the meaning of $\\operatorname{e}$'s in equation (11), (12), (17) and  (18)?\n\n- Typos: line 24, 'large-scale'; it seems to be '$d$' (other than '$\\operatorname{d}$') in  equation (11), (17) and (18).  \n\n- Typos: line 94 summarized **in** Table 2.\n\n- Typos: line 150, our BGB algorithm is better **than** greedy ...\n\n- Please check the format of the reference list, particularly the letter case (in [3], [5], [9], [13]) and the math symbol (in [15]), etc.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The authors provided explicit local superlinear convergence rates for  block good Broyden's method and block bad Broyden's method. The rate improves previous results and reveals the advantage of block update.\n\n- The established convergence results give new understanding on the performance difference between the good and bad Broyden's methods. \n\n- The paper is clearly written and well-organized.", "weaknesses": "- In Algotithm 1 and Algotithm 2, the Jacobian matrix is explicitly needed even when $k=1$, while that is not the case for classic Broyden's methods. \n- The convergence rate depends on the dimension. When $d\\gg 1$, the rate $1-1/d$  is close to $1$ and the convergence will be slow. \n- Essentially the algorithms and analysis is the block version of previous work [38]. Although the comparison with [38] is include, it is still not so clear if this generalization (from rank $1$ to rank $k$ ) is straight-forward. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and helpful comments.\n\n> In Algotithm 1 and Algotithm 2, the Jacobian matrix is explicitly needed even when $k=1$, while that is not the case for classic Broyden's methods.\n\n**Response:**\nOur algorithms **do not** require the full information of the Jacobian matrix. When updating the Jacobian estimator by the block updates (line 6 of Algorithm 1 and 2), we only need to calculate $k$ columns of the Jacobian matrix which is selected by the sampling matrix ${\\bf U}_t$. Since $k\\ll d$, it is cheap to obtain the partial information of the Jacobian. Using this partial information of the Jacobian can significantly improves the convergence rates compared to the classical Broyden's methods (see Table 1).\n\nThe efficiency of proposed methods are also validated in our experiments part. As a result, although our methods need to calculate a bit more information per iteration, they require less running time than classical ones (see Figure 1 (d), (e), (f)). \n\n \n\n\n> The convergence rate depends on the dimension. When $d\\gg 1$, the rate $1-1/d$ is close to 1\n and the convergence will be slow.\n\n**Response:**\nOur block good Broyden's method has the rate of $\\mathcal{O}((1-k/d)^{t(t-1)/4})$, while the classical Broyden's method converges with the rate of $\\mathcal{O}(1/{t}^{t/2})$. \nHence, our method is faster than the classical one if the dimension satisfies $d \\le \\mathcal{O}(kt/\\ln(t))$.  \n\nOn the other hand, such dimension dependency rates are commonly appeared in greedy or random quasi-Newton methods, even for the convex minimization problems [A, 24].\n\n\n> Essentially the algorithms and analysis is the block version of previous work [38]. Although the comparison with [38] is include, it is still not so clear if this generalization (from rank 1 to rank $k$) is straight-forward.\n\n**Response:**\nThe generalization from rank-$1$ to rank-$k$ is not straight-forward. None of previous work on block updates demonstrate the superiority of using rank-$k$ update over the rank-1 update. For example, [18] propose the block bad Broyden's update for matrix approximation but the its analysis only with the implicit linear rate ([Section 8.3, 18]), while our analysis (Theorem 3.2) clearly show the advance of using rank-$k$ update.\n\nIn addition, our work does not only improve the convergence rates by using the block updates compared with [38], but also weaken the initial condition by carefully choosing the measure (line 135) and generalizing the lemma for the matrix approximation (Theorem 3.1 and Remark 3.3) where we allow any nonsingular matrix ${\\bf C}$ in equation (5) and (6). We show that our initial condition is strictly weaker than that in [38] (line 149-157).\n\nAlso, [38] only gives the random or greedy version of the good Broyden's methods, we present the block bad Broyden's methods which are novel and firstly show the estimator matrix converges to the ${\\bf J}_*^{-1}$.\n\n> The rank $k$ is not defined in the contribution 1 when it is firstly used.\n\n**Response:**\n$k$ is the rank of the differential between the updated matrix and the original matrix in the matrix approximation update in the contribution 1. We will clarify this in the revision.\n\n> What is the definition of $\\hat{\\kappa}$ in line 51, equation (8) and Table 2?\n\n**Response:**\nIn line 51, equation (8) and Table 2, we define $\\hat{\\kappa}=\\sigma_{\\max}({\\bf A})/\\sigma_{\\min}({\\bf A})$ where $\\sigma_{\\max}(\\bf A)$, $\\sigma_{\\min}(\\bf A)$ are the largest and smallest singular value of a given non-singular matrix ${\\bf A}$ respectively. \n\n> I suggest to clarify the meaning of $\\kappa$ in line 59.\n\n**Response:**  In line 59, we will define $\\kappa$ as the condition-number of ${\\bf J}({\\bf x}^\\*)$.\n\n> In line 78, ${\\bf x}^*$ is defined as 'the solution'. I suggest to clarify the uniqueness of the solution for the problem (1) considered. The nonlinear equation (1) may have multiple solutions.\n\n**Response:** Thanks for the advice, we will clarify the uniqueness of the solution of eq.1. \n\n> What is the meaning of the bracket notation, for example that used in Table 1?\n\n**Response:** The notation $[d]$ means $\\{1,2\\cdots,d\\}$.\n\n> What is the meaning of $e$'s in equation (11), (12), (17) and (18)?\n\n**Response:** The notation $e$ in equations (11), (12), (17) and (18) presents the the Euler constant, i.e, $e=2.718...$.\n\n\nWe would like to thank the reviewer's valuable suggestion on improving the presentation, we will incorporate these in the revision. We will fix the typos and check the format of the reference list.\n\n\n**References**\n\n [A]. Anton Rodomanov and Yurii Nesterov. Greedy quasi-Newton methods with explicit superlinear convergence. SIAM Journal on Optimization, 31(1):785–811, 2021."}, {"review_id": "cCOaSXkAL5", "reviewer": "Reviewer_XomP", "summary": "This paper extends the Broyden family quasi-Newton method into block setting and shows explicit local linear convergence rate under mild conditions. More specifically, the authors studied both the “good” and “bad” Broyden algorithms, namely the update on the Hessian/Jacobian and the inverse Hessian/Jacobian respectively. The authors provided some insights on why the “good” update is better than the “bad” update and provided numerical experiments to support their findings.", "questions": "1. Perhaps the biggest question I have toward the comparison of “good” and “bad” Broyden is that for the good Broyden method, still it computes the inverse of $B_{t}^{-1}$, which means that the dependency on the condition number is implicitly incorporated. I’d appreciate to hear from the author on how this problem is addressed (and how previous literature deals with this problem);\n2. In assumption 4.1, the assumption is imposed toward the sequence $\\{B_{t}\\}$, which is not very good. Is there a possible safeguard mechanism so that the Jacobians are well-defined? This is pretty common in quasi-Newton literatures, such as [1].\n3. Another problem is that the block update seems to be lack of motivations. Isn’t the case $k=1$ already enough to show the dependency of $\\kappa$ for the “bad” Broyden update? Certainly the $k$ in each of the convergence result and the numerical experiments show the efficiency of block updates, but usually block updates are for bigger targets such as parallelization or decentralized update. Could the authors give some comment on this direction;\n4. The numerical experiments on Chandrasekhar H-equation is not sufficient to show the efficiency of the proposed method. It would be interesting to see applications and experiments on problems with real-world data. In particular, would the “bad” Broyden method be better when the problem dimension is relatively large?\n\n\nReferences:\n[1] Wang, Xiao, et al. \"Stochastic quasi-Newton methods for nonconvex stochastic optimization.\" SIAM Journal on Optimization 27.2 (2017): 927-956.", "limitations": "The limitation is well stated in weakness and question sections.\n\nI’m not aware of any potential negative social impact of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theory is well-rounded and the method is consistent with existing works. The analysis on Algorithm 2 is interesting which incorporates the condition number of the Jacobian and brings insights on why the convergence of “bad” Broyden method is worse in practice. ", "weaknesses": "(Please reply to the Questions section directly) First the “good” Broyden family still computes the inverse of matrix in the update; Second, the Assumption 4.1 is imposed toward the iterates directly, which is not very good; Third, it’s not very clear why we consider the block update. Also the numerical experiment is not adequate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and helpful comments.\n\n> Perhaps the biggest question I have toward the comparison of “good” and “bad” Broyden is that for the good Broyden method, still it computes the inverse of ${\\bf B}_t^{-1}$, which means that the dependency on the condition number is implicitly incorporated. I’d appreciate to hear from the author on how this problem is addressed (and how previous literature deals with this problem);\n\n**Response:**\nNotice that in the analysis of the good Broyden's method, we only care about the error between the estimator ${\\bf B}\\_t$ and the Jacobian ${\\bf J}\\_\\*$, i.e., $\\|\\|{\\bf C}({\\bf B}\\_t-{\\bf J}\\_\\*)\\|\\|\\_F$, rather than the error between ${\\bf B}\\_t^{-1}$ and ${\\bf J}\\_\\*^{-1}$. Thus the convergence rate of the good Broyden's method is condition-number free.\n\nPrevious works [25], [38] also established such condition-number free superlinear rates for quasi-Newton methods on convex optimization and nonlinear equations respectively. Their analysis is also based on controlling the error between the estimator matrix and the exact Jacobian (or Hessian) matrix which do not incorporate the condition number.\n\n\nOn the other hand, the analysis of the bad Broyden's method considers the error between ${\\bf H}_t$ and ${\\bf J}\\_\\*^{-1}$, which incorporates the condition number in the convergence rate. \n\n\n\n> In assumption 4.1, the assumption is imposed toward the sequence ${\\bf B}_t$, which is not very good. Is there a possible safeguard mechanism so that the Jacobians are well-defined? This is pretty common in quasi-Newton literatures, such as [1].\n\n**Response:** We provide discussion on Assumption 4.1, illustrate that it is a reasonable assumption and give some potential ways to eliminate this Assumption. Please refer to the global response (Section 3).\n\n> Another problem is that the block update seems to be lack of motivations. Isn’t the case already enough to show the dependency of $\\kappa$ for the “bad” Broyden update? Certainly the $k$ in each of the convergence result and the numerical experiments show the efficiency of block updates, but usually block updates are for bigger targets such as parallelization or decentralized update. Could the authors give some comment on this direction;\n\n**Response:**\nThe block updates are very important for high performance computing. It can increase the reuse rate of the data in cache and take advantage of parallel computing. For more details, please refer to [A]. We will provide discussion on this topic in the revision.\n\n\n> The numerical experiments on Chandrasekhar H-equation is not sufficient to show the efficiency of the proposed method. It would be interesting to see applications and experiments on problems with real-world data. In particular, would the “bad” Broyden method be better when the problem dimension is relatively large?\n\n**Response:**\nWe have added experiments based on the reviewer's suggestion, please refer to the global response (Section 1). We did not find that the block bad method would be better than the block good method when the dimension is relatively large.\n\n\n**References**\n\n[A] Tim Davis. Block matrix methods: Taking advantage of high-performance computers. Technical Report TR-98-024, Computer and Information Sciences Department, University of Florida, 1998.\n"}, {"review_id": "uPMUVIhqCo", "reviewer": "Reviewer_X3mb", "summary": "In this work the authors introduce block variants of both good and bad Broyden's methods, which exhibit explicit local superlinear convergence rates. The block good Broyden's method, in particular, demonstrates a faster convergence rate compared to existing Broyden's methods that are not dependent on the condition number. This is achieved by leveraging multiple rank modifications on the Jacobian estimator. On the other hand, the block bad Broyden's method directly estimates the inverse of the Jacobian, resulting in reduced computational costs during the iteration process. The theoretical findings offer new insights into why the good Broyden's method tends to outperform the bad Broyden's method in most cases. Empirical results further validate the superiority of the proposed methods and affirm the theoretical analysis conducted by the authors.", "questions": "* Can you compare the proposed method with the results presented by [1]?\n*  Why did you choose Chandrasekhar H-equation to conduct the experiments for the given method? \n\n\n[1] Robert M Gower and Peter Richtarik. Randomized quasi-newton updates are linearly convergent matrix inversion algorithms. arXiv preprint arXiv:1602.01768, 2016.", "limitations": "None.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors provide explicit convergence rates for the block good Broyden’s update and the block bad Broyden’s update\n* The block good Broyden’s update can approximate a nonsingular matrix A with a linear rate of $(1-k/d)^t$  and the “bad” update can approximate the inverse matrix $A^{−1}$ with an linear rate of $(1-k/(d \\hat{\\kappa}^2))^t$\n* They propose the first explicit convergence rate for the block bad Broyden’s update.\n* The assumptions are supported by theory and experiments.", "weaknesses": "In the experiment section Figure 1 and Figure 2 are a little bit confusing as for example Figure 1(a) and Figure 1(d) represents the experiments for the same N so they can be grouped under the same subfigure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and helpful comments.\n\n> In the experiment section Figure 1 and Figure 2 are a little bit confusing as for example Figure 1(a) and Figure 1(d) represents the experiments for the same N so they can be grouped under the same subfigure.\n\n**Response:**\nWe thank the author for pointing this and would like to improve the figures in the revision based on the suggestion. \n\n\n> Can you compare the proposed method with the results presented by [1]?\n\n**Response:**\nWe make comprehensive comparison to the results presented by [1] according to the reviewer's suggestion. Please refer to Section 2 in the global response.\n\n> Why did you choose Chandrasekhar H-equation to conduct the experiments for the given method?\n\n**Response:**\nThe Chandrasekhar H-equation plays an important role in scientific computing [A, B]. As shown in [C] and [Section 5.6, 20], its discrete version can be used in a wide class of problems of analytical radiative transfer theory. Thus we choose it to verify the empirical performance of our methods. In addition, recent studies [24, 38] on nonlinear equations also perform experiments on the H-equation.\n\n\n\n\n**References**\n\n[A] Subrahmanyan Chandrasekhar, Radiative Transfer, Dover, New York, 1960.\n\n[B] Richard W. Leggett. A new approach to the H-equation of Chandrasekhar. SIAM Journal on Mathematical Analysis, 7(4):542-550, 1976: \n\n[C] C. T. Kelley. Approximate methods for the solution of the Chandrasekhar H-equation. Journal of Mathematical Physics, 23(11):2097-2100, 1982."}]

Author rebuttal:
We thank all the reviewers for their detailed and helpful comments. We response to the common issues raised by the reviewers here.

### **1. Additional Experiments**
We have compared the performance of the JFNK (Jacobian-Free Newton Krylov) method with ours on H-equation in Figure 1. We observe that our method outperforms JFNK since JFNK is unstable and very sensitive to the subspace dimension $r$. In addition, JFNK does not have superlinear convergent rates. 

We also test the proposed block Broyden's methods with different block size $k=\{1, 80, 500\}$ on H-equation where we set a relatively large problem dimension $N=2000$ and present the results in Figure 2. 

To verify the efficiency of our methods on real-world data, we adopt quasi-Newton methods to solve the classical logistic regression: 
$$
    \min\_{{\bf x}\in \mathbb{R}^d} f({\bf x}) = \frac{1}{n}\sum\_{i=1}^n \ln(1+\exp(-b\_i{\bf a}\_i^{\top}{\bf x})) + \frac{\lambda}{2}\| \|{\bf x}\|\|^2,
$$
which needs to solve the following nonlinear equations
\begin{align*}
    \lambda {\bf x} - \frac{1}{n}\sum_{i=1}^{n}\frac{\exp{(-b_i{\bf a}_i^{\top}{\bf x})}}{1+\exp(-b_i{\bf a}_i{\bf x})}\cdot b_i{\bf a}_i = {\bf 0}.
\end{align*}

We compare the proposed methods BGB and BBB with GB-Cl, BB-Cl, GB-Ra and JFNK method. We do not compare them with GB-Gr because it use greedy strategy in [38] to choose ${\bf U}\_t$, 
which requires to access the full Jacobian and thus is very expensive in practice. We set the initial Jacobian estimator ${\bf B}_0=\bf I$ for all cases and validate our methods on two real world datasets a9a and w8a from the Libsvm dataset [A] and present the results in Figure 3. The results demonstrate that the proposed BGB method also outperforms the baselines significantly for the logistic regression.

We will add these additional empirical results to the revision.

### **2. Comparison to Gower and Richtárik's work**

Gower and Richtárik's work [B] mainly focus on approximately computing the inverse of a matrix. Their theoretical analysis only provide the approximation error of inverse matrix. On the other hand, our work focus on solving the general nonlinear equations, which is more challenging. We provide convergence analysis for solving nonlinear equations, which is completely not included in Gower and Richtárik's work.

Even for the matrix approximation, our theoretical results improve the results of [B].

- For the block good Broyden's update, We provide the rate of $\mathcal{O}((1-k/d)^t)$ while [Section 5, 18] (arXiv version of [B]) only provides the rate of $\mathcal{O}((1-1/d)^t)$ for the case of $k=1$.

- For the block bad Broyden's update, we provide the explicit rate of $\mathcal{O}((1-k/(d\hat{\kappa}^2))^t)$ while [Remark 7.2, B] (or [Section 8.3, 18]) only gives an implicit rate of $\mathcal{O}((1-\rho)^t)$ where $\rho = 1/\kappa_{2,F}({\bf A}{\bf S})$ can be arbitrary small.

- We evaluate our convergence property on a more general measure than that of Gower and Richtárik [18, B]. Their results hold for $\mathbb{E}[\|\|{\bf B}_t-{\bf A}\|\|_F^2]$ and $\mathbb{E}[{\|\|{\bf H}_t-{\bf A}^{-1}\|\|^2_F}]$ while our results hold for $\mathbb{E}[{\|\|{\bf C}({\bf B}_t-{\bf A})\|\|^2_F}]$ and $\mathbb{E}[{\|\|{\bf C}({\bf H}_t-{\bf A}^{-1})\|\|^2_F}]$ for any non-singular matrix ${\bf C}$.

Please also refer to Table 2 and Remark 3.3 in our paper.


### **3. Discussion on Assumption 4.1**
Assumption 4.1 is standard and widely used in analysis of Broyden's methods (See Theorem 8.2.4 of [13], Assumption 2 of [38]). We think it is reasonable to follow such common assumption.

It is possible to remove Assumption 4.1 if we moderate the initial conditions (10) (or (16)).
Intuitively, based on the non singularity of ${\bf J}\_\*$ and the point-wise smoothness of ${\bf J}(\cdot)$, we can find some local region $\Omega$ where for all ${\bf x}\in\Omega$, ${\bf J}({\bf x})$ is non-singular. When ${\bf B}\_0$ (or ${\bf H}\_0$) is sufficiently closed to ${\bf J}\_\*$ (or ${\bf J}\_\*^{-1}$), we can guarantee the non-singularity of ${\bf B}\_0$, based on Theorem 3.1 (or 3.2), we have ${\bf B}\_{t+1}$ will be closed to the ${\bf J}\_{t+1}$, and hence guarantee the non singularity of ${\bf B}\_{t+1}$ by the iterative schemes. 

We thank reviewer XomP for pointing out the safeguard mechanism in [C] which can keep the Jacobians well-defined. However, the methods in [C] aim to solve minimization problem where the Jacobian (Hessian matrix) is symmetric, while the Jabobian matrix of nonlinear equations may be asymmetric. It is interesting to study how to incorporate the mechanism of [C] into solving nonlinear equations in the future. 

We will involve more discussion based on above response in the revision. 



**References**

[A]. Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Trans-
actions on Intelligent Systems and Technology, 2(27):1–27, 2011.

[B]. Robert M. Gower and Peter Richtárik. Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms. SIAM Journal on Matrix Analysis and Applications, 38(4):1380–1409, 2017.

[C]. Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-Newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2):927-956, 2017.

Meta-review: This paper studies quasi-Newton methods for solving nonlinear equations. Explicit local superlinear convergence rate is provided. One reviewer is negative towards this paper beacuse the high $O(d^2)$ memory cost. Personally, I donot think this is a big issue because this paper studies quasi-Newton methods, which require $O(d^2)$ memory cost in general. The other reviewers are positive. I suggest to accept this paper. The AC had a thorough discussion with the SAC and the SAC agreed on the decision.
Decision: Accept (poster)