Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search
Authors: Qiujiang Jin
Ruichen Jiang
Aryan Mokhtari
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Quasi-Newton method
BFGS Algorithm
Global convergence analysis
Non-asymptotic convergence analysis
Inexact line search
Primary area: optimization

Abstract: In this paper, we present the first explicit and non-asymptotic global convergence rates of the BFGS method when implemented with an inexact line search scheme satisfying the Armijo-Wolfe conditions. We show that BFGS achieves a global linear convergence rate of $(1 - \frac{1}{\kappa})^t$ for $\mu$-strongly convex functions with $L$-Lipschitz gradients, where $\kappa = \frac{L}{\mu}$ represents the condition number. Additionally, if the objective function's Hessian is Lipschitz, BFGS with the Armijo-Wolfe line search achieves a linear convergence rate that depends solely on the line search parameters, independent of the condition number. We also establish a global superlinear convergence rate of $\mathcal{O}((\frac{1}{t})^t)$. These global bounds are all valid for any starting point $x_0$ and any symmetric positive definite initial Hessian approximation matrix $B_0$, though the choice of $B_0$ impacts the number of iterations needed to achieve these rates. By synthesizing these results, we outline the first global complexity characterization of BFGS with the Armijo-Wolfe line search. Additionally, we clearly define a mechanism for selecting the step size to satisfy the Armijo-Wolfe conditions and characterize its overall complexity.

Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolf Line Search
Qiujiang Jin ECE, UT Austin giujiangjann@gmail.ccm com
Ruichen Jiang ECE, UT Austin rjiang@utexas.com edu
Aryan Mokhtari ECE, UT Austin mokhtari@austinn utexas. edu
Abstract
In this paper, we present the first explicit and non-asynmn asnmatymptoiic global convergence rates of the BFGS method when implemented with an inexact line search scheme satisfying the Armijo Armijo-Wolfe conditions. We show that BFGS achieves a global linear convergence rate of (1 ) for j-strongly convex functions with L-LLipschtzz gradients, where x = & represents the condition number. Additionally, if the objective function's 's Hessian Lipschítz, BFGS with the Armijo-Woon Wolfe line search achieves a linear convergence rate that depends solely on the line search parameters, independent of the condition number. We also establish a global superlinear convergence rate of (({+)'). These global bounds are all valid for any starting point Zo and any symmetric positive definite initial Hessian approximation matrix Bg though the choice of B, impacts the number of iterations needed to achieve these rates. By synthesizing these results, we outline the first global complexity characterization of BFGS with the Armijo- Wolfe line search. Additionally, we clearly define a mechanism for selecting the step size to satisfy the Armijo- Wolfe conditions and characterize overall complexity.
Introduction
In this paper, we focus on solving the following unconstrained convex minimization problem
min #gRd
fxx)
where f Rd R is strongly convex and twice differentiable. Quasi-Newton methods are among the most popular algorithms for solving this class of problems due to their simplicity and fast convergence. Like gradient descent-type methods, they require only gradient information for implementation, while they aim to mimic the behavior of Newton's 's method by using gradient information to approximate the curvature of the objective function. There are several variations of quasi-Newtor methods, primarily distinguished by their update rules for the Hessian approximation matrices. The most well-know among these include the (BFGS) method [3-6]. the Symmetric Rank-One (SR1) method [7, 81, and the Broyden method [9]. Apart from these classical methods, other variants have also been proposed in the literature, including randomized quasi-Newton methods [10-14], greedy quasi-Newton methods [13-16], and those based on online learning techniques [17, 18J. this paper, we mainly focus on the global analysis of the BFGS method, arguably the most successful quasi-Newton method in practice.
(DFP) method [1, 2]. the Broyden-
The classic analyses of BFGS, including [19-28], primarily focused on demonstrating local asymp- totic superlinear convergence without addressing an explicit global convergence rate when BFGS is deployed with a line-search scheme. While attempts have been made to establish global convergence for quasi-Newton methods using line search or trust-region techniques in previous studies [8, 29-33], these efforts provided only asymptotic convergence guarantees without explicit global convergence rates, thus not fully characterizing the global convergence rate of classical quasi-Newton methods.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In recent years, there have been efforts to characterize the explicit convergence rate of BFGS within local neighborhood of the solution, establishing a superlinear convergence rate of the form ( (7))'
see, for example, [34-37]. However, these results focus solely on local convergence analysis of BFGS under conditions where the stepsize is consistently set to one, the iterate remains close to the optimal solution, and the initial Hessian approximation matrix meets certain necessary conditions. Consequently, these analyses do not extend providing global convergence guarantee. For more details on this subject, we refer the reader to the discussion section in [38].
To the best of our knowledge, only few papers are closely related to our work and establish a global non-asymptotic guarantee for BFGS. In [39], it was shown that BFGS with exact line search achieves global linear rate of (1 -/-² (1 + H -' - 11 + - where y is the strong convexity parameter, L is the Lipschitz constant of the gradient, Bo is the initial Hessian approximation matrix, and Tr(-) denotes the trace of a matrix. After (cd) iterations, this rate approaches (1 - ) which is significantly slower than the convergence rate of gradient descent. Additionally, a recent draft in [40] studied the global convergence of BFGS under an inexact line search. While this work establishes a local superlinear rate, it only shows a global linear rate of the form (1 - E). Hence, both these results fail to prove any global advantage for BFGS over gradient descent. In [38], the authors improved upon [39] by showing a better global linear convergence rate and faster superlinear rate for BFGS with exact line search. Specifically, for an L-Lipschitz and u-strongly convex function, _
BFGS initialized with Bo L/ achieves a global linear rate of (1 Læzz ) for 2 1, while BFGS with Bg = μ achieves the same rate after d log x iterations. With the additional assumption that the objective's s Hessian is Lipschitz, an improved linear rate of (1 - 4) is achieved after (1x) iterations when Bg = LI and after Od n + k) when By = μl, matching the rate of gradient descent. A superlinear rate of (2/v3)' was also shown when the number of iterations exceeds specific thresholds.
Contributions. In this paper, analyze the BFGS method combined with the Komij line search, the most commonly used line search criteria in practical BFGS applications: see, e.g., [41]. For minimizing an L-smooth and μ-stroogly convex function, we present a global convergence rate of (1- To the best of our knowledge, this is the first result demonstrating a global linear convergence rate for BFGS that matches the rate of gradient descent under these assumptions. Furthermore, we show that if the objective function's 's Hessian is Lipschitz continuous, BFGS with the Armijo Wolfe line search converges at a linear rate determined solely by the line search parameters and not the problem's 's condition number, k = 1/H, when the number of iterations is sufficiently large. Finally, we prove a global non-asymptotic superlinear convergence rate of (k(d.,,Co)//)f where h(d, k. Co) depends on the condition number k, the dimension d, and the weighted distance between the initial point To and the optimal solution x., denoted by Co- We summarize our results in Table 1. By combining these convergence results, we establish the total iteration complexity of BFGS with the Armijo-Wold Wolfe line search. We also specify the line search complexity by investigating a bisection algorithm for choosing the step size that satisfies the Armijo Tomioo-Woffe Wolfe conditions. Our result is one of the first non-asymptotic analysis characterizing the global convergence complexity of the BFGS quasi-Newton method with an inexact line search.
Notation. We denote the f2-norm by || []. the set of d x d symmetric positive definite matrices by sd and use A < B to mean B - A is symmetric positive semi-definite. The trace and determinant of a matrix A are represented as Tr(A) and Det(A), respectively.
2 Preliminaries
In this section, we present the assumptions, notations, and intermediate results useful for the global convergence analysis. First, we state the following assumptions the objective function f.
Assumption 2.1. Assumption 2.2. The gradient of f is Lipschitz continuous with parameter L 0.
The function f is twice differentiable and strongly convex with parameter μ > 0.
These assumptions are common in the convergence analysis of quasi-Newtor methods. Under these, we show a global linear convergence rate of O((1 - ".)) To achieve a faster linear convergence rate that is independent of the problem condition number, and a global superlinear rate, we require an additional assumption that the objective function Hessian is Lipschitz continuous, as stated next.
Assumption 2.3. The Hessian of f Lipschitz continuous with parameter M > 0, for xr E Rdd
we have 2 f(y()) < M | vll-
2

---

Initial Matrix
Convergence Phase
Convergence Rate
Starting moment
Bo
Linear phase I
(B,) v(Bb) + Co V (Bo) + Cok
Bo
Linear phase II
Bo
Superlinear phase
(( Co 9 CBB
V(BB) + Co (Bn) + Cor
1
L.I
Linear phase I
LI
Linear phase II
dx + Cak
LI
Superlinear phase
du Com
dk + Cok
jul
Linear phase I
1)
dlog
Linear phase II
(1 + Co)d + Cuk
Superlinear phase
(ogG
(1 + Co)d + Cok
Table 1: Summary of our results for (i) an arbitrary positive definite Bo. (ii) Bg L,,, and (iii) Bo pd.
Here, (A) := Tr(A) d log (A), Bo + Bo and Bg V f(x)) Bo Bo f(r.) 3 The last column shows the number of iterations required to achieve the corresponding linear or superlinear convergence phase. For brevity, the absolute constants are dropped.
Note that the above regularity condition on the Hessian assumption is also common for establishing the superlinear convergence rate of quasi-Newton methods [19-28].
BFGS Update. Next, we state the general update rule of BFGS. If we denote x, as the iterate at
time f, the vector 9r f((z) as the objective function gradient at Zt. and Be as the Hessian approximation matrix step f, then the update is given by
It+1 It + nede,
de = -B gt.
where > 0 is the step size and d, is the descent direction. By defining the variable difference 8, == T++1 Iy and the gradient difference Y/ (=(+1) fz)), we can present the Hessian approximation matrix update for BFGS as follows:
B1+1 = B, B Br
+ Vrlle
(3)
8, B,st
sTy y/+
To avoid the costly operation of inverting the matrix B,, one can define the inverse Hessian approxi- mation matrix as He := B," and apply the -Morrano--orrooo--- Woodbury formula to obtain
St3/e
(
8/
S15,
H++1 =
He
Vr
s. ye
is well-known that for a strongly convex objective function, the Hessian approximation matrices B, remain symmetric and positive definite if the initial matrix Bo is symmetric positive definite [41]. Therefore, all matrices B, and H; are symmetric positive definite throughout this paper.
As mentioned earlier, establishing global convergence guarantee for BFGS requires pairing it with line search scheme select the stepsize 7)-- This paper focuses on implementing BFGS with the Armijo-Woffe line search, detailed in the following subsection.
Armijo-Wolfe Line Search. We consider stepsize 17: > 0 that satisfies the Armijo Wolfe conditions
f(x: + md)) S f(x) + om (frt de,
(5)
vf(z; + +dd) d, 2 BVf(zz)
(6)
where a and 3 are the line search parameters, satisfying 0 < a < B < and 0 < The condition in (5) is the Armijo condition, ensuring that the step size тi provides sufficient decrease in the objective function f. The condition in (6) is the curvature condition, which guarantees that the slope f + n)d de at 7) is not strongly negative, indicating that further movement along de would significantly decrease the function value. These conditions provide upper and lower bounds on the admissible step size 7)t In some references, the Armijo- Smijo line search conditions are known as the weak Wolfe conditions [42, 43). The procedure for finding 7)t that satisfies these conditions described in Section 7. Next lemma presents key properties of the Armijo-Wor Wolfe conditions.
3

---

Lemma 2.1. Consider the BFGS method with Armijo- Wolfe inexact line search, where the step size satisfies the conditions in (5) and (6). Then, for any initial point 2o and any symmetric positive definite initial Hessian approximation matrix Ba, the following results hold for all 0:
f(x1) ((244)) 2
V1 2 31
and f(x++1) S f(re)
(7)
-9i- St
9t 8t
Remark 2.1. While in this paper we only focus on the Armijo-Wokd line search, our results are also valid for some other line search schemes that require stricter conditions. For instance, the strong Wolfe line search, given O < a < 3 < and O < a < 2.2 the required conditions for the step size are
f(x + midd) S f(1)) am, ((x))" de. IV + mide"
TT ddll = f(x)) T de.
Indeed, if th satisfies the strong Wolfe conditions, also satisfies the Ammijo-Wlly conditions. Another commonly employed line search scheme
Goldstein. which imposes the conditions T de S f(x+) - f(xx + mxd4) S - -C2 ((xx)) de,
-c1 (xx))
Goldstein line search indicates that Th satisfies the sufficient decrease condition in (5) required for the Armijo- Armijo-Wolfe conditions, with a C1- Moreover, given the convexity of f. the upper bound on f(z,) f(x + m,d,) in the Armijo-Goldsee
with 0 < C1 1 C2 1. The lower bound on fxx) f f(x; + nide) in the
line search suggests ni f(z + Mid)) de S f(zz) - + n(de) S Thus, Th also meets the curvature condition in (6) required in the Armijo- Wolfe conditions with 3 c2. Hence, all our results derived under the Armijo- Wolfe line search are also valid for both the strong Wolfe line search and the Goldstein line search
-C2 fzz) T dr.
3 Convergence Analysis
In this section, we present our theoretical framework for analyzing the global linear convergence rates of BFGS with the Armijo-Wolf Wolfe line search scheme. To start, we introduce some necessary definitions and notations. We define the average Hessian matrices Je and G2
as
J - S. V2 f'z + + =x))dTT,
v2 [[v''((aa
Ge Gr:=
+ T(a- - =xz))dT.
(8)
Further, for measuring the suboptimality of the iterates we define the sequence C2 as
M
C. == F
2((((m) f(x.)),
AI 2 0,
where M is the Lipschitz constant of the Hessian defined in Assumption 2.3 and μ is the strong con- vexity parameter introduced Assumption 2. analyze the dynamies of the Hessian approximation matrices ( B, + we use the function (-A)
(A) == Tr(A) - d - log Det(A),
(10)
well-defined for any A E + was introduced in [32] to capture the discrepancy between A and the identity matrix 1. Note that (AA 2 0 for any A E 8 and (A) = O if and only if A = I.
Before we start convergence analysis, given any weight matrix P E Qd $4 we define the weighted versions of the vectors It. 8t, Vt. de and the matrix B,, Jr as
g. p-$ 1 St.
S, = P
Ú. p- yts
d; =
(11)
B P
J, = P
(12)
Note that these weighted matrices and vectors preserve many properties of their unweighted coun- terparts. For instance, two of these main properties are ". s, 9t s; and 0. & v st. Similarly, the update for the weighted version of Hessian approximation matrices closely mirrors the update of their unweighted counterparts, as noted in the following expression:
B B. B,8,87 B.
DeD.
A1 2 0.
(13)
87 B.S.
8, De
Finally, we define a crucial quantity, Ô., which measures the angle between the weighted descent direction and the negative of the weighted gradient direction, satisfying
- 8
cos(O.)
(14)
|1 $

---

3.1 Intermediate Results
In this section, we present our framework for analyzing the convergence of BFGS with an inexact line search. We first characterize the relationship between the function value decrease at each iteration and key quantities, including the angle 0g defined in (14).
Proposition 3.1. Let (2e) be the iterates generated by BFGS. Recall the definitions of weighted vectors in (11). Then, for any weight matrix P and for all t Z 1, we have
f(x)) 1 f(xx) f(zo) f(xx))
(1
1-1 II ==
cos² cos?(0.)
(
Piqun
(15)
mi
where Pt, qt, my and in are defined
D. = f(e) - f(I++1)
|
Dr Sc | 1
0 Sc
ae = [(x)) f(x))
mr
(16)
- 8c
-. &t
This result shows the convergence rate of BFGS with Armijo- Wolfe line search depends on four products: IT Ps. IT:i0 9c, I f4, and IT: co.) To establish an explicit rate, need
lower bounds on these products. Lemma 2.1 shows that the lower bounds for I P. and II n. depend on the inexact line search parameters a and 3. We will further prove that if the unit step size V) satisfies the Armijo-Woll conditions, better lower bounds can be obtained for these products. cus" cus'((,)
The lower bounds for I1 q and I1:-0
(d,) were established in previous work [38] as presented
in Appendix D. Specifically, the bounds for IT d depend on the choice of the weight matrix, which varies in different sections of the paper, requiring separate bounds for each case. However, the bound for I (0.) does not require separate treatment. This is explicitly established in Proposition D.I, a classical result, as discussed in [41, Section 6.4]. We build all our linear and superlinear results by establishing different bounds the terms in (15).
mi
Global Linear Convergence Rates
Building on the tools introduced in Section establish explicit global linear convergence rates for BFGS with the Armijo-Won Wolfe line search, requiring only the strong convexity and gradient Lipschitz conditions from Assumptions 2.1 and 2.2. Our proof leverages the fundamental inequality in (15) from Proposition 3.1 and lower bounds on the terms that appear in the contraction factor. Here, we set the weight matrix P P LI and hence define the initial weighted matrix Bo as Bo + Bo. The following theorem presents our first global linear convergence rate of BEGS for any Bo E $
Theorem 4.1. Suppose Assumptions 2.1 and 2.2 hold. Let {21)12o be the iterates generated by BFGS, where the step size satisfies the Armijo- Wolfe conditions in (5) and (6). For any initial point To E Rdd and any initial Hessian approximation matrix Bo E Sd 84 we have
f(z)) f(x.) < (1- (1--- (( 20 (a(1--3) 3) - f(xo) - f(x.)
111.
(17)
K
Remark 4.1. In [38], the authors analyzed BFGS with exact line search and established global ) In comparison, our result in (17) achieves a faster linear
((Hp)
linear rate of (1 - rate by eliminating the /R factor in the denominator. This improvement arises from using the Armijo- Wolfe conditions. Specifically, under these conditions, we show Him))-(m1111) 2 a as shown -9i st in Lemma 2.1, where a (0, 1/2) is line search parameter. In contrast, using exact line search, the authors in [38] proved that [(2x)-((2<<1))
-9. 2 VR+T thus leading to the extra vTr factortor in their rate.
From Theorem 4.1, we observe that the linear convergence rate is determined by the quantity V (Bo) Thus, simplify our bounds, we consider two different initializations: B, LI and Bg pll
Corollary 4.2. Suppose Assumptions 2.1 and 2.2 hold, {2ehe2o are generated by BFGS with step size satisfying the Armijo- Wolfe conditions (5) and (6), and xo E B8d is an arbitrary initial point.
5

---

If the initial Hessian approximation matrix is set as Bu = LI, then for any t 2 1
f(x1) f(x))
2a(1 3)
(18)
f( - f(x.)
K
If the initial Hessian approximation matrix is set as Bo = pl,, then for any t 2 1 we have (1 log 2 Moreover, for I 2 d log K. we have
f(x))
f(x,) f(x.) v 1 2a 9)
(19)
f(zo) f(x=)
3k
Corollary 4.2 shows that when initialized with Bo = LI, BFGS achieves a linear rate of O - )) from the first iteration, matching the rate of gradient descent. It also indicates that initializing with Bo = !uT achieves a similar rate but after dogg k iterations. While this suggests a preference for initializing with Bo- LT, subsequent analysis reveals that with enough iterations, BFGS with either initialization can attain a faster linear rate independent of k. In some cases, starting with Bg = ju may lead to fewer total iterations to achieve this faster rate. We will explore this trade-off later.
5 Condition Number Independent Linear Convergence Rates
In this section, we improve the previous results and establish a mon-asymptotic, condition number- free global linear convergence rate for BFGS with the Armijo Wolfe line search. This requires the additional assumption that the Hessian is Lipschitz continuous. Our analysis builds on the previous methodology but uses P = V f(x.) instead of P LI to prove the condition number-independent global linear rate. Thus, the weighted initial matrix Bu is f(xx)
- $ Bu V fz..) 1. Next, present general global convergence bound for any initial Hessian approximation Bo E
Proposition 5.1. Suppose Assumptions 2.1, 2.2 and 2.3 hold. Let {z1)120 be the iterates generated by BFGS with the step size satisfying the Armijo Wolfe conditions in (5) and (6). Recall the definition Cf, in (9) and (-) in (10). For any initial point Zo E IRd and any initial Hessian approximation matrix Bo Sd the following result holds:
f(xa) f(zx) S (1 (1-2a(1 2a(1 3)e [(x)) - f(x.)
Proposition 5.1 demonstrates that the convergence rate BEGS with the Armijo Wolfe line search is influenced by (Bo)) and the sum Σi= C. The first term Vi (Bo)) is a constant that depends on our choice of the initial Hessian approximation matrix By The second term Σ/= C2 can also be upper bounded using the non-asymptotic global linear convergence rate provided in Theorem 4.1.
f-1
Theorem 5.2. Suppose Assumptions 1, 2.2 and 2.3 hold, and let (aehe2o be the iterates generated by BFGS with the Armijo- Wolfe line search in (5) and (6). Then, for any initial point zo E Rd and any initial Hessian approximation Bu E $ ift 2 (Bo) + +33 1e (Bo) + a(1-9) Cor, we have
9
f(zo) - f(x)) S (1 20 (3
(xx) fxx
(20)
3
This result shows that when the number of iterations meets 2 V (B)) + V + a(1-B) By Cok, BFGS with Armijo-Wolfe conditions achieves a condition number-independent linear rate. The choice of Bo is critical as it influences the required iterations through Bg = V (xx,) (( - 1 and Bo 1, Bo. Different choices of Bo affect V (( (Bo) + 3C, V (Bo) and thus the number of iterations needed for condition-free linear convergence. While optimizing Bg minimize V VBB)) 3C, V (Bp) is possible, we focus on two practical initialization schemes: Bo = LI and Bo = =ul.
Corollary 5.3. Suppose that Assumptions 2. 2.2 and 2.3 hold. Let (x,) 12.1 be the iterates generated by the BFGS method, where the slep size satisfies the Amiioo-Woje conditions in (5) and (6), and To Rdd as an arbitrary initial point. Then, given the result in Theorem 5.2, we have
we set Bg LI, the rate in (20) holds for 2 di + a<l- Cok,
we set Bg μI,, the rate in (20) holds for t Z (1 + 1+33))d
all-3) Cok.
Based on Corollary 5.3, if Co & K. or equivalently f(n) - (x.) < Lt, then BFGS with Bg = μT requires less iterations to achieve the condition number-independee linear convergence rate.

---

6 Global Superlinear Convergence Rates
In this section, we present our global superlinear result. Consider the definition Bo = as well as the definition of Pt which is given by
Pe = -9. de = f(x,))
V 0.
(21)
|
To motivate, let us briefly discuss why we are only able to show a linear convergence rate instead of a superlinear rate in Theorem 5.2. By inspecting the proof, we observe that the bottleneck is due to the lower bounds on fr. and f4. we used ýt 2 and nn 2 1 - / from Lemma 2. which leads to the constant factor a(1 - 3) in the final linear rate in Theorem 5.2. Thus, to show a superlinear convergence rate, we need to establish tighter lower bounds for f.. and ât In the following lemma, we show that if the step size T) = I, we are able to establish such tighter lower bounds.
Lemma 6.1. Recall fr f(x)) ((me)(( and fu 8. &, satisfies the Armijo- Wolfe conditions (5) and (6), then we have
9. 6t defined in (16). If the unit step size 1/. = 1
-9, s,
1+C,
1
pt 2 1-
2u 2 (1 C1+
(22)
2pt
In contrast to the constant lower bounds in Lemma 2.1, the lower bounds in (22) depend on C, and Pr- Later, we show C, - 0 and f:: - 1. Hence, the lower bounds in (22) approach I as the number of iterations increases, enabling us to prove a superlinear rate. That said, the lower bounds in Lemma 6. hold only when 7/2 1. To complete the picture, we need to quantify when and how often the unit step size is selected during BFGS exccution. This is addressed in the next lemmas.
Lemma 6.2. Suppose Assumptions 2.1, 2.2, and 2.3 hold and define the constants
6, : min
1 6'
2((11 a a) 11 (2)
-11 }. 82 == max V1-3
1
8g
V1 (23)
8' 22((1a))
which satisfy 0 < 5, < 82 < 1 < 6z. IfC, S 8n and on S Pr S 8g. then Ve = 1 satisfies the Armijo-Woll Wolfe conditions (5) and (6).
Lemma 6.2 shows that when C2 - dj and or falls within the interval [62. the step size nh = 1 is admissible and meets the Armijo-Wolh Wolfe conditions. Note that by the linear convergence result in Theorem 1. the first condition on C2 will be satisfied when & is sufficiently large. Additionally, using Proposition G.2 in the Appendix, we can show that the second condition on Pa is violated only for a finite number of iterations. These observations are formally presented in the following lemma.
Lemma 6.3. Suppose Assumptions 2.1, 2.2, and 2.3 hold and the iterates {I; Jt20 are generated by the BFGS method with step size satisfying the Armijo Wollfe conditions in (5) and (6). Recall Ce defined in (9), (-) defined in (10), {8.). defined in (23) and Bo- 1, BB. We have C. S 82 when
3k log
Co
2 to = max (Bo). a(l - 3)
81 S
(24)
we define w(x) x log(1 + x), the size of the set Moreover, we
{1: pt $ dal] is most
| s 8, (W(B)) + 2C v (Bo) + 6Con a(1 a(1-1)) ) where 8s == min 1), wo(s - 1)}
1
(25)
Lemma 6.3 implies that conditions C. S 81 and p. E [62, 83] will be satisfied for all but a finite number of iterations. Thus, if the line search always starts by testing the unit step size (as shown in Section 7), we will choose f/- = 1, and accordingly, the tighter lower bound in Lemma 6.1 will apply for all but finite number of iterations. By applying these lower bounds along with (15) from Proposition 3.1, we can prove global superlinear convergence rate, as presented next.
Remark 6.1. Lemmas 6.2 and 6.3 are inspired by the analysis in [40]. Specifically, Lemma 5.10 of [40] characterized the conditions on C₁ and Ps under which 1 = satisfies the Armijo condition (5), and further bounded the number of iterations where these conditions are violated. However, our Lemma 6.2 addresses both the Armijo condition in (5) and the curvature condition in (6), and the arguments appear simpler. Additionally, our proof for the superlinear convergence rate differs from [40]. Their approach analyzed the Dennis-Moré ratio and measured "local" superlinear convergence using the distance (Vx(x))) ) (x+- - x.)lll In contrast, our "global" result is based on the unified framework in Proposition 3.1 and uses the function value gap as a measure of convergence.
7

---

Theorem 6.4. Suppose Assumptions 2.1, 2.2, and 2.3 hold and the iterates (xa 112u are generated
by BFGS with step size satisfying the Armijo- -oole conditions in (5) and (6). Recall the definition Cf in (9), (-) in (10), Bu == I Bo. Bo : V (x.)) Bo V (x.))= and ő1, 82, 83, in (23) and (25). Then, for any zo E Rd and any Bo E 54+, the following global superlinear result holds:
[(x)) [xx,)
(, + (6o 5gCo) 4 ( (B) + a11
36
Co log
+
(11-3)
38g
Co)k
(26)
f(z)) f(x.)
t
where { defined below are constants that only depend on line search parameters a and [
5g = max (2 + 2. 453)
26z 61 log 82 :g:= log 2a(1-33 : 85, =6:
28 - 1- 81
262 1-
The above result shows global superlinear convergence rate of the form ((( where C" depends on the condition number K, the initial weighted distance Co. and the initial Hessian approximation matrix Bg. To simplify the expression, we report the above bound for Bo LI and Bo = pl.
Corollary 6.5. Suppose Assumptions 2.1, 2.2, and 2.3 hold and the iterates {2+ are generated by the BFGS method with step size satisfying the Armijo-Warn Wolfe conditions in (5) and (6), and xo Rd
as an arbitrary initial point. Then, given the result in Theorem 6.4, the following results hold:
If we set Bg LI, then we have
366 log Co + 36g Cu) 67dk + (((1-)) 61
[ax)) [(x.) ((x0) - f(x.)
a(1-8)
(27)
t
we set Bo μI,, then we have
f(xx) - f(xx) F(xo) - f(x.)
3d (ō6 + 87 + &oCo + (al1-))
Co + log
b1 a(1- Bj Co)
36g
(28)
This result shows that BFGS with Bn = L. achieves global superlinear rate of O(( dde+Coo )., while BFGS with the initialization Bu ,Il converges at global superlinear rate of O(( Coddog Hence, the superlinear result for B, = μIl outperforms the rate for B, = LI when C. log K & K. Remark 6.2. We chose Bg = L1 and Bo pl as two specific cases since they lead to explicit upper bounds in terms of the dimension d and the condition number k in various theorems, simplifying the interpretation of our results. In practice, however, we often set By = cl, where = 1..0%. with = I2 - F1, y = f((2)) - ((1)) and xı, x2 as two randomly selected vectors. This choice ensures e E [us, D}, and in the following numerical experiments, the performance of Bo el is similar to that of By = pul The complexity of BFGS with this initialization is reported in Appendix H.
Con Co )).
Complexity Analysis
Discussions on the iteration complexity. Using the three established convergence results in The- orems 4.1, 5.2 and 6.4, we can characterize the total number of iterations required for the BFGS method with the Armijo-Wolfe line search to find a solution with function suboptimality less than e. However, as discussed above, the choice of the initial Hessian approximation B, heavily influences the number of iterations required to observe these rates. To simplify our discussion, we focus on two specific initializations: Bo LI and Bo = pl.
The case of Bg I.: The overall iteration complexity of BFGS with By = I.7 given by
o min x log 1 - (d + Co)x + log
log 1
log
1
dx+Con log
The case of Bn = nJ: The overall iteration complexity of BFGS with Bo = uut is given by
O min d dlog + log 1 Coldlog k) log
1
log
log 2 V
Cold x+x) log
8

---

We remark that the comparison between these two complexity bounds depends on the relative values of K. d, Co. and e, and neither is uniformly better than the other. It is worth noting that for BFGS with Bn = I.I, we achieve complexity that is consistently superior to the O (A log :) complexity of gradient descent. Moreover, in scenarios where Co- = ((1) and d < K, BFGS with Bo = μd could result in an iteration complexity of O (v: + log ) which is much more favorable than that of gradient descent. The proof of these complexity bounds can be found in Appendix I.
Discussions on the line search complexity. We present the log bisection algorithm to choose the step size at iteration t satisfying the Armijo-Wolfe Wolfe conditions (5) and (6) in Algorithm I in Appendix J. We define Mmain and Mama as the lower and upper bounds of the "slicing window" containing the trial step size T)t, respectively. We start with the initial trial step size 1)2 1 and keep enlarging or decreasing it depending on whether the Armijo condition (5) or the curvature condition (6) is satisfied. Then, we dynamically update Amin Bmaz and shrink the size of this "slicing window" (Amin: 1lmaa). We pick the trial step size 1) as the geometric mean of Rmin and Amaz. i.e., log 17 -log Iima + log Mmma) /2, which is the reason why we call this algorithm "log bisection". Note that in each loop of Algorithm 1, we query the function value and gradient at most once to check the Armijo-Woli Wolfe conditions at Lines 2 and 9. The next theorem characterizes the average number of function value and gradient evaluations per iteration in Algorithm I after t iterations, denoted by As, which is equivalent to the average number of loops per iterations.
Theorem 7.1. Suppose Assumptions 2.1, 2.2 and 2.3 hold. Let {2rh120 be generated by BFGS with step size satisfying the Armijo-War Wolfe conditions in (5) and (6) and is chosen by Algorithmm 1. If we define a == (B,) + 3 x)o, then for any initial point To E E and initial Hessian approximation Bg E s the average number of the function value and gradient evaluations per iteration in Algorithm 1 after iterations satisfies
1 1- _ 2(1 1-13 1+
3 a 3 - a =) +2 +2 (log, 16(1-)))+ -log, ( 6 (B.) + 120
)
A, S 2+
The above result shows that when we run BFGS for N iterations, the total number of function and gradient evaluations is O(N + N log(1 x) )
N log(1 + *(B)))))) )). Thus, the total line search complexity can always be bounded by O(N log(( (B)) + +o) - O(N max (log d, log K, log C) Furthermore, notice that when N is sufficiently large such that we reach the superlinear convergence stage, i.e., N = 22 ND (Bo) + a). the total line search complexity becomes O(N), which means the average number of function and gradient evaluations per iteration
constant (1). We report the line search complexity results of different Bo = LI and Bo = pll in Appendix K.4.
8 Numerical Experiments
We conduct numerical experiments on cubic objective function defined as
f(x)
Σ glo) x v1(11)) BBU x
2 -
(29)
12
and g : R + R is defined as
|w Aw? 2 |
| < A
((w)=
(30)
1/4
3
| > A.
where a, B, A, E R are hyper-parameters and {" are standard orthogonal unit vectors in Rd We focus on this objective function because it is used in [26] to establish tight lower bound for second-order methods. We compare the convergence paths of BFGS with an inexact line search step size T7 that satisfies the Armijo-Wolt Wolfe conditions (5) and (6) for various initialization matrices Bp: specifically, Bg = LI, Bo = μul, Bo = I, and Bo = cl where is defined in Remark 6.2. is easily verified that E [M, Lj. We also compare the performance of BFGS methods to the gradient descent (GD) method with backtracking line search, using a = 0.1 in condition (5) and 3 = 0.9 in condition (6). Step size n is chosen each iteration via log bisection in Algorithm 1. Empirical results compared across various dimensions and condition numbers Ri, with the x-axis representing the number of iterations / and the y-axis showing the ratio fzx.) [(
9

---

BOSS
BIGS Loccurt
RICS Goomaled
LITOR Zorbac 21
BITOR Doccert A2 Cocnel 6D
DIFES
60
mumber iterations
mumber of iterations A
number iterations
(a) = 100, K 100.
(b) 100, K 1000.
d == 300, K 100.
12 Iacadd
Bi0t Teana
BEGG Inraac
Elo ICC
7on2
BiG 12
EPC2 Bxceet
cumber of Berations &
number Eersaioon
number of iseaaioons
(d) d 300, 6 1000.
(c) d 600, 100.
(f) d 600, 1000.
Figure 1: Convergence curves of BFGS with inexact line search of different Bg and gradeint descent with backtracking line search.
First, we observe that BFGS with By L. initially converges faster than BFGS with Bg JIT in most plots, aligning with our theoretical findings that the linear convergence rate BFGS with Bo = LI surpasses that of Bo μI in Corollary 4.2. In Corollary 4.2, we show that BFGS with BB- = LL could achieve the linear rate of (1 1/x) from the first iteration while BFGS with Bo μl needs to run d log K to reach the same linear rate. Second, the transition to superlinear convergence for BFGS with Bg = 5l typically occurs around Rs d, as predicted by our theoretical analysis. Although BFGS with B, = LI initially converges faster, its transition superlinear convergence consistently occurs later than for Bu = pl. Notably, for fixed dimension d = 600, the transition to superlinear convergence for Bo LI occurs increasingly later the problem condition number rises, an effect not observed for Bo = μl. This phenomenon indicates that the superlinear rate for Bn IJ is more sensitive the condition number x, which corroborates our results in Corollary 6.5. In Corollary 6.5, we present that BFGS with Bo = LI needs de steps to reach the superlinear convergence stage while this is improved to dloog for BFGS with Bn = pl. Moreover, the performance of BFGS with Bo = I and Bo cl is similar to BFGS with Bo = μd. Notice that the initializations of Bo = I and Bo cl are two commonly-used practical choices of the initial Hessian approximation matrix Bo
Conclusions, Limitations, and Future Directions
In this paper, we analyzed the global non-asymptotic convergence rates of BFGS with Armijo- Wolfe line search. We showed for objective function that is u-stronglyy convex with an T.- Lipschitz gradient, BFGS achieves a global convergence rate of (1 - 1/k)', where k = L./p. Additionally, assuming the Hessian is M M-Lipschitz, we showed BFGS achieves a linear convergence rate determined solely by the line search parameters, independent of the condition number. Under similar assumptions, we also established a global superlinear convergence rate. Given these bounds, we determined the overall iteration complexity of BFGS with the Armijo- Wolfe line search and specified this complexity for initial Hessian approximations Bd LI and B, nl.
One limitation of this paper is that the analysis only applies to strongly convex functions. Developing an analysis for the general convex setting is still unsolved. Another drawback is that we focus solely on the BFGS method. Extending our theoretical results to the entire convex Broyden's 's class of quasi-Newtor methods, including both BFGS and DFP, is natural next step.
10

---

Acknowledgments
The research of Q. Jin, R. Jiang, and A. Mokhtari is supported in part by NSF Award 2007668 and the NSF AI Institute for Foundations of Machine Learning (IFML).
References
[1] W. Davidon. Variable metric method for minimization. Tech. rep. Argonne National Lab., Lemont, III., 1959 (page 1).
[2] R. Fletcher and M. J. Powell. "A rapidly convergent descent method for minimization". The computer journal journal 6.2 (1963), pp. 163-168 (page I).
[3] C. G. Broyden. "The convergence of single-rank quasi-Newton methods". Mathematics of Computation 24.1 10 (1970), pp- 365-382 (page 1).
[4] R. Fletcher. "A new approach variable metric algorithmss. The computer journal 13.3 (1970), pp. 317-322 (page 1).
[5] D. Goldfarb. "A family of variable-metric methods derived by variational means". Mathematics of computation 24.109 (1970), pp. 23-26 (page 1).
[6] D. F. Shanno. "Conditioning of quasi-Newton methods for function minimization". Mathemat- ics of computation 24.111 (1970), pp. 647-656 (page 1).
[7] A. R. Conn, N. I. M. Gould, and P. L. Toint. "Convergence of quasi-Newton matrices generated by the symmetric rank one update". Mathematical (page 1).
proputtiiiioooooommnmnnnn programming 50.1-3 (1991), pp. 177-195
[8] H. F. Khalfan, R. H. Byrd, and R. B. Schnabel. "A theoretical and experimental study of the symmetric rank-one update". SIAM Optim. 3.1 (1993), pp. 1-24 (page 1).
[9]
G. Broyden. "A class of methods for solving nonlinear simultaneous equations". Mathemat- ics of computation 19.92 (1965), pp. 577-593 (page 1).
[10] Gower, D. Goldfarb, and Richtárik. "Stochastic block BFGS: Squeezing more curvature out of data". In: Int. Conference on Machine Learning. PMLR. 2016, pp. 1869-1878 (page 1).
[11] R. M. Gower and P. Richtárik. "Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms". SIAM Journal on Mairix Analysis and Applications 38.4 (2017),
pp. 1380-1409 (page 1).
[12] D. Kovalev, R. M. Gower, P. Richtárik, and A. Rogozin. "Fast linear convergence of random- ized BFGS". arXiv preprint arXiv:2002. 1337 (2020) (page 1).
[13] D. Lin, H. Ye, and Z. Zhang. "Greedy and random quasi-Newton methods with faster explicit superlinear convergence", Advances in Neural Information Processing Systems 34 (2021),
pp. 6646-6657 (page 1).
[14] D. Lin, H. Ye, and Z. Zhang. "Explicit convergence rates of greedy and random quasi-Newton methods". Journal of Machine Learning Research 23. 162 (2022), pp. 1-40 (page 1).
[15] A. Rodomanov and Nesterov. "Greedy Quasi-Newton Methods with Explicit Superlincar Convergence", SIAM Jourmal Optimization 31.1 (2021), pp. 785-811 (page l).
[16] Z.-Y. Ji and Y.-H. Dai. "Greedy PSB methods with explicit superlinear convergence". Compu- lational Optimization and Applications 85.3 (2023), pp. 753-786 (page 1).
[17] R. Jiang, Q. Jin, and A. Mokhtari. "Online Learning Guided Curvature Approximation: A Quasi-Newtor Method with Global -on-Asymito Superlinear Convergence" In: Proceed- ings of Thirty Sixth Conference on Learning Theory. Vol. 195. 2023, pp. 1962-1992 (page 1).
[18] R. Jiang and A. Mokhtari. "Accelerated quasi-newton proximal extragradient: Faster rate for smooth convex optimization". Advances in Neural Information Processing Systems 36 (2023) (page l).
[19] C. G. Broyden, J. E. Dennis Jr, and J. Moré. "On the local and superlinear convergence of quasi-Newton methods". IMA Journal of Applied Mathematics 12.3 (1973), pp. 223-245 (pages 3).
[20] J. E. Dennis and Moré. "A characterization of superlinear convergence and its application
to quasi-Newton methods". Mathematics of computation 28. 18.166 (1974), pp. 549-560 (pages 1,
3).
[21] Griewank and L. Toint. "Local convergence analysis for partitioned quasi-Newton updates", Numerische Mathematik 39.3 (1982), pp. 429-448 (pages 1, 3).

---

[22] J. Dennis, H. J. Martinez, and R. A. Tapia. "Convergence theory for the structured BFGS secant method with an application to nonlinear least squares". Journal of Optimization Theory and Applications 61.2 (1989), pp. 161-178 (pages 3)
[23] Y. Yuan. "A modified BFGS algorithm for unconstrained optimization", IMA Journal of Numerical Analysis 1 1.. (1991), pp. 325-332 (pages I,).
[24] M. Al-Baali. "Global and superlinear convergence of a restricted class of seaf-scaling methods with inexact line searches. for convex functions". Computational Optimization and Applica- tions 9.2 (1998), pp. 191-203 (pages 1, 3).
[25] D. Li and M. Fukushima. "A Globally and Superlinearly Convergent Gauss-Newton -Based BFGS Method for Symmetric Nonlinear Equations". SIAM Journal on Numerical Analysis
37.1 (1999), PP. 152-172 (pages 1,3)
[26] H. Yabe, H. Ogasawara, and M. Yoshino. "Local and superlinear convergence of quasi- Newton methods based on modified secant conditions". Journal of Computational and Applied Mathematics 205.1 (2007), pp. 617-632 (pages 1,3,9) 9).
[27] A. Mokhtarr, M. Eisen, and A. Ribeiro, "IQN: An incremental quasi- quasi-Newton method with local superlinear convergence rate". SIAM Journal on Optimization 28.2 (2018), pp. 1670-1698 (pages 1, 3).
[28] W. Gao and D. Goldfarb. "Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions"" Optimization Methods and Software 34.1 (2019),
Pp. 194 197 (pages I, 3).
[29] M. Powell. "On the convergence of the variable metric algorithm".. IMA Journal of Applied Mathematics 7.1 (1971), pp. 21-36 (page l).
[30] M. Powell. "Some global convergence properties variable metric algorithm for mini- mization without exact line searches". Nonlinear programming 9.1 (1976). pp. 53-72 (page 1).
[31] R. H. Byrd, J. Nocedal, and Y. Yuan. "Global convergence of class of quasi- quasi-Newton methods on convex problems". SIAM Journal on Numerical Analysis 24.5 (1987), pp. 1171-1190 (page 1).
[32] R. H. Byrd and J. Nocedal. "A Tool for the Analysis of Quasi-Newton Methods with Applica- tion to Unconstrained Minimization". SIAM Journal on Numerical Analysis, Vol. 26, No. 3 (1989) (pages 1, 4).
[33] R. H. Byrd, H. F. Khalfan, and R. Schnabel. "Analysis of symmetric rank-one trust region method".. SIAM Journal on Optimization 6.4 (1996), pp. 1025-1039 (page 1).
[34] A. Rodomanov and Y. Nesterov. "Rates of Superlinear Convergence for Classical Quasi- Newton Methods". Mathematical Programming (2021), pp. 1-32 (pages 2, 19).
[35] A. Rodomanov and Y. Nesterov. "New Results on Superlinear Convergence of Classical Quasi-Newton Methods". Journal of Optimization Theory and Applications 188.3 (2021),
pp. 744-769 (page 2).
[36] Ye, D. Lin, X. Chang, and 7.. Zhang. "Towards explicit superlinear convergence rate for SR1". Mathematical Programming 199.1 (2023), pp. 1273-1303 (page 2).
[37] Q. Jin and A. Mokhtari. "Non-asymptotic Superlinear Convergence of Standard Quasi-Newton
Methods".. Mathematical Programming, Volume 200, pages 425-473 (2022) (page 2).
[38] Q. Jin, R. Jiang, and A. Mokhtari. aNoptasympootic Global Convergence Rates of BFGS with Exact Line Search".. arXiv preprint arXiv:2404.01267 (2024) (pages 2, 5, 16, 37).
[39] V. Krutikov, E. Tovbis, P. Stanimirović, and L. Kazakovtsev. "On the Convergence Rate of Quasi-Newton Methods on Strongly Convex Functions with Lipschitz Gradient". Mathematics
11. 1.23 (2023), p. 4715 (page 2).
[40] A. Rodomanov. "Global Complexity Analysis of BFGS". arXiv preprint arXiv:2404.15051 (2024) (pages 2, 7).
[41] J. Nocedal and S. Wright. Numerical optimization. Springer Science Business Media, 2006 (pages 2, 5)..
[42] P. Wolfe. "Convergence Conditions for Ascent Methods". SIAM Review 11.2 (1969), pp. 226-
235 (page 3).
[43] P. Wolfe. "Convergence Conditions for Ascent Methods. II: Some Corrections". SIAM Review 13.2 (1971), pp. 185-188 (page 3).
[44] Y. Nesterov. Lectures on convex optimization. Springer Optimization and Its Applications
(SOIA, volume 137), 2018 (page 20).
12

