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

Response to weakness 1,2,3. We will soften our claims and add “$B_0 = L I$” in the abstract. Our global superlinear convergence analysis is based on the results from the global linear convergence rates, so we need to present both the linear and superlinear convergence results. Moreover, the linear convergence rates we obtained in this submission are also novel and innovative since there is no such linear ratio of $1 - \frac{1}{\kappa}$ or parameter-free linear rate as presented in Section 5 in previous works. We will revise the abstract accordingly to resolve these ambiguities.

Response to weakness 4. The key intuitive explanation is the step size $\eta_t$ satisfying the exact line search may not satisfy the sufficient descent condition (5) for any $\alpha \in (0, \frac{1}{2})$, which is a fundamental condition to prove the convergence bound in our paper. We will add this explanation in our revised version.

Response to weakness 5. We will clarify that when $B_0 = L I$, the linear rate of $(1 - \frac{\mu}{L})^t$ is achieved at the first iteration while for $B_0 = \mu I$, the same bound holds for $t \geq d\log{\kappa}$.

Response to weakness 6. We agree with the reviewer that $LI$ and $\mu I$ are not necessarily practical initialization schemes, as we generally may not know the values of $L$ or $\mu$. We will modify the wording in our revised version. It is better to state that we choose these two specific initialization matrices since they can make all the non-asymptotic global linear and superlinear convergence bounds and expressions simpler and clearer. That said, in the attached numerical experiments, we have illustrated the convergence rate of two more practical choices: $B_0 = I$ and $B_0 = cI$ where $c \in [\mu, L]$ and is easy to compute. In the revised paper, we plan to add corollaries for these two special cases after each result presented in the paper.

Response to weakness 7, 9, 13. We will fix all these typos.

Response to weakness 8. Let's clarify why $\hat{\rho_t}$ should converge to 1. This is because The global linear convergence results indicate that $\sum_{i = 0}^{\infty}C_i < +\infty$. Hence, from (44) of Proposition G.2 in the appendix, we know that $\sum_{i = 0}^{\infty}\omega(\rho_i - 1) < +\infty$, which implies that $\lim_{i \to \infty}\omega(\rho_i - 1) = 0$. Notice that the function $\omega$ is continuous and $\omega(x) = 0$ if and only if $x = 0$. Therefore, we have that $\lim_{i \to \infty}\rho_i = 1$.

In equation (22), the lower bound of $\hat{p}_t$ should converge to $\frac{1}{2}$ since $C_t$ converges to 0 and $\rho_t$ converges to 1. We would like to highlight that the fact that $\hat{p}_t$ converges to $\frac{1}{2}$ is not problematic, as the lower bound of $\hat{q}_t$ has a factor of 2 (see line 519, part (b) of Lemma D.2 in the appendix). This factor of 2 of $\hat{q}_t$ times the limit $\frac{1}{2}$ of $\hat{p}_t$ produces the unit factor 1, which leads to the superlinear convergence rates of the BFGS method in section 6.

Response to weakness 10. We will add more lines in Corollary 4.2 for the convergence results of any initial $B_0$ in our revised version.

Response to weakness 11. We will add comments to our revised paper. In fact when $B_0 = L I$, we have that $t_0 = \frac{3\kappa}{\alpha(1 - \beta)}\log{\frac{C_0}{\delta_1}}$ and $|I| \leq \delta_4\Big(d\kappa + \frac{6C_0\kappa}{\alpha(1 - \beta)}\Big)$. When $B_0 = \mu I$, we have that $t_0 = \max\\{d\log{\kappa}, \frac{3\kappa}{\alpha(1 - \beta)}\log{\frac{C_0}{\delta_1}}\\}$ and $|I| \leq \delta_4\Big(\Psi((1 + 2C_0)d\log{\kappa} + \frac{6C_0\kappa}{\alpha(1 - \beta)}\Big)$.

Response to weakness 12. We have added one table in the attached pdf presenting all the convergence stages with a required number of iterations to transit to each phase.

Response to weakness 14. Thanks for the comments. We did not explicitly present different convergence stages in our submission. To address this issue, in the attached PDF we included a table highlighting all the linear and superlinear convergence stages with the required number of steps to transition to each phase. Please check the table in the uploaded PDF file. We will add this transition table in our revised version.

Response to weakness 15. In general, backtracking line search is used for finding an acceptable step size when we know that the interval of admissible step sizes is bounded below by zero and can be written as $(0, \eta_1]$. In this case, we can start the process of selecting the step size with a large step size $\eta_{initial}$, possibly $\eta = 1$, and then backtrack it by a factor $\beta < 1$. It can be easily verified that after at most $\log_{1/\beta} (\eta_{initial}/\eta_1)$ iterations, we will find an admissible step size. In fact, if we only needed the sufficient decrease condition (5), we could apply the backtracking technique with initial $\eta_1 = 1$.

However, the weak Wolfe conditions require both (5) and (6). Condition (6) indicates that there exists a strictly positive $\eta_2$ such that the admissible step size $\eta_t \geq \eta_2$. Hence, the lower bound of the proper step size satisfying both (5) and (6) is not zero, and we can no longer utilize backtracking to find such a step size. Therefore, we need to find a window $[\eta'_2, \eta'_1]$ such that $\eta'_2 \geq \eta_2$ and $\eta'_1 \leq \eta_1$ so that when $\eta_t$ belongs to this window $[\eta'_2, \eta'_1]$, we have that $\eta_t \in [\eta_2, \eta_1]$ and this $\eta_t$ satisfies conditions (5) and (6). We need to use the bisection method to construct both the upper and lower bounds of this window. We apply the log bisection instead of the vanilla bisection because it helps simplify the theoretical analysis of the line search complexity. We will highlight this in our revised version of the paper.

Response to weakness 16 and Limitations. Please check numerical experiments in the attached file.

Question 1. Unifying the global and local convergence rates into one framework of BFGS with line search is nice. We can also address this problem by a simple way, i.e., run (accelerated) gradient descent to enter the local region, then run standard BFGS to achieve the superlinear rate. Can you compare the results in your paper with this heuristic method?

Response. This is a great question. We can use the suggested method of the combination of accelerated gradient descent (AGD) with BFGS to achieve a faster convergence rate compared to the vanilla BFGS with line search. However, we would like to highlight the following two points:

First, we would like to mention that the global convergence complexity of the vanilla BFGS quasi-Newton method with line search was an interesting open problem worth exploring. Interestingly, our results show that BFGS with inexact line search is no worse than gradient descent, and will reach the faster superlinear convergence stage after some explicit iterations. Indeed, it would be great if one could use this analysis to design an accelerated version of BFGS that globally outperforms AGD, meaning it achieves a global linear rate that matches the one for AGD and an eventual superlinear rate.

Second, the size of the local neighborhood for BFGS to achieve superlinear convergence depends on some parameters of the objective function, such as the gradient smoothness parameter $L$ or the strong convexity parameter $\mu$. Hence, to follow the reviewer's suggestion and switch from AGD to BFGS in a local neighborhood of the solution, we need to know these parameters to determine if the iteration has reached the local regime. Therefore, this combination of AGD and BFGS requires knowing the values of parameters $L$ or $\mu$. For our vanilla BFGS with line search, we do not require access to any of those parameters in the implementation of the algorithm. Although in Corollary 6.5 we compare the results of different $B_0 = LI$ and $B_0 = \mu I$, we only use these $B_0$ to explicitly obtain the convergence bounds of the BFGS. In practice, $B_0$ could be any symmetric positive definite matrix. We can just choose $B_0 = I$ or $B_0 = cI$ for any positive real number $c$ (please check the presented experiments in the attached PDF). Therefore, to implement the AGD plus BFGS, we need to know some parameters of the objective function. In contrast, to implement the vanilla BFGS with line search, we don't need to know any parameters except the line search parameters $\alpha$ and $\beta$ as specified in (5) and (6). This is one advantage of vanilla global BFGS with line search over the combination of first-order methods with local BFGS.

Question 2. Can you provide some result for $B_0 = \alpha I$ with $\alpha \in (\mu, I)$ as the extension of Corollary 6.5?

Response. All our global linear and superlinear convergence bounds hold for any $B_0$ as long as it is symmetric positive definite. The only difference the choice of initial Hessian approximation could make is in the value of $\Psi(\bar{B_0})$ and $\Psi(\tilde{B_0})$ appearing in our theoretical results. In the corollaries of our paper, we chose $B_0 = LI$ and $B_0 = \mu I$ as two special cases because we can obtain specific and explicit upper bounds in terms of the dimension $d$ and the condition number $\kappa$ in different theorems, making our results easier to parse.

If we choose $B_0 = \alpha I$ in Corollary 6.5, then $\Psi(\bar{B_0}) = \Psi(\frac{\alpha}{L}I) = \frac{\alpha}{L}d - d + d\log{\frac{L}{\alpha}}$. Moreover, we would have $\Psi(\tilde{B_0}) = \Psi(\alpha \nabla^2{f(x_*)^{-1}}) = \alpha\mathbf{Tr}(\nabla^2{f(x_*)^{-1}}) - d - \log{\mathbf{Det}(\alpha\nabla^2{f(x_*)^{-1}})}$ which is totally determined by the Hessian matrix $\nabla^2{f(x_*)^{-1}}$. In this case, one can use the upper bounds $\Psi(\bar{B_0}) = d(\frac{\alpha}{L} - 1 + \log{\frac{L}{\alpha}})$ and $\Psi(\tilde{B_0}) = \mathbf{Tr}(\alpha\nabla^2{f(x_*)}^{-1}) - d - \log{\mathbf{Det}(\alpha\nabla^2{f(x_*)}^{-1})} \leq d(\frac{\alpha}{\mu} - 1 + \log{\frac{L}{\alpha}})$ to simplify the expressions.

Applying these values of $\Psi(\bar{B_0})$ and $\Psi(\tilde{B_0})$ to the superlinear bound in Theorem 6.4, we can obtain the superlinear convergence rates for $B_0 = \alpha I$ in Corollary 6.5. We also include the performance of BFGS with $B_0 = cI$ where $c \in [\mu, L]$ in our numerical experiments as presented in Figure 1 of the attached pdf. We observe that the performance of BFGS with $B_0 = cI$ is very similar to the convergence curve of BFGS with $B_0 = \mu I$ in our numerical experiments. We will add this dicussion to the revised paper.

Question 3. The discussion on the initial Hessian estimator after Corollary 6.5 is interesting. It is better to provide some experiments to validate it. Considering the theoretical contribution of this paper is strong, I will still recommend accept even if there is no additional experiment in rebuttal.

Response. Thanks for the advice. We have attached the empirical results of our numerical experiments with different $B_0$ in the pdf.

Question 4. The following recent work for the explicit superlinear convergence rates of quasi-Newton methods should be involved into the literature review:

Response. Thanks for pointing out all these papers. Indeed, they are all relevant to our submission since they characterize local non-asymptotic convergence rates of different quasi-Newton methods in various settings. We will cite these papers as previous works in the introduction section of our revised version.

Question 5. In line 49, it is somewhat inappropriate to call reference [40] a draft. It is more appropriate to use "unpublished paper" or "technical report" to describe it.

Response. Thanks for the advice. We will modify our text in the revised version to cite the reference [40] as a "technical report".

Response to Weakness. Thank you to the reviewer for raising this valid point. We would like to mention that our paper and reference [38] have similar goals, both aiming to establish the global convergence rate of BFGS under some line-search scheme. The primary difference is in the choice of line-search: in our work, the step size is chosen to satisfy the weak Wolfe conditions specified in (5) and (6), while in [38], the step size is determined by exact line search. Given that, it is inevitable to see some similarities and overlaps in the presentation and intermediate results of our submission and [38]. In fact, we have highlighted in the paper any overlap with [38]. That said, all our theoretical results are different from the ones in [38] and our analysis deviates from [38] in the following multiple levels:

1. The global linear convergence rate $1 - \frac{1}{\kappa}$ in Theorem 4.1 of our paper is strictly better than the corresponding global linear rate $1 - \frac{1}{\kappa^{1.5}}$ of the exact line search in [38]. This improvement is due to the fact that we can lower bound the term $\hat{p}_t$ defined in (22) by $\alpha$ as presented in Lemma 2.1 in our submission instead of $\frac{1}{\sqrt{\kappa}}$ in [38]. This difference of the lower bounds of $\hat{p}_t$ leads to the improvement of our results.
2. The convergence bounds in Theorem 5.2 are novel and unique to our submission, demonstrating that under the additional assumption that the Hessian is also Lipschitz, BFGS can achieve a linear rate independent of the problem parameters after a certain number of iterations. The analysis in [38] failed to establish similar parameter-free global linear rates, under similar assumptions.
3. The most significant distinction between our analysis and the one in [38] is in the global superlinear convergence. Specifically, in our submission, we focus on the "good" event that ensures the unit step size $\eta_t = 1$ is admissible (satisfying the weak Wolfe conditions (5) and (6)) and control the size of the "bad" set of the time indexes where $\eta_t \neq 1$ (see Lemmas 6.1 to 6.3). This technique and idea are independent of the superlinear convergence analysis in [38], where the step size $\eta_t$, determined by the exact line search, can be $1$, larger than $1$, or smaller than $1$.

Response to question 1. This is a good point. Note that for any objective function that is bounded below and any descent search direction $d_t$ where $g_t^\top d_t < 0$, there always exists an interval of the form $[\eta_l, \eta_u]$ for which all the real values in this interval satisfy the weak Wolfe conditions specified in (5) and (6). (Please check Lemma 3.1 in Numerical Optimization by Stephen J. Wright and Jorge Nocedal.) Notice that we assume that the objective function is bounded below in our submission and the BFGS search direction $d_t = B_t^{-1} g_t$ is a descent search direction. Hence, there always exists an interval of step size choices for which the conditions (5) and (6) are satisfied. We will highlight this point in the revised paper. While this is only an existence result, in our line search routine, we proposed the log bisection algorithm (Algorithm 1) that chooses the step size $\eta_t$ satisfying the weak Wolfe conditions (5) and (6), and we also characterized the complexity of our log bisection scheme that produces such $\eta_t$. Please check all the proofs in Appendix I. Hence, it is possible to efficiently find such stepsize.

Regarding your question on whether the exact line-search step size satisfies the conditions in (5) and (6), the short answer is no. To be more precise, the step size $\eta_t$ obtained by the exact line-search satisfies the property that $g_{t + 1}^\top d_t = 0$. Hence, it satisfies the curvature condition (6) for any $\beta \in (0, 1)$. However, there is no guarantee that the exact line-search step size could satisfy the sufficient descent condition (5) for any $\alpha \in (0, 1/2)$. Therefore, in general, the exact line-search step size from [38] is not admissible for the weak Wolfe conditions (5) and (6).

Response to question 2. This is a good question. All our global linear and superlinear convergence bounds hold for any $B_0$ as long as it is symmetric positive definite. The only difference the choice of initial Hessian approximation could make is in the value of $\Psi(\bar{B_0})$ and $\Psi(\tilde{B_0})$ appearing in our theoretical results. In the corollaries of our paper, we chose $B_0 = LI$ and $B_0 = \mu I$ as two special cases because we can obtain specific and explicit upper bounds in terms of the dimension $d$ and the condition number $\kappa$ in different theorems, making our results easier to parse.

It is possible to establish all results for the special case where $B_0 = I$, and only the values of $\Psi(\bar{B_0})$ in Theorem 4.1 and Theorem 5.2 and $\Psi(\tilde{B_0})$ in Theorem 6.4 will change, where $\bar{B_0} = \frac{1}{L}B_0$ and $\tilde{B_0} = \nabla^2{f(x_*)}^{-\frac{1}{2}}B_0 \nabla^2{f(x_*)}^{-\frac{1}{2}}$. Notice that the transition time required to reach different linear and superlinear convergence stages depends on the values of $\Psi(\bar{B_0})$ and $\Psi(\tilde{B_0})$. Hence, the only impact of choosing $B_0$ as the identity matrix is that it will affect the required number of steps to reach the parameter-free linear convergence stage and the superlinear convergence stage. In fact, if $B_0 = I$, we have that $\Psi(\bar{B_0}) = \frac{1}{L}d - d + d\log{L}$ and $\Psi(\tilde{B_0}) = \mathbf{Tr}(\nabla^2{f(x_*)}^{-1}) - d - \log{\mathbf{Det}(\nabla^2{f(x_*)}^{-1})} \leq d(\frac{1}{\mu} - 1 + \log{L})$. Finally, to better study the special case of $B_0 = I$, we conducted numerical experiments with BFGS using $B_0 = I$, as presented in Figure 1 of the attached PDF. As we observe, the performance of choosing $B_0$ as the identity matrix $I$ is quite good compared to other initializations of $B_0$.