Computing the Newton-step faster than Hessian accumulation

Akshay Srinivasan, Emanuel Todorov

Computing the Newton-step of a generic function with $N$ decision variables takes $O(N^3)$ flops. In this paper, we show that given the computational graph of the function, this bo…