---

Appendix
A Some Results on the Connections between Different Hessian Matrices
Lemma A.1. Suppose Assumptions 2.1, 2.2, and 2.3 hold, and recall the definitions of the matrices Jr and G2 in (8), and the quantity C₁ in (9). Then, the following statements hold:
(a) Suppose that (I S (ar for any I 2 O. we have that
fxx) J. (1+ C.V I+C,
(31)
(b) Suppose that f(x+11 S fxx) for any t 2 0 and 2 E [0, 11, we have that
1+C (z.)) V f(r +(1+11 - zz)) 3 (1 + (())
(32)
(c) For any 2 0, we have that
1
(33)
1+
(d) For any 1 12 0, we have thut
1 V
(34)
1+C,
(e) For any t 2 0 and i E [o, 11. we have that
1
G. = 2 f(z tfz x1) I (1 + C.G.,
(35)
C+
(f) For any t 2 0 and F, f E [0, 11. suppose that f(1(+1) S (zz) Then, we have that
1
fx + +8{)= = 2 [(x + fat) 3 (1 + 2C,) V2 V + fx))
(36)
1 2C,
Proof.
(a) Recall the definition of Jr in (8). Using the triangle inequality, we have that
|| f(x.) - Jell = J. (v2 f(x,) - f(x + T(E+11 (aai1-xx))) xz))) dr
f(*)(x)) f2f(2 + T - 21))
Moreover, it follows from Assumption 2.3 that ((.) - f2f(E, - T(r++1 - xz)) S M - (I, xx) + T(x. - x1+1)ll for any T E [0, 1j. Thus, we can further apply the triangle inequality to obtain
[(x) Sell S [ M [[1 ()xx xx) + r(x, 1(11)
< M | - zall 1/'' (1-T)dt + MI - -20ll //' rdr
M (| x.a11 + ||,8111 =x=1).
Since f is strongly convex. by Assumption 2.1 and f(x(+1) S f(z)), we have 5112;
I=11²= s f(x)) - [xx),, which implies that ||æ,---]| x- S (( f(x))// Similarly, since f(z++1) S f(zz). it also holds that | - xx & (((((z++)) - f(x)))/u s /2(f(x))- f(x,))/H Hence, we obtain that
M
[[v2 Jill
2(f(()) f(z+))
(37)
Vp
13

---

Moreover, notice that by Assumption 2.1, we also have Jj = pl and V2 = pl. Hence, (37) implies that
M - CoJer
v2 f(x)) - J: 1 fV - - 1
M
J - (xx))) 3 || ((=))]
V - C
where we used the definition of C in (9). By rearranging the terms, we obtain (31).
(b) Similar to the arguments in (a), for any i E [0, 1], we have that
f + f( =x)) V v2 (ax)) ||
<M][(1 - =) xx)) f f x.)]l
M ((1 (1-+)) x+1l f11x2+11 -x+1] x.1l)
$ M (V ////
(1(0)) f(x.)) + ++V
(f(041)) ( f(x)))
- <M 2 (f(x))- - f(xx))
Moreover, notice that by Assumption 2.1, we also have V2 f(xe+1 xz)) = pl and fxx) ? pl. The rest follows similarly as in the proof of (a) and we prove (32).
(c) Similar to the arguments in (a), we have that
M 2((((t)) - f(xa)).
[V') S M| - x.11 11.11
Vp
Moreover, notice that by Assumption 2.1 we also have V f(x;) 2 ull and v2f(xx) 2 uI.
The rest follows similarly as in the proof of (a) and prove (33).
(d) Recall the definition of G, in (8). Similar to the arguments in (a), we have that
fzx.) - G.ll = [. (v²f(x.) - -22(tt) T(x. xx))) dr
[ v2 T(x. -xt))
M / [[(1-)(aa 2;)lldr M x+ / (1 T)dT
M
M - ( 2 ||:: x.aIl S Vp
Moreover, notice that by Assumption 2.1 we also have G. 2 Hl and V2 fxx) ) 2 pl. The rest follows similarly as in the proof of (a) and we prove (34).
(e) Recall the definition of gi in (8). Similar the arguments in (a), for any 7 E [0, 1), we have that
V2 [(r + F(r. xz)) - -Gall
(V2 + f(x.. xx)) - 42 f2 T(I. - -xx))) dr
[. | + 7(x. -xa)) 42 f(x; + -xt))l
< [' M - =|||=+ - x. 2.11dr s 5 5 I - x+11 S
1
M
-
/ 2(f((x)) - (fann)-f(xxn) f(xx)).
Vi
Moreover, notice that by Assumption 2.1, we also have f + Ñ(z. xz)) 2 JuT and
Ge 2 ul. The rest follows similarly in the proof of (a) and we prove (35).
14

