Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions. (2nd January 2019)

• Record Type: Journal Article
• Authors: Gao, Wenbo; Goldfarb, Donald
• Is Part Of: Optimization methods and software. Volume 34:Number 1(2019)
• Page Start: 194
• Page End: 217
• Publication Date: 2019-01-02
• Subjects: Quasi-Newton methods -- BFGS -- self-concordant functions -- damped Newton method; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1510927
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: We consider the use of a curvature-adaptive step size in gradient-based iterative methods, including quasi-Newton methods, for minimizing self-concordant functions, extending an approach first proposed for Newton's method by Nesterov. This step size has a simple expression that can be computed analytically; hence, line searches are not needed. We show that using this step size in the BFGS method (and quasi-Newton methods in the Broyden convex class other than the DFP method) results in superlinear convergence for strongly convex self-concordant functions. We present numerical experiments comparing gradient descent and BFGS methods using the curvature-adaptive step size to traditional methods on deterministic logistic regression problems, and to versions of stochastic gradient descent on stochastic optimization problems.