4
$\begingroup$

Suppose I define two functions of $x$ in terms of a convex function $f$ with a unique minimum $x_0$:

$$f_1(x) = 1 \times f(x)$$

$$f_2(x) = 2 \times f(x)$$

Suppose I wanted to minimize each of these functions numerically.
Clearly, the minima of both occur at the same $x_0$.
But if I tried to do gradient descent, I would be performing the updates

$$x \gets x - \lambda \nabla f_k(x)$$

and therefore step sizes would be larger for $f_2$ than $f_1$.
To me, this doesn't make sense. The step sizes should not depend on the scaling factor!
It therefore seems to imply that gradient descent should be normalized such that the step sizes have constant magnitude regardless of the gradient's magnitude.

So what justification is there for having the step size increase with the magnitude of the gradient when it's obvious that scaling the original function will change the gradient but not the location of its extrema?

$\endgroup$
2
  • $\begingroup$ are you trying to minimize $f_1$ and $f_2$ jointly? Not sure if I understand your scenario. $\endgroup$ Apr 17 '16 at 19:25
  • $\begingroup$ @CharlieParker: I was analyzing two separate cases. $\endgroup$
    – user541686
    Apr 18 '16 at 0:22
2
$\begingroup$

That's one of the reasons that the gradient decent is not the best method. This issue is resoved by the Newton method.

Let $H_k(x)=\nabla^2f_k(x)$ be the Hessian of $f_k(x)$, then by the Newton method your updates will be:

$$x_{t+1}=x_t-\lambda H_k(x_t)^{-1}\nabla f_k(x_t)$$

Now for example, if $f_k(x)=kf(x)$, then $\nabla f_k(x)=k\nabla f(x)$, and $H_k(x)=k\nabla^2 f(x)$, (and $H_k(x)^{-1}=\frac{1}{k}(\nabla^2 f(x))^{-1}$) therefor:

$$x_{t+1}=x_t-\lambda H_k(x_t)^{-1}\nabla f_k(x_t)=x_t-\lambda \frac{1}{k}(\nabla^2 f(x_t))^{-1}k\nabla f(x_t)=x_t-\lambda (\nabla^2 f(x_t))^{-1}\nabla f(x_t)$$

which does not depend on $k$.

$\endgroup$
4
  • $\begingroup$ No method is perfect. All methods, including Newton's method, have disadvantages. For instance, Newton's method is more computationally expensive on a per-iteration basis, sometimes significantly so. There are real-world problems where Newton's method simply cannot be done because it's too expensive. And of course, what do you do if the function is not twice-differentiable, or if it is not strictly convex? $\endgroup$ Oct 23 '14 at 14:19
  • 1
    $\begingroup$ @MichaelGrant: You are absolutely right! Calculation of the Hessian matrix (and its inverse) can be intractable or expensive. And definitely you know better than us (since I know who you are) that, that's a reason for why we use BFGS (and L-BFGS). I was just trying to refer the OP's point, that while the simple gradient descent is not the "best" method, it is also not wrong. $\endgroup$
    – Alt
    Oct 25 '14 at 0:39
  • 1
    $\begingroup$ Thanks for the kind words! But I wouldn't say for sure that I would know better than you. Of course I am biased towards methods I know how to use well :-) I just want to make sure the OP understands that gradient methods still have their usefulness; indeed they are enjoying a bit of resurgence lately. But step size management is critical! $\endgroup$ Oct 25 '14 at 1:36
  • $\begingroup$ Hi! So I'm not sure why I forgot about this question I asked nearly two years ago, but looking at your answer again, I feel like Newton's method is very misleading here because it can change the direction of the step entirely, not just its magnitude -- it's solving a different problem. The entire point of my question was the magnitude, and I still don't understand why gradient descent methods -- which are used in practice, and by which I mean the ones that take steps in the same direction as the gradient -- don't scale themselves to normalize. CC @MichaelGrant. $\endgroup$
    – user541686
    Jun 21 '16 at 23:48
2
$\begingroup$

Your intuition is correct. Outside of a narrow window around the optimum, the magnitude of the gradient is actually irrelevant to the step size. It is just as easy to imagine a steep gradient towards a nearby optimum, or a shallow gradient to a distant optimum, as it is to imagine a steep gradient to a far off optimum or a shallow gradient to a nearby optimum.

The distance to the optimum is only proportional to the gradient's magnitude when the parameter's value is already within a neighborhood of the optimum small enough to contain no inflection points, which is not generally something we can know in advance if we are using gradient descent. That is why it is necessary to multiply the gradient by a small (or even diminishing) step size.

I have personally found, in developing my own algorithms, that it is possible to simply throw away the gradient's magnitude and use a step size which depends only on the number of updates. This is a scale-invariant and more robust approach, which, as a bonus, bypasses the issues of "vanishing" and "exploding" gradients.

$\endgroup$
1
$\begingroup$

If your step size $\lambda$ is small enough, then when you update $$x_{t+1} = x_t - \lambda \nabla f_k(x)$$ you can ensure that $f_k(x_t) \geq f_k(x_{t+1})$. At least for the function you performed a gradient descent step on. So, if $\lambda$ is small enough for $f_1$, maybe it's not small enough for $f_2$.

The normalization you're talking about is something like one of the methods based on newton's method or conjugate gradient.

$\endgroup$
3
  • $\begingroup$ I'm not sure this is answering the question (or maybe I'm not understanding what you're getting at). $\endgroup$
    – user541686
    Oct 21 '14 at 20:45
  • 1
    $\begingroup$ Unless I am wrong, most people use a variable step size to avoid the problems you're pointing at. So, to me there's probably no real justification for having the step size change with the magnitude of the gradient : that's a drawback of the method. That's why we have newton's method, conjugate gradient and other stuff like that. $\endgroup$
    – davcha
    Oct 21 '14 at 20:51
  • $\begingroup$ It's not like you can ignore step size with Newton's method though. Sure, once you enter the region of quadratic convergence, a step size of 1 is optimal. But outside this region you must still guard against overshoot, and adaptive step sizes can be helpful. (Besides, how do you know when you've arrived in the region of quadratic convergence?) My point: no descent method is going to be completely free from scaling and/or step size issues in practice. $\endgroup$ Oct 24 '14 at 17:13

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.