Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate

We would like to thank the Reviewer for their time and effort spent in this manuscript and for the constructive feedback which helped improve the paper. In the sequel, we provide our response and actions to each of the Reviewer's comments.

W1: Thank you for the comment. We would like to clarify that the goal of this paper is to explore the possibility of achieving an explicit superlinear rate with limited memory and characterize the role of the memory size in the convergence rate. On the one hand, we provide a definitive answer to this question, i.e., we provably show that it is possible to achieve non-asymptotic superlinear rates for limited-memory methods and analyze how the memory size affects the convergence rate explicitly via the minimal relative condition number. On the other hand, we identify the sufficient condition required for achieving this superlinear rate, i.e., the minimal relative condition number $\beta_{\tau}$ of the error matrix is bounded. Both facts have not been studied so far.

We agree with the Reviewer that there may exist pessimistic scenarios where the boundness assumption may not hold and the convergence rate of the LG-BFGS in Theorem 1 may reduce to be linear. This indicates that while it is possible to achieve superlinear rates, it requires certain conditions, which identifies the inevitable limitation brought by the memory shortage. However, even in the worst case, the convergence rate of the LG-BFGS is at least linear as stated in Proposition 1. These results provide a clear theoretical explanation for the relationship between the convergence rate and the memory limitation. We will clarify this point and include the above discussions in the final upload.

W2: We agree with the Reviewer that the bound provided in Appendix F is not ideal but only for reference, and the rate derived from this bound is not superlinear. However, we would like to clarify that this bound is the worst-case analysis established on the condition number, i.e., the minimal relative condition number with a single memory $\beta_{1}$ (memory size one). Moreover, even in the worst scenario without bound, the LG-BFGS retains the linear convergence rate as stated in Theorem 1 and outperforms the gradient descent as corroborated in our experiments. We will clarify this point in the final upload. Thank you for the comment.

W3: Thank you for the comment. We would like to clarify that the contributions of this work are to answer three questions that have been unclear in the literature: (i) Is it possible to achieve superlinear rates for limited-memory methods? (ii) If so, what conditions are required to make it possible? (iii) How does the memory size affect the convergence rate? This paper provides a definitive answer to the first question, identifies the exact condition / assumption required for superlinear convergence to the second question, and furnishes a clear expression for the non-asymptotic convergence of the proposed LG-BFGS that delineates the direct influence of memory size through the concept of relative condition number to the third question.

Moreover, we highlight that our assumption and results are consistent with the full-memory BFGS method, i.e., the bound of $\beta_\tau$ reduces to $1$ and the superlinear rate becomes that of the full-memory method when the memory size $\tau$ increases to the feature dimension $d$. This builds a clear path from the limited-memory method to its full-memory counterpart, and provides an explicit theoretical explanation behind their performance changes along the reduction of memory size. All these aspects have not been studied so far and thus, we consider this work as the first strade that closes the gap and believe these are novel contributions for the community to further explore the limited-memory methods.

Finally, we remark that even with the boundness assumption, providing an explicit non-asymptotic superlinear rate for limited-memory BFGS methods is already a challenging and tedious task. This requires: (i) developing a novel combination of greedy selection and displacement aggregation to maximize the update progress within the limited-memory framework; (ii) defining a novel concept that embeds the impact of memory limitation in the convergence characterization; (iii) providing novel theoretical derivations that are capable of leveraging the advantages of both techniques to achieve non-asymptotic superlinear convergence with memory limitation.

We will be sure to appropriately caveat the abstract and introduction to clarify the restricted setting in which our results hold, so as to ensure we are not overclaiming. Thank you again for your insightful comment.

We wish to thank the Reviewer for the consideration on the answers and for the additional feedback. We are glad to see the Reviewer found our answers helpful.

