# Finding the cost of Hessian-vector product computation?

Suppose we have a composition of functions $$F(x)=f_n \circ f_{n-1} \circ \ldots \circ f_1 \circ x$$, where $$f_i: \mathbb{R}^{d_{i-1}}\to \mathbb{R}^{d_i}$$

The Jacobian of $$F$$, has shape $$d_n \times d_0$$ and can be written as a product of Jacobians of $$f_i$$'s. We can assume these Jacobians are provided, then the minimum cost to compute Jacobian is obtained by solving the matrix chain problem. What about the minimum cost to compute the Hessian-vector product?

More precisely, define Hessian-vector product of $$F$$

$$\text{hvp}(F,x,v)_{i,j}=\sum_{k=1}^{d_0} \frac{\partial^2 F_i(x)}{\partial x_j \partial x_k} v_k$$

Where $$\frac{\partial^2 F_i(x)}{\partial x_j \partial x_k}$$ is the Hessian of $$F$$, a tensor with shape $$d_n\times d_0 \times d_0$$ and $$v$$ is a vector with $$d_0$$ elements.

Given the list of dimensions $$d_0,\ldots,d_n$$, what is the minimum cost to compute $$\text{hvp}$$?

PS, for $$n=3$$, hvp computation is visualized below as a sum of 3 tensor network diagrams: