# Computing the Newton-step faster than Hessian accumulation

arXiv: https://arxiv.org/abs/2108.01219 · HTML: https://mlsanity.com/paper/2108.01219/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 8 references that are in the map.
- First posted on arXiv 2 Aug 2021.

## Builds on (most cited first, 1 of 1)

- [Graphical Newton](https://mlsanity.com/paper/1508.00952/) (2015)

## Abstract (arXiv)

Computing the Newton-step of a generic function with N decision variables takes O(N3) 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.