Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence
Authors: Dachao Lin
Haishan Ye
Zhihua Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: quasi-Newton methods
superlinear convergence
local convergence
convex optimziation

Abstract: In this paper, we follow Rodomanov and Nesterov’s work to study quasi-Newton methods. We focus on the common SR1 and BFGS quasi-Newton methods to establish better explicit (local) superlinear convergence rates. First, based on the greedy quasi-Newton update which greedily selects the direction to maximize a certain measure of progress, we improve the convergence rate to a condition-number-free superlinear convergence rate. Second, based on the random quasi-Newton update that selects the direction randomly from a spherically symmetric distribution, we show the same superlinear convergence rate established as above. Our analysis is closely related to the approximation of a given Hessian matrix, unconstrained quadratic objective, as well as the general strongly convex, smooth, and strongly self-concordant functions.

Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence
Dachao Lin
Haishan Ye" Zhihua Zhang
Academy for Advanced Interdisciplinary Studies, Peking University School of Management, Xi'an an Jiaotong University; Shenzhen Research Institute of Big Data
3 School of Mathematical Sciences, Peking University: Huawei Noah's Ark Lab 1 iindcchao@pku. edu. en yehaishan@xjtu edw.euu.t.uuuuu.....oo..o....... en zhzhangdmath, pku. edu.
Abstract
In this paper, we follow Rodomanov and Nesterov 19 s work to study quasi- Newton methods. We focus on the common SRI and BFGS quasi-Newton methods to establish better explicit (local) superlinear convergence rates. First, based on the greedy quasi-Newton update which greedily selects the direction to maximize a certain measure of progress, we improve the convergence rate to a condition- number-free superlinear convergence rate. Second, based the random quasi- Newton update that selects the direction randomly from a spherically symmetric distribution, show the same superlinear convergence rate established as above. Our analysis is closely related to the approximation of given Hessian matrix, unconstrained quadratic objective, well as the general strongly convex, smooth and strongly self-concordant functions.
1
Introduction
We study the superlinear convergence of famous quasi-Newton methods that replace the exact Hessian applied in classical Newton methods with certain approximations. The approximation is updated in iterations based some special formulas from the previous variation. There exist various quasi- Newton algorithms with different Hessian approximations. The three most popular versions are the Davidon-Fletchen Fletcher--chheeeeeee Powell (DFP) method 10], the Broylen--Flecher-GGoldde Goldaarb-Saaaaa (BFGS)
method 2
3 9 21). and the Symmetric Rank (SRI) method 1 77. all of which belong to the Broyden family I of quasi-Newtoo algorithms. The most attractive property of quasi-Newton
methods is their superlinear convergence, which can trace back to the 1970s
4 8 [7]. However, the
superlinear convergence rates provided in prior work are asymptotic (5 13
15
22
24
The results
only show that the ratio of successive residuals tends to zero as the running iterations approach to infinity, while still lacking a specific superlinear convergence rate.
Recently, Rodomanov and Nesterov 19 gave the first explicit local superlinear convergence for their proposed new quasi-Newton methods. They introduced greedy quasi-Newton updates by greedily selecting from basis vectors to maximize a certain measure of progress, and established an explicit non-asymptotic bound on the local superlinear convergence mainly applicable to the DFP methods because they reduced all possible Broyden family to the DFP update based on the monotonicity property (see Lemma 2.2 However, the SR1 and BFGS updates are more popular and faster than the DFP update in practice, which also has been verified in their experiments. In addition, Rodomanov and Nesterov [19] also discovered that the randomized methods do not lose superlinear convergence but they did not provide theoretical guarantees.
correspondingly. Their proofs
"Equal Contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Greedy or Random Methods
Strongly Self-concordant Objective
ko
DFP, BFGS, SRI
19
(1 nA
k(k 1)/2
(5) & (1
ho
O (nx (nxlInnuu (n(n))
2n
BFGS, SRI (Corollary 4.4 (1 1 k(k 1)/2
(1 1 No
O (max (n, k) In(nx))
2n
Table 1: Comparison of the existing specific superlinear convergence rates of the random or greedy quasi-Newton methods with our results in the view of (- (see the definition in Eq. (17p), where n is the dimension of parameters, & is the condition number of the objective function, and ko, k are the iteration numbers. Rodomanov and Nesterov [19 's results are suitable for greedy quasi-Newton methods using the Broyden family update, which includes DFP, BFGS, SR1 methods.
Along this line, there are other results of local superlinear convergence analysis. Rodomanov and Nesterov [20] analyzed the well-known DFP and BFGS methods, using a standard Hessian update direction through the previous variation. They demonstrated faster initial convergence rates, while slower final rates compared Rodomanov and Nesterov
[19] 's results. Rodomanov and Nesterov [18] improved Rodomanov and Nesterov 20''s results by reducing the dependence of the condition number и to In K, though having similar worse long-history behavior. Jín and Mokhtari [14] provided a non-asymptoti dimension-free superlinear convergence rate of the original Broyden family when the initial Hessian approximation is also good enough.
In this work, we prove faster convergence rates for greedy and random quasi-Newton algorithms, particularly on the SR1 and BFGS methods. We present our contribution as follows:
First, in the setting of approximating an exact Hessian, we use two update methods: 1) greedy update modified from Rodomanov and Nesterov [19]; 2) rundom update that randomly selects the updating direction from any spherically symmetric distribution. We show that convergence. Particularly, we obtain the superlinear convergence rate O (1- k) for SR1 update, and the linear convergence rate )( for BFGS update, where is the current iteration, and n is the dimension of parameters. Both findings improve the original convergence rate O((1- (11-1)))) [99].
both methods share faster condition-number-fee
Second, we extend our analysis to practical scheme. We show (local) superlinear conver- gence under the SR1 update and BFGS update, when applied to unconstrained quadratic objective or strongly self-concordant functions. We list our results in Table with the same formulation of [19]. Note that in general, the convergence goes through two periods. The first period lasts for kn iterations, and only has a linear convergence rate 0(1 žे )ka). The second period has superlinear convergence rate (((-_))(t-1)/3)) Our revised bound takes fewer first-period iterations ko as well as a faster (condition-number-fiee number-frree superlinear convergence rate in the second period compared to [99]
Notation. We denote vectors by lowercase bold letters (e.g., u. x), and matrices by capital bold letters (e.g., W [wzy]) D) We use c e, for the n-dimensional coordinate directions. Let (A) > ... 2 (A) be the eigenvalues of a real symmetrie matrix A E _ Moreover, ||- denotes the fz-norm (standard Euclidean norm). For a given positive definite matrix A (i.e.,
A 0). we induce the following pair of conjugate Euclidean norms: || [ A - Vx Axx | |x & = V2 fxx) > 0, we prefer to use notation || ll and || Il.. provided that there no ambiguity with the reference function f. We recall the rate of convergence used in this paper.
V ---A. When A
Definition 1.1 (Linear/Superlincar convergence) Suppose sequence { converges to 0 with
lim |xn+1| |x,l
q E 10.
Now suppose another sequence } converges to 3 and satisfies that 1yn - -vl S |r,// Vn We say {un} converges superlinearly if g = 0, linearly if E (0. 1).
Organization. In Section 2
we discuss quasi-Newton updating rules for approximating a positive definite Hessian matrix using the SR1 update (Subsection 2.1 and the BFGS update (Subscction

---

2.2 In Section we analyze previous methods applied to the problem of minimizing a quadratic function. In Section 4 we show that similar results also hold in more general setting the strongly seff-concordant function. We give some empirical results in Section 5 Finally, in Section we present our conclusion.
of minimizing
Quasi-Newton updates
Before starting our theoretical results, we briefly review class of quasi-Newton updating rules for approximating positive definite matrix A E R=x* We follow the definition in [19, employing the following family of updates which describes the Broyden family [16, Section 6.3] of quasi-Newton updates, parameterized by scalar E R.
Definition 2.1 Ler A 3 G (that is, G A is positive semi-definite) For any R", Gu Au, define Broyd, (G, A, u) G. Otherwise, we define
G Auu G Guu T A
(u Gu
Auu" T A +1
Broyd, (G, A, u) -
+
Au
u Au
u Au
(1)
(G A)uu (G A)
+ (1 (1- G
u (G Aju
For several choices of т, we can recover several well-known quasi-Newton methods. corresponds to the well-known SRI update:
For 7 Eq.
(G A)uuu" (G A)
SRI(G, A, u) G
(2)
u' T A)u
For 7BPGS
Au u Gau
[0, 1), we recover the famous BFGS update:
BFGS A, & G Guu T
Auu A
u Gu
u Au
For corresponds to the well-known DFP update:
DFP(G,A,u)) 2 Auu G Guu A
Gu Au
Aun't T A
+
+
(4)
u Au
u
u Au
Additionally, the Broyden family has matrix monotonicity below, showing the relationship among these quasi-Newton methods.
Lemma 2.2 (Rodomanov and Nesterov 2 1, then we have for any RR and
19 Lemmas 2.1 and 2.2) If A - 3 11 for some
E lK with S T2 that (G, Broyd, (G, A. u) Broydd, (G, A,u) u).
And for any T E [0, 1). we have A 3 Broyd, (G, A, u) 1 AA
Hence, < 3 17A for some 2 1, it follows from Lemma 2.2 that
A SRI A, u) = BFGS A, u) = DFP(G, A, u) 1 nA.
Intuitively, the approximation produced by SRI is better than that produced by BFGS. And both of them are better than that produced by DFP. However, Rodomanov and Nesterov 19 deduced the analysis by casting all updates described by Broyden family (r E [0, 1]) into the slowest DFP update (T 1). Moreover, SR1 and BFGS methods also have faster numerical performance in practice. Therefore, we consider there might have faster superlinear convergence rates SR1 and BFGS methods.
Now we consider the fundamental matrix approximation problem below to obtain the convergence rate of the SRI and BFGS updates.

---

2.1 Superlinear convergence for SR1 update
We first describe the SRI update for approximating fixed positive definite matrix A R and leave the proof in Appendix A Let us now justify the efficiency of update Eq. in ensuring convergence G to A. For this, we introduce the following measure of progress:
G - tr(G - A).
(5)
Previous work 19 uses a different measure as follows
(G) _ (A-i, - a = ir [[G - A) A
(6)
which might be improper for analyzing the SRI update. Thus we employ a more concise measure (-). However, we will reuse (-)) in the proof of BFGS update in Subsection 2.2
According to GG), one iteration update leads to
u TG -
G TA(G)
u.
u u - AAu"
Note that we always have G ž AfG A from Lemma
2.2 Moreover, the choice of the updating
direction u directly influences the decrease in the measure TA (.). In the following, we show two efficient ways for selecting u introduced in Algorithm
First, we use the greedy method introduced in [19,, that greedily selects u from the basis vectors to obtain the largest decrease of (G(+)) - T (G): (G( - arg ma(uue(e.......
GG A)"a
" (G Aju
However, we may encounter numerical overflow due divided by 0f (G AA)u is nearly 0. Noting that G ž A, we have v(u (G - A) u) (u u) 2 u TT( A)u 2 0, Vu E R from inequality. Thus we employ safer adjustment:
T
(G Aju
(Greedy SR1) (G)
arg max (c.........))
arg max u T (G A)u. (eI....,o.)
u
Moreover, we only need to obtain the diagonal elements of A (the current Hessian in practice), thus the total complexity (n²) in each iteration which is acceptable and the same as the classical quasi-Newton methods.
Second, from the proof of the greedy method, we discover that the random method by choosing from a spherically symmetric distribution, e.g., (Random SR1) u ~ (0, or u ~ U
(8)
also has similar performance (in expectation) and the same running complexity O(r²) in each iteration.
Rodomanov and Nesterov 11 Theorem 3.5] already showed that G, A if the us for & (O...., n } are linearly independent. Thus, we only consider & S n. Now let us estimate the decrease in the measure (-)-) based on the direction chosen from previous strategies. In the following, the expectation considers all the randomness of the directions uN 's during iterations, and when applied the greedy method, we can view it with no randomness for the same notation.
Theorem 2.3 Under the SRI update in Algorithml 7 we obtain that for the greedy method defined in Eg. or the random method defined in Eq.
0 0s ETE S 11 (1-nkkt1) (1-n))(((((nn+)
(1~1) Ta(Go), 15 n.
E ETA(GE-))
(9)
Hence, TA (or E TTA(GE)) converges to zero superlinearly.
2.2 Linear convergence for BFGS update
We now consider the classical BFGS update in the same scheme and leave the proof in Appendix A Using the measure a A (-), we obtain that
u T ATGAA-CA +1, G. = BFGS(G,,, u,u).
A (G+) (
(10)
Gu
Note that use Hessian-vedd product obtain Au in practice.

---

Algorithm 1 Greedy/Random SR1 update
Algorithm Greedy/Random BFGS update
1: Initialization: Set Go A.
Initialization: Set Go = A, Lo G 1/2 2: for k 2 0 do
2: for & == .2.... do
3: Choose us from
Compute u = L
uR with üy from
1) greedy method: u2 = u (Gx). or
1) greedy method: ūg u LA), 1,),00 or
2) random method: ut Unif(S
random method: un Uni
4: Compute Gk+1 SR1 (G): A, un).
4: Compute G++1 BFGS (k.. A, u
Compute Lk+1 based on Proposition 2.6
5: end for
6: end for
If we directly apply the greedy method or random method from the previous content, we could only obtain the same linear convergence rate [19 Theorem 2.5]. However, if we take advantage of the current G, and choose a scaled direction such that u. L à where L L = G we could simplify the formulation and obtain faster condition-numile cortn-uumbbr--reee linear convergence rate. Specifically, the greedy update after replacing u to L i is as follows:
---TA-LLA
(Greedy BFGS) (A( = arg max
(11)
and the random method is the same as the SR1 update used in Eq.
8
(Random BFGS) ū ~ (0, In) or ú ~ Unif(S
(12)
Now give the linear convergence rate of our modified BFGS update.
Theorem 2.4 Under the BFGS update in Algorithm 2 defined in Eq. (TT) or the random method defined in Eq. 122.
obtain that for the greedy method
0 O S (1 (1-1) n E BO
(1-((11)) 11= oa(Go), 1
(13)
Therefore, (Gk)) (or E (G&)) converges to zero linearly.
Remark 2.5 Note that the complexity in Eq. (TT is (nn)) because we have multiply-add operations with (unknown) A- Hence do not apply this greedy strategy in practice, but view it theoretical result similar to the random strategy. Moreover, the random method is still practical, and show the efficiency of our scaled direction compared the original direction in experiments.
Finally, we can employ an efficient way (with complexity (n²))) for updating Lx. The main idea is employing the rank-one update and the one-row appending update of QR decomposition with the inverse BFGS update. Proposition 2.6 we show how to compute L from Lg with O(n)) flops.
Proposition 2.6 Suppose already have H₁ & G matrix. Now we construct Lx41 with O(n²)) flops.
LE La, where L is upper triangular
Step 1: Using the formulation in Golub and Van Loan 12 Section 12.5.1), we can obtain QR decomposition of
Augul
(x(A)s)
L I
L
ui
ux Aus
u Au
with O(r²), flops
flops because it is rank-one change of Li..
Step 2: We have Li (I,- Augug
Qs from Step 1, with orthogonal matrix Q2 Raxx
= Auu
and an upper triangular matrix RS
Raxn Denoting
Uk Vu Aus
we can write
R QU
T R Rr + UUU (vk
R
U R
u Au
Using the formulation in Golub and Van Loan
[12)
Section 12.5.3] for computing the QR decom-
position after appending a row, we can obtain
v R
R with only O(n²) flops, where
QK+I E 1n+11nn is column orthogonal matrix and R&+1 E <Raxn is an upper triangular matrix. This implies H R Re+1, which satisfies requirements.
5

---

Algorithm 3 Greedy/Random SR SRI/BFSS methods for quadratic minimization
1: Initialization: Choose 2o E IR". Set Go
LIn (or any Go - A).
2: for k do
3: Update 24+1
G V f(xx). Choose one of the following update rules:
4: (i) SRI: Choose us following Algorithm| [ Compute G.+1 SR1 (R. GR. A, uz).
5: (ii) BFGS: Choose uy following Algorithm
2
Compute Gk+1 = BFGS A, un).
6: end for
3 Unconstrained quadratic minimization
Based on the efficiency of the greedy/random SRI and BFGS updates in matrix approximation, we next turn to minimize the quadratic function (with fixed Hessian):
1 Ax bTxx. 2
f(x)
(14)
where A is positive definite matrix, and there exist, μr I. >> O, s.t., μI 3 A I.I,,- We show the detail in Algorithm 3 which is only for theoretical analysis. In practice, we use the inverse update rules (Nocedal and Wright [6 Eq. (6.17) and Eq. (6.25)I) to update G directly:
(In G Ajuu' (In AG-
G =
G. =RI (G, u);
(15)
u (AA AG AAuu
uu A
Auu
uu
G--
G-1
In
= BFGS A,
(16)
Au u
u
Au
u
Au'
To estimate the convergence rate of Scheme
14
we measure the norm of the gradient of f as
(x(x) VV a E
(17)
Note that this measure of optimality is directly related to the functional residual. Indeed, let x A- 'b be the minimizer of Eq. (14.. Then we obtain
1 )))())² '(Ax (Ax b)
f(x) - f(x") (x
x²)² A(x x²) = (Ax ()) b)T A
The following lemma shows how (-(-) varies after one iteration of process in Algorithm 3
Lemma 3.1 (Rodomanov and Nesterov 19
Lemma 3.2) Let k 2 and let nk 2 satisfy A
Ga 3 A. Then we have that (x [
(x I (m ())5(
1/
Thus, to estimate how fast {x())) converges to 0, we need the upper bound of mæs which is already done in Subsections 2.1 and 2.2 Thus, we can guarantee superlinear convergence of Xy(xx; using the greedy/random SRT or BFGS update. The proof of Theorem 3.2 can be found in Appendix A
Theorem 3.2 Under Algorithm
3 we choose SRI update, then we have
Gr
A)
E
0 O
(x(s))
H
we adopt BFGS update, then we have
( (x(x))
<(1 (1- tr [Go A) A ") k
E
Thus, we see both SRI and BFGS methods share superlinear convergence for {Ay (xx2)) In particular, for the SR1 update, our bound recovers the classical result in [16, Theorem 6. showing that the update stops after finite steps because G,, = A and Xy(x,,-1 1) = 0. Moreover, we also give an exact convergence rate during the entire optimization process. And the main decreasing term (1 - for the SR1 I update as well as (1 1 for the BFGS update in the k-th iteration are independent of the condition number x of A, which improves the bound (1 1 in [19 Theorem 3.4].

---

Algorithm 4 Greedy/Random SRI/BFSS methods for strongly self-concordant objective
1: Initialization: Choose 2o E R.. Set Go Lla, Lo Ln/VL.
2: for k 2 0 do
3: Update 0k+1 = 3k G (((xs)
4: Compute rІ. = || 26 Iay, Gx = (1 (1+ MrX) Gb. = =
5: (i) Greedy/Random SR1: Choose us = ((x24)) (G&), or us ~ Unif(Sn-1)
Compute G++1 SR1 (G+: V (=*++)))))....... 4x).
6: (ii) Greedy/Random BFGS: Choose Un = u (n), or üs ~ Unif(S
Compute Gk+1 BFG,(G,, f(((xx11) L ú and Lx+1 based on Proposition 2.6
7: end for
Minimization of general functions
Finally, we consider the optimization of more general machine learning objective with unfixed Hessians: min f())), where / IR - R is twice differentiable function with positive definite Hessians. Our goal extend the results in previous sections, assuming that the methods can start from sufficiently good initial point To. We use the same assumption strongly self-concordant followed by Rodomanov and Nesterov 19].
Definition 4.1 (Strongly self-concordant) A function f Rh - Re is strongly self-concordant if the Hessians of J are close to each other in the sense that there exists a constant M 2 0 s.t.
f0y( - 2 f(x) < M y 20 ((w)), V 2,
Rodomanov and Nesterov have already mentioned several properties and examples of strongly self-concordant function, such as strongly convex function with Lipschitz continuous Hessian. Let us now make one more common assumption about the function f as Rodomanov and Nesterov [19] did, that the function f is y-strroggy convex and L-smooth, i.e., there exist L 2 μ > 0 such that
μI, 3 f(x) 3 LJn,, V aE R
and K. := L/μ. Unlike quadratic minimization, the true Hessian in each step varies. In order to make G2 > V2 f(r() always hold, we adjust G3 before doing quasi-Newtor update. Instructed from [19, we also use the correction stralegy, which enlarges the approximation G properly shown in Line 4 of Algorithm Moreover, Algorithm[4]] is only for theoretical analysis. We need to adopt the inverse update rules (Eqs. (15) and (16)) in practice. Additionally, assume that the constants M and L are available for simplicity.
For the BFGS update, we can analyze how the Hessian approximation measure a changes after one iteration following [19] The proof can be found in Appendix A
(G) ova f (G)
Theorem 4.2 Suppose that in Algorithm 4 BFGS update is used, and that the initial point xo is sufficiently close to the solution:
In 2
(a)) 4mt(n + 1)
(18)
Then for all l 2 0. we have
[ (1-
f²f(zx) 1 Gk. Eox, (Gt) < 2nx
(19)
and
Ay( Xy(x+)
1 n2
E
2nx
1
(20)
As for the SR1 update, the main difficulty compared to 19 that we utilize different measure T (.)) instead of a a-).), resulting in refined proof version below, and we leave the proofs in Appendix A
7

---

Matrix Approximation
Matrix Approximation
Quadratic
10
10
107
Ra5R1
GrBFGSv1
tr1 -1-0
10-
RabF
DrG.. A)
R3BF55M2
10
100
10
10
GrSkivv2
Ra6FoSvvi
10
RaSR1
RaBFOS
Theary
Theery
10-33
10
20
250 500
Epochs, n 100, K 2000
Epochs, n 100, 2000
Epochs, 100, - 2000
(a)
(b)
(c)
Figure/ 1: (a, b) Comparison different direction choosing methods under the SRI or BFGS update for approximating matrix A that μId, J A 3 LI, from G LIn- (a) The variation of TA (G)) during Random SRI (RaSR1) and our Greedy SR1 (GrSRIvE (v2) update with nearly matched upper bound. (b) The variation of o (G&) during our Random BFGS (RaBFGSv2) update and the original random version (RaBFGSv1). (c) Comparison of SRI and BFGS methods for quadratic objective. Here only depict RaSR1 method, while the other SRI-type methods share similar behavior.
Theorem 4.3 For Algorithm with SRI update, suppose that the initial point wy sufficiently close to the solution:
In
MXy(20) S 4x(2nk + 1)
(21)
Then for all k 2 0, we have
(1
(1-
f(x)) 3 Gk, Eo (Gk) S 2nn?
(22)
n2
and
E >5(arx+1) (a(wx))
S 2nk²
(1-
1 1
(23)
Corollary 4.4 Combining with 119 Theorem 4.7] (shown in Appendix B. if xo satisfies 3 4x we could obtain 1) for the greedy BFGS or greedy SRI method,
(1)( I
Ag( 1
1 (1-1) 17
11/21)/2
(1 (b))
1 kp
-Ay(a)); for all k: 2 0.
2x
where ko =0 1 for any 8 (0,1). 1),
= (max(n, n3} In(nx)),, for the random BFGS or random SRI method, with probability
{g( & (1- 1
11/-1)/2
A(K-
1 (1-
1 2x
Ax))))), for all k 2 0,
+1
2
where kn = O (maxff, xi) In(nx/o)).
Therefore, both greedy and random methods have non-asymptotic superlinear convergence rates. Additionally, our superlinear rates are condition-number-ffi number-fice compared to the rates in 19
5 Numerical experiments
In this section, verify our theorems through numerical results for quasi-Newton methods. Rodomanov and Nesterov [19 have already compared their proposed greedy quasi-Newton method with the classical quasi-Newton methods. They showed that GrDFP, GrBFGS, GrSRI (greedy
DFP, BFGS, SRI methods) using directions based on (G) = arg max ........ Au quite competitive convergence with the standard versions. They also presented the results for the randomized versions RaDFP, RaBFGS, RaSR1, which choose directions directly from standard Fuclidean sphere. They discovered that the randomized methods are slightly slower than the greedy ones. However, the difference is not really significant.
u Gu have
8

---

Dara sut ai (1. 122. /1- 11220, y 2 3.00, A 276581
Data set abia (1- 122. /1- 11220, A. 2763731
10
BudRa
RudEs
Budt 65+4
20
10
10
206
468
200
000
1200
3030
2400
250
500
750
1603
1253
15.00
1750
2000
(b) 0.1
Figure 2: Comparison of SRI and BFGS update for éz-regularized logistic regression applied with 'a6a" data from the LIBSVM collection of real-world data sets. We list the name of dataset, the dimension n and the condition number k under the corresponding y in the title of each figure. The lines of GrSRIv1 and GrSRIv2 are overlapped in some figures.
The difference between our algorithms and their methods mainly comes from the greedy strategy for SR1 and the random strategy for B Hence, we mainly focus exhibiting our validity in these schemes. We refer to GrSRI v2 as our revised method and GrSRIvl as the previous method. Similarly, denote RaBFGSv2 that uses scaled directions (L u) and RaBFGSv that directly uses random directions u correspondingly. We use u Unif(8"-1) in all experiments for brevity.
Matrix approximation. When using Algorithms T and for approximating matrix A > 0, we show the measure as proved by Theorems 2.3 and 2.4 in Figures [eguresTaaaaa and [b] As Figure depecicss, our greedy and random SR1 updates (GrSR 1v2 and RaSR1 1) share superlinear convergence rate under measure TA (+), while our theoretical bound matches them well. Moreover, Figure Tb describes the behavior of the random BFGS update. Note that the greedy BFGS update we proposed does not satisfy the O(n²) complexity, thus we leave it out. Our theory totally matches the linear convergence of measure a (-) (-) in our modified random BFGS update (RaBFGSv2). However, directly choosing direction without scaling (RaBFGSv1) fails to give such bounds. Moreover, we also discover the same findings under different condition numbers in Appendix C. Clearly, our methods provide effective ways of approaching a positive definite Hessian matrix.
Quadratic minimization. We also consider unconstrained quadratic minimization with the same positive definite matrix A and a randomly selected vector b R.". Running Algorithm with SR1 and BFGS updates, we obtain the superlinear convergence of x-(-) shown in Figure Ic Not surprisingly, our RaBFGSv2 runs faster than RaBFGSv1, while we also have the theoretical guarantee. At the same time, SRI- SRI-type methods converge to zero after + 1 steps because G, A. Here, we only depict the RaSRI update, while the other SR stype methods share similar behavior. Although theoretical bound can not directly match the experiments due to the related initial terms TA (G.) and a A ( (o),, the decay terms: (1 k/n) vs. (1 1/n)* already show the superiority of the SR1 method over the BFGS method in the quadratic minimization problem.
Regularized logistic regression. Next, we consider & fz-regularized logistic regression:
N
? f(w)= = Σ (1+e vew + -- 1w0112 w WER". 2
where X = -..... .. N. R training samples with the corresponding labels y UN {+1, -1), and 0 is the regularization coefficient. We follow the same experimental design but take data from the LIBSVM collection of real-world data sets for binary classification problems [6]. And we do not apply the correction strategy (G:- (1+ Mr Gx) in Algorithm 4h recommended
by [19]. Other details are shown in Appendix C In order to simulate the local convergence, we use
the same initialization after running several standard Newton's 's steps to make measure [(r)(
small (around 10
10').
'There no difference in the random SRI method compared to Rodomanov and Nesterov 19 which directly selects random directions. And our greedy BFGS method is not efficient (O(n²) 3 in each iteration) as we mentioned in Remark 2.5 Thus we leave it

---

250.m
18m
(a) 7
(b) 0.1
(c) 0.01
Figure 3: Comparison of SRI and BFGS update for Regularized Log-Sum-Exp. The dimension n, number of linear functions, the regularization coefficient y and condition number displayed in the title of each graph. The lines of GrSRIvI and GrSRIv2 are overlapped in each figure.
We show the results in Figure 2 As we can see, the general picture is the same for the previous objective. In particular, SRI 1-1 -type methods are faster than BFGS-type methods, and the greedy algorithms also converge more rapidly than the random algorithms. The only difference that our RaBFGSv2 may have slower convergence behavior than RaBFGSvl under small in Figure 2a We consider our scaled direction more suitable for constant Hessian matrix the quadratic objective has. Thus we still have better convergence rate in the last few iterations when Hessians are nearly unchanged in Figure 2a However, the Hessian varies drastically in the initial period. Thus there is less benefit under a more accurate Hessian approximation. When applied to the ill-conditioning setting with a large a in Figure 2b] we find our RaBFGSv2 could be faster than GrBFGSv and RaBFGSv1. This implies that proposed method has less dependence the condition number
Regularized Log-Sum-Exp. Followed by Rodomanov and Nesterov [9]. we also present prelimi- nary computational results for greedy and random quasi-Newton methods, applied to the following test function with C [cI...., cm] E. I bi...., bm E R, and ? >
f(x) = In
bj
+
C 2
||0 2 x BRER R..
j=1
We also use the same synthetic data in [19 Section 5.1] and leave the detail in Appendix As Figure 3 depicts, the BFGS-type methods are slower than the SRI-type methods. GrBFGSv and RaBFGSv1 are faster than RaBFGSv2 in a small condition number case, but they become slower than RaBFGSv2 when the condition number becomes huge. Therefore, we think our RaBFGSv2 which uses scaled direction indeed has less dependence on the condition number as our theory shows.
Overall, our proposed methods do not lose the superlinear convergence rate in the large condition number schemes, while also present the theoretical guarantee for these algorithms.
6 Conclusion
In this work, we have studied the behavior of two famous quasi-Newton methods: the SR1 and the BFGS methods. We have presented different greedy methods contrast Rodomanov and Nesterov [19], and the random version of these methods. In particular, we have provided the faster Hessian approximation behavior and the condition-numin -wm--n--mmbbeeeeeeeeeeeeeeeeeeee (local) superlinear convergence rates applied to quadratic strongly self-concordant objectives. Moreover, the experiments corroborate our analysis well. Note that our current results do not give the superlinear convergence rate of the standard quasi-Newton methods with only gradient information. However, we hope that the theoretical analysis and the related work would useful for understanding the quasi-Newton methods in more specific view.
10

---

Acknowledgments and Disclosure of Funding
Lin and Zhang have been supported by the National Key Research and Development Project of China (No. 2018AAA0101004) by the National Natural Science Foundation of China (No. 1 11771002), and Beijing Natural Science Foundation (Z190001). Ye has been supported by the National Natural Science Foundation of China (No. 12101491), and Shenzhen Research Institute of Big Data (SRIBD) (No. J00120190004).
References
[1] Charles G Broyden. Quasi-newton methods and their application to function minimisation. Mathematics of Computation, 21 21(99):368-38) 1967.
[2] Charles G Broyden. The convergence of class of double-rank minimization algorithms: 2. the new algorithm. IMA journal of applied mathematics, 63):222-231, 1970.
[3] Charles George Broyden. The convergence of class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 6(1):76-90, 1970.
[4] Charles George Broyden, John E Dennis and Jorge Moré. On the local and superlinear convergence of quasi- quasi-newton methods. IMA Journal of Applied Mathematics, 12(3):223-245, 1973.
[5] Richard H Byrd, Jorge Nocedal, and Ya-Xiang Yuan. Global convergence of cass of quasi- newton methods on convex problems. SIAM Journal on Numerical Analysis, 171 1987.
[6] Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1-27, 2011.
[7] William C Davidon. Variable metric method for minimization. SIAM Journal on Optimization, 1(1):1117, 1991.
[8] John E Dennis and Jorge Moré. A characterization of superlinear convergence and its application to quasi-newton newton methods. Mathematics of computation, 28(126) 1974.
[9] Roger Fletcher. A new approach to variable metric algorithms. The computer journal, 13(3); 317-322, 1970.
[10] Roger Fletcher and Michael JD Powell. A rapidly convergent descent method for minimization. The computer journal, 6(2):163-166) 1963.
[11] Donald Goldfarb. family of variable-metric methods derived by variational means. Mathe- matics of computation, 24(109):23-26, 1970.
[12] Gene H Golub and Charles F Van Loan. Matrix computations, 1996.
[13] Andreas Griewank and Ph L Toint. Local convergence analysis for partitioned quasi-newton updates. Numerische Mathematik, 39(3):429 1982.
[14] Qiujiang Jin and Aryan Mokhtari. Non superlinear convergence of standard quasi- newton methods. arXiv preprint arXiv:2003. 2020.
[15] Dmitry Kovalev, Robert M Gower, Peter Richtárik, and Alexander Rogozin. Fast linear convergence of randomized bfgs. arXiv preprint arXiv:2002.1 11337, 2020.
[16] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science Business Media, 2006.
[17] MJD Powell. On the convergence the variable metric algorithm. IMA Journal of Applied Mathematics, 7(1):21-36, 1971.

---

[18] Anton Rodomanov and Yurii Nesterov. New results on superlinear convergence of classical quasi-newton methods. Journal of Optimization Theory and Applications. 188(3)744-766,.1 Jan 2021. ISSN 1573-2878. doi: 10.10077710955--00000085- URI. http:/ttp:://.. doi. org/10 1007/s10957-000-01110 01805-8
[19] Anton Rodomanov and Yurii Nesterov. Greedy newton methods with explicit superlinear convergence. SIAM Journal on Optimization, 31(1):785-88) 811, 2021.
[20] Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi- newton methods. Mathematical Programming, pages 1-32, 2021.
[21] David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathemat- ics of computation, 24(111):647-656, 1970.
[22] Andrzej Stachurski. Superlinear convergence of broyden's bounded f-class of methods. Mathe- matical Programming, 20(1):19-2212, 1981.
[23] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[24] Hiroshi Yabe and Naokazu Yamaki. Local and superlinear convergence of structured quasi- newton methods for nonlinear optimization. Journal of the Operations Research Society of Japan, 39(4):541-557 1996.
12


Reviews:
[{"review_id": "xNgLt3auNV", "reviewer": "Reviewer_8zir", "summary": "This paper introduces new non-asymptotic analysis for quasi-Newton methods, extending recent results on DFP to BFGS and SR1. This is relevant since these two methods produce better Hessian approximations so can converge faster. The authors show that the same rates of convergence can be achieved using either greedy or random updates, which is relevant because greedy updates do not always come for free.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper introduces interesting new analysis which advances the understanding of quasi-Newton methods. Its outline is relatively straightforward. The theoretical results are written in a way that the reader can see its important parts, rather than being overcome with complex constants (which sadly happens quite often in the related literature). The theoretical results are convincing.\n\nOn the other hands, a few concerns appear.\nFirst, the clarity of the paper could be improved upon. There are three steps: matrix approximation, then minimisation of a very simple quadratic objective (with fixed Hessian), and finally optimisation of a more. relevant ML objective. Making this gradation more explicit would help the non-expert reader figure out what exactly is being optimised at any given moment, which can prove a bit tricky for now.\n\nSecond, a lot of energy and space is devoted to developing theory on very simple problems on which the algorithms will not be applied (if there's a closed form solution, why bother optimising?). It appears at the very end of the paper that on relevant tasks, the new method does not perform better than previous work, which makes the whole endeavour somewhat less relevant.\n\nAll told, while this paper is not groundbreaking from a practical standpoint it presents convincing new theoretical analysis and advances our understanding of relevant methods.\n\n\nDetails:\n- in the notations using x as the argument and index for the norm definition is confusing.\n- In theorem 2.3, the inequality does not seem to imply super but rather sub-linear convergence, unless the G_0 is replaced by G_{k-1}?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I see no additional societal impact to the existing literature on the topic", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "wtOj9LtP1SF", "reviewer": "Reviewer_87Me", "summary": "This  paper proposes a tighter local analysis of two popular variants of quasi-Newton methods: BFGS and SR1 with greedy or random choice of directions. It is heavily based on a recent work of Rodomanov & Nesterov, but the analysis is simpler and, most importantly, the guarantees are strictly better (the final bounds do not contain the conditional number $\\kappa$).\n\nI think it is really a good paper.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "  Similarly to Rodomanov & Nesterov, the authors first study quadratic case (where the Hessian doesn't change from iteration to iteration) and then consider a general case with strongly self-concordant functions (where the Hessian changes in a controlled way). For SR1 update they use a slightly different (and simpler) measure function, which was key in establishing tighter bounds.\n\n\n\nI checked mathematics only partially, mostly related to SR1 update. Although I still need some clarification on that, the major derivations seem correct.\n\n\n__Proof of Theorem 4.3__:\n\n1. line 451: why $M\\lambda_k < 2$? We need it in order to apply Lemma B.2\n2. Eq. (44): why do we write the last term in all inequalities as $\\eta_k + 2Mr_k$  and not $\\eta_k + 2M\\lambda_k$ that we obtained in (41)? We need to use the latter anyway in the end of (44).\n3. line 465: I find it a bit too quick. Also, we didn't use just (43), some derivations from (44) were also used.\n\n__Proof of Corollary 4.4__:\n1. Eq. after line 470: from that inequality we can only obtain the lower bound for $k_1$. Similarly for $k_2$ below.\n\n\n\n__Minor comments__:\n1. line 40: I think this work is not about closing the gap in the experiments, it is a theoretical work.\n2. Algorithm 1, line 2: it is better to write \"for $k = 0,\\dots, n-1$\"\n3. I would add the updates for InvSR1 and InvBFGS to the main text.\n4. line 171: there is no training process, it is just pure optimization.\n5. Section 4: $\\kappa$ has to be redefined here, before it was defined only for quadratics.\n6. line 244: Is there any particular reason why we use the Frobenius norm for $X$ and not the spectral one (the smaller one)?\n7. line 377: it is true, but for me it wasn't obvious.\n\n\n\n\nThe English of the paper might be improved, I list some errors below (maybe I didn't understand something).\n\n1. Too many sentences start from \"And\", often there is no need for it.\n2. line 44: \"both the methods\"\n3. line 86: I am not sure what the authors want to say by \"benign monotonicity\"\n4. line 103: \"we would reuse\"\n5. line 111: \"from the\"\n6. line 208: we do not verify theorems in optimization by numerical experiments.\n7. line 232-233: \"all obtain\", \"Theorem shows in Figure\".\n8. line 385 and in other places: not sure what \"expectation view\" means.\n9. line 388: \"are spherical symmetry\"\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "0", "review_text": "", "extra_scores": {"ethical_concerns": "0", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "0"}, "extra_text": {}}, {"review_id": "RCzUD6LoR4A", "reviewer": "Reviewer_h3n6", "summary": "In this paper, the authors have applied the methods of greedy/random choice of directions that enable better Hessian approximation (proposed by Rodomanov and Nesterov in [18]) to the quasi-Newton optimization scheme. In this way, the authors have achieved a condition-number free super-linear convergence rate. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is clearly written and the mathematics is clear. The only concern is that the improvment over Rodomanov and Nesterov in [18] might be incremental, so it would be a good idea if the authors can accompany the paper with a section indicating explicitly the improvements over Rodomanov and Nesterov in [18]. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "IInBBVffxZ1", "reviewer": "Reviewer_pExt", "summary": "This work considers the topic of the convergence of quasi-Newton and it builds on top of a series of recent results by Rodomanov and Nesterov. The main two contributions of this paper are: 1) improve the bounds for greedy quasi-Newton methods using a new potential function; 2) to propose a new modification of greedy strategy to obtain better results. The authors consider two settings: unconstrained quadratics and general strongly self-concordant functions (the same settings were considered in prior work). All results are local but this is probably inevitable as quasi-Newton methods approximate Newton's method, which itself is a local method.\n\nI find the results to be very solid and promising. The topic of quasi-Newton methods might get a second breath due to the recent results and I would be glad to see this paper accepted. It does have a small number of typos but I think most of them can be fixed if the authors proofread their work (I hope the authors will do at least a partial pass during the discussion stage). ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Strength\n1. This work has a very interesting theory and I particularly appreciate that the authors managed to use a somewhat simpler potential than the one employed by Rodomanov and Nesterov. \n2. I also enjoyed the style of writing and the presentation of the obtained results.\n3. I find the topic of quasi-Newton to be quite promising right now, and I hope that this work will inspire further research in this direction.\n4. Quasi-Newton methods are widely used in practice but there are still many limitations (such as stochastic extensions of quasi-Newton methods), which helpfully can be addressed once we have a better understanding of their basic variants.\n\n\n## Weaknesses\n1. The paper has a number of typos and the use of articles is not great. I would also appreciate if the authors made some of the sentences shorter as it's hard to read them (for instance, the last sentence in the first paragraph).\n2. The experiments are performed on logistic regression, which is often not a good example because it's well-conditioned. Please do similar experiments on the log-sum-exp objective, whose conditioning can be controlled using the smoothing parameter (by smoothing I mean approximation of the maximum function).\n\n## Questions\nIn the proof of Corollary 4.4 (the part about SR1), the authors combine their guarantees with the guarantees of Rodomanov and Nesterov. However, when greedy strategies are used, I think this is not correct because Rodomanov and Nesterov use a different strategy for selecting u_k. Therefore, I think Corollary 4.4 is not precise in relation to SR1.\n\n## Suggestions\n1. As the results from Appendix C are not too long and they allow for a more efficient implementation that needs only O(n^2), I think they should be moved to the main part or at least explained briefly. I think this is particularly important because BFGS is sometimes more numerically stable than SR1.\n2. Theorems 4.2 and 4.3 give slightly different results that suggest a better bound for BFGS than for SR1, for instance, in terms of the initial distance to the solution. I suggest adding this to Table 1.\n3. Please update the numerical discussion to include log-sum-exp experiments.\n\n## Typos\n\"quasi-Newton methods, that\": no comma here\n\"Newton methods to certain approximation\": \"Newton methods with a certain approximation\"\n\"worse long history behavior\": \"worse long-history behavior\"\n\"Second, we extent\": \"Second, we extend\"\n\"our analysis to practical scheme\": \"our analysis to a practical scheme\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "0gdrHF1VpnJ", "reviewer": "Reviewer_y3vR", "summary": "This paper presents two modified greedy quasi-Newton updates, originally given by Rodomanov and Nesterov [18]. They first consider using these updates to approximate a positive definite Hessian. In particular, for the greedy SR1 update, they introduce a different progress measure, which is maximized over the coordinate bases to yield the vector used in the update. This new measure allows them to obtain a superlinear convergence rate for the Hessian approxiamtion error, where the rate is independent of the condition number $\\kappa$. For the greedy BFGS update, they use the same progress measure as in Rodomanov and Nesterov [18], but preconditions the corresponding greedily selected vector with the current Hessian approximation. This yields a linear convergence rate for the Hessian approximation, although their greedy selection for BFGS is rather impractical. In addition to the modified greedy selection strategies, their analyses and rates also apply to a random selection from a spherically symmetric distribution.\n\nSimilar to Rodomanov and Nesterov [18], they then apply these results to analyzing the convergence rate of minimizing strongly-convex quadratics, as well as strongly self-concordant objectives. They obtain similar explicit local rates as the previous work, but without the condition number (although the initial, non-local phase still converges linearly with a dependence on $\\kappa$).\n\nExperiments on evaluating the newly introduced Hessian approximations show that their methods are quite effective. On a strongly-convex quadratic minimization problem the conclusions are similar. For minimizing a strongly-convex logistic regression problem, the randomized BFGS (with the preconditioned vector) does not perform better than the version from Rodomanov and Nesterov [18], which does not contain the preconditioning. This is true for the two logistic regression problems with different scales of condition numbers. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Strengths**\nThis work is strong in the sense that they are able to significantly improve existing rates with very simple modifications to an existing algorithm, especially when the improved (local) rates do not depend on the condition number. These results are very interesting and further establish the potential of greedy/random quasi-Newton methods. The paper is easy to read as it mainly follows the same structure as Rodomanov and Nesterov [18], with key differences emphasized appropriately.\n\n**Weaknesses**\nOne of the drawbacks in the proposed greedy updates is that we now have two different greedy selection rules for SR1 and BFGS, respectively. This is not a main issue in terms of implementation ease, as the two Hessian approximation updates themselves are already different. However, this distinction leads to separate analyses for SR1 and BFGS, which is not as satisfying as the analyses provided by Rodomanov and Nesterov [18], where the three main quasi-Newton updates (SR1, BFGS, DFP) are all covered. Another drawback of this distinction is that, the proposed greedy BFGS is rather impractical, as the authors mentioned that the cost to obtain the vector is $O(n^3)$.  Furthermore, this work does not seem to cover the DFP update, which leaves me wondering whether the new progress measure introduced for SR1 or the preconditioning of the greedy vector in the BFGS case are mainly ad hoc, and whether there is a way to obtain condition number free rates for the general Broyden family.\n\n=== Update ===\nI no longer view this as a weakness. Unified analyses would be nice if they also provide tight rates, but it seems to be highly non-trivial for the Broyden family. \n\nIn terms of the related work, the authors should discuss the work of [Jin and Mokhtari, 2020], in which non-asymptotic superlinear convergence rate of the original Broyden family are also proved. In their results, the rates are independent of the problem dimension $n$. In addition, they do not use the greedy/random basis selection, nor do they require access to the diagonal of the true Hessian. \n\nFor the first set of experiments (Figure 1), it would be helpful to see a comparison between problems with varying condition numbers, and compare whether the local convergence of the proposed updates are indeed condition-number independent in practice. \n\n**Reference mentioned**\n[Jin and Mokhtari, 2020] *Non-asymptotic superlinear convergence of standard quasi-Newton methods*\n\n\n**Minor concerns**\n- B.3 Proof of Theorem 3.2\n\t- This proof invokes Lemma 3.1 (Lemma 3.2 from Rodomanov and Nesterov [18]), while assuming it holds with an expectation. I believe it indeed holds with an application of the operator convexity property of the matrix inverse, but it would help clarify if the authors can include the proof of this lemma under expectation.\n- L102: The authors claimed that the progress measure $\\sigma_\\mathbf{A}(G)=\\text{tr}(A^{-1}(G-A))$ might be improper for analyzing the SR1 update. Could you please elaborate why this might be true? Is it because SR1 is a rather good approximation of the exact Hessian, and thus preconditioning the progress measure with $A^{-1}$ could de-emphasize the proximity between $G$ and $A$? And hence the modification to $\\tau_\\mathbf{A}(G)=\\text{tr}(G-A)$ ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommended acceptance, and this represents as a non-trivial improvement over the existing results. Please make the changes discussed in the reviews/responses, such as the addition of the log-sum-exp experiment.
Decision: Accept (Poster)