Why am I not getting the correct output from my gradient descent algorithm? [closed]

I have started taking online ML classes, and i was introduced to the topic of Gradient Descent, the Prof, himself hadnt shown us himself how to implement it in a programming language, so for fun, i thought to implement it in python with what I knew. But I was getting the wrong output, and some errors, can anybody please show me what I have done wrong?

Code:

theta0=0
theta1=0
learning_rate=1;
m=84
derivative_theta0=1
derivative_theta1=1
while(derivative_theta0 !=0 and derivative_theta1!=0):
hypothesis=theta0+(theta1*x)
cost=((hypothesis-y)**2).sum()
error=(hypothesis-y)
derivative_theta0=1/m*((error).sum())
derivative_theta1=1/m*((error*x).sum())
theta0=theta0-(learning_rate*derivative_theta0)
theta1=theta1-(learning_rate*derivative_theta1)


Error:

C:\Users\vedant.sureka\Anaconda3\lib\site-packages\ipykernel_launcher.py:13: RuntimeWarning: invalid value encountered in double_scalars del sys.path[0] C:\Users\vedant.sureka\Anaconda3\lib\site-packages\ipykernel_launcher.py:14: RuntimeWarning: invalid value encountered in double_scalars

Then when i printed the value of theta0, i got output "nan".

Here is an image containing everything as well:

[![Click this to see image containing everything][1]][1]

Here is the google drive link for the data i have used: GPA is y, SAT is x. https://drive.google.com/open?id=1r62CaxRN92HpeYgH20e13v6bXJwHOGnX

• Can you post your x and y as well? I don't see a fault in your gradient descent implementation (except that the while statement can be a bit hard for floating points) Commented May 8, 2020 at 22:03
• Added, please check to see my mistake now Commented May 9, 2020 at 12:03
• Can you copy/paste as text so that I can use. It's probably because of numerical problems btw since your sat score is large. Commented May 9, 2020 at 12:07
• Actually i did copy and paste it, but stackexchange automatically converted into an image. If comfortable, you can provide me with your email, and ill mail it to you Commented May 9, 2020 at 12:52
• For reviewers who are going to review if this post is an off-topic one or not: I don't think it is because it involves checking gradient descent implementation, data normalisation and choosing a suitable convergence rate. Commented May 9, 2020 at 15:51

Ok, I've changed your code and now it converges (you don't have errors in your gradient descent code, except a scalar which doesn't matter):

x = x / 1000

tol = 1e-6
theta0=0
theta1=0
learning_rate=0.1;
m=84
derivative_theta0=1
derivative_theta1=1
while(np.abs(derivative_theta0) > tol and np.abs(derivative_theta1) > tol):
hypothesis=theta0+(theta1*x)
cost=((hypothesis-y)**2).sum()
error=(hypothesis-y)
derivative_theta0=1/m*((error).sum())
derivative_theta1=1/m*((error*x).sum())
theta0=theta0-(learning_rate*derivative_theta0)
theta1=theta1-(learning_rate*derivative_theta1)


Basically, there are three things to note:

• For convergence, you need to set a tolerance threshold and compare against it. Expecting the error to be equal to exactly $$0$$ is not practical in general. I've added this for you.

• Due to high scale in x variable, the loss surface is very oblique, and you'll have hard time while convergence. I've just divided your test scores by $$1000$$ to make it easier. Typically, you apply standardisation/normalisation to your data before inputting into your algorithm.

• And, learning rate choice is critical. I've decreased it such that it can converge. Depending on Hessian, learning rates greater than some threshold impede convergence.

• +1 for actually run and fix the code! Thanks for your contribution Commented May 9, 2020 at 16:14
• Hey Gunes! First of all, thanks for the great answer, but I still cant understand why did you use 1e-6, and not 0, my Prof. said that when the derivative=0, that is when we have the global minimum, why is it that attaining that is impossible? Commented May 10, 2020 at 10:51
• @divyamsureka it can be as small as you like, which is called the tolerance in many computational packages, but $0$ is never recommended. We're using finite precision arithmetic (i.e. 32-64 bit floating points) in computers. There is no way you can represent all real numbers in computers. This means you might never get derivative equal to $0$. For example, consider a function where the derivative is equal to $0$ only when $x=\sqrt{2}$, which requires infinite precision. Since you'll never reach that number, there will always be a difference, and your derivative may not be $0$ when rounded. Commented May 10, 2020 at 11:06