# Efficient solvers for Armijo's backtracking problem

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2021.

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

- [Adaptive Backtracking Line Search](https://mlsanity.com/paper/2408.13150/) (2024)

## Abstract (arXiv)

Backtracking is an inexact line search procedure that selects the first value in a sequence x0, x0β, x0β2... that satisfies g(x)≤ 0 on ℝ_+ with g(x)≤ 0 iff x≤ x^*. This procedure is widely used in descent direction optimization algorithms with Armijo-type conditions. It both returns an estimate in (β x^*,x^*] and enjoys an upper-bound lceil logβ ε/x0 rceil on the number of function evaluations to terminate, with ε a lower bound on x^*. The basic bracketing mechanism employed in several root-searching methods is adapted here for the purpose of performing inexact line searches, leading to a new class of inexact line search procedures. The traditional bisection algorithm for root-searching is transposed into a very simple method that completes the same inexact line search in at most lceil log2 logβ ε/x0 rceil function evaluations. A recent bracketing algorithm for root-searching which presents both minmax function evaluation cost (as the bisection algorithm) and superlinear convergence is also transposed, asymptotically requiring ~ log log log ε/x0  function evaluations for sufficiently smooth functions. Other bracketing algorithms for root-searching can be adapted in the same way. Numerical experiments suggest time savings of 50% to 80% in each call to the inexact search procedure.