Regularized Newton Method with Global $O(1/k^2)$ Convergence
arxiv.org
arxiv.org
Because the textbook proof of the fast convergence of Newton's method make additional assumptions on the objective function, for example that it is strongly convex, or it is self concordant. This paper only assumes Lipschitz continuous Hessians.
The idea of dampening the Hessian is old (it's sometimes called "damped newton method", or "trust region newton method", or "levenberg-marquardt", though the latter two refer to more specific ideas). This paper offers a view to how much dampening to apply.
The motivation for the idea is very nice and easy to understand. The author completely explains it before the middle of the second page. I encourage you to look at it if you know enough vector calc to make sense of the notation. Essentially, he takes a well-known fast-converging method whose steps are hard to compute and shows how these steps can be approximated cheaply while still retaining much of the convergence rate benefit.
This may have implications for many large-scale optimization problems as L-M regularized Newton steps are a sort of natural halfway house between gradient descent and the full Newton's method, both theoretically and practically.
It looks interesting, but some things, like the L-M lambda beeing constant? No, you adapt it to the data increasing and decreasing it in accordance with the feedback from the step error predictions. Similar, but not identically to what is proposed here. Id need to read it carefully and it doesnt look bad, but think I'll just wait for the reviewers.
Personally I wouldn't have known divergence of Newton's method with line search off the top of my head. What I think everyone in this field would know is that Newton's method with constant step size diverges. I'm actually curious now if Newton's method with backtracking line search from a constant step size diverges. Exact line search can go a little nuts, that doesn't surprise me, but divergence with backtracking from a constant step size seems less likely. (I guess it depends on what "constant" means here...)
Seems like it could be awfully nice to have a smart theoretically backed initial guess of the dynamic lambda. The author actually uses a feedback strategy to set H in conjunction with his gradient scaling (see Algorithm 2 / AdaN), and it's possible that the scaling allows H to be basically correct more often and not have to be adjusted so much? Which is potentially really helpful since Newton steps aren't cheap and you don't want to waste them on guess-and-check.
But it's not obvious it's better than other strategies and we do need benchmarks to prove it out, yes.
The author is from INRIA, which does a lot of advanced optimization research, so I'd say it's a serious paper prima facie.
https://doi.org/10.1137/S0036142996304796 (free version https://repository.lib.ncsu.edu/bitstream/handle/1840.4/296/...)
If I have f(x), then I define
g(x) = 100*f(x)
h(x) = .01*f(x)
Normally, the scale factor of a function cancels out when multiplying the inverse Hessian times the gradient, but the square root changes that here. This seems undesirable.
Maybe it can be hand-waved away with their constant H, which looks like a tuning parameter.
There may be stability issues with perfect scale invariance. You don't want to drop your identity matrix term when the gradient gets too small; that would defeat the purpose of the L-M regularization.
Regularization in general tends to make things less symmetric and invariant. It's kind of a necessary evil.
And you're right, the H plays an important role in keeping the scheme relatively efficient. It is typically adjusted dynamically in L-M schemes (see AdaN and AdaN+ algorithms in the paper).
I'm curious if this square root trick performs better than a well written trust region algorithm.
[1] https://docs.scipy.org/doc/scipy/reference/optimize.html#
I feel insignificant just by reading the first phrase.
Convex objective: a bowl-like function, we want inputs that put us at the bottom of it
Lipschitz: a space that isn’t too stretchy
Hessians: second partial derivatives of the terms we’re optimizing (inputs we want)
Regularization: make the “fix by approx” procedure a bit more well behaved
Levenberg–Marquardt: another adaptation to make the fix procedure better
Thanks for the breakdown, it makes the paper more accessible.
i.e. Mitochondria->PowerHouseOfTheCell
Not knowing precisely which definition you need for an application or which one you need for a proof to hold is essential for progress.
Math doesn't make up "jargon" for no reason. The names are to denote to professionals the least needed elements to make something true.
Understanding optimization at this level and being able to formulate your own problems in one of the canonical forms gives you super powers.
You don’t even have to build your own solvers. The commercial/open source ones are typically good enough.
But as a maintainer of solvespace (Open Source CAD software with geometric/algebraic constraint system) I am left wondering if this can be applied to our constraint solver, which I didn't write. It solves systems of algebraic constraints using some form of Newtons method, partial derivatives, jacobian... All stuff I'm familiar with, but not in great detail. Figuring out how best (and weather) to apply this might be a major digression ;-)
The interesting part (to me, as that is not my specialty) lies in the translation of the 3D constraints (including rotation, etc.) into a single objective function for solving Newton-style.
That's funny - I like the geometry stuff and have a good grasp of how to create useful constraint equations. I just don't know too much about the code for solving systems of those equations ;-)
For orientation we use quaternions. For other things it's an axis-angle representation. For the equal angle constraint I'm not sure how that's implemented. There was a recent addition of length-ratio between lines and arcs. That implementation was surprising to me.
I often wonder about the intentions of those who post of these types of comments. Being charitable one might suppose the parent is offering a backward sort of compliment to the authors. Something like "Great job, beyond my capabilities, I'm glad someone is working on these things".
There are a lot of less charitable formulations; why should other readers care about parent commenters insecurity? Does parent commenter not appreciate the work that goes into studying these topics? Was parent commenter told they were "smart" to often as a child and never learned to exert themselves academically? Etc.
Although this post is mostly in jest, I really am curious what prompts these comments, comments of this type are quite reliable.
You're missing the obvious interpretation -- jargonization of the sciences keeps people out and keeps the masses stupid. Math is particularly guilty of this -- more charitable fields use jargon that is at least semi-self-explanatory, words and phrases that, while jargon, do make sense if you deconstruct them. In Math, people are so arrogant that they discover something and immediately name it after themselves, so if you haven't had a topology class, you won't know that X person's name maps to Y concept. Good jargon can be pieced together with pure reason alone without knowing the names of the people who invented what. This isn't true across the board of course -- "gradient descent" is a particularly well-named piece of jargon, for example.
Not that many people wouldn’t like for the thing they introduce to eventually be named after them. But, I think it would generally be considered presumptuous to directly name it after oneself.
I remember one story where one mathematician upon hearing something referred to as a [some term named after them], asked what the term referred to. (I want to say it was Hilbert asking what a “Hilbert space” was, but I’m not sure.)
> J. von Neumann in 1927 introduced the axiomatic description of a Hilbert space, and used it in his work on quantum mechanics. There is a story of the time he came to Göttingen in 1929 to lecture on these ideas. The lecture started "A Hilbert space is a linear vector space over the complex numbers, complete in the convergence defined by an inner product (a product <a,b> of two vectors a, b) and separable". At the end of the lecture, David Hilbert (by custom sitting in the first row of the Mathematische Gesellschaft), who was then evidently thinking about his definition and not about the axiomatic description, is said to have asked, "Dr. von Neumann, ich möchte gern wissen, was ist dann eigentlich ein Hilbertscher Raum?" [Freely translated this is "Dr. von Neuman, I would very much like to know, what after all is a Hilbert space?"]
https://books.google.com/books?id=8mBdvAjk_gQC&newbks=1&newb...
I think a larger problem in reading math might be polysemy. Symbols have multiple meanings, so context has to be used to infer what meaning is intended by authors.
A working title for a manuscript I am shopping out to the various neuroscience journals right now. I feel like I'm finally the esoteric person I've always wanted to be.
I also presented this work online and the recording is available on youtube, I hope you’d enjoy it: https://youtu.be/0lXvUMfafBY
(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...
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.
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?
[edit] removed irrelevant stuff. The xkcd is great though :)
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.
The current paper does not directly affect most ML algorithms because it speaks directly to convex optimization. Most ML models are highly nonlinear, so globalization of the optimization algorithm is required. Here, globalization means something like a line-search or a trust-region to ensure convergence to a local minima. Convex problems using an appropriate algorithm and under the correct assumptions do not necessarily require the use of a globalization technique and will converge directly to a local min, which is now global due to convexity. Normally, this discussion is done in the context of interior point methods for linear cone problems and helps explain why globalization is not done for these algorithms. An example of this can be found in Convex Optimization by Boyd and Vandenberghe in section 11.5.3, but it's a well researched topic. The algorithm in this paper discusses a technique where they also don't require a typical globalization technique.
Anyway, mostly I'm commenting to dispel the misconception that 2nd order method can not be applied to large scale problems. I've applied them successfully to problems with hundreds of millions of variables and they work just fine. Largely, their success is tied to how complicated the spectrum of the Hessian is, but that's a longer discussion.
What does the "complexity" of a spectrum mean? Is this a statement about the uniqueness (or not) of the eigenvalues or something else entirely?
1. A neural network with ReLU activations (the most common one) effectively has a piecewise linear optimisation surface, so the 2nd derivative is 0 almost everywhere. No curvature, no Hessian.
2. 2nd order methods make an assumption that the optimisation surface is (close to) convex, which is very much not the case with neural networks.
3. Even if the above were not true, to measure the Hessian you would have to iterate through the entire training set to measure it before you could make take an optimisation step.
4. Representing the entire Hessian for a network with N parameters needs O(N²) space, where N is on the order of 10⁹, so you couldn't use a method that needs the whole Hessian. There are so-called Quasi-Newton methods that need O(N) space though, like L-BFGS.
Neural networks need completely different optimisation methods, and there is no practically useful application of any of the Newton or Quasi-Newton methods for their optimisation.
I don't think this is quite fair. There are several variations of 2nd order methods, notably KFAC and Shampoo, that seem to quite effective for large-scale neural network training, e.g., see the intro of this paper for an overview: https://openreview.net/forum?id=-t9LPHRYKmi
Update: your other comment clarified this for me. It's cheap relative to other methods that work with non-self-concordant objectives.
Many optimization problems are NP Hard and cannot be solved in a reasonable amount of time. Convex optimization problems are a special subclass which can typically be solved efficiently (meaning in polynomial time).
This paper provides a new approach to solving Convex Optimization problems for systems where other methods struggle.
Newton's method already has "good asymptotic time" (e.g. if you use it to compute a square root, you double the number of correct digits with each step!) - but only under certain conditions (e.g. "not too far from the solution"). This paper shows how to modify it so this sort of benefit is obtained under a wider range of conditions ("global").
There are other related methods with a similar goal, but some require more expensive computations. The method from the paper appears to fill a sweet spot in high-dimensional optimization by virtue of requiring "few" matrix inversions (or linear solves) while having very good convergence properties.
When you are dealing with the kind of problem that this sort of method is applicable to, it appears to me that you might benefit from looking into using this method. But it's not a revolutionary improvement from what I can tell - there are many related methods, and chances are you could have used something similar for similar benefit already.
And it's likely that someone already used more or less this method in practice. As the paper notes:
> Our goal is twofold. On the one hand, we are interested in designing methods that are useful for applications and can be used without any change as black-box tools. On the other hand, we hope that our theory will serve as the basis for further study of globally-convergent second-order and quasi-Newton methods with superior rates. Although many of the ideas that we discuss in this paper are not new and have been observed by practitioners to help solve challenging optimization problems, our analysis, however, is the first of its kind. We hope that our theory will lead to appearance of new methods that are motivated by the theoretical insights of our work.
I would say "interesting" more than "groundbreaking", in the sense that you will not solve problems that you were not previously solving.
The benchmarks provided show nice convergence. The interesting part is that the method will not fail, which is very good. The benchmarks seem to crush other methods but keep in mind that the plots do not show "time required" but "number of iterations required" and that with Newton's method you are doing much much more work per iteration: computing the Hessian instead of the gradient and solving a system of linear equations on every iteration.
Not in the least. Much of the scientific computation out there is to solve these types of problems. Even if you sped up computers ten-fold you wouldn't be satisfied.
When I was in grad school, the computational teams would run calculations where it would take a few days to get a single data point (they were trying to plot a curve). And they had problems in their head where it would take over a month to get a data point - but of course they weren't pursuing those problems as it was impractical.
Things like computing the derivative - let alone the Hessian - can be quite expensive for some problems.
Computers are quite fast at doing this in one variable, but typically you're in at least 10s, if not 10,000s of variables, which makes it much much harder.
In dense math, consider n=10,000. Typically a single step involves at least one system solve. Using some matrix factorization approach you're doing O(n*3) operations, assume the constant is ~1 and you have 1 TFlop of computation per step. Modern compute capability of a consumer device is about 1 TFlop/s, give or take. If you're doing (say) 300 steps to reach a solution, you're now at the 5 minute mark for a single moderately sized problem.
Admittedly things like sparse math and iterative solution approaches exist, but so do much bigger problems. And that's before we get to non-convex problems which will often use a convex solver to repeatedly solve subproblems.