3 ms·

I think a concrete example of what you're saying is that a rotation vector field (e.g. F(x,y) = [y, -x]) is not the gradient of any potential function. And I t

I think a concrete example of what you're saying is that a rotation vector field (e.g. F(x,y) = [y, -x]) is not the gradient of any potential function. And I think you're saying it's intrinsically easier to find where a vector field vanishes if it has a potential function. You can just follow the vector field and you'll get to a zero. But if you follow a rotating vector field, it will take you in circles. But given that you're doing Newton's method, I don't think one problem is easier than the other, right?

dataflow 5y ago
Is your conjecture that Newton's method would always work at least as well as gradient descent when the vector field has nonzero rotation? I don't see why that should be true, especially given that's not the case when there's zero rotation. You could easily come up with examples where gradient descent would work better despite the rotation, and I expect you could also find lots of rotation cases where Newton's method would get completely thrown off (whereas GD wouldn't). (Also, don't conflate the problem with the solution. My statements were about optimization vs. root finding, not about Newton vs. GD. Even if there is a solution that works for multiple problems, that doesn't mean the problems are equally difficult. If one problem admits solutions that the other doesn't, then it's still easier in that sense. If a problem can be reduced to another, then it's also easier in that sense. Just like how you can use a cannon to kill a fly, but that doesn't mean destroying a building is as easy as killing a fly...)
- gugagore 5y ago
  > Is your conjecture that Newton's method would always work at least as well as gradient descent when the vector field has nonzero rotation? > You could easily come up with examples where gradient descent would work better despite the rotation, and I expect you could also find lots of rotation cases where Newton's method would get completely thrown off (whereas GD wouldn't). I don't think I understand the meaning of the questions. It isn't gradient descent unless you have a potential function. You cannot do gradient descent on a vector field that is not a gradient. You can solve an ODE. You can, of course, turn a root-finding problem (F(x) = 0) into a minimization problem by defining a potential like g(x) = (F(x))^2. You can do gradient descent on g. So in that sense, both of these problems reduce to each other, though there are better methods for solving F(x) = 0 than minimizing g. I still don't understand this sense of optimization being easier than root finding. What I do understand is some sense in which there are more vector fields than there are gradients, since only some vector fields are gradients of potential functions. My comment was intended to point that out, since I thought that is maybe what you meant.
  - dataflow 5y ago
    I think I explained it poorly. I used "gradient descent" colloquially there, I just meant following the 'flow' in your vector field like you might in actual gradient descent. (Yes in this case it'd be Euler's method, and you can add whatever bells and whistles you would add for GD like to choose step sizes and whatnot.) I'm saying you might still be able to find the zero of your function by doing that. That neither implies that Newton's method would have performed better on your problem (it may perform better, or it may not), nor does it imply that your vector field must have been a gradient of anything. Right? Whereas you're saying "given that you're doing Newton's method, I don't think one problem is easier than the other, right?" as if Newton is somehow guaranteed to give equally good if not better results than e.g. Euler when your vector field isn't a gradient... which I don't believe it is? Certainly there are cases when that happens but it's not implied, right?

dataflow 5y ago

Is your conjecture that Newton's method would always work at least as well as gradient descent when the vector field has nonzero rotation? I don't see why that should be true, especially given that's not the case when there's zero rotation. You could easily come up with examples where gradient descent would work better despite the rotation, and I expect you could also find lots of rotation cases where Newton's method would get completely thrown off (whereas GD wouldn't). (Also, don't conflate the problem with the solution. My statements were about optimization vs. root finding, not about Newton vs. GD. Even if there is a solution that works for multiple problems, that doesn't mean the problems are equally difficult. If one problem admits solutions that the other doesn't, then it's still easier in that sense. If a problem can be reduced to another, then it's also easier in that sense. Just like how you can use a cannon to kill a fly, but that doesn't mean destroying a building is as easy as killing a fly...)

gugagore 5y ago
> Is your conjecture that Newton's method would always work at least as well as gradient descent when the vector field has nonzero rotation? > You could easily come up with examples where gradient descent would work better despite the rotation, and I expect you could also find lots of rotation cases where Newton's method would get completely thrown off (whereas GD wouldn't). I don't think I understand the meaning of the questions. It isn't gradient descent unless you have a potential function. You cannot do gradient descent on a vector field that is not a gradient. You can solve an ODE. You can, of course, turn a root-finding problem (F(x) = 0) into a minimization problem by defining a potential like g(x) = (F(x))^2. You can do gradient descent on g. So in that sense, both of these problems reduce to each other, though there are better methods for solving F(x) = 0 than minimizing g. I still don't understand this sense of optimization being easier than root finding. What I do understand is some sense in which there are more vector fields than there are gradients, since only some vector fields are gradients of potential functions. My comment was intended to point that out, since I thought that is maybe what you meant.
- dataflow 5y ago
  I think I explained it poorly. I used "gradient descent" colloquially there, I just meant following the 'flow' in your vector field like you might in actual gradient descent. (Yes in this case it'd be Euler's method, and you can add whatever bells and whistles you would add for GD like to choose step sizes and whatnot.) I'm saying you might still be able to find the zero of your function by doing that. That neither implies that Newton's method would have performed better on your problem (it may perform better, or it may not), nor does it imply that your vector field must have been a gradient of anything. Right? Whereas you're saying "given that you're doing Newton's method, I don't think one problem is easier than the other, right?" as if Newton is somehow guaranteed to give equally good if not better results than e.g. Euler when your vector field isn't a gradient... which I don't believe it is? Certainly there are cases when that happens but it's not implied, right?