I've implemented my own gradient descent algorithm for an OLS, code below. It work's, however, when the learning rate is too large (i.e. learn_rate >= .3), my approach is unstable. The coefficient's explode and I get an overflow error. I understand that if my learning rate is too large, I get bad results. The algorithm will take too big of steps and continuously miss the optimia. However, given that the OLS loss function is a convex optimization problem, I'm surprised that the a large learning rate would cause explosive coefficient estimates. Any insight would be greatly appreciated (as well as coding suggestions, though I know this is not the right place for that kind of talk)
import pandas as pd
import numpy as np
y1 = np.array([0, 1, 2])
X1 = np.array([[0, 0], [1, 1], [2, 2]])
def gradient_descent(LHS, RHS, N, learn_rate, tol, params, max_iter):
#Append intercept
constant = np.ones((N, 1))
RHS = np.hstack((constant, RHS))
#Define Gradient - Using Matrix Notation
def gradient(X, y, p):
grad_part1 = -2*np.dot(np.transpose(X),y)
grad_part2 = 2*np.dot(np.dot(np.transpose(X), X), p)
return((1/len(y))*(grad_part1 + grad_part2))
#Define Gradient update
def param_update(p,lr,X,y):
return(p - lr*gradient(X, y, p))
#Check if we start at optimia
old_params = params
params = param_update(params, learn_rate, RHS, LHS)
if all(abs(params - old_params) <= tol):
return(params)
#If not, run gradient descent
else:
iter = 1
while(any(abs(params - old_params)) > tol and iter < max_iter):
old_params = params
params = param_update(params, learn_rate, RHS, LHS)
iter += 1
return([params, iter])
LHS = y1.reshape(len(y1),1)
RHS = X1
myres = gradient_descent(LHS, RHS, len(LHS), .1, .1, np.array([[1], [1], [1]]), 10000)
myres = gradient_descent(LHS, RHS, len(LHS), .3, .1, np.array([[1], [1], [1]]), 10000)