# A Stochastic Line Search Method with Convergence Rate Analysis

arXiv: https://arxiv.org/abs/1807.07994 · HTML: https://mlsanity.com/paper/1807.07994/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2018.

## Built on by (most cited first, 5 of 5)

- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [Direct-Search for a Class of Stochastic Min-Max Problems](https://mlsanity.com/paper/2102.11386/) (2021)
- [Towards Simple and Provable Parameter-Free Adaptive Gradient Methods](https://mlsanity.com/paper/2412.19444/) (2024)
- [Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems](https://mlsanity.com/paper/2305.09978/) (2023)
- [Boosting Variational Inference With Locally Adaptive Step-Sizes](https://mlsanity.com/paper/2105.09240/) (2021)

## Abstract (arXiv)

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.