Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance
Authors: Qiujiang Jin
Aryan Mokhtari
Venue: NeurIPS 2025 spotlight ()
Keywords: Convex Optimization
Quasi-Newton Method
BFGS Algorithm
Global Convergence Analysis
Self-Concordance
Primary area: optimization

Abstract: In this paper, we establish global non-asymptotic convergence guarantees for the BFGS quasi-Newton method without requiring strong convexity or the Lipschitz continuity of the gradient or Hessian. Instead, we consider the setting where the objective function is strictly convex and strongly self-concordant. For an arbitrary initial point and any arbitrary positive-definite initial Hessian approximation, we prove global linear and superlinear convergence guarantees for BFGS when the step size is determined using a line search scheme satisfying the weak Wolfe conditions.  Moreover, all our global guarantees are affine-invariant, with the convergence rates depending solely on the initial error and the strongly self-concordant constant. Our results extend the global non-asymptotic convergence theory of BFGS beyond traditional assumptions and, for the first time, establish affine-invariant convergence guarantees—aligning with the inherent affine invariance of the BFGS method.

Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance
Qiujiang Jin UT Austin suujianngjn00@maill com
Aryan Mokhtari UT Austin & Google Research mokhtari@austinn utexas. edu
Abstract
In this paper, establish global non-asymptotic convergence guarantees for the BFGS quasi-Newton method without requiring strong convexity or the Lipschitz continuity of the gradient Hessian. Instead, we consider the setting where the objective function is strictly convex and strongly self-concordant, For an arbitrary initial point and any arbitrary positive-definite initial Hessian approximation, we prove global linear and superlinear convergence guarantees for BFGS when the step size is determined using a line search scheme satisfying the weak Wolfe conditions. Moreover, all our global guarantees are affine- invariant, with the convergence rates depending solely on the initial eгror and the strongly self-concordant constant. Our results extend the global traditional assumptions and, for the first time, establish affine-inee invariant convergence guarantees aligning
asymptotic convergence theory of BFGS beyond
aliignng with the inherent affine invariance of the BFGS method.
Introduction
In this paper, we consider the convex optimization problem
min f(x), HER
(1)
where the function f is twice differentiable and strictly convex. We focus on quasi-Newton meth- ods ods-iterative optimization algorithms that approximate the Hessian and its inverse using gradient information, making them efficient for large-scale problems where computing the Hessian costly. Different variants update the Hessian approximation in distinct ways. The most famous quasi-Newton methods include the Shanno (BFGS) method (6 the Symmetric Rank-One (SR1) method (7) 8. and the Broyden method [9. There are also variants of these methods, including limited memory BFGS [T0] [I]. randomized quasi-Newton methods [12 and greedy quasi-Newton methods (15188.
(DFP) method 122, the Broyden-Fleteie
In this paper, we focus exclusively on the BFGS method, one of the most widely used and well- regarded quwsi-Newton algorithms. Specifically, we analyze its convergence guarantees in the setting where the objective function is strictly convex and self-concordant and establish aon-ssympo guarantees for this case. Before highlighting our contributions, we first provide a summary of the existing convergence guarantees for BFGS established in prior work.
Classic asymptotic guarantees. The local asymptotic superlinear convergence of quasi-Newton methods, including BFGS, has been established in several works (19)28). Similarly, their global convergence under globalization strategies like line search and trust-region methods has been ana- However, these results are asymptotic and lack showing explicit rates.
lyzed S 2
Non-asymptotic guarantees under stronger assumptions. Recently, there were several break- throughs regarding the non-asymptotic local superlinear convergence analysis of BFGS including [35]- 38 for the case that the objective function is strongly convex. More precisely, these works established
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

an explicit superlinear rate of (t) under the assumptions of strong convexity and Lipschitz continuity of the gradient and Hessian, given that the initial point within a local neighborhood of the optimum and the initial Hessian approximation satisfies certain conditions. Later, these local analyses were extended and non-asymptotic global convergence rates of BFGS were established in [39 [22] under similar assumptions on the objective function. In particular, 44 established global explicit superlinear convergence guarantees of the whole convex class of Broyden's 's family of quasi-Newton methods including both BFGS and DFP with step size satisfying the exact line search schemes. In follow up work 22. the explicit global convergence rates for BFGS was established when deployed with inexact line search satisfying the Armijo-Wolfe Wolfe conditions. Specifically, these works show that when the objective is j--strongly convex, its gradient is L-Lipschitz smooth, and its Hessian is K- K-Lipschitz continuous, global linear convergence rate of (1 1/x)* can be that of gradient descent, where k = [/ is the condition number. Moreover, global superlinear convergence rates of ((dx + Ct))/tt and ((Cad log + Ct were established under specific choices of the initial Hessian approximation, where d the problem dimension, and Co is the initial function value gap between the initial iterate To and the unique optimal solution T..-
While these results represent significant progress in studying quasi-Newton methods, the established non-asymptotic guarantees for BFGS, and most quasi-Newton methods in general, have two major limitations. First, these results rely on relatively strong assumptions that may not hold in many practical settings. For instance. in the case of logistic regression, the loss is strictly convex but not necessarily strongly convex. Similarly, a bog-barrier function does not satisfy the global Lipschitz condition for gradient. Second, all previously established non-asymptotic convergence rates for BFGS are not affine invariant, as they depend on parameters such as the strong convexity constant μt, gradient Lipschitz constant I., and Hessian Lipschitz constant K, all of which vary under a change of basis coordinate system in Rdd In contrast, BFGS is affine invariant with respect to linear transformations of the variables. This means that the convergence behavior of BFGS remains unaffected by the choice of coordinate system and instead depends solely on the topological structure of f.
Contributions: We aim to address the discussed issues, and our main contributions are as follows:
We establish global non-asympiotic linear and superlinear convergence rates for BFGS without requiring strong convexity or Lipschitz continuity of the gradient or Hessian. Instead, we consider functions that strictly convex and strongly self-concordant. Our analysis provides explicit global convergence guarantees for BFGS when the step size is selected via a line search satisfying the weak Wolfe conditions. These guarantees hold for any initial point To and any positive-definil initial Hessian approximation By.
We derive explicit convergence rates for the BFGS method that are affine invariant. Specif- ically, our results show that both global linear and superlinear convergence rates depend solely on the strongly self-concordant constant, which remains invariant under linear trans- formations of the variables. To the best of our knowledge, these are the first theoretical convergence rates consistent with the affine invariance property of the BFGS method, reflecting its independence from the choice of coordinate system.
Notation. We denote the 12-norm by || and the set of d x d symmetric positive definite matrices by S4 + We write < trace and determinant of matrix A are represented as Tr(A) and Det(A), respectively. For function that is strictly convex, we define the weighted norm I|- as allaa Vul (2f(x)u
is positive semi-definite, and A x it is positive definite. The
2 Background and Preliminaries
In this section, we provide brief overview of the BFGS quasi-Newton method. At iteration Te denotes the current iterate, 9: = fx(x) the gradient of the objective function, and B, the Hessian approximation matrix. The general template of quasi-Newton methods update is given by
1 24 + Tede,
de - gt.
where 7/ > 0 is the step size. By defining the variable difference and the gradient difference as
3t == Tt+1
Zt,
yt = - -ffte)))-(aa))) vf(=)),
(3)
2

---

we can present the Hessian approximation matrix update for BFGS as follows:
B,315 Br
+ yt
B++1 = B,
(4)
89 Bist 8/ yt
Further, if we define the inverse of Hessian approximation as H2 == B using the Sherman- Morrison- Woodbury formula, we have H4+1 = (T te H.(T
ye 9.9,) + yr s,2; Note that the
function f is strictly convex as considered in this paper and the initial Hessian approximation matrix is positive definite, then B, E 8 for any iterations > 0 (Chapter 6 (43). In this paper, we
focus on the analysis of BFGS when f/e is selected based the Armijo- Armijo-Wolfe Wolfe conditions, given by
f(z + mede) S f(x)) + am V))r) de.
(5)
ff(z, + md)) de 2 fzx()))) T de.
(6)
where a and are the line search parameters, satisfying 0 < a 3 < and <<6 a 1/2.
it is known that the iterates of BFGS are affine invariant. This property underscores the necessity of an analysis framework aligned with affine invariance, which is the main focus of our paper. We state the following proposition for completeness.
Affine Invariance property of BFGS. From 44 45
Proposition 2.1. Let the iterations { + be generated by the BFGS algorithm applied to the
objective function (x), as defined in 2 2).4). Consider the iterates { ) produced by applying BFGS to the transformed function σ(x) f f(A)). where A E. Raxd is non-singular matrix. Assume that the initializations satisfy ing- A x0 and Bo = A BaA. Then, for any i 0, the following
relationships hold: it- A Tt, B. A B,A and ((ix)) (axe).
2.1 Assumptions
Next, we state our assumptions and compare them with those used in prior work. Assumption 2.2. The function satisfies the following conditions: (i) it is twice differentiable and strictly convex, and (ii) it is strongly self-concordant with parameter > 0, i.e, for any x, y, 2 E IR
f² v f(v) 3 M| vll= (Illv(((v)))
Our first assumption requires the objective funetion be strictly convex, i.e., (2f(x) > 0. This is indeed a weaker condition than the strong convexity assumptions used in prior works that establish non-asymptotic guarantees for BFGS, such as (35/42). The second condition concerns strong self- concordance, which defines subclass of self-concordant functions. Specifically, if f is M-strongly self-concordant, then it is also M/ a//o-self-ooncordaan. To see this, fix x R2 and Rd. The inequality u. (V2f(a tu) (²f(r))u +M] [|]] holds, and dividing by and taking the limit as I + 0 yields D3 [(x)(u, u, u) < [ A symmetric argument shows [(x)(1 u, u|| S M|lu M| 3. implying that I is self-concordant with parameter M/2. Moreover, Theorem 5.1.2 of [66] shows that the strong seff-concordance parameter M is affine invariant: for any non-singular
A E dddd the function (xx) f(Ar remains M-strongly self-concordant.
Next, we explain why our assumptions are strictly weaker than the more common conditions of strong convexity, Lipschitz gradient, and Lipschitz Hessian. Prior work (e.g.. Example 4.1 in [7) shows that if function is strongly convex and its Hessian is Lipschitz with respect to a matrix B -- 0, then it is also strongly self-concordant. However, the converse does not hold: strong self-concordance does not imply strong convexity, gradient smoothness, or Lipschitz Hessian continuity.
As a concrete example, we can consider the log-sum-exp function formally defined as f(x) = log (E exp(c, æ 1- 6.)) + Σm x)²² where {c) E E and {6. E R. This function not strongly convex with respect to the identity matrix I, due to the absence of explicit & regularization. However, it can be shown to be strongly convex and have Lipschitz Hessian with respect to the matrix B = Σn G.e, (Note that this matrix could be possibly singular). As result, it is strongly self-concordant but not strongly convex in the standard sense; check Appendix F Other examples include the hard cubic function and the logistic regression objective discussed in Section ( Another illustrative case is the log log-barrier function f(x)
log(1 x²), which is strongly self-concordant with M = for [x - yl S 1/2, yet its gradient and Hessian are not Lipschitz continuous. Full detailed discussion for these examples is provided in Appendix F
3

---

2.2 Definitions
Next, we state our definitions and notations. For any A E $4 define ((4) as
((A) == Tr(A) - log (et(A).
(8)
This function characterizes the distance between matrix A and the identity matrix I. Note that V (4) 2 0 for any A E $$ and (A)
if and only if A =
A common technique in the analysis of quasi-Newton methods involves the use of a reweighting matrix; see, e.g.. (29). We also use this approach in our analysis. Specifically, given any weight
matrix P E S4 4. + we define the weighted versions of the vectors gr, St, yt. de and the matrix B,
P gt. P ;=:=
yt: d P P
The weight matrix P plays fundamental role in our proof and the global linear and superlinear convergence rates are based on different choices of P. Note that the update rule for the weighted version of Hessian approximation matrices B, is similar to the update rule of the unweighted B,, i.e., B++1 B.
B.a.8, B.
B. We next introduce common function in self-concordant analysis: 8g du
5, R.
w(x) == log (a + 1).
(10)
As shown in Lemma B.3 (x) is strictly increasing for x > O. Hence, we can define its inverse function w (.) such that w (w(z))
for x > 0. It can be verified that (=)) is also strictly increasing for > O. Further, since (xz) is a convex function, w (=x) is concave. We use w-1 to measure suboptimality of the iterates { = and define the sequences {Cr and {De) as
:= f(x)) f(.))
: (M/)
(11)
Indeed, both of the above sequences are always non-negative.
Remark 2.3, The expression w (.) frequently appears in our complexity bounds. To better under- stand this function and its approximation, as shown in Lemma B.3 we can the approximation (a) s (a + /2a). Consequently, if < 1, w (a) O a.), and if a > 1, (a) O(a).
With these preliminaries, the next two sections prove global linear and superlinear convergence rates of BFGS for strictly convex, strongly self-concordant functions rates that remain invariant under linear transformations, consistent with BFGS's s affine invariance.
3 Global Linear Convergence Rates
In this section, we present the global linear convergence results of BFGS when the step size selected based on the weak Wolfe conditions introduced in (5) and (6. Before we begin, we need to define the following weighted versions of the initial Hessian approximation matrix Bo:
42 V fx.)) - V f(x.)~+
Bg
Bo = ('= ((c
(12)
1+ Do
These two weighted versions of Bu correspond to the weight matrices P (1+ D2) f(x and P = fz.). respectively. They play a key role in the non-asymptotic analysis of BFGS for seff-concordant functions. Next, present our first global explicit linear convergence rate of BFGS for any initial point xo and any initial Hessian approximation matrix By E $
Theorem 3.1. Suppose Assumption 2.2 holds. Let {æ+ bezo be the iterates generated by BFGS. where
the step size satisfies the Armijo Wolfe conditions in 5) and (6) Recall (-) in 8. Do in [I] and
Bo in 122. 2 For any initial point xo E TR. and any initial Hessian approximation Bg E Sd we have
f(x)) - fxxx) f(xo) - fxx))
S a(1 33
*(Bp)
(13)
(1 + Do)²
Moreover, when (Bo), we obtain that
f(xe) - f(xx)
5 (1
a(1 3)
(14)
f(x0) - f(x.)
3(1 + Do)

---

Theorem 3.1 states that BFGS converges globally at linear rate, influenced by the line search parameters (as expected), the term V (Bo), which quantifies the discrepancy between the initial Hessian approximation and the optimal one, and Do. which depends on the suboptimality of the initial function value and the strongly self-concordance parameter. To further simplify the expression, as shown in the second result, when ł 2 V Bo). the linear convergence rate can be further simplified as O(1 - 1/(1 + )) Hence, Do = 2 1 (f(o)) - //4) indicates the rate.
Two remarks follow the above result. First, our global linear convergence rate does not require assuming strong convexity or gradient Lipschitz-ness, ness.. Second, the linear convergence rate is affine invariant across different linear systems, consistent with the affine invariance property of BFGS.
We emphasize that the proof of Theorem 3.1 for showing global linear convergence rate is fundamen- tally different from the analyses in prior work. Specifically, the results in [1 38 42 heavily depend on the strong convexity and gradient Lipschitz-ness assumptions showcase linear convergence rate: they use the Lipschitz continuity of the gradient to upper bound |luel2//s by I., and use u-strong convexity to establish the following lower bound 9g ||
f(x))) 2 2p. 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 /s, 3/+ and lower bound on [1 (oell//(((zz)) - f (x.)). Instead, for the first bound, we transfer the inequality to the norm induced by the weight matrix P (1+ V2) assumption have | 19/8 Dr 1. For the lower bound on /g.]1//(((xx) - I (x=)), instead of a uniform lower bound, we show that it can be bounded below by 1/(1 + D.). which is dependent
and show under this norm and strong self self-concordance
on It, but we show that even this time-dependent lower bound is sufficient establish a linear convergence rate for BFGS. For more details check the proofs of Lemma B.7 and Section C.2 in the Appendix.
The linear convergence result depends on V (Bo). and hence the choice of Bg affects the convergence rate. In practice, it is often a scaled identity and a common choice is Bg = cT, where = (sTy) ||= with 22 I1, y V (1²) - (z()). and 22 as two randomly selected vectors. In the next corollary, we present our global linear rate when Bg- = aT where > is an arbitrary constant.
Corollary 3.2. Suppose Assumptions 2.2 holds, (2re)20 are generated by BFGS with step size satisfying the Armijo- conditions in and (6) and 20 I& is arbitrary initial point. If the initial Hessian approximation matrix is set as Bo = a. for any a > O, then we have that
f(x)) f(x.) [(x0) - fxx))
(1 (
1
a(1 3)e 4
(15)
Do)
where A == [(x))
can be written as
D+Da
a 2 [xx))
A Tr
d - log Det
(16)
1 Do
1 Do
Moreover, when t 2 A,, we obtain that
f(x)) - fxx)) f(xo) - f(x)) < (1 a<l 99)
(17)
3(1 + D
Note that the proof of this corollary simply follows by setting By = al in Theorem 3.1 The above result shows that by selecting Bu al, the linear convergence rates of the BFGS method is totally determined by the initial suboptimality Do and the trace and determinant of the inverse matrix of the Hessian r., which are also consistent with the affine invariance property of BFGS.
Next, we proceed to present an improved version of the result Theorem 3.1 showing that after a sufficient number of iterations, the linear rate of BFGS becomes independent of Do and Bo-
Theorem 3.3. Suppose Assumptions 2.2 holds, and let tezo be the iterates generated by the BFGS method with the Armijo- Wolfe line search in (5) and (6). Recall the definition of (-(-) in (8. Do in
(TT) and Bo. Bu in (1). Then, for any initial point zo E TRdd and any initial Hessian approximation
matrix Bn E Sd when 1 2 V (BB)) + 3D (V (B) + a(1-p)
3()+D))) ), we have
f(x)) fxxx)
2a(1 - -B)
[xo) - f(x,) <
1-
(18)
3
5

