# How do I implement stochastic gradient descent correctly?

I'm trying to implement stochastic gradient descent in MATLAB however I am not seeing any convergence. Mini-batch gradient descent worked as expected so I think that the cost function and gradient steps are correct.

The two main issues I am having are:

1. Randomly shuffling the data in the training set before the for-loop
2. Selecting one example at a time

Here is my MATLAB code:

Generating Data

alpha = 0.001;
num_iters = 10;

xrange =(-10:0.1:10); % data lenght
ydata  = 5*(xrange)+30; % data with gradient 2, intercept 5

% plot(xrange,ydata); grid on;
noise  = (2*randn(1,length(xrange))); % generating noise
target = ydata + noise; % adding noise to data

f1 = figure
subplot(2,2,1);
scatter(xrange,target); grid on; hold on; % plot a scttaer
title('Linear Regression')
xlabel('xrange')
ylabel('ydata')

tita0 = randn(1,1); %intercept (randomised)

% Initialize Objective Function History
J_history = zeros(num_iters, 1);

% Number of training examples
m = (length(xrange));


Shuffling data, Gradient Descent and Cost Function

% STEP1 : we shuffle the data
data = [ xrange, ydata];
data = data(randperm(size(data,1)),:);
y = data(:,1);
X = data(:,2:end);

for iter = 1:num_iters

for i = 1:m

x = X(:,i); % STEP2 Select one example

h = tita0 + tita1.*x; % building the estimated     %Changed to xrange in BGD

%c = (1/(2*length(xrange)))*sum((h-target).^2)

temp0 = tita0 - alpha*((1/m)*sum((h-target)));
temp1 = tita1 - alpha*((1/m)*sum((h-target).*x));  %Changed to xrange in BGD
tita0 = temp0;
tita1 = temp1;

fprintf("here\n %d; %d", i, x)

end

J_history(iter) = (1/(2*m))*sum((h-target).^2); % Calculating cost from data to estimate

fprintf('Iteration #%d - Cost = %d... \r\n',iter, J_history(iter));

end


On plotting the cost vs iterations and linear regression graphs, the MSE settles (local minimum?) at around 420 which is wrong.

Any suggestions on what I am doing wrong?

EDIT:

As suggested in the answer below, my updated code:

% STEP1 : we shuffle the data
data = [ xrange' , target'];
data = data(randperm(size(data,1)),:);
y = data(:,1);
X = data(:,2:end);

for iter = 1:num_iters

for i = 1:m

x = X(i,:); % STEP2 Select one example

h = tita0 + tita1.*x; % building the estimated

%c = (1/(2*length(xrange)))*sum((h-target).^2)

temp0 = tita0 - alpha*((1/m)*sum((h-y(i))));
temp1 = tita1 - alpha*((1/m)*sum((h-y(i)).*x));
tita0 = temp0;
tita1 = temp1;

fprintf("here\n %d; %d", i, x)

end


Some fundamentals are wrong in your program:

• Your gradient update is based on target variable, but it's not shuffled, and it shouldn't be an array. It should be just a value, because it is the target for $$i-$$th sample. Suggested correction:

tita0 = tita0 - alpha*((1/m)*((h-y(i)))); tita1 = tita1 - alpha*((1/m)*((h-y(i)).*x));

• Your data array isn't of correct dimension, and it should include target instead of y, i.e. the noisy observations. Suggested correction:

data = [ xrange', target']; data = data(randperm(size(data,1)),:);

And another one I forgot to mention:

• Your x and y indexings are also wrong:

y = data(:,2); X = data(:,1);

Increase your number of iterations, to $$10000$$, and you'll see that $$\theta$$ will converge to $$[5,30]$$. I'm having the correct results, you should be having it after doing these modificaitions.

• Thank you for your suggestion. Unfortunately I am not able to get good results with the suggestions above. I agree with both suggestions and my experiment was fundamentally flawed. However I am still shuffling the data incorrectly or selecting one example incorrectly since I keep getting that Index in position 2 exceeds array bounds for x = X(:,i); – Rrz0 Apr 19 at 16:08
• Ok, another mistake was that, it should be X(i.,:) – gunes Apr 19 at 16:16
• After implementing the changes above, MSE linearly increases with number of iterations. As you suggested I was indexing the array incorrectly. I'm not sure which part of gradient descent is not working. Will update code above – Rrz0 Apr 19 at 18:04
• @Rrz0 added one more minor correction. – gunes Apr 19 at 18:14