I am trying to implement a gradient descent algorithm for a simple linear function:

y(x) = x


Where initial hypothesis function is:

h(x) = 0.5 * x


and learning rate:

alpha = 0.1


Target function graph is blue and hypothesis is green.

Cost function:

J = 1/2m * sum[(h(x) - y(x)) * (h(x) - y(x))]


q = q - alpha/m * sum[(h(x) - y(x)) * x]


My implementation does not converge:

import numpy as np
import matplotlib.pyplot as plt

def y(x):
return x

def get_h(q):
""" Create hypothesis function

Args:
q - coefficient to multiply x with

Returns:
h(x) - hypothesis function
"""
return lambda x: q*x

def j(x, y, h):
"""Calculte a single value of a cost function

Args:
x - target function argument values
y - target function
h - hypothesis function

Returns:
Value of a cost function for the given hypothesis function
"""
m = len(x)
return (1/(2*m)) * np.sum( np.power( (y(x) -h(x)),2 ) )

def df(h, y, xs):
"""Calculate gradient of a cost function

Args:
h - hypothesis function
y - target function
xs - x values

Returns:
differential of a cost function for a hypothesis with given q

"""
df = np.sum((h(xs)-y(xs))*xs) / len(xs)
return df

xs = np.array(range(100))
ys = y(xs)
hs = h(xs)

costs = []
qs = []
q = 0.5
alpha = 0.1
h = get_h(0.5) # initial hypothesis function
iters = 10
for i in range(iters):
cost = j(xs,y,h)
costs.append(cost)
qs.append(q)
print("q: {} --- cost: {}".format(q,cost))
df_cost = df(h, y, xs)
q = q - alpha * df_cost  # update coefficient
h = get_h(q) # new hypothesis


What am I doing wrong? Should I account for q0 even if my target function intercept is zero?

Update / Solution

Answer from gunes is correct, the problem was with too big learning rate alpha = 0.1. Hypothesis function converges with target function even with alpha = 0.0001 and 30 iterations as opposed to alpha = 1E-5 and 100 iterations as gunes has suggested.

This updated code shows how it all works:

costs = []
df_costs = [] # cost differential values
qs = [] # cost parameters
q = 0.5 # initial coast parameter
h = get_h(0.5) # initial hypothesis function
alpha = 0.0001 # learning rate
iters = 30 # number of gradient descent itterations

_=plt.plot(xs,ys) # plot target function
for i in range(iters):
_=plt.plot(xs,h(xs)) # plot hypothesis
cost = j(xs,y,h) # current cost
costs.append(cost)
qs.append(q) # current cost function parameter
#print("q: {} --- cost: {}".format(q,cost))
df_cost = df(h, y, xs) # get differential of the cost
df_costs.append(df_cost)
#print("df_cost: ",df_cost)
q = q - alpha * df_cost  # update hypothesis parameter
h = get_h(q) # get new hypothesis

_=plt.title("Hypothesis converges with target")
_=plt.show()
_=plt.close()


_=plt.title("Costs")
_=plt.xlabel("Iterations")
_=plt.plot(range(iters), costs)
_=plt.show()
_=plt.close()


_=plt.title("Cost differentials")
_=plt.xlabel("Iterations")
_=plt.plot(range(iters), df_costs)
_=plt.show()
_=plt.close()


Your gradients and update rules are correct. It's just you're using a large learning rate for your data, because your gradients are large. Try $$\alpha=10^{-5}$$ and $$100$$ iterations. You'll see that it'll converge.
• Yeah, my $\alpha$ was just a suggestion for a small value. – gunes Aug 26 '20 at 15:14