A Stochastic Line Search Method with Expected Complexity Analysis
Courtney Paquette, Katya Scheinberg
Abstract
For deterministic optimization, line search methods augment algorithms by providing stability and improved efficiency. Here we adapt a classical backtracking Armijo line search to the stochastic optimization setting. While traditional line search relies on exact computations of the gradient and values of the objective function, our method assumes that these values are available up to some dynamically adjusted accuracy which holds with some sufficiently large, but fixed, probability. We bound the expected number of iterations to reach a desired first-order accuracy in the nonconvex, convex, and strongly convex cases and show that this bound matches the complexity bound of deterministic gradient descent up to constants.