# 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 '15 at 18:04
• stats.stackexchange.com/questions/160179/… – Mark L. Stone Sep 18 '15 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 '15 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. – Mark L. Stone Sep 18 '15 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. – Mark L. Stone Sep 18 '15 at 21:33

• 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. – Cliff AB Sep 18 '15 at 18:43
• 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. – Cliff AB Sep 18 '15 at 19:01
• $\mathbf{X}^{\rm T}\mathbf{X}$ needs to be numerically of full rank, not full rank in infinite precision. – Mark L. Stone Sep 18 '15 at 19:11