5
$\begingroup$

In regression analysis, instead of gradient descent, Newton's method can be used for minimizing the cost function. However, in Newton's method, we need to calculate second derivative too.

For example, to minimize a cost function $F(x)$, we need to find $x_0$ such that $F'(x0) = 0$, which means that we need to find the zeroes of $F'(x)$.

And for that, we can use Newton's method:
$$ x_1 = x_0 - \frac{F'(x_0)}{F"(x_0)} $$

In the case of linear regression, the cost function is:
$$ J = [h(x) - y]^2 $$

In the case of logistic regression, the cost function is:
$$ J = y \log(h(x)) + (1 - y)(1 - \log(h(x))) $$

In both the cases, since the cost function's minimum value is $0$, why can't we directly find the zeroes of the function using Newton's method, thus avoiding the calculation of the second derivative?

$\endgroup$
5
  • 6
    $\begingroup$ It is not the case that the minimum value of the cost function will always be zero in linear or nonlinear regression. Usually, it is not, but will be if all the "equations", i.e., data points, are entirely consistent - but this is not usually the case in regression analysis. $\endgroup$ Commented Apr 16, 2016 at 17:09
  • $\begingroup$ @MarkL.Stone How does Newton's method behave on a function which doesn't have any roots? Won't it just output the x where F(x) is nearest to the X-axis (i.e the minima of F(x))? $\endgroup$ Commented Apr 16, 2016 at 17:43
  • 1
    $\begingroup$ Not necessarily. It depends on the function and the implementation of Newtons' method. You could end up far away with the algorithm reporting "failed". $\endgroup$ Commented Apr 16, 2016 at 17:52
  • $\begingroup$ @MarkL.Stone Could you give any example for such a case? (not doubting your opinion, just curious!) $\endgroup$ Commented Apr 16, 2016 at 18:07
  • 1
    $\begingroup$ homes.soic.indiana.edu/classes/spring2012/csci/b553-hauserk/… $\endgroup$
    – goelakash
    Commented Apr 16, 2016 at 19:51

2 Answers 2

1
$\begingroup$

As mentioned in the comments, the reason is that the cost functions mentioned might not have any zeroes at all, in which case Newton's method will fail to find the minima.

I have created a visualization to show this:

Simulation of Newton's Raphson method on a function not having any zeroes

As you can see, the method is not converging at all for this particular case.

The code used to create this is stored here.

Adding the relevant portion of the code here itself for convenience:

newton.m:

% Dummy statement to avoid writing function in the first line and making it a 'function file' instead of a 'script file'
1;


% The function to find zeroes of.
% The function is specifically chosen to not have any zeroes
% so as to show the weakness of Newton's method.
function y = f(x)
    y = (x - 5).^2 + 5;
endfunction


% The derivative of f(x)
function y = fd(x)
    y = 2 * (x - 5);
endfunction


% Initial guess
x0 = 1.5;

% Max number of iterations
itermax = 20;

% Epsilon value initialized to a very large value
eps = 1;

% A vector for storing the history of the approximate roots
xvals = x0;

% Number of iterations done
itercount = 0;

% Required for plotting f(x) vs x
x = linspace(0, 10, 100);

% Create a figure whose output is not rendered on the screen
% Not working currently; supposedly a bug in Octave
% A workaround is to use gnuplot instead of qt - `graphics_toolkit gnuplot`
% but this is very slow.
% Uncomment the following to activate the feature once the bug is fixed
% figure('Visible','off');

% The main loop
while eps >= 1e-5 && itercount <= itermax
    % x1 = New value of root
    % x0 = Current value of root
    x1 = x0 - f(x0) / fd(x0);

    % Plot f(x)
    % Plot a line passing through points [x0, f(x0)] and [x1, 0]
    % Plot a line passing through points [x1, 0] and [x1, f(x1)]
    % Plot a line passing through points [x0, 0] and [x0, f(x0)]
    plot(x, f(x), ";f(x);", [x0 x1], [f(x0) 0], "-r;f'(x);", [x1 x1], [0 f(x1)], ":r", [x0 x0], [0 f(x0)], ":r");
    title('f(x) = (x-5)^2 + 5');


    % Set limits for the axes shown in the plots
    xlim([0 10]);
    ylim([0 30]);

    % Label the two consecutive zeroes on the X-axis
    text(x0, -2, sprintf('x%d', itercount), 'color', 'red');
    text(x1, -2, sprintf('x%d', itercount+1), 'color', 'red');

    % Print the plot to a file
    filename = sprintf('output/%05d.jpg', itercount);
    print(filename)

    % Append the zero to the array of zeroes calculated so far
    xvals = [xvals; x1];

    % Calculate the epsilon value
    eps = abs(x1-x0);

    x0 = x1;
    itercount = itercount+1;
end


% Print the result of the iteration
xvals
f_zero = f(xvals(end))
eps
itercount
$\endgroup$
7
  • 2
    $\begingroup$ You appear to have confused a cost function with its derivative. In practically all statistical applications, the cost function has a minimum: that is what is being sought, not a zero! $\endgroup$
    – whuber
    Commented Apr 18, 2016 at 14:08
  • 1
    $\begingroup$ @whuber I know the difference between the cost function and its derivative. The problem is that this method would work only if there exists a hypothesis which perfectly fits the data (i.e. the zero of the cost function exists), as in that case finding the minimum and finding the zero of the cost function would have been the same thing (as cost functions are not designed to output negative values). $\endgroup$ Commented Apr 18, 2016 at 14:17
  • $\begingroup$ Your comment appears to continue the confusion between a cost function and its derivative. The OP is applying Newton's method to $F^\prime$, not $F$ itself. It will therefore fail for nondifferentiable functions or when minima occur on a boundary, but those do not appear to be the possibilities you are investigating here. $\endgroup$
    – whuber
    Commented Apr 18, 2016 at 14:19
  • $\begingroup$ @whuber I am the OP! $\endgroup$ Commented Apr 18, 2016 at 14:21
  • 1
    $\begingroup$ But finding a zero of a cost function is pointless: as you have noted, it is usually not the case that a cost function has a zero. It is difficult to see how your demonstration is related to the question that has been asked in this thread. $\endgroup$
    – whuber
    Commented Apr 18, 2016 at 14:39
0
$\begingroup$

for 1-dim data you can apply Newton-method without 2nd derivative (like here), usually Newton-method with 1st derivative only - is known as pseudo-Newton.

But if your input into logistic_regression func is multi-dim then you need to use Hessian, like here

p.s. if you do standartization for your input prior fitting, then you do not need Intercept in your least-squares method, I suppose. As so as, in $f(x) = ax + b$, a represents the gradient of the line, and b represents the y-axis intercept (which is sometimes called the vertical intercept), thus, I see no problem, to find zero of func. for standartized data , just then do reverse transformations *std+mean

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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