Vipul: Created page with "==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 vec..."

2014-05-26T23:06:20Z

Created page with "==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 vec..."

New page

==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===

{{further|[[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 of a function of one variable|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]].

Gradient descent with exact line search - Revision history

Vipul: Created page with "==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 vec..."