Graphical Newton
This work addresses computational efficiency for optimization algorithms in machine learning and scientific computing, though it appears incremental as it builds on known graph-based methods.
The paper tackles the problem of reducing the cubic time complexity of computing the Newton step for generic functions by leveraging prior knowledge of the computational structure, achieving a time complexity linear in the graph size and cubic in its tree-width.
Computing the Newton step for a generic function $f: \mathbb{R}^N \rightarrow \mathbb{R}$ takes $O(N^{3})$ flops. In this paper, we explore avenues for reducing this bound, when the computational structure of $f$ is known beforehand. It is shown that the Newton step can be computed in time, linear in the size of the computational-graph, and cubic in its tree-width.