4 ms·

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

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.
        mijoharas 5y ago
        > but then your starting point is already at the optimum 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.
        abeppu 5y ago
        Newton's method is _commonly_ used for function minimization by looking for the zero of the derivative, and this is entirely what the article is about. In sec 1.1 at the top of page 2, they say very clearly "In this work, we are interested in solving the unconstrained minimization problem ...". Even in the first para, they say "Newton’s method is a cornerstone of convex optimization", meaning optimization/minimization of a convex function. 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.

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.
      - mijoharas 5y ago
        > but then your starting point is already at the optimum 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.
        abeppu 5y ago
        Newton's method is _commonly_ used for function minimization by looking for the zero of the derivative, and this is entirely what the article is about. In sec 1.1 at the top of page 2, they say very clearly "In this work, we are interested in solving the unconstrained minimization problem ...". Even in the first para, they say "Newton’s method is a cornerstone of convex optimization", meaning optimization/minimization of a convex function. 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.