Fminunc : trust-region fails on supplying gradient

Hi,

I am trying to implement logistic regression. Whenever I use a default Quasi-Newton algorithm with fminunc (exitflag and output on), it works fine (it looks fine, because f(x) value and first_order_optimality values are changing over the iterations). But when I supply the gradient and use 'trust-region' instead, it is giving exitflag 2 and f(x) value and first_order_optimality values are being constant over all the iterations. I tried changing initial points. Here's my function

       load ../../data/train.txt
x_train = train(:,1:57);
x_train = [x_train ones(250,1)];
y_train = train(:,58);
% Scaling y = -1 data to y = 0
for index = 1:250
    if (y_train(index) == -1)
        y_train(index) = 0;
    end
end
%initializing out learning parameters (57 features + 1 bias term) with all
%zeros
w_initial = rand(58,1);

 % Case - 1 : We will use 100% training data in first case
percent = 1;
r = percent * 250;
x_train = x_train(1:r,:);
y_train = y_train(1:r,:);
cost = calculateCost(w, x_train, y_train);
fprintf('Initial calculated cost = %f', cost);
options = optimoptions(@fminunc, 'Display','iter', 'Algorithm','trust-region', 'GradObj', 'on', 'MaxFunEvals', 100000, 'MaxIter', 5000);
[w, optcost exitflag output] = fminunc(@(x)(calculateCost(x, x_train, y_train)), w_initial, options)

And here's my cost function where I am also supplying the gradient...

       function [cost, gradient] = calculateCost(w, x_train, y_train)
%calculating dimensions of training set
[examples, feat_bias] = size(x_train);
%defining our logistic/sigmoid function based hypothesis
h = logistic(y_train .* (x_train * w));
%cost is MLE of our hypothesis function
cost = -(sum(log(h)));
%supplying gradient for more efficient trust-region usage
gradient = zeros(feat_bias, 1);
if nargout > 1
    for i = 1:examples
        gradient = gradient + (h(i) - y_train(i)) * x_train(i,:)' ;
    end
end
end

 function [logi] = logistic(a)
logi = 1./(1 + exp(-a));
end

I think I am supplying the gradient correctly (as per the documentation given).

Here's the console output:

      -----
      f(x): 138.263 over all the 13 iterations!!
      first ord opt : 47.1 over all the 13 iterations!!
exitflag = 2       
iterations: 13
                funcCount: 14
             cgiterations: 29
            firstorderopt: 47.1413
                algorithm: 'trust-region'
                  message: 'Local minimum possible.
      Local minimum possible.
      -----

I know the answer trust-region has found is incorrect (because it is not same as that of quasi-newton's).

I am not getting the it.. Why isn't it working?

Answer 1

[Matt J]

Did you use the 'DerivativeCheck' or 'CheckGradient' option to verify your gradient calculation?

The gradient calculation does look wrong to me. The derivative of log(h) should involve,

h'/h= exp(-a)/(1+exp(-a))

[Tushar Shinde]

Yes. It is failing the derivative check:

DerivativeCheck failed: User-supplied and forward finite-difference derivatives do not match within 1e-06 relative tolerance.

[Tushar Shinde]

But I have double checked the method for calculating the gradient for logistic regression:

summation_over_all_training_examples(sigmoid(Zi - Yi)*Xi)

where Zi = Yi(Theta' * X)

[Matt J]

Even if that expression for the gradient is correct, in what way does it resemble your code?

(h(i) - y_train(i)) * x_train(i,:)'