11 ms·
Regularized Newton Method with Global $O(1/k^2)$ Convergence
- cheypen 5y agoThe talk given by the author https://www.youtube.com/watch?v=0lXvUMfafBY https://www.youtube.com/watch?v=0lXvUMfafBY is also quite good.
- jmount 5y agoFor those interested, James Renegar also had some great stuff on Newton's method ("A polynomial-time algorithm, based on Newton's method, for linear programming" 1988). It seems there are a lot of great algorithmic opportunities in specializing Newton's method to a given problem domain.
- redwood 5y agoCan someone explain? https://en.m.wikipedia.org/wiki/Newton%27s_method https://en.m.wikipedia.org/wiki/Newton%27s_method
- djmips 5y agoAn fun visual explanation of Newton's Method is contained within this video by 3Blue1Brown https://youtu.be/-RdOwhmqP5s https://youtu.be/-RdOwhmqP5s
- mijoharas 5y agoWould 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 agoThe 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 agoUnless 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 agoTheir 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 agoImportant 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 agoActually, 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.
- deleted 5y ago[deleted]
- rwilson4 5y agoHaven'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 agoThis is great for Big-O notation https://www.bigocheatsheet.com https://www.bigocheatsheet.com
- deleted 5y ago[deleted]
- mvanaltvorst 5y agoNewton'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 agoTo 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 agoSo isn't the magic here convexity? Convexity is such a huge constraint that I would guess convergence would be hard to avoid.
- jleahy 5y agoTell that to Newton’s method, which can fail to converge for convex functions.
- kergonath 5y agoThere 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 agoIt'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 agoYou're correct, I should've used F there, my bad. Too late to edit, unfortunately!
- deleted 5y ago[deleted]
- dataflow 5y ago
- kiengcan9999 5y agoThere 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 agoThis 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 :)
- jejones3141 5y agoTake 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 agoOther 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.
- kubb 5y agoIs it a groundbreaking better way to approximate continuous functions, or is it fundamentally impractical, like new algorithms with a good asymptotic time often are? I'm curious to know, but my mathematical illiteracy prevents me from reading the paper.
- kiengcan9999 5y agoFrom abstract: "Our method is the first variant of Newton’s method that has both cheap iterations and provably fast global convergence". It seems interesting.
- rwilson4 5y ago"Cheap iterations" led me to expect a 1st order method, not requiring computing the matrix of 2nd derivatives, which is the bottleneck in large systems. But this does indeed rely on the Hessian, so I'm not sure what makes the iterations "cheap".
- MauranKilom 5y agoIf you don't want to compute the Hessian, you're at the wrong address with Newton's method. Quasi-Newton methods is where you want to look.
- rwilson4 5y agoSure, or Nesterov's accelerated gradient descent or something. I'm just not sure what the authors mean by "cheap iterations". Update: your other comment clarified this for me. It's cheap relative to other methods that work with non-self-concordant objectives.
- rwilson4 5y agoThis is an approach for solving convex optimization problems. An optimization problem is when you want to find the best option, or the fastest, or the most profitable. If you're asking questions with superlatives (most, best, fastest), you may be working on an optimization problem. 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.
- drstrangevibes 5y agoCould this be applied to gradient descent in neural networks?
- nitred 5y agoI'll just wait for a few months for this algorithm to show up in `scipy.optimize` [1] [1] https://docs.scipy.org/doc/scipy/reference/optimize.html# https://docs.scipy.org/doc/scipy/reference/optimize.html#
- random314 5y agoThis applies to convex optimization. I am wondering if it could also be extended to neural networks too?
- rwilson4 5y agoTheoretically yes, but: typically with neural networks, and esp. deep networks with millions or billions of parameters, 2nd order methods which require calculating and factoring the matrix of 2nd derivatives are prohibitively expensive. 1st order methods such as gradient descent skip this, albeit with a tradeoff in convergence. The method proposed in this paper is impractical for large systems such as computer vision or language models.
- kxyvr 5y agoAs a note, 2nd order methods do not require calculating the entire Hessian nor do they require factorizing the matrix. A trust-region method using Steihaug-Toint (truncated) CG or a Newton-Krylov method simply require Hessian-vector products, which are not particularly costly to compute. In fact, a forward-mode automatic differentiation (AD) method on an existing gradient calculation, which could also be done using AD, will calculate the Hessian-vector product at a cost of twice the gradient calculation. Though, AD is not required and this can be done by hand. Even if only a single Krylov iteration is done, there are many benefits to using this methodology to help handle the scaling of the problem. These algorithms are described fully in a book such as Numerical Optimization by Nocedal and Wright. 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.
- marcodiego 5y ago> We present a Newton-type method that converges fast from any initialization and for arbitrary convex objectives with Lipschitz Hessians. We achieve this by merging the ideas of cubic regularization with a certain adaptive Levenberg--Marquardt penalty. I feel insignificant just by reading the first phrase.
- brrrrrm 5y agoNewton method: find an error and attempt to fix it by approximation 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
- robbedpeter 5y agoIt's funny how many complex ideas are "just" simpler ideas mapped to the right sequence of steps. The jargon and naming conventions can obscure the idea from outsiders, but allows for brief and accurate communication. If they'd explained the idea Barney-style, they'd have needed twice as many pages. Thanks for the breakdown, it makes the paper more accessible.
- sorokod 5y agoWell a simpler idea is in way like the initial guess for Newton-Raphson. Sometimes you get convergence and sometimes you don't
- whatshisface 5y agoEvery idea in math is like that, because the rules of math are to do everything in little steps.
- tubby12345 5y agoMath is about formalizing "simple ideas" so that they can be reasoned about exactly.
- loehnsberg 5y agoI am not an expert on convex, unconstrained optimization but I frequently use these methods. I'd wait until it's peer-reviewed and published in a good journal (SIAM) before I get too excited about this one.
- civilized 5y agoThis is very interesting. It looks like the innovation is to scale the identity matrix in the L-M step formula by the square root of the norm of the gradient. Very simple and elegant, and trivial to implement. Lots of people are going to be shaking their heads wondering why they didn't think of this first. 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.
- midjji 5y agoThe problem with simple innovations in old methods, is that there is very rarely anything new under the sun, odds are good its already been done. The paper does not evaluate on any of the big standard benchmark either. The paper spends a surprising/suspicious amount of time on very basic things. "The divergence issues of Newton’s method with line search seems to be a relatively unknown fact." No its well known! 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.
- civilized 5y agoAll good points. 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.
- paulpauper 5y agoI was not aware that this was a problem in need of solving. aren't computers so fast that this is already solved form a practical standpoint. Newton's method (as well as extensions of it to vector analysis) is ancient math. I was not even aware that this is an area of ongoing interest.
- syvon 5y agoI am unsure if this precise problem needed a better solution, but even if not, this is not how math research works. Finding better solutions to random / useless problems can lead to a better solution to a problem which needs solving. The relevance of the problem is not a consideration.
- BeetleB 5y ago> aren't computers so fast that this is already solved form a practical standpoint. 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.
- owlbite 5y agoNon-linear optimization is very popular in many fields (non-linear = real world, optimization = find me the least cost/most profit/lowest energy). Nearly all scientific problems can be reformulated as an optimization problem. Training neural networks is a (stochastic) non-linear optimization problem. 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.
- rahimiali 5y agoPeople who're familiar with Newton's method might be surprised at the convergence rate. 1/k^2 is slower than the textbook rate for Newton's method with line search, which is 2^{-2^k}, basically implying convergence in a constant number of steps. The rate in this paper seems to be no faster than plain gradient descent on a strongly convex function! So why go through the trouble of the much more complicated update? 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.
- civilized 5y agoThere are two kinds of convergence proofs - the ones that get you a 1/k or 1/k^2 rate, and the ones that get you "linear" or "superlinear" convergence (which is optimization jargon for exponential/superexponential decay of the error). The latter require way too strong of assumptions to be that useful in practice, and we generally think of them as just "local" convergence theorems - i.e. the assumptions they make start to be true when you get close enough to the minimum, and the fast convergence kicks in at that point. Which is nice, but getting close enough in the first place is often 99% of the problem!
- stellalo 5y agoThis is interesting, but it’s a pity that the only experimental results do not show fast asymptotic convergence of the main and simpler algorithm proposed (Algorithm 1, the one stated in the abstract) but only for its line search variants (Algorithms 2 and 4 in the paper).
- vsskanth 5y agoWhat is y in these equations
- konstmish 5y agoHey, I’m Konstantin, the author of the paper. It’s a big surprise to see an active discussion here, it was very interesting for me to read the comments. I agree with the people saying that Newton with line search often works as it is, the point of my work is to obtain a theory that can be used later to obtain extensions to harder settings or modifications with more aggressive iterations. Only the time will tell if the method itself is useful in practice. I feel like most questions have been already answered here by the community, but I’m happy to answer any remaining questions. I also presented this work online and the recording is available on youtube, I hope you’d enjoy it: https://youtu.be/0lXvUMfafBY https://youtu.be/0lXvUMfafBY