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 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 at 14:29

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.