W1, W2, Q3: The Reviewer is correct that this modification on the correction strategy has an impact on the convergence results. Specifically, from $\mu I\preceq\nabla^2f(x_t)\preceq LI$, we have $\phi_t\le\hat{\phi}_t\le\frac{L}{\mu}\phi_t$ and $\phi_tC_M\le\hat{\phi}_tC_M\le\phi_t\frac{L}{\mu}C_M$ in the correction strategy. This indicates that while this modification may increase the error between the Hessian approximation $\hat{B_t}$ and the actual Hessian $\nabla^2 f(x_t)$, this increase is limited. For Proposition 2, it will reduce the update progress in (24) of the proof, necessitating a slightly better initialization to establish a bound in (27) to derive the linear convergence. For Proposition 3, $\phi_t$ will be replaced by $\hat{\phi}_t$ as the Reviewer points out. For Theorem 1, it will reduce the update progress in (59) and (60) of the proof, and need a slightly better initialization to establish a bound from (64) to (65) for deriving the superlinear convergence. Additionally, the Reviewer is correct that the minimal relative condition number will be w.r.t. the modified error matrix, which may have slightly larger eigenvalues. We will include these modifications and clarify these details clearly in the final upload. Thank you again for pointing this out.

(cont.)....

Q5: The Reviewer raises a good point. We would like to clarify that assuming $\beta_{t,\tau}$ is bounded by $C_\beta$, the contraction factor $(1-\frac{\mu}{\beta_{t,\tau}dL})$ in (17) is bounded by a constant, i.e., $(1-\frac{\mu}{\beta_{t, \tau}dL}) \le (1-C)$, while $\phi_t\le\lambda_f(x_t)$ decreases to zero at a linear rate from Theorem 1. Thus, (17) would become a contraction when the iteration is large or the initialization is good. Moreover, the memory size $\tau$ determines the value of the contraction factor, i.e., a larger $\tau$ yields a smaller $\beta_{t, \tau}$, leads to a smaller contraction factor, increases the convergence rate. We will add more discussions regarding this fact in the final upload. Thank you for the suggestion.

Q6: We agree with the Reviewer that the rate improvement of Greedy BFGS compared to BFGS is because of the greedy update strategy used for the curvature matrix. Specifically, the greedy update strategy of G-BFGS selects the variable variation $s_t$ as the basis vector that maximizes the weighted norm ratio [cf. (6)]. It optimizes the update progress of the Hessian approximation [cf. (41) in the proof of Proposition 2] and improves the convergence rate. We will clarify this point in the revised paper. Thank you for the comment.

Q7: Thank you for the comment. If $\tau$ is small, the performance of LG-BFGS will degrade close to L-BFGS, though the computation of LG-BFGS decreases. The reason we explored this range of $\tau$ is to illuminate the performance tradeoffs between these extremes. In general, we agree selecting $\tau$ as an absolute constant makes sense, but doing so would not reveal how performance varies with respect to the interplay between memory size and feature dimension. We will clarify this selection of memory parameter and conduct this additional numerical study in the final upload, if afforded the opportunity.

We would like to thank the Reviewer for spending time thoroughly reviewing the manuscript and providing constructive feedback. We are glad to see the Reviewer appreciated the novelty and the presentation of the work. In the sequel, we provide our response and actions to each of the Reviewer's comments and questions.

W1, W2, Q3: We agree with the Reviewer that the weighted norm $\phi_t=\lVert x_{t+1}-x_t\rVert_{\nabla^2f(x_t)}$ in the correction strategy requires the computation $O(d^2)$. However, we would like to clarify that this weighted norm can be replaced by $\hat{\phi_t}=\lVert x_{t+1}-x_{t}\rVert_{LI}$, which provides the same correction guarantees and only requires the computation $\mathcal{O}(d)$.

Specifically, from $\mu I\preceq\nabla^2 f(x_t)\preceq LI$ of Assumption 1, we have $\hat{\phi}_t\ge\phi_t$ and $(1+\hat{\phi}_tC_M)B_t\succeq (1+\phi_tC_M)B_t\succeq B_t$, and thus $\hat{\phi}_t$ provides the same correction guarantees as $\phi_t$. Since $LI$ is a diagonal matrix, $\hat{\phi}_t$ only requires the computation $O(d)$. Additionally, we note that this modification has an impact. It leads to a larger error between the Hessian approximation $\hat{B}_t$ and the actual Hessian $\nabla^2f(x_t)$, subsequently reducing the update progress of algorithm. We will clarify this point and include this modification in the final upload. Thank you for pointing this out.

W3, Q8.2: Thank you for the comment. We would like to clarify this point from two aspects:

(i) While the proposed LG-BFGS requires more worst-case computation than L-BFGS, it achieves a faster convergence rate w.r.t. iteration in all experiments -- see Fig. 1 in Section 6. In the experiments of the appendix, we see that LG-BFGS is faster w.r.t. runtime than L-BFGS in scenarios (a), (b) and (d), while we concede that it may be slower in some scenarios like (c) (where these scenarios are for specific relationships on memory parameter $\tau$ and input dimension $d$). This indicates an inevitable trade-off between the convergence rate and the computational cost.

(ii) We propose LG-BFGS as the first step to explore the possibility of achieving a non-asymptotic superlinear convergence with limited memory and analyze the explicit effect of memory limitation on the convergence rate. We are currently working on potential extensions to further reduce the worst-case computation of LG-BFGS. For example, we may develop a method that harmoniously combines LG-BFGS and L-BFGS in a compatible way akin to [a], thereby leveraging the strengths from both sides. With these endeavors in mind, we believe this work lays a foundation to develop extended limited-memory methods, offering more refined trade-offs between rate and cost in future research.

[a] Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood.

W4, Q8.1: Thank you for the comment. We would like to clarify that we do not apply the correction strategy in all experiments, following the existing greedy BFGS methods (Rodomanov & Nesterov 2021a; Lin et al. 2021). Specifically, the application of the correction strategy is to guarantee the error matrix positive semi-definite, i.e., $\hat{B_t}-\nabla^2f(x_{t+1})\succeq 0$. However, in practical implementation, the error matrix is positive definite without correction and thus, there is no need to apply the correction strategy, as recommended by (Rodomanov & Nesterov 2021a; Lin et al. 2021). To further address the Reviewer's concern, we will provide an ablation study comparing the performance of LG-BFGS with and without the correction factor in the final upload.

Q1: We agree with the Reviewer that using this notation for both bases is ambiguous. We will disambiguate the notation of general versus standard basis vectors so the algorithm executation is clear. Specifically, we will use $g_i$ to represent a general basis and $e_i$ to represent the standard one in the revised paper. Thank you for the suggestion.

Q2: We agree with the Reviewer and we will endeavor to be consistent with the use of complexity notation, to omit constant factors that are not problem-dependent. We thank the reviewer for helping us clarify the algorithm's required computational effort.

Q4: The Reviewer is correct that it is the error matrix $\hat{B_t}-\nabla^2f(x_{t+1})$ in Theorem 1, and we will explicitly state this fact. Thank you for pointing this out.

We would like to thank the Reviewer for their time spent in this paper and for the insightful comments which helped improve the paper. We are glad to see the Reviewer found the contribution novel. In what follows, we provide our response and actions to your concerns.

W1: Thank you for the suggestion. We will revise the presentation of our contributions in the final upload to be itemized bullets as follows:

1. We propose a Limited-memory Greedy (LG)-BFGS method, which is a novel synthesis of greedy basis selection and displacement aggregation. It maximizes the update progress per iteration to improve the convergence, while maintaining the limited memory setting.

2. We furnish a clear and explicit expression for the non-asymptotic convergence of the LG-BFGS, which not only delineates the direct influence of memory size through the concept of relative condition number $\beta_\tau$ [Def. 1], but also identifies roles played by other factors (e.g., problem properties, initial conditions, etc.). This is the first work that characterizes the explicit effect of memory size on the convergence rate.

3. The LG-BFGS presents an non-asymptotic superlinear rate with the boundness assumption on $\beta_\tau$. This is the first work that shows the possibility of achieving superlinear rates in limited-memory methods and identifies the exact condition / assumption under which this could be possible. The result recovers that of the full-memory method when the memory size increases to the feature dimension. This establishes a clear path from limited-memory methods to full-memory ones, and provides an explicit theoretical explanation behind the performance change along the reduction of memory size

In summary, this paper answers three unknown questions: (i) Is it possible for limited-memory methods to achieve explicit superlinear rates? (ii) If so, which condition does it require? (iii) What is the explicit effect of memory size on the convergence rate?

W2: Thank you for the suggestion. We have changed the color, which will be reflected in the final version of this work.

W3: Thank you for the suggestion. We will include the table to summarize the comparision of convergence rate and computation complexity in Section 5, which will be comparable to the one below:

W4: Thank you for the suggestion. We will add this citation, and are grateful for the Reviewer to bringing this innovative work to our attention. We have reproduced the manner in which it will be discussed in the paper here for convenience:

