Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
share|improve this question
    
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

1 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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.