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: enter image description here



Your Answer

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

Browse other questions tagged or ask your own question.