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?

  • 3
    $\begingroup$ 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. $\endgroup$ – John Sep 18 '15 at 18:04
  • 4
    $\begingroup$ stats.stackexchange.com/questions/160179/… $\endgroup$ – Mark L. Stone Sep 18 '15 at 18:05
  • $\begingroup$ @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. $\endgroup$ – jeff Sep 18 '15 at 18:07
  • 2
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Sep 18 '15 at 18:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Sep 18 '15 at 21:33


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

  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Sep 18 '15 at 18:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Cliff AB Sep 18 '15 at 18:43
  • 2
    $\begingroup$ Please advice me which of the zero available computers having infinite precision floating point arithmetic you will be using. $\endgroup$ – Mark L. Stone Sep 18 '15 at 18:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Cliff AB Sep 18 '15 at 19:01
  • 1
    $\begingroup$ $\mathbf{X}^{\rm T}\mathbf{X}$ needs to be numerically of full rank, not full rank in infinite precision. $\endgroup$ – Mark L. Stone Sep 18 '15 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.