Answers are grounded in this paper and cite their sources.
In this paper, we establish the first explicit and non-asymptotic global convergence analysis of the BFGS method when deployed with an inexact line search scheme that satisfies the Armijo-Wolfe conditions. We show that BFGS achieves a global convergence rate of (1-1/κ)ᵏ for μ-strongly convex functions with L-Lipschitz gradients, where κ=L/μ denotes the condition number. Furthermore, if the objective function's Hessian is Lipschitz, BFGS with the Armijo-Wolfe line search achieves a linear convergence rate only determined by the line search parameters and independent of the condition number. These results hold for any initial point x₀ and any symmetric positive definite initial Hessian approximation matrix B₀, although the choice of B₀ affects the iteration count required to attain these rates. Specifically, we show that for B₀ = LI, the rate of O((1-1/κ)ᵏ) appears from the first iteration, while for B₀ = μ I, it takes dlog κ iterations. Conversely, the condition number-independent linear convergence rate for B₀ = LI occurs after O(κ(d +M √f(x₀)-f(x_*)μ3/2)) iterations, whereas for B₀ = μ I, it holds after O(M √f(x₀)-f(x_*)μ3/2(dlog κ + κ)) iterations. Here, d denotes the dimension of the problem, M is the Lipschitz parameter of the Hessian, and x_* denotes the optimal solution. We further leverage these global linear convergence results to characterize the overall iteration complexity of BFGS when deployed with the Armijo-Wolfe line search.
No takes yet. Share an insight, caveat, or question.
Jin et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: