If you are interested in this kind of thing, there are a whole host of "derivative free" optimization methods out there. One I've seen used in particular at a previous job, the Nelder-Mead (downhill simplex) method, always struck me as pretty elegant and intuitive once you've seen it explained. https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method)
But with scipy you have to offload to the cpu which is not always great. Tensorflow 1.0 had a complicated scipy loop integrated which caused that the scaling of gpu's was near impossible with tf.
Nelder Mead is sometimes effective, and it is pretty to visualize, but it gets stuck in some trivial cases. It can fail to find the bottom of a low dimensional parabola, for instance. CMA-ES is worth looking at, and has a similar idea but a more robust algorithm. It's basically a cloud of points with some momentum:
From what i remember, they are "trust region" methods, which work by trying to fit a quadratic function to the local neighbourhood, then analytically finding the minimum of that. The clever stuff is in how you form and update the trust region efficiently.
Both Powell's and Nelder-mead are often the only thing I can get to work when the optimization is of a quantity derived from integrating a system of differential equations. Not sure why that is.
I would add Bayesian Optimization as a very strong member of family of derivative free algorithms. It assumes a black-box function, which also can be noisy (not all derivative-free algorithms can work well with noise). One of my favorite categories of algorithms. And its a fairly active area of research today, for applications in hyperparameter tuning.
I've seen this before; it was called "over-relaxing the step", I think. The idea is that even if a step is too big, we can still show that the step was in the right direction. That's the same as the author's technique of taking multiple normal-sized steps in a single direction.
I don't know the name for the other part of the author's technique, where several Newton-Raphson steps are taken, but I've seen it before, too. Crucially, the author takes ratios of first and second derivatives, rather than of the original function and first derivative, which is the right thing to do for minimization but is going to be perhaps more expensive than the original gradient computation.
For the first section, where he uses a Hessian and finds he really only needs one step for linear regression -- isn't he basically doing a newton method, and it works more or less perfectly b/c with the normal squared error term (L2 norm) his problem is exactly quadratic? I haven't unpacked his math carefully but I think (quasi)newton methods are often worth a look if (a) your dimension is small enough that the the D^2 hessian is ok, and (b) your data is small enough that you can afford to us exact derivatives rather than mini-batch estimates.
Actually there is no need for gradient decent at all if you have a linear regression problem, because you can find the min/max exactly by inverting your weight-matrix (pseudo-inverse if degenerate). Additionally, second order optimisation, i.e. using the Hessian in addition to the gradient is a well studied problem in the literature. My understanding is that it is in general not worth it because calculating the Hessian is very expensive (see e.g. https://arxiv.org/abs/2002.09018).
One important example is large, sparse systems/matrices. The pseudo-inverse requires computing an inversion that can be very expensive due to the size of the matrix. That matrix generally will also no longer be sparse, so it will be expensive to store and work with.
The author of this post has rediscovered some fundamental ideas in optimization just by tinkering around! Neat!
> The objective function for linear regression is quadratic (and convex). This explains why Newton's method finds the optimum in one step--the local quadratic approximation turns out to be a global approximation!
> Notice, however, that Newton's method requires us to invert the Hessian matrix (f''), which is expensive in general. I don't think autograd software can get around this limitation.
> The KeepStepping optimizer is performing "gradient descent with line search", which is a more Googleable term.
For more about optimization for solving linear systems (as is the case for linear regression), I recommend Shewchuk 1994, "Conjugate Gradient without the Agonizing Pain" [1], which has some nice geometric insight.
Yeah I remember being told that quasi-Newton methods can get close to the final answer in just one step in my undergraduate statistics class.
But what works for traditional statistics (like matrix inversion) tends to have the wrong big-O for big data. Would be nice though if there were a website somewhere that summarized the state of the ML-applicable optimization field with links to papers in order of increasing complexity. Instead there are like a billion websites rehashing basic SGD that seem to dominate search results.
Although I guess most of the easy to use methods like Adam are already baked into all the frameworks.
Just like you say, I've also recently found it much harder to google for survey articles too. I know they do exist somewhere, but I can't seem to find the magic words I need to enter into the search bar!
We seem to be returning to a world where the only reliable way to find information is to stumble upon someone's webpage (e.g. [1]) who has curated a list of links.
Awesome! I have always been looking for a book like this. Thanks for sharing. A quick look at the book tells me that this is a handbook of different optimization techniques that can be used under different conditions. Do you know if there's a python/matlab version of the examples mentioned in the book?
>The author of this post has rediscovered some fundamental ideas in optimization just by tinkering around! Neat!
I checked the guy’s LinkedIn, he has 5 years of econometrics and data science education. I am honestly perplexed how anything in this article could come off as new to someone with such background.
Seems to be the case here. Regardless of the author's educational background, kudos to them for continuing to dive deeper into the math. After a math degree and three years of graduate school, I still run into blind spots almost every day, for topics that people across the hall from me would consider elementary.
A lot of adaptive GD algos work by kind of approximating the inverse Hessian, which is usually too expensive to solve at every step. Adagrad (my go-to) essentially finds a diagonal approximation to the Hessian, which often works well in practice.
There's fancier techniques to take low-rank approximations and that sort of thing, but I feel like they're usually more trouble than their worth.
The author rediscovered Newton's method. Next in line is the realisation that Hessian can be approximated and we will see the rediscovery of BFGS, L-BFGS, etc.
I somehow find it more worrisome that someone who works as a "resarch advocate" and previously a "data scientist" thinks he's had novel insight into optimization over the weekend than that a medical doctor can't recognize that he's rediscovered basic numerical integration.
"The total area under a curve is computed by dividing the area under the curve between two designated values on the X-axis (abscissas) into small segments (rectangles and triangles) whose areas can be accurately calculated from their respective geometrical formulas."
I think it kinda cuts both ways, and people filled with self-doubt will undermine their own learning. When I was young, like 10-12, I basically independently discovered Scheme on paper, from boredom. I know I also independently discovered integration, it's just that my experience with other things that have names in maths told me that what I'd discovered was too obvious to have a name; so I didn't know anyone thought it was a big deal until much later.
That is not a complete summary of the technique, though. The key insight here isn't the integration method used. Rather it is applying integration (whatever method used) until the loss increases, then starting from scratch.
It's like saying that Maxwell's equations "are just general relativity."
You can apply calculus to estimate the stepsize you need for the current iteration. If you do this in a principled way then my results suggests that for linear regression you may only need one gradient calculation.
Yes, it's called Linear Least Squares. Gauss discovered it in 1795.
It's newtons method that he rediscovers. Are people not taught numerical methods these days? We learned it quite early in the much more general context of finding zeros.
Doesn't the Hessian take O(N²) space in the number of independent variables? Like, if you have one dependent variable and a million independent variables, isn't the Hessian a trillion-element matrix, albeit a symmetric one?
Also techniques that only require the product of the hessian with some arbitrary vector, which itself is just a vector. That can be easy to compute in some problems.
If you reduce a matrix to its Cholesky decomposition you can save about half the space because you only need to store the diagonal and lower triangle. IIRC the gradients are also relatively tame for Cholesky-matrices vs their full counterparts.
> If you reduce a matrix to its Cholesky decomposition you can save about half the space because you only need to store the diagonal and lower triangle.
That's not a space savings for a known-symmetric matrix, though, for which you already need only store the diagonal and lower triangle.
As many have pointed out, this rediscovers Newton's method. The reason that this type of approach with a "hessian pre-conditioning" is not widely used in practice is that computing the hessian is costly. Avoiding that additional computation is the idea underlying "quasi-Newton" methods like BFGS and (more loosely) popular methods like Adagrad.
This is what you want for step length in a line search for most smooth continuous unconstrained optimizations. Really a lot more important than I had expected. The post is about LLS, which is a special case.
Many comment here are about the first section (which is indeed rediscovering the basis of optimisation) but I find the second section much more interesting.
He notes that computing the gradient is much more expensive than doing a single evaluation and that the gradient tend to stay in the same overall direction. Thus he proposes to compute the gradient only a fraction of the time and to use normal evaluations in the meantime.
Following an old gradient and only updating it when it becomes clearly obsolete seems like an interesting idea to me.
That is the basic premise of Policy Gradients for multi-agent models. Each agent is assigned one gradient, which they train on until end. This replaces the updating of gradients in distributed systems; and policies seem to work well for Reinforcement Learning.
Let's say I have a hyperparameter optimization task where I have to tune a simulation to some spec by varying 2-4 input parameters, and the output is a single number. I have no analytical gradient, though it's probably OK to assume the domain is smooth. Each sim takes hours to run, the entire search could take days, and I would like something that works well in parallel so I can speed up the search. What's the state of art here? Are there anything close-to-state-of-art that's useable out of the box? I've read a few papers but they don't tend to come with software.
I think Bayesian Optimization is what you're looking for here. There's an internal tool at google ("Vizier") for which a white paper has been published that solves this exact problem. I don't know if there are any public implementations of Vizier but you could probably reverse engineer some of it from the white paper: https://static.googleusercontent.com/media/research.google.c...
Powell's method (actually methods, with different solvers depending on details such as whether you have constraints) is very old and implemented practically everywhere.
Read it hoping the topic was going to be sub-gradient optimization (or any kind of technique that follows an "interesting" direction when the gradient is either not available or "boring").
51 comments
[ 2.8 ms ] story [ 90.4 ms ] threadhttps://en.wikipedia.org/wiki/CMA-ES
https://en.wikipedia.org/wiki/PDFO
From what i remember, they are "trust region" methods, which work by trying to fit a quadratic function to the local neighbourhood, then analytically finding the minimum of that. The clever stuff is in how you form and update the trust region efficiently.
I don't know the name for the other part of the author's technique, where several Newton-Raphson steps are taken, but I've seen it before, too. Crucially, the author takes ratios of first and second derivatives, rather than of the original function and first derivative, which is the right thing to do for minimization but is going to be perhaps more expensive than the original gradient computation.
https://en.m.wikipedia.org/wiki/Gram–Schmidt_process
> The objective function for linear regression is quadratic (and convex). This explains why Newton's method finds the optimum in one step--the local quadratic approximation turns out to be a global approximation!
> Notice, however, that Newton's method requires us to invert the Hessian matrix (f''), which is expensive in general. I don't think autograd software can get around this limitation.
> The KeepStepping optimizer is performing "gradient descent with line search", which is a more Googleable term.
For more about optimization for solving linear systems (as is the case for linear regression), I recommend Shewchuk 1994, "Conjugate Gradient without the Agonizing Pain" [1], which has some nice geometric insight.
[1]: http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradi...
But what works for traditional statistics (like matrix inversion) tends to have the wrong big-O for big data. Would be nice though if there were a website somewhere that summarized the state of the ML-applicable optimization field with links to papers in order of increasing complexity. Instead there are like a billion websites rehashing basic SGD that seem to dominate search results.
Although I guess most of the easy to use methods like Adam are already baked into all the frameworks.
We seem to be returning to a world where the only reliable way to find information is to stumble upon someone's webpage (e.g. [1]) who has curated a list of links.
[1]: http://www.math.columbia.edu/~khovanov/resources/
[1] https://mitpress.mit.edu/books/algorithms-optimization
[1] https://www.cvxpy.org/
[2] https://docs.scipy.org/doc/scipy/reference/tutorial/optimize...
[3] https://www.mathworks.com/products/optimization.html
I checked the guy’s LinkedIn, he has 5 years of econometrics and data science education. I am honestly perplexed how anything in this article could come off as new to someone with such background.
There's fancier techniques to take low-rank approximations and that sort of thing, but I feel like they're usually more trouble than their worth.
I somehow find it more worrisome that someone who works as a "resarch advocate" and previously a "data scientist" thinks he's had novel insight into optimization over the weekend than that a medical doctor can't recognize that he's rediscovered basic numerical integration.
"The total area under a curve is computed by dividing the area under the curve between two designated values on the X-axis (abscissas) into small segments (rectangles and triangles) whose areas can be accurately calculated from their respective geometrical formulas."
It's like saying that Maxwell's equations "are just general relativity."
Yes, it's called Linear Least Squares. Gauss discovered it in 1795.
https://en.wikipedia.org/wiki/Limited-memory_BFGS
That's not a space savings for a known-symmetric matrix, though, for which you already need only store the diagonal and lower triangle.
This is what you want for step length in a line search for most smooth continuous unconstrained optimizations. Really a lot more important than I had expected. The post is about LLS, which is a special case.
He notes that computing the gradient is much more expensive than doing a single evaluation and that the gradient tend to stay in the same overall direction. Thus he proposes to compute the gradient only a fraction of the time and to use normal evaluations in the meantime.
Following an old gradient and only updating it when it becomes clearly obsolete seems like an interesting idea to me.
This sounds exactly like a linesearch https://en.m.wikipedia.org/wiki/Line_search
It's unfortunately not presenting anything new.