10. Gradient Descent and Line Search — Separating Direction from Step Length

// CORE 4/7 — gradient descent, exact line search, backtracking, Armijo, Wolfe, momentum, Nesterov

Gradient descent is the most fundamental first-order optimization algorithm. The key is to consider direction and step length separately.

Gradient descent

The update is

$$x_{k+1}=x_k-\alpha_k\nabla f(x_k).$$

$-\nabla f(x_k)$ is the descending direction, and $\alpha_k$ is the step size. Even with the right direction, a step that is too large bounces away, while one that is too small is excessively slow.

Exact line search

After choosing the current direction $p_k$, exact line search finds the step size that minimizes the objective along that line:

$$\alpha_k=\arg\min_{\alpha>0} f(x_k+\alpha p_k).$$

It is conceptually clean, but can be expensive because a one-dimensional optimization problem must be solved exactly at every iteration.

Backtracking

Backtracking begins with a large step and shrinks it until a condition is satisfied.

1. Choose an initial $\alpha$.
2. If the decrease is insufficient, shrink it with $\alpha\leftarrow\rho\alpha$.
3. Move once the decrease is sufficient.

Here $0<\rho<1$. It is cheaper and more robust than exact line search.

Armijo condition

The Armijo condition checks whether "the value decreased at least as much as expected":

$$f(x_k+\alpha p_k)\le f(x_k)+c_1\alpha\nabla f(x_k)^\top p_k.$$

The right side is a decrease based on the linear prediction with some margin. If $p_k$ is a descent direction, then $\nabla f(x_k)^\top p_k<0$, so the right side is less than $f(x_k)$.

Wolfe condition

The Wolfe condition adds a curvature condition to Armijo's sufficient-decrease condition:

$$\nabla f(x_k+\alpha p_k)^\top p_k\ge c_2\nabla f(x_k)^\top p_k.$$

It prevents a step from being too small. Quasi-Newton methods such as BFGS frequently use Wolfe line search.

Momentum

Momentum accumulates previous movement directions:

$$v_{k+1}=\beta v_k+\nabla f(x_k),\qquad x_{k+1}=x_k-\alpha v_{k+1}.$$

Gradients oscillate from side to side in a long valley; momentum accumulates the consistent direction and enables faster forward progress.

Nesterov

Nesterov momentum first looks one step ahead using momentum and calculates the gradient at that position:

$$v_{k+1}=\beta v_k+\nabla f(x_k-\alpha\beta v_k),$$ $$x_{k+1}=x_k-\alpha v_{k+1}.$$

The intuition is "look ahead to where inertia will take you and adjust." This acceleration idea is frequently used in deep-learning optimization.

Selection criteria

Method	Advantage	Caution
Fixed step	Easy to implement	Requires step tuning
Exact line search	Theoretically clean	High cost per iteration
Backtracking	Robust and easy to implement	Requires several function evaluations
Armijo/Wolfe	Fits convergence theory well	Requires parameter selection
Momentum/Nesterov	Fast in valleys	May oscillate

Next: Newton and Quasi-Newton Methods