Computing the Newton-step faster than Hessian accumulation
This work addresses computational bottlenecks in optimization for researchers and practitioners, offering non-trivial gains in iteration-complexity even with dense Hessians, though it is incremental as it builds on existing control methods.
The paper tackles the problem of reducing the computational cost of computing the Newton-step from O(N^3) to O(mτ^3) by leveraging the computational graph's tree-decomposition, generalizing nonlinear optimal-control methods to general optimization problems.
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.