4 ms·
Prof Higham has quite the list of papers on the finer points of numerical algorithms going back to his MSc in 1983: http://www.ma.man.ac.uk/~higham/papers/bibb
by defrost 4y ago
Prof Higham has quite the list of papers on the finer points of numerical algorithms going back to his MSc in 1983:
http://www.ma.man.ac.uk/~higham/papers/bibbase.php http://www.ma.man.ac.uk/~higham/papers/bibbase.php
including a brief note on the comparing "Top 10 Algorithms in Applied Mathematics" between 2000 and 2016 that may interest some:
https://nhigham.com/2016/03/29/the-top-10-algorithms-in-applied-mathematics/ https://nhigham.com/2016/03/29/the-top-10-algorithms-in-appl...
It'd be nice to see some meat on the bones and a few ripping yarns about the application end of applied math techniques .. eg: forming an enhanced image from tens (or hundreds) of thousands of multichannel spectral samples using a sensitivity adjusted SVD, and then removing the most common expected background to highlight the anomalies.
It's dry stuff in Linear Algebra, somewhat more exciting when searching for nuclear weapons in a forest or gold in a desert.
- bee_rider 4y agoHe also wrote "Accuracy and Stability of Numerical Algorithms" which is part of the canon of the field.
- melony 4y agoWhy is Newton’s Method not used more often in ML? I know Newton’s method requires the 2nd derivative while Gradient Descent family of algorithms only requires the first, but shouldn’t Newton’s Method be just as straightforward when using autodifferentiation since the process is just a computational graph graph transform using a lookup table?
- phao 4y agoWith Newton's method, you'll be solving Hx=g (H = hessian of f, g = gradient of f) at each iteration. For large number of variables N, building H is of order N^2 and solving Hx = g is of order N^3 with an usual solver. N^2 and N^3 are really large for an already large N. I believe the reason is as simple as that. It isn't that it is tedious and difficult to write down the formulas or the code to compute H. It's just too costly, computationally speaking. There is also an increased memory cost (possibly having to store H). When people do have ways to go around this problem, they do use Newton's method for large scale problems.
- jmalicki 4y agoAdding to sibling post from phao, Optimizers like ADAM essentially do a diagonal approximation to Newton's method, which gives some, though certainly not all, of the benefit of Newton. There is the seminal paper "Deep Learning via Hessian-free Optimization" [1] that applies Newton's method (Hessian free because of a clever trick of solving Hx=-g iteratively without explicitly constructing the Hessian, and getting an approximation without full O(n^3)) - but n^2 or n^3 is just too large in practice when the diagonal approximations work just fine. [1] https://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.pdf https://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.p...
- newrotik 4y agoAdding to the answers already given (complexity related to the computation of full Hessians). First order methods, i.e., methods that only require gradients, are the methods of choice when extreme solution accuracy is not required, which is the case in many practical settings (including ML). One of Newton's method major selling points is that once it's close to a local minimum, under the right smoothness assumptions it essentially converges faster and faster to an exact optimizer - in practice you get "one more correct significant digit each iteration" once you are close enough. It's called Newton's method region of quadratic convergence, see [0] Theorem 14.1, p.3 [0] https://www.stat.cmu.edu/~ryantibs/convexopt-F16/scribes/newton-scribed.pdf https://www.stat.cmu.edu/~ryantibs/convexopt-F16/scribes/new...