Line Search

This is the step you take before you can do Gradient Descent — the algorithm that trains every neural network, from a phone's voice assistant to ChatGPT. When you hear that a model has 'learned', some optimisation routine chose a direction to improve the loss and then asked how far to go. Line search answers that 'how far' question. With it, you can read any optimisation paper, debug why training diverges (step too big) or crawls (step too small), and understand why modern trainers use learning-rate schedules and adaptive optimisers like Adam. It directly unlocks your study of Gradient Descent, Learning Rate Schedules, and Adaptive Optimisers.

Imagine you are on a foggy mountain and you want to reach the valley floor. You can feel the slope under your feet — that tells you which direction is downhill. But the direction alone does not tell you how far to step. Take a tiny step and you will be walking all day; take a huge step and you might overshoot and end up on the other side, even higher. Line search is the rule you use to choose that step length. You have already picked a direction (downhill, which in mathematics is the negative of the gradient), so now you ask: 'How far along this direction should I go?' One extreme is to compute the exact distance that gets you to the lowest point in that direction — that is exact line search. The other — and by far the more practical — is to try a step, see if the loss actually decreases enough, and shrink the step until it does. That 'try, check, shrink' approach is called backtracking line search, and with a simple condition (the Armijo condition) it is the cheap, standard choice. It is the difference between guessing and knowing you are making progress.

Think of tuning a radio dial to find the clearest station. You know roughly which way to turn the dial (that's your direction), but you don't know how much to turn it. You turn a small amount, listen for a moment: is the signal clearer? If it is, you might turn a little more in the same direction. If it is worse, you turn back a bit. You don't try every possible position on the dial — that would take forever. You take one step, check the signal, and if it's 'good enough', you stop. That's backtracking line search: you try a step size, evaluate the objective (like the static quality), and accept it if it meets a sufficient-decrease condition. The radio dial is one-dimensional, so you could scan it completely; but in machine learning the 'dial' has millions of dimensions, and you can only feel the slope at the single point where you stand. You cannot see the whole path, so you must test a few distances and accept the first that gives a sufficient improvement. The analogy breaks down because with a radio you can hear the whole band, but with a neural network you are blind — you only have the loss at the current weights and the slope, nothing else. That is exactly why line search has to be heuristic and cheap.

Line search is the process of choosing how far to move along a given descent direction, either by finding the exact optimal distance or, more commonly, by testing steps and accepting the first one that sufficiently decreases the objective function.

This sits directly on top of Gradient Descent — which you will study next. Gradient descent tells you the direction to move: the negative of the gradient (the steepest downhill). But it says nothing about how far. Line search supplies that missing piece. In your library notes, line search is the bridge between choosing a direction and actually updating the parameters. It also connects to Hyperparameter Tuning, because the step size you end up using is the single most consequential hyperparameter in training. Adaptive optimisers like Adam were created to sidestep the need for line search, but they are built on the same underlying idea: adjust the step size so that you are always making progress without diverging. When you later study Convex Optimization, you will see that exact line search has nicer guarantees, but in nonconvex deep learning, backtracking is the workhorse.