---

ff Similar to the arguments in (a), for any 7, E [0, 1], we have that
V f( + fs.)) f(r fsti
2 7 F|||,|1| - M||sell M (1 2+ll + || x+
s (V 2
+ / (f(ec41) f(2x))
- f(x))) f(2))))(22))) P -
s 2M V (1(zt)) f(x.))
Moreover, notice that by Assumption 2.1, we also have f2x Fst) = ul and V far( +st) = pl. The rest follows similarly in the proof of (a) and we prove (36).
B Proof of Lemma 2.1
Recall that gt (xx)) Given the condition in (5) and the fact that 8t ned,, have
f(1++1) s f(x)) + ag, St.
Moreover, since B, is symmetric positive definite, we have -9, st na.. B, gt > 0 (unless ør 0 and we are the optimal solution). This further leads the first claim, which
f(x)) f((1411)
2a
-6 St
Similarly, the above argument implies that ag < 0 and as a result f(*(+1) S fzx) and the last claim also follows.
To prove the second claim, we leverage the condition (6). Specifically, if we subtract g. de from both sides of that condition, we obtain that
(0t+1 9e) d, 2 (B 119. de
Next, using the fact that = nid, by multiplying both sides by me and use the simplification Vt g++1 St obtain that
Ve 81 2 (B 1)97
(1) 8, = - se B).
Again using the argument that 9. is positive (if we are not at the optimal solution), we can divide both sides of the above inequality by -9. st. leading to the second claim.
C Proof of Proposition 3.1
First, we note that o. 8t gī 8t and ui_ 8, ve 8t. Using the definition of pr in (16), have that
f(zi) - f(x++1) = P: -9, 11
(38)
11
Hence, using the definition of Ô, in (14) and the definition of mec ú in (16), it follows that
x.T 8
x2) ||&
(TTT;)² |
DT b 8.
cos2(
11 2
1 12 & 1
0. 13 2| 0.
5. &
m
Furthermore, have l| ae (x,) - f(xx)) from the definition of in (16). Thus, the equality in (38) can be rewritten as
p. cos2 (0=)) (f(x.) f(x.))
f(x,) f(1+11)
mh
15

