Bypassing inverse matrix calculation and the comparison of Gradient Descent and Newton Descent

Question

I am currently reading Pattern Classification (2nd ed) by R. O. Duda, P. E. Hart and D. G. Stork, John. In the 5th chapter the Gradient Descent algorithm is introduced with the following notations :

$a(k + 1) = a(k) − η(k)∇J(a(k))$

The book then shows that if we accept that the function we want to optimize along $J()$ can be approximated with a second-order Taylor expansion around a value $a(k)$ like this

$J(a)≃ J(a(k)) +∇J^t(a(k))(a − a(k)) +\frac{1}{2}(a − a(k))^tH(a(k)) (a − a(k))$,

then the the optimal step size $η^*(k)$ after setting $a=a(k+1)$ derivating with respect to $η(k)$ is $η^*(k) =\frac{||∇J||^2}{∇J^tH∇J}$ where $∇J$ is the gradient and $H$ is the Hessian matrix of course. I plugged $η^*(k)$ back into the first equation and obtained:

$a(k + 1) = a(k) − \frac{||∇J||^2}{∇J^tH∇J}∇J(a(k))$.

I couldn't help but notice that this form of the Gradient Descent resembles the Newton Descent so much which is written as:

$a(k + 1) = a(k) −H^{−1}∇J $

And here comes the engineer speaking (Please bear with me!): If I "cancel out" the gradients in the numerator and the denominator I get $\require{cancel}\frac{\cancel{||∇J||^2}}{\cancel{∇J}^tH\cancel{∇J}}=\frac{1}{H}$ which "is" $H^{-1}$. So based on this this immaculate deduction we obtain the Newton Descent as a special case of Gradient Descent where the step size is optimal. However... I constructed several testcases where I compared the two algorithms and it turns out considering individual iterations in some cases they definitely give the same answer, sometimes the resulting $a(k+1)$ vectors are the same length but point to different directions, sometimes the other way around, and in some cases the answer is totally different. Of course in the end they converge to the same answer, but the route may be different. This led me to believe that there may be a subspace in the domain where the two methods are the same giving rise to the opportunity to use the Gradient Descent algorithm instead of the Newton method even if the Hessian matrix is singular. The computational complexity is lower since this way we bypass the computation of an inverse matrix.

Question 1:
I know the answer is probably no but... Is it possible that analytically $\frac{||∇J||^2}{∇J^tH∇J}∇J(a(k))$ is in fact equal to $H^{−1}∇J(a(k))$ and my negative test results came from some numerically ill-behaved phenomenon?

Question 2: If not, is there a well-defined circumstance, a condition under which this holds true (as in my positive testcases)?

I know this was a bit of a stretch, but it would be surprising to me if there wasn't any deeper connection between the two terms considering the fact that the algorithms do more or less the same thing and the form of the two sides are basically identical.

Answer 1

Let's take a look at the expression you wrote for gradient descent:

$$a_{k+1} = a_k - \eta_k \nabla J(a_k)$$

And for Newton's method:

$$a_{k+1} = a_k - H^{-1} \nabla J(a_k)$$

An important difference is that $\eta_k$ is a scalar, whereas $H^{-1}$ is a matrix. In gradient descent, subtracting a scaled version of the gradient from the current parameters means we step in the direction opposite the gradient (i.e. in the direction of steepest descent). In Newton's method, multiplying the gradient by a matrix (the inverse Hessian) has the effect of stretching the gradient by different amounts in different directions. This means we won't generally step along the direction of the gradient. Rather, the step direction accounts for local curvature of the objective function, typically allowing Newton's method to converge in fewer iterations than gradient descent.

You mentioned that $\eta_k = \frac{\|\nabla J\|^2}{\nabla J^T H \nabla J}$ is the optimal step size for gradient descent, based on a local quadratic approximation of the objective function. However, this is only the optimal step assuming we must step along the direction of the gradient. This step direction is not based on a local quadratic approximation as it is in Newton's method and, as above, the two are not generally equivalent.

Regarding your derivation, it's not valid to cancel terms as you suggest. As above, $\frac{\|\nabla J\|^2}{\nabla J^T H \nabla J}$ is a scalar and $H^{-1}$ is a matrix, so they can't be equivalent.

Regarding question 2, Newton's method will step in the same direction as gradient descent if the Hessian is a scalar multiple of the identity matrix. That is, $H = \alpha I$ for some scalar $\alpha$. In this case, Newton's method will step in the direction opposite the gradient, since:

$$H^{-1} \nabla J(a_k) = (\alpha I)^{-1} \nabla J(a_k) = \frac{1}{\alpha} \nabla J(a_k)$$