# Adaptive Backtracking Line Search

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 46 references that are in the map.
- First posted on arXiv 23 Aug 2024.

## Builds on (most cited first, 15 of 15)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Interactive Supercomputing on 40,000 Cores for Machine Learning and Data Analysis](https://mlsanity.com/paper/1807.07814/) (2018)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [Backtracking strategies for accelerated descent methods with smooth composite objectives](https://mlsanity.com/paper/1709.09004/) (2017)
- [Backtracking gradient descent method for general C1 functions, with applications to Deep Learning](https://mlsanity.com/paper/1808.05160/) (2018)
- [Scaled, inexact and adaptive generalized FISTA for strongly convex optimization](https://mlsanity.com/paper/2101.03915/) (2021)
- [Parameter-Free FISTA by Adaptive Restart and Backtracking](https://mlsanity.com/paper/2307.14323/) (2023)
- [Approximately Exact Line Search](https://mlsanity.com/paper/2011.04721/) (2020)
- [Efficient solvers for Armijo's backtracking problem](https://mlsanity.com/paper/2110.14072/) (2021)

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

- [Deep Unfolding: Recent Developments, Theory, and Design Guidelines](https://mlsanity.com/paper/2512.03768/) (2025)
- [Text-Centric Post-Training for Omni-Modal Reasoning](https://mlsanity.com/paper/2610.02819/) (2026)

## Abstract (arXiv)

Backtracking line search is foundational in numerical optimization. The basic idea is to adjust the step-size of an algorithm by a constant factor until some chosen criterion (e.g. Armijo, Descent Lemma) is satisfied. We propose a novel way to adjust step-sizes, replacing the constant factor used in regular backtracking with one that takes into account the degree to which the chosen criterion is violated, with no additional computational burden. This light-weight adjustment leads to significantly faster optimization, which we confirm by performing a variety of experiments on over fifteen real world datasets. For convex problems, we prove adaptive backtracking requires no more adjustments to produce a feasible step-size than regular backtracking does. For nonconvex smooth problems, we prove adaptive backtracking enjoys the same guarantees of regular backtracking. Furthermore, we prove adaptive backtracking preserves the convergence rates of gradient descent and its accelerated variant.