# Stochastic gradient descent squared loss

I have implemented stochastic gradient descent in matlab and I would like to compare my results with another source but the error I am getting is higher (I am using squared error). I am worried I am misunderstanding the algorithm or have a bug. I have done trial and error parameter tuning, and am quite confident I have appropriate value for B, and know that I am working with the same data as my comparison. Please let me know what can be improved and if there is a mistake.

    % [w] = learn_linear(X,Y,B)
%
% Implement the online gradient descent algorithm with a linear predictor
% and minimizes over squared loss.
% Inputs:
%     X,Y - The training set, where example(i) = X(i,:) with label Y(i)
%     B - Radius of hypothesis class.
% Output:
%     w - predictor (as a row vector) from the hypothesis class (norm(w) <= %B)

function [w] = learn_linear_sq_error(X, Y, B)
[r c] = size(X);
w = zeros(1, c);
sum_w = zeros(1, c);
% number of iterations
T = 1000;

% Run T iterations of online gradient descent:
for t = 1:T,
% Calculate step size for the current iteration.
eta_t = 1 / sqrt(t);

% Choose a random sample, and calculate its gradient.
i_t = round(rand(1) * (r - 1)) + 1;
g_t = calc_g_t(X(i_t, :), Y(i_t), w);

% Apply the update rule/projection using the chosen sample, by %finding
% the w that minimizes '|w - (w_t - eta_t * g_t)|' while          %maintaining norm(w) <= B.
pw = w - eta_t * g_t;
norm_pw = norm(pw);
if norm_pw <= B
w = pw;
else
w = B * pw / norm_pw;
end

% accumulate the sum in preparation for calculating the final average.
sum_w = sum_w + w;

end

% Return the average of all intermediate w's.
w = sum_w / T;
end

%
% Calculate the sub gradient, with respect to squared loss, for a given sample
% and intermediate predictor.
% Inputs:
%     x,y - A sample x (given as a row vector) and a tag y in R.
%     w - our current predictor.
% Output:
%     g_t - the gradient (as a row vector) for the given values of x, y, w.

function g_t = calc_g_t(x, y, w)

g_t = 2 * (w*x' - y) * x;

end

-
One thing you could try is to keep the error data at each iteration and make a plot to see if you are converging to the error value of the comparison. – toto2 Apr 26 '14 at 13:01
Thanks. I tried this but I seem to not be going too much lower than the error I am getting. I tried running for 400,000+ iterations and do not get significantly lower error. – jon Apr 26 '14 at 14:29

You probably do not need help with this question anymore (looks like it's been a year), but I thought I'd point something out in case someone else finds it useful. I think your squared loss expression should be $(w'*x - y)^2$ and the derivative of that with respect to $x$ is: $2*(w'*x-y)*w$. What you have is the outer product which results in a matrix minus a scalar. So I noticed two errors: