Gradient descent with exact line search

From Calculus
Jump to: navigation, search

Definition

Gradient descent with exact line search is a variant of gradient descent where we perform an exact line search along the line of the gradient vector to move to the point of global minimum along that line. It can be contrasted with other methods of gradient descent, such as gradient descent with constant learning rate (where we always move by a fixed multiple of the gradient vector, and the constant is called the learning rate) and gradient descent using Newton's method (where we use Newton's method to determine the step size along the gradient direction).

As a general rule, we expect gradient descent with exact line search to have faster convergence when measured in terms of the number of iterations (if we view one step determined by line search as one iteration). However, determining the step size for each line search may itself be a computationally intensive task, and when we factor that in, gradient descent with exact line search may be less efficient. A lot depends on the details of the functional form. Functional forms for which the line search can be performed quickly (for instance, there exists a simple closed-form expression for the optimum when the function is restricted to a line) are amenable to this method.

Particular cases

The special case of a quadratic function of multiple variables

For further information, refer: Gradient descent with exact line search for a quadratic function of multiple variables

For a quadratic function of multiple variables, the exact line search for the function when restricted to a line coincides with applying Newton's method for optimization to the restricted function, because the restriction is quadratic. Thus, gradient descent with exact line search coincides with gradient descent using Newton's method.