Can someone explain? https://en.m.wikipedia.org/wiki/Newton%27s_method
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)
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)|))
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.
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").
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.
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?
(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...)
> 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.
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?
Update: I've skimmed the paper and here's the gist as I understand it. The paper alleges that Newton's method can have convergence issues, even when using line search. Their approach resolves these convergence issues. It's 6am where I am which isn't great for processing this stuff, but I write a lot of custom Convex Optimization solvers, and I've never had convergence issues with Newton's method with the default line search parameters suggested by the book mentioned above, even with some bad condition numbers that throttle off-the-shelf solvers (which is why I write my own).
The paper talks about speed of convergence, which initially made me think this was a first order method, not requiring calculating the Hessian (matrix of 2nd order derivatives). For large systems this is really slow and 1st order methods speed this up by working only with the first derivatives. But that's not what this paper is: they still use the Hessian but add regularization, which presumably just improves the condition number. Reminds me of proximal algorithms but haven't explored that connection.
Update on the update: the paper addresses situations where the self-concordance assumption does not hold. TBH I didn't pay much attention in class when we went over self-concordancy and convergence, but the contribution of this paper seems to be extending convergence guarantees even to non-self-concordant systems.
This seems to be another variant that claims to find the global minimum quicker than other existing methods. I am not experienced enough to verify this claim. I am also not sure how this new algorithm performs in practice; in theory, ellipsoid methods are a lot more efficient than simplex methods for optimising convex functions, while in practice simplex methods are usually an order of magnitude faster. So take this result with a grain of salt.
If you don’t make assumptions, you would need to consider every single point of the domain, and there is an infinite number of them. The job gets easier the more assumptions you make about the continuous, differentiable, and monotonous character of the function.
Things can get ugly--say, if the derivative is zero at your guess--and if your initial guess is bad, or f is wonky (say it has several zeroes near one another) it may take a long time. But as people have said, if you have a good guess, convergence is quadratic, doubling the number of good bits each time, so for floating point square root, peek at the exponent and take half that (multiply by sqrt(2) if it's odd). log2(#mantissa bits) iterations and you're as good as it gets.
Apparently this new method avoids the nasty cases and is still fast. Cool stuff.
(I could have a go at explaining newton's method, but I don't understand the arxiv article. In simple terms newton raphson iteration is an iterative method of finding the "zeros" of a function. You do it by evaluating the derivative of a function, and iteratively following that gradient until you find the zero point.)
Even in convex functions, the whole domain is not necessarily sufficiently close.
e.g. y = X^2 - 1 choose 'starting position' X = 0.
Newton raphson is used to find where f(x) = 0, not where the derivative f'(x) = 0.
For the function given above f(x) = 0 when x = 1 and x = -1. Not when the derivative is at 0 (when x = 0).
You'd be done in 0 steps to find the minimum of the function, or the point of 0 derivative, but that's not what you're looking for with newton raphson.
The article says "Unfortunately, Newton’s method is unstable: it works only for strongly convex problems and may diverge exponentially when initialized not very close to the optimum." And I was asking for an example or description of such a case.
You'll also note there are several comments in this discussion that mention the hessian/2nd order derivatives, and these all show up because this is being used in the context of optimization by looking for f'(x) = 0.
Example from Boyd.
https://math.stackexchange.com/questions/3408436/newton-rhap...
[edit] removed irrelevant stuff. The xkcd is great though :)