Computing the Newton-step faster than Hessian accumulation

08/02/2021
by   Akshay Srinivasan, et al.
25

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 bound can be reduced to O(mτ^3), where τ, m are the width and size of a tree-decomposition of the graph. The proposed algorithm generalizes nonlinear optimal-control methods based on LQR to general optimization problems and provides non-trivial gains in iteration-complexity even in cases where the Hessian is dense.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset