More Descent, Less Gradient | Hacker News Reader

More Descent, Less Gradient

koaning.io

129 pointscantdutchthis49 comments

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.

[1]: http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradi...

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.

[1]: http://www.math.columbia.edu/~khovanov/resources/

Another amazing resource is [1]. Seriously one of the best purchases I have ever made, and I spend a lot more on books than I should.

[1] https://mitpress.mit.edu/books/algorithms-optimization

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 book ships with Julia examples, but most of the algorithms are available in cvxpy [1], scipy.optimize [2] and matlab optimization toolboxes [3].

[1] https://www.cvxpy.org/

[2] https://docs.scipy.org/doc/scipy/reference/tutorial/optimize...

[3] https://www.mathworks.com/products/optimization.html

>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.

totally possible to learn a lot of economics and statistics and never have formal coursework in numerical methods for optimization.

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.

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.

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.

It reminds me of this story from a decade back: https://science.slashdot.org/story/10/12/06/0416250/medical-...

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.

That is hilarious.

"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.

It's a shame that it only works for glucose curves. Imagine if someone could generalize it :-)

Oh I remember this! Was hilarious!

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."

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)

https://en.wikipedia.org/wiki/Coordinate_descent - Coordinate descent is another nice one that works well for certain problems.

In Python, scipy actually supports a lot of different optimization methods, including Nelder-Mead.

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:

https://en.wikipedia.org/wiki/CMA-ES

There's a family of such methods invented by Michael Powell:

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.

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.

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.

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.

> Following an old gradient and only updating when it becomes clearly obsolete

This sounds exactly like a linesearch https://en.m.wikipedia.org/wiki/Line_search

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.

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?

There are "limited memory" algorithms which use low rank approximations.

https://en.wikipedia.org/wiki/Limited-memory_BFGS

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.

https://en.wikipedia.org/wiki/Wolfe_conditions

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.

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.

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).

It seems to me that gradient descent would be, often, a better solution than the moore-penrose inverse. Is it not more efficient in most cases?

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.

I always thought you‘d use Gram Schmitz for linear regression

https://en.m.wikipedia.org/wiki/Gram–Schmidt_process

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").

It's unfortunately not presenting anything new.

The next step to investigate here is line search.

I think that’s pretty much what he’s doing in the second part of the post

Reply on news.ycombinator.com