Is backtracking an exact line search?

No. It accepts a trial meeting a decrease condition rather than necessarily finding the minimum along the line.

Must the step always be halved?

No. Any chosen reduction factor strictly between zero and one can define the geometric trial sequence.

Does it automatically handle constraints?

No. Feasibility and domain requirements must be incorporated into the surrounding method and trial checks.

AI Glossary / Mathematics and optimization / Intermediate

Backtracking line search

Definition

Backtracking line search is a procedure for choosing how far an optimization algorithm should move along a proposed direction. It starts with a trial step and repeatedly reduces it until the objective decreases sufficiently. It is commonly used inside gradient-based methods to avoid taking an overly large step, while accepting a useful improvement without solving an exact one-dimensional minimization problem.

What it means

An optimization iteration has two separate choices: where to head and how far to go. Backtracking addresses the second. It does not supply a good direction by itself, and shrinking an unsuitable direction indefinitely is not a reliable repair.

For minimization of a differentiable function, a descent direction p satisfies gradient(f,x) dot p < 0. This says that sufficiently small positive movements initially reduce the function. The line search tests actual objective values to decide whether the chosen movement is acceptable.

How it works

Choose an initial step t, a reduction factor beta between zero and one, and a sufficient-decrease constant c between zero and one. A common implementation starts with t = 1.

The Armijo condition accepts the step when f(x + t p) is no greater than f(x) + c t gradient(f,x) dot p. The right side demands a fraction of the decrease predicted by the local linear approximation. If the condition fails, replace t by beta times t and test again.

Accept the first successful trial and let the outer optimization method update x. Trial points must lie in the function's domain. Standard small-step acceptance reasoning assumes a differentiable objective and a genuine descent direction; convergence of the entire algorithm needs further conditions.

Three practical examples

1. A deterministic model-fitting routine evaluates whether a proposed gradient step reduces its training objective enough before changing parameters.

2. A Newton-based solver uses a damped step when a full Newton movement produces an unsuitable objective value far from a solution. The proposed direction must still satisfy the solver's requirements.

3. A numerical optimization lesson compares a fixed step with backtracking on a curved function, showing how rejected trials differ from accepted outer iterations.

Think of it this way

Think of testing the length of a step down a sloping path. If a long stride lands too high, you try a shorter stride along the same heading. The analogy is limited: backtracking evaluates mathematical trial points and a precise decrease rule, and it does not literally reverse a physical action already performed.

Worked example

Minimize f(x) = x squared. At x = 2, the objective is 4 and the derivative is 4. Choose the negative-gradient direction p = −4. The directional derivative is 4 × (−4) = −16, so this is a descent direction.

Use initial step t = 1, reduction factor beta = 0.5, and c = 0.1. The Armijo right side is 4 − 1.6t.

For t = 1, the candidate is x + t p = −2. Its objective is 4, while the allowable bound is 2.4. Since 4 is greater than 2.4, reject this trial. Merely ending with the same objective is not sufficient decrease.

Reduce t to 0.5. The candidate is now zero, with objective zero. The bound is 3.2, so the condition holds and this step is accepted. There were two trial evaluations but only one accepted parameter update.

The example happens to land exactly at the minimum. That is not a general property of backtracking. With beta = 0.25 instead, the second trial would use t = 0.25, land at x = 1, and yield objective 1. It also passes, because 1 is below the bound 3.6, even though it does not minimize the function along the direction. The rule seeks adequate decrease, not necessarily the best possible step.

Illustrative case study

Fictional case: Oak Analytics implements a calibration routine and reports that optimization has stalled. A review finds that every rejected trial was being counted as an accepted iteration, making its progress chart misleading.

The team records trial step sizes, objective values, acceptance decisions, and gradient norms separately. It also checks a small problem with an analytically known derivative before trusting the larger model. A cap on trial evaluations produces a clear failure status rather than silently accepting the last unsuccessful step. The case illustrates diagnostic design and does not claim a measured speedup.

Common misconceptions and mistakes

Do not confuse reducing the step with changing the direction. Backtracking keeps p fixed during that line search.

Do not assume that any decrease satisfies the Armijo rule. The required decrease depends on the directional derivative and the candidate step size.

Conversely, passing the rule does not prove that the point is globally optimal. For nonconvex objectives, further iterations can still lead to different stationary points. Noisy objective estimates also complicate deterministic acceptance tests: comparing unrelated minibatches can make a step appear better or worse for reasons unrelated to its size.

Business use

Backtracking is useful when objective evaluations are affordable relative to the cost of unstable updates. Its extra trials should be included in performance accounting; counting only accepted iterations can conceal substantial work.

For a production fitting service, keep clear termination reasons such as a small gradient, an evaluation limit, or a failed line search. Test derivative calculations and variable scaling before tuning reduction factors. A very small accepted step may reflect local curvature, poor scaling, or an unsuitable direction, and those explanations call for different responses.

Check your understanding

In the worked example with beta = 0.25, why is x = 1 accepted even though x = 0 has a smaller objective?

Answer: The trial at x = 1 satisfies the sufficient-decrease test. Backtracking stops at that acceptable trial; it is not required to find the exact line minimum.

Related terms

Line search
Gradient descent
Step size
Objective function
Armijo condition
descent direction
Newton's method
Wolfe conditions

Learn next

Study descent directions next. Change the worked direction to p = +4 and explain why the usual descent argument no longer applies. Then compare a sufficient-decrease test with a stopping test for the overall optimizer.

Sources

Primary reference opened and read: Stephen Boyd, Convex Optimization I, Lecture 15, https://see.stanford.edu/materials/lsocoee364a/transcripts/ConvexOptimizationI-Lecture15.html. It explains descent directions, trial reduction and sufficient decrease. The quadratic calculations and fictional case are original hand-checked illustrations.

Previous: Backpropagation through structure Next: Backtracking search