Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search

Authors: qiujiang  jin
ruichen  jiang
aryan  mokhtari
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 18:23:13

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.

Main paper: 
 introduction: 
 In this paper, we focus on solving the following unconstrained convex minimization problemEQUATIONwhere f : R d → 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 method by using gradient information to approximate the curvature of the objective function. There are several variations of quasi-Newton methods, primarily distinguished by their update rules for the Hessian approximation matrices. The most well-known among these include the Davidon-Fletcher-Powell (DFP) method [1, 2] , the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method [3] [4] [5] [6] , the Symmetric Rank-One (SR1) method [7, 8] , 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] [11] [12] [13] [14] , greedy quasi-Newton methods [13] [14] [15] [16] , and those based on online learning techniques [17, 18] . In this paper, we mainly focus on the global analysis of the BFGS method, arguably the most successful quasi-Newton method in practice.The classic analyses of BFGS, including [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] , primarily focused on demonstrating local asymptotic 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] [30] [31] [32] [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. B0 = ∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2. 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] [20] [21] [22] [23] [24] [25] [26] [27] [28] .BFGS Update. Next, we state the general update rule of BFGS. If we denote x t as the iterate at time t, the vector g t = ∇f (x t ) as the objective function gradient at x t , and B t as the Hessian approximation matrix at step t, then the update is given byEQUATIONwhere η t > 0 is the step size and d t is the descent direction. By defining the variable difference s t := x t+1 -x t and the gradient difference y t := ∇f (x t+1 ) -∇f (x t ), we can present the Hessian approximation matrix update for BFGS as follows:EQUATIONTo avoid the costly operation of inverting the matrix B t , one can define the inverse Hessian approximation matrix as H t := B -1 t and apply the Sherman-Morrison-Woodbury formula to obtainEQUATIONIt is well-known that for a strongly convex objective function, the Hessian approximation matrices B t remain symmetric and positive definite if the initial matrix B 0 is symmetric positive definite [41] . Therefore, all matrices B t and H t are symmetric positive definite throughout this paper.As mentioned earlier, establishing a global convergence guarantee for BFGS requires pairing it with a line search scheme to select the stepsize η t . This paper focuses on implementing BFGS with the Armijo-Wolfe line search, detailed in the following subsection.Armijo-Wolfe Line Search. We consider a stepsize η t > 0 that satisfies the Armijo-Wolfe conditionsEQUATION∇fEQUATIONwhere α and β are the line search parameters, satisfying 0 < α < β < 1 and 0 < α < 1 2 . The condition in (5) is the Armijo condition, ensuring that the step size η t provides a sufficient decrease in the objective function f . The condition in (6) is the curvature condition, which guarantees that the slope ∇f (x t + η t d t )⊤ d t at η t is not strongly negative, indicating that further movement along d t would significantly decrease the function value. These conditions provide upper and lower bounds on the admissible step size η t . In some references, the Armijo-Wolfe line search conditions are known as the weak Wolfe conditions [42, 43] . The procedure for finding η t that satisfies these conditions is described in Section 7. Next lemma presents key properties of the Armijo-Wolfe conditions. 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 x 0 and any symmetric positive definite initial Hessian approximation matrix B 0 , the following results hold for all t ≥ 0:EQUATIONRemark 2.1. While in this paper we only focus on the Armijo-Wolfe line search, our results are also valid for some other line search schemes that require stricter conditions. For instance, in the strong Wolfe line search, given 0 < α < β < 1 and 0 < α < 1 2 , the required conditions for the step size aref (x t + η t d t ) ≤ f (x t ) + αη t ∇f (x t ) ⊤ d t , |∇f (x t + η t d t ) ⊤ d t | ≤ β∇f (x t ) ⊤ d t ,Indeed, if η t satisfies the strong Wolfe conditions, it also satisfies the Armijo-Wolfe conditions.Another commonly employed line search scheme is Armijo-Goldstein, which imposes the conditions-c 1 η t ∇f (x t ) ⊤ d t ≤ f (x t ) -f (x t + η t d t ) ≤ -c 2 η t ∇f (x t ) ⊤ d t , with 0 < c 1 ≤ c 2 < 1.The lower bound on f (x t ) -f (x t + η t d t ) in the Armijo-Goldstein line search indicates that η t satisfies the sufficient decrease condition in (5) required for the Armijo-Wolfe conditions, with α = c 1 . Moreover, given the convexity of f , the upper bound on f (x t ) -f (x t + η t d t ) in the Armijo-Goldstein line search suggests -η t ∇f(x t + η t d t ) ⊤ d t ≤ f (x t ) -f (x t + η t d t ) ≤ -c 2 η t ∇f (x t ) ⊤ d t .Thus, η t also meets the curvature condition in (6) required in the Armijo-Wolfe conditions with β = c 2 . Hence, all our results derived under the Armijo-Wolfe line search are also valid for both the strong Wolfe line search and the Armijo-Goldstein line search. 
convergence analysis: 
 In this section, we present our theoretical framework for analyzing the global linear convergence rates of BFGS with the Armijo-Wolfe line search scheme. To start, we introduce some necessary definitions and notations. We define the average Hessian matrices J t and G t asEQUATIONFurther, for measuring the suboptimality of the iterates we define the sequence C t asEQUATION)where M is the Lipschitz constant of the Hessian defined in Assumption 2.3 and µ is the strong convexity parameter introduced in Assumption 2.1.To analyze the dynamics of the Hessian approximation matrices {B t } +∞ t=0 , we use the function Ψ(A) Ψ(A) := Tr(A) -d -log Det(A), (10) well-defined for any A ∈ S d ++ . It was introduced in [32] to capture the discrepancy between A and the identity matrix I. Note that Ψ(A) ≥ 0 for any A ∈ S d ++ and Ψ(A) = 0 if and only if A = I. Before we start convergence analysis, given any weight matrix P ∈ S d ++ , we define the weighted versions of the vectors g t , s t , y t , d t and the matrix B t , J t asEQUATIONEQUATION) Note that these weighted matrices and vectors preserve many properties of their unweighted counterparts. For instance, two of these main properties are ĝ⊤ t ŝt = g ⊤ t s t and ŷ⊤ t ŝt = y ⊤ t s t . 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:EQUATIONFinally, we define a crucial quantity, θt , which measures the angle between the weighted descent direction and the negative of the weighted gradient direction, satisfyingEQUATION)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 θt defined in (14) .Proposition 3.1. Let {x t } t≥0 be the iterates generated by BFGS. Recall the definitions of weighted vectors in (11) . Then, for any weight matrix P and for all t ≥ 1, we haveEQUATION)where pt , qt , mt and nt are defined asEQUATION)This result shows the convergence rate of BFGS with Armijo-Wolfe line search depends on four products:t-1 i=0 pi , t-1 i=0 qi , t-1 i=0 ni , and t-1 i=0 cos 2 ( θi) mi .To establish an explicit rate, we need lower bounds on these products. Lemma 2.1 shows that the lower bounds for t-1 i=0 pi and t-1 i=0 ni depend on the inexact line search parameters α and β. We will further prove that if the unit step size η t = 1 satisfies the Armijo-Wolfe conditions, better lower bounds can be obtained for these products.The lower bounds for t-1 i=0 qi and t-1 i=0cos 2 ( θi) miwere established in previous work [38] as presented in Appendix D. Specifically, the bounds for t-1 i=0 qi 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 fort-1 i=0 cos 2 ( θi) midoes not require separate treatment. This is explicitly established in Proposition D.1, a classical result, as discussed in [41, Section 6.4] . We build all our linear and superlinear results by establishing different bounds on the terms in (15) .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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 or the standard error of the mean. 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 of compute required for each of the individual experimental runs as well as 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 it into the paper). 
global linear convergence rates: 
 Building on the tools introduced in Section 3, we establish explicit global linear convergence rates for BFGS with the Armijo-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 to P = LI and hence define the initial weighted matrix B0 as B0 = 1 L B 0 . The following theorem presents our first global linear convergence rate of BFGS for any B 0 ∈ S d ++ . Theorem 4.1. Suppose Assumptions 2.1 and 2.2 hold. Let {x t } t≥0 be the iterates generated by BFGS, where the step size satisfies the Armijo-Wolfe conditions in (5) and (6) . For any initial point x 0 ∈ R d and any initial Hessian approximation matrix B 0 ∈ S d ++ , we haveEQUATION)Remark 4.1. In [38] , the authors analyzed BFGS with exact line search and established a global linear rate of (1 -e -Ψ( B0 )t 1 κ(1+ √ κ) ) t .In comparison, our result in (17) achieves a faster linear rate by eliminating the √ κ factor in the denominator. This improvement arises from using the Armijo-Wolfe conditions. Specifically, under these conditions, we showf (xt)-f (xt+1) -g ⊤ t st≥ α as shown in Lemma 2.1, where α ∈ (0, 1/2) is a line search parameter. In contrast, using exact line search, the authors in [38] proved that f (xt)-f (xt+1) -g ⊤ t st ≥ 2 √ κ+1, thus leading to the extra √ κ factor in their rate.From Theorem 4.1, we observe that the linear convergence rate is determined by the quantity Ψ( B0 ) Thus, to simplify our bounds, we consider two different initializations: B 0 = LI and B 0 = µI.Corollary 4.2. Suppose Assumptions 2.1 and 2.2 hold, {x t } t≥0 are generated by BFGS with step size satisfying the Armijo-Wolfe conditions in (5) and (6), and x 0 ∈ R d is an arbitrary initial point.• If the initial Hessian approximation matrix is set as B 0 = LI, then for any t ≥ 1EQUATION• If the initial Hessian approximation matrix is set as B 0 = µI, then for any t ≥ 1 we haveEQUATION)Corollary 4.2 shows that when initialized with B 0 = LI, BFGS achieves a linear rate of O((1 -1 κ ) t ) from the first iteration, matching the rate of gradient descent. It also indicates that initializing with B 0 = µI achieves a similar rate but after d log κ iterations. While this suggests a preference for initializing with B 0 = LI, subsequent analysis reveals that with enough iterations, BFGS with either initialization can attain a faster linear rate independent of κ. In some cases, starting with B 0 = µI may lead to fewer total iterations to achieve this faster rate. We will explore this trade-off later. 