---

By rearranging the term in the above equality, we obtain
f12+11) f(x.)) (1 P cos)(0.) (f(at) ((xa)),
(39)
mh
To prove the inequality in (15), note that for any 1, we have
f(x,) - ((x.) f(xo) - (xx))
II ( (2x)
cos² mi
II
p.g.A
f(x)) f(x.)
where the last equality is due to (39). Note that all the terms of the form Pegpn; cos² non-negative, for any i 2 0. Thus, by applying the inequality of arithmetic and geometric means twice, we obtain
vi; are
cos? (0.) mi
cOs (0.)
1 Puiin
i.
m.
i=0
i=U
17
cos2 (0:))
1-1
cos (0:) m
P
1
II
P.gen
m;
2=0
i=0
This completes the proof.
D Results from [38]
In this section, we summarize some results that we use from [38] to establish lower bound on (0.) and 4.-
Proposition D.1 (138, Proposition 2)). Let (Bere20 be the Hessian approximation matrices generated by the BFGS update in (3). For a given weight matrix P E qd recall the weighted vectors defined in (11) and the weighted matrix in (12). Then, have
l1 + log
cos² O
(B+ S (B.) +
Vt 2 0,
Dt 8
my
where mh is defined in (16) and cos (0.) is defined in (14). As corollary, we have,
cos? c0s)(
11:611
log
2 (BB)) +
Σ X
V2 1.
(40)
m
V; 8
If we take exponentiation on both sides of the above incquality (40) in Proposition D.I, we can obtain
a lower bound for the product [ cos (())) with the sum Σ/=
1 and (B().. This classical
8, 81
inequality describing the relationship between the ratio cos)(d)) and the potential function (.) plays a critical role in the following convergence analysis.
In the following two lemmas, we provide bounds on the quantities q and ( ūe respectively by directly citing results from Lemma 4 and Lemma 5 in [38] again. Notice that both dr and || / /8, Dr depend on different choices of the weight matrix
1a.111 Lemma D.2 (138, Lemma 4)). Recall the definition qe = T(.J)J(a..) in (16). Suppose Assump- tions 2, 2.2, and 2.3 hold. Then we have the following results:
(a) If we choose P = LI, then q. 2 2/K.
(b) If we choose (x.), then q. 2 2/(1
Lemma D.3 (138, Lemma 5)). Let f120 be the iterates generated by the BFGS algorithm with inexact line search satisfying (5) and (6). Suppose Assumptions 2.1, 2.2, and 2.3 hold. Then we have the following results:
(a) If we choose P L.T, then 16 < 1.
(b) If we choose P = (2)( then 1rll < + Cr-
16

---

E Proofs in Section
E.1 Proof of Theorem 4.1
Recall that we choose P = L, throughout the proof. Note that given this weight matrix, it can be easily verified that Proposition D.I to obtain
|1 l
1 for any t z 0 by using Lemma D.3 (a). Hence, (40) in
& 9,
cos (o,)
1-1
10:11 8 0s
log
2 (Bo) +
Σ
2 - (Bo).
ms
1
which further implies that
cos
c
((ao)
mi e
Moreover, for the choice P = LI, it can be shown that dt-
2 by using Lemma D.2
L
[2.]]
(a). From Lemma 2.1, we know P:: 2 and fu 2 1 3, which lead to
P.ñ 2 (0.)
(0.)
(2a(1- 3) e cVV(Bo)
II
mi
mi;
i=0
1=0
1=0
1=0
1=0
Thus, it follows from Proposition 3.1 that
17
f(x)) (xx,) f(zo) fxx)) $
P.G.A
p( 20((1 - (3)
II 1=0
cos? cos)((:)
1
my
This completes the proof.
E.2 Proof of Corollary 4.2
Notice that the first case where Bo LI, we have (BB) and thus it achieves the best linear convergence results according to Theorem 4.1. On the other hand, for Bo ,l, have V (Bo) = () = d( - + log I dlog K. We complete the proof by combining these
conditions with the inequality (17) in Theorem 4.1. Notice that e e~ 2 e- N Y/ for 1.
Proofs in Section
F.1 Proof of Proposition 5.1
Recall that we choose the weight matrix P = v2f(z,) throughout the proof. Similar to the proof of Theorem 4.1, we start from the key inequality in (15), but we apply different bounds on the d and
cos2((,) (0.) Specifically, by using Lemma D.3 (b), we have 18 < + C. for any 2 0. Hence, we
(40) in Proposition D.1 obtain
cOs) (Bo) m,
10
log
Σ
1
2 V(BB)
Σ
C₁,
8. fi
1=
which further implies that
cos (0+)
II 0=0
2 c
- C,
(41)
m
Moreover, since qe 2 (1+0,)² for any 2 0 by using Lemma D.2 (b), we get
1-1
II
a
2
2
t-1
e
2C,
2 -
(42)
(1 + C
1=0
==0
17

---

where we use the inequality 1+ r S e" for any 2 E R. From Lemma 2.1, we know P. 2 and
A 3, which lead to
_
I
p.ú, 2 (1 3)
(43)
Combining (41), (42), (43) and (15) from Proposition 3.1, prove that
$7
f(xx) (xx.) f(xo) - (xx))
S 1 II
cos (0.))
<11-20l
(1-2a(1 20(11 - B)e 9(Bo) a 2
Ci
m;
This completes the proof.
F.2 Proof of Theorem 5.2
When we have & 2 (BB) + 3 3/-0 C₁ Proposition 5.1 implies the condition that f(m))-((ar f(a)) S
(I (-)))1-0)) I (1 2a(1-0) which leads to the linear rate in (20). Hence, it is sufficient
to establish an upper bound on Σ C.. Recall that C2
M 1²
v 2(f(())) - f(xx)) defined in (9).
We decompose the sum into two parts: _i=0 [ C and > [i
[B)]] C. For the first part, note that since (1++1) I f(x::) by Lemma 2.1, we also have C++1 I C. for i 2 0. Hence, have
Σ =
[o( C, - Co( &
+ 1). Moreover, by Theorem 4.1, when t 2 v/ (Bo)
we have
f(x)) - f(xx)=
- 11-- (() 20(11 - 3) -
20(1 ()
20 3) t
- 1
f(xo) - f(x,)
eK
3x
Hence, this further implies that
f(x;) f(x,)
20((1
(3) 7
C, Co
Σ
< Co
Σ
V. f(xo)) - f(xx)
3x
i= [B
[=[V(Bo)]
i=|\(Bo]]
20
2a(1 3)
ax11 - 3) -1)
3k
S Co
S Co
36
where we used the fact that Ee (1 p)$ Hence, by combining both inequalities, we have
TTp I-VI-p
vT-p+1-p < p
1
for any P E (0,
3Cox
ΣG
Σ
C++ Σ
G. CDo + a(1 - 3)
(44)
i= [.(
Hence, this proves that (20) is satisfied when 2 (Bp)) 3Co (Bo)
9Cur
all-B)
E33
Proof of Corollary 5.3
For Bo = LI, we have Bo = + B, = and Bo V= - Thus, it holds that (Bo) (1) 0. Moreover, by Assumptions 2.1 and 2.2, have 1 3 f²f(x=)~ = 1 j I, which implies that I = B, 1 wI. Thus, we further have
w(B)) < Tr(n d - log Det(!) = dx d S dr.
Combining these two results, the threshold for transition time can be bounded by T (BB))) 3C, (Bo) + - Con & dr --- Cor. Hence, by Theorem 5.2, the linear rate in (20) is achieved when f. 2 dx at1-3 Cor.
9
18

---

For Bu = μl, we have B, = Σ. B. = I and B = B -V²)()))
Thus, it holds that T/ (B)) VV( (22 d d d dloo I d dllog,. Moreover, by Assumptions 2.1
and 2.2, we have 1 3 Bo I This implies that
v(BB)= - Tr)B)) d - log Det (Bo) S Tr(T) - d log Det( dog k.
Combining these results, the threshold for the transition tume can be bounded by (B)) 3Co V (Bb) + |{(ー)) Con I (1 + 3Cb) d log + a(1- Cok. Hence, by Theorem 5.2, the linear rate in (20) is satisfied when 2 (1 + 3Co) d log K a(1-3) Con.
9
9
G Intermediate Results and Proofs in Section 6
G.1 Intermediate Results
To present result first introduce the following function
w(x) == log (x: + 1);
(45)
which is defined for x > -1. Further In the next result, we present some basic properties of the function (xx) defined in (45).
Lemma G.1. Recall the definition of function w(x) in (45), we have that
(a) (xx) increasing function for x > and decreasing function -1 < x Moreover, (x) 0 for all x -1.
(b) When x 2 O, we have that w(x) 2
2²a
2(++x)
(c) When x S we have that w(x) 2
x²
24
Proof. Notice that w (z) . we know that when æ >> O, w2(x) > 0 and when -1 < w wxxx) <
O, w/ (x) < Therefore, w(x) increasing function for x > and w(x) is decreasing function for -1 < < 0. Hence, wxx 2 w()) 0 for all -.
w(x) > 21+#] is equivalent to w1 (z)
a²
2(1 r)w(r) x² 0. Since w/ (x) 2x
2 log (1 + x) (x) 2 0 for all 11, we know that w/ (x) increasing function for and hence, (I) 2 (0) = 0 for x 0.
w<x)= 2 ² is equivalent to (2) = (2=))==))= 2 0. Since ('(()) = - - log (1 + x) S 0
24z for all - 1. we know that (z) is decreasing function for æ > -1 and hence, (2 > (2 (0)
for x 0.
Proposition G.2. Let (Bihr0 be the Hessian approximation matrices generated by the BFGS update in (3), Suppose Assumptions 2. 2.2, and 2.3 hold and (x++1) S (xx) for any 1 2 0. Recall the definition of (.) in (10) and C, in (9), we have that
1-1
Σ w( - 1) < BB) + 1=0
+2 Co
W 2 1,
(46)
2=0
Proof. First, taking the trace and determinant on both sides of the equation (13) for any weight matrix P E 84 and using results from Lemma 6.2 of [34], we show that
|1, 87 B,s,
87 Dt
Det B+T1) = Det(D (B.)
8, Dr
$ B
Taking the logarithm on both sides of the second equation, we obtain that
8T 1t log Det(B log Det Det(
log
$J B,
19

---

Thus, we obtain that
w (Bc+1) - ((BB)= = -T((B++1)-Tr(b + log Det(Br - log Det Det(B(+1)
11 11
|B log
87 Dt
|
8/ 1/2
||
log
log
8 Øt
86 BiSt
8, Bi
8, Ut
87 B
|
8: B
which leads to
B₁ 11
87 BB&
||
||
log
1- -1=V(B,) (B++1) +
+ log
8 B,
||
8, Øt
3 gt
Notice that Byst -1 87 By
n1.6. de and 1|8,11 1/2 l1ded |1? we have that
19:11
-g. de
11 11
|| 1
log
- -V(B.) 1 (Bett)) +
1 + log
- de
||de|12
8f 5t
3, 0r
Note that given the fact that - -e d; 3. TT,,B,B, ge > 0. by using the Cauchy-Schwarz inequality we
11 - =.
a. di Hence, we can write
obtain
2
ddll
-. de
-T,dd - s (BB) ((B+1)) +
1 1 +
|| 12
log
log
|1de|12
||d.|1
87 0t
Úc
Now, by selecting the weight matrix as P (xx)) many expressions get simplified and we have 0. di
9." d, Pe, Pt - log Pt 1 w(p: - 1). and B, B, v2 - ((x))))))
|| d.11
Hence, we have
1 + log
||&
w(p 1) vB)B) - V (B.+1) +
(47)
3. Út
3. ÿt
Notice that
16e1 8, 91
< 1 + Ct for any 2 0 by using Lemma D.3 (b) with P = f2 and
|| < log(1 + C.) S C2 for any 1 2 0 by using (31) from Lemma A.I. 87 J,&, Leveraging these conditions with the inequality (47), we obtain that
log |1:.1
log
27 de
w(p: - 1) s (B.) v (B++1) + 2C2. Summing both sides of the above inequality from to 1, we prove the conclusion
h-1 Eipp: - 1) (BB) (BBB) +2 > C s (B)) + E.. C
1-1
1-1
where the last inequality holds since v (B.) 2 0.
Lemma G.3. Suppose Assumptions 2.1, 2.2, and 2.3 hold and C Σ 6 and Ps 2 at iteration f, then have
f(i, + de) S f(t)).
(48)
Proof.
Since assumption 2.3 hold, using Lemma 1.2.4 in [44], we have that
1 (v- x) V²)(((() x) s M (v()) f(x)- - Vf(x) (y- x) x)-
lly xl13,
Vr, E Rd.
6
Setting x = It and = It + de, we have that
f(x + d.) f(xx) s of de + 24 S M
||de
(49)
Notice that using (33) from Lemma A.1 and the definition of P: in (21). we have that
||de 12
1+C,
-.. df v2 f(x,)d < (1 + C.)d f(x.)d = -g d6 C.)
Dr. d.
(50)
_ de
20

---

Applying Assumption 2.1 with the definition d, = (1r.) jd we obtain that
1 #
-90 de
| 1?2
-9 de
1
||dl|
|d:11
||del|
|d
11
16 de
1 pt
Since - de < || by Cauchy- Schwarz incquality where Gr = 42 f(xz)
ge. we obtain
|
||de||
|d
llãel
l|gell
- 1l
9t de
Pt
which leads to By applying Taylor's theorem with Lagrange remainder, there exists Ft [0. 1] such that
D.
de
91 de μ² p
||d <
|
l@xll-
(51)
a Pt.
1
f(x)) = f(x.) + fx(x,)) (xt x.) +
2 7 x,) =T.T²² V2 + Fe(x, xx)) - Ix)
(52)
= f(x)) +
2 (It - x.) V f + fz. - x1)) - =x,,,
where used the fact that fxx)) O in the last equality. Moreover, by the fundamental theorem of calculus, we have
| 42 f(x + T(x. xx))({== xx) dr = Ge(a: - -x"),
f(m))-
where we use the definition of Gr in (8). Since VS(x.) 0 and we denote gr = V((z)), this further implies that
It - x. = (VS(c)) v((())) G. gc.
(53)
Combining (52) and (53) leads to
f(x,) - f(x.) 79 G.- (-'12f(a + ft(x. - xz Go
(54)
Based on (35) Lemma A.1, have V2 ffr + ( x1) - I Gr which implies that
G. V + fr( - G1))GT 2 1 C. G.
Moreover, it follows from (34) in Lemma A.1 that G, (1+ (1) which implies that
1 [+
G.
Combining the above two conditions, we obtain that
G. V22 [(x + Fr - GT
+ C.j² (V'I(x.))
and hence
96 G + (x. Gz)) g:
(1 + C. T (V*I(x))) -'g.
1 10. (55)
(1+ C.j2
Combining (54) and (55) leads
||ăx|| S (1+
(56)
Combining (51) and (56) leads to
9. d,
9. - de 1
|del|
9g
<
(1 (L+G))v(f(a))
(57)
1
n p
21

---

Leveraging (49), (50) and (57) with the definition of C2 in (9), we have that
1 di
V2 ((: )d + M
f(x d,) f(xx) - 9.d4 de
|ddell
C+C
M 1
de(-1+ del-d
(1 + Ct) ((f(z)))))))))))))))) f(xx)))
(58)
2pr
6 # Pi
C
1+ C2
C.(1 + CC)
- del-111
2pt
6p
Notice that -6 de Ii Br gt
> 0 and when C₁ and Pt 2 z. we can verify that
1 C.
C((1+CL)
+
ipž 1.
2pc
Therefore, (58) implies the conclusion that
[(x+ de) (1x)) < O.
G.2 Proof Lemma 6.1
Since 7 = 1 satisfies Armijo Wolfe conditions, we know that 73. is chosen to be one at iteration and It-1 + de. We have f(++11 I faz) from Lemma 2.1. Using Taylor's expansion, have
that ((*++1) (xx) + de de + 2dl V f(x + f(x++1 =x)),,, where + E [0, I]. Hence, we have that
f(x1)= - f(11+1) = - de - 1/2/ 2 f(x + f(11+1 - x())
Pt
Di de
-t de
1 d, fxx f(1111111//1/111 - 21
1
C+C, d, f(..)d
1 + C.
2
Dt de
2
-6 de
2pt
where we apply the (32) from Lemma A.I since f(x++1) S f (xr) and recall the definition of in (21). Similarly, using (31) from Lemma A.1 since f(r(+1) S f(1t), we have that
3/2 8t 2f J.St Jedk 2 I+C, -9. d,
d, 2 fxx))e
ig
91
g. St
- de
(1 + Cc)pi'
where the fact that Ve J.S, with J, defined in (8) and 8, Je+1 prove the conclusions.
34 de. Therefore,
G.3 Proof Lemma 6.2
Denote T++1 = Dt + d, and & = 5t+1 - 21 = de. Since o1 S f f(x)) from Lemma G.3. Using Taylor's expansion, we have that f(ā(+1) = f(z)) + g. de d f2 + f(ā+41 - 2z,),,, where & E [0, 1]. Hence, we have
1 and 82 2 8. we have f(T+11) S 6
7
(xx)) f(x++1) -9, de 1 f2 + f(ā++1 - =re)d
41 de
91 d:
d, V2 (xz + 7 f(Tr+1 xz 2 1+C C. di 42 V2
1+ C.
16 de
2
- de
2p:
where we apply the (32) from Lemma A.I since f(3++1) f(x). Therefore, when C. 81 5 /2(1 - a) and P: 2 82 2
V2(1-a) we obtain that ((82)1( > 1+C. 2 a and unit
2.
step size = satisfies the sufficient condition (5).
Similarly, using (31) from Lemma A.I since f(1(+1) f(x)) and denote ge+1 vf((t-1).
Ht = 0k+1 - 9t. we have that
y. 5t
3. J1St
d. Jjd
1
d. 2 f(
1
2
9t 5t
81
91 de
1 +
Ct
91 de
(1 + C.)p:
22

---

- Therefore, when C. 56 - v and Pt S dg v--Ø we obtain that 01 2 (1+ 2
1 8. which indicates that 9. --1d 9 13 v. 8, + 9: s, - -9 5, 3)+ g. 8t 3g. 8 3g,
d, dg. Hence, unit step size 1h: = satisfies the curvature condition (6). Therefore, we prove that when C2 < 61 and 82 S Pt S d3. step size 7): satisfies the Armijo-Wolfe conditions (5) and (6).
G.4 Proof of Lemma 6.3
Since in Theorem 4.1, we already prove that
f(x)) f(x.) f(xo) - f(x,)
- 1 1-e- v(Bn) 20(1 (9)
This implies that
Ci s (1-6 ocBal 20(1 3) $
Co.
When / 2 (BB),,, we obtain that
2a(1 53 )
$
C2 S
Co.
3x
When 2 3x a(1-3) bj
log Ca
we obtain that
G S (1
20(1 23)
Co Sn
366
Therefore, the first claim in (24) follows.
Now define I {t Pt 82) and 12 {t : Pt 5z}. we know that [ 44
[2]
Notice that for t E I1, we have that Pt - 1 < 82 - 1 < 0 since 82 < and the function ((x) defined in (45) is decreasing for -1 < 2 < from (a) in Lemma G.I. Hence, we have that
Eie,, w(p: - 1) 2 Σ w(62 - 1) = w(2 - -/) Similarly, we have that for t E 72, we have
that P: - 1 > 8g- 1 > since dg > 1 and the function w(x) is increasing for x > O from (a) in Lemma G.1. Hence, we have that Eiet, w(p: - 1) Eiet, w(6g - 1) (6g 12) Using (46)
from Proposition G.2, we have that El= (pp - 1) - (BB)) + D C. & 1 (B.) + 2 ~ C; for any t 2 1. Therefore, we obtain that
400
(Bb) +
Σ 1=0
C. 2 Σ
w(p: 1)> Σ
w(B: 1) + Σ w(3 - 1)
1=0
ich
El19
2 w(d2 1)/4| + w(ds 1)1121 > min w), 1) + (12)),
which leads the result
VB + 2 C, = d2 (v(Bb) + + C₁
to0
[ = 17l + T2l <
(59)
min ( 1), (6; 1)}
1=0
where d4 fin -1] Using the upper bound of Σt C. < CoV (113)
3COx
in
(44), we prove the second claim in (25).
G.5 Proof of Theorem 6.4
First, we prove that for any initial point zo E Rdd and any initial Hessian approximation matrix Bu E sd the following result holds:
f(x)) fxx)) < f(00) - f(x))
8oto + (BB) + 88 Ei=o
+00 Ci ):
vt > to.
23

---

where to is defined in (24). We choose the weight matrix as P fax)) throughout the proof.
Using results (41) and (42) from the proof of Proposition 5.1, we obtain that
(0.)
c (BB)- C. - C.
(60)
m
1-1
II
q: 2 20-2-222220 -i Ci 22' 2'e-- C:
(61)
i=0
Recall the definition of the set {t: Pt $ 16 d21) Notice that for 2 lo. define 13 {t: t2 to, Ps & [82, o and 1
= {t: t 2 to, Pt E [d2, da]}. Then, we have that
1-1
f--1
1-1
4-1
II i=0
P:
II
p.
II p.u.
II p. II Ar..
(62)
O=0
i=to
2=
iETs
RET
From Lemma 2.1, we know Pe 2 a and n4 2 1 - 33 for any 2 O, which lead to
tg 1
II
pan 2 a (1 - -3) 2t e to log za(i-3)
1
(63)
t=
Il iEls
>
II
a(1 B)
1/a log vallーp
1
1| log 2
2|1s|
2/4a|
iElg
(64)
1 & (v C:) log 2a(1-10
2/1s
where the second inequality holds since [//| I |/] log 2n(1-a] and the last inequality holds since (59) from the proof of Lemma 6.3 Appendix G.4. Notice that when index E /4, we have
C S 81 from Lemma 6.3 and Pi E [82, 63]. Applying Lemma 6.1 and Lemma 6.2, we know that for satisfies the Armijo Wolfe conditions (5), (6) and we have p. 2 1+G > 0 (since
i E I4, m
2p.
C. < 81 S 2. p.
2 52 N
and h4 2 [++C
from (22). Hence, we obtain that
II
p:n N
24
II
22-
1+C, C.
Ps
+ C.)ps
1
2 1 Eier, C. II (2
2
1 1 C;
Pi
Pi
(65)
HET4
SEL
EE
where the last inequality holds since
1+c, 2 c Using the fact that log 2
we obtain
x²
II NE
1+ C2
1 Ps
II iET4
log (2- 1+0 -
log Ps
Pi
4E4
II
P1-1-C, 11
-log
II
201
ie4
IE
(66)
II iET4
-(p;-1)+2[
Apt 1-
m.)) los -1pp:---1-lap (1
II iE4
-2 1) -1 P,3 2p4
II iEL
2ic, lox 1: 1a 10
2p: 1p:-1-0;
II SEA
2(p,-1) (1
where the second inequality holds since (pp: 1) > 0 and the third inequality holds since p; 82
due to E I4 and C; S 82 due to 2 to and Lemma 6.3. Notice that 2p; - - C. 2 26 1 81 > 0
for all E I4 since C; < 6, I _ and p. 2 62 2 I.
When p 2 1. using log ps S p: (b) in Lemma G.1 and p; S 83 due i I4, we have that
(p: - 1) log Pi S (p: - 1)2 < 2pra(px - 1) < 25z - 1). Similarly, when A < 1, using log p; 1
(67)
1, p.:
(c) in Lemma G.1 and Ps 2 82 due to i I4, we have
(p. - 1) log < (p) - 1)2
P: +
(pp - 1) - (1+ 82
ww(p - 1).
(68)
Pi
Pi
24

---

Combining (66), (67) and (68), we obtain that
1 C.
1
II (2
Px
Pi
1
II
62)
(1-lop
2
28g 11
e
$1
252 122-1-8
iEl
iE /4
2(p log
los
(1-log C2]
26g -1-11
262
262 162-1-51
1
iEL
(69)
211 by 10
282-1-61
202
II IE4
e
262-1-2
lox &
e 25
24
oo Eichg (pp (----1) 11- 26
4g L Lichp w(pi 1)
202
1 of Diere C.
e
(Eicli w(p 11+ 2 u(p:-11)
282-1-1
loxb,
Lies C.
Eiet w(p= 1) 282 1 Cier C.
where 65- m
2+
46
}. Combining (65) and (69), obtain that
26
20
26.
II RE
p.ù 2 2/41
Exer II (2
1 Ci
Ps
iEL
56 Eier w(n 11)-(1+
81 Eiel
2 2 2/41
(70)
26 do Σt w(p--1-
262-1-61 Σ+z Ci
2 244
1 -bs
(v(Bo)+2 c:)
_ -og
1-----1
Ens C₁
2
where the last inequality due to (46) from Lemma G.1. Combining (62), (63), (64) and (70), we obtain that
to
p.n.
=
p.ù
1I p.n;
Il p...
1
0=
KE4
(71)
to log
aoci-ay (64 log
andi-m (Bo) log 2oci-oy 101---y-265 +26
26g -1o00
262-1 -100 Etoo C:
2 e
Leveraging (60), (61), (71) with (15) from Proposition 3.1, we prove that
[ YT-
| II
f(x)) - f(xx)
p.q.n, cos?(
cos? (0.))
f(xo) - f(I)) 1 - [I
m,
myg
1 2ari-a 8) +1448 log 2ori-er (9) + (33228
20ri-o1 of +25g 26g
2
o2
S6lo (o)) D0 Ci
Snto + B,V((BB) + Sn t C.
-- 1-e
t
where the inequality is due the fact that Theorem 6.4. Hence, we prove that
-- < x for any x R and de 67. 8g are defined in
f(x)) fxxx) < f(00) - f(xx)
1ō60 + (BB) 8z +00 Ci )
vt to
(72)
25

---

Using (44) from the proof of Theorem 5.2 in Appendix F.2, we have that
3Con
Σ
C. S (B) + a(1 - 3)
(73)
==
Notice that from (24) in Lemma 6.3, we have that
3x
Co
3k
Co
to = max max(Uu(o),
log
S (Bo) + a(1 - 3) 81
log
(74)
a(l - 81
Leveraging (72), (73) and (74), we prove the conclusion.
G.6 Proof of Corollary 6.5
Using the fact that for Bo LI, we have (Ba) = and (B)) I ds, and for the case that Bo μl, have v (Bo) I d log and (Bo) I d log obtain the corresponding superlinear results for these two conditions.
G.7 Specific Values of {6.]
As we stated before, all the {8 are universal constants that only depend on line search parameters and B. We can choose specific values of and / to make definitions of {6, } more clear. If
pick t/2 and 3 I. we have that
7
61
82
53
2,
84
118,
6s 14, 66 log
57 =200,
6g 524.
8
H Complexity of BFGS with the Initialization By = cl
Recall that [u, L] by our choice of e in Remark 6.2. If choose By cl, then (B (G+T) = fd d dog L Moreover, we have V (B)) = (c.))((a))))) d log (x.,)
which is determined by the Hessian matrix f2, In this case,
one can use the upper bounds V V/( (B))= = d(f - + log -) and vo = Tr(cV2 (xx))
log Det(cV3 fxx)) d(
log () to simplify the expressions.
Applying these values of (B and & (Bo) to our linear convergence result in Theorem 4.1 and the superlinear convergence result in Theorem 6.4, for Bg = cI:
obtain the following convergence guarantees
For t 2 d(i + log 5), we have f(xx)-f(x, < 5(1 20 2a(1-9)) 1(x0)
3x
For L = S(d - + log +) + Cod(f 1 + log ( + Cor), we have f(x))) f(r.)
S
(0 -( )+ 1og 4)+Go=))'
Moreover, derive similar iteration complexity bounds following the arguments in Section I. We also include the performance of BFGS with Bo = cl in our numerical experiments as presented Figure 1. We observe that the performance of BFGS with Bo cl is very similar the convergence curve of BFGS with Bo = ul in our numerical experiments.
I Proof of Iteration Complexity
When Bg LL. if we regard the line search parameters a and 3 as absolute constants, the first result
established in Corollary 4.2 leads to a global complexity of OK log L), which is on par with gradient descent. Moreover, the first result in Corollary 5.3 implies a complexity of O ((d + Co) + log !), where the first term represents the number of iterations required to attain the linear rate in (20), and the second term represents the additional number of iterations needed to achieve the desired accuracy
26

---

from the condition number-independerr linear rate. For the analysis of the superlinear convergence rate, we denote that Qz dx Co.. From the first result in Corollary 6.5, we have that
f(xx) - f(x.) f( - (x,))
S Pre
Let T, be the number such that the incquality (Lx S above becomes equality. we have
1 = T. log log
T.
< T. T.
1),
Ut
Qr.
Qr. + V 12.
+ 452,. log
T. 2
2
Hence, we have that
T. f2
2t + V 07 + 4 f log
log
log = T. log
2 T, log
2 T. log
2 +
282r.
log
T. S
log
log
+
Hence, reach the accuracy of need the number of iterations to be at least
log
t
log
V
1
1 log
D2g
Therefore, the iteration complexity for the case of Bo = Ll is
1 ( min log :. (d Co)x + log c' log + du Con log 1)
log
Similarly, in this case of Bo - ull the second result in Corollary 4.2 establishes a global complexity of O (dlog log 2), where the first term represents the number of iterations before the línear convergence rate in (19) begins, and the second term arises from the linear rate itself. Addition- ally, following the same argument, the second result in Corollary 5.3 indicates a complexity of OCCnd log K + Cox + log 2). Here, the first term accounts for the wait time until the convergence rate takes effect, and the second term is associated with the condition indeeerindeeenneent linear rate. For the superlinear convergence rate, when Bg μI, to reach the accuracy of c, we need the number of iterations to be at least
log 1
log
+ 4
1 1 + Q2
log
where 22 Cyd log + Cok. The proof is the same as the proof for the case of Bg LI. Therefore, the iteration complexity for the case of Bo = uI is
o min dlog x #log - Co(dlog 1t) log ? log {min
1
log
1 +
log
Co
xtx)
J Log Bisection Algorithm for Weak Wolfe Conditions
27

---

Algorithm Log Bisection Algorithm for Weak Wolfe Conditions
Require: Initial step size (0) 1, Mmii 0, Tmme +00
1: for = 0, 0,2, do
2: if' f(z, + +n 1 di) > f(zz) an) (xx)) de then
Set (i+1)
(7))) and Menin (1)
3:
Mmin
4:
if Minn then
n = ( )
5:
6:
else
7:
nf(+t1) V
Amar Amin
(i-1) (++1)
8:
end if
9:
else if Va(x + 17 d.) de < <()(( de then
10:
Set Mmaa Mman and Umsn r/
(i+1)
(6+1)
(8)
11:
if Mina = to0 then
r 2
12:
13:
else
(/(+1) = v (imml (6+1)
14:
Umin
15: end if
else
17: Return v7(1)
18: end if
19:
end for
K Results and Discussion on the Bisection Scheme for Line Search in
Section 7
K.1 Proof of Lemma K.1
First, we present major results concerning the complexity of the bisection method, which specifies range of values that meet the conditions in (5) and (6).
Lemma K.1. Suppose that Assumptions 2. 2.2 and 2.3 hold. Recall the definition of Pt in (21)
and C2 in (9), At iteration there is unique fr > 0 such that the sufficient decrease condition (5) is equity for Ups ie.,
f(x 1, fxx) on, on. (xx)) de.
(75)
Then, Th satisfies the sufficient decrease condition (5) if and only if mr We also have that
2(1 a)
1 C. P: S 2 a1 C.)pt
(76)
Similarly, there is also unique > O such that the curvature condition (6) is equity for i.e.,
Vf(r, + mide) d, = [V de.
(77)
Then, nr. satisfies the curvature condition (6) if and only if m: 2 mh Moreover, we have that
Tr 1 (1 (1 + 2C2)
8
1.
(78)
Proof. Notice that Assumption 2.1 indicates that the objective function f(x) is strongly convex.
Consider function (n( f(x, + 7d4) an fxx)) dr. We observe that this function h (n) strongly convex and (0) = f(x,), M (0) < 0. Hence, there is unique Tr > O such that bn (n=) f(xx) and I if and only if [xx, + m.d) S f(xx) + oo.. (xx)) dr.
Denote that Ft+1 = It + d. We know that (*++ (xx)) = an.g de. Since ((F41)
ne + 1 4 f T(#411 Iz))d, for + E (0, 1), have that
n.g. de + V2 + 7(541 xx))d an.g. de,
28

---

g d.
7/- = 2(1 -a)
v2 (4 + 7 (T++1 - rz))d.
which leads
0/ de
- 9 de d, (2f(xx)
Th = 2(1 -x) (x)
S 2 ao)1 + Ct)
de (xr + [ - Iz))d
91 de
= =1)1- C,)
= 2(( -1) + C:)pr.
|d.112
9t de
2(1 aa) a)
-. de 1+ di (z.(dd
2(1 -a) a)
7 2(1 - a) di f2
T - xe))
1 1 C. Pc.
where we use the (32) from Lemma A.I and the fact that f(ā+41) = f(z+) + anggt de S f(x)). Hence, we prove the results in (76).
Similarly, consider function h22 = ff(z + nds) d. We observe that this function h2(1) is strictly increasing function for 17 2 0 and h²(()) ff(z)) de < fxx) de, he((ezact) = f1(r + (e) de = 0 /V (ax) Td, where Bexxct = arg min (ar + syde) is the exact line search step size satisfying [ + "eeraadh)) d, O. Hence, there is unique vn (0, Heract) such that (2 = fxx) de and 1): 2 m if and only if V ff(x= + mede) de 2 3V fx:)) de.
Notice that
Mat + m,)) = (xx) + an, an (M)) dd.
Using mean value theorem, we know there exists 1j E (0, m-) such that
f(r + n. = fxx) + 7, V f (.z + rdde) T de.
The above two equities indicates that
ff + rd))) d: a f de
Recall that
V f(a + n)d)" de = BV (xxt T dr. T
Combing the above two equities, we obtain that
(Vf(r, + ndd)- - ff(z, + m)d)) de = (zx(() d4 a). Using mean value theorem again, we know there exists ij E (n, π) such that
(v + nd.)) - ff + m)d,)) d = (īj - m dd V2 f(x, + rd,))d.
Leveraging the above two equities, we obtain that
VF(t)) de
- = (3 a) d3 VV2((z + yd
Notice that 7 S Tr. we have that
Vf de
T T 2 7- Tp (B a) dj V2 f + ddde)de
(79)
Recall the definition of np in (77), we have that
(v + m)d) - vf(x))) de = -(1 f(x)) dr.
Notice that there exists i E m)), such that
(Vf(z, + md) V (xx)) de = mid f2x( + ndd)dd.
Combing the above two equities, we obtain that
-1 (V de
m = di V= + fdd
(80)
29

---

Leveraging (79) and (80), we have that
7r 1 m Grr 1
(3 - addd V2 f(z + rydidde
111
(1 - 3)d, V2 f2r +
Recall that Zt+1 = 2t + n, and notice that of S fr. ń I Dr- We have that 2t + ryde = 2t f(Fc-1 - ze) and xe + rjde = It + f( - 1x) with
_ E (0, 1) and - E (0, 1). Since
f(ā(+1) = f(x + mrdd)) = fx)) + am, V f(z)) de & f(x)). applying (36) in Lemma A.I, we prove the conclusion that
(3 a) ] V2f f(z; idd
Tr 2 1
(1 - 3)d, fz, + rjde)ds
= 1 ++ (3 add V f(x + +f - 21]]d
21+ 3-a a (1- B) 20,)
B)d, v f(2 *(Fx+1 xx])d
K.2 Bound on the Number of Inner Loops
Proposition K.2. Suppose that Assumptions 2. 2.2 and 2.3 hold. Consider the BFGS method with inexact line search defined in (5) and (6) and we choose the step size Tr. according to Algorithm 1. Ar iteration I, denote de as the number of loops in Algorithum to terminate and return the тt satisfying the Wolfe conditions (5) and (6). Then da is finite and upper bounded by
A 2 12+10g log2 (1+ (1 - (1 + 2C₂))
8-a a
(81)
+ loga (1 + logz (2(1- (1 + Ct)) + max(1ogg Pt, loga P: 1
Proof. At the first iteration, if (0) satisfies the weak Wolfe conditions (5) and (6), the algorithm terminates and returns the unit step size = 1. In this case, we have that X = 1.
Suppose that the first iteration, 17 doesn't it satisfy the sufficient decrease condition (5) but satisfies the curvature condition (6), we have that Tymas = +oo, 7min = 1 and r7 = 2. Assume returns. This
(4) that in the Algorithm 1, Mmaz is never set to finite value and the algorithm means that the condition in line 2 is never satisfied, and as a result, we keep repeating steps in line 12. Thus, 17(6) = 22' -1 and since the condition in line 2 is never satisfied, we always have that f(x, + 1d) S f(x + ( ( dr. Notice that lim;- 17 + +oo and V (xx) de < O. We obtain that lim fxx + ( dz) + -00, which is contradiction since f is strongly convex.
fxx)
Hence, at some point, either the algorithm finds an admissible step size and returns, or Timaz must become finite. Suppose that this happens iteration K; 2 of the loop Algorithm 1. Then, we know that r/(K,) returns Ki, k satisfies the Armijo Armijo-Wolfe Wolfe conditions and therefore 7 I dr- Using the upper bound result in (76) from Lemma K.1, we obtain that vy (Ka) 2221- -1 S fr S 2(1 a) C.)pt.
2 In the first case that the algorithm finds an admissible step size and
which leads to
K1 < log2 (1 + logg (2(1 a)(1 C.)p:))
A
(82)
In the second case that maaz becomes finite but the algorithm does not terminate, we have that -1) satisfies the sufficient condition (5) and rf (K,-)) S f)- Similarly, this implies that
K, < 1 + log2 (1+ log, (2(1 a1 + C.)p)))
(83)
Then, we further go through the log bisection process. Notice that for any iteration i i> K1, the sequence 1 is finite and non-increasing and the sequence n 1 and non-decreasing. The log bisection process indicates that
(6)
log2
Mmar
log2
Tinaz
Vi Ki.
(84)
(1-1)
2
1min
Uman
30

---

The Algorithm implies that for any i > K1, we have that
f0t + I de) (1x) orr V (xxe) de,
(6) Vflzz + mmin di) d de < < dd.
Hence, we know that for any i > K1, Mmar 2 7) and 7min I where fr, it are defined in (75), (77) from Lemma K.1. Therefore, using result (78) from Lemma K.I, we have that for any j 2 1,
(k++))
Amazz
The > 0.
log2
2 log2
(85)
(k1+))
Amsn
mp
Notice that (84) implies that
(Ki-)) -)
(K,+1)
Mmna
Amaa
log2
log2 (K, [K++1) +1]
(86)
(K1- (K--))
2
Mmnn
Mmén
which leads to 0 = lim 20 log2
Donk
+1)
limy-++ss log2
Poggi A
log2
Dr > 0. This is a m
Tmnn [K++1]
contradiction. Hence, Algorithm must terminate after finite number of loops. Now suppose that Algorithm terminates after K1 + + iterations, (85) and (86) indicate that when 11 2 1, we have
(k++1)
(K++Fi)
1
log2
Timaa
(Ki+1) log2 Umi
Jmna
2 logz
B-a Th loga (1+ [++11 (1 31(3)((11 +C2)
(87)
2
Mmin
(K)+
m
where the last inequality holds since (78) in Lemma K.I. Notice that mhaa (ki+t)) = 22% and
Kr+1
22 Hence, we obtain that
(K++1)
logg (K,+1) Mmnn
Mmaa
2K:-1
S 1 + loga a)(1-a) + Ct)p.).
(88)
Combing (87), (88) and using log x 2 4. we have that
8 8-6
Ti < loga
+ (1 + loga (2(1-a)1++ C:)p:)
-log2 log2
1
(1- (3)(1 + 20,)
B --a
< 1 + logg [ + logz (2(1-a)(1 + C.lp.) - log2 log
1 +
(1 (3) + 202)
(89)
(1 + logg (2(1 - a) + +.))))) log2 (1-
$ + loga
1
3-a
(1 (1=00()+20.)
(1 - 3) + +20,)
= + +oga
(1 loga (2(1-
- a)(( a))1 + Ct)):) + logz
1
B 8-0
Leveraging (83) and (89), we prove that
A = +1
+ (1 (1+ loga (2(1-a) a)] ([1=)a((+C))p)) loga (1+ (1 - 3)( 2C1) B a a
(90)
Similarly, suppose that the first iteration, 17 satisfies the sufficient decrease condition (5) but doesn't satisfy the curvature condition (6), we have that mmaaz = 1, 7mmn = and r7 = 2- Assume that in the Algorithm 1, .mm never set to positive value and the algorithm never returns. This means that the condition in line 2 is always satisfied, and as result, we keep repeating steps in line 5. Thus, (8 = 21)= and since the condition in line is always satisfied, we have that f(z + ( > f(x.) + am (1) f=z)) de. Therefore, we know that (7()) 2 7/ where т₁- > is defined in (75) from Lemma K. Notice that ()()) 2 Tr for any and lim (7 = 0, this leads to a contradiction.
Hence, some point either the algorithm returns step size satisfying the weak Wolfe conditions or Imi must become positive. Suppose that this happens at iteration K₂ 2 1 the loop in Algorithm 1.
Then, we know that (K2) ( (
31

---

In the first case that the algorithm finds an admissible step size and returns 17 17* 17 satisfies the Armijo-Woll Wolfe conditions and therefore 17 K² S f/. Using the upper bound result (76) from
Lemma K.1, we obtain that (/(a) = -2 1 1r - 2(1 - (1 + Cs)ps, which leads to
A = Kg S log2 (1 + log2 (2(1 - a) + C))):)
(91)
In the second case that Uman becomes positive but the algorithm does not terminate, we have that of (K22-)) doesn't 't satisfy the sufficient condition (5) and ()(221)) 2 Dr. Using the lower bound result
2(1-a) in (76) from Lemma K.1, we obtain that 17 (K=-))) (2) 2 2-222-1-- 1/r I+0, Pt. which leads to
K2 S 1 + log2 (1 + log2 2(1 - a
1+ C+
(92)
Then, we further go through the log bisection process. Using the same techniques, we can assume that Algorithm terminates after K₂ + T2 iterations, where r32 2 1 satisfies that
(K2+1)
(K2+T2)
"r > loga (1 (1 - 3) + +Ct))
B-a
2 log2
(k2+1) = loog (K2+T22
2 logg
(93)
Amin
7min
q
where the last inequality holds since (78) in Lemma K.1. Notice that ymmas
(k2+11)
= (1) (1) and
K2+1 (2)2 Hence, obtain that
Tmmnn
(K2+1)
log2
Tiaaz
2k2-1 5 log2 2(1 a)pt
C+
(94)
(k2+1)
Umin
Combing (93), (94) and using log x 2 1- 1, we have that
1 Ct
3 - a [1 - 8) + 2C,)
I2 S 1 + log2
[ + log2
-log2 log2
1 +
2(1 a)p:
< 1 + loga
1 log2
2(1 a)pt )
-a)pp/
C.
-log log
(1
+
[1 - B)( + 20t)
3 a
1 C.
) logg (1
1
(95)
< 1 + log2
[ + logz
2(1 a)pt
1 + B-o
(1-1)[1+205)
1 C.
[1+ (1 B3 + +201)
= 1 + logg
[1 log2
+ log2
2(1 a)pp
3 - a
Leveraging (92) and (95), we prove that
A K2 + +1
< 2 + 2 log2
(1 loga
2(1 - pppp + loga (1 (1 B) + 2C,)
1+ C.
(96)
8 3-a a
Notice that < 1/2 and thus a[1 < 2(1 (x), combining (82), (90), (91) and (96), we prove the final conclusion
(1 (1 (1- (-)())+12))) 2Ct))
A S 2 1 logz
3-a
(1 + 1og, (2(1- -1--0 (1) + C:)) + max(log2 Pe, logg 1
+ 2 logg
K.3 Proof of Theorem 7.1
Using result from Proposition K.2, we have that
loge (1+ (1 (1-3)(1 + 2C,)
A
X
2+
3 3-a a
1=0
(97)
2 1-1
log2 (1 + logg (2(1-a) + +ca) + max(log, Pi, logg pr. 1
+
7 1=0
32

---

Using Jensen's 's inequality, we have that
1
log2 (1 (1- (1] + < log2 (1+ 1-
2(1 3)
E
Ci
3 +
(98)
3-a
B - a
t
1=0
log2 (1 1og2 (2(1- aa)(1 + Ci)) + max Ps; log2
1)
Pi
i=0
( log, 2(1-a)= 1 Σ
-11
< logz
logz(1 (1 + C2)
max Ps. log2 Pi
(99)
1=0
Ei Ci
1
S sogg
(1+
loga log,
a1) 1og2 (1
+
log Pss log2 ps
We also have that
1
max (loga Pi: log2
loga Pi
+
Σ
log2
Pi
Pi
==,,s
1-1
1
log2 Pi
+
+ log2 Ps
log2
+
log2
(100)
t
t <
Pi
Pi
2=
==0,1pp:22
2
Σ
loge Pi
loge
1
Pi
22
where the inequality is due to log2 Pi I 1 for Pi < 2 and loga 1 < 1 for Pi > of w and (b) in Lemma G.I, we obtain that
1
Using the definition
2.
logg e t 0,222
t-1
log loga Σ (p--1 1 w(ps - 1))
1-1
loga Ps
2222
logg e
2p: w(ps 1) w(p 1))
(101)
e=0,pp2 Ps
log, e
Pi +
w(pi - 1) <
3 3log2 e
Σ
h-1
w(p: 1).
1
i=0.p:2 Pi
Similarly, using (c) in Lemma G.I, we obtain that
1
loga
log2 e
log
1 logg e
Σ
(w(p: - +1 -1 ph)
t
P:
t
Pi
t
logae e
Σ
(w(p: - 1
+
1 Pi (p: - 1))
(102)
1- Pi
log2 e
1-1
2 w(p; 1) 5 4log e
t-1
Σ
w(ps - 1).
t
1- Ps
t
1=
Combining (100), (101) and (102), we prove that
max Pú, log,
-
1 } 2
Σ
loga Pi +
log2 1
Pi
Pi
1=
:=0,p;2
(103)
4log2
1-1
1-1
< +
Σ
w(p - 1) 52+
7
V (B)) +2 Σ
C.).
1=0
1=0
33

---

where we use the fact that w(p; 1) 2 0 for any 2 0 and the last inequality is due to (46) in Proposition G.2. Leveraging (97), (98), (99) and (103), we have that
A₂ S 2 + log2 (1
1 1- 3 +
2(1 B) E C.
3-a
B a
+ 2 2oog
3 + logg 2(1 a) loga (1 +1+ 2i=0 Ci
6 + (Bo)
+2 E..))
==0
+1 1-3 +
2( - B] Ei Ci)
1 2 + log2
3-a
B
logg 16(1 a) loga (L + EED
6V (Bo + 12 E/0 Co
+ 2ogg
We prove the final conclusion using (44) from the proof of Theorem 5.2 in Appendix F.2, i.c.,
Σ
[-
Co + 3CON
c S
a(1 ((1-80 B)
20
K.4 Corollaries of Theorem 7.1 for Bo LI and Bo = pl
Corollary K.3 (Ba LI). Suppose that Assumptions 2.1, 2.2 and 2.3 hold. Let {aeltza be the iterates generated by the BFGS method, where the step size satisfies the Armijo-Woff conditions in (5) and (6). For any initial point un E Rd and the initial Hessian upproximation matrix Bg = LI, the average complexity of line search Algorithm I Ta is upper bounded by
1-3 2(1 - B) 3CoR
Ar S 2
(1+
3 3-a a a(1-B)t
+ 2 2oog
logg 16(1 aa) +log (1 a(1 B)t
3Cok +
6ds
a(1-B)
38CaM
Moreover, when
2 6dw
a(1-3) Coks, we have that
36
3(1 (01-9) 9) + 2 1og (5 + +og, 2(1 -a)).
A 2 log2 (1+ 3
(104)
Proof. Since Bo LI, we have Bo = Bo I and Bo = LV² Using results in the proof of Corollary 5.3, have
=
L (B)) O. v (Bo) s dr.
Combining these two results with the result in Theorem 7.1, we prove the conclusion.
Corollary K.4 (Bo = pl). Let {ze)120 be the iterates generated by the BFGS method with inexact line search (5), (6) and suppose that Assumptions 2.1, 2.2 and 2.3 hold. For any initial point zo Rd and the initial Hessian approximation matrix Bo ,l, the average complexity of line search Algorithm 1 Ty is upper bounded by
3COx 2(1 - B) lod + a(1-0)
Ar S 2 + logz (1+
1 1 +
B a
B 3-a
t
Codlog n +
3Cox
6(1 + 2Co) n + 36CON
+ 2 log2 (log2 16(1 - a) + log2 (1 +
a(1-8)
a(1-8)
Moreover, when 2 6(1 + +C2 log + 36Cpb a[1-B], we have that
A₂ < 2 + log, (1+ 3(1 - 3)
+ 2 log + log,, 2(1 a)).
(105)
3
34

---

Proof. Since Bo pI, we have Bo = Bo = I and B, = BB nV f(x.)) Using results in the proof of Corollary 4.2, we have
V (B) S dlog Ki
(Bo) S dllg k.
Combining these two results with (26) in Theorem 6.4, we prove the conclusion.
35

---

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

---

Answer: [Yes]
Justification: All the theorems, formulas, and proofs in the paper are numbered and cross- referenced. All assumptions for each presented result are clearly stated referenced in the statements of the lemmas, propositions, or theorems. The proofs of all results are presented in the supplemental material. High-level ideas of the proofs are included in the main text whenever possible. Some lemmas are borrowed from [38], and this is explicitly mentioned in both the paper and the supplementary material section D.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
37

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/guicn hwwlcc/ggg//////ee Stweee///ooSuuuissiiooooc conoollcy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: wwwodeSumisssoonoo....
// http:ppulllpllpdeeepppppppp
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: tttttps://eurrre nwwrips.....p// http:/puli/Bthhssaiiiaaae iinesisseellee
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
39

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
40

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "f5FbcvyvQe", "reviewer": "Reviewer_7mqx", "summary": "The paper provides non-asymptotic global convergence for BFGW with Armijo-Wolfe (A-S) line search. It provides three main results: \n\n(a) $O(1- 1/\\kappa)^t$ rate globally\n\n(b) with Lipschitz Hessian: $O(1-\\alpha(1-\\beta))^t$ rate (condition number independent) after iteration t is large enough \n\n(c) with Lipschitz Hessian: $O((1/t)^t)$ superlinear rate", "questions": "1. I am looking for some comments about the existence of stepsize $\\eta_t$ satisfying A-S conditions (5) and (6). Does the exact line-search stepisze in [38] satisfy it?\n\n2. What happens if we simply pick the initial $B_0$ to be the identity matrix$?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The convergence is characterized non-asymptotically. I believe such results for BFGS with A-S stepsize are new. \n\n2. The rate provided for BFGS is faster than in previous literature.", "weaknesses": "Authors should carefully consider the similarities and differences with the reference [38]. For example, Proposition 3.1 in this manuscript is almost the same as Proposition 1 in [38], which is a critical element of this paper. Additionally, the proof employs some results from [38]. I am concerned about the extent of this overlap. Although authors already commented on the final results difference with [38], there is also much overlap in the main contents. It is essential for the authors to more thoroughly address and discuss these parallels within the manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Weakness.** Thank you to the reviewer for raising this valid point. We would like to mention that our paper and reference [38] have similar goals, both aiming to establish the global convergence rate of BFGS under some line-search scheme. The primary difference is in the choice of line-search: in our work, the step size is chosen to satisfy the weak Wolfe conditions specified in (5) and (6), while in [38], the step size is determined by exact line search. Given that, it is inevitable to see some similarities and overlaps in the presentation and intermediate results of our submission and [38]. In fact, we have  highlighted in the paper any overlap with [38]. That said, all our theoretical results are different from the ones in [38] and our analysis deviates from [38] in the following multiple levels: \n1. The global linear convergence rate $1 - \\frac{1}{\\kappa}$ in Theorem 4.1 of our paper is strictly better than the corresponding global linear rate $1 - \\frac{1}{\\kappa^{1.5}}$ of the exact line search in [38]. This improvement is due to the fact that we can lower bound the term $\\hat{p}_t$ defined in (22) by $\\alpha$ as presented in Lemma 2.1 in our submission instead of $\\frac{1}{\\sqrt{\\kappa}}$ in [38]. This difference of the lower bounds of $\\hat{p}_t$ leads to the improvement of our results. \n2. The convergence bounds in Theorem 5.2 are novel and unique to our submission, demonstrating that under the additional assumption that the Hessian is also Lipschitz, BFGS can achieve a linear rate independent of the problem parameters after a certain number of iterations. The analysis in [38] failed to establish similar parameter-free global linear rates, under similar assumptions. \n3. The most significant distinction between our analysis and the one in [38] is in the global superlinear convergence. Specifically, in our submission, we focus on the \"good\" event that ensures the unit step size $\\eta_t = 1$ is admissible (satisfying the weak Wolfe conditions (5) and (6)) and control the size of the \"bad\" set of the time indexes where $\\eta_t \\neq 1$ (see Lemmas 6.1 to 6.3). This technique and idea are independent of the superlinear convergence analysis in [38], where the step size $\\eta_t$, determined by the exact line search, can be $1$, larger than $1$, or smaller than $1$.\n    \n**Response to question 1.** This is a good point. Note that for any objective function that is bounded below and any descent search direction $d_t$ where $g_t^\\top d_t < 0$, there always exists an interval of the form $[\\eta_l, \\eta_u]$ for which all the real values in this interval satisfy the weak Wolfe conditions specified in (5) and (6). (Please check Lemma 3.1 in Numerical Optimization by Stephen J. Wright and Jorge Nocedal.) Notice that we assume that the objective function is bounded below in our submission and the BFGS search direction $d_t = B_t^{-1} g_t$ is a descent search direction. Hence, there always exists an interval of step size choices for which the conditions (5) and (6) are satisfied. We will highlight this point in the revised paper. While this is only an existence result, in our line search routine, we proposed the log bisection algorithm (Algorithm 1) that chooses the step size $\\eta_t$ satisfying the weak Wolfe conditions (5) and (6), and we also characterized the complexity of our log bisection scheme that produces such $\\eta_t$. Please check all the proofs in Appendix I. Hence, it is possible to efficiently find such stepsize.\n    \nRegarding your question on whether the exact line-search step size satisfies the conditions in (5) and (6), the short answer is no. To be more precise, the step size $\\eta_t$ obtained by the exact line-search satisfies the property that $g_{t + 1}^\\top d_t = 0$. Hence, it satisfies the curvature condition (6) for any $\\beta \\in (0, 1)$. However, there is no guarantee that the exact line-search step size could satisfy the sufficient descent condition (5) for any $\\alpha \\in (0, 1/2)$. Therefore, in general, the exact line-search step size from [38] is not admissible for the weak Wolfe conditions (5) and (6).\n    \n**Response to question 2.** This is a good question. All our global linear and superlinear convergence bounds hold for any $B_0$ as long as it is symmetric positive definite. The only difference the choice of initial Hessian approximation could make is in the value of $\\Psi(\\bar{B_0})$ and $\\Psi(\\tilde{B_0})$ appearing in our theoretical results. In the corollaries of our paper, we chose $B_0 = LI$ and $B_0 = \\mu I$ as two special cases because we can obtain specific and explicit upper bounds in terms of the dimension $d$ and the condition number $\\kappa$ in different theorems, making our results easier to parse.\n    \nIt is possible to establish all results for the special case where $B_0 = I$, and only the values of $\\Psi(\\bar{B_0})$ in Theorem 4.1 and Theorem 5.2 and $\\Psi(\\tilde{B_0})$ in Theorem 6.4 will change, where $\\bar{B_0} = \\frac{1}{L}B_0$ and $\\tilde{B_0} = \\nabla^2{f(x_*)}^{-\\frac{1}{2}}B_0 \\nabla^2{f(x_*)}^{-\\frac{1}{2}}$. Notice that the transition time required to reach different linear and superlinear convergence stages depends on the values of $\\Psi(\\bar{B_0})$ and $\\Psi(\\tilde{B_0})$. Hence, the only impact of choosing $B_0$ as the identity matrix is that it will affect the required number of steps to reach the parameter-free linear convergence stage and the superlinear convergence stage. In fact, if $B_0 = I$, we have that $\\Psi(\\bar{B_0}) = \\frac{1}{L}d - d + d\\log{L}$ and $\\Psi(\\tilde{B_0}) = \\mathbf{Tr}(\\nabla^2{f(x_*)}^{-1}) - d - \\log{\\mathbf{Det}(\\nabla^2{f(x_*)}^{-1})} \\leq d(\\frac{1}{\\mu} - 1 + \\log{L})$. Finally, to better study the special case of $B_0 = I$, we conducted numerical experiments with BFGS using $B_0 = I$, as presented in Figure 1 of the attached PDF. As we observe, the performance of choosing $B_0$ as the identity matrix $I$ is quite good compared to other initializations of $B_0$.", "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": "", "extra_scores": {}}, {"review_id": "gJvbNcWpML", "reviewer": "Reviewer_GXyX", "summary": "This paper provides the non-asymptotic global linear convergence rate of $O((1-1/\\kappa)^t)$ for BFGS method with inexact line search. It also shows the superlinear convergence rate of $O((1/t)^t)$ under the Hessian Lipschitz condition.", "questions": "The BFGS method is a classical quasi-Newton method proposed in 1970 and its explicit local superlinear convergence rate has been established until 2021. However, the global convergence of BFGS is an interesting problem which has not been well addressed before. For example, applying traditional analysis of Armijo-Wolfe line search on BFGS to guarantee the global convergence cannot achieve the explicit local superlinear rates.\n\nThis paper provides both global and local convergence rates of BFGS methods with inexact line search, matching the rates of gradient descent and BFGS under the first-order and second-order Lipschitz assumptions. Both of these results are reasonable, and the theoretical analysis based on the function $\\Phi(A)={\\rm Tr}(A)-d-\\log\\det(A)$ make sense. I believe the theoretical contribution of this paper is valuable to the community of machine learning and optimization.\n\nI have some minor questions/comments:\n1. Unifying the global and local convergence rates into one framework of BFGS with line search is nice. We can also address this problem by a simple way, i.e., run (accelerated) gradient descent to enter the local region, then run standard BFGS to achieve the superlinear rate. Can you compare the results in your paper with this heuristic method?\n2. Can you provide some result for $B_0=\\alpha I$ with $\\alpha\\in(\\mu,L)$ as the extension of Corollary 6.5?\n3. The discussion on the initial Hessian estimator after Corollary 6.5 is interesting. It is better to provide some experiments to validate it. Considering the theoretical contribution of this paper is strong, I will still recommend accept even if there is no additional experiment in rebuttal.\n4. The following recent work for the explicit superlinear convergence rates of quasi-Newton methods should be involved into the literature review:\n\n         [A] Zhuanghua Liu, Luo Luo, Bryan Kian Hsiang Low. Incremental quasi-Newton methods with faster superlinear convergence rates. AAAI 2024.\n         [B] Aakash Lahoti, Spandan Senapati, Ketan Rajawat, Alec Koppel. Sharpened lazy incremental quasi-Newton method. arXiv:2305.17283.\n         [C] Chengchang Liu, Cheng Chen, Luo Luo. Symmetric rank-k methods. arXiv:2303.16188, 2023.\n         [D] Chengchang Liu, Cheng Chen, Luo Luo, John C.S. Lui. Block Broyden's methods for solving nonlinear equations. NeurIPS 2023.\n         [E] Chengchang Liu, Luo Luo. Quasi-Newton methods for saddle point problems. NeurIPS 2022.\n         [F] Chengchang Liu, Shuxian Bi, Luo Luo, John C.S. Lui. Partial-quasi-Newton methods: efficient algorithms for minimax optimization problems with unbalanced dimensionality. KDD 2022.\n         [G] Haishan Ye, Dachao Lin, Zhihua Zhang. Greedy and random Broyden's methods with explicit superlinear convergence rates in nonlinear equations. arXiv:2110.08572\n         [H] Dachao Lin, Haishan Ye, Zhihua Zhang. Explicit superlinear convergence rates of Broyden's methods in nonlinear equations. arXiv:2109.01974\n\n5. In line 49, it is somewhat inappropriate to call reference [40] a draft. It is more appropriate to use \"unpublished paper\" or \"technical report\" to describe it.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "See questions.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question 1.** *Unifying the global and local convergence rates into one framework of BFGS with line search is nice. We can also address this problem by a simple way, i.e., run (accelerated) gradient descent to enter the local region, then run standard BFGS to achieve the superlinear rate. Can you compare the results in your paper with this heuristic method?*\n    \n**Response.** This is a great question. We can use the suggested method of the combination of accelerated gradient descent (AGD) with BFGS to achieve a faster convergence rate compared to the vanilla BFGS with line search. However, we would like to highlight the following two points:\n\nFirst, we would like to mention that the global convergence complexity of the vanilla BFGS quasi-Newton method with line search was an interesting open problem worth exploring. Interestingly, our results show that BFGS with inexact line search is no worse than gradient descent, and will reach the faster superlinear convergence stage after some explicit iterations. Indeed, it would be great if one could use this analysis to design an accelerated version of BFGS that globally outperforms AGD, meaning it achieves a global linear rate that matches the one for AGD and an eventual superlinear rate.\n\nSecond, the size of the local neighborhood for BFGS to achieve superlinear convergence depends on some parameters of the objective function, such as the gradient smoothness parameter $L$ or the strong convexity parameter $\\mu$. Hence, to follow the reviewer's suggestion and switch from AGD to BFGS in a local neighborhood of the solution, we need to know these parameters to determine if the iteration has reached the local regime. Therefore, this combination of AGD and BFGS requires knowing the values of parameters $L$ or $\\mu$. For our vanilla BFGS with line search, we do not require access to any of those parameters in the implementation of the algorithm. Although in Corollary 6.5 we compare the results of different $B_0 = LI$ and $B_0 = \\mu I$, we only use these $B_0$ to explicitly obtain the convergence bounds of the BFGS. In practice, $B_0$ could be any symmetric positive definite matrix. We can just choose $B_0 = I$ or $B_0 = cI$ for any positive real number $c$ (please check the presented experiments in the attached PDF). Therefore, to implement the AGD plus BFGS, we need to know some parameters of the objective function. In contrast, to implement the vanilla BFGS with line search, we don't need to know any parameters except the line search parameters $\\alpha$ and $\\beta$ as specified in (5) and (6). This is one advantage of vanilla global BFGS with line search over the combination of first-order methods with local BFGS.\n\n**Question 2.** *Can you provide some result for $B_0 = \\alpha I$ with $\\alpha \\in (\\mu, I)$ as the extension of Corollary 6.5?*\n    \n**Response.** All our global linear and superlinear convergence bounds hold for any $B_0$ as long as it is symmetric positive definite. The only difference the choice of initial Hessian approximation could make is in the value of $\\Psi(\\bar{B_0})$ and $\\Psi(\\tilde{B_0})$ appearing in our theoretical results. In the corollaries of our paper, we chose $B_0 = LI$ and $B_0 = \\mu I$ as two special cases because we can obtain specific and explicit upper bounds in terms of the dimension $d$ and the condition number $\\kappa$ in different theorems, making our results easier to parse.\n    \nIf we choose $B_0 = \\alpha I$ in Corollary 6.5, then $\\Psi(\\bar{B_0}) = \\Psi(\\frac{\\alpha}{L}I) = \\frac{\\alpha}{L}d - d + d\\log{\\frac{L}{\\alpha}}$. Moreover, we would have $\\Psi(\\tilde{B_0}) = \\Psi(\\alpha \\nabla^2{f(x_*)^{-1}}) = \\alpha\\mathbf{Tr}(\\nabla^2{f(x_*)^{-1}}) - d - \\log{\\mathbf{Det}(\\alpha\\nabla^2{f(x_*)^{-1}})}$ which is totally determined by the Hessian matrix $\\nabla^2{f(x_*)^{-1}}$. In this case, one can use the upper bounds $\\Psi(\\bar{B_0}) = d(\\frac{\\alpha}{L} - 1 + \\log{\\frac{L}{\\alpha}})$ and $\\Psi(\\tilde{B_0}) = \\mathbf{Tr}(\\alpha\\nabla^2{f(x_*)}^{-1}) - d - \\log{\\mathbf{Det}(\\alpha\\nabla^2{f(x_*)}^{-1})} \\leq d(\\frac{\\alpha}{\\mu} - 1 + \\log{\\frac{L}{\\alpha}}) $ to simplify the expressions.\n    \nApplying these values of $\\Psi(\\bar{B_0})$ and $\\Psi(\\tilde{B_0})$ to the superlinear bound in Theorem 6.4, we can obtain the superlinear convergence rates for $B_0 = \\alpha I$ in Corollary 6.5. We also include the performance of BFGS with $B_0 = cI$ where $c \\in [\\mu, L]$ in our numerical experiments as presented in Figure 1 of the attached pdf. We observe that the performance of BFGS with $B_0 = cI$ is very similar to the convergence curve of BFGS with $B_0 = \\mu I$ in our numerical experiments. We will add this dicussion to the revised paper.\n\n**Question 3.** *The discussion on the initial Hessian estimator after Corollary 6.5 is interesting. It is better to provide some experiments to validate it. Considering the theoretical contribution of this paper is strong, I will still recommend accept even if there is no additional experiment in rebuttal.*\n    \n**Response.** Thanks for the advice. We have attached the empirical results of our numerical experiments with different $B_0$ in the pdf.\n\n**Question 4.** *The following recent work for the explicit superlinear convergence rates of quasi-Newton methods should be involved into the literature review:*\n    \n**Response.** Thanks for pointing out all these papers. Indeed, they are all relevant to our submission since they characterize local non-asymptotic convergence rates of different quasi-Newton methods in various settings. We will cite these papers as previous works in the introduction section of our revised version.\n\n**Question 5.** *In line 49, it is somewhat inappropriate to call reference [40] a draft. It is more appropriate to use \"unpublished paper\" or \"technical report\" to describe it.*\n    \n**Response.** Thanks for the advice. We will modify our text in the revised version to cite the reference [40] as a \"technical report\".", "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": "", "extra_scores": {}}, {"review_id": "5PQiLQwG3X", "reviewer": "Reviewer_EiJP", "summary": "This paper establishes a unified non-asymptotic convergence analysis of the BFGS method with Armijo-Wolfe line search. It shows that BFGS exhibits two converging stages: (1) a linear global convergence rate, and the rate is  independent of the condition number when Hessian is Lipschitz continuous. (2) a superlinear convergence as the unit step length satisfies the Armijo-Wolfe line search condition. The convergence rate is dependent of initialization of weight matrix, suboptimality of initial iterate, condition number, and parameters in line search condition. The iteration complexity is also explored using a log bisection algorithm.", "questions": "Please see the previous section.", "limitations": "The discussed limitations of the work are clear. I see no potential negative societal impact related to this work. I suggest to include empirical results or numerical experiments to validate the theoretical findings.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The non-asymptotic global convergence rate presented in this paper improves the previous result in the literature. The theoretical framework is rigorous, with clearly stated assumptions and detailed proofs supporting the main results. The theorem statements and comments are clear.\n- The use of log bisection algorithm is innovative.\n- The explanation of theoretical results aid in the reader's understanding of the methodology and results.\n- By providing a unified non-asymptotic convergence analysis of global and superlinear convergence result together with the complexity analysis, the paper  in optimization literature.", "weaknesses": "- The statement “present the first explicit” in abstract is too strong.\n- The author could add “with $B_0 = L I$” or comment that this result needs such condition in Line 4 to be more precise.\n- A general comment for abstract: the abstract starts with a global convergence result and then establishes the global superlinear convergence rate. However, this could be confusing to the audiences unfamiliar with the literature. Why would you present linear convergence if you have proved a superlinear convergence? Hence, I would suggest to improve the presentation to make the abstract more clear.\n- When [38] is mentioned, the authors could comments about why the convergence rate is worse even with an exact line search. Although a theoretical reason is discussed in remark 4.1, I feel that a more intuitive explanation could be provided in the introduction section.\n- In line 62 of the contribution, the author should mention that the convergence rate $(1-\\frac{\\mu}{L})^t$ is proved under the condition $B_0 = L I$.\n- It is stated “we focus on two practical initialization schemes:” in line 217. However, the initialization requires $L$ or $\\mu$, which is normally unknown. Hence, they are not practical schemes.\n- $\\tilde B_0$ is redefined in line 227.\n- The $\\hat \\rho_t$ should converge to 1/2 instead of 1 in line 237.\n- make { } in $\\delta_2$ larger in eq. 23.\n- It would be more interesting to add one more bullet point to Corollary 4.2, for $t \\ge T(d, \\kappa, B_0)$, you could achieve similar explicit linear rate for any initial weighted matrix $B_0$.\n- The authors could comment more about the finite number of iterations. (results in lemma 6.3) For example, how large it is in your specialized two initializations? How will the interation indices in set I be distributed?\n- When $t$ is not sufficiently large, the upper bound provided in (26) could be very large compared to the upper bound given in Section 4 and 5.  In terms of the presentation, it might be more transparent to present all the transitions you have in terms of the convergence, from inexplicit linear convergence, to explicit linear convergence, to superlinear convergence.\n- $C_0$ Should be suboptimality of initial iterate in line 273.\n- The author comments in line 319 that “notice that when N is sufficiently large such that we reach the superlinear convergence stage”. However, there are not really different stages presented in Section 6.\n- Log bisection algorithm is not usually used in practice for BFGS. The author should comment about the reason that one should use log bisection rather than other popular line search schemes like backtracking.\n- While this is a theoretical paper, authors could still show some numerical experiment results to present different convergence stages of BFGS, performance with different initialized matrix $B_0$, change of step size etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to weakness 1,2,3.** We will soften our claims and add “$B_0 = L I$” in the abstract. Our global superlinear convergence analysis is based on the results from the global linear convergence rates, so we need to present both the linear and superlinear convergence results. Moreover, the linear convergence rates we obtained in this submission are also novel and innovative since there is no such linear ratio of $1 - \\frac{1}{\\kappa}$ or parameter-free linear rate as presented in Section 5 in previous works. We will revise the abstract accordingly to resolve these ambiguities.\n\n**Response to weakness 4.** The key intuitive explanation is the step size $\\eta_t$ satisfying the exact line search may not satisfy the sufficient descent condition (5) for any $\\alpha \\in (0, \\frac{1}{2})$, which is a fundamental condition to prove the convergence bound in our paper. We will add this explanation in our revised version.\n\n**Response to weakness 5.** We will clarify that when $B_0 = L I$, the linear rate of $(1 - \\frac{\\mu}{L})^t$ is achieved at the first iteration while for $B_0 = \\mu I$, the same bound holds for $t \\geq d\\log{\\kappa}$.\n\n**Response to weakness 6.**  We agree with the reviewer that $LI$ and $\\mu I$ are not necessarily practical initialization schemes, as we generally may not know the values of $L$ or $\\mu$. We will modify the wording in our revised version. It is better to state that we choose these two specific initialization matrices since they can make all the non-asymptotic global linear and superlinear convergence bounds and expressions simpler and clearer. That said, in the attached numerical experiments, we have illustrated the convergence rate of two more practical choices: $B_0 = I$ and $B_0 = cI$ where $c \\in [\\mu, L]$ and is easy to compute. In the revised paper, we plan to add corollaries for these two special cases after each result presented in the paper.\n\n**Response to weakness 7, 9, 13.**  We will fix all these typos.\n\n**Response to weakness 8.**  Let's clarify why $\\hat{\\rho_t}$ should converge to 1. This is because The global linear convergence results indicate that $\\sum_{i = 0}^{\\infty}C_i < +\\infty$. Hence, from (44) of Proposition G.2 in the appendix, we know that $\\sum_{i = 0}^{\\infty}\\omega(\\rho_i - 1) < +\\infty$, which implies that $\\lim_{i \\to \\infty}\\omega(\\rho_i - 1) = 0$. Notice that the function $\\omega$ is continuous and $\\omega(x) = 0$ if and only if $x = 0$. Therefore, we have that $\\lim_{i \\to \\infty}\\rho_i = 1$. \n\nIn equation (22), the lower bound of $\\hat{p}_t$ should converge to $\\frac{1}{2}$ since $C_t$ converges to 0 and $\\rho_t$ converges to 1. We would like to highlight that the fact that $\\hat{p}_t$ converges to $\\frac{1}{2}$ is not problematic, as the lower bound of $\\hat{q}_t$ has a factor of 2 (see line 519, part (b) of Lemma D.2 in the appendix). This factor of 2 of $\\hat{q}_t$ times the limit $\\frac{1}{2}$ of $\\hat{p}_t$ produces the unit factor 1, which leads to the superlinear convergence rates of the BFGS method in section 6.\n\n**Response to weakness 10.**  We will add more lines in Corollary 4.2 for the convergence results of any initial $B_0$ in our revised version.\n\n**Response to weakness 11.** We will add comments to our revised paper. In fact when $B_0 = L I$, we have that $t_0 = \\frac{3\\kappa}{\\alpha(1 - \\beta)}\\log{\\frac{C_0}{\\delta_1}}$ and $|I|  \\leq \\delta_4\\Big(d\\kappa + \\frac{6C_0\\kappa}{\\alpha(1 - \\beta)}\\Big)$. When $B_0 = \\mu I$, we have that $t_0 = \\max\\\\{d\\log{\\kappa}, \\frac{3\\kappa}{\\alpha(1 - \\beta)}\\log{\\frac{C_0}{\\delta_1}}\\\\}$ and $|I|  \\leq \\delta_4\\Big(\\Psi((1 + 2C_0)d\\log{\\kappa} + \\frac{6C_0\\kappa}{\\alpha(1 - \\beta)}\\Big)$.\n\n**Response to weakness 12.**  We have added one table in the attached pdf presenting all the convergence stages with a required number of iterations to transit to each phase. \n\n**Response to weakness 14.**  Thanks for the comments. We did not explicitly present different convergence stages in our submission. To address this issue, in the attached PDF we included a table highlighting all the linear and superlinear convergence stages with the required number of steps to transition to each phase. Please check the table in the uploaded PDF file. We will add this transition table in our revised version. \n\n**Response to weakness 15.**  In general, backtracking line search is used for finding an acceptable step size when we know that the interval of admissible step sizes is bounded below by zero and can be written as $(0, \\eta_1]$. In this case, we can start the process of selecting the step size with a large step size $\\eta_{initial}$, possibly $\\eta = 1$, and then backtrack it by a factor $\\beta < 1$. It can be easily verified that after at most $\\log_{1/\\beta} (\\eta_{initial}/\\eta_1)$ iterations, we will find an admissible step size. In fact, if we only needed the sufficient decrease condition (5), we could apply the backtracking technique with initial $\\eta_1 = 1$. \n   \nHowever, the weak Wolfe conditions require both (5) and (6). Condition (6) indicates that there exists a strictly positive $\\eta_2$ such that the admissible step size $\\eta_t \\geq \\eta_2$. Hence, the lower bound of the proper step size satisfying both (5) and (6) is not zero, and we can no longer utilize backtracking to find such a step size. Therefore, we need to find a window $[\\eta'_2, \\eta'_1]$ such that $\\eta'_2 \\geq \\eta_2$ and $\\eta'_1 \\leq \\eta_1$ so that when $\\eta_t$ belongs to this window $[\\eta'_2, \\eta'_1]$, we have that $\\eta_t \\in [\\eta_2, \\eta_1]$ and this $\\eta_t$ satisfies conditions (5) and (6). We need to use the bisection method to construct both the upper and lower bounds of this window. We apply the log bisection instead of the vanilla bisection because it helps simplify the theoretical analysis of the line search complexity. We will highlight this in our revised version of the paper.\n\n**Response to weakness 16 and Limitations.** Please check numerical experiments in the attached file.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for providing all these valuable advice and constructive feedbacks. Here is the general response.

**Numerical Experiments**

We conducted some numerical experiments and we attached all our empirical results in Figure 1 of the uploaded file. We focus on the hard cubic objective function defined as
\begin{equation*}
    f(x) = \frac{\alpha}{12}\left(\sum_{i = 1}^{d - 1}g(v_i^\top x - v_{i + 1}^\top x) - \beta v_1^\top x\right) + \frac{\lambda}{2}\\|x\\|^2,
\end{equation*}
and $g: \mathbb{R} \to \mathbb{R}$ is defined as
\begin{equation*}
    g(w) =
    \begin{cases}
        \frac{1}{3}|w|^3 & |w| \leq \Delta, \\
        \Delta w^2 - \Delta^2 |w| + \frac{1}{3}\Delta^3  & |w| > \Delta,
    \end{cases}       
\end{equation*}
where $\alpha, \beta, \lambda, \Delta \in \mathbb{R}$ are hyper-parameters and $\{v_i\}_{i = 1}^{n}$ are standard orthogonal unit vectors in $\mathbb{R}^{d}$. This hard cubic function is used to establish a lower bound for second-order methods. 

We compared the convergence curves of the BFGS method with inexact line search step size $\eta_t$ satisfying weak Wolfe conditions (5) and (6) of different initialization matrices $B_0$: $B_0 = L I$, $B_0 = \mu I$, $B_0 = I$ and $B_0 = c I$ where $c = \frac{s^\top y}{\|s\|^2}$, $s = x_2 - x_1$, $y = \nabla{f(x_2)} - \nabla{f(x_1)}$ and $x_1, x_2$ are two randomly generated vectors. It can be easily verified that $c \in [\mu, L]$. We choose $\alpha = 0.1$ in condition (5) and $\beta = 0.9$ in condition (6). We apply the log bisection in Algorithm 1 to choose the step size $\eta_t$ at each iteration. We compare the empirical results with various dimensions $d$ and condition numbers $\kappa$. The x-axis is the number of iterations $t$ and the y-axis is the ratio $\frac{f(x_t) - f(x_*)}{f(x_0) - f(x_*)}$. 

First, we observe that BFGS with $B_0 = L I$ initially converges faster than BFGS with $B_0 = \mu I$ in most plots, aligning with our theoretical findings that the linear convergence rate of BFGS with $B_0 = L I$ surpasses that of $B_0 = \mu I$ in Corollary 4.2. In Corollary 4.2, we show that BFGS with $B_0 = L I$ could achieve the linear rate of $1 - 1/\kappa$ from the first iteration while BFGS with $B_0 = \mu I$ needs to run $d\log{\kappa}$ to reach the same linear rate.

Second, the transition to superlinear convergence for BFGS with $B_0 = \mu I$ typically occurs around $t \approx d$, as predicted by our theoretical analysis. Although BFGS with $B_0 = L I$ initially converges faster, its transition to superlinear convergence consistently occurs later than for $B_0 = \mu I$. Notably, for a fixed dimension $d=600$, the transition to superlinear convergence for $B_0 = L I$ occurs increasingly later as the problem condition number rises, an effect not observed for $B_0 = \mu I$. This phenomenon indicates that the superlinear rate for $B_0 = L I$ is more sensitive to the condition number $\kappa$, which corroborates our results in Corollary 6.5. In Corollary 6.5, we present that BFGS with $B_0 = L I$ needs $d\kappa$ steps to reach the superlinear convergence stage while this is improved to $d\log{\kappa}$ for BFGS with $B_0 = \mu I$.

Moreover, the performance of BFGS for $B_0 = I$ and $B_0 = c I$ are similar to the performance of BFGS with $B_0 = \mu I$. Notice that the initializations of $B_0 = I$ and $B_0 = c I$ are two practical choices of the initial Hessian approximation matrix $B_0$ that are commonly used. 

**Different Convergence Stages**

We also attach table 1 in the uploaded file with summary of all our convergence results for (i) an arbitrary positive definite $B_0$, (ii) $B_0=L I$, and (iii)$B_0=\mu I$. The table contains all the convergence rates of three different convergence phases: (i) linear convergence phase with $1 - 1/\kappa$. (ii) parameter-free linear convergence phase and (iii) superlinear convergence phase with number of iterations required to achieve the corresponding stages.

Meta-review: The paper studies BFGS with an inexact line search scheme satisfying the Armijo-Wolfe conditions. 
1. On smooth strongly convex functions they show the sub-optimality is bounded by O( (1 - 1/\kappa)^t ) matching gradient descent. This improves on best-known the global convergence guarantees for BFGS where t is number of iterations.
2. With the added assumption that the Hessian is Lipschitz the paper shows that, after sufficient number of iterations faster convergence occurs. These results are less novel given non-asymptotic superlinear convergence for BFGS is already well-studied [37,38].

The closest related papers is Qiujiang Jin, Ruichen Jiang, Aryan Mokhtari [38]. [38] considers the same function classes but focuses on exact line search rather than satisfying the Armijo-Wolfe conditions. Satisfying the Armijo-Wolfe conditions is more realistic. The major theoretical gain over [38] is that on smooth strongly convex functions [38] only proves an O( (1 - 1/\kappa^{1.5})^t ) suboptimality bound whereas this paper shows a O( (1 - 1/\kappa)^t ) suboptimality bound.

Since the O( (1 - 1/\kappa)^t ) suboptimality bound is worse than the O( (1 - 1/\kappa^{1/2})^t ) suboptimality bound of AGD its not clear that O( (1 - 1/\kappa)^t ) is the best suboptimality guarantee for BFGS. This paper would have been much stronger if the authors had shown either a better suboptimality guarantee or a lower bound on the performance of BFGS to show that O( (1 - 1/\kappa)^t ) is tight.

Minor comments:
- [37] was published in mathematical programming in 2023 but you currently cite the arxiv version
Decision: Accept (spotlight)