A Stochastic Line Search Method with Convergence Rate Analysis

By Courtney Paquette, Katya Scheinberg. 2018

53 citations recorded by the source corpus.

For deterministic optimization, line-search methods augment algorithms by providing stability and improved efficiency. 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 show the expected number of iterations to reach a near stationary point matches the worst-case efficiency of typical first-order methods, while for convex and strongly convex objective, it achieves rates of deterministic gradient descent in function values.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Other authors [12, 17, 22, 42, 62] use a line-search termination criteria that requires function/gradient evaluations averaged over multiple samples.”
A Subsampling Line-Search Method with Second-Order Results (2018, methodology): “Finally, contemporary to the first version of this paper, a stochastic line-search framework was described by Paquette and Scheinberg [38].”