Spotlight Poster
Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search
Qiujiang Jin · Ruichen Jiang · Aryan Mokhtari
West Ballroom A-D #5803
Abstract:
In this paper, we present the first explicit and non-asymptotic global convergence rates of the BFGS method when implemented with an inexact line search scheme satisfying the Armijo-Wolfe conditions. We show that BFGS achieves a global linear convergence rate of for -strongly convex functions with -Lipschitz gradients, where represents the condition number. Additionally, if the objective function's Hessian is Lipschitz, BFGS with the Armijo-Wolfe line search achieves a linear convergence rate that depends solely on the line search parameters, independent of the condition number. We also establish a global superlinear convergence rate of . These global bounds are all valid for any starting point and any symmetric positive definite initial Hessian approximation matrix , though the choice of impacts the number of iterations needed to achieve these rates. By synthesizing these results, we outline the first global complexity characterization of BFGS with the Armijo-Wolfe line search. Additionally, we clearly define a mechanism for selecting the step size to satisfy the Armijo-Wolfe conditions and characterize its overall complexity.
Chat is not available.