# Efficient O(N) Hessian Vector Product with Pearlmutter trick

Hi everyone, am I correct that there is currently no way to efficiently compute the Hessian vector product using Pearlmutter trick (from Fast Exact Multiplication by the Hessian), i.e. approximately same time complexity as two gradient computations, due to missing forward-mode AD in PyTorch? Is there any way to work around this?

I am aware that I can simply use plain AD to compute the Hessian vector product (which will be slow), and that I can use finite difference approximation (which will be inexact and numerically unstable). Iâ€™ve also seen the R-operator and L-operator defined in a similiar issue ([Adding functionality] Hessian and Fisher Information vector products) and how they replace the R-operator with two L-operator calls, however this still wonâ€™t be O(N) or am I missing something? Thanks for your input!

2 Likes

Hey,

The r and l operators by definition have complexities O(N), since theyâ€™re just a backward pass or backward called twice. So yes, the actual complexity is going to be O(3N) but you drop the constant since itâ€™s still O(N).

I guess youâ€™re right theoretically but when I try it in practice I get vastly different runtimes. Maybe an implementation issue? Maybe I misunderstood something about R-op or L-op? This is what the comparison looks like (timing on CPU):

``````Pearlmutter:                       3.89 s Â± 151  ms per loop (7 runs, 1 loop each)
Simple AD:                         1.21 s Â± 64.5 ms per loop (7 runs, 1 loop each)
Finite difference approximation:   327 ms Â± 11   ms per loop (7 runs, 1 loop each)
``````

The first two return the same (correct) result and the last one returns a pretty good approximation. Here is more or less what the Pearlmutter implementation looks like:

``````def hvp(model, criterion, inputs, outputs, v, *args, **kwargs):

# Forward-pass
prediction = model(inputs)
L = criterion(prediction, outputs)

vp = rop(parameters_to_vector(y), model.parameters(), v)

return vp

def rop(y, x, v):

w = torch.zeros(y.size(), requires_grad = True)
return parameters_to_vector(r)
``````
1 Like

Hi,

Quick note about your `rop` function, if your grad_ouputs is a Tensor of 0s, all your gradients in g will be 0. Maybe you meant ones?
Also hvp (if it means hessian vector product) does not need 3 calls to backward as you do here. Only 2 are needed.

I am not familiar with the Pearlmutter trick but does it boil down to mixing forward and backward AD to compute the hessian faster?
If so, in the approximation that forward/backward prop/forward prop all have the same cost C.
Computing the Hessian vector product with double backward will cost 4C (C forward, C first backward, 2C second backward).
Computing the Hessian vector product with forward/backward AD will cost 3C (C forward, C forward mode grads, C backward of forward mode grad).

So while This would give some benefit compared to double backward, It might not be as big as what you expect.

Thanks for your thoughts @albanD ! So the implementation above is not the vanilla 2-backward calls implementation of HVPs, itâ€™s supposed to implement the Pearlmutter trick, which is indeed mixing forward and backward AD if I understand correctly. We can replace the forward-mode with two reverse-mode calls (see for reference j-townâ€™s A new trick for calculating Jacobian vector products) so altogether three backward calls as above should be fine. Please correct me if Iâ€™m wrong.

Now what I donâ€™t understand is why this approach is taking so much longer than both the naive (â€śSimple ADâ€ť above) approach and the finite different approximation. Itâ€™s one order of magnitude slower than finite difference approximation which requires two gradient evaluations and asymptotically speaking should have the same complexity as Pearlmutters method. I guess Iâ€™m lacking some knowledge on autograds internals hereâ€¦

EDIT: So rereading the above linked blog postâ€™s conclusion actually brings some clarification:

For Autograd, the situation isnâ€™t quite as simple. Autograd doesnâ€™t do its differentiation ahead of time, and needs to trace a functionâ€™s execution in order to reverse-differentiate it. This makes our new trick, in its basic form, significantly less efficient than the forward mode implementation that Iâ€™ve written.

So this is also the case for PyTorch and PyTorchâ€™s autograd I guess? As a result the trick doesnâ€™t bring any advantage because it computes more than â€śnecessaryâ€ť in some way? An actual forward-mode implementation is the only way to move forward?

A forward-mode implementation is going to give you benefits in theory yes. But the theory only tells you that it will be 3/4th of the runtime. It would go from 4s to 3s. It is important but not that much given the measurements you showed above.
Not sure what the practical result would be though as you would need a forward mode AD system

1 Like