Line search selects how far to move along a chosen optimization direction. Given a direction such as the negative gradient, it finds a positive step length α that produces a large decrease in the loss without overshooting. section 5.1.1
A line search fits into gradient descent as a short, repeatable procedure:
- Choose the negative gradient as the descent direction and normalize it to unit length. section 5.1.1
- Evaluate candidate distances along that direction and select the step length α. section 5.1.1
- Update the current solution using wnew = wold + α·d, then test whether the change is below a convergence tolerance. section 5.1.1
- Use an exact or approximate search, or replace it with a predetermined step strategy when efficiency matters. section 5.1.1
In gradient boosting, line search computes each hypothesis weight, or step length, after a weak regressor approximates the negative loss gradient. Thus, it controls the size of each additive ensemble update. section 5.2.1
Branin gradient descent
A gradient-descent implementation can call scipy.optimize.line_search after computing and normalizing the Branin function’s negative gradient. Starting at [-4, -5], the procedure follows a descent path toward one local minimum; different initializations can reach different minima. section 5.1.1
: wold = some initial guess, converged=False
while not converged:
1. compute the direction (d) as negative gradient at wold and normalize
to unit length
2. compute the step length using line search (distance, α)
3. update the solution: wnew = wold + distance *direction = wold + α ⋅ d
4. if change between wnew and wold is below some specified tolerance:
converged=True, so break
5.else set wnew = wold, get ready for the next iteration
Follow the procedural listing to see where direction selection, line search, updating, and convergence checking occur in each iteration. section 5.1.1
