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

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.

Strengths

- The non-asymptotic global convergence rate presented in this paper improves the previous result in the literature. The theoretical framework is rigorous, with clearly stated assumptions and detailed proofs supporting the main results. The theorem statements and comments are clear. - The use of log bisection algorithm is innovative. - The explanation of theoretical results aid in the reader's understanding of the methodology and results. - By providing a unified non-asymptotic convergence analysis of global and superlinear convergence result together with the complexity analysis, the paper in optimization literature.

Weaknesses

- The statement “present the first explicit” in abstract is too strong. - 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

Please see the previous section.

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

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.

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.

Strengths

See questions.

Weaknesses

N/A

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.

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

N/A

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

Strengths

1. The convergence is characterized non-asymptotically. I believe such results for BFGS with A-S stepsize are new. 2. The rate provided for BFGS is faster than in previous literature.

Weaknesses

Authors should carefully consider the similarities and differences with the reference [38]. For example, Proposition 3.1 in this manuscript is almost the same as Proposition 1 in [38], which is a critical element of this paper. Additionally, the proof employs some results from [38]. I am concerned about the extent of this overlap. Although authors already commented on the final results difference with [38], there is also much overlap in the main contents. It is essential for the authors to more thoroughly address and discuss these parallels within the manuscript.

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$?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A