Accelerations of standard BFGS have been considered in various forms; however, Nesterov acceleration is one approach that has been shown to enhance the rate of convergence of standard BFGS after a threshold number of iterations, under suitable choice of step-size and error-bound tolerance [1]. However, we note that, similar to standard BFGS, accelerated variants require full memory to achieve these rates.

W5: We agree with the Reviewer that the title may give the impresion that our results hold for the entire Broyden class of Quasi-Newton methods, or SR1, whereas our developments are only for BFGS. However, similar techniques could be applied to these alternative approaches. We will be more careful to caveat these points of distinction in the abstract and introduction so as to clarify the interpretation. Thank you for the suggestion.

W6: We agree with the Reviewer that [2] provides an analysis methodology for both local and global convergence. However, we would like to clarify that this work requires full memory for implementation, i.e., it requires the storage of the previous Hessian approximation matrix or instead storing all past curvature information, which is different from our limited-memory setting. Moreover, it was contemporaneous of ours, and marks a significant departure from a long history of analyzing the local rate of convergence of Quasi-Newton methods. It is a valid scope of future work to explore how explicit superlinear rates in the limited-memory setting may be achieved globally. We will add this work and include the above discussion in the final upload. Thank you for pointing this out.

We wish to thank the Reviewer for the consideration on our responses and for the additional feedback.

We have updated the revised manuscript in the system based on our responses to your comments. Thank you again for providing high-quality comments and nice suggestions, which enabled us to strengthen our paper.

Thank you for the feedback regarding the update issue of the system. We have re-updated the manuscript in the system and please let us know if you still cannot see the revisions in the updated manuscript.

Specifically, we have made the following revisions based on your suggestions:

(i) We have revised the second paragraph of Section 1 to include the references suggested by the Reviewer;

(ii) We have revised the proposed research questions and the contributions in Section 1, to itemize and highlight our contributions;

(iii) We have added the sentence after the contributions in Section 1, to clarify that "our development focuses on the BFGS method in the class of quasi-Newton methods, while similar techniques could be applied to its alternative variants".

(iv) We have added Table I to summarize the comparisons in Section 5.

(v) We have changed the color of GD and fixed the lapsus in Figure 1 in Section 6 to avoid any confusion.

(vi) We have revised the definition of $\phi_t$ in the correction strategy and clarified that "it only requires the computation $O(d)$ because $LI$ is a diagonal matrix" in the first paragraph of Section 3.1. Moreover, we have revised the initial condition in Proposition 2 and Theorem 1 to update the impact of this modification (Theorem 1 considers the same settings as Proposition 2 and thus, there is no change in Theorem 1). Additionally, since the correction factor $\phi_t$ has been updated with the modified one, we do not need to change Proposition 3 and the contraction factor in Theorem 1.

Thank you again for the constructive suggestions and the additional feedback. Please let us know if there is still any problem of seeing the revisions in the updated manuscript of the system.

We would like to thank the Reviewer for reviewing our manuscript and for the constructive feedback. We are glad to see the Reviewer appreciated the presentation and the results of the paper. In what follows, we provide our response and actions to your comments.

Response to Weakness: The Reviewer is correct that the minimal relative condition number $\beta_\tau$ (or the bound $C_\beta$) embeds the role of the memory size $\tau$ in the convergence rate. Specifically, a larger $\tau$ decreases the minimal relative condition number $\beta_{\tau}$, reduces the contraction factor $1-\mu/(\beta_{\tau}dL)$, and improves the convergence rate, but increases the storage memory and computational cost; hence, yielding an inevitable trade-off between these factors.

On the other hand, we agree with the Reviewer that interesting topics for future research include deriving explicit dependency of $\beta_\tau$ (or $C_\beta$) on the memory size $\tau$. We consider this work as the first stride to explore the possibility of achieving superlinear rates with limited-memory BFGS methods and analyze the inherent role of the memory size on the convergence rate. We will clarify this point in the final upload. Thank you for the comment.

As the discussion period is drawing to close, we sincerely appreciate the Reviewers for providing high-quality comments and nice suggestions, which helped strength our paper. If our responses have addressed your concerns, we humbly hope the Reviewers could revisit the score in light of the responses and revisions.

Thank you again for your time and effort in reviewing our work.