Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance

Weaknesses: The approach and derivation of the rates are specific to BFGS, and not for a broader class/family of quasi-Newton methods.

Response: This is a great point. The results in our paper are currently specific to the BFGS quasi-Newton method. To the best of our knowledge, when using an inexact line search—such as the Armijo–Wolfe line search—there is no theoretical guarantee that other quasi-Newton methods from the convex Broyden class, such as DFP, achieve global superlinear convergence.

The main challenge in analyzing DFP lies in the potentially unbounded exponential growth of the largest eigenvalue of its Hessian approximation. Without a controllable upper bound on this eigenvalue, it is difficult to lower bound the angle between the DFP search direction and the gradient vector—a key property for establishing superlinear convergence.

For more details, please refer to the following reference:

Richard H. Byrd, Jorge Nocedal, Ya-Xiang Yuan, “Global Convergence of a Class of Quasi-Newton Methods on Convex Problems,” SIAM Journal on Numerical Analysis.

Additionally, only under exact line search does the convex Broyden class—including both BFGS and DFP—produce identical iterates. However, exact line search is far less practical than the inexact line search strategies considered in our work due to its significantly higher computational cost.

Extending our BFGS analysis under inexact line search to a broader class of quasi-Newton methods, such as DFP, remains an interesting direction for future research.

This is an excellent point that we will add to the revised paper. Thanks for your comment.

Weaknesses: The class of self-concordant functions is relatively narrow compared to broader classes such as convex or strongly convex functions. While the authors argue that prior works required strong convexity/smoothness, relying on self-concordance could be considered an “even stronger” and less practical assumption.

Response As we explained in the paper, our assumption of strong self-concordance is strictly weaker than the more commonly used conditions of strong convexity and Lipschitz continuous Hessians employed in previous work on quasi-Newton methods (lines 112–116 of our submission). While we acknowledge that strong self-concordance is a stronger assumption than plain convexity, some form of Hessian continuity is essential for establishing global superlinear convergence of second-order optimization methods such as Newton’s and quasi-Newton methods. Furthermore, strong self-concordance is frequently encountered in practical engineering applications, as it is satisfied by many commonly used functions, including log-sum-exp, and log-barrier functions. Therefore, studying quasi-Newton methods under the assumption of strong self-concordance has substantial practical and valuable relevance. Building on this foundation, we aim to extend our results to the standard self-concordant setting in future work.

Moreover, we would like to emphasize that the primary contribution of our work is the development of a global, non-asymptotic convergence theory for BFGS quasi-Newton methods that respects their affine invariance. While we agree with the reviewer that the strongly self-concordant setting is not the most general, the significance of our results lies in demonstrating two key points: (i) it is possible to achieve superlinear convergence rates beyond the classical assumptions of strong convexity and Lipschitz continuity of the gradient and Hessian, and (ii) it is possible to derive a global complexity theory for BFGS that aligns with its affine-invariance properties. This work represents an initial step toward extending the analysis of BFGS to broader settings.

Weaknesses: The experimental section is relatively weak and is limited to synthetic problems (artificial cubic function and logistic regression); it would be stronger with results on real-world datasets or applications, or to illustrate better the different convergence behavior predicted by the theoretical results from Theorems 3.3 and 4.3

Response Thank you for the helpful suggestion. Currently, our numerical experiments focus on different objective functions with randomly generated parameters. This design was chosen to isolate the effect of parameters such as the problem dimension $d$ on the performance of the BFGS algorithm.

We agree with the reviewer that supplementing our empirical results with additional synthetic problems would strengthen the evaluation. In the revised version of our submission, we will include experiments on problems arising from practical applications—such as pattern recognition, signal processing, and related fields—and incorporate real-world datasets to demonstrate the method’s effectiveness in realistic scenarios.

Question: Do you believe it is possible to have a similar analysis for a family of quasi-Newton methods, rather than only BFGS?

Response This is an excellent question. We believe that extending our analysis of BFGS under inexact line search to a broader class of quasi-Newton methods—such as DFP and SR1—is both natural and worthwhile. Such an extension represents a promising direction for follow-up work and future research.

As we have noted before, the main challenge in analyzing DFP lies in the potentially unbounded exponential growth of the largest eigenvalue of its Hessian approximation. Without a controllable upper bound on this eigenvalue, it is difficult to obtain a uniform lower bound on the angle between the DFP search direction and the gradient—a key property for establishing superlinear convergence.

We believe that extending our analysis to DFP is feasible, although it may require additional iterations for DFP to achieve a superlinear convergence rate compared with BFGS.

Weakness: Although there are minor differences in specific details between this work and the related study [1], the overall proof framework closely follows that of the existing work [1]. The technical contribution is incremental compared with prior work.

Response: As stated in our paper, the primary novelty of our work lies in extending the global, non-asymptotic convergence analysis of quasi-Newton methods—specifically BFGS—to self-concordant functions without assuming strong convexity. Moreover, our results are affine-invariant, consistent with the intrinsic geometry of the BFGS method.

Regarding reference [1], we would like to emphasize that our paper is not a derivative of the works in [1]; rather, it extends their analysis to a substantially more general setting by removing the assumptions of strong convexity and Lipschitz continuity of the gradient and Hessian. Once these assumptions are relaxed, the theoretical tools and techniques developed in [1] are no longer applicable.

Our submission makes two key contributions that clearly distinguish it from prior work:

1. Generalization of convergence theory: We establish global non-asymptotic linear and superlinear convergence rates for BFGS without strong convexity or Lipschitz continuity of the gradient or Hessian. Existing analyses rely critically on strong convexity, whereas our results demonstrate that superlinear convergence remains achievable even in its absence, substantially broadening the theoretical foundation of BFGS.

2. Affine-invariant convergence guarantees: We derive explicit convergence rates that depend only on the self-concordance parameter of the objective function. These rates are affine-invariant, matching the coordinate-free nature of BFGS. In contrast, previous results depend on coordinate-specific quantities. To our knowledge, this is the first work to provide affine-invariant guarantees for BFGS.

Finally, the technical contributions of our paper require new proof strategies, which we summarize in the following points.

First, the proof of Theorem 3.1 for showing global linear convergence rate is fundamentally different from the analyses in prior work. Specifically, those prior results heavily depend on the strong convexity and gradient Lipschitz-ness assumptions to showcase a linear convergence rate: they use the Lipschitz continuity of the gradient to upper bound $||y_t||^2/s_t^\top y_t$ by $L$, and use $\mu$-strong convexity to establish the following lower bound $||g_t||^2/(f(x_t) - f(x_*)) \geq 2\mu$. These bounds are key to establishing the global linear rate of BFGS in prior work. In our setting such bounds do not hold and we do not have a universal upper bound on $||y_t||^2/s_t^\top y_t$ and a lower bound on $||g_t||^2/(f(x_t) - f(x_*))$. Instead, for the first bound, we transfer the inequality to the norm induced by the weight matrix $P = (1 + D_0)\nabla^2{f(x_*)}$ and show under this norm and strong self-concordance assumption we have $||y_t||^2/s_t^\top y_t \leq 1$. For the lower bound on $||g_t||^2/(f(x_t) - f(x_*))$, instead of a uniform lower bound, we show that it can be bounded below by $1/(1 + D_t)$, which is dependent on $x_t$, but we show that even this time-dependent lower bound is sufficient to establish a linear convergence rate for BFGS.

Second, we highlight the key difference between Lemma 4.1 and prior results in [35-38]. The proof from previous results hinged on ensuring $f(x_t + d_t) \leq f(x_t)$, i.e., that a unit step yields a decrease in function value. Under Lipschitz continuity of the Hessian with constant $K$, the error of approximating $f(y)$ by its second-order Taylor expansion at $x$ is bounded by $\frac{K}{6}||y - x||^3$. Without this assumption, and under $M$-strongly self-concordant assumption, we instead use the bound $f(y) \leq f(x) + g(x)^\top(y - x) + \frac{4}{M^2}\omega\left(\frac{M}{2}||y - x||_x\right)$ for $||y - x||_x < \frac{2}{M}$, where $\omega(x) = - x - \log(1 - x)$ is defined for $x < 1$. As a result, the error is no longer cubic in $||y - x||$, making it more challenging to ensure a function decrease. Nevertheless, we can still guarantee this property, with the main difference being that the error bound $\delta_1$ now depends on $\omega(x)$ defined above.

