Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence
Year: 2021

Abstract:
In this paper, we follow Rodomanov and Nesterov [19]’s work to study quasiNewton 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 conditionnumber-free superlinear convergence rate. Second, based on the random quasiNewton 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.

heading: 1 Introduction
text: 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 on some special formulas from the previous variation. There exist various quasiNewton algorithms with different Hessian approximations. The three most popular versions are the Davidon-Fletcher-Powell (DFP) method [7, 10], the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method [2, 3, 9, 11, 21], and the Symmetric Rank 1 (SR1) method [1, 7], all of which belong to the Broyden family [1] of quasi-Newton algorithms. The most attractive property of quasi-Newton methods is their superlinear convergence, which can trace back to the 1970s [4, 8, 17]. 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 rate correspondingly. Their proofs are 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.
∗Equal Contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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 to 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 lnκ, though having similar worse long-history behavior. Jin and Mokhtari [14] provided a non-asymptotic 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) random update that randomly selects the updating direction from any spherically symmetric distribution. We show that both methods share a faster condition-number-free convergence. Particularly, we obtain the superlinear convergence rate O ( 1− kn ) for SR1 update, and the linear convergence rate
O((1− 1n ) k) for BFGS update, where k is the current iteration, and n is the dimension of parameters. Both findings improve the original convergence rate O((1− 1nκ ) k) [19].
• Second, we extend our analysis to a practical scheme. We show (local) superlinear convergence under the SR1 update and BFGS update, when applied to unconstrained quadratic objective or strongly self-concordant functions. We list our results in Table 1 with the same formulation of [19]. Note that in general, the convergence goes through two periods. The first period lasts for k0 iterations, and only has a linear convergence rate O((1− 12κ )
k0). The second period has a superlinear convergence rate O((1− 1n )
k(k−1)/2). Our revised bound takes fewer first-period iterations k0 as well as a faster (condition-number-free) superlinear convergence rate in the second period compared to [19].
Notation. We denote vectors by lowercase bold letters (e.g., u,x), and matrices by capital bold letters (e.g., W = [wij ]). We use e1, . . . , en for the n-dimensional coordinate directions. Let λ1(A) ≥ · · · ≥ λn(A) be the eigenvalues of a real symmetric matrix A ∈ Rn×n. Moreover, ‖ · ‖ denotes the `2-norm (standard Euclidean norm). For a given positive definite matrix A (i.e., A 0), we induce the following pair of conjugate Euclidean norms: ‖x‖A , √ x>Ax, ‖x‖∗A ,√
x>A−1x. When A = ∇2f(x) 0, we prefer to use notation ‖ · ‖x and ‖ · ‖∗x, provided that there is no ambiguity with the reference function f . We recall the rate of convergence used in this paper.
Definition 1.1 (Linear/Superlinear convergence) Suppose a sequence {xn} converges to 0 with
lim n→∞ |xn+1| |xn| = q ∈ [0, 1).
Now suppose another sequence {yn} converges to y∗ and satisfies that |yn − y∗| ≤ |xn|,∀n ≥ 0. We say {yn} converges superlinearly if q = 0, linearly if q ∈ (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 (Subsection
2.2). In Section 3, we analyze previous methods applied to the problem of minimizing a quadratic function. In Section 4, we show that similar results also hold in a more general setting of minimizing the strongly self-concordant function. We give some empirical results in Section 5. Finally, in Section 6, we present our conclusion.

heading: 2 Quasi-Newton updates
text: Before starting our theoretical results, we briefly review a class of quasi-Newton updating rules for approximating a positive definite matrix A ∈ Rn×n. 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 a scalar τ ∈ R.
Definition 2.1 Let A G (that is, G−A is positive semi-definite). For any u ∈ Rn, if Gu = Au, define Broydτ (G,A,u) , G. Otherwise, we define
Broydτ (G,A,u) , τ
[ G− Auu >G + Guu>A
u>Au +
( u>Gu
u>Au + 1
) Auu>A
u>Au ] + (1− τ) [ G− (G−A)uu
>(G−A) u>(G−A)u
] .
(1)
For several choices of τ , we can recover several well-known quasi-Newton methods.
For τ = 0, Eq. (1) corresponds to the well-known SR1 update:
SR1(G,A,u) , G− (G−A)uu >(G−A)
u>(G−A)u . (2)
For τBFGS , u >Au u>Gu ∈ [0, 1], we recover the famous BFGS update:
BFGS(G,A,u) , G− Guu >G
u>Gu +
Auu>A
u>Au . (3)
For τ = 1, it corresponds to the well-known DFP update:
DFP(G,A,u) , G− Auu >G + Guu>A
u>Au +
( u>Gu
u>Au + 1
) Auu>A
u>Au . (4)
Additionally, the Broyden family has matrix monotonicity below, showing the relationship among these quasi-Newton methods.
Lemma 2.2 (Rodomanov and Nesterov [19] Lemmas 2.1 and 2.2) If A G ηA for some η ≥ 1, then we have for any u ∈ Rn, and τ1, τ2 ∈ R with τ1 ≤ τ2 that
Broydτ1(G,A,u) Broydτ2(G,A,u).
And for any τ ∈ [0, 1], we have A Broydτ (G,A,u) ηA.
Hence, if A G ηA for some η ≥ 1, it follows from Lemma 2.2 that
A SR1(G,A,u) BFGS(G,A,u) DFP(G,A,u) ηA.
Intuitively, the approximation produced by SR1 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 (τ ∈ [0, 1]) into the slowest DFP update (τ = 1). Moreover, SR1 and BFGS methods also have faster numerical performance in practice. Therefore, we consider there might have faster superlinear convergence rates of SR1 and BFGS methods.
Now we consider the fundamental matrix approximation problem below to obtain the convergence rate of the SR1 and BFGS updates.

heading: 2.1 Superlinear convergence for SR1 update
text: We first describe the SR1 update for approximating a fixed positive definite matrix A ∈ Rn×n and leave the proof in Appendix A. Let us now justify the efficiency of update Eq. (2) in ensuring convergence G to A. For this, we introduce the following measure of progress:
τA(G) , tr(G−A). (5) Previous work [19] uses a different measure as follows
σA(G) , 〈A−1,G〉 − n = tr [ (G−A)A−1 ] , (6)
which might be improper for analyzing the SR1 update. Thus we employ a more concise measure τA(·). However, we will reuse σA(·) in the proof of BFGS update in Subsection 2.2. According to τA(G), one iteration update leads to
τA(G+) (5) = τA(G)− u>(G−A)2u u>(G−A)u , G+ = SR1(G,A,u).
Note that we always have G+ A if G A from Lemma 2.2. Moreover, the choice of the updating direction u directly influences the decrease in the measure τA(·). In the following, we show two efficient ways for selecting u introduced in Algorithm 1.
First, we use the greedy method introduced in [19], that greedily selects u from the basis vectors to obtain the largest decrease of τA(G+) − τA(G): ūA(G) , arg maxu∈{e1,...,en} u>(G−A)2u u>(G−A)u . However, we may encounter numerical overflow due to divided by 0 if u>(G −A)u is nearly 0. Noting that G A, we have √ (u>(G−A)2u) (u>u) ≥ u>(G −A)u ≥ 0, ∀u ∈ Rn from Cauchy–Schwarz inequality. Thus we employ a safer adjustment:
(Greedy SR1) ūA(G) , arg max u∈{e1,...,en} u>(G−A)u u>u = arg max u∈{e1,...,en} u>(G−A)u. (7)
Moreover, we only need to obtain the diagonal elements of A (the current Hessian in practice), thus the total complexity is O(n2) in each iteration2, 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 u from a spherically symmetric distribution, e.g.,
(Random SR1) u ∼ N (0, In) or u ∼ Unif(Sn−1), (8) also has similar performance (in expectation) and the same running complexity O(n2) in each iteration.
Rodomanov and Nesterov [19, Theorem 3.5] already showed that Gn = A if the uk for k ∈ {0, . . . , n − 1} are linearly independent. Thus, we only consider k ≤ n. Now let us estimate the decrease in the measure τA(·) based on the direction u chosen from previous strategies. In the following, the expectation considers all the randomness of the directions uk’s during iterations, and when applied to the greedy method, we can view it with no randomness for the same notation.
Theorem 2.3 Under the SR1 update in Algorithm 1, we obtain that for the greedy method defined in Eq. (7) or the random method defined in Eq. (8),
0 ≤ E τA(Gk) ≤ (
1− 1 n− k + 1
) E τA(Gk−1) ≤ ( 1− k
n
) τA(G0), 1 ≤ k ≤ n. (9)
Hence, τA(Gk) (or E τA(Gk)) converges to zero superlinearly.

heading: 2.2 Linear convergence for BFGS update
text: We now consider the classical BFGS update in the same scheme and leave the proof in Appendix A. Using the measure σA(·), we obtain that
σA(G+) = σA(G)− u>GA−1Gu
u>Gu + 1, G+ = BFGS(G,A,u). (10)
2Note that we can use Hessian-vector product to obtain Au in practice.
Algorithm 1 Greedy/Random SR1 update 1: Initialization: Set G0 A. 2: for k = 0, . . . , n− 1 do 3: Choose uk from
1) greedy method: uk = ūA(Gk), or 2) random method: uk ∼ Unif(Sn−1).
4: Compute Gk+1 = SR1(Gk,A,uk).
5: end for
Algorithm 2 Greedy/Random BFGS update 1: Initialization: Set G0 A, L0 = G−1/20 . 2: for k ≥ 0 do 3: Compute uk = L>k ũk with ũk from
1) greedy method: ũk = ũA(Lk), or 2) random method: ũk ∼ Unif(Sn−1).
4: Compute Gk+1 = BFGS(Gk,A,uk). 5: Compute Lk+1 based on Proposition 2.6. 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 in [19, Theorem 2.5]. However, if we take advantage of the current G, and choose a scaled direction such that u = L>ũ where L>L = G−1, we could simplify the formulation and obtain a faster condition-number-free linear convergence rate. Specifically, the greedy update after replacing u to L>ũ is as follows:
(Greedy BFGS) ũA(L) = arg max ũ∈{e1,...,en}
ũ>L−>A−1L−1ũ
ũ>ũ , (11)
and the random method is the same as the SR1 update used in Eq. (8). (Random BFGS) ũ ∼ N (0, In) or ũ ∼ Unif(Sn−1), (12)
Now we give the linear convergence rate of our modified BFGS update.
Theorem 2.4 Under the BFGS update in Algorithm 2, we can obtain that for the greedy method defined in Eq. (11) or the random method defined in Eq. (12),
0 ≤ EσA(Gk) ≤ (
1− 1 n
) E σA(Gk−1) ≤ ( 1− 1
n
)k σA(G0), 1 ≤ k. (13)
Therefore, σA(Gk) (or EσA(Gk)) converges to zero linearly.
Remark 2.5 Note that the complexity in Eq. (11) is O(n3) because we have multiply-add operations with (unknown) A−1. Hence we do not apply this greedy strategy in practice, but view it as a theoretical result similar to the random strategy. Moreover, the random method is still practical, and we show the efficiency of our scaled direction compared to the original direction in experiments.
Finally, we can employ an efficient way (with complexity O(n2)) for updating Lk. The main idea is employing the rank-one update and the one-row appending update of QR decomposition with the inverse BFGS update. In Proposition 2.6, we show how to compute Lk+1 from Lk with O(n2) flops.
Proposition 2.6 Suppose we already have Hk , G−1k = L > k Lk, where Lk is an upper triangular matrix. Now we construct Lk+1 with O(n2) flops.
Step 1: Using the formulation in Golub and Van Loan [12, Section 12.5.1], we can obtain QR decomposition of
Lk ( Ik − Auku > k
u>kAuk
) = Lk − Lk(Auk)
u>kAuk u>k
with O(n2) flops because it is a rank-one change of Lk.
Step 2: We have Lk ( In − Auku > k
u>kAuk
) = QkRk from Step 1, with an orthogonal matrix Qk ∈ Rn×n
and an upper triangular matrix Rk ∈ Rn×n. Denoting vk = uk√ u>k Auk , we can write
Hk+1 (16) = R>kQ > kQkRk +
uku > k
u>kAuk = R>kRk + vkv > k =
( vk R > k )(v>k Rk ) .
Using the formulation in Golub and Van Loan [12, Section 12.5.3] for computing the QR decomposition after appending a row, we can obtain ( v>k Rk ) = Qk+1Rk+1 with only O(n2) flops, where Qk+1 ∈ R(n+1)×n is a column orthogonal matrix and Rk+1 ∈ Rn×n is an upper triangular matrix. This implies Hk+1 = R>k+1Rk+1, which satisfies our requirements.
Algorithm 3 Greedy/Random SR1/BFGS methods for quadratic minimization 1: Initialization: Choose x0 ∈ Rn. Set G0 = LIn (or any G0 A). 2: for k ≥ 0 do 3: Update xk+1 = xk −G−1k ∇f(xk). Choose one of the following update rules: 4: (i) SR1: Choose uk following Algorithm 1. Compute Gk+1 = SR1(Gk,A,uk). 5: (ii) BFGS: Choose uk following Algorithm 2. Compute Gk+1 = BFGS(Gk,A,uk). 6: end for

heading: 3 Unconstrained quadratic minimization
text: Based on the efficiency of the greedy/random SR1 and BFGS updates in matrix approximation, we next turn to minimize the quadratic function (with a fixed Hessian):
f(x) = 1
2 x>Ax− b>x, (14)
where A is a positive definite matrix, and there exist µ,L > 0, s.t., µIn A LIn. We show the detail in Algorithm 3, which is only for theoretical analysis. In practice, we use the inverse update rules (Nocedal and Wright [16, Eq. (6.17) and Eq. (6.25)]) to update G−1k directly:
G−1+ = G −1 + (In −G−1A)uu>(In −AG−1) u>(A−AG−1A)u , G+ = SR1(G,A,u); (15)
G−1+ = ( In − uu>A
u>Au
) G−1 ( In − Auu>
u>Au
) + uu>
u>Au , G+ = BFGS(G,A,u). (16)
To estimate the convergence rate of Scheme (14), we measure the norm of the gradient of f as λf (x) , √ ∇f(x)>∇2f(x)−1∇f(x), x ∈ Rn. (17)
Note that this measure of optimality is directly related to the functional residual. Indeed, let x∗ = A−1b be the minimizer of Eq. (14). Then we obtain
f(x)− f(x∗) = 1 2 (x− x∗)>A (x− x∗) = 1 2 (Ax− b)>A−1 (Ax− b) = 1 2 λf (x) 2.
The following lemma shows how λf (·) varies after one iteration of process in Algorithm 3.
Lemma 3.1 (Rodomanov and Nesterov [19] Lemma 3.2) Let k ≥ 0, and let ηk ≥ 1 satisfy A Gk ηkA. Then we have that λf (xk+1) ≤ ( 1− 1ηk ) λf (xk) ≤ (ηk − 1)λf (xk).
Thus, to estimate how fast λf (xk) converges to 0, we need the upper bound of ηk, which is already done in Subsections 2.1 and 2.2. Thus, we can guarantee a superlinear convergence of λf (xk) using the greedy/random SR1 or BFGS update. The proof of Theorem 3.2 can be found in Appendix A.
Theorem 3.2 Under Algorithm 3, if we choose SR1 update, then we have
E λf (xk+1) λf (xk) ≤ ( 1− k n ) tr(G0 −A) µ , 0 ≤ k ≤ n.
If we adopt BFGS update, then we have
E λf (xk+1) λf (xk) ≤ ( 1− 1 n )k tr [ (G0 −A)A−1 ] , k ≥ 0.
Thus, we see both SR1 and BFGS methods share superlinear convergence for {λf (xk)}. In particular, for the SR1 update, our bound recovers the classical result in [16, Theorem 6.1], showing that the update stops after finite steps because Gn = A and λf (xn+1) = 0. Moreover, we also give an exact convergence rate during the entire optimization process. And the main decreasing term ( 1− kn ) for the SR1 update as well as (1− 1n ) k for the BFGS update in the k-th iteration are independent of the condition number κ of A, which improves the bound (1− 1nκ ) k in [19, Theorem 3.4].
Algorithm 4 Greedy/Random SR1/BFGS methods for strongly self-concordant objective
1: Initialization: Choose x0 ∈ Rn. Set G0 = LIn,L0 = In/ √ L. 2: for k ≥ 0 do 3: Update xk+1 = xk −G−1k ∇f(xk). 4: Compute rk = ‖xk+1 − xk‖xk , G̃k = (1 +Mrk)Gk, L̃k = Lk/ √ 1 +Mrk. 5: (i) Greedy/Random SR1: Choose uk = ū∇2f(xk+1)(G̃k), or uk ∼ Unif(Sn−1). Compute Gk+1 = SR1(G̃k,∇2f(xk+1),uk). 6: (ii) Greedy/Random BFGS: Choose ũk = ũ∇2f(xk+1)(L̃k), or ũk ∼ Unif(Sn−1). Compute Gk+1 = BFGS(G̃k,∇2f(xk+1), L̃>k ũk), and Lk+1 based on Proposition 2.6. 7: end for

heading: 4 Minimization of general functions
text: Finally, we consider the optimization of a more general machine learning objective with unfixed Hessians: minx∈Rn f(x), where f : Rn → R is a twice differentiable function with positive definite Hessians. Our goal is to extend the results in the previous sections, assuming that the methods can start from a sufficiently good initial point x0. We use the same assumption strongly self-concordant followed by Rodomanov and Nesterov [19].
Definition 4.1 (Strongly self-concordant) A function f : Rn → R is strongly self-concordant if the Hessians of f are close to each other in the sense that there exists a constant M ≥ 0 s.t.
∇2f(y)−∇2f(x) M‖y − x‖z∇2f(w), ∀ x,y, z,w ∈ Rn.
Rodomanov and Nesterov [19] have already mentioned several properties and examples of strongly self-concordant function, such as a 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 µ-strongly convex and L-smooth, i.e., there exist L ≥ µ > 0 such that
µIn ∇2f(x) LIn, ∀ x ∈ Rn
and κ := L/µ. Unlike quadratic minimization, the true Hessian in each step varies. In order to make Gk ∇2f(xk) always hold, we adjust Gk before doing quasi-Newton update. Instructed from [19], we also use the correction strategy, which enlarges the approximation Gk properly shown in Line 4 of Algorithm 4. Moreover, Algorithm 4 is only for theoretical analysis. We need to adopt the inverse update rules (Eqs. (15) and (16)) in practice. Additionally, we assume that the constants M and L are available for simplicity.
For the BFGS update, we can analyze how the Hessian approximation measure σx(G) , σ∇2f(x)(G) changes after one iteration following [19]. The proof can be found in Appendix A.
Theorem 4.2 Suppose that in Algorithm 4 BFGS update is used, and that the initial point x0 is sufficiently close to the solution:
Mλf (x0) ≤ ln 2
4κ(2n+ 1) . (18)
Then for all k ≥ 0, we have
∇2f(xk) Gk, Eσxk(Gk) ≤ 2nκ (
1− 1 n
)k , (19)
and
E λf (xk+1)
λf (xk) ≤ 2nκ
( 1− 1
n
)k . (20)
As for the SR1 update, the main difficulty compared to [19] is that we utilize a different measure τA(·) instead of σA(·), resulting in a refined proof version below, and we leave the proofs in Appendix A.
Theorem 4.3 For Algorithm 4 with SR1 update, suppose that the initial point x0 is sufficiently close to the solution:
Mλf (x0) ≤ ln 2
4κ(2nκ+ 1) . (21)
Then for all k ≥ 0, we have ∇2f(xk) Gk,Eσxk(Gk) ≤ 2nκ2 (
1− 1 n
)k , (22)
and
E λf (xk+1)
λf (xk) ≤ 2nκ2
( 1− 1
n
)k . (23)
Corollary 4.4 Combining with [19, Theorem 4.7] (shown in Appendix B.1), if x0 satisfies Mλf (x0) ≤ ln 32 4κ , we could obtain 1) for the greedy BFGS or greedy SR1 method,
λf (xk0+k) ≤ (
1− 1 n
)k(k−1)/2 · ( 1
2
)k · (
1− 1 2κ
)k0 · λf (x0), for all k ≥ 0,
where k0 = O (max{n, κ} ln(nκ)), 2) for the random BFGS or random SR1 method, with probability 1− δ for any δ ∈ (0, 1),
λf (xk0+k) ≤ (
1− 1 n+ 1
)k(k−1)/2 · ( 1
2
)k · (
1− 1 2κ
)k0 · λf (x0), for all k ≥ 0,
where k0 = O (max{n, κ} ln(nκ/δ)) .
Therefore, both greedy and random methods have non-asymptotic superlinear convergence rates. Additionally, our superlinear rates are condition-number-free compared to the rates in [19].

heading: 5 Numerical experiments
text: In this section, we 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, GrSR1 (greedy DFP, BFGS, SR1 methods) using directions based on ūA(G) = arg maxu∈{e1,...,en} u>Gu u>Au
, have quite competitive convergence with the standard versions. They also presented the results for the randomized versions RaDFP, RaBFGS, RaSR1, which choose directions directly from a standard Euclidean sphere. They discovered that the randomized methods are slightly slower than the greedy ones. However, the difference is not really significant.
The difference between our algorithms and their methods mainly comes from the greedy strategy for SR1 and the random strategy for BFGS3. Hence, we mainly focus on exhibiting our validity in these schemes. We refer to GrSR1v2 as our revised method and GrSR1v1 as the previous method. Similarly, we denote RaBFGSv2 that uses scaled directions (L>u) and RaBFGSv1 that directly uses random directions u correspondingly. We use u ∼ Unif(Sn−1) in all experiments for brevity.
Matrix approximation. When using Algorithms 1 and 2 for approximating a matrix A 0, we show the measure as proved by Theorems 2.3 and 2.4 in Figures 1a and 1b. As Figure 1a depicts, our greedy and random SR1 updates (GrSR1v2 and RaSR1) share superlinear convergence rate under measure τA(·), while our theoretical bound matches them well. Moreover, Figure 1b describes the behavior of the random BFGS update. Note that the greedy BFGS update we proposed does not satisfy the O(n2) 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 a direction without scaling (RaBFGSv1) fails to give such bounds. Moreover, we also discover the same findings under different condition numbers in Appendix C.1. 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 ∈ Rn. Running Algorithm 3 with SR1 and BFGS updates, we obtain the superlinear convergence of λf (·) shown in Figure 1c. Not surprisingly, our RaBFGSv2 runs faster than RaBFGSv1, while we also have the theoretical guarantee. At the same time, SR1-type methods converge to zero after n+ 1 steps because Gn = A. Here, we only depict the RaSR1 update, while the other SR1-type methods share similar behavior. Although our theoretical bound can not directly match the experiments due to the related initial terms τA(G0) and σA(G0), the decay terms: (1− k/n) vs. (1− 1/n)k already show the superiority of the SR1 method over the BFGS method in the quadratic minimization problem.
Regularized logistic regression. Next, we consider `2-regularized logistic regression:
f(w) = N∑ i=1 ln ( 1 + e−yiw >xi ) + γ 2 ‖w‖2, w ∈ Rn,
where X = [x1, . . . ,xN ] ∈ Rn×N are training samples with the corresponding labels y1, . . . , yN ∈ {+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̃k = (1 +Mrk)Gk) in Algorithm 4) recommended by [19]. Other details are shown in Appendix C.2. In order to simulate the local convergence, we use the same initialization after running several standard Newton’s steps to make measure ‖∇f(w0)‖ small (around 10−2 ∼ 101).
3There is no difference in the random SR1 method compared to Rodomanov and Nesterov [19], which directly selects random directions. And our greedy BFGS method is not efficient (O(n3) in each iteration) as we mentioned in Remark 2.5. Thus we leave it out.
We show the results in Figure 2. As we can see, the general picture is the same as for the previous objective. In particular, SR1-type methods are faster than BFGS-type methods, and the greedy algorithms also converge more rapidly than the random algorithms. The only difference is that our RaBFGSv2 may have slower convergence behavior than RaBFGSv1 under a small κ in Figure 2a. We consider our scaled direction is more suitable for a constant Hessian matrix as the quadratic objective has. Thus we still have a 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 κ in Figure 2b, we find our RaBFGSv2 could be faster than GrBFGSv1 and RaBFGSv1. This implies that our proposed method has less dependence on the condition number κ.
Regularized Log-Sum-Exp. Followed by Rodomanov and Nesterov [19], we also present preliminary computational results for greedy and random quasi-Newton methods, applied to the following test function with C = [c1, . . . , cm] ∈ Rn×m, b1, . . . , bm ∈ R, and γ > 0:
f(x) := ln  m∑ j=1 ec > j x−bj + 1 2 m∑ j=1 ( c>j x )2 + γ 2 ‖x‖2 ,x ∈ Rn.
We also use the same synthetic data in [19, Section 5.1] and leave the detail in Appendix C.2. As Figure 3 depicts, the BFGS-type methods are slower than the SR1-type methods. GrBFGSv1 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 we also present the theoretical guarantee for these algorithms.

heading: 6 Conclusion
text: 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 in contrast to Rodomanov and Nesterov [19], and the random version of these methods. In particular, we have provided the faster Hessian approximation behavior and the condition-number-free (local) superlinear convergence rates applied to quadratic or 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 be useful for understanding the quasi-Newton methods in a more specific view.
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. 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).

Review summaries:
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.  Similar 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$).  Experiments 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.  

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.

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.  I 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). 

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$).  I think it is really a good paper.