Line-search strategies play a central role in nonlinear programming, providing stability, improved efficiency, and adaptivity to unknown parameters. While the practical benefits for deterministic algorithms are well-documented, line-search strategies for stochastic algorithms are in their infancy.

I will present the first practical line-search method for stochastic optimization, which has rigorous convergence guarantees and requires only knowable quantities for implementation. While traditional line-search methods rely on exact computations of the gradient and function values, 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 that the expected number of iterations to reach an approximate-stationary point matches the worst-case efficiency of typical first-order methods, while for convex and strongly convex objectives, it achieves rates of deterministic gradient descent in function values.

Moreover, this approach is applicable to broader settings in unconstrained stochastic optimization, such as for trust region and cubic regularized methods. The framework is based on bounding the expected stopping time of a stochastic process, using probabilistic quantities associated to random walks and supermartingales.