Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Thank you for publicizing an early draft. It is really good and very helpful.

I think your explanations are great, but you seem to imply that the gradient 3 for f(x,y) = xy with x = -2 and y=3 derived w.r.t x is somehow the "best" gradient (you call it the correct or actual gradient) but I don't understand why this is better than any other positive number.

Wouldn't we optimize faster of we tug with a force of 6 instead of 3?

  x = -2, y= 3, 
  dx = 3, dy = -2
  step = 0.0001

  f(x,y) = -6

  f(x+dx*step, y*dy*step) =  -5.998...

  // Now if we double the gradient
  f(x+2*dx*step, y*2*dy*step) = -5.997...


I'm not the OP but:

The analytical gradient is actually a general tool used in multivariable calculus. It's vector-valued, in that if you take the gradient of a function of three variables: f(x, y, z), then you'll get a 3-vector back. Vectors are defined by two characteristics: a direction and a magnitude. The gradient's direction is the direction of greatest increase and the magnitude of the gradient is the instantaneous rate of change.

The gradient is being put to work here in order to optimize a function using a process called gradient ascent. Intuitively it makes sense that in order to optimize your function you'd want to "move" in the direction of greatest increase at every step. However, the size of the step that you take is tricky. As you point out, in this case, we can increase the objective function value more if we double the step size. However, you're not actually doubling /the gradient/.

If you look at the expression that you wrote you should see:

    x + 2 * dx * step, y * 2 * dy * step.
What you've done is double the step-multiplier, not the gradient itself (<dx, dy>). This means that the optimization process jumps further at each step. However, the step size that OP chose is somewhat arbitrary to begin with, so it's not clear why any particular choice would be better or worse. The reason that the step size matters is that if your step size is too large your optimization process might jump over a minimum location or something similarly bad -- there are pathological functions like the Rosenbrock Function [1] which are notoriously hard to optimize with gradient ascent. In practice, you'll often choose your step size more intelligently based on a few different tests, or vary it as the optimization process progresses.

In this particular instance, the surface that you're trying to optimize is pretty simple so basically any step value will do the trick. It may take a different number of steps in order to compute the global maximum, but most reasonable step sizes will get there.

[1] http://en.wikipedia.org/wiki/Rosenbrock_function


This is actually a Really good question, I should really expand on this in the guide.

The simplicity of the example is deceiving you, in the sense that in a more complex circuit (than just x * y), it will no longer be the case that just simply marching along the direction of the gradient in huge steps will necessarily lead to good outcome.

All we can do is work very locally. You are at some specific point (x,y)=(-2,3). The gradient is telling you that the best direction (in this 2-D space) to go along if you're interested in increasing your function is in the direction (3, -2), which is the gradient at that point.

Now if you remember there's a crucial parameter step_size, and the update will take the form (in vector notation):

(x,y) += step_size * (dx, dy)

all that the gradient is saying is that if step_size is infinitesimally small, your function will increase, and that this direction is the Fastest increase. If you try any other direction with infinitesimally small step_size, you will do worse. However, there are no guarantees whatsoever on what happens when the step_size is larger. In practice we use step sizes of 0.001, or whatever (small numbers), and it works only because the functions we deal with are relatively smooth and well-behaved.

However, after we take the small step we have to right away re-evaluate the gradient because suddenly the direction could be all shifted. Sometimes doing gradient descent is compared to walking blind on a hill and trying to get to the top: you can sense the steepness of the hill at your feet (the gradient), and you make steps accordingly. But if you make too large of a step and you're not careful, there could have been actually been large drop.

TLDR: x * y is very simple example, this certainly wouldn't be the case in more complicated circuit.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: