5 ms·

(Disclaimer: Not an expert, and only gave the paper a very cursory read). Newton's method attempts to find zeroes of a function (i.e. find x where F(x) = 0). T

(Disclaimer: Not an expert, and only gave the paper a very cursory read). Newton's method attempts to find zeroes of a function (i.e. find x where F(x) = 0). This is equivalent to finding a (possible) minimum of a function f(x) where f'(x) = F(x). Note: The wiki article describes the process of finding zeroes for F(x), whereas the article searches minima of f(x), in terms of my notation here. At a basic level, Newton's method iteratively improves a guess x_k via the following update step: x_(k+1) = x_k - f(x_k) / f'(x_k) When close to the correct solution, convergence is quadratic: You "double the number of correct digits" at every step, so to speak. But if you're far away, you might be diverging (going further away from the solution). Progress can also be slow under other conditions (multiple solutions nearby). The paper, essentially, suggest the following update step instead: x_(k+1) = x_k - f(x_k) / (f'(x_k) + sqrt(H |f(x_k)|)) for some H (that needs to be chosen/estimated). The extra term can be thought of as some form of regularization. This supposedly avoids divergence (where f is non-decreasing and does not grow too fast), and is also consistently fast. Note that I've simplified to the one-dimensional case here. There are further concerns in higher dimensions (e.g. number of matrix inversions) that this method handles well, according to the authors.

gugagore 5y ago
It's great that you clarified the root-finding / minimization perspectives. Shouldn't your update equations be written in terms of F, not f? (Alternatively, write f'(x_k) / f''(x_k).) To minimize f, find zeros of f' = F. To find a zero of F, construct a linear approximation using f''=F' If you're using Newton's method to minimize a function f, you need the first- and second-order derivatives (hence the same "second-order method").
- MauranKilom 5y ago
  You're correct, I should've used F there, my bad. Too late to edit, unfortunately!
- deleted 5y ago
  [deleted]
dataflow 5y ago
> This is equivalent to finding a (possible) minimum of a function f(x) where f'(x) = F(x). I'd like to clarify that the "equivalence" might be misleading. Just because you have a vector-valued function, that does not imply it has an antiderivative you can minimize, so merely having that scalar antiderivative actually gives the problem more structure and thus intrinsically makes it "easier" in that sense.
- gugagore 5y ago
  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.

gugagore 5y ago

It's great that you clarified the root-finding / minimization perspectives. Shouldn't your update equations be written in terms of F, not f? (Alternatively, write f'(x_k) / f''(x_k).) To minimize f, find zeros of f' = F. To find a zero of F, construct a linear approximation using f''=F' If you're using Newton's method to minimize a function f, you need the first- and second-order derivatives (hence the same "second-order method").

MauranKilom 5y ago
You're correct, I should've used F there, my bad. Too late to edit, unfortunately!
deleted 5y ago
[deleted]

dataflow 5y ago

> This is equivalent to finding a (possible) minimum of a function f(x) where f'(x) = F(x). I'd like to clarify that the "equivalence" might be misleading. Just because you have a vector-valued function, that does not imply it has an antiderivative you can minimize, so merely having that scalar antiderivative actually gives the problem more structure and thus intrinsically makes it "easier" in that sense.

gugagore 5y ago
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.