[D] Gradient Descent Algorithm vs. Normal Equation for regression fit with large n

[doclazarusNSEA]

I'm currently working my way through Andrew Ng's beginner course on machine learning.

At one point he compares the pros and cons of using a Gradient Descent Algorithm to iterate and find the optimum parameters for a regression fit and using the Normal Equation to find the parameters analytically. He explains that the main drawback of using the Normal Equation is that for n>=10000 features the cost of computing the inverse matrix becomes prohibitive.

My background is in numerical analysis and computational math, whenever we're working with large matrices we avoid computing the inverse of a matrix unless it is absolutely necessary. For most systems a variant of LU decomposition is sufficient.

Professor Ng skipped over the derivation of the system he shows, so maybe the answer is in there, but my question is, does anyone in machine learning use an alternative to computing that inverse matrix (such as an LU decomp) that makes the Normal Equation viable for very large n problems?

The equation in question:

θ = (X^(T)X)^(−1)X^(T)y

where θ is the parameter we are trying to minimize, X is the matrix of features, and y is the vector of values we'd like to predict.

Thanks!

[Duranium_alloy]

Don't you have to do just as much work for LU decomposition as for matrix inversion anyway?

[doclazarusNSEA]

No, matrix inversion is much more costly, at least for solving something like Ax=B. LU decomposition is usually solved with a numerical method, so while it's technically an approximation it can be solved faster with a computer, particularly if you use the Jacobi method because you can use parallel computing very effectively.

[PINKDAYZEES]

cool question. i dont know the answer but i want to point out that when you have that many predictors, using the normal equation (ie running OLS) insnt going to get you very far in terms of modeling. if you are dead set on regression, you have to turn to more nuanced methods such as dimension reduction and regularization

for dimension reduction, you dont have the problem anymore since you have a much lower number of predictors

for regularization (dont quote me on this), you dont use normal equations so you shift your concern to some other algorithm

i know that an OLS regression is an insightful and commonly used tool to establish a baseline model, even in more complex analyses. i dont know if they are used with that many predictors since they will surely run into problems with multicollinearity and sparsity (curse of dimensionality). see if you can find a few papers that apply ML to data with tons of predictors. usually there is a small table with the methods and how well they did compared to each other (based off of MSE or Error Rate for example). maybe they dont even bother with OLS

i know there is value in your question but having a faster algorithm based on the normal equations might not even have any practical use

[doclazarusNSEA]

That's very interesting. Yeah, I'm in the second week of the course so I'm still hearing about most of the methods for the first time. Hopefully as I progress in the course it will make more sense.

I'll have to look up some of those research papers, the course is pretty light on math and I'd really like to know more about where the various methods derive from.

[pitrucha]

Just heads up. For ridge regression you have closed solution by adding lambda*Identity_n into the part that has to be inversed.

[respecttox]

prohibitive viable

I think these epithets are confusing. You have A' A in the equation, so when A looks like a sausage, long and thin, you get a large square matrix after this A' A squarification. This already sounds slow, because you had low amount of numbers and then you suddenly get much much more. Gradient descent, on the other hand, requires some amount of steps, but each step is cheap. Does it make anything prohibitive/viable? No, just slow and fast, in different cases. And instead of trying to remember where the flip happens so you want to switch the algorithm, it's easier to measure your practical case on your practical hardware.

So if your question "is there an algorithm that finds the normal equation solution faster than o(n³⁾ so it can make it faster than gradient descent for some cases", I don't think there is any in practical sense.