Automatic Differentiation: Inverse Accumulation Mode
This work addresses the computational bottleneck of inverting Jacobians in optimization and numerical methods, offering potential efficiency gains for Newton-type algorithms.
The authors propose a method for automatic differentiation that computes Jacobian-inverse-vector and Jacobian-inverse-transpose-vector products as efficiently as forward and reverse mode, under sparsity constraints. This enables efficient direct calculation of Newton steps.
We show that, under certain circumstances, it is possible to automatically compute Jacobian-inverse-vector and Jacobian-inverse-transpose-vector products about as efficiently as Jacobian-vector and Jacobian-transpose-vector products. The key insight is to notice that the Jacobian corresponding to the use of one basis function is of a form whose sparsity is invariant to inversion. The main restriction of the method is a constraint on the number of active variables, which suggests a variety of techniques or generalization to allow the constraint to be enforced or relaxed. This technique has the potential to allow the efficient direct calculation of Newton steps as well as other numeric calculations of interest.