---

This theorem demonstrates that when the number of iterations is larger than (Bb)) + 3Do ( - 3(1+Do)²
a(1-8) BFGS with stepsize satisfying the Armijo-Wooo Wolfe conditions achieves an explicit linear convergence rate that is independent of the initial suboptimality Do and only determined by the line search parameters a and / defined in (5) and (6). That said, the point that transition this fast rate happens still depends on the choice of zo and Ba, as stated in Theorem 3.3 Similar to Corollary 3.2
next we present the special case of Theorem 3. of Bu al for any a >0.
Corollary 3.4. Suppose Assumptions 2.2 holds, { satisfying the Armijo-Wolfe conditions in and (6) and 2o I& is an arbitrary initial point. If the initial Hessian upproximation matrix is set as Bu - al for any a > O, then the following rate holds
generated by BFGS with step size
f(xa) f(x.) <
-0(1-
20(1 - -3)
(19)
[100) (((r))
3
for all iterates satisfying 2 2 + +3D [ + 3(1+Do)²) where A is defined in (66) and
A (r ((x.) - d log Det(aV2
(20)
Note that both A and A₂ are determined by the Hessian the optimal solution I.,, while A also depends on the initial suboptimality error through Do. In general, we do expect the convergence rates of BFGS to depend on the distance between Zpp and r., which is characterized by Do defined in (IT)
as well as the distance between the initial Hessian approximation matrix Bo and the exact Hessian at optimal solution Is, which is characterized by A and A₂ when Bo = al.
Global Superlinear Convergence Rates
Building the established linear convergence results, next establish our global superlinear convergence rate of BFGS. A key point in our analysis is that to reach the superlinear convergence stage, the unit step size must be chosen after some iterations. This is necessary condition, as noted in several prior works 30 32 29] The fundamental methodology is to first establish the sufficient conditions of when the unit step size can be selected, i.e., when 7 1 satisfies the conditions in (5) and (6). Then, based on these conditions, we can prove that after some specific iterations to, the unit step size т)t 1 is admissible for the inexact line search scheme except for finite number of iterations, which leads to the final proof of the global non-asymptotic superlinear convergence rate.
Next, we proceed to establish under what conditions 17 1 is admissible. First, define Ps
Pr = -9e de
d=
v2 ((.)))
14 2 0.
(21)
1
In the following lemma, we demonstrate that when C, f(xx) (a.)) is small enough and p. is close enough to 1, the unit step size V/e = 1 is admissible and meets the Armijo conditions.
Lemma 4.1. Suppose Assumption 2.2 holds and define
4
4
2 ()]1-a)--
a) -1
4
(
((i1--1))
8 min
16' M2
32
M
M2
w
(
(22)
15
1
82 max
83 ==
16'
22
V1 3
which satisfy 0 < 81 < 82 < < 83. IfC, S 8n and 82 S p: S 8g. then 1) satisfies 5 and 6
First, we highlight the key difference between Lemma 4.1 and prior results in 38
The proof
of Lemma 4.1 hinges on ensuring of (xx +d) < f1x1), 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(v by its second-order Taylor expansion at z is bounded by K lly - xx13. Without this assumption, and under M-strongly self-concordant assumption, r) + Naw. (o lly æ=1z) for |/y =lIa M. where w. (x)
instead use the bound f(v) < f(x) + 9(x)) (v loog(1 2)) is defined for 1.
As result, the error is no longer cubic in Vyy x making it more challenging to ensure function

