Gradient descent and line search

Insert $y=x-\eta\nabla f(x)$ into the smoothness upper bound. The predicted change is at most minus the step size times one minus half the scaled curvature, multiplied by the squared gradient norm. Thus any step strictly between zero and $2/L$ decreases the objective when the gradient is nonzero. The conventional choice $1/L$ gives a clean guaranteed reduction and avoids operating close to the unstable boundary.

This is a statement about exact arithmetic, exact gradients, and a valid smoothness bound on the relevant segment. A coding error in a derivative cannot be repaired by citing the theorem. Directional finite-difference checks can expose such errors, although their own rounding and truncation limits matter. Logging both gradient norms and accepted objective changes makes it easier to distinguish an oversized step from an inaccurate derivative or a flat objective scale.

Armijo backtracking begins with a trial step, tests actual improvement against a fraction of the linear prediction, and repeatedly shrinks the step if the test fails. For gradient descent the required decrease is proportional to the squared gradient norm. Choose a sufficient-decrease constant strictly between zero and one and a shrink factor in the same range. With a descent direction and appropriate local smoothness, sufficiently small positive trials are accepted.

Do not interpret acceptance as a global certificate. It only says the current trial makes the promised local progress. Convexity, lower boundedness, regularity, and the step-selection rules enter broader convergence results. Backtracking also consumes extra function evaluations, which may dominate runtime if each evaluation requires an expensive simulation. In stochastic learning, evaluating two fresh random minibatches can invalidate a deterministic acceptance comparison; controlled data reuse or stochastic line-search theory is needed.

A small step can mean convergence, but it can also mean an extremely small chosen learning rate. A small change in objective can hide substantial error in a flat direction. For a differentiable unconstrained problem, a gradient-norm tolerance directly measures first-order stationarity. With known positive strong-convexity constant, the squared gradient also gives an upper bound on the objective gap. Constraints require a projected-gradient or other appropriate residual instead of the raw gradient.

The lab exposes the exact recurrence for the unit quadratic. Compare step 0.5 with 1.5: both contract in magnitude, but the latter alternates sides. At step size $\eta=2$, a nonzero initial position oscillates without decreasing value; above two it diverges. These experiments isolate a step-size mechanism. They neither perform line search nor justify applying the same numeric thresholds to an objective with a different curvature constant.