7 ms·

Can someone explain? https://en.m.wikipedia.org/wiki/Newton%27s_method https://en.m.wikipedia.org/wiki/Newton%27s_method

djmips 5y ago
An fun visual explanation of Newton's Method is contained within this video by 3Blue1Brown https://youtu.be/-RdOwhmqP5s https://youtu.be/-RdOwhmqP5s
mijoharas 5y ago
Would you like someone to explain newton's method (Newton Raphson iteration), or the linked article? (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.)
- whinvik 5y ago
  The problem with Newton's method is that it is provably convergent but only if you are sufficiently close to the solution. That basically means that the initial condition that you chose for solving the problem is very important. What this paper seems to suggest is that their method is globally convergent and they produce the algortithm to do it, although there is some tuning that needs to be done. So in theory, with their method we will always get to a solution, no matter the initial condition we chose.
  - dahak27 5y ago
    Unless I'm mistaken (very possible), the existing cubic Newton method they discuss already has this convergence guarantee, but introduces a lot of extra expensive work at each step. The specific contribution of the paper is finding clever regularization tricks to keep this guarantee while sidestepping the extra hassle the cubic method needs
  - abeppu 5y ago
    Their abstract says that their global convergence claim is for convex objectives. So structurally, they're only talking about functions for which the whole domain is "sufficiently close to the solution" i.e. where every tangent is a global bound.
    - SpaceManNabs 5y ago
      Important to note that other variants of newton's method do not necessarily converge from any starting point on even strictly convex functions. Even in convex functions, the whole domain is not necessarily sufficiently close.
      - abeppu 5y ago
        Actually, can you expand on that? The paper makes some broad statements about how existing methods are unstable and need to have a good starting point etc. This is not my area, but in the past when I've used (quasi)newton methods, it "just worked". What are the kinds of strictly convex functions that cause this bad behavior? For "strictly convex" in my limited, low-dimensional imagination I just picture a bowl-shape. They mention failure modes, but I'd love a clear (ideally visual) example of when it goes wrong. Robust global quadratic convergence seems to be the main value proposition here, so understanding the non-global fragile non-convergence of other methods seems important.
        mijoharas 5y ago
        I believe if you select as a starting point, a point where the derivative of the function is 0, then 'classic' newton raphson will not converge (since you select the "crossing point" of this tangent line for your next iteration, and that is undefined when you have 0 gradient.) e.g. y = X^2 - 1 choose 'starting position' X = 0.
        abeppu 5y ago
        ... but then your starting point is already at the optimum. You're done in zero steps! I think for a "strictly convex" function, the (sub)derivative will _only_ be zero at the global minimum.
- deleted 5y ago
  [deleted]
