Descent Methods & Line Search
Any direction that points downhill will do — the work is deciding how far to step.
The idea
A descent method minimizes a differentiable convex function $f$ by producing a sequence $x^{(0)}, x^{(1)}, \dots$ that converges to a minimizer of $f$, updating by $x^{(k+1)} = x^{(k)} + t^{(k)}\,\Delta x^{(k)}, \qquad t^{(k)} > 0,$ and insisting that $f$ strictly decrease at every step. The vector $\Delta x^{(k)}$ is the search direction and the scalar $t^{(k)}$ is the step size, and a descent method chooses both afresh at every iteration — where Gradient Descent folded both into one learning rate $\eta$, fixed by hand before the run began.
The direction has a simple test: for convex $f$, any $\Delta x$ with $\nabla f(x)^{T}\Delta x < 0$ decreases $f$ initially, so the negative gradient is one legal choice out of a whole halfspace of them.
The step size has no such test, so we search for it rather than solve for it. Exact line search minimizes $f$ outright along the ray. Backtracking starts at $t = 1$ and shrinks $t$ by a fixed factor until the decrease obtained is at least a prescribed fraction of the decrease the tangent line predicted.
Algorithm.
Algorithm: General Descent Method Input: differentiable convex f, starting point x Output: an approximate minimizer of f 1. if the stopping criterion holds, return x 2. choose a descent direction Δx // any Δx with ∇f(x)·Δx < 0 3. line search: choose a step size t > 0 along the ray // exact or backtracking 4. x = x + t Δx // f strictly decreases at every step 5. go to step 1
Neither search can repair a bad direction. Where $f$ is far steeper across a valley than along it, the negative gradient points mostly across the valley, and the iterates zigzag however carefully the step size is chosen.
Ways to work on it
- Walkthrough. Descent directions, why a fixed learning rate breaks, backtracking, and the zig-zag no step size can fix.
- Practice. Spot a descent direction, run a backtracking line search, and take an _1 steepest descent step.
- Hardest. One bowl minimized twice — gradient descent against steepest descent in a different norm.
Not sure where to start? Take the ten-question placement test.