---

decrease. Nevertheless, we can still guarantee this property, with the main difference being that the error bound 8, now depends on wxx) defined above. See Lemma B.9 and Section C.4 for details.
The result in Lemma 4.1 shows that when C. S ó1 and E [62, 6a]. we can choose the step size "e = at iteration of BFGS, it satisfies the weak Wolfe conditions. Moreover, from the global non-asymptotic linear convergence rates of the last section, we can specify the to such that for any t 2 to. the first condition C. < ô1 always holds. Moreover, we can demonstrate that the second condition on is violated only for finite number of iterations, i.e. the set of the indices that Pt $ [8g. 63] can be upper bounded by some constants. We formally present these results in the following lemma and the proofs are available in Appendix C.5
Lemma 4.2. Suppose Assumptions 2.2 holds and (zi)e20 are generated by BFGS with step size satisfying the Armijo-Wonn conditions (5) Recall the definition of C2 in (II). D2 in (TT. (-))
{5.) in (2 and Bo, Bo
We have C. S 81 when 2 to, where to is defined as
3(1 + Do)2
Co
to = max (Bb),,
log 81 S
(23)
a(1
Moreover, the size of the set I {to sist-11 Pt & [82, 53]3 is at most
I s 54 (((B)) + 2Do (Bb) + 3(1 + 1o)²) 111+bD))) a(1 - )) where 54 == min 1), (03 1)} (24)
1
The above lemma specifies the time instance lo for which C, S 61 is satisfied for any L 2 to and for only finite number of indices, the condition P: E [82, 63] does not hold. In practice, we always start with the unit step size when we implement the inexact line search scheme at iteration to check = 1 satisfies the Armijo- Wolfe conditions in (5) and (6) Hence, when 2 to. only for a finite number of iterations that At & [82, 63). the unit step size is not selected. With all these points, we present the global superlinear convergence rate of BFGS for self-concordant functions.
Theorem 4.3. Suppose Assumptions 2.2 holds and the iterates {are J120 are generated by BFGS with step size satisfying the Armijo- Wolfe conditions in (5) and (6). Recall the definition of De (TI.
(-) in (8). By, Bo (12), and {6 (22). 24.. Then, for any initial point ag E Rd and any
initial Hessian upproximation matrix By E
S 44 the following global superlinear result holds:
f(x)) - [(xx)
Solo + 5
+ 8g 5g (B)
+
30+DD)) a(l-3)
t
f(x0) - f(x.) $
where to is defined in (33
(d: defined below only depend on line search parameters a and B
2 (2/52)
45g
1
55 = max
25 17/16'
25 - 17/16 {
252-17/10
66 log
2a - -3)
(25)
26g 1/16
log 82
87 1 1 5506 + 85.
8g 2 26 + 25g +
282 - 17/16
Theorem 4.3 shows that the superlinear convergence rate of BFGS for self-concordant function is of the form (C/t)² for some constant C' > O. Notice that from the definition of to in (23). we know that to ( + (1 + Da)² log Da). Hence, the superlinear convergence rate of the order O(( W D. (LL)(
and we reach the superlinear convergence stage when t 2 ((V(BB) + Do ( (B,) + (1 + ))) which depends on the initial suboptimality Dg and the initial Hessian approximation matrix By. To our knowledge, this is the first non-asymptotie global superlinear convergence rate of a quasi-Newton method without the assumption of strong convexity. Moreover, the superlinear rate in Theorem 4.3 is independent of the linear system chosen for the variables, and, hence, it is consistent with the affine invariance property of BFGS. Next, we present 0.
the superlinear convergence rate of BFGS for the special case of B = al, where
Corollary 4.4. Suppose Assumptions 2.2 holds, {x:)120 are generated by BFGS with step size satisfying the Armijo Wolfe conditions in and 66 and 20 I is arbitrary initial point. If the
7

---

initial Hessian approximation matrix is Bo = al where >> O, the following result holds:
[(x))- 0o
3()+Do)
a(1-8)
f(xo) - f(x.)
t
where to is defined in (33 {6: are defined in
25
and 11, D2 are defined in (16). (20).
5 Complexity Analysis
Iteration Complexity. Using Theorems 3.3 and 4.3 we characterize the global iteration complex- ity of BFGS with inexact line search conc-connnda functions. These three results provide upper bounds, and the smallest these bounds determines the complexity of BFGS. The smallest bound de- pends on the required accuracy relative the problem and algorithm parameters. Specifically, for any + initial point Zi E R and initial Hessian approximation matrix By E S +. to achieve a function value accuracy of 0, i... f (ITT) f(x.) S the number of iterations reguired, per Theorem 3.1 is most 7 O (Bo) + (1 + Do) log 2). The result in Theorem 4.3 eliminates the multiplicative factor in the (1c) term but requires a possibly larger additive constant, resulting in complexity of 72 ( (b) + (v) + (1 + )) + log !)) Indeed, T2 is smaller than 7i when is small and log becomes the dominant term. When is very small, the superlinear bound from Theorem 4.3 provides the best complexity, which is T3 of (log 11/log + v( (9: Pol-yp0 log
Given these three bounds the overall iteration complexity of BFGS for the considered setting is T= min (T1, T2, Ts}. Note that, for the special case of Bo aT where a > 0 an arbitrary positive constant, the complexity bounds denoted by Tı, T2, T3 can be further simplified as
Ti - --((A+((++D)) :
T: = (1 )). T3 =
log V
log
log
where A1, A2 are defined in 16.. 22)). and C₁ = D2 + (A1 + (1 + Do) For full iteration complexity details, see Appendix D
Line Search Complexity. While the previous section characterized the complexity of BFGS under Assumption 2.2 analyzing its gradient complexity requires determining the number of gradient queries needed per iteration to obtain an admissible step size. [4), the authors proposed an efficient log- bisectionnnn approach for step size selection in BFGS, satisfying the line search conditions in (5) and (6). and provided a complexity analysis. However, their results apply only to strongly convex functions with Lipschitz-continuous gradients and Hessians. In this section, examine the line-search complexity of the log-bisection approach from convex and strongly self-concordant. Let A, denote the average number of iterations in Algorithm I required to terminate after iterations. The following proposition provides an upper bound for Aç-
42 when the objective function is strictly
2.2 holds. Let ( be generated by BFGS with step size satisfying the Armijo- Wolfe conditions (5) and (6) and is chosen by Algorithm 7 Let N2 be the average number of the function value and gradient evaluations per iteration in Algorithm| Saatam/aafttr aater t iterations. For any initial point Ig E R.d and initial Hessian approximation Bo Sd
Proposition 5.1. Suppose Assumptions
E.. we have that
+T A = ( 1 + log (I 1+ (+++) + log [++og((1+ 1 + (B(B) +T
t
where I = O(D, - 2o)) As corollary, for the special case of Bo = al where > 0. we have A, = 01 + log(1 + log(1 (1 + dxtf))), where i =0 (Do( A + (1 Do)
This proposition implies the average number of iterations in Algorithm is at most O (1 +T), which is a constant depending on the initial suboptimality Do and the initial matrix Bo. Moreover, when the number of iterations T exceeds Ω (Ba) +T), the average number of function and gradient evaluations per iteration for Algorithm I is an absolute constant of O(1). Thus, even in the worst case, the gradient and iteration complexities remain of the same order, up to logarithmic factors.

---

10
10
BEG3 BFGS
BEGS BFCS cI
16
AGD
AGD
10
10
120
210
900 1800
number of iterations &
number of iterations lt
(a) d 100.
(b) d 1000.
Figure 1: Convergence rates BFGS with different Bo gradient descent and accelerated gradient descent for solving the hard cubic function with different dimensions.
10
10
10
(10
10
10
BPGS
BEGS REEGS cl
10
BPGS cl
10
AGD
AGD
10
1040
number of iterations A
number of iterations k
(a) d 100.
(b) 1000.
Figure 2: Convergence rates BEGS with different Bg, gradient descent and accelerated gradient descent for solving the logistic regression function with different dimensions.
Numerical Experiments
Next, we present numerical experiments applying BFGS to two functions satisfying Assumptions 2.2 We report our results using two different choices of initial Hessian approximation Bo: (i) Bo 7, and (ii) Bo = cl, where c- | selected. The line search parameters also set also report the convergence paths of gradient descent (GD) and accelerated gradient descent (AGD), with step sizes determined using backtracking line search.
=_y with 22 21, f((2)) - Vz(x)), where æ1, 22 are randomly 0.1 and = 0.9. In our experiments,
The first function that we study the cubic function from 47
| A A |z|
x A
f(x) 12
Σ ol v.412)) wonl
where g(x)
J A.
Note that g R R. We set the hypermeters of the objective function as W1 = 4, = 3, A and the vectors {ur set to be the orthogonal unit basis vectors of Rdd We study this function as it serves as a benchmark for establishing lower bounds for second-order methods. The second loss is the logistic regression: and J. are their corresponding labels. We assume that Rd generated with standard normal distribution and y/ E {-1, 1 generated with uniform distribution for all < N. We choose the number of data points as N d. Note that both the hard cubic function and the logistic regression function are strictly convex and strongly concordan:,,,; see Appendix
f(x) N EN In (1 + 9:2, ²), where {2; J.v are the data points
The convergence paths for the cubic problem are shown in Figure for various problem dimensions Initially, the performance of BFGS is worse than that of the first-order gradient descent and accelerated gradient descent methods. However, after approximately d iterations, BFGS significantly outperforms the first-order methods. Notably, for this problem, the performance of BFGS with Bo I and Bo cl nearly identical. Figure shows the convergence paths for the logistic loss

---

10
16
Step Size
10
Step Size
10
10"
10
BDGS d
DFGS
104
107
500
2100
2000
Number of iterations
Number of iterations k:
(a) 100.
(b) d 1000.
Figure 3: Step size of BFGS with different Bg using inexact line search for solving the hard cubic function with different dimensions.
10
9F18
BPGS
-1P22 TTnoo
BPGS Trane
G1D
GD Tiacs
CD Thore
AGD
ACD
30
01
50
120
150 180
210
200
270
300
300 500
900
1200 1500 1800 2100 2002 2700 2000
number of iterations
number of iterations k
(a) d = 100.
(b) d = 1000.
Figure 4: Convergence rates of BFGS with different Bu, gradient descent and accelerated gradient descent for solving the hard cubic function with transformation matrix A.
across different problem dimensions d. Initially, BFGS performs similarly first-order methods, but after several iterations, it outperforms them. Notably, in this experiment, BFGS with Bg = cl outperforms BFGS with B,- T. We also compared the performance of these different optimization methods with respect to the number of gradient evaluations and the time in seconds. Please check Figure and Figure in Appendix and any other additional numerical experiments.
Moreover, we display the step sizes selected at each iteration by the inexact line search the BFGS method in Figure 3 We observe that the step sizes initially very small, then gradually increase, and after approximately d iterations, they stabilize at for nearly all subsequent iterations. This confirms theoretical analysis: BEGS enters the superlinear convergence phase after about d iterations, and there are only limited iterations where the unit step size didn't satisfy the weak Wolfe condition proved in Lemma 4.2
Finally, in Figure 4 we compare the performance of BFGS, GD, and AGD under transformation matrix A chosen to be non-singular ill-conditioned matrix. We observe that the convergence trajectory BFGS with this transformation is identical to that the vanilla BFGS method, consistent with the affine invariance of quasi-Newton methods proved in Proposition 2.1 In contrast, the performance GD and AGD degrades significantly under the transformation matrix, since first-order methods do not possess the affine-invariane property.
7 Conclusions
We established non-asymptotic global linear and superlinear convergence rates for the BFGS method strietly convex and strongly self-concordant functions, using Wolfe step sizes. Our guarantees hold for any initial point up g and any positive-definite initial Hessian approximation Bp e $#1. Our analysis also respects the affine invariance of BFGS. A limitation is the reliance on strong self-concordance; extending results to standard self-concordance is a potential future direction.
10

---

References
[1] WC Davidon. Variable metric method for minimization. Technical report, Argonne National Lab., Lemont, III., 1959.
[2] Roger Fletcher and Michael JD Powell. A rapidly convergent descent method for minimization. The computer journal, 6(2):163-168, 1963.
[3] Charles Broyden. The convergence of single-rank quasi- guasi-Newton methods. Mathematics of Computation, 24(110):365-33 382, 1970.
[4] Roger Fletcher. A new approach to variable metric algorithms. The computer journal, 13(3): 317-322, 1970.
[5] Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathe- matics of computation, 24(109):23-26, 1970.
[6] David F Shanno. Conditioning of quasi-Newton methods for function minimization. Mathemat- ics of computation, 24:4176: 1970.
[7] Andrew R. Conn, Nicholas I. M. Gould, and Ph L Toint. Convergence of quasi-Newton matrices generated by the symmetric rank one update. Mathematical programming, 50(1-3):177-195, 1991.
[8] H Fayez Khalfan, Richard H Byrd, and Robert B Schnabel. A theoretical and experimental study the symmetric rank-one update. SIAM J. Optim., 3(1):1-24, 1993.
[9] Charles G Broyden. class of methods for solving nonlinear simultaneous equations. Mathe- maticy of computation, 19(92):577-593, 1965.
[10] Dong C Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimiza- tion. Mathematical programming, 45(1-3):503-523 1989.
[11] Jorge Nocedal. Updating quasi-Neus quasi-Newton matrices with limited storage. Mathematics of compu- lation, 35(151):773-782 1980.
[12] Robert Gower, Donald Goldfarb, and Peter Richtárik. Stochastic block BFGS: Squeezing more curvature out of data. In International Conference on Machine Learning, pages 1869-1878. PMLR, 2016.
[13] Robert M Gower and Peter Richtárik. Randomized quasi-newton updates are linearly convergent matrix inversion algorithms. SIAM Journal on Matrix Analysis and Applications, 38(4):1380 1409, 2017.
[14] Dmitry Kovalev, Robert M Gower, Peter Richtárik, and Alexander Rogozin. Fast linear convergence of randomized bfgs. 1331 2020.
[15] Dachao Lin, Haishan Ye, and Zhihua Zhang. Greedy and random quasi-Newton methods with faster explicit superlinear convergence. Advances in Neural Information Processing Systems, 34:6646-6657,, 2021.
[16] Dachao Lin, Haishan Ye, and Zhihua Zhang. Explicit convergence rates of greedy and random quasi-Newton methods. Journal of Machine Learning Research, 23(162):1-40, 2022.
[17] Anton Rodomanov and Yurii Nesterov. Greedy quasi-newton methods with explicit superlinear convergence. SIAM Journal Optimization, 31(():785-811 2021.
[18] Zhen- Yuan Ji and Yu-Hong Dai. Greedy psb methods with explicit superlinear convergence. Computational Optimization and Applications, 85(3):753-786, 2023.
[19] Charles George Broyden, John E Dennis Jr, and Jorge J Moré. On the local and superlincar convergence of quasi-Newton methods. IMA Journal of Applied Mathematics, 12(3):223-24) 1973.
[20] John E. Dennis and Jorge Moré. A characterization of superlinear convergence and its application to quasi-Newton methods. Mathematics of computation, 28(126):549-66) 1974.
11

---

[21] Andreas Griewank and Ph L Toint. Local convergence analysis for partitioned quasi-Newton updates, Numerische Mathematik, 39(3):429 448, 1982.
[22] JE Dennis, Héctor J Martinez, and Richard A Tapia. Convergence theory for the structured BFGS secant method with an application to nonlinear least squares. Journal of Optimization Theory and Applications, 12):1611177) 1989.
[23] Y. Yuan, A modified BFGS algorithm for unconstrained optimization. IMA Journal of Numerical Analysis, 11(3):325-32,, 1991.
[24] Mchiddin Al-Baali. Global and superlinear convergence restricted class of self-scaling methods with inexact line searches, for convex functions. Computational Optimization and Applications, 9(2):1912033 1998.
[25] Donghui Li and Masao Fukushima. A globally and superlinearly convergent Gauss -NwtooN based BFGS method for symmetric nonlinear equations. SIAM Journal on Numerical Analysis, ((()):1221772, 1999.
[26] Hiroshi Yabe, Hideho Ogasawara, and Masayuki Yoshino. Local and superlinear convergence of quasi-Newton methods based on modified secant conditions. Journal of Computational and Applied Mathematics, 205(1):617-632 2007.
[27] Aryan Mokhtari, Mark Eisen, and Alejandro Ribeiro. IQN: method with local superlinear convergence rate. SIAM Journal on Optimization, 28(2):1670- 1698, 2018
An incremental quasi-Newton
[28] Wenbo Gao and Donald Goldfarb. Quasi-newton methods: superlinear convergence without line searches for self-concordant functions. Optimization Methods and Software, 34(1):194 217, 2019.
[29] Richard H. Byrd and Jorge Nocedal. tool for the analysis of quasi-newton methods with application to unconstrained minimization. SIAM Journal Numerical Analysis, Vol. 26, No. 3. 1989.
[30] MJD Powell. On the convergence of the variable metric algorithm. IMA Journal of Applied Mathematics, 7(1):21-36, 1971.
[31] Michael JD Powell. Some global convergence properties of variable metric algorithm for minimization without exact line searches. Nonlinear programming, 911::33-72, 1976.
[32] Richard H Byrd, Jorge Nocedal, and Y. Yuan. Global convergence of class of quasi-Newton methods on convex problems. SIAM Journal on Numerical Analysis, 24 1987.
[33] Richard H Byrd, Humaid Fayez Khalfan, and Robert B Schnabel. Analysis of symmetric rank-one trust region method. SIAM Journal on Oplimization, 6045:102)) 1996.
[34] Shida Wang, Fadili Jalal, and Peter Ochs. Global non-asymptotic super-linear convergence rates of regularized proximal quasi-newton methods on non-smooth composite problems. arXiv preprint arXiv:2410. 1676, 2024.
[35] Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi- newton methods. Mathematical Programming, pages 1-32, 2021.
[36] Anton Rodomanov and Yurii Nesterov. New results on superlinear convergence of classical quasi-newton methods. Journal of Optimization Theory and Applications, 188(3):744-769, 2021.
[37] Haishan Ye, Dachao Lin, Xiangyu Chang, and Zhihua Zhang. Towards explicit superlinear convergence rate for srl. Mathematical Programming, 199(1):1733-130: 2023.
[38] Qiujiang Jin and Aryan Mokhtari. Non-asymptotic superlinear convergence of standard quasi- newton methods. arXiv preprint arXiv:2003. 2020.
12

---

[39] Vladimir Krutikov, Elena Tovbis, Predrag Stanimirovié, and Lev Kazakovtsev. On the con- vergence rate of quasi-newtoo methods on strongly convex functions with lipschitz gradient. Mathemalics, 11(23):4715, 2023.
[40] Anton Rodomanov. Global complexity analysis of bfgs, arXiv:2404.13051, 2024.
[41] Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotie global convergence rates of bfgs with exact line search. arXiv preprint arXiv:2404.01266 2024.
[42] Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence analysis of bfgs with the armijo-wolfe line search. Conference on Neural Information Processing Systems (NeurIPS 2024), 2024.
[43] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science Business Media, 2006.
[44] Yu-Hong Dai, Jarre Florian, and Lieder Felix. the existence of affine invariant descent directions. Optimization Methods and Software 35.5: 938 2020.
[45] N Lyness. The affine scale invariance of minimization algorithms. Mathematics of Computa- tion 34.1 265-287, 1979.
[46] Yurii Nesterov. Lectures on convex optimization. Springer Optimization and Its Applications (SOIA, volume 137), 2018.
[47] Arjevanil Yossi, Shamirl Ohad, and Shiff Ron. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, Series A (2019), 178:327-360, 2019.
[48] Frank Nielsen and Gaetan Hadjeres. Monte carlo information geometry: The dually flat case. arXiv.1803.07225, 2018.
[49] N. Doikov and Y. Nesterov. Minimizing uniformly convex functions by cubic regularization of newton method. arXiv, 1905.02671, 2019.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims in the abstract and introduction align with all the theoretical and experimental results presented in our paper. We assert establishing global convergence of BFGS under the condition of self-conccrdance, and our theoretical results guarantee this.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations and drawbacks of this paper in the paragraph of Section
Guidelines:
The answer NA means that the paper has 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 separate "I "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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: All the theorems, formulas, and proofs in the paper are numbered and cross- referenced. All assumptions clearly stated or referenced in the statements of the lemmas, propositions, or theorems. All the proofs of all results are presented in the appendix of supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have formalized the objective loss function, described the data and initial- ization as well as all the execution details. Please check details in the numerical experiments section
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibilitty In the case of closed-source models, it may be that access to the model is limited in
15

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We have uploaded our Matlab codes which generate all the empirical results in the numerical experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-souree benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https
mnaps.ccc/ublic//uiieee htw.bl////guuudeeddddddbbiiiiii Cooe//oodeeeeeeeeeeeee wwt.iissssiiiiiiiiiiiiooii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have specified how our algorithms and baselines are initialized and how the hyperparameters are selected. Please check details in 6
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This paper focuses on a deterministic optimization problem and the algorithms considered do not have any source of randomness. The objective loss function used in the numerical experiments requires random matrices and random vectors. The initial vectors are also generated randomly. We have presented the details the random generations of these matrices and vectors. However, all the optimization methods presented in our experiments are deterministic algorithms. There no need report the corresponding error bars. Please check details in 6
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We only need to install the Matlab software on our personal computer with normal CPU to codes and reproduce the experiments, we do not run any form of large-scale training.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
17

---

Answer:
[NA]
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 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 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 being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. 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, 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 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 best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets g.g code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
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 used and, possible, include URL.
18

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.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 balaaets.ppperssttt paperssii thcode. com con/datases package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of 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 available online, the authors are encouraged to reach out to the asset's s creators.
13. 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 use any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. 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 involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS 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.
15. Institutional review board (IRB) approvals 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 crowdsoureing nor research with human subjects.
19

---

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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The paper does not involve any uages of LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM for what should or should not be described.
20


Reviews:
[{"review_id": "JDQ2TFQnhJ", "reviewer": "Reviewer_wDXh", "summary": "This paper provides a new non-asymptotic convergence analysis for the BFGS quasi-Newton method under the assumption of strict convexity and strong self-concordance, which is weaker than the typical strong convexity and Lipschitz Hessian assumptions. The main results are the establishment of global linear and superlinear convergence rates that are, unlike prior analyses, invariant to affine transformations of the variables. The analysis holds for any initial point and positive-definite initial Hessian, with a step size selected by a line search satisfying the weak Wolfe conditions.", "questions": "Please see above.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*\n\nThe paper is technically deep and addresses a well-known theoretical challenge in the analysis of quasi-Newton methods. The primary strength is the rigorous mathematical construction of a convergence proof that aligns with the affine-invariant nature of the BFGS algorithm. The authors successfully overcome significant technical hurdles by developing an analysis based on time-dependent bounds derived from the self-concordance property, rather than relying on the uniform bounds available under stronger assumptions. The paper is also well-written, with the introduction and proof sketches clearly laying out the logical flow of the arguments.\n\n*Weaknesses*\n\nWhile the paper is technically sound, its primary weakness is that the overall significance of its main contribution is questionable and not sufficiently justified.\n\n1. Questionable Significance of Affine-Invariant Guarantees: The central claim is providing the \"first affine-invariant global non-asymptotic convergence guarantees\". While this is a theoretically elegant result, the paper fails to make a compelling case for its practical or theoretical impact. The BFGS algorithm's performance is already known to be affine-invariant; achieving a theoretical rate that reflects this property feels more like a \"cleanup\" of the theory rather than a groundbreaking discovery that offers new insights. The authors do not explain how this new analysis could lead to better algorithms, improved practical implementations, or a fundamentally new understanding of BFGS's behavior. Logistic regression, log-sum-exp, and log barrier functions the only examples that satisfy the strong concordance assumptions in this paper, but these are not broad enough to justify the significance of the paper's extension over the existing results. \n\nIt would help to better assess the significance of this work if the authors can clearly state the key technical difficulties for obtaining affine-invariant convergence analysis. Specifically, can the analysis in the recent breakthroughs on BFGS with standard non-affine assumptions [35-38] be modified and adapted to work with the current paper's setting? If not, what were the main technical innovation that the authors made to overcome such difficulties? \n\n2. Limited Scope of Assumptions: The analysis relies on strong self-concordance, a condition that is not universally met. While the authors correctly argue this is weaker than requiring strong convexity and a Lipschitz Hessian, it is still a restrictive structural assumption. This limits the applicability of these \"first-ever\" guarantees to a specific class of problems, somewhat diminishing the claim of broad impact.\n\n3. Inappropriate Citation: The paper relies on an informal source to support a technical claim. Specifically, Footnote 1 on page 16 cites a Math Stack Exchange post. For a formal academic publication, especially one of this theoretical depth, relying on a community forum instead of a textbook or peer-reviewed article is unprofessional and inappropriate.\n\n*Minor comments*\n\nThe usage of = and := sometimes seems off. For example, on line 85, it might be better to use $H_{t+1}=....$ rather than $:=$. And in equation (9), it might be better to use $:=$.\n\nline 164, potential extra punctuation? \"To further simplify the expression\" instead of \"To further, simplify the expression\"\n\nline 227, typo \"admissible\" instead of \"addmissible\"\n\nThe expression inside big O looks weird in Prop.5.1. The first term goes to 0 as t goes to infinity and the second term goes to negative infinity. From the last part of the proof in the appendix, it seems to me the correct big O might be $O(1+\\log(1+\\Gamma/t)+\\log(1+\\log(1+\\frac{\\Psi(B+\\Gamma)}{t})))$", "was_revised": true, "final_justification": "I thank the authors for their thorough response. Based on it and the evaluations from the other reviewer, I am raising my evaluation from 4 to 5.", "rebuttal": "**Questionable Significance of Affine-Invariant Guarantees** \n    \n**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.\n\nWe 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.\n\nAnalogously, 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.\n\nWe will add the above point in the revised paper. Thanks for your comment.\n\n**The key technical difficulties compared with prior works [35-38]**\n    \n**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.\n\nFirst, 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.\n\nSecond, 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. \n\nPlease 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. \n    \nWe will add a remark in the revised paper to explicitly highlight these contributions. Thank you for your feedback.\n\n**Limited Scope of Assumptions**\n    \n**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.\n\n**Inappropriate Citation**\n    \n**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. \n\n**Minor comments**\n    \n**Response** Thanks for pointing out all these typos. We will fix all of them in the revised version of our submission."}, {"review_id": "QvgfQznT9N", "reviewer": "Reviewer_zMJm", "summary": "This work analyzes the BFGS algorithm with Wolfe line search for minimizing strictly convex and strongly self-concordant functions. Although BFGS is known to be affine-invariant and to converge superlinearly, a global superlinear rate independent of problem conditioning had not been established. The authors close this gap by proving the first global superlinear convergence rate that depends only on the initial suboptimality and the strong self-concordance constant, for arbitrary starting points and arbitrary positive-definite BFGS initializations.", "questions": "1. Do you think it would be possible to obtain similar results with just an Armijo backtracking line search? The curvature condition makes the line search slightly more complicated to implement, and additional calls to the gradient oracle. Newton's method only requires the sufficient decrease condition in the line search (though the quadratic rate is local). \n2. Can we optimize the bound in, say, Theorem 3.3 or Theorem 4.3, over $\\alpha$ and $\\beta$ to further tighten the bounds?", "limitations": "- It's unclear for now whether strong self-concordance indeed holds for the objectives claimed by the authors. (see weaknesses)\n\n**Minor issues:**\n- After Assumption 2.2 (strong self-concordance), the notion of standard self-concordance is brought up for comparison. The definition for the latter should also be given for readers unfamiliar with the concept.\n- Right after that (lines 107-108), I think the two occurrences of $|u|^3x$ should be typeset as $\\Vert u\\Vert^3_x$, and the last $|u|^3_x$ should be $\\Vert u\\Vert^3_x$?\n- Line 109: if we want to be extra precise, Nesterov's Theorem 5.1.2 [46] is for the affine invariance of _standard_ self-concordance, not strong self-concordance. Although it's pretty obvious that affine invariance also holds for strong self-concordance. \n- Line 153's clarity can be improved by referring back to (9), i.e., \"... of $B_0$ correspond to \\[$\\hat B_0$ in (9) with\\] the weight matrices $P=...$\"\n- Line 288: expression for $T_3$ is hard to read. Perhaps put it into display math mode? The tilde and bar over $B_0$ also seem to be off. \n- Line 324: should this cubic function have a citation? \n- The Appendix could use a bit more organization, such has having its table of content, and a bit of discussion before each proof. It's recommended to use the `restatable` package to restate result statements before the proofs (and put proofs into proof environments). \n- Line 1051: $log$ -> $\\log$\n- Line 1053: after \"that greedy quasi-Newton paper\" perhaps cite [17] again. I recommend using the author-year citation style but I understand the space constraint. \n- Plots: the problem / objective function name can go into the title of the figure in large font instead of in the caption which is hard to find.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n- This work analyzes a highly relevant algorithm in convex optimization—BFGS with Wolfe line search—and establishes a non-asymptotic, affine-invariant superlinear convergence rate. I consider this a significant theoretical contribution that highlights the algorithm’s close connection to Newton’s method, both being affine-invariant with superlinear rates. Given that BFGS is effectively what’s implemented in widely used libraries like scipy, the result is also of high impact for existing practical implementations. The results are very explicit and satisfying, with all constant dependencies clearly stated.\n- The paper is very well organized and clearly written. I particularly appreciate the following aspects:\n\t- The introduction is very concise, and well-structured. It provides an overview of existing literature, clearly stating the limitations of existing works before presenting the authors' own contributions. I appreciate that the authors go beyond simply listing references when discussing references; the discussions of how they relate to each other and connect to the present work provide valuable context for the reader. The coherence also reflects authors' deep understanding of existing results.\n\t- The setup and assumptions are all very standard and clearly stated. The paper is very polished overall, with no major typographical errors. Although the results use some seemingly non-standard functions and quantities (for instance $\\omega$ and $\\Psi$), they are nonetheless commonly used in recent BFGS analyses. It's very helpful that the authors provide intuitions when each of these objects are introduced. The sketch of proof techniques following each major result are also very helpful, especially when emphasizing what's no longer possible with the self-concordance assumption as opposed to the strong-convexity and smoothness assumptions in previous works, and how the difficulties are overcome. \n\t- I also like that the authors give separate statements for when the BFGS initialization is chosen to be a multiple of the identity. These correspond to practical choices and the rates are more parsable. \n\t- It's nice that the authors also included an iterations complexity with line search taking into consideration, especially because the curvature condition is used as well which requires additional gradient (not just function value) evaluations. \n\n\n**Weaknesses:**\n\nMy only major concern is the applicability of strong self-concordance. The authors claim that \n1. The class of strong self-concordant functions is a subclass of \\[standard\\] self-concordant functions.\n2. The logistic regression objective is satisfies strong self-concordance.\nHowever, we know (for instance from [Bach (2010)](https://arxiv.org/pdf/0910.4627)) that the logistic regression objective does not satisfy the standard self-concordance definition. Rather, it satisfies a generalized self-concordance definition (that is different from the strong self-concordance used in the present paper). Therefore logistic regression cannot be strongly self-concordant?\n\nThe authors did provide an argument for logistic regression being strongly self-concordant (in Appendix F) but I find it a bit hand-wavy. If we consider logistic regression with only 1 data point, the objective is just $f(x)=\\ln(1+\\exp(z^\\top x))$ (absorbing $y$ and the negative sign into $z$), we have $\\nabla^2f(x) = \\sigma'(z^\\top x)z^2$ where $\\sigma$ is the sigmoid function. The authors claim that $f$ is strongly convex wrt the matrix $B$, which in this case is just $z^2$, and thus one can use an existing argument from [47] that $f$ is strongly self-concordant. But strong convexity does not hold globally even wrt $B$ since $\\sigma'$ still asymptotes to $0$. Am I missing something here or is logistic regression actually not strongly self-concordant? \n\n- Similarly, I expect a more rigorous proof that the log-sum-exp function is strongly convex (wrt the corresponding $B$) which lets you apply the argument of [47]. \n- 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.\n\n\nThe other weakness is on the experimental design:\n1. The breakthrough in this paper is an affine invariant superlinear rate of BFGS. However, the experimental design doesn't really reflect this. It's nice to have plots for varying dimensions and to see that BFGS performs much better than GD and accelerated gradient. But these are well-known and not very surprising. My (not very well-thought-through) suggestion is as follows: for each problem (or just take a real logistic regression dataset which I recommend), run GD / AGD in the original coordinate system as well as a linearly transformed coordinate system, where the transformation is chosen such that GD / AGD performs a lot worse. Then run the BFGS variants in both coordinate systems as well, and show that they are unaffected by this change of basis, while still converging blazing fast.\n2. In addition to suboptimality vs. number of iterations, plots with number of gradient evaluations on the x-axis should also be included (especially since backtracking line search for GD / AGD does not involve additional gradient evals). Perhaps also include a set with wall-clock time on the x-axis. \n3. It would also be nice to see a plot of $\\eta_k$ vs. $k$ to see how often is the unit step size accepted/rejected.\n4. Is it possible to estimate the constants in the bound of, say, Corollary 4.4? If yes, it may be worthwhile to plot the corresponding $(C/k)^k$ curve along with the experimental results just to see how well they match. \n\n**Note:** I did not check all the convergence proofs in detail (especially the algebraic manipulations). I only checked major proof steps and they seem to be correct.", "was_revised": true, "final_justification": "This is a very strong submission highly relevant in convex optimization. The results are solid and the paper is very well-written.", "rebuttal": "**Proof of the strongly self-concordance of logistic regression and the log-sum-exp function**\n    \n**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\nN. Doikov and Y. Nesterov. Minimizing uniformly convex functions by cubic regularization of newton method. arXiv, 1905.02671, 2019\n\nWe will supplement more rigorous proof analysis in the revised version of the submission.\n\n**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.**\n    \n**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.\n\n**Weakness 1 on the experimental design**\n\n**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.\n\n| Iteration   | 200 | 400 | 600 | 800 | 1000 |\n| -------- | ------- | ------ | ------ | ------ | ------ |\n| BFGS I | 4.98e-3 | 2.40e-4 | 6.45e-6 | 3.67e-9 | 1.02e-12  |\n| BFGS cI | 1.65e-3 | 5.15e-8 | 7.56e-12 | 8.78e-15 | 5.32e-18  |\n |   GD | 6.30e-3 | 4.53e-3 | 3.67e-3 | 2.32e-3 | 1.45e-3 | \n  |  AGD | 8.14e-4 | 5.96e-4 | 4.50e-4 | 3.43e-4 | 2.58e-4  | \n\n\n| Iteration   | 200 | 400 | 600 | 800 | 1000 |\n| -------- | ------- | ------ | ------ | ------ | ------ |\n  |  BFGS I | 4.58e-3 | 2.83e-4 | 1.22e-5 | 5.02e-8 | 6.08e-11  |\n   | BFGS cI | 2.41e-4 | 2.04e-9 | 3.95e-12 | 1.54e-15 | 6.78e-18 |\n   | GD | 5.57e-1 | 4.39e-1 | 3.32e-1 | 2.13e-1 | 1.23e-1 | \n  |  AGD | 6.86e-2 | 4.81e-2 | 3.52e-2 | 2.71e-2 | 2.07e-2  | \n\n\nWe 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.\n\n**Weakness 2 on the experimental design**\n    \n**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.\n    \n| Gradient | 866 | 1265 | 1476 | 1676 | 1876 |\n| -------- | ------- | ------ | ------ | ------ | ------ |\n| BFGS I | 1.26e-3 | 4.48e-5 | 6.78e-6 | 3.58e-8 | 6.38e-11  | \n   | BFGS cI | 1.47e-3 | 2.63e-8 | 5.37e-12 | 2.98e-15 | 1.88e-18 |\n   | GD | 5.40e-3 | 3.65e-3 | 2.88e-3 | 1.97e-3 | 1.02e-3  | \n   | AGD | 6.90e-4 | 5.17e-4 | 4.55e-4 | 3.92e-4 | 2.98e-4 | \n\n\n  |  Time(s) | 3.93 | 6.01 | 7.94 | 9.84 | 11.7 | \n | -------- | ------- | ------ | ------ | ------ | ------ |\n| BFGS I | 1.11e-3 | 6.40e-5 | 1.12e-5 | 1.05e-6 | 1.88e-9  | \n |   BFGS cI | 8.77e-6 | 8.19e-9 | 5.78e-12 | 3.95e-15 | 8.23e-18 |\n  |  GD | 6.35e-3 | 4.98e-3 | 3.89e-3 | 2.32e-3 | 1.51e-3 | \n  |  AGD | 5.66e-4 | 4.07e-4 | 3.12e-4 | 2.10e-4 | 1.37e-4 | \n\n\n\n**Weakness 3 on the experimental design**\n    \n**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.\n\n**Weakness 4 on the experimental design**\n    \n**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.\n\n**Question 1**\n    \n**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.\n\nThis 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.\n\n**Question 2**\n    \n**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.\n\n**Minor comments**\n    \n**Response.** Thanks for pointing out all these typos. We will fix all of them in the revised version of our submission."}, {"review_id": "pQoKNAIvBw", "reviewer": "Reviewer_gJJa", "summary": "This paper considers the global non-asymptotic convergence guarantee of the BFGS method for solving strictly convex and strongly self-concordant objective functions. The convergence analysis of the BFGS method in this paper does not require the common assumptions, including strong convexity and Lipschitz continuity of the gradient or Hessian. They provide guarantees of global linear convergence and superlinear convergence after certain iterations.", "questions": "* 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?\n* In line 107 and 108, is the term $M |u|^3 x$ a typo?", "limitations": "Please refer to the weakness section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths;\n\n* The paper is well-written and easy to follow. In several parts of the work, the authors clarify the difference between their analysis and the analysis in existing work [1].\n* The convergence guarantee of the BFGS does not require common assumptions such as strong convexity and Lipschitz continuity of the gradient or Hessians. \n* This work provides extensive numerical experiments to demonstrate the effectiveness of the BFGS method for strictly convex functions.\n\nWeakness:\n\n* 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.\n\n\nReferences:\n\n[1] Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence analysis of BFGS with the Armijo-Wolfe line search. Conference on Neural Information Processing Systems (NeurIPS 2024), 2024.", "was_revised": true, "final_justification": "It is a solid and well-written paper. Therefore, I will maintain my score.", "rebuttal": "**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.**\n    \n**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.\n\nRegarding 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. \n    \nOur submission makes two key contributions that clearly distinguish it from prior work:\n\n1. 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.\n\n2. 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.\n\nFinally, the technical contributions of our paper require new proof strategies, which we summarize in the following points.\n\nFirst, 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.\n\nSecond, 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. \n\nPlease 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. \n    \nWe will add a remark in the revised paper to explicitly highlight these points. Thank you for your feedback.\n\n**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?**\n    \n**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.\n\nThe 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.\n\nFor more details, please refer to the following reference:\n\nRichard H. Byrd, Jorge Nocedal, Ya-Xiang Yuan, “Global Convergence of a Class of Quasi-Newton Methods on Convex Problems,” SIAM Journal on Numerical Analysis.\n\nOnly 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.\n\nThis is an excellent point that we will add to the revised paper. Thanks for your comment. \n\n**Question: In line 107 and 108, is the term $M|u|^3x$ a typo?**\n    \n**Response:** Thanks for pointing out this typo. The correct version is $M||u||_{x}^{3}$. We will fix this typo in the revised submission."}, {"review_id": "gnSDO5VOvG", "reviewer": "Reviewer_yiN7", "summary": "The paper proves global linear and non-asymptotic local superlinear convergence rates for the BFGS method when applied to strictly convex and strongly self-concordant functions. Unlike prior work, it does not assume strong convexity or Lipschitz continuity of the gradient or Hessian. The results are affine-invariant and hold under weak Wolfe conditions, for any initialization. The analysis is complemented by numerical experiments supporting the theoretical claims.", "questions": "Do you believe it is possible to have a similar analysis for a family of quasi-Newton methods, rather than only BFGS?", "limitations": "See Weaknesses", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper addresses an old and complicated question on the rate of convergence of BFGS, by providing explicit rates for the “real” implementation of BFGS (vanilla BFGS with Armijo-Wolfe line search) for self-concordant functions. While the paper has some weaknesses, it is a strong contribution to optimization. \n\n**Strengths**\n\n- Despite the technicality of the paper, I appreciate the author’s effort to make it accessible\n- The rate of convergence of BFGS was unknown for a long time, and this paper addresses an important gap in the theoretical understanding of this algorithm.\n- The rate is derived for a practical implementation of BFGS (i.e., classical BFGS algorithm with a weak Wolfe condition for the stepsize). Moreover, the analysis matches the affine-invariant nature of BFGS, which is often overlooked in previous work.\n- The rates are non-asymptotic, and all constants have been carefully computed.\n\n**Weaknesses**\n\n- The approach and derivation of the rates are specific to BFGS, and not for a broader class/family of quasi-Newton methods.\n- 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.\n- 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", "was_revised": true, "final_justification": "I thanks the authors for their rebuttal. \n\nThe authors convinced me that extending their analysis to other QN schemes migh be difficult, in particular, the technical difficulty of DFP is the a priori unbounded exponential growth of the largest eigenvalue of the Hessian estimate.\n\nA quick question about one of your claim:\n> Additionally, only under exact line search does the convex Broyden class—including both BFGS and DFP—produce identical iterates.\n\nWhere can i find such a reference discussing this? This seems true on quadratics but not for the general convex case.\n\n\nMoreover, the authors will include additional numerical experiments, which I believe where lacking in the original paper. The goal of the numerical experiment was not to show the competitiveness of BFGS, which is already well know, but to illustrate that self-concordance can be found in other practical applications.\n\nFinally, After reading the other reviews and rebuttal, it seems the authors successfully address most of the concerns.\n\nHence, I will raise my score to strong accept.", "rebuttal": "**Weaknesses: The approach and derivation of the rates are specific to BFGS, and not for a broader class/family of quasi-Newton methods.**\n    \n**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.\n\nThe 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.\n\nFor more details, please refer to the following reference:\n    \nRichard H. Byrd, Jorge Nocedal, Ya-Xiang Yuan, “Global Convergence of a Class of Quasi-Newton Methods on Convex Problems,” SIAM Journal on Numerical Analysis.\n\nAdditionally, 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.\n\nExtending 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.\n\nThis is an excellent point that we will add to the revised paper. Thanks for your comment. \n\n**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.**\n    \n**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.\n\nMoreover, 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. \n\n**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**\n    \n**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.\n\nWe 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.\n\n**Question: Do you believe it is possible to have a similar analysis for a family of quasi-Newton methods, rather than only BFGS?**\n    \n**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.\n\nAs 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.\n\nWe 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."}]

Author rebuttal:

Meta-review: This paper establishes global non-asymptotic convergence guarantees for the BFGS method under strict convexity and strong self-concordance, without requiring strong convexity or Lipschitz continuity assumptions. The authors prove affine-invariant global linear and superlinear convergence from arbitrary initialisations under weak Wolfe line search, extending the theoretical understanding of BFGS beyond traditional settings.

All reviewers agree that the paper is well written and represents a significant advancement in the field of quasi-Newton methods, making substantial contributions. The ideas are novel, and the results are theoretically sound and well justified. The reviewers suggest some improvements such as enhancing clarity and improving the numerical experiments, which the authors are strongly encouraged to address in the final version of the paper.
Decision: Accept (spotlight)