rwilson4 5y ago
Haven't read the paper yet, but Boyd and Vandenberghe's book, Convex Optimization, is available for free on the authors' website and covers all the foundational material. 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.
oriettaxx 5y ago
This is great for Big-O notation https://www.bigocheatsheet.com https://www.bigocheatsheet.com
deleted 5y ago
[deleted]
mvanaltvorst 5y ago
Newton's method is an algorithm you can use to minimise/maximise/find the root of a differentiable function very quickly if you start with a reasonable guess. There are many variants on Newton's method, e.g. BFGS that does not require the hessian (/2nd order derivative) of the function. A pitfall of Newton's method is that it does not find the global minimum per se, it might just converge to a local minimum if this local minimum is "closer" to your initial guess. Some variants of Newton's method allow you to avoid this pitfall, but they are slow in practice. 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.
- MauranKilom 5y ago
  To clarify, "global" in this context refers to global convergence (as in, it won't diverge no matter the starting point), not global optima. They assume a convex function, i.e. only a single minimum. The paper is unrelated to avoiding local minima.
  - abetusk 5y ago
    So isn't the magic here convexity? Convexity is such a huge constraint that I would guess convergence would be hard to avoid.
    - jleahy 5y ago
      Tell that to Newton’s method, which can fail to converge for convex functions.
    - kergonath 5y ago
      There is no way of ensuring that you have found a global minimum if the function is not convex, or if you don’t make equivalent assumptions, in the general case (if the domain of the function is continuous, and/or infinite). 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.
MauranKilom 5y ago
(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
kiengcan9999 5y ago
There is a helpful note here: https://huynp.com/optimization/2018/11/11/Fundamental-of-Unconstrained-Optimization.html https://huynp.com/optimization/2018/11/11/Fundamental-of-Unc...
gmadsen 5y ago
[deleted]
- kergonath 5y ago
  This is a useful thing to keep in mind: https://xkcd.com/1053/ https://xkcd.com/1053/ . [edit] removed irrelevant stuff. The xkcd is great though :)
  - gmadsen 5y ago
    fair enough, and rereading my comment, it does come off that way. I was more curious what his background was, but that is not how I worded it.
    - kergonath 5y ago
      Fair enough! It’s difficult to get the tone across in writing.
jejones3141 5y ago
Take an initial guess at where f(x) = 0; call it x1. Then you generate what you hope is a better guess x2 by finding where the line through (x1, f(x1)) with slope f'(x1) hits zero. Lather, rinse, repeat. 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.
mkl 5y ago
Other people have given you mathematical explanations (it finds values of x such that f(x) = 0). If you want an intuitive geometrical understanding (of the one dimensional version, i.e. x and f(x) represent numbers not vectors) try playing with this demo I made: https://www.desmos.com/calculator/kogwanro0d https://www.desmos.com/calculator/kogwanro0d. It shows the way the method follows tangent lines to get each iteration. You can move the orange start point, adjust the function with the b and c sliders, or change the f(x) function formula to another function entirely.

djmips 5y ago

An fun visual explanation of Newton's Method is contained within this video by 3Blue1Brown https://youtu.be/-RdOwhmqP5s https://youtu.be/-RdOwhmqP5s

mijoharas 5y ago

Would you like someone to explain newton's method (Newton Raphson iteration), or the linked article? (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.)

whinvik 5y ago
The problem with Newton's method is that it is provably convergent but only if you are sufficiently close to the solution. That basically means that the initial condition that you chose for solving the problem is very important. What this paper seems to suggest is that their method is globally convergent and they produce the algortithm to do it, although there is some tuning that needs to be done. So in theory, with their method we will always get to a solution, no matter the initial condition we chose.
- dahak27 5y ago
  Unless I'm mistaken (very possible), the existing cubic Newton method they discuss already has this convergence guarantee, but introduces a lot of extra expensive work at each step. The specific contribution of the paper is finding clever regularization tricks to keep this guarantee while sidestepping the extra hassle the cubic method needs
- abeppu 5y ago
  Their abstract says that their global convergence claim is for convex objectives. So structurally, they're only talking about functions for which the whole domain is "sufficiently close to the solution" i.e. where every tangent is a global bound.
  - SpaceManNabs 5y ago
    Important to note that other variants of newton's method do not necessarily converge from any starting point on even strictly convex functions. Even in convex functions, the whole domain is not necessarily sufficiently close.
    - abeppu 5y ago
      Actually, can you expand on that? The paper makes some broad statements about how existing methods are unstable and need to have a good starting point etc. This is not my area, but in the past when I've used (quasi)newton methods, it "just worked". What are the kinds of strictly convex functions that cause this bad behavior? For "strictly convex" in my limited, low-dimensional imagination I just picture a bowl-shape. They mention failure modes, but I'd love a clear (ideally visual) example of when it goes wrong. Robust global quadratic convergence seems to be the main value proposition here, so understanding the non-global fragile non-convergence of other methods seems important.
      - mijoharas 5y ago
        I believe if you select as a starting point, a point where the derivative of the function is 0, then 'classic' newton raphson will not converge (since you select the "crossing point" of this tangent line for your next iteration, and that is undefined when you have 0 gradient.) e.g. y = X^2 - 1 choose 'starting position' X = 0.
        abeppu 5y ago
        ... but then your starting point is already at the optimum. You're done in zero steps! I think for a "strictly convex" function, the (sub)derivative will _only_ be zero at the global minimum.
deleted 5y ago
[deleted]

rwilson4 5y ago

Haven't read the paper yet, but Boyd and Vandenberghe's book, Convex Optimization, is available for free on the authors' website and covers all the foundational material. 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.

oriettaxx 5y ago

This is great for Big-O notation https://www.bigocheatsheet.com https://www.bigocheatsheet.com

deleted 5y ago

[deleted]

mvanaltvorst 5y ago

Newton's method is an algorithm you can use to minimise/maximise/find the root of a differentiable function very quickly if you start with a reasonable guess. There are many variants on Newton's method, e.g. BFGS that does not require the hessian (/2nd order derivative) of the function. A pitfall of Newton's method is that it does not find the global minimum per se, it might just converge to a local minimum if this local minimum is "closer" to your initial guess. Some variants of Newton's method allow you to avoid this pitfall, but they are slow in practice. 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.

MauranKilom 5y ago
To clarify, "global" in this context refers to global convergence (as in, it won't diverge no matter the starting point), not global optima. They assume a convex function, i.e. only a single minimum. The paper is unrelated to avoiding local minima.
- abetusk 5y ago
  So isn't the magic here convexity? Convexity is such a huge constraint that I would guess convergence would be hard to avoid.
  - jleahy 5y ago
    Tell that to Newton’s method, which can fail to converge for convex functions.
  - kergonath 5y ago
    There is no way of ensuring that you have found a global minimum if the function is not convex, or if you don’t make equivalent assumptions, in the general case (if the domain of the function is continuous, and/or infinite). 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.

MauranKilom 5y ago

(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

kiengcan9999 5y ago

There is a helpful note here: https://huynp.com/optimization/2018/11/11/Fundamental-of-Unconstrained-Optimization.html https://huynp.com/optimization/2018/11/11/Fundamental-of-Unc...

gmadsen 5y ago

[deleted]

kergonath 5y ago
This is a useful thing to keep in mind: https://xkcd.com/1053/ https://xkcd.com/1053/ . [edit] removed irrelevant stuff. The xkcd is great though :)
- gmadsen 5y ago
  fair enough, and rereading my comment, it does come off that way. I was more curious what his background was, but that is not how I worded it.
  - kergonath 5y ago
    Fair enough! It’s difficult to get the tone across in writing.

jejones3141 5y ago

Take an initial guess at where f(x) = 0; call it x1. Then you generate what you hope is a better guess x2 by finding where the line through (x1, f(x1)) with slope f'(x1) hits zero. Lather, rinse, repeat. 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.

mkl 5y ago

Other people have given you mathematical explanations (it finds values of x such that f(x) = 0). If you want an intuitive geometrical understanding (of the one dimensional version, i.e. x and f(x) represent numbers not vectors) try playing with this demo I made: https://www.desmos.com/calculator/kogwanro0d https://www.desmos.com/calculator/kogwanro0d. It shows the way the method follows tangent lines to get each iteration. You can move the orange start point, adjust the function with the b and c sliders, or change the f(x) function formula to another function entirely.