Stochastic gradient descent squared loss

Question

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

Answer 1

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:

1. You need an inner product instead of an outer product.
2. You applied the chain rule wrong when you took the derivative w.r.t x.