Please refer to the proofs of Lemmas B.5, B.7, B.8, and B.9 in the Appendix, which are entirely original. These lemmas introduce new theoretical tools developed specifically for this work under the strong self-concordance assumption and are not derived from or dependent on any prior literature.

We will add a remark in the revised paper to explicitly highlight these points. Thank you for your feedback.

Question: Is it possible to extend the global convergence analysis of the BFGS method to the broader restricted Broyden family, including methods such as the DFP method?

Response: This is an excellent question. The results in our paper are currently specific to the BFGS quasi-Newton method. To the best of our knowledge, when using an inexact line search—such as the Armijo–Wolfe line search—there is no theoretical guarantee that other quasi-Newton methods from the convex Broyden class, such as DFP, achieve global superlinear convergence.

The main challenge in analyzing DFP arises from the potentially unbounded exponential growth of the largest eigenvalue of its Hessian approximation. Without a controllable upper bound on this eigenvalue, it becomes extremely difficult to lower bound the angle between the DFP search direction and the gradient vector—a property that is crucial for establishing superlinear convergence.

For more details, please refer to the following reference:

Richard H. Byrd, Jorge Nocedal, Ya-Xiang Yuan, “Global Convergence of a Class of Quasi-Newton Methods on Convex Problems,” SIAM Journal on Numerical Analysis.

Only under exact line search does the convex Broyden class of quasi-Newton methods—including both BFGS and DFP—produce identical iterates. However, exact line search is far less practical than the inexact line search strategies considered in our work, due to its substantially higher computational cost. Extending our BFGS analysis under inexact line search to a broader class of quasi-Newton methods, such as DFP, remains an interesting direction for future research.

This is an excellent point that we will add to the revised paper. Thanks for your comment.

Question: In line 107 and 108, is the term $M|u|^3x$ a typo?

Response: Thanks for pointing out this typo. The correct version is $M||u||_{x}^{3}$. We will fix this typo in the revised submission.

Proof of the strongly self-concordance of logistic regression and the log-sum-exp function

Response: We agree with the reviewer that logistic regression does not satisfy the standard self-concordance definition. Rather, it satisfies a generalized self-concordance definition. For the strongly self-concordance proof of the logistic regression, we emphasize that in our BFGS method we use the line search scheme such that we always have $f(x_{t + 1}) \leq f(x_t)$. Hence, the iterations generated by BFGS method with weak-Wolfe line search conditions always stay in the bounded set {$x | f(x) \leq f(x_0)$} where $x_0$ is the initial point. In this bounded set, the strongly self-concordance always hold since the Hessian of the logistic regression function is strongly convex with respect to the operator matrix $B = \sum_{i = 1}^{n}z_iz_i^\top$. For example in the first dimension case, we have that $f''(x) = \sigma'(z^\top x)z$ where $\sigma$ is the sigmoid function. In that bounded domain, we always have some uniform lower bound $\mu > 0$ for this $\sigma'$. Therefore, we can use existing argument from [47] to prove that $f$ is strongly self-concordant in this domain {$x | f(x) \leq f(x_0)$}. The proof of strong self-concordance of the log-sum-exp function is similar and presented in section G of Appendix in our paper and example 1 from the following reference:

N. Doikov and Y. Nesterov. Minimizing uniformly convex functions by cubic regularization of newton method. arXiv, 1905.02671, 2019

We will supplement more rigorous proof analysis in the revised version of the submission.

It would also be nice to discuss what kind of functions satisfy standard self-concordance but is not strongly self-concordant. This is to give an idea of how strict this assumption is, since for the affine invariant analysis of Newton's method, standard self-concordance suffices.

Response: This is a great point. The log-barrier function $f(x) = -\sum_{i = 1}^{n}\log{(b_i - a_i^\top x)}$ serves as an example of a function that is standard self-concordant but not strongly self-concordant. We will include this log-barrier function as an illustrative example of such a case in the revised version of our submission.

Weakness 1 on the experimental design

Response: This is an excellent and valuable suggestion. We will extend our numerical experiments to consider both the standard coordinate system and several linearly transformed coordinate systems, allowing us to compare the performance of BFGS with first-order methods such as GD and AGD. Below, we present the results for the hard-cubic function with dimension $d = 100$. The first table reports the results in the standard coordinate system, while the second table corresponds to a linearly transformed coordinate system with an ill-conditioned matrix.

We observe that the performance of BFGS remains similar under both conditions, whereas the performance of first-order methods degrades when the linear transformation matrix is ill-conditioned. This illustrates the affine invariance property of quasi-Newton methods and confirms that they consistently outperform first-order methods across different linear transformations.

Weakness 2 on the experimental design

Response. Thank you for this suggestion. We will include additional numerical experiments using the number of gradient evaluations and the time spent as alternative x-axis metrics. Here are the results for hard-cubic function with dimension $d = 100$ with gradient evaluations and the time in terms of seconds.

Weakness 3 on the experimental design

Response: Thanks for the suggestion. We will add the plots to check how often the unit step size is accepted or rejected in our revised version of the paper. We observed that after approximately $d$ iterations, the unit step size is always accepted, which is consistent with our theoretical analysis that after approximately $d$ iterations, the BFGS method reach the superlinear convergence stage.

Weakness 4 on the experimental design

Response: Thanks for your suggestion. We can estimate the constants in the bound and we will add the curves of $(C/k)^k$ in the figures of the numerical experiments in the revised version of our submission to check that the empirical performance of BFGS method is consistent with the superlinear convergence upper bounds from the theoretical analysis.

Question 1

Response: This is an excellent question. In theory, it is possible to establish global convergence of the BFGS method using only an Armijo backtracking line search, which enforces the sufficient decrease condition without requiring a curvature condition. However, achieving superlinear convergence typically relies on some form of curvature condition, such as the Wolfe or strong Wolfe conditions. Without such conditions, providing a rigorous superlinear convergence guarantee becomes significantly more challenging.

This limitation highlights an interesting direction for future research. We believe it may still be possible to establish non-asymptotic superlinear convergence of BFGS without a curvature condition. However, in this setting, the method would likely require more iterations before entering the superlinear convergence phase compared to when the (weak) Wolfe conditions are imposed.

Question 2

Response: This is a very good question. Theoretically, it is possible to choose $\alpha$ and $\beta$ to optimize the linear and superlinear convergence rates. In practice, however, the line search parameters are typically treated as fixed constants, since the dominant factors affecting performance are the properties of the objective function, such as its dimension $d$ and condition number $\kappa$. Consequently, there is generally no need to fine-tune $\alpha$ and $\beta$ to achieve tighter convergence bounds.

Minor comments

Response. Thanks for pointing out all these typos. We will fix all of them in the revised version of our submission.

Dear authors,

Thank you for your detailed response.

I'm ok with your argument that logistic regression satisfies strong self-concordance, in that it holds true over any compact subset of the domain and as BFGS with Wolfe line search generates iterates always remain within a compact set. But by this argument, shouldn't the log barrier $f(x) = -\sum_{i = 1}^{n}\log{(b_i - a_i^\top x)}$ you mentioned later in the rebuttal also be strongly self-concordant (over any compact subset of its domain)?

Other than this, the added experimental results look great. I look forward to reading the updated version!

Questionable Significance of Affine-Invariant Guarantees

Response: We would like to emphasize that the primary contribution of our work is the development of a global, non-asymptotic convergence theory for BFGS quasi-Newton methods that respects their affine invariance. While we agree with the reviewer that the strongly self-concordant setting is not the most general, the significance of our results lies in demonstrating two key points: (i) it is possible to achieve superlinear convergence rates beyond the classical assumptions of strong convexity and Lipschitz continuity of the gradient and Hessian, and (ii) it is possible to derive a global complexity theory for BFGS that aligns with its affine-invariance properties. This work represents an initial step toward extending the analysis of BFGS to broader settings.

We also note that our result is meaningful in the context of Newton’s method. Classical global convergence analyses for Newton’s method rely on strong convexity and Lipschitz continuity, assumptions that break down in the setting of interior-point methods, where log-barrier functions are not strongly convex. The affine-invariant self-concordance framework enabled polynomial-time complexity guarantees for Newton’s method in such cases, preserving its affine-invariant nature.

Analogously, our extension of BFGS to the affine-invariant, strongly self-concordant setting lays the groundwork for quasi-Newton methods within interior-point frameworks. Our analysis provides the first global superlinear convergence result under the strong self-concordance assumption, moving beyond traditional analyses based on strong convexity and smoothness—just as self-concordance transformed the theory for Newton’s method. Building on this foundation, we aim to extend our results to the standard self-concordant setting in future work, enabling rigorous analysis of quasi-Newton methods for interior-point problems.

We will add the above point in the revised paper. Thanks for your comment.

The key technical difficulties compared with prior works [35-38]

Response: That is a valid point. We would like to emphasize that our paper is not a derivative of the works in [35–38]; rather, it extends their analysis to a substantially more general setting by removing the assumptions of strong convexity and Lipschitz continuity of the gradient and Hessian. Once these assumptions are relaxed, the theoretical tools and techniques developed in [35–38] are no longer applicable. Consequently, our analysis requires entirely new proof strategies, which we summarize in the following points.

First, the proof of Theorem 3.1 for showing global linear convergence rate is fundamentally different from the analyses in prior work. Specifically, those prior results heavily depend on the strong convexity and gradient Lipschitz-ness assumptions to showcase a linear convergence rate: they use the Lipschitz continuity of the gradient to upper bound $||y_t||^2/s_t^\top y_t$ by $L$, and use $\mu$-strong convexity to establish the following lower bound $||g_t||^2/(f(x_t) - f(x_*)) \geq 2\mu$. These bounds are key to establishing the global linear rate of BFGS in prior work. In our setting such bounds do not hold and we do not have a universal upper bound on $||y_t||^2/s_t^\top y_t$ and a lower bound on $||g_t||^2/(f(x_t) - f(x_*))$. Instead, for the first bound, we transfer the inequality to the norm induced by the weight matrix $P = (1 + D_0)\nabla^2{f(x_*)}$ and show under this norm and strong self-concordance assumption we have $||y_t||^2/s_t^\top y_t \leq 1$. For the lower bound on $||g_t||^2/(f(x_t) - f(x_*))$, instead of a uniform lower bound, we show that it can be bounded below by $1/(1 + D_t)$, which is dependent on $x_t$, but we show that even this time-dependent lower bound is sufficient to establish a linear convergence rate for BFGS.

Second, we highlight the key difference between Lemma 4.1 and prior results in [35-38]. The proof from previous results hinged on ensuring $f(x_t + d_t) \leq f(x_t)$, i.e., that a unit step yields a decrease in function value. Under Lipschitz continuity of the Hessian with constant $K$, the error of approximating $f(y)$ by its second-order Taylor expansion at $x$ is bounded by $\frac{K}{6}||y - x||^3$. Without this assumption, and under $M$-strongly self-concordant assumption, we instead use the bound $f(y) \leq f(x) + g(x)^\top(y - x) + \frac{4}{M^2}\omega\left(\frac{M}{2}||y - x||_x\right)$ for $||y - x||_x < \frac{2}{M}$, where $\omega(x) = - x - \log(1 - x)$ is defined for $x < 1$. As a result, the error is no longer cubic in $||y - x||$, making it more challenging to ensure a function decrease. Nevertheless, we can still guarantee this property, with the main difference being that the error bound $\delta_1$ now depends on $\omega(x)$ defined above.

Please refer to the proofs of Lemmas B.5, B.7, b.8, and B.9 in the Appendix, which are entirely original. These lemmas introduce new theoretical tools developed specifically for this work under the strong self-concordance assumption and are not derived from or dependent on prior literature.

We will add a remark in the revised paper to explicitly highlight these contributions. Thank you for your feedback.

Limited Scope of Assumptions

Response: We appreciate the reviewer’s observation regarding our assumption of strong self-concordance. This assumption was chosen deliberately, as it enables a clean and tractable analysis while still covering a broad and practically relevant class of problems, including certain regularized models in machine learning. Our goal was to move beyond the more restrictive assumptions of strong convexity and Lipschitz continuity of the Hessian, which often exclude these settings. We agree that extending our analysis to more general forms of self-concordance—such as the standard self-concordance commonly used in the analysis of Newton’s method—would be a natural and valuable direction for future work.

Inappropriate Citation

Response: We agree that citing informal sources such as Math Stack Exchange is not ideal for a formal academic publication. Our intention was to provide an accessible explanation for a well-known but perhaps hard-to-locate fact. In the revised version, we will replace this citation with references to the formal source that rigorously establishes the result. Thanks for pointing out this issue.

Minor comments

Response Thanks for pointing out all these typos. We will fix all of them in the revised version of our submission.