40
$\begingroup$

I was trying to learn machine learning using the Coursera material. In this lecture, Andrew Ng uses gradient descent algorithm to find the coefficients of the linear regression model that will minimize the error function (cost function).

For linear regression, do we need gradient descent? It seems I can analytically differentiate the error function and set it to zero to solve for the coefficients; is that right?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Linear models have been decently well handled since the 1700's. There are a ton of ways to handle them that don't require gradient descent (GD). There are nonlinear models where most of those methods fall flat on their face. Andrew is making you use an unfamiliar but very useful method against a very simple problem so you can debug your approach. When you are good with the method you can apply it to the stunningly nonlinear problems for which GD is the only method to get results. $\endgroup$
    – EngrStudent
    Jul 6, 2015 at 17:26
  • 12
    $\begingroup$ No, you don't have to use approaches like gradient descent (that's not the only optimization method, in any case). You can indeed analytically solve it, as you suggest; you differentiate with respect to each parameter, so you get one equation per parameter. But it's useful to solve simple problems that can be done other ways; if you know the answer already you can be sure when you're getting the right answer with gradient descent. $\endgroup$
    – Glen_b
    Jul 6, 2015 at 17:27
  • $\begingroup$ If the cost function is the usual quadratic ('distance') penalty, there is a closed form solution. However, gradient descent is generally much faster, that is why it is typically used. $\endgroup$
    – meh
    Jul 6, 2015 at 17:48
  • $\begingroup$ In addition, gradient descent can be used to find numerical solutions to problems that are analytically intractable. I would suspect that he uses gradient descent early on to get one used to it. I believe he then uses gradient descent with neural nets. Needless to say the neural net situation is more complicated. I think from a pedagogical situation, having seen them before, with linear models, gradient descent for use with neural nets seems more reasonable. $\endgroup$
    – meh
    Jul 6, 2015 at 17:51
  • 3
    $\begingroup$ Thanks for posting thet link to the Andre Ng videos I watched several. I already knew it, though not to this extreme, but it's scary to see what the vast majority of people "learning" optimization are learning, not to mention what at least some of them are learning about statistical computing. Gene Golub, THE pioneer in computing and using SVD, would be rolling over in his grave if he knew what is being taught now in his Stanford Computer Science Dept. The "funniest' video is youtube.com/watch?v=B3vseKmgi8E , which recommends and compares the 2 WORST algorithms for least squares. $\endgroup$
    – Mark L. Stone
    Jul 31, 2015 at 19:03

3 Answers 3

Reset to default
54
+50
$\begingroup$

Linear Least squares can be solved by

0) Using high quality linear least squares solver, based on either SVD or QR, as described below, for unconstrained linear least squares, or based on a version of Quadratic Programming or Conic Optimization for bound or linearly constrained least squares, as described below. Such a solver is pre-canned, heavily tested, and ready to go - use it.

1) SVD, which is the most reliable and numerically accurate method, but also takes more computing than alternatives. In MATLAB, the SVD solution of the unconstrained linear least squares problem A*X = b is pinv(A) * b, which is very accurate and reliable.

2) QR, which is fairly reliable and numerically accurate, but not as much as SVD, and is faster than SVD. In MATLAB, the QR solution of the unconstrained linear least squares problem A*X = b is A\b, which is fairly accurate and reliable, except when A is ill-conditioned, i.e., has large condition number. A\b is faster to compute than pinv(A) * b, but not as reliable or accurate.

3) Forming the Normal equations (TERRIBLE from reliability and numerical accuracy standpoint, because it squares the condition number, which is a very bad thing to do) and

3a) solving by Cholesky Factorization (not good)

3b) explicitly inverting matrix (HORRIBLE)

4) Solving as a Quadratic Programming problem or Second Order Cone problem

4a) Solve using high quality Quadratic Programming software. This is reliable and numerically accurate, but takes longer than SVD or QR. However, it is easy to add bound or general linear constraints, or linear or quadratic (two norm) penalty or regularization terms to the objective function, and still solve the problem using Quadratic Programming software.

4b) Solve as a Second Order Cone problem using high quality Conic Optimization software. Remarks are the same as for Quadratic Programming software, but you can also add bound or general linear constraints and other conic constraints or objective function terms, such as penalty or regularization terms in various norms.

5) Solve using high quality general purpose nonlinear optimization software. This may still work well, but will in general be slower than Quadratic Programming or Conic Optimization software, and maybe not quite as reliable. However, it may be possible to include not only bound and general linear constraints, but also nonlinear constraints into the least squares optimization. Also, can be used for nonlinear least squares, and if other nonlinear terms are added to the objective function.

6) Solve using lousy general purpose nonlinear optimization algorithms --> DON'T EVER DO THIS.

7) Solve using THE WORST POSSIBLE general purpose nonlinear optimization algorithm there is, i.e., gradient descent. Use this only if you want to see how bad and unreliable a solution method can be If someone tells you to use gradient descent to solve linear least squares problems

7 i) Learn about statistical computing from someone who knows something about it

7 ii) Learn optimization from someone who knows something about it.

