Hacker News Reader

Comment by throwlaplace | Hacker News Reader

>normal equation is vastly superior to gradient descent in solving out the coefficients for polynomial regression

Completely depends on the size of your data set. I would not want to pseudo-invert a design matrix > 1000 samples.

You don't need to invert the matrix. You want to solve X' X Beta = X' Y for Beta. Computationally, it is faster to solve the equations one by one.

https://www.johndcook.com/blog/2010/01/19/dont-invert-that-m...

Isn’t John D Cook arguing for iterative methods there? It does not read as a defense of “using the normal equations” or direct methods. In fact, the reference to sparsity makes you think John May be referring to SGD or a similar iterative method.

Obviously, any solution you get solves the normal equation so it’s unclear what the parent comment meant by using the normal equation is superior to SGD.

Stochastic gradient descent only approximates the solution, and it may do that by looking at a single equation (or a small batch of them) at a time, without ever bothering with the whole system.

Is it approximating the gradient or approximating the solution?

If it’s the gradient, doesn’t it have the real gradient in expectation, so you can run as many iterations to get epsilon precision up to what your machine will support?

It'd be something like conjugate gradient, not sgd. Unless A itself is too big to fit in memory.

The method John d Cook is referring to is something like conjugate gradient not sgd?

I’m not too familiar with CG. What clues you in that he’s thinking more CG than SGD?

It is just "what you do". If it is a small problem the default is qr decomp of A. If you are worried about speed do a cholesky decomp of A'A. If the problem is big (usually because of a sparse A) then you do conjugate gradient (because fill in will bite with a direct method). If it is really, really big (A can't fit in memory) then it isn't clear what the "thing to do" is. It is probably "sketching" but in ML/neural network land everyone just does SGD, which you can think of as a monte carlo estimate of the gradient (A for a linear problem). Maybe sketching and SGD are equivalent (or an appemroximation). "what you do" is based on convergence and stability characteristics.

Helpful. It makes sense that CG maintains sparsity. I didn’t realize it saw use in practice.

i have no idea what he's advocating for? gaussian elimination? matrix decomposition? first doesn't work for non-square and the second is still slower than gradient descent often (in particular in the case that you don't need the exact minimum [such a in data science]).

You never invert A^T A anyway, you would do Cholesky on it and use it to solve A^T A x = A^T b. But regardless, QR on A should be the first choice.

that's a fair point. i would still use gradient descent (or conjugate gradients) if i didn't care about the exact minimum.

Reply on news.ycombinator.com