Quasi-Newton Methods: Superlinear Convergence Without Line Search for Self-Concordant Functions

Wenbo Gao, Donald Goldfarb

Published 2016-12-21Version 1

We derive a \emph{curvature-adaptive} step size for gradient-based iterative methods, including quasi-Newton methods, for minimizing self-concordant functions. 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 generally) 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 logistic regression problems.