13
$\begingroup$

In general setting of gradient descent algorithm, we have $x_{n+1} = x_{n} - \eta * gradient_{x_n}$ where $x_n$ is the current point, $\eta$ is the step size and $gradient_{x_n}$ is the gradient evaluated at $x_n$.

I have seen in some algorithm, people uses normalized gradient instead of gradient. I wanted to know what is the difference in using normalized gradient and simply gradient.

$\endgroup$
  • 1
    $\begingroup$ Can I ask a question? how can I calculate the normalized gradient if I have already obtained the gradient vector? If the gradient vector is numeric large, I need to normalize the gradient. Could you give some intuitive examples about normalizing gradient? Thank you! $\endgroup$ – user34683 Nov 12 '13 at 10:46
8
$\begingroup$

In a gradient descent algorithm, the algorithm proceeds by finding a direction along which you can find the optimal solution. The optimal direction turns out to be the gradient. However, since we are only interested in the direction and not necessarily how far we move along that direction, we are usually not interested in the magnitude of the gradient. Thereby, normalized gradient is good enough for our purposes and we let $\eta$ dictate how far we want to move in the computed direction. However, if you use unnormalized gradient descent, then at any point, the distance you move in the optimal direction is dictated by the magnitude of the gradient (in essence dictated by the surface of the objective function i.e a point on a steep surface will have high magnitude whereas a point on the fairly flat surface will have low magnitude).

From the above, you might have realized that normalization of gradient is an added controlling power that you get (whether it is useful or not is something upto your specific application). What I mean by the above is:
1] If you want to ensure that your algorithm moves in fixed step sizes in every iteration, then you might want to use normalized gradient descent with fixed $\eta$.
2] If you want to ensure that your algorithm moves in step sizes which is dictated precisely by you, then again you may want to use normalized gradient descent with your specific function for step size encoded into $\eta$.
3] If you want to let the magnitude of the gradient dictate the step size, then you will use unnormalized gradient descent. There are several other variants like you can let the magnitude of the gradient decide the step size, but you put a cap on it and so on.

Now, step size clearly has influence on the speed of convergence and stability. Which of the above step sizes works best depends purely on your application (i.e objective function). In certain cases, the relationship between speed of convergence, stability and step size can be analyzed. This relationship then may give a hint as to whether you would want to go with normalized or unnormalized gradient descent.

To summarize, there is no difference between normalized and unnormalized gradient descent (as far as the theory behind the algorithm goes). However, it has practical impact on the speed of convergence and stability. The choice of one over the other is purely based on the application/objective at hand.

$\endgroup$
  • $\begingroup$ You could take a intermediate approach where you normalize based on the first gradient, for example. This would still make the relative gradient size matter in terms of step size. $\endgroup$ – dashnick Jan 20 '17 at 4:16
2
$\begingroup$

What really matters is how $\eta$ is selected. It doesn't matter whether you use the normalized gradient or the unnormalized gradient if the step size is selected in a way that makes the length of $\eta$ times the gradient the same.

$\endgroup$
2
$\begingroup$

Which method has faster convergence will depend on your specific objective, and generally I use the normalized gradient. A good example of why you might want to do this is a simple quadratic: $f(x) = x^Tx$. In this case the ODE that describes a given gradient descent trajectory (as step sizes approaches zero) can be determined analytically: $y(t) = x_0/||x_0|| * e^{-t}$. So, the norm of the gradient decreases exponentially fast as you approach the critical point. In such cases it's often better to bounce back and forth across the min a few times than to approach it very slowly. In general though, first order methods are known to have very slow convergence around the critical points so you should not really be using them if you really care about accuracy. If you can't compute the Hessian of your objective analytically you can still approximate it (BFGS).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.