2
$\begingroup$

I cannot wrap my head around this simple concept.

Suppose we have a linear regression, and there is a single parameter theta to be optimized (for simplicity purposes):

$h(x) = \theta \cdot x$

The error cost function could be defined as $J(\theta) = \frac1m \cdot \sum (h(x) - y(x)) ^ 2$, for each $x$.

Then, theta would be updated as:

$\theta = \theta - \alpha\cdot \frac1m \cdot \sum (h(x) - y(x)) \cdot x$, for each $x$.

From my understanding the multiplier after the alpha term is the derivative of the error cost function $J$. This term tells us the direction to head in, in order to arrive at the minimum making a small step at a time. I understand the concept of "hill climbing" correctly, at least I think.

Here is where I don't seem to wrap my head around:

If the form of the error function is known (like in our case: we could visually plot the function if we take enough values of theta and plug them in the model), why can't we take the first derivative and set it to zero (partial derivative if the function has multiple thetas). This way we would have all the minimums of the function. Then with the second derivative, we could determine whether it's a min or a max.

I've seen this done in calculus for simple functions like $y = x^2 + 5x + 2$ (may years ago, maybe I am wrong), so what is stopping us from doing the same thing here?

Sorry for asking such a silly question.

Thank you.

$\endgroup$
2
$\begingroup$

Consider differentiating this $$\nabla_\theta\|X\theta -y\|^2=2X^T(X\theta -y)=0$$

Hence solving this, would give us $$X^TX\theta =X^Ty$$

Solving this would give us the optimal solution theoretically. However, numerical stability is an issue and also don't forget computational complexity. The complexity to solve a linear system is cubic.

Also, sometimes, we do not even know even have a closed form, a gradient based approach can be more applicable.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you for replying. However, I am not that mathematically literate to understand your answer. Is there a simpler answer? $\endgroup$ – zafirzarya Mar 17 '19 at 10:53
  • $\begingroup$ I found an answer in MSE to illustrate why computing $X^TX$ is bad. Most approaches that aim at directly solving the normal equation is more expensive than a gradient based approach. Also such gradient based approach have been adapted to a sampling based approach as well known as stochastic gradient descent that can handle very big data. $\endgroup$ – Siong Thye Goh Mar 17 '19 at 11:15

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.