Improve this answer
$\endgroup$
15
  • $\begingroup$ Nice post, why you think that Cholesky is not good given your system is PD though? (and not with a ridiculous condition number) BTW, I think in you want to say (or add) the notion of generalised inverse (used mostly for educational purposes obviously) either at the "SVD" or the "explicitly inverting" point. $\endgroup$
    – usεr11852
    Jul 31, 2015 at 15:40
  • 3
    $\begingroup$ BTW, it's ridiculous how frequently matrices with very high condition numbers are generated, especially by the unwashed masses (i.e., the majority of people doing linear least squares, especially given the democratization in access), who are not attuned to it. $\endgroup$
    – Mark L. Stone
    Jul 31, 2015 at 16:06
  • 1
    $\begingroup$ mldivide, i.e.. backslash, i.e., \ uses QR when m ~= n (least squares), as I stated in the 2nd sentence of my paragraph (2) above. You'd be surprised how much crap there is in MATLAB though - not just in the toolboxes, some of which are absolutely horrid, but to a lesser extent in some of the core functions as well. $\endgroup$
    – Mark L. Stone
    Jul 31, 2015 at 19:11
  • 1
    $\begingroup$ @MarkL.Stone, great answer! could you please explain a bit more on why it's not advisable to use Gradient descent for solving least square! (in my understanding it's just an iterative approach compared to the others(direction solution approaches) which you have mentioned above). Moreover, Could you also comment on the problem: "if I have n>=30,000 features for a problem, Normal equation method will be very slow since inverting n*n matrix would be terrible! on the other hand, GD would work in this case pretty! any thoughts on how SVD & QR will perform". any suggestion would be helpful. $\endgroup$
    – Anu
    Dec 28, 2018 at 5:29
  • 1
    $\begingroup$ @ anu Only use gradient descent as a last resort. and that would only be if the problem is too big to be solved by SVD or QR. Never form the Normal Equations, let alone explicitly invert a matrix to solve Normal equations, NEVER. 30,000 features doesn't sound like very many for nowadays. $\endgroup$
    – Mark L. Stone
    Dec 28, 2018 at 17:17
0
$\begingroup$

Finding coefficients of a linear model is technically the process of finding solutions to a set of Linear Equations.

For computing such solutions, a lot of optimization techniques have been developed and Gradient Descent is one of them.
Thus, Gradient Descent is not the only way to do that.

Andrew Ng uses it in the course is because it is simple to understand, without dealing with advanced Linear Algebra and Numerical Computing.

Improve this answer
$\endgroup$
5
  • $\begingroup$ While not wrong I think your answer misses the bigger picture by focusing on a non-standard case. The vast majority of linear regression models are fitted by using QR decomposition employing a closed form solution. GD -gradient decent- is used as an example to introduce more advanced methods (eg. SGD - stochastic GD). $\endgroup$
    – usεr11852
    Jul 31, 2015 at 12:59
  • $\begingroup$ Can you elaborate what is QR decomposition? $\endgroup$
    – Victor
    Jul 31, 2015 at 14:08
  • 3
    $\begingroup$ You want to solve $Ax=b$. Given $A=QR$ where $R$ is upper triangular and $Q$ is orthogonal, $ Ax=b \Rightarrow QRx=b \Leftrightarrow Rx = Q^Tb$ which can be solved by backward substitution (ie. fast) as $R$ is triangular and $Q^T Q=I$. For very large matrices (millions of entries) this can be more expensive than an iterative solver eg. SGD. As most people do not have very large matrices the QR decomposition is better. In general QR decomposition has shaped the numerical world; SIAM selected it as one of the top10 algorithms of the 20th century. $\endgroup$
    – usεr11852
    Jul 31, 2015 at 14:26
  • $\begingroup$ @usεr11852 yes ofcourse. That because, i wanted to keep the answer simple, so as to avoid concepts such as QR decompostion, remaining relevant to the domain of Ng's course level. $\endgroup$
    – Vikas Raturi
    Jul 31, 2015 at 17:03
  • 4
    $\begingroup$ QR was one of the top 10 algorithms of the 20th century. But time marches on, and even though effective algorithms for computing SVD date back to the 1960s, you have to look at the importance of the application areas. Therefore I believe SVD is the TOP algorithm of the 21st century. Quite frankly, have you ever heard of QR being used to recommend movies? No, SVD is used for that critical appiication. SVD clearly is the algorithm of choice when Twitter sends out unsolicited recommendations to conservative old geezers as to which teenage celebrities they should follow. Let's see QR do that!!! $\endgroup$
    – Mark L. Stone
    Jul 31, 2015 at 17:41
-1
$\begingroup$

Yes you can.

To solve the Ax=B problem you can use the QR or other matrix decomposition based least squares solvers. However, I tried to do it by Gradient Descent with L2 norm regularization. And I think GD is better.

The first picture is the result of numpy.nnls, orange line is ground truth, blue line is numpy.nnls result.

The second picture is the result of my gradient descent with l2 norm result.

The second result is better.

numpy.nnls result

gradient descent

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ In the second case you used regularization, so you optimized different functions, hence it tells nothing about comparing the optimization algorithms. $\endgroup$
    – Tim ♦
    Mar 4, 2022 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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