  There has been much recent interest in finding unconstrained local minima of
smooth functions, due in part of the prevalence of such problems in machine
learning and robust statistics. A particular focus is algorithms with good
complexity guarantees. Second-order Newton-type methods that make use of
regularization and trust regions have been analyzed from such a perspective.
More recent proposals, based chiefly on first-order methodology, have also been
shown to enjoy optimal iteration complexity rates, while providing additional
guarantees on computational cost.
  In this paper, we present an algorithm with favorable complexity properties
that differs in two significant ways from other recently proposed methods.
First, it is based on line searches only: Each step involves computation of a
search direction, followed by a backtracking line search along that direction.
Second, its analysis is rather straightforward, relying for the most part on
the standard technique for demonstrating sufficient decrease in the objective
from backtracking. In the latter part of the paper, we consider inexact
computation of the search directions, using iterative methods in linear
algebra: the conjugate gradient and Lanczos methods. We derive modified
convergence and complexity results for these more practical methods.

Optimization and Control