condition number independent linear convergence rates: 
 In this section, we improve the previous results and establish a non-asymptotic, condition numberfree 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 = ∇ 2 f (x * ) instead of P = LI to prove the condition number-independent global linear rate. Thus, the weighted initial matrix B0 is∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2. Next, we present a general global convergence bound for any initial Hessian approximation B 0 ∈ S d ++ . Proposition 5.1. Suppose Assumptions 2.1, 2.2 and 2.3 hold. Let {x t } t≥0 be the iterates generated by BFGS with the step size satisfying the Armijo-Wolfe conditions in (5) and (6) . Recall the definition of C t in (9) and Ψ(•) in (10) . For any initial point x 0 ∈ R d and any initial Hessian approximation matrix B 0 ∈ S d ++ , the following result holds:f (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤ 1 -2α(1 -β)e -Ψ( B0 )+3 t-1 i=0 C i t t , ∀t ≥ 1.Proposition 5.1 demonstrates that the convergence rate of BFGS with the Armijo-Wolfe line search is influenced by Ψ( B0 ) and the sum t-1 i=0 C i . The first term Ψ( B0 ) is a constant that depends on our choice of the initial Hessian approximation matrix B 0 . The second term t-1 i=0 C i can also be upper bounded using the non-asymptotic global linear convergence rate provided in Theorem 4.1. Theorem 5.2. Suppose Assumptions 2.1, 2.2 and 2.3 hold, and let {x t } t≥0 be the iterates generated by BFGS with the Armijo-Wolfe line search in (5) and (6). Then, for any initial point x 0 ∈ R d and any initial Hessian approximationEQUATION)This result shows that when the number of iterations meets t ≥ Ψ( B0 ) + 3C 0 Ψ( B0 ) + 9 α(1-β) C 0 κ, BFGS with Armijo-Wolfe conditions achieves a condition number-independent linear rate. The choice of B 0 is critical as it influences the required iterations throughB0 = ∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2 and B0 = 1 L B 0 . Different choices of B 0 affect Ψ( B0 ) + 3C 0 Ψ( B0 )and thus the number of iterations needed for condition-free linear convergence. While optimizing B 0 to minimize Ψ( B0 ) + 3C 0 Ψ( B0 ) is possible, we focus on two practical initialization schemes: B 0 = LI and B 0 = µI. Corollary 5.3. Suppose that Assumptions 2.1, 2.2 and 2.3 hold. Let {x t } t≥0 be the iterates generated by the BFGS method, where the step size satisfies the Armijo-Wolfe conditions in (5) and (6), and x 0 ∈ R d as an arbitrary initial point. Then, given the result in Theorem 5.2, we have• If we set B 0 = LI, the rate in (20) holds for t ≥ dκ + 9 α(1-β) C 0 κ, • If we set B 0 = µI, the rate in (20) holds for t ≥ (1 + 3C 0 )d log κ + 9 α(1-β) C 0 κ. Based on Corollary 5.3, if C 0 ≪ κ, or equivalently f (x 0 )-f (x * ) ≪ L 2 µM 2 , then BFGS with B 0 = µI requires less iterations to achieve the condition number-independent linear convergence rate. 
global superlinear convergence rates: 
 In this section, we present our global superlinear result. Consider the definition B0 = ∇2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2as well as the definition of ρ t which is given byEQUATIONTo 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 pt and nt : we used pt ≥ α and nt ≥ 1 -β from Lemma 2.1, which leads to the constant factor α(1 -β) in the final linear rate in Theorem 5.2. Thus, to show a superlinear convergence rate, we need to establish tighter lower bounds for pt and nt . In the following lemma, we show that if the step size η t = 1, we are able to establish such tighter lower bounds.Lemma 6.1. Recall pt = f (xt)-f (xt+1) -ĝ ⊤ t ŝtand nt = ŷ⊤ t ŝt -ĝ ⊤ t ŝt defined in (16) . If the unit step size η t = 1 satisfies the Armijo-Wolfe conditions (5) and (6), then we haveEQUATION)In contrast to the constant lower bounds in Lemma 2.1, the lower bounds in (22) depend on C t and ρ t . Later, we show C t → 0 and ρ t → 1. Hence, the lower bounds in ( 22) approach 1 as the number of iterations increases, enabling us to prove a superlinear rate. That said, the lower bounds in Lemma 6.1 hold only when η t = 1. To complete the picture, we need to quantify when and how often the unit step size is selected during BFGS execution. This is addressed in the next lemmas. Lemma 6.2. Suppose Assumptions 2.1, 2.2, and 2.3 hold and define the constants EQUATIONwhich satisfy 0 < δ 1 < δ 2 < 1 < δ 3 . If C t ≤ δ 1 and δ 2 ≤ ρ t ≤ δ 3 , then η t =EQUATIONMoreover, if we define ω(x) = x -log(1 + x), the size of the setI = {t : ρ t / ∈ [δ 2 , δ 3 ]} is at most |I| ≤ δ 4 Ψ( B0 ) + 2C 0 Ψ( B0 ) + 6C 0 κ α(1 -β), whereEQUATIONLemma 6.3 implies that conditions C t ≤ δ 1 and ρ t ∈ [δ 2 , δ 3 ] 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 η t = 1, and accordingly, the tighter lower bound in Lemma 6.1 will apply for all but a finite number of iterations. By applying these lower bounds along with (15) from Proposition 3.1, we can prove a 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 t and ρ t 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 ∥∇f (x * ) 1 2 (x t -x * )∥. 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. Theorem 6.4. Suppose Assumptions 2.1, 2.2, and 2.3 hold and the iterates {x t } t≥0 are generated by BFGS with step size satisfying the Armijo-Wolfe conditions in (5) and (6) . Recall the definition of C t in (9), Ψ(•) in (10) , B0 := 1 L B 0 , B0 := ∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2, and δ 1 , δ 2 , δ 3 , δ 4 in (23) and (25) . Then, for any x 0 ∈ R d and any B 0 ∈ S d ++ , the following global superlinear result holds:EQUATIONwhere {δ i } 8 i=5 defined below are constants that only depend on line search parameters α and β,δ 5 := max{2 + 2 δ2 , 4δ 3 } 2δ 2 -1 -δ 1 , δ 6 := log 1 2α(1-β) , δ 7 := 1+δ 4 δ 6 +δ 5 , δ 8 := 1+2δ 7 + 2δ 2 -δ 1 -log δ 2 2δ 2 -1-δ 1 .The above result shows a global superlinear convergence rate of the form O((C ′ t ) t ), where C ′ depends on the condition number κ, the initial weighted distance C 0 , and the initial Hessian approximation matrix B 0 . To simplify the expression, we report the above bound for B 0 = LI and B 0 = µI. Corollary 6.5. Suppose Assumptions 2.1, 2.2, and 2.3 hold and the iterates {x t } t≥0 are generated by the BFGS method with step size satisfying the Armijo-Wolfe conditions in (5) and (6), and x 0 ∈ R d as an arbitrary initial point. Then, given the result in Theorem 6.4, the following results hold:EQUATION• If we set B 0 = µI, then we haveEQUATIONThis result shows that BFGS with B 0 = LI achieves a global superlinear rate of O(( dκ+C0κ t ) t ), while BFGS with the initialization B 0 = µI converges at a global superlinear rate of O(( C0d log κ+C0κ t ) t ). Hence, the superlinear result for B 0 = µI outperforms the rate for B 0 = LI when C 0 log κ ≪ κ. Remark 6.2. We chose B 0 = LI and B 0 = µI as two specific cases since they lead to explicit upper bounds in terms of the dimension d and the condition number κ in various theorems, simplifying the interpretation of our results. In practice, however, we often set B 0 = cI, where c = s ⊤ y ∥s∥ 2 , with s = x 2 -x 1 , y = ∇f (x 2 ) -∇f (x 1 ), and x 1 , x 2 as two randomly selected vectors. This choice ensures c ∈ [µ, L], and in the following numerical experiments, the performance of B 0 = cI is similar to that of B 0 = µI. The complexity of BFGS with this initialization is reported in Appendix H. 
complexity analysis: 
 Discussions on the iteration complexity. Using the three established convergence results in Theorems 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 ϵ. However, as discussed above, the choice of the initial Hessian approximation B 0 heavily influences the number of iterations required to observe these rates. To simplify our discussion, we focus on two specific initializations: B 0 = LI and B 0 = µI.The case of B 0 = LI: The overall iteration complexity of BFGS with B 0 = LI is given byO   min    κ log 1 ϵ , (d + C 0 )κ + log 1 ϵ , log 1 ϵ log 1 2 + 1 4 + 1 dκ+C0κ log 1 ϵ      .The case of B 0 = µI: The overall iteration complexity of BFGS with B 0 = µI is given byO   min    d log κ + κ log 1 ϵ , C 0 (d log κ + κ) + log 1 ϵ , log 1 ϵ log 1 2 + 1 4 + 1 C0(d log κ+κ) log 1 ϵ      .We remark that the comparison between these two complexity bounds depends on the relative values of κ, d, C 0 , and ϵ, and neither is uniformly better than the other. It is worth noting that for BFGS with B 0 = LI, we achieve a complexity that is consistently superior to the O κ log 1 ϵ complexity of gradient descent. Moreover, in scenarios where C 0 = O(1) and d ≪ κ, BFGS with B 0 = µI could result in an iteration complexity of O κ + log 1 ϵ , 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 η t at iteration t satisfying the Armijo-Wolfe conditions ( 5) and ( 6) in Algorithm 1 in Appendix J. We define η min and η max as the lower and upper bounds of the "slicing window" containing the trial step size η t , respectively. We start with the initial trial step size η t = 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 η min , η max and shrink the size of this "slicing window" (η min , η max ). We pick the trial step size η as the geometric mean of η min and η max , i.e., log η = (log η max + log η max )/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-Wolfe conditions at Lines 2 and 9. The next theorem characterizes the average number of function value and gradient evaluations per iteration in Algorithm 1 after t iterations, denoted by Λ t , 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 {x t } t≥0 be generated by BFGS with step size satisfying the Armijo-Wolfe conditions in (5) and ( 6) and is chosen by Algorithm 1. If we define σ := (Ψ( B0 ) + 3 α(1-β) κ)C 0 , then for any initial point x 0 ∈ R d and initial Hessian approximation B 0 ∈ S d ++ , the average number of the function value and gradient evaluations per iteration in Algorithm 1 after t iterations satisfiesΛ t ≤ 2+log 2 1+ 1 -β β -α + 2(1 -β) β -α σ t +2 log 2 log 2 16(1-α)+log 2 1+ σ t )+ 6Ψ( B0 ) + 12σ t .The above result shows that when we run BFGS for N iterations, the total number of function and gradient evaluations isO N + N log(1 + σ N ) + N log(1 + Ψ( B0)+σ N) . Thus, the total line search complexity can always be bounded by O(N log(Ψ( B0 ) + σ)) = O(N max{log d, log κ, log C 0 }). Furthermore, notice that when N is sufficiently large such that we reach the superlinear convergence stage, i.e., N = Ω(Ψ( B0 ) + σ), the total line search complexity becomes O(N ), which means the average number of function and gradient evaluations per iteration is a constant O(1). We report the line search complexity results of different B 0 = LI and B 0 = µI in Appendix K.4. 
numerical experiments: 
 We conduct numerical experiments on a cubic objective function defined asEQUATIONand g : R → R is defined asEQUATIONwhere α, β, λ, ∆ ∈ R are hyper-parameters and {v i } n i=1 are standard orthogonal unit vectors in R d . We focus on this objective function because it is used in [26] to establish a tight lower bound for second-order methods. We compare the convergence paths of BFGS with an inexact line search step size η t that satisfies the Armijo-Wolfe conditions ( 5) and ( 6) for various initialization matrices B 0 : specifically, B 0 = LI, B 0 = µI, B 0 = I, and B 0 = cI where c is defined in Remark 6.2. It is easily verified that c ∈ [µ, L]. We also compare the performance of BFGS methods to the gradient descent (GD) method with backtracking line search, using α = 0.1 in condition ( 5) and β = 0.9 in condition (6) .Step size η t is chosen at each iteration via log bisection in Algorithm 1. Empirical results are compared across various dimensions d and condition numbers κ, with the x-axis representing the number of iterations t and the y-axis showing the ratio First, we observe that BFGS with B 0 = LI initially converges faster than BFGS with B 0 = µI in most plots, aligning with our theoretical findings that the linear convergence rate of BFGS with B 0 = LI surpasses that of B 0 = µI in Corollary 4.2. In Corollary 4.2, we show that BFGS with B 0 = LI could achieve the linear rate of (1 -1/κ) from the first iteration while BFGS with B 0 = µI needs to run d log κ to reach the same linear rate. Second, the transition to superlinear convergence for BFGS with B 0 = µI typically occurs around t ≈ d, as predicted by our theoretical analysis. Although BFGS with B 0 = LI initially converges faster, its transition to superlinear convergence consistently occurs later than for B 0 = µI. Notably, for a fixed dimension d = 600, the transition to superlinear convergence for B 0 = LI occurs increasingly later as the problem condition number rises, an effect not observed for B 0 = µI. This phenomenon indicates that the superlinear rate for B 0 = LI is more sensitive to the condition number κ, which corroborates our results in Corollary 6.5. In Corollary 6.5, we present that BFGS with B 0 = LI needs dκ steps to reach the superlinear convergence stage while this is improved to d log κ for BFGS with B 0 = µI. Moreover, the performance of BFGS with B 0 = I and B 0 = cI is similar to BFGS with B 0 = µI. Notice that the initializations of B 0 = I and B 0 = cI are two commonly-used practical choices of the initial Hessian approximation matrix B 0 .f (xt)-f (x * ) f (x0)-f (x * ) . 
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 an objective function that is µ-strongly convex with an L-Lipschitz gradient, BFGS achieves a global convergence rate of (1 -1/κ) t , where κ = L/µ. Additionally, assuming the Hessian is 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 B 0 = LI and B 0 = µI.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 class of quasi-Newton methods, including both BFGS and DFP, is a natural next step.Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: Lemma A.1. Suppose Assumptions 2.1, 2.2, and 2.3 hold, and recall the definitions of the matrices J t and G t in (8), and the quantity C t in (9) . Then, the following statements hold:(a) Suppose that f (x t+1 ) ≤ f (x t ) for any t ≥ 0, we have thatEQUATION(b) Suppose that f (x t+1 ) ≤ f (x t ) for any t ≥ 0 and τ ∈ [0, 1], we have thatEQUATION(c) For any t ≥ 0, we have thatEQUATION(d) For any t ≥ 0, we have thatEQUATION(e) For any t ≥ 0 and τ ∈ [0, 1], we have thatEQUATION(f) For any t ≥ 0 and τ , τ ∈ [0, 1], suppose that f (x t+1 ) ≤ f (x t ). Then, we have thatEQUATIONProof.(a) Recall the definition of J t in (8) . Using the triangle inequality, we have that∥∇ 2 f (x * ) -J t ∥ = 1 0 ∇ 2 f (x * ) -∇ 2 f (x t + τ (x t+1 -x t )) dτ ≤ 1 0 ∥∇ 2 f (x * ) -∇ 2 f (x t + τ (x t+1 -x t ))∥dτ.Moreover, it follows from Assumption 2.3 that∥∇ 2 f (x * ) -∇ 2 f (x t + τ (x t+1 -x t ))∥ ≤ M ∥(1 -τ )(x * -x t ) + τ (x * -x t+1 )∥ for any τ ∈ [0, 1]. Thus, we can further apply the triangle inequality to obtain∥∇ 2 f (x * ) -J t ∥ ≤ 1 0 M ∥(1 -τ )(x * -x t ) + τ (x * -x t+1 )∥dτ ≤ M ∥x t -x * ∥ 1 0 (1 -τ )dτ + M ∥x t+1 -x * ∥ 1 0 τ dτ = M 2 (∥x t -x * ∥ + ∥x t+1 -x * ∥).Since f is strongly convex, by Assumption 2.1 andf (x t+1 ) ≤ f (x t ), we have µ 2 ∥x t - x * ∥ 2 ≤ f (x t ) -f (x * ), which implies that ∥x t -x * ∥ ≤ 2(f (x t ) -f (x * ))/µ. Similarly, since f (x t+1 ) ≤ f (x t ), it also holds that ∥x t+1 -x * ∥ ≤ 2(f (x t+1 ) -f (x * ))/µ ≤ 2(f (x t ) -f (x * ))/µ.Hence, we obtain thatEQUATIONMoreover, notice that by Assumption 2.1, we also have J t ⪰ µI and ∇ 2 f (x * ) ⪰ µI. Hence, (37) implies that∇ 2 f (x * ) -J t ⪯ ∥∇ 2 f (x * ) -J t ∥I ⪯ M µ 3 2 2(f (x t ) -f (x * ))J t = C t J t , J t -∇ 2 f (x * ) ⪯ ∥J t -∇ 2 f (x * )∥I ⪯ M µ 3 2 2(f (x t ) -f (x * ))∇ 2 f (x * ) = C t ∇ 2 f (x * ).where we used the definition of C t in (9) . By rearranging the terms, we obtain (31) .(b) Similar to the arguments in (a), for any τ ∈ [0, 1], we have that∇ 2 f (x t + τ (x t+1 -x t )) -∇ 2 f (x * ) ≤ M ∥(1 -τ )(x t -x * ) + τ (x t+1 -x * )∥ ≤ M (1 -τ )∥x t -x * ∥ + τ ∥x t+1 -x * ∥ ≤ M (1 -τ ) 2 µ (f (x t ) -f (x * )) + τ 2 µ (f (x t+1 ) -f (x * )) ≤ M 2 µ (f (x t ) -f (x * ))Moreover, notice that by Assumption 2.1, we also have∇ 2 f (x t + τ (x t+1 -x t )) ⪰ µI and ∇ 2 f (x * ) ⪰ µI.The rest follows similarly as in the proof of (a) and we prove (32) .(c) Similar to the arguments in (a), we have that∇ 2 f (x * ) -∇ 2 f (x t ) ≤ M ∥x t -x * ∥ ≤ M √ µ 2(f (x t ) -f (x * )).Moreover, notice that by Assumption 2.1 we also have∇ 2 f (x t ) ⪰ µI and ∇ 2 f (x * ) ⪰ µI.The rest follows similarly as in the proof of (a) and we prove (33) .(d) Recall the definition of G t in (8) . Similar to the arguments in (a), we have that∥∇ 2 f (x * ) -G t ∥ = 1 0 ∇ 2 f (x * ) -∇ 2 f (x t + τ (x * -x t )) dτ ≤ 1 0 ∥∇ 2 f (x * ) -∇ 2 f (x t + τ (x * -x t ))∥dτ ≤ M 1 0 ∥(1 -τ )(x * -x t )∥dτ = M ∥x t -x * ∥ 1 0 (1 -τ )dτ = M 2 ∥x t -x * ∥ ≤ M √ µ 2(f (x t ) -f (x * )).Moreover, notice that by Assumption 2.1 we also have G t ⪰ µI and ∇ 2 f (x * ) ⪰ µI. The rest follows similarly as in the proof of (a) and we prove (34) .(e) Recall the definition of g t in (8) . Similar to the arguments in (a), for any τ ∈ [0, 1], we have that∇ 2 f (x t + τ (x * -x t )) -G t = 1 0 ∇ 2 f (x t + τ (x * -x t )) -∇ 2 f (x t + τ (x * -x t )) dτ ≤ 1 0 ∇ 2 f (x t + τ (x * -x t )) -∇ 2 f (x t + τ (x * -x t )) dτ ≤ 1 0 M |τ -τ |∥x t -x * ∥dτ ≤ 1 2 M ∥x t -x * ∥ ≤ M √ µ 2(f (x t ) -f (x * )).Moreover, notice that by Assumption 2.1, we also have ∇ 2 f (x t + τ (x * -x t )) ⪰ µI and G t ⪰ µI. The rest follows similarly as in the proof of (a) and we prove (35) .(f) Similar to the arguments in (a), for any τ , τ ∈ [0, 1], we have that∇ 2 f (x t + τ s t ) -∇ 2 f (x t + τ s t ) ≤ M |τ -τ |∥s t ∥ ≤ M ∥s t ∥ ≤ M (∥x t+1 -x * ∥ + ∥x t -x * ∥) ≤ M 2 µ (f (x t ) -f (x * )) + 2 µ (f (x t+1 ) -f (x * )) ≤ 2M 2 µ (f (x t ) -f (x * ))Moreover, notice that by Assumption 2.1, we also have ∇ 2 f (x t + τ s t ) ⪰ µI and ∇ 2 f (x t + τ s t ) ⪰ µI. The rest follows similarly as in the proof of (a) and we prove (36) .Recall that g t = ∇f (x t ). Given the condition in ( 5) and the fact that s t = η t d t , we havef (x t+1 ) ≤ f (x t ) + αg ⊤ t s t .Moreover, since B t is symmetric positive definite, we have -g ⊤ t s t = η t g ⊤ t B -1 t g t > 0 (unless g t = 0 and we are at the optimal solution). This further leads to the first claim, which isf (x t ) -f (x t+1 ) -g ⊤ t s t ≥ α.Similarly, the above argument implies that αg ⊤ t s t < 0 and as a result f (x t+1 ) ≤ f (x t ) and the last claim also follows.To prove the second claim, we leverage the condition in (6) . Specifically, if we subtract g ⊤ t d t from both sides of that condition, we obtain that (g t+1 -g t ) ⊤ d t ≥ (β -1)g ⊤ t d t Next, using the fact that s t = η t d t , by multiplying both sides by η t and use the simplification y t = g t+1 -g t we obtain thaty ⊤ t s t ≥ (β -1)g ⊤ t s t = -g ⊤ t s t (1 -β).Again using the argument that -g ⊤ t s t is positive (if we are not at the optimal solution), we can divide both sides of the above inequality by -g ⊤ t s t , leading to the second claim.First, we note that ĝ⊤ t ŝt = g ⊤ t s t and ŷ⊤ t ŝt = y ⊤ t s t . Using the definition of pt in ( 16), we have thatEQUATION)Hence, using the definition of θt in (14) and the definition of mt , nt in (16) , it follows that-ĝ ⊤ t ŝt ∥ĝ t ∥ 2 = (ĝ ⊤ t ŝt ) 2 ∥ĝ t ∥ 2 ∥ŝ t ∥ 2 ∥ŝ t ∥ 2 -ĝ ⊤ t ŝt = (ĝ ⊤ t ŝt ) 2 ∥ĝ t ∥ 2 ∥ŝ t ∥ 2 ∥ŝ t ∥ 2 ŷ⊤ t ŝt ŷ⊤ t ŝt -ĝ ⊤ t ŝt = nt cos 2 ( θt ) mt .Furthermore, we have ∥ĝ t ∥ 2 = qt (f (x t ) -f (x * )) from the definition of qt in (16) . Thus, the equality in (38) can be rewritten asf (x t ) -f (x t+1 ) = pt qt nt cos 2 ( θt ) mt (f (x t ) -f (x * )).By rearranging the term in the above equality, we obtainEQUATIONTo prove the inequality in (15) , note that for any t ≥ 1, we havef (x t ) -f (x * ) f (x 0 ) -f (x * ) = t-1 i=0 f (x i+1 ) -f (x * ) f (x i ) -f (x * ) = t-1 i=0 1 -pi qi ni cos 2 ( θi ) mi ,where the last equality is due to (39) . Note that all the terms of the form 1 -pi qi ni cos 2 ( θi) mi are non-negative, for any i ≥ 0. Thus, by applying the inequality of arithmetic and geometric means twice, we obtaint-1 i=0 1 -pi qi ni cos 2 ( θi ) mi ≤ 1 t t-1 i=0 1 -pi qi ni cos 2 ( θi ) mi t = 1 - 1 t t-1 i=0 pi qi ni cos 2 ( θi ) mi t ≤   1 - t-1 i=0 pi qi ni cos 2 ( θi ) mi 1 t   t .This completes the proof.D Results from [38] In this section, we summarize some results that we use from [38] to establish a lower bound on t-1 i=0 cos 2 ( θi) mi and qt . Proposition D.1 ([38, Proposition 2] ). Let {B t } t≥0 be the Hessian approximation matrices generated by the BFGS update in (3). For a given weight matrix P ∈ S d ++ , recall the weighted vectors defined in (11) and the weighted matrix in (12) . Then, we haveΨ( Bt+1 ) ≤ Ψ( Bt ) + ∥ŷ t ∥ 2 ŷ⊤ t ŝt -1 + log cos 2 θt mt , ∀t ≥ 0,where mt is defined in (16) and cos( θt ) is defined in (14) . As a corollary, we have,EQUATIONIf we take exponentiation on both sides of the above inequality (40) in Proposition D.1, we can obtain a lower bound for the productt-1 i=0 cos 2 ( θi) miwith the sum t-1 i=0 ∥ŷi∥ 2 ŝ⊤ i ŷi and Ψ( B0 ). This classical inequality describing the relationship between the ratio cos 2 ( θt) mt and the potential function Ψ(.) plays a critical role in the following convergence analysis.In the following two lemmas, we provide bounds on the quantities qt and ∥ŷ t ∥ 2 /ŝ ⊤ t ŷt respectively by directly citing results from Lemma 4 and Lemma 5 in [38] again. Notice that both qt and ∥ŷ t ∥ 2 /ŝ ⊤ t ŷt depend on different choices of the weight matrix P . (16) . Suppose Assumptions 2.1, 2.2, and 2.3 hold. Then we have the following results:Lemma D.2 ([38, Lemma 4]). Recall the definition qt = ∥ĝt∥ 2 f (xt)-f (x * ) in(a) If we choose P = LI, then qt ≥ 2/κ. Lemma 5] ). Let {x t } t≥0 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: Recall that we choose P = LI throughout the proof. Note that given this weight matrix, it can be easily verified that ∥ŷt∥ 2 ŝ⊤ t ŷt ≤ 1 for any t ≥ 0 by using Lemma D.3 (a). Hence, we use (40) in Proposition D.1 to obtain(b) If we choose P = ∇ 2 f (x * ), then qt ≥ 2/(1 + C t ) 2 . Lemma D.3 ([38,t-1 i=0 log cos 2 ( θi ) mi ≥ -Ψ( B0 ) + t-1 i=0 1 - ∥ŷ i ∥ 2 ŝ⊤ i ŷi ≥ -Ψ( B0 ),which further implies thatt-1 i=0 cos 2 ( θi ) mi ≥ e -Ψ( B0) .Moreover, for the choice P = LI, it can be shown that qt =∥gt∥ 2 L(f (xt)-f (x * )) ≥ 2κ by using Lemma D.2 (a). From Lemma 2.1, we know pt ≥ α and nt ≥ 1 -β, which lead tot-1 i=0 pi ni qi mi cos 2 ( θi ) ≥ t-1 i=0 pi t-1 i=0 qi t-1 i=0 ni t-1 i=0 cos 2 ( θi ) mi ≥ 2α(1 -β) κ t e -Ψ( B0) .Thus, it follows from Proposition 3.1 thatf (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤   1 - t-1 i=0 pi qi ni mi cos 2 ( θi ) 1 t   t ≤ 1 -e -Ψ( B0 ) t 2α(1 -β) κ t .This completes the proof.Notice that in the first case where B 0 = LI, we have Ψ( B0 ) = 0 and thus it achieves the best linear convergence results according to Theorem 4.1. On the other hand, for B 0 = µI, we haveΨ( B0 ) = Ψ( µ L I) = d( 1 κ -1 + log κ) ≤ d log κ.We complete the proof by combining these conditions with the inequality (17) in Theorem 4.1. Notice that e -x ≥ e -1 ≥ 1 3 for x ≤ 1.F.1 Proof of Proposition 5.1Recall that we choose the weight matrix as P = ∇ 2 f (x * ) 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 qt andcos 2 ( θt)mt . Specifically, by using Lemma D.3 (b), we have ∥ŷt∥ 2 ŝ⊤ t ŷt ≤ 1 + C t for any t ≥ 0. Hence, we use (40) in Proposition D.1 to obtainEQUATIONMoreover, since qt ≥ 2 (1+Ct) 2 for any t ≥ 0 by using Lemma D.2 (b), we getEQUATIONwhere we use the inequality 1 + x ≤ e x for any x ∈ R. From Lemma 2.1, we know pt ≥ α and nt ≥ 1 -β, which lead toEQUATIONCombining ( 41), ( 42), ( 43) and ( 15) from Proposition 3.1, we prove thatf (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤   1 - t-1 i=0 pi qi ni mi cos 2 ( θi ) 1 t   t ≤ 1 -2α(1 -β)e -Ψ( B0 )+3 t-1 i=0 C i t t .This completes the proof.When we have t ≥ Ψ( B0 ) + 3t-1 i=0 C i , Proposition 5.1 implies the condition that f (xt)-f (x * ) f (x0)-f (x * ) ≤ 1 -2α(1-β) e t ≤ 1 -2α(1-β) 3 t, which leads to the linear rate in (20) . Hence, it is sufficient to establish an upper bound on (9) .t-1 i=0 C i . Recall that C i = M µ 3 2 2(f (x i ) -f (x * )) defined inWe decompose the sum into two parts:⌈Ψ( B0)⌉-1 i=0 C i and t i=⌈Ψ( B0)⌉ C i .For the first part, note that since f (x i+1 ) ≤ f (x i ) by Lemma 2.1, we also have C i+1 ≤ C i for i ≥ 0. Hence, we have⌈Ψ( B0)⌉-1 i=0 C i ≤ C 0 ⌈Ψ( B0 )⌉ ≤ C 0 (Ψ( B0 ) + 1). Moreover, by Theorem 4.1, when t ≥ Ψ( B0 ) we have f (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤ 1 -e -Ψ( B0 ) t 2α(1 -β) κ t ≤ 1 - 2α(1 -β) eκ t ≤ 1 - 2α(1 -β) 3κ t .Hence, this further implies thatt i=⌈Ψ( B0)⌉ C i = C 0 t i=⌈Ψ( B0)⌉ f (x i ) -f (x * ) f (x 0 ) -f (x * ) ≤ C 0 t i=⌈Ψ( B0)⌉ 1 - 2α(1 -β) 3κ i 2 ≤ C 0 ∞ i=1 1 - 2α(1 -β) 3κ i 2 ≤ C 0 3κ α(1 -β) -1 ,where we used the fact that∞ i=1 (1 -ρ) i 2 = √ 1-ρ 1- √ 1-ρ = √ 1-ρ+1-ρ ρ ≤ 2ρ -1 for any ρ ∈ (0, 1). Hence, by combining both inequalities, we haveEQUATIONHence, this proves that ( 20) is satisfied whent ≥ Ψ( B0 ) + 3C 0 Ψ( B0 ) + 9C0κ α(1-β) .F.3 Proof of Corollary 5.3For B 0 = LI, we have B0 = 1 L B 0 = I and B0 = ∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2 = L∇ 2 f (x * ) -1 .Thus, it holds that Ψ( B0 ) = Ψ(I) = 0. Moreover, by Assumptions 2.1 and 2.2, we have1 L I ⪯ ∇ 2 f (x * )-1 ⪯ 1 µ I, which implies that I ⪯ B0 ⪯ κI. Thus, we further haveΨ( B0 ) ≤ Tr(κI) -d -log Det(I) = dκ -d ≤ dκ.Combining these two results, the threshold for transition time can be bounded by Ψ( B0 ) + 3C 0 Ψ( B0 ) + For B 0 = µI, we have B0 = 1 L B 0 = 1 κ I and B0 = ∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2 = µ∇ 2 f (x * ) -1 .Thus, it holds that Ψ( B0 ) = Ψ(1 κ I) = d κ -d + d log κ ≤ d log κ.Moreover, by Assumptions 2.1 and 2.2, we have 1 κ I ⪯ B0 ⪯ I. This implies thatΨ( B0 ) = Tr( B0 ) -d -log Det( B0 ) ≤ Tr(I) -d -log Det( 1 κ I) = d log κ.Combining these two results, the threshold for the transition tume can be bounded byΨ( B0 ) + 3C 0 Ψ( B0 ) + 9 α(1-β) C 0 κ ≤ (1 + 3C 0 )d log κ + 9 α(1-β) C 0 κ.Hence, by Theorem 5.2, the linear rate in (20) is satisfied when t ≥ (1 + 3C 0 )d log κ + 9 α(1-β) C 0 κ.To present our result we first introduce the following functionEQUATIONwhich is defined for x > -1. Further In the next result, we present some basic properties of the function ω(x) defined in (45). Lemma G.1. Recall the definition of function ω(x) in (45), we have that (a) ω(x) is increasing function for x > 0 and decreasing function for -1 < x < 0. Moreover, ω(x) ≥ 0 for all x > -1.(b) When x ≥ 0, we have that ω(x) ≥ x 2 2(1+x) . (c) When -1 < x ≤ 0, we have that ω(x) ≥ x 2 2+x .Proof. Notice that ω ′ (x) = x 1+x , we know that when x > 0, ω ′ (x) > 0 and when -1 < x < 0, ω ′ (x) < 0, ω ′ (x) < 0. Therefore, ω(x) is increasing function for x > 0 and ω(x) is decreasing function for -1 < x < 0. Hence, ω(x) ≥ ω(0) = 0 for all x > -1.ω(x) ≥ x 2 2(1+x) is equivalent to ω 1 (x) := 2(1 + x)ω(x) -x 2 ≥ 0. Since ω ′ 1 (x) = 2x - 2 log (1 + x) = 2ω(x) ≥ 0 for all x > -1, we know that ω 1 (x) is increasing function for x > -1 and hence, ω 1 (x) ≥ ω 1 (0) = 0 for x ≥ 0. ω(x) ≥ x 2 2+x is equivalent to ω 2 (x) := (2+x)ω(x)-x 2 ≥ 0. Since ω ′ 2 (x) = x 1+x -log (1 + x) ≤ 0 for all x > -1, we know that ω 2 (x) is decreasing function for x > -1 and hence, ω 2 (x) ≥ ω 2 (0) = 0 for x ≤ 0.Proposition G.2. Let {B t } t≥0 be the Hessian approximation matrices generated by the BFGS update in (3). Suppose Assumptions 2.1, 2.2, and 2.3 hold and f (x t+1 ) ≤ f (x t ) for any t ≥ 0. Recall the definition of Ψ(.) in (10) and C t in (9), we have thatEQUATIONProof. First, taking the trace and determinant on both sides of the equation ( 13) for any weight matrix P ∈ S d ++ and using results from Lemma 6.2 of [34] , we show that EQUATION∥ĝ t ∥ 2 -ĝ ⊤ t dt -log -ĝ ⊤ t dt ∥ dt ∥ 2 -1 = Ψ( Bt ) -Ψ( Bt+1 ) + ∥ŷ t ∥ 2 ŝ⊤ t ŷt -1 + log ∥ŝ t ∥ 2 ŝ⊤ t ŷt.Note that given the fact that -ĝ ⊤ t dt = ĝ⊤ t B-1 t ĝt > 0, by using the Cauchy-Schwarz inequality weobtain ∥ĝt∥ 2 -ĝ ⊤ t dt ≥ -ĝ ⊤ t dt∥ dt∥ 2 . Hence, we can write-ĝ ⊤ t dt ∥ dt ∥ 2 -log -ĝ ⊤ t dt ∥ dt ∥ 2 -1 ≤ Ψ( Bt ) -Ψ( Bt+1 ) + ∥ŷ t ∥ 2 ŝ⊤ t ŷt -1 + log ∥ŝ t ∥ 2 ŝ⊤ t ŷt. Now, by selecting the weight matrix as P = ∇ 2 f (x * ), many expressions get simplified and we haveEQUATION2 . Hence, we have ≤ log(1 + C t ) ≤ C t for any t ≥ 0 by using (31) from Lemma A.1. Leveraging these conditions with the inequality (47), we obtain that ω(ρ t -1) ≤ Ψ( Bt ) -Ψ( Bt+1 ) + 2C t .EQUATIONSumming both sides of the above inequality from i = 0 to t -1, we prove the conclusiont-1 i=0 ω(ρ i -1) ≤ Ψ( B0 ) -Ψ( Bt ) + 2 t-1 i=0 C i ≤ Ψ( B0 ) + 2 t-1 i=0 C i ,where the last inequality holds since Ψ( Bt ) ≥ 0.Lemma G.3. Suppose Assumptions 2.1, 2.2, and 2.3 hold and C t ≤ 1 6 and ρ t ≥ 7 8 at iteration t, then we haveEQUATIONProof. Since assumption 2.3 hold, using Lemma 1.2.4 in [44] , we have that|f (y) -f (x) -∇f (x) ⊤ (y -x) - 1 2 (y -x) ⊤ ∇ 2 f (x)(y -x)| ≤ M 6 ∥y -x∥ 3 , ∀x, y ∈ R d .Setting x = x t and y = x t + d t , we have thatEQUATION)Notice that using (33) from Lemma A.1 and the definition of ρ t in (21), we have thatEQUATIONApplying Assumption 2.1 with the definition dt = ∇ 2 f (x * ) 1 2 d t , we obtain that∥d t ∥ 3 ≤ 1 µ 3 2 ∥ dt ∥ 3 = -g ⊤ t d t µ 3 2 ∥ dt ∥ 2 -g ⊤ t d t ∥ dt ∥ = -g ⊤ t d t µ 3 2 1 ρ t ∥ dt ∥.Since -g ⊤ t dt ≤ ∥g t ∥∥ dt ∥ by Cauchy-Schwarz inequality where gt = ∇ 2 f (x * )-1 2 g t , we obtain∥ dt ∥ = ∥g t ∥ ∥ dt ∥ ∥g t ∥ ≤ ∥g t ∥ ∥ dt ∥ 2 -g ⊤ t dt = 1 ρ t ∥g t ∥,which leads toEQUATIONBy applying Taylor's theorem with Lagrange remainder, there exists τt ∈ [0, 1] such thatEQUATIONwhere we used the fact that ∇f (x * ) = 0 in the last equality. Moreover, by the fundamental theorem of calculus, we have∇f (x t ) -∇f (x * ) = 1 0 ∇ 2 f (x t + τ (x * -x t ))(x t -x * ) dτ = G t (x t -x * ),where we use the definition of G t in (8) . Since ∇f (x * ) = 0 and we denote g t = ∇f (x t ), this further implies thatEQUATIONCombining ( 52) and (53) leads toEQUATIONBased on (35) in Lemma A.1, we have ∇ 2 f (x t + τt (x * -x t )) ⪰ 1 1+Ct G t , which implies thatG -1 t ∇ 2 f (x t + τt (x * -x t ))G -1 t ⪰ 1 1 + C t G -1 t .Moreover, it follows from (34) in Lemma A.1 thatG t ⪯ (1 + C t )∇ 2 f (x * ), which implies that G -1 t ⪰ 1 1 + C t (∇ 2 f (x * )) -1 .Combining the above two conditions, we obtain thatG -1 t ∇ 2 f (x t + τt (x * -x t ))G -1 t ⪰ 1 (1 + C t ) 2 (∇ 2 f (x * )) -1 ,and henceg ⊤ t G -1 t ∇ 2 f (x t + τt (x * -x t ))G -1 t g t ≥ 1 (1 + C t ) 2 g ⊤ t (∇ 2 f (x * )) -1 g t = 1 (1 + C t ) 2 ∥g t ∥ 2 . (55)Combining (54) and (55) leads toEQUATIONCombining ( 51) and (56) leads toEQUATIONLeveraging ( 49), ( 50) and (57) with the definition of C t in (9), we have thatEQUATION).(58)Notice that -g ⊤ t d t = -g ⊤ t B -1 t g t > 0 and when C t ≤ 1 6 and ρ t ≥ 7 8 , we can verify that1 + C t 2ρ t + C t (1 + C t ) 6ρ 2 t < 1.Therefore, (58) implies the conclusion thatf (x t + d t ) -f (x t ) ≤ 0.G.2 Proof of Lemma 6.1Since η t = 1 satisfies Armijo-Wolfe conditions, we know that η t is chosen to be one at iteration t and x t+1 = x t + d t . We have f (x t+1 ) ≤ f (x t ) from Lemma 2.1. Using Taylor's expansion, we have that f(x t+1 ) = f (x t ) + g ⊤ t d t + 1 2 d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t , where τ ∈ [0, 1]. Hence, we have that pt = f (x t ) -f (x t+1 ) -g ⊤ t d t = -g ⊤ t d t -1 2 d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t -g ⊤ t d t = 1 - 1 2 d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t -g ⊤ t d t ≥ 1 - 1 + C t 2 d ⊤ t ∇ 2 f (x * )d t -g ⊤ t d t = 1 - 1 + C t 2ρ t ,where we apply the (32) from Lemma A.1 since f (x t+1 ) ≤ f (x t ) and recall the definition of ρ t in (21) . Similarly, using (31) from Lemma A.1 since f (x t+1 ) ≤ f (x t ), we have thatnt = y ⊤ t s t -g ⊤ t s t = s ⊤ t J t s t -g ⊤ t s t = d ⊤ t J t d t -g ⊤ t d t ≥ 1 1 + C t d ⊤ t ∇ 2 f (x * )d t -g ⊤ t d t = 1 (1 + C t )ρ t ,where we use the fact that y t = J t s t with J t defined in (8) and s t = x t+1 -x t = d t . Therefore, we prove the conclusions.G. (x t+1 ) = f (x t ) + g ⊤ t d t + 1 2 d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t , where τ ∈ [0, 1]. Hence, we have f (x t ) -f (x k+1 ) -g ⊤ t d t = -g ⊤ t d t -1 2 d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t -g ⊤ t d t = 1 - 1 2 d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t -g ⊤ t d t ≥ 1 - 1 + C t 2 d ⊤ t ∇ 2 f (x * )d t -g ⊤ t d t = 1 - 1 + C t 2ρ t ,where we apply the (32) from Lemma A.1 since f (x t+1 ) ≤ f (x t ). Therefore, whenC t ≤ δ 1 ≤ 2(1 -α) -1 and ρ t ≥ δ 2 ≥ 1 √ 2(1-α), we obtain thatf (xt)-f (x k+1 ) -g ⊤ t dt≥ 1 -1+Ct 2ρt ≥ α and unit step size η t = 1 satisfies the sufficient condition (5).Similarly, using (31) from Lemma A.1 since f (x t+1 ) ≤ f (x t ) and denote ḡk+1 = ∇f (x t+1 ), ȳt = ḡk+1 -g t , we have thatȳ⊤ t st -g ⊤ t st = s⊤ t J t st -g ⊤ t st = d ⊤ t J t d t -g ⊤ t d t ≥ 1 1 + C t d ⊤ t ∇ 2 f (x * )d t -g ⊤ t d t = 1 (1 + C t )ρ t .Therefore, whenC t ≤ δ 1 ≤ 1 √ 1-β -1 and ρ t ≤ δ 3 = 1 √ 1-β , we obtain that ȳ⊤ t st -g ⊤ t st ≥ 1 (1+Ct)ρt ≥ 1 -β, which indicates that ḡ⊤ t+1 d t = ḡ⊤ t+1 st = ȳ⊤ t st + g ⊤ t st ≥ -g ⊤ t st (1 -β) + g ⊤ t st = βg ⊤ t st = βg ⊤ t d t .Hence, unit step size η t = 1 satisfies the curvature condition (6) . Therefore, we prove that when C t ≤ δ 1 and δ 2 ≤ ρ t ≤ δ 3 , step size η t = 1 satisfies the Armijo-Wolfe conditions ( 5) and (6) .Since in Theorem 4.1, we already prove thatf (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤ 1 -e -Ψ( B0 ) t 2α(1 -β) κ t .This implies thatC t ≤ 1 -e -Ψ( B0 ) t 2α(1 -β) κ t 2 C 0 .When t ≥ Ψ( B0 ), we obtain thatC t ≤ 1 - 2α(1 -β) 3κ t 2 C 0 .When t ≥ 3κ α(1-β) log C0 δ1 , we obtain thatC t ≤ 1 - 2α(1 -β) 3κ t 2 C 0 ≤ δ 1 .Therefore, the first claim in (24) follows.I 1 = {t : ρ t < δ 2 } and I 2 = {t : ρ t > δ 3 }, we know that |I| = |I 1 | + |I 2 |.Notice that for t ∈ I 1 , we have that ρ t -1 < δ 2 -1 < 0 since δ 2 < 1 and the function ω(x) defined in (45) is decreasing for -1 < x < 0 from (a) in Lemma G.1. Hence, we have thati∈I1 ω(ρ i -1) ≥ i∈I1 ω(δ 2 -1) = ω(δ 2 -1)|I 1 |.Similarly, we have that for t ∈ I 2 , we have that ρ i -1 > δ 3 -1 > 0 since δ 3 > 1 and the function ω(x) is increasing for x > 0 from (a) in Lemma G.1. Hence, we have that i∈I2 ω(ρ i -1) ≥ i∈I2 ω(δ 3 -1) = ω(δ 3 -1)|I 2 |. Using (46) from Proposition G.2, we have thatt-1 i=0 ω(ρ i -1) ≤ Ψ( B0 ) + 2 t-1 i=0 C i ≤ Ψ( B0 ) + 2 +∞ i=0 C i for any t ≥ 1. Therefore, we obtain that Ψ( B0 ) + 2 +∞ i=0 C i ≥ +∞ i=0 ω(ρ i -1) ≥ i∈I1 ω(β i -1) + i∈I2 ω(β i -1) ≥ ω(δ 2 -1)|I 1 | + ω(δ 3 -1)|I 2 | ≥ min{ω(δ 2 -1), ω(δ 3 -1)}(|I 1 | + |I 2 |),which leads to the resultEQUATIONwhere δ 4 := 1 min{ω(δ2-1),ω(δ3-1)} . Using the upper bound of 44), we prove the second claim in (25) .+∞ i=0 C i ≤ C 0 Ψ( B0 ) + 3C0κ α(1-β) in (First, we prove that for any initial point x 0 ∈ R d and any initial Hessian approximation matrix B 0 ∈ S d ++ , the following result holds:f (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤ δ 6 t 0 + δ 7 Ψ( B0 ) + δ 8 +∞ i=0 C i t t , ∀t > t 0 ,where t 0 is defined in (24) . We choose the weight matrix as P = ∇ 2 f (x * ) throughout the proof. Using results ( 41) and ( 42) from the proof of Proposition 5.1, we obtain thatEQUATION)Recall the definition of the set I = {t : ρ t / ∈ [δ 2 , δ 3 ]}. Notice that for t ≥ t 0 , defineEQUATION)From Lemma 2.1, we know pt ≥ α and nt ≥ 1 -β for any t ≥ 0, which lead toEQUATIONEQUATION)where the second inequality holds since |I 3 | ≤ log 1 2α(1-β) > 0 and the last inequality holds since (59) from the proof of Lemma 6.3 in Appendix G.4. Notice that when index i ∈ I 4 , we have C i ≤ δ 1 from Lemma 6.3 and ρ i ∈ [δ 2 , δ 3 ]. Applying Lemma 6.1 and Lemma 6.2, we know that for i ∈ I 4 , η i = 1 satisfies the Armijo-Wolfe conditions ( 5), ( 6) and we have pi ≥ 1 -1+Ci 2ρi > 0 (sinceC i ≤ δ 1 ≤ 1 6 , ρ i ≥ δ 2 ≥ 7 8) and ni ≥ 1 (1+Ci)ρi from (22) . Hence, we obtain thatEQUATIONwhere the last inequality holds since 1 1+Ci ≥ e -Ci . Using the fact that log x ≥ 1 -1 x , we obtainEQUATION)where the second inequality holds since ω(ρ i -1) ≥ 0 and the third inequality holds since ρ i ≥ δ 2 due to i ∈ I 4 and C i ≤ δ 1 due to i ≥ t 0 and Lemma 6.3. Notice thatEQUATION)Similarly, when ρ i < 1, using log ρ i ≥ 1 -1 ρi , (c) in Lemma G.1 and ρ i ≥ δ 2 due to i ∈ I 4 , we haveEQUATIONCombining ( 66), ( 67) and (68), we obtain thati∈I4 (2 - 1 + C i ρ i ) 1 ρ i ≥ i∈I4 e -2(ρ i -1) log ρ i +(1-log δ 2 )C i 2δ 2 -1-δ 1 = i∈I4 e -2(ρ i -1) log ρ i 2δ 2 -1-δ 1 i∈I4 e -(1-log δ 2 )C i 2δ 2 -1-δ 1 = i∈I4,ρi<1 e -2(ρ i -1) log ρ i 2δ 2 -1-δ 1 i∈I4,ρi≥1 e -2(ρ i -1) log ρ i 2δ 2 -1-δ 1 i∈I4 e -(1-log δ 2 )C i 2δ 2 -1-δ 1 ≥ i∈I4,ρi<1 e - 2(1+ 1 δ 2 )ω(ρ i -1) 2δ 2 -1-δ 1 i∈I4,ρi≥1e -4δ 3 ω(ρ i -1)EQUATION)where δ 5 = max{ 65) and ( 69), we obtain that2+ 2 δ 2 2δ2-1-δ1 , 4δ3 2δ2-1-δ1 }. Combining (EQUATIONwhere the last inequality is due to (46) from Lemma G.1. Combining (62), ( 63), ( 64) and (70), we obtain thatEQUATIONLeveraging ( 60), ( 61), ( 71) with ( 15) from Proposition 3.1, we prove thatf (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤   1 - t-1 i=0 pi qi ni cos 2 ( θi ) mi 1 t   t =   1 - t-1 i=0 pi ni t-1 i=0 qi t-1 i=0 cos 2 ( θi ) mi 1 t   t ≤ 1 -e - t 0 log 1 2α(1-β) +(1+δ 4 log 1 2α(1-β) +δ 5 )Ψ( B0 )+(3+2δ 4 log 1 2α(1-β) +2δ 5 + 2δ 2 -δ 1 -log δ 2 2δ 2 -1-δ 1 ) +∞ i=0 C i t t = 1 -e -δ 6 t 0 +δ 7 Ψ( B0 )+δ 8 +∞ i=0 C i t t ≤ δ 6 t 0 + δ 7 Ψ( B0 ) + δ 8 +∞ i=0 C i t t ,where the inequality is due to the fact that 1 -e -x ≤ x for any x ∈ R and δ 6 , δ 7 , δ 8 are defined in Theorem 6.4. Hence, we prove thatEQUATIONUsing ( 44) from the proof of Theorem 5.2 in Appendix F.2, we have thatEQUATION)Notice that from (24) in Lemma 6.3, we have thatEQUATION)Leveraging ( 72), ( 73) and (74), we prove the conclusion.G.6 Proof of Corollary 6.5Using the fact that for B 0 = LI, we have Ψ( B0 ) = 0 and Ψ( B0 ) ≤ dκ, and for the case that B 0 = µI, we have Ψ( B0 ) ≤ d log κ, and Ψ( B0 ) ≤ d log κ, we obtain the corresponding superlinear results for these two conditions.i } 8 i=1As we stated before, all the {δ i } 8 i=1 are universal constants that only depend on line search parameters α and β. We can choose specific values of α and β to make definitions of {δ i } 8 i=1 more clear. If we pick α = 1 4 and β = 3 4 , we have that δ 1 = 1 6 , δ 2 = 7 8 , δ 3 = 2, δ 4 =Ψ( B0 ) = Ψ(c∇ 2 f (x * ) -1 ) = cTr(∇ 2 f (x * ) -1 ) - d -log Det(c∇ 2 f (x * ) -1), which is determined by the Hessian matrix ∇ 2 f (x * ) -1 . In this case, one can use the upper boundsΨ( B0 ) = d( c L -1 + log L c ) and Ψ( B0 ) = Tr(c∇ 2 f (x * ) -1 ) -d - log Det(c∇ 2 f (x * ) -1 ) ≤ d( c µ -1 + log L c) to simplify the expressions. Applying these values of Ψ( B0 ) and Ψ( B0 ) to our linear convergence result in Theorem 4.1 and the superlinear convergence result in Theorem 6.4, we can obtain the following convergence guarantees for B 0 = cI:• For t ≥ d( c L -1 + log L c ), we have f (xt)-f (x * ) f (x0)-f (x * ) ≤ 1 -2α(1-β) 3κ t ; • For t = Ω(d( c µ -1 + log L c ) + C 0 d( c L -1 + log L c ) + C 0 κ), we have f (xt)-f (x * ) f (x0)-f (x * ) ≤ O d( c µ -1+log L c )+C0d( c L -1+log L c )+C0κ t t .Moreover, we can derive similar iteration complexity bounds following the same arguments as in Section I. We also include the performance of BFGS with B 0 = cI in our numerical experiments as presented in Figure 1 . We observe that the performance of BFGS with B 0 = cI is very similar to the convergence curve of BFGS with B 0 = µI in our numerical experiments.When B 0 = LI, if we regard the line search parameters α and β as absolute constants, the first result established in Corollary 4.2 leads to a global complexity of O(κ log 1 ϵ ), which is on par with gradient descent. Moreover, the first result in Corollary 5.3 implies a complexity of O (d + C 0 )κ + log 1 ϵ , 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 ϵ from the condition number-independent linear rate. For the analysis of the superlinear convergence rate, we denote that Ω L = dκ + C 0 κ. From the first result in Corollary 6.5, we have thatf (x t ) -f (x * ) f (x 0 ) -f (x * ) ≤ ( Ω L t ) tLet T * be the number such that the inequality ( Ω L t ) t ≤ ϵ above becomes equality. we havelog 1 ϵ = T * log T * Ω L ≤ T * ( T * Ω L -1), T * ≥ Ω L + Ω 2 L + 4Ω L log 1 ϵ 2 .Hence, we have thatlog 1 ϵ = T * log T * Ω L ≥ T * log Ω L + Ω 2 L + 4Ω L log 1 ϵ 2Ω L ≥ T * log   1 2 + 1 4 + log 1 ϵ Ω L   , T * ≤ log 1 ϵ log 1 2 + 1 4 + log 1 ϵ Ω L .Hence, to reach the accuracy of ϵ, we need the number of iterations t to be at leastt ≥ log 1 ϵ log 1 2 + 1 4 + 1 Ω L log 1 ϵ .Therefore, the iteration complexity for the case ofB 0 = LI is O   min    κ log 1 ϵ , (d + C 0 )κ + log 1 ϵ , log 1 ϵ log 1 2 + 1 4 + 1 dκ+C0κ log 1 ϵ      .Similarly, in this case of B 0 = µI, the second result in Corollary 4.2 establishes a global complexity of O d log κ + κ log 1 ϵ , where the first term represents the number of iterations before the linear convergence rate in (19) begins, and the second term arises from the linear rate itself. Additionally, following the same argument, the second result in Corollary 5.3 indicates a complexity ofO(C 0 d log κ + C 0 κ + log 1 ϵ ).Here, the first term accounts for the wait time until the convergence rate takes effect, and the second term is associated with the condition number-independent linear rate. For the superlinear convergence rate, when B 0 = µI, to reach the accuracy of ϵ, we need the number of iterations t to be at leastt ≥ log 1 ϵ log 1 2 + 1 4 + 1 Ωµ log 1 ϵ ,whereΩ µ = C 0 d log κ + C 0 κ.The proof is the same as the proof for the case of B 0 = LI. Therefore, the iteration complexity for the case ofB 0 = µI is O   min    d log κ + κ log 1 ϵ , C 0 (d log κ + κ) + log 1 ϵ , log 1 ϵ log 1 2 + 1 4 + 1 C0(d log κ+κ) log 1 ϵ      .Require:EQUATIONmin = 0, η (0) max = +∞ 1: for i = 0, 1, 2, . . . do 2: if f (x t + η (i) d t ) > f (x t ) + αη (i) ∇f (x t ) ⊤ d t then 3: Set η (i+1) max = η (i) and η (i+1) min = η (i) min 4: if η (i) min = 0 then 5: η (i+1) = ( 1 2 ) 2 i+1 -1 6:else 7:η (i+1) = η (i+1) max η (i+1) min 8:end if9: else if ∇f (x t + η (i) d t ) ⊤ d t < β∇f (x t ) ⊤ d t then 10: Set η (i+1) max = η (i)max and η(i+1) min = η (i) 11: if η (i) max = +∞ then 12: η (i+1) = 2 2 i+1 -113: else 14: First, we present major results concerning the complexity of the bisection method, which specifies a range of values that meet the conditions in ( 5) and ( 6). Lemma K.1. Suppose that Assumptions 2.1, 2.2 and 2.3 hold. Recall the definition of ρ t in (21) and C t in (9) . At iteration t, there is unique η r > 0 such that the sufficient decrease condition (5) is equity for η r , i.e.,EQUATIONEQUATIONThen, η t satisfies the sufficient decrease condition (5) if and only if η t ≤ η r . We also have thatEQUATIONSimilarly, there is also unique η l > 0 such that the curvature condition (6) is equity for η l , i.e.,EQUATIONThen, η t satisfies the curvature condition (6) if and only if η t ≥ η l . Moreover, we have thatEQUATIONProof. Notice that Assumption 2.1 indicates that the objective function f (x) is strongly convex.Consider function h 1 (η) = f (x t + ηd t ) -αη∇f (x t ) ⊤ d t . We observe that this function h 1 (η) is strongly convex and h 1 (0) = f (x t ), h ′ 1 (0) < 0. Hence, there is unique η r > 0 such that h 1 (η r ) = f (x t ) and η t ≤ η r if and only if f (x t + η t d t ) ≤ f (x t ) + αη t ∇f (x t ) ⊤ d t .Denote that xt+1 = x t +η r d t . We know that f(x t+1 )-f (x t ) = αη r g ⊤ t d t . Since f (x t+1 )-f (x t ) = η r g ⊤ t d t + 1 2 η 2 r d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t for τ ∈ (0, 1), we have that η r g ⊤ t d t + 1 2 η 2 r d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t = αη r g ⊤ t d t , η r = 2(1 -α) -g ⊤ t d t d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t .which leads toη r = 2(1 -α) -g ⊤ t d t d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t ≤ 2(1 -α)(1 + C t ) -g ⊤ t d t d ⊤ t ∇ 2 f (x * )d t = 2(1 -α)(1 + C t ) -g ⊤ t d t ∥ dt ∥ 2 = 2(1 -α)(1 + C t )ρ t . η r = 2(1 -α) -g ⊤ t d t d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t ≥ 2(1 -α) 1 + C t -g ⊤ t d t d ⊤ t ∇ 2 f (x * )d t = 2(1 -α) 1 + C t ρ t .where we use the (32) from Lemma A.1 and the fact that f(x t+1 ) = f (x t ) + αη r g ⊤ t d t ≤ f (x t ). Hence, we prove the results in (76).Similarly, consider function h 2 (η) = ∇f (x t + ηd t ) ⊤ d t . We observe that this function h 2 (η) is strictly increasing function for η ≥ 0 andh 2 (0) = ∇f (x t ) ⊤ d t < β∇f (x t ) ⊤ d t , h 2 (η exact ) = ∇f (x t + η exact d t ) ⊤ d t = 0 > β∇f (x t ) ⊤ d t where η exact := arg min η>0 f (x t + ηd t ) is the exact line search step size satisfying ∇f (x t + η exact d t ) ⊤ d t = 0. Hence, there is unique η l ∈ (0, η exact ) such that h 2 (η l ) = β∇f (x t ) ⊤ d t and η t ≥ η l if and only if ∇f (x t + η t d t ) ⊤ d t ≥ β∇f (x t ) ⊤ d t .Notice thatf (x t + η r d t ) = f (x t ) + αη r ∇f (x t ) ⊤ d t .Using mean value theorem, we know there exists η ∈ (0, η r ) such thatf (x t + η r d t ) = f (x t ) + η r ∇f (x t + ηd t ) ⊤ d t .The above two equities indicates that∇f (x t + ηd t ) ⊤ d t = α∇f (x t ) ⊤ d t .Recall that∇f (x t + η l d t ) ⊤ d t = β∇f (x t ) ⊤ d t .Combing the above two equities, we obtain that(∇f (x t + ηd t ) -∇f (x t + η l d t )) ⊤ d t = -∇f (x t ) ⊤ d t (β -α).Using mean value theorem again, we know there exists η ∈ (η l , η) such that(∇f (x t + ηd t ) -∇f (x t + η l d t )) ⊤ d t = (η -η l )d ⊤ t ∇ 2 f (x t + ηd t )d t .Leveraging the above two equities, we obtain thatη -η l = (β -α) -∇f (x t ) ⊤ d t d ⊤ t ∇ 2 f (x t + ηd t )d t .Notice that η ≤ η r , we have thatEQUATIONRecall the definition of η l in (77), we have that(∇f (x t + η l d t ) -∇f (x t )) ⊤ d t = -(1 -β)∇f (x t ) ⊤ d t .Notice that there exists η ∈ (0, η l ), such that(∇f (x t + η l d t ) -∇f (x t )) ⊤ d t = η l d ⊤ t ∇ 2 f (x t + ηd t )d t .Combing the above two equities, we obtain thatEQUATIONLeveraging ( 79) and (80), we have thatη r η l = 1 + η r -η l η l ≥ 1 + (β -α)d ⊤ t ∇ 2 f (x t + ηd t )d t (1 -β)d ⊤ t ∇ 2 f (x t + ηd t )d t .Recall that xt+1 = x t + η r d t and notice that η ≤ η r , η ≤ η r . We have that x t + ηd t = x t + τ (x t+1 -x t ) and x t + ηd t = x t + τ (x t+1 -x t ) with τ = η ηr ∈ (0, 1) and τ = η ηr ∈ (0, 1). Since (36) in Lemma A.1, we prove the conclusion that f (x t+1 ) = f (x t + η r d t ) = f (x t ) + αη r ∇f (x t ) ⊤ d t ≤ f (x t ), applyingη r η l ≥ 1 + (β -α)d ⊤ t ∇ 2 f (x t + ηd t )d t (1 -β)d ⊤ t ∇ 2 f (x t + ηd t )d t = 1 + (β -α)d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t (1 -β)d ⊤ t ∇ 2 f (x t + τ (x t+1 -x t ))d t ≥ 1 + β -α (1 -β)(1 + 2C t ) . K.2EQUATIONProof. At the first iteration, if η (0) = 1 satisfies the weak Wolfe conditions ( 5) and ( 6), the algorithm terminates and returns the unit step size η t = 1. In this case, we have that λ t = 1.Suppose that at the first iteration, η (0) = 1 doesn't satisfy the sufficient decrease condition (5) but satisfies the curvature condition (6), we have that η(1)EQUATIONmin = 1 and η (1) = 2. Assume that in the Algorithm 1, η (i) max is never set to a finite value and the algorithm never returns. This means that the condition in line 2 is never satisfied, and as a result, we keep repeating steps in line 12. Thus, η (i) = 2 2 i -1 and since the condition in line 2 is never satisfied, we always have that f (x t + η (i) d t ) ≤ f (x t ) + αη (i) ∇f (x t ) ⊤ d t . Notice that lim i→∞ η (i) → +∞ and ∇f (x t ) ⊤ d t < 0. We obtain that lim i→∞ f (x t + η (i) d t ) → -∞, which is a contradiction since f is strongly convex. Hence, at some point, either the algorithm finds an admissible step size and returns, or η (i) max must become finite. Suppose that this happens at iteration K 1 ≥ 1 of the loop in Algorithm 1. Then, we know that η (K1) = 2 2 K 1 -1 . In the first case that the algorithm finds an admissible step size and returns η K1 , η K1 satisfies the Armijo-Wolfe conditions and therefore η K1 ≤ η r . Using the upper bound result in (76) from Lemma K.1, we obtain that ηEQUATIONIn the second case that η (i) max becomes finite but the algorithm does not terminate, we have that η (K1-1) satisfies the sufficient condition (5) and η (K1-1) ≤ η r . Similarly, this implies thatEQUATIONThen, we further go through the log bisection process. Notice that for any iteration i > K 1 , the sequence η(i)max is finite and non-increasing and the sequence η(i)min ≥ 1 and non-decreasing. The log bisection process indicates thatEQUATIONThe Algorithm 1 implies that for any i > K 1 , we have thatf (x t + η (i) max d t ) > f (x t ) + αη (i) max ∇f (x t ) ⊤ d t , ∇f (x t + η (i) min d t ) ⊤ d t < β∇f (x t ) ⊤ d t .Hence, we know that for any i > K 1 , ηmax ≥ η r and η (i) min ≤ η l where η r , η l are defined in (75), (77) from Lemma K.1. Therefore, using result (78) from Lemma K.1, we have that for any j ≥ 1,EQUATIONNotice that (84) implies thatEQUATIONwhich leads to 0 = lim j→+∞1 2 j-1 log 2 η (K 1 +1) max η (K 1 +1) min = lim j→+∞ log 2 η (K 1 +j) max η (K 1 +j) min ≥ log 2 ηr η l > 0.This is a contradiction. Hence, Algorithm 1 must terminate after finite number of loops. Now suppose that Algorithm 1 terminates after K 1 + Γ 1 iterations, (85) and ( 86) indicate that when Γ 1 ≥ 1, we haveEQUATIONwhere the last inequality holds since (78) in Lemma K.1. Notice that η(K1+1) max = 2 2 K 1 -1 and η K1+1 min = 2 2 K 1 -1 -1. Hence, we obtain thatEQUATIONCombing ( 87), (88) and using log x ≥ 1 -1 x , we have thatEQUATIONLeveraging ( 83) and (89), we prove thatEQUATIONSimilarly, suppose that at the first iteration, η (0) = 1 satisfies the sufficient decrease condition (5) but doesn't satisfy the curvature condition (6), we have that η(1)EQUATIONmin = 0 and η (1) = 1 2 . Assume that in the Algorithm 1, η (i) min is never set to a positive value and the algorithm never returns. This means that the condition in line 2 is always satisfied, and as a result, we keep repeating steps in line 5. Thus, η (i) = ( 12 ) 2 i -1 and since the condition in line 2 is always satisfied, we have that f (x t + η (i) d t ) > f (x t ) + αη (i) ∇f (x t ) ⊤ d t . Therefore, we know that η (i) ≥ η r where η r > 0 is defined in (75) from Lemma K.1. Notice that η (i) ≥ η r > 0 for any i and lim i→∞ η (i) = 0, this leads to a contradiction. Hence, at some point either the algorithm returns a step size satisfying the weak Wolfe conditions or η (i) min must become positive. Suppose that this happens at iteration K 2 ≥ 1 of the loop in Algorithm 1. Then, we know that η (K2) = ( 12 ) 2 K 2 -1 .In the first case that the algorithm finds an admissible step size and returns η K2 , η K2 satisfies the Armijo-Wolfe conditions and therefore η K2 ≤ η r . Using the upper bound result in (76) from Lemma K.1, we obtain that ηEQUATIONIn the second case that η (i) min becomes positive but the algorithm does not terminate, we have that η (K2-1) doesn't satisfy the sufficient condition (5) and η (K2-1) ≥ η r . Using the lower bound result in (76) from Lemma K.1, we obtain that η (K2-1) = ( 12 ) 2 K 2 -1 -1 ≥ η r ≥ 2(1-α) 1+Ct ρ t , which leads toEQUATIONThen, we further go through the log bisection process. Using the same techniques, we can assume that Algorithm 1 terminates after K 2 + Γ 2 iterations, where Γ 2 ≥ 1 satisfies thatEQUATIONwhere the last inequality holds since (78) in Lemma K.1. Notice that η(K2+1) max = ( 1 2 ) 2 K 2 -1 -1 and η K2+1 min = ( 1 2 ) 2 K 2 -1. Hence, we obtain thatEQUATIONCombing ( 93), (94) and using log x ≥ 1 -1 x , we have thatEQUATIONLeveraging ( 92) and (95), we prove thatEQUATIONNotice that α < 1 2 and thus 1 2(1-α) < 2(1 -α), combining (82), (90), ( 91) and (96), we prove the final conclusionλ t ≤ 2 + log 2 1 + (1 -β)(1 + 2C t ) β -α + 2 log 2 1 + log 2 2(1 -α)(1 + C t ) + max{log 2 ρ t , log 2 1 ρ t } . K.3 Proof of Theorem 7.1Using result from Proposition K.2, we have thatEQUATIONUsing Jensen's inequality, we have thatEQUATION)EQUATIONWe also have thatEQUATIONwhere the inequality is due to log 2 ρ i ≤ 1 for ρ i < 2 and log 21 ρi ≤ 1 for ρ i > 1 2 .Using the definition of ω and (b) in Lemma G.1, we obtain thatEQUATIONSimilarly, using (c) in Lemma G.1, we obtain thatEQUATIONCombining (100), ( 101) and (102), we prove thatEQUATIONwhere we use the fact that ω(ρ i -1) ≥ 0 for any i ≥ 0 and the last inequality is due to (46) in Proposition G.2. Leveraging (97), (98), ( 99) and (103), we have thatΛ t ≤ 2 + log 2 1 + 1 -β β -α + 2(1 -β) β -α t-1 i=0 C i t + 2 log 2 3 + log 2 2(1 -α) + log 2 1 + t-1 i=0 C i t ) + 6 t Ψ( B0 ) + 2 t-1 i=0 C i ≤ 2 + log 2 1 + 1 -β β -α + 2(1 -β) β -α t-1 i=0 C i t + 2 log 2 log 2 16(1 -α) + log 2 1 + t-1 i=0 C i t ) + 6Ψ( B0 ) + 12 t-1 i=0 C i t .We prove the final conclusion using (44) from the proof of Theorem 5.2 in Appendix F.2, i.e., t-1 i=0 C i ≤ C 0 Ψ( B0 ) + 3C 0 κ α(1 -β) . K.4Λ t ≤ 2 + log 2 1 + 1 -β β -α + 2(1 -β) β -α 3C 0 κ α(1 -β)t + 2 log 2 log 2 16(1 -α) + log 2 1 + 3C 0 κ α(1 -β)t + 6dκ + 36C0κ α(1-β) t .Moreover, when t ≥ 6dκ + 36 α(1-β) C 0 κ, we have thatEQUATIONProof. Since B 0 = LI, we have B0= 1 L B 0 = I and B0 = ∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2 = L∇ 2 f (x * ) -1 .Using results in the proof of Corollary 5.3, we haveΨ( B0 ) = 0, Ψ( B0 ) ≤ dκ.Combining these two results with the result in Theorem 7.1, we prove the conclusion.Corollary K.4 (B 0 = µI). Let {x t } t≥0 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 x 0 ∈ R d and the initial Hessian approximation matrix B 0 = µI, the average complexity of line search Algorithm 1 T k is upper bounded byΛ t ≤ 2 + log 2 1 + 1 -β β -α + 2(1 -β) β -α C 0 d log κ + 3C0κ α(1-β) t + 2 log 2 log 2 16(1 -α) + log 2 1 + C 0 d log κ + 3C0κ α(1-β) t + 6(1 + 2C 0 )d log κ + 36C0κ α(1-β) t .Moreover, when t ≥ 6(1 + 2C 0 )d log κ + 36C0κ α(1-β) , we have thatEQUATIONProof. Since B 0 = µI, we have B0= 1 κ B 0 = I and B0 = ∇ 2 f (x * ) -1 2 B 0 ∇ 2 f (x * ) -1 2 = µ∇ 2 f (x * ) -1 .Using results in the proof of Corollary 4.2, we haveΨ( B0 ) ≤ d log κ, Ψ( B0 ) ≤ d log κ.Combining these two results with (26) in Theorem 6.4, we prove the conclusion.NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no 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 a separate "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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.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 not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Justification: There is no societal impact of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: 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

Reviews: review: paper_summary: paper_summary: The paper provides non-asymptotic global convergence for BFGW with Armijo-Wolfe (A-S) line search. It provides three main results: 

(a) $O(1- 1/\kappa)^t$ rate globally

(b) with Lipschitz Hessian: $O(1-\alpha(1-\beta))^t$ rate (condition number independent) after iteration t is large enough 

(c) with Lipschitz Hessian: $O((1/t)^t)$ superlinear rate
strength_weakness: strength_weakness: 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.
questions: 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?

2. What happens if we simply pick the initial $B_0$ to be the identity matrix$?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: N/A
questions: 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.

This 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.

I have some minor questions/comments:
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?
2. Can you provide some result for $B_0=\alpha I$ with $\alpha\in(\mu,L)$ as the extension of Corollary 6.5?
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.
4. The following recent work for the explicit superlinear convergence rates of quasi-Newton methods should be involved into the literature review:

         [A] Zhuanghua Liu, Luo Luo, Bryan Kian Hsiang Low. Incremental quasi-Newton methods with faster superlinear convergence rates. AAAI 2024.
         [B] Aakash Lahoti, Spandan Senapati, Ketan Rajawat, Alec Koppel. Sharpened lazy incremental quasi-Newton method. arXiv:2305.17283.
         [C] Chengchang Liu, Cheng Chen, Luo Luo. Symmetric rank-k methods. arXiv:2303.16188, 2023.
         [D] Chengchang Liu, Cheng Chen, Luo Luo, John C.S. Lui. Block Broyden's methods for solving nonlinear equations. NeurIPS 2023.
         [E] Chengchang Liu, Luo Luo. Quasi-Newton methods for saddle point problems. NeurIPS 2022.
         [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.
         [G] Haishan Ye, Dachao Lin, Zhihua Zhang. Greedy and random Broyden's methods with explicit superlinear convergence rates in nonlinear equations. arXiv:2110.08572
         [H] Dachao Lin, Haishan Ye, Zhihua Zhang. Explicit superlinear convergence rates of Broyden's methods in nonlinear equations. arXiv:2109.01974

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.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - The statement “present the first explicit” in abstract is too strong.
- The author could add “with $B_0 = L I$” or comment that this result needs such condition in Line 4 to be more precise.
- 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.
- 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.
- 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$.
- 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.
- $\tilde B_0$ is redefined in line 227.
- The $\hat \rho_t$ should converge to 1/2 instead of 1 in line 237.
- make { } in $\delta_2$ larger in eq. 23.
- 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$.
- 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?
- 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.
- $C_0$ Should be suboptimality of initial iterate in line 273.
- 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.
- 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.
- 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.
questions: questions: Please see the previous section.
limitations: 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.

Comments: comment: Thank you for the reply. I don't have further questions.
Thanks for your further response.
Thank you for reading our rebuttal and providing your follow-up comments.

We will include the discussion on the AGD+BFGS comparison in our revised paper. Additionally, we will address the comments you made regarding the figures. We appreciate your feedback.
Thanks for your careful rebuttal.  I strongly recommend you incorporate the discussion on AGD+BFGS into revision.

Some minor comments on figures in PDF:
1. The initial Hessian estimator in the figure should be displayed in formula font.
2. Different line styles should be used to distinguish the curves in the figures.