Hessian-free and Truncated Newton methods

Question

In this paper on Deep Learning for Machine Learning, the approach is referred to as Hessian-free method. That is because the Hessian is never computed explicitly. Instead, the product of the Hessian and a vector is obtained using finite difference approximation. This is used by the Conjugate Gradient step to compute the Newton direction. The number of iterations that Conjugate Gradient runs is truncated, as soon as a "good enough" direction is obtained. The paper states this truncation as an aspect of the Hessian-free method. However, isn't this truncated Newton method? It looks like this paper is combining Hessian-free with truncated Newton method.

Answer 1

It looks like this paper is combining Hessian-free with truncated Newton method.

Yes, it is.

...the approach is referred to as Hessian-free method. That is because the Hessian is never computed explicitly. Instead, the product of the Hessian and a vector is obtained using finite difference approximation.

Right. This step is analogous to the "Jacobian-free" half of Jacobian-free Newton-Krylov methods.

This is used by the Conjugate Gradient step to compute the Newton direction.

Correct.

The number of iterations that Conjugate Gradient runs is truncated, as soon as a "good enough" direction is obtained. The paper states this truncation as an aspect of the Hessian-free method. However, isn't this truncated Newton method?

Yes. You're right that the discussion in Section 3 of the paper is confusing. The author is combining two things:

• an "inexact" or "truncated" (quasi-)Newton method will solve the linear equations within a (quasi-)Newton method inexactly, using an iterative solver. In this paper, the author is using the conjugate gradient (CG) method. Such a method requires Hessian-vector products (or, for solving nonlinear equations, Jacobian matrix-vector products). One could calculate this matrix-vector product exactly, or approximately.
• a "Hessian-free" method in optimization (respectively, a "Jacobian-free" method for solving nonlinear equations) approximates the Hessian-vector product (respectively, the Jacobian matrix-vector product) using finite difference evaluations.
• So, typically, one uses a Hessian-free method within a truncated Newton method, but you could just as easily use a truncated Newton method with exact Hessian-vector products. This paper chooses to combine the Hessian-free method with a truncated Newton method, which is a reasonable choice.