  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.
