# Probabilistic Line Searches for Stochastic Optimization

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2015.

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

- [Large Scale Private Learning via Low-rank Reparametrization](https://mlsanity.com/paper/2106.09352/) (2021)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [Local Bayesian optimization via maximizing probability of descent](https://mlsanity.com/paper/2210.11662/) (2022)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [AutoLRS: Automatic Learning-Rate Schedule by Bayesian Optimization on the Fly](https://mlsanity.com/paper/2105.10762/) (2021)
- [Cockpit: A Practical Debugging Tool for the Training of Deep Neural Networks](https://mlsanity.com/paper/2102.06604/) (2021)
- [Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits](https://mlsanity.com/paper/2111.07952/) (2021)
- [KOALA: A Kalman Optimization Algorithm with Loss Adaptivity](https://mlsanity.com/paper/2107.03331/) (2021)
- [BayeSQP: Bayesian Optimization through Sequential Quadratic Programming](https://mlsanity.com/paper/2602.03232/) (2026)
- [Empirically explaining SGD from a line search perspective](https://mlsanity.com/paper/2103.17132/) (2021)
- [Faster Convergence for Transformer Fine-tuning with Line Search Methods](https://mlsanity.com/paper/2403.18506/) (2024)
- [Improving Line Search Methods for Large Scale Neural Network Training](https://mlsanity.com/paper/2403.18519/) (2024)
- [No learning rates needed: Introducing SALSA -- Stable Armijo Line Search Adaptation](https://mlsanity.com/paper/2407.20650/) (2024)
- [Bayesian autoregression to optimize temporal Mat'ern kernel Gaussian process hyperparameters](https://mlsanity.com/paper/2508.09792/) (2025)
- [A Probabilistically Motivated Learning Rate Adaptation for Stochastic Optimization](https://mlsanity.com/paper/2102.10880/) (2021)
- [Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions](https://mlsanity.com/paper/2104.12949/) (2021)
- [GOALS: Gradient-Only Approximations for Line Searches Towards Robust and Consistent Training of Deep Neural Networks](https://mlsanity.com/paper/2105.10915/) (2021)
- [To Raise or Not To Raise: The Autonomous Learning Rate Question](https://mlsanity.com/paper/2106.08767/) (2021)
- [Black Box Probabilistic Numerics](https://mlsanity.com/paper/2106.13718/) (2021)
- [Using a one dimensional parabolic model of the full-batch loss to estimate learning rates during training](https://mlsanity.com/paper/2108.13880/) (2021)
- [Bolstering Stochastic Gradient Descent with Model Building](https://mlsanity.com/paper/2111.07058/) (2021)
- [Layer-wise Adaptive Step-Sizes for Stochastic First-Order Methods for Deep Learning](https://mlsanity.com/paper/2305.13664/) (2023)
- [Learning-Rate-Free Learning: Dissecting D-Adaptation and Probabilistic Line Search](https://mlsanity.com/paper/2308.03102/) (2023)
- [Painless Federated Learning: An Interplay of Line-Search and Extrapolation](https://mlsanity.com/paper/2408.17145/) (2024)
- [Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimization](https://mlsanity.com/paper/2411.15795/) (2024)
- [Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search](https://mlsanity.com/paper/2505.00162/) (2025)
- [Information Preserving Line Search via Bayesian Optimization](https://mlsanity.com/paper/2507.15485/) (2025)
- [The cost of useful natural gradient updates](https://mlsanity.com/paper/2609.33499/) (2026)
- [Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02190/) (2026)

## Abstract (arXiv)

In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a probabilistic line search by combining the structure of existing deterministic methods with notions from Bayesian optimization. Our method retains a Gaussian process surrogate of the univariate optimization objective, and uses a probabilistic belief over the Wolfe conditions to monitor the descent. The algorithm has very low computational cost, and no user-controlled parameters. Experiments show that it effectively removes the need to define a learning rate for stochastic gradient descent.