Gradient descent - Revision history

Vipul: /* Types of gradient descent */

2016-05-08T22:28:30Z

Types of gradient descent

← Older revision		Revision as of 22:28, 8 May 2016
Line 50:		Line 50:
	\| [[Gradient descent with exact line search]] \|\| The step size in each step is determined using an exact [[line search]] along the line of the gradient vector through the current point. \|\| Stationary \|\| No explicit functional form for <math>\alpha^{(k)}</math>, since it depends on details about the function. \|\| Note that this requires computation of the exact functional form restricted to the line as well as a procedure to optimize that function when restricted to that line. Neither of these may be available.		\| [[Gradient descent with exact line search]] \|\| The step size in each step is determined using an exact [[line search]] along the line of the gradient vector through the current point. \|\| Stationary \|\| No explicit functional form for <math>\alpha^{(k)}</math>, since it depends on details about the function. \|\| Note that this requires computation of the exact functional form restricted to the line as well as a procedure to optimize that function when restricted to that line. Neither of these may be available.
	\|-		\|-
	\| [[Gradient descent using Newton's method]] \|\| Here, the step size in each step is determined by applying one iteration (or a fixed number of iterations) of [[Newton's method for optimization of a function of one variable]] when performing the line search to determine the step size. \|\| Stationary \|\| <math>\alpha^{(k)}</math> is the reciprocal of the second-order directional derivative of <math>f</math> at <math>\vec{x}^{(k)}</math> along the direction of <math>(\nabla f)(\vec{x}^{(k)})</math>. Explicitly, if <math>H</math> is the Hessian of <math>f</math> at <math>\vec{x}_k</math>, and <math>\vec{v} = (\nabla f)(\vec{x}^{(k)})</math>, then <math>\alpha^{(k)} = \frac{\|\vec{v}\|^2}{\vec{v}^TH\vec{v}}</math>. \|\| Note that this coincides with exact line search when the function involved is a [[quadratic function of multiple variables]], because the restriction to the line is a quadratic function, and Newton's method for optimization converges in one step for a quadratic function of one variable. Note that this requires the computation of the [[second derivative]] at the point.<br>'''Note that this method is completely different from''' [[Newton's method for optimization of a function of multiple variables]], which does not move along the gradient direction, but rather, adjusts it by the inverse of the [[Hessian matrix]].		\| [[Gradient descent using Newton's method]] \|\| Here, the step size in each step is determined by applying one iteration (or a fixed number of iterations) of [[Newton's method for optimization of a function of one variable]] when performing the line search to determine the step size. \|\| Stationary \|\| <math>\alpha^{(k)}</math> is the reciprocal of the second-order directional derivative of <math>f</math> at <math>\vec{x}^{(k)}</math> along the direction of <math>(\nabla f)(\vec{x}^{(k)})</math>. Explicitly, if <math>H</math> is the Hessian of <math>f</math> at <math>\vec{x}^{(k)}</math>, and <math>\vec{v} = (\nabla f)(\vec{x}^{(k)})</math>, then <math>\alpha^{(k)} = \frac{\|\vec{v}\|^2}{\vec{v}^TH\vec{v}}</math>. \|\| Note that this coincides with exact line search when the function involved is a [[quadratic function of multiple variables]], because the restriction to the line is a quadratic function, and Newton's method for optimization converges in one step for a quadratic function of one variable. Note that this requires the computation of the [[second derivative]] at the point.<br>'''Note that this method is completely different from''' [[Newton's method for optimization of a function of multiple variables]], which does not move along the gradient direction, but rather, adjusts it by the inverse of the [[Hessian matrix]].
	\|}		\|}

Vipul: /* Types of gradient descent */

2016-05-08T22:28:10Z

Types of gradient descent

← Older revision		Revision as of 22:28, 8 May 2016
Line 50:		Line 50:
	\| [[Gradient descent with exact line search]] \|\| The step size in each step is determined using an exact [[line search]] along the line of the gradient vector through the current point. \|\| Stationary \|\| No explicit functional form for <math>\alpha^{(k)}</math>, since it depends on details about the function. \|\| Note that this requires computation of the exact functional form restricted to the line as well as a procedure to optimize that function when restricted to that line. Neither of these may be available.		\| [[Gradient descent with exact line search]] \|\| The step size in each step is determined using an exact [[line search]] along the line of the gradient vector through the current point. \|\| Stationary \|\| No explicit functional form for <math>\alpha^{(k)}</math>, since it depends on details about the function. \|\| Note that this requires computation of the exact functional form restricted to the line as well as a procedure to optimize that function when restricted to that line. Neither of these may be available.
	\|-		\|-
	\| [[Gradient descent using Newton's method]] \|\| Here, the step size in each step is determined by applying one iteration (or a fixed number of iterations) of [[Newton's method for optimization of a function of one variable]] when performing the line search to determine the step size. \|\| Stationary \|\| <math>\alpha^{(k)}</math> is the reciprocal of the second-order directional derivative of <math>f</math> at <math>\vec{x}_k</math> along the direction of <math>(\nabla f)(\vec{x}_k)</math>. Explicitly, if <math>H</math> is the Hessian of <math>f</math> at <math>\vec{x}_k</math>, and <math>\vec{v} = (\nabla f)(\vec{x}_k)</math>, then <math>\alpha^{(k)} = \frac{\|\vec{v}\|^2}{\vec{v}^TH\vec{v}}</math>. \|\| Note that this coincides with exact line search when the function involved is a [[quadratic function of multiple variables]], because the restriction to the line is a quadratic function, and Newton's method for optimization converges in one step for a quadratic function of one variable. Note that this requires the computation of the [[second derivative]] at the point.<br>'''Note that this method is completely different from''' [[Newton's method for optimization of a function of multiple variables]], which does not move along the gradient direction, but rather, adjusts it by the inverse of the [[Hessian matrix]].		\| [[Gradient descent using Newton's method]] \|\| Here, the step size in each step is determined by applying one iteration (or a fixed number of iterations) of [[Newton's method for optimization of a function of one variable]] when performing the line search to determine the step size. \|\| Stationary \|\| <math>\alpha^{(k)}</math> is the reciprocal of the second-order directional derivative of <math>f</math> at <math>\vec{x}^{(k)}</math> along the direction of <math>(\nabla f)(\vec{x}^{(k)})</math>. Explicitly, if <math>H</math> is the Hessian of <math>f</math> at <math>\vec{x}_k</math>, and <math>\vec{v} = (\nabla f)(\vec{x}^{(k)})</math>, then <math>\alpha^{(k)} = \frac{\|\vec{v}\|^2}{\vec{v}^TH\vec{v}}</math>. \|\| Note that this coincides with exact line search when the function involved is a [[quadratic function of multiple variables]], because the restriction to the line is a quadratic function, and Newton's method for optimization converges in one step for a quadratic function of one variable. Note that this requires the computation of the [[second derivative]] at the point.<br>'''Note that this method is completely different from''' [[Newton's method for optimization of a function of multiple variables]], which does not move along the gradient direction, but rather, adjusts it by the inverse of the [[Hessian matrix]].
	\|}		\|}

Vipul: /* Intuition behind choice of learning rate */

2015-01-21T22:49:36Z

Intuition behind choice of learning rate

← Older revision		Revision as of 22:49, 21 January 2015
Line 28:		Line 28:
	\| Quadratic function of one variable \|\| [[Gradient descent with constant learning rate for a quadratic function of one variable]] \|\| Constant \|\| Constant (only one dimension, so no scope for variation) \|\| The first derivative is a linear function with slope equal to the second derivative. We need to move by the value <math>-f'(x)/f''(x)</math>, where <math>f''(x)</math> is the slope of the line. The ideal learning rate is therefore <math>1/f''(x)</math>. Note that <math>f''</math> is constant.		\| Quadratic function of one variable \|\| [[Gradient descent with constant learning rate for a quadratic function of one variable]] \|\| Constant \|\| Constant (only one dimension, so no scope for variation) \|\| The first derivative is a linear function with slope equal to the second derivative. We need to move by the value <math>-f'(x)/f''(x)</math>, where <math>f''(x)</math> is the slope of the line. The ideal learning rate is therefore <math>1/f''(x)</math>. Note that <math>f''</math> is constant.
	\|-		\|-
	\| Quadratic function of multiple variables \|\| [[Gradient descent with constant learning rate for a quadratic function of multiple variables]] \|\| Constant \|\| Variable \|\| The main challenge arises from the "elliptical geometry", i.e., the second derivative being radically different in different directions. We can get a mathematical handle of this by finding the eigenvalues of the Hessian. The ratio of the largest to the smallest eigenvalue, also known as the condition number, helps us understand the difficulty of the problem. Basically, if we are choosing a constant learning rate, it has to be chosen ~~as the reciprocal of~~ the largest eigenvalue (the <math>L^2</math>-norm) but that would result in very slow convergence along the directions of the smaller eigenvalues.		\| Quadratic function of multiple variables \|\| [[Gradient descent with constant learning rate for a quadratic function of multiple variables]] \|\| Constant \|\| Variable \|\| The main challenge arises from the "elliptical geometry", i.e., the second derivative being radically different in different directions. We can get a mathematical handle of this by finding the eigenvalues of the Hessian. The ratio of the largest to the smallest eigenvalue, also known as the condition number, helps us understand the difficulty of the problem. Basically, if we are choosing a constant learning rate, it has to be chosen based on the largest eigenvalue (the <math>L^2</math>-norm) but that would result in very slow convergence along the directions of the smaller eigenvalues.
	\|-		\|-
	\| Convex function of one variable \|\| [[Gradient descent with constant learning rate for a convex function of one variable]] \|\| Variable \|\| Constant (only one dimension, so no scope for variation) \|\| The details depend on whether there is a global bound on the second derivative. If there is such a bound, and we are aware of it in advance, the quality of convergence depends on how widely the second derivative at the optimum differs from the global bound. The quadratic case is extreme: these values coincide, so we can get one-step convergence if we know the second derivative.		\| Convex function of one variable \|\| [[Gradient descent with constant learning rate for a convex function of one variable]] \|\| Variable \|\| Constant (only one dimension, so no scope for variation) \|\| The details depend on whether there is a global bound on the second derivative. If there is such a bound, and we are aware of it in advance, the quality of convergence depends on how widely the second derivative at the optimum differs from the global bound. The quadratic case is extreme: these values coincide, so we can get one-step convergence if we know the second derivative.

Vipul: /* Iterative step */

2015-01-18T16:16:35Z

Iterative step

← Older revision		Revision as of 16:16, 18 January 2015
Line 15:		Line 15:
	<math>\vec{x}^{(k+1)} = \vec{x}^{(k)} - \alpha^{(k)} \nabla f\left(\vec{x}^{(k)}\right)</math>		<math>\vec{x}^{(k+1)} = \vec{x}^{(k)} - \alpha^{(k)} \nabla f\left(\vec{x}^{(k)}\right)</math>

	Note that the quantity <math>\alpha^{(k)}</math> (called the '''learning rate''') needs to be specified, and the method of choosing this constant describes the type of gradient descent.		Note that the quantity <math>\alpha^{(k)}</math> (called the '''learning rate''') needs to be specified, and the method of choosing this constant describes the type of gradient descent. For the simplest type of gradient descent, called [[gradient descent with constant learning rate]], all the <math>\alpha^{(k)}</math> equal a constant <math>\alpha</math> and are independent of the current iterate.

	One aspect that distinguishes gradient descent from some variants (such as [[parallel coordinate descent]], [[sequential coordinate descent]], and [[accelerated gradient method]]s) is that in every iteration, we move strictly along the direction of the gradient vector, i.e., <math>\vec{x}^{(k)} - \vec{x}^{(k+1)}</math> is a scalar multiple of the gradient vector at <math>\vec{x}^{(k)}</math>.		One aspect that distinguishes gradient descent from some variants (such as [[parallel coordinate descent]], [[sequential coordinate descent]], and [[accelerated gradient method]]s) is that in every iteration, we move strictly along the direction of the gradient vector, i.e., <math>\vec{x}^{(k)} - \vec{x}^{(k+1)}</math> is a scalar multiple of the gradient vector at <math>\vec{x}^{(k)}</math>.

Vipul: /* Iterative step */

2015-01-18T16:10:48Z

Iterative step

← Older revision		Revision as of 16:10, 18 January 2015
Line 15:		Line 15:
	<math>\vec{x}^{(k+1)} = \vec{x}^{(k)} - \alpha^{(k)} \nabla f\left(\vec{x}^{(k)}\right)</math>		<math>\vec{x}^{(k+1)} = \vec{x}^{(k)} - \alpha^{(k)} \nabla f\left(\vec{x}^{(k)}\right)</math>

	Note that the quantity <math>\alpha^{(k)}</math> needs to be specified, and the method of choosing this constant describes the type of gradient descent.		Note that the quantity <math>\alpha^{(k)}</math> (called the '''learning rate''') needs to be specified, and the method of choosing this constant describes the type of gradient descent.

	One aspect that distinguishes gradient descent from some variants (such as [[parallel coordinate descent]], [[sequential coordinate descent]], and [[accelerated gradient method]]s) is that in every iteration, we move strictly along the direction of the gradient vector, i.e., <math>\vec{x}^{(k)} - \vec{x}^{(k+1)}</math> is a scalar multiple of the gradient vector at <math>\vec{x}^{(k)}</math>.		One aspect that distinguishes gradient descent from some variants (such as [[parallel coordinate descent]], [[sequential coordinate descent]], and [[accelerated gradient method]]s) is that in every iteration, we move strictly along the direction of the gradient vector, i.e., <math>\vec{x}^{(k)} - \vec{x}^{(k+1)}</math> is a scalar multiple of the gradient vector at <math>\vec{x}^{(k)}</math>.

Vipul: /* Gradient descent in a typical machine learning context */

2014-09-12T01:05:37Z

Gradient descent in a typical machine learning context

← Older revision		Revision as of 01:05, 12 September 2014
Line 55:		Line 55:
	==Gradient descent in a typical machine learning context==		==Gradient descent in a typical machine learning context==

	The mathematical form of gradient descent in machine learning problems is more specific: the function that we are trying to optimize is ~~[[additively separable function\|additively separable]]~~, with all the additive components having the same functional form but with different parameters (note that the ''parameters'' referred to here are the feature values for examples, not the "parameter vector" -- which plays the role of the input to the function in this case). Explicitly, the function <math>f</math> on which we are doing gradient descent has the form:		The mathematical form of gradient descent in machine learning problems is more specific: the function that we are trying to optimize is expressible as a sum, with all the additive components having the same functional form but with different parameters (note that the ''parameters'' referred to here are the feature values for examples, not the "parameter vector" -- which plays the role of the input to the function in this case). Explicitly, the function <math>f</math> on which we are doing gradient descent has the form:

	<math>f(\vec{x}) = \sum_{i=1}^m g(\vec{x}, \vec{v}_i)</math>		<math>f(\vec{x}) = \sum_{i=1}^m g(\vec{x}, \vec{v}^{(i)})</math>

	where <math>\vec{v}_i</math> is a vector storing the <math>i^{th}</math> example, and <math>m</math> is the number of examples. In such an implementation, gradient descent can be parallelized. We have that the gradient is a sum of the gradients of each of the additive components:		where <math>\vec{v}^{(i)}</math> is a vector storing the <math>i^{th}</math> example, and <math>m</math> is the number of examples. In such an implementation, gradient descent can be parallelized. We have that the gradient is a sum of the gradients of each of the additive components:

	<math>\nabla f(\vec{x}) = \sum_{i=1}^m \nabla_{\vec{x}} g(\vec{x}, \vec{v}_i)</math>		<math>\nabla f(\vec{x}) = \sum_{i=1}^m \nabla_{\vec{x}} g(\vec{x}, \vec{v}^{(i)})</math>

	The computation of the summands can be carried out in parallel by different processors, each of which has access to the corresponding set of <math>\vec{v}_i</math>s.		The computation of the summands can be carried out in parallel by different processors, each of which has access to the corresponding set of <math>\vec{v}^{(i)}</math>s.

	==Variants of gradient descent==		==Variants of gradient descent==

Vipul: /* Intuition behind choice of learning rate */

2014-09-07T22:17:55Z

Intuition behind choice of learning rate

← Older revision		Revision as of 22:17, 7 September 2014
Line 26:		Line 26:
	! Case !! Discussion of [[gradient descent with constant learning rate]] !! Variation in second derivative when restricted to a line !! Variation in second derivative between directions !! Explanation		! Case !! Discussion of [[gradient descent with constant learning rate]] !! Variation in second derivative when restricted to a line !! Variation in second derivative between directions !! Explanation
	\|-		\|-
	\| Quadratic function of one variable \|\| [[Gradient ~~decent~~ with constant learning rate for a quadratic function of one variable]] \|\| Constant \|\| Constant (only one dimension, so no scope for variation) \|\| The first derivative is a linear function with slope equal to the second derivative. We need to move by the value <math>-f'(x)/f''(x)</math>, where <math>f''(x)</math> is the slope of the line. The ideal learning rate is therefore <math>1/f''(x)</math>. Note that <math>f''</math> is constant.		\| Quadratic function of one variable \|\| [[Gradient descent with constant learning rate for a quadratic function of one variable]] \|\| Constant \|\| Constant (only one dimension, so no scope for variation) \|\| The first derivative is a linear function with slope equal to the second derivative. We need to move by the value <math>-f'(x)/f''(x)</math>, where <math>f''(x)</math> is the slope of the line. The ideal learning rate is therefore <math>1/f''(x)</math>. Note that <math>f''</math> is constant.
	\|-		\|-
	\| Quadratic function of multiple variables \|\| [[Gradient descent with constant learning rate for a quadratic function of multiple variables]] \|\| Constant \|\| Variable \|\| The main challenge arises from the "elliptical geometry", i.e., the second derivative being radically different in different directions. We can get a mathematical handle of this by finding the eigenvalues of the Hessian. The ratio of the largest to the smallest eigenvalue, also known as the condition number, helps us understand the difficulty of the problem. Basically, if we are choosing a constant learning rate, it has to be chosen as the reciprocal of the largest eigenvalue (the <math>L^2</math>-norm) but that would result in very slow convergence along the directions of the smaller eigenvalues.		\| Quadratic function of multiple variables \|\| [[Gradient descent with constant learning rate for a quadratic function of multiple variables]] \|\| Constant \|\| Variable \|\| The main challenge arises from the "elliptical geometry", i.e., the second derivative being radically different in different directions. We can get a mathematical handle of this by finding the eigenvalues of the Hessian. The ratio of the largest to the smallest eigenvalue, also known as the condition number, helps us understand the difficulty of the problem. Basically, if we are choosing a constant learning rate, it has to be chosen as the reciprocal of the largest eigenvalue (the <math>L^2</math>-norm) but that would result in very slow convergence along the directions of the smaller eigenvalues.

Vipul: /* Intuition behind choice of learning rate */

2014-09-07T22:16:46Z

Intuition behind choice of learning rate

← Older revision		Revision as of 22:16, 7 September 2014
Line 21:		Line 21:
	==Intuition behind choice of learning rate==		==Intuition behind choice of learning rate==

	~~To get at~~ the ~~intuition behind~~ the ~~choice~~ of ~~learning rate~~, ~~consider the following~~:		Essentially, the learning rate should be chosen to be the reciprocal of the second derivative (often referred to as the ''curvature'' although it is not the same as curvature as used in differential geometry). There are, however, a number of subtleties. The cases are discussed below, in roughly increasing order of complexity:

	* In the case of [[gradient descent with constant learning rate for a quadratic function of one variable]], ~~the ideal choice of learning rate~~ is ~~the reciprocal of~~ the second derivative ~~of the function (which is a constant value)~~. ~~Intuitively, we want~~ to move ~~far enough that~~ the ''~~first~~'' ~~derivative~~ (the ~~one-dimensional analogue~~ of the ~~gradient vector~~) ~~becomes zero~~. ~~Since~~ the ~~first derivative is changing linearly~~, ~~and its slope equals~~ the second derivative~~, we need to divide~~ by the ~~second derivative~~. So the ~~ideal~~ learning rate is the reciprocal of the ~~second derivative~~.		{\| class="sortable" border="1"
	* The situation becomes a little more complicated when we consider [[~~gradient~~ descent with constant learning rate for a convex function of one variable]]~~. In this case~~, there is ~~no globally uniform ideal learning rate. In fact, there may exist no learning rate that works globally. If, however, the convex function has~~ a global ~~upper~~ bound on ~~its~~ second derivative, ~~then~~ we ~~can use~~ the ~~reciprocal~~ of ~~that~~ global bound ~~as our constant learning rate~~. ~~More generally~~, we can ~~use a changing~~ learning rate ~~that adapts to~~ the ~~values~~ of second derivative ~~around~~ the ~~current iterate~~.		! Case !! Discussion of [[gradient descent with constant learning rate]] !! Variation in second derivative when restricted to a line !! Variation in second derivative between directions !! Explanation
			\|-
			\| Quadratic function of one variable \|\| [[Gradient decent with constant learning rate for a quadratic function of one variable]] \|\| Constant \|\| Constant (only one dimension, so no scope for variation) \|\| The first derivative is a linear function with slope equal to the second derivative. We need to move by the value <math>-f'(x)/f''(x)</math>, where <math>f''(x)</math> is the slope of the line. The ideal learning rate is therefore <math>1/f''(x)</math>. Note that <math>f''</math> is constant.
			\|-
			\| Quadratic function of multiple variables \|\| [[Gradient descent with constant learning rate for a quadratic function of multiple variables]] \|\| Constant \|\| Variable \|\| The main challenge arises from the "elliptical geometry", i.e., the second derivative being radically different in different directions. We can get a mathematical handle of this by finding the eigenvalues of the Hessian. The ratio of the largest to the smallest eigenvalue, also known as the condition number, helps us understand the difficulty of the problem. Basically, if we are choosing a constant learning rate, it has to be chosen as the reciprocal of the largest eigenvalue (the <math>L^2</math>-norm) but that would result in very slow convergence along the directions of the smaller eigenvalues.
			\|-
			\| Convex function of one variable \|\| [[Gradient descent with constant learning rate for a convex function of one variable]] \|\| Variable \|\| Constant (only one dimension, so no scope for variation) \|\| The details depend on whether there is a global bound on the second derivative. If there is such a bound, and we are aware of it in advance, the quality of convergence depends on how widely the second derivative at the optimum differs from the global bound. The quadratic case is extreme: these values coincide, so we can get one-step convergence if we know the second derivative.
			\|-
			\| Convex function of multiple variables \|\| [[Gradient descent with constant learning rate for a convex function of multiple variables]] \|\| Variable \|\| Variable \|\| Two sources of variation enter the picture: the elliptical geometry arising from different second derivatives in different directions, and the ratio of the second derivative at the optimum to the global bound on the second derivative.
			\|}

	==Corresponding root-finding method==		==Corresponding root-finding method==

Vipul: /* Types of gradient descent */

2014-09-07T22:02:38Z

Types of gradient descent

← Older revision		Revision as of 22:02, 7 September 2014
Line 41:		Line 41:
	\| [[Gradient descent with exact line search]] \|\| The step size in each step is determined using an exact [[line search]] along the line of the gradient vector through the current point. \|\| Stationary \|\| No explicit functional form for <math>\alpha^{(k)}</math>, since it depends on details about the function. \|\| Note that this requires computation of the exact functional form restricted to the line as well as a procedure to optimize that function when restricted to that line. Neither of these may be available.		\| [[Gradient descent with exact line search]] \|\| The step size in each step is determined using an exact [[line search]] along the line of the gradient vector through the current point. \|\| Stationary \|\| No explicit functional form for <math>\alpha^{(k)}</math>, since it depends on details about the function. \|\| Note that this requires computation of the exact functional form restricted to the line as well as a procedure to optimize that function when restricted to that line. Neither of these may be available.
	\|-		\|-
	\| [[Gradient descent using Newton's method]] \|\| Here, the step size in each step is determined by applying one iteration (or a fixed number of iterations) of [[Newton's method for optimization of a function of one variable]] when performing the line search to determine the step size. \|\| ~~Stationaryo~~ \|\| <math>\alpha^{(k)}</math> is the reciprocal of the second-order directional derivative of <math>f</math> at <math>\vec{x}_k</math> along the direction of <math>(\nabla f)(\vec{x}_k)</math>. Explicitly, if <math>H</math> is the Hessian of <math>f</math> at <math>\vec{x}_k</math>, and <math>\vec{v} = (\nabla f)(\vec{x}_k)</math>, then <math>\alpha^{(k)} = \frac{\|\vec{v}\|^2}{\vec{v}^TH\vec{v}}</math>. \|\| Note that this coincides with exact line search when the function involved is a [[quadratic function of multiple variables]], because the restriction to the line is a quadratic function, and Newton's method for optimization converges in one step for a quadratic function of one variable. Note that this requires the computation of the [[second derivative]] at the point.<br>'''Note that this method is completely different from''' [[Newton's method for optimization of a function of multiple variables]], which does not move along the gradient direction, but rather, adjusts it by the inverse of the [[Hessian matrix]].		\| [[Gradient descent using Newton's method]] \|\| Here, the step size in each step is determined by applying one iteration (or a fixed number of iterations) of [[Newton's method for optimization of a function of one variable]] when performing the line search to determine the step size. \|\| Stationary \|\| <math>\alpha^{(k)}</math> is the reciprocal of the second-order directional derivative of <math>f</math> at <math>\vec{x}_k</math> along the direction of <math>(\nabla f)(\vec{x}_k)</math>. Explicitly, if <math>H</math> is the Hessian of <math>f</math> at <math>\vec{x}_k</math>, and <math>\vec{v} = (\nabla f)(\vec{x}_k)</math>, then <math>\alpha^{(k)} = \frac{\|\vec{v}\|^2}{\vec{v}^TH\vec{v}}</math>. \|\| Note that this coincides with exact line search when the function involved is a [[quadratic function of multiple variables]], because the restriction to the line is a quadratic function, and Newton's method for optimization converges in one step for a quadratic function of one variable. Note that this requires the computation of the [[second derivative]] at the point.<br>'''Note that this method is completely different from''' [[Newton's method for optimization of a function of multiple variables]], which does not move along the gradient direction, but rather, adjusts it by the inverse of the [[Hessian matrix]].
	\|}		\|}

Vipul: /* Iterative step */

2014-09-07T22:00:25Z

Iterative step

← Older revision		Revision as of 22:00, 7 September 2014
Line 18:		Line 18:

	One aspect that distinguishes gradient descent from some variants (such as [[parallel coordinate descent]], [[sequential coordinate descent]], and [[accelerated gradient method]]s) is that in every iteration, we move strictly along the direction of the gradient vector, i.e., <math>\vec{x}^{(k)} - \vec{x}^{(k+1)}</math> is a scalar multiple of the gradient vector at <math>\vec{x}^{(k)}</math>.		One aspect that distinguishes gradient descent from some variants (such as [[parallel coordinate descent]], [[sequential coordinate descent]], and [[accelerated gradient method]]s) is that in every iteration, we move strictly along the direction of the gradient vector, i.e., <math>\vec{x}^{(k)} - \vec{x}^{(k+1)}</math> is a scalar multiple of the gradient vector at <math>\vec{x}^{(k)}</math>.

			==Intuition behind choice of learning rate==

			To get at the intuition behind the choice of learning rate, consider the following:

			* In the case of [[gradient descent with constant learning rate for a quadratic function of one variable]], the ideal choice of learning rate is the reciprocal of the second derivative of the function (which is a constant value). Intuitively, we want to move far enough that the ''first'' derivative (the one-dimensional analogue of the gradient vector) becomes zero. Since the first derivative is changing linearly, and its slope equals the second derivative, we need to divide by the second derivative. So the ideal learning rate is the reciprocal of the second derivative.
			* The situation becomes a little more complicated when we consider [[gradient descent with constant learning rate for a convex function of one variable]]. In this case, there is no globally uniform ideal learning rate. In fact, there may exist no learning rate that works globally. If, however, the convex function has a global upper bound on its second derivative, then we can use the reciprocal of that global bound as our constant learning rate. More generally, we can use a changing learning rate that adapts to the values of second derivative around the current iterate.

	==Corresponding root-finding method==		==Corresponding root-finding method==