# Can gradient descent find a better solution than least squares regression?

Suppose I want to regress from an N-dimensional space to a 1-dimensional variable. I know that we can calculate the regression matrix with $\beta = (\mathbf{X}^{\rm T}\mathbf{X})^{-1} \mathbf{X}^{\rm T}\mathbf{y}$ , and another alternative is optimizing $\beta$ in the N-dimensional parameter space with a grid-search, or a gradient descent method.

My question is, (for the linear case), the least-squares method solves for the best $\beta$ analytically, so gradient descent cannot find a "better" solution, right?

P.S. : "Better" will be defined with the same performance measure, i.e. sum of the squares of the errors.

Moreover, for non-linear regression (like quadratic, polynomial, or in another kernel space like Gaussian), we can always represent the data matrix $X$ with the related features, so we can again compute a linear regression in this kernel space, right?

So given that we do not have a very big dataset (i.e. matrix inversion is not a problem in terms of computational cost), does gradient descent have any advantage to the least-squares solution in terms of accuracy?

One detail I can think of is finding a solution that has less error, but that indicates overfitting. Currently I don't care for that. So even an over-fitted one, can gradient descent find a "better" (see above) solution than least-squares?

• I think the key is choosing the right objective function. For a particular objective function, least squares is the optimal solution. Choose a different objective function and you might get coefficients that are more robust. Alternately, you could use the same objective, but put constraints on the coefficients, like an L1 norm.
– John
Sep 18, 2015 at 18:04
• stats.stackexchange.com/questions/160179/… Sep 18, 2015 at 18:05
• @John thanks for your answer. Can you give some more detail about the constraints? Do you mean the L1 norm of $\beta$ should be lower than a threshold? And what about the objective functions? I cannot think of any objective function other than the sum of errors' squares. Mark; I'm also coming from Andrew Ng's course :) That thread answers my question for the linear case. But what about non-linear regression? I still cannot see how it can be better than LS when we represent the same problem with the features from non-linear spaces.
– jeff
Sep 18, 2015 at 18:07
• Least absolute error most assuredly does NOT require gradient decent. Least absolute error of a linearly parameterized problem can be solved as a Linear Programming problem, using mature, efficient, reliable Linear Programming software/algorithms. Sep 18, 2015 at 18:37
• You can not convert any nonlinear regression problem into a linear one. Some nonlinear models can be converted to linear, such as by taking log of both sides of y = aexp(bx), but if so, the error distribution is transformed, so they are not equivalent. Other nonlinear models can not be transformed to linear. Sep 18, 2015 at 21:33

No.

These two methods both solve the same problem: minimizing the sum of squares error. One method is much faster than the other, but they are both arriving at the same answer.

This would be akin to asking "which gives a better answer to 10/4: long division or a calculator?"

• Those are two of the worst and most unreliable methods to solve a least squares problem. They may both get it wrong, especially for ill-conditioned problems. Sep 18, 2015 at 18:34
• I agree that gradient descent is a bad algorithm to use. I'm not sure that I agree that $\hat \beta = (X^T X)^{-1} X Y$ is a bad solution. But I believe you are implying that I computed $(X^T X)^{-1}X Y$ in an unstable way. I (intentionally) never specified how to approximate this solution. If that value was computed exactly (of course assuming $(X^T X)^{-1}$ exists...), this would be the solution. Sep 18, 2015 at 18:43
• Please advice me which of the zero available computers having infinite precision floating point arithmetic you will be using. Sep 18, 2015 at 18:45
• My point is that if $X^T X$ is full rank, the OLS solution is $(X^T X)^{-1} X^T Y$. Any approximation of the OLS solution is then an approximation of $(X^T X)^{-1} X^T Y$. Of course, some approximations are better than others, but at no point have I said what the best approximation to use is. Sep 18, 2015 at 19:01
• $\mathbf{X}^{\rm T}\mathbf{X}$ needs to be numerically of full rank, not full rank in infinite precision. Sep 18, 2015 at 19:11

OLS solves for BLUE (best linear unbiased estimator) only when all Gauss-Markov assumptions are met. You need a linear model, independence, identical distribution, exogeneity, and homoscedasticity. In scenarios, without linearity, we can still solve for a local minimum using gradient descent. Preferably, stochastic gradient descent with momentum. In terms of finding better solutions than OLS, the answer is do you want to find OLS? If the OLS assumptions are not met then you might need to perform weighted OLS, GLS, Lasso regression, or ridge regression. The model you chose depends on which assumptions your violate and how.