Fetching the paper…

Reading the bibliography…

2021

Computing the Newton-step faster than Hessian accumulation

Srinivasan, Akshay, Todorov, Emanuel

Original
PDF
Post on X

Understand

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\tau^3)$, where $\tau, 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.

Computing the Newton-step faster than Hessian accumulation · Around

Built on

Differential Dynamic Programming
Jacobson, D. H. and Mayne, D. Q · 1970
Earlier work this paper cites.
Differential Dynamic Programming and Newton’s Method
De O. Pantoja, J · 1988
Earlier work this paper cites.

Similar

Solution of Discrete-Time Optimal Control Problems on Parallel Computers
Wright, S. J · 1990
Cited alongside, same era.
Advantages of Differential Dynamic Programming Over Newton’s Method for Discrete-Time Optimal Control Problems
Liao, L.-z. and Shoemaker, C. A · 1992
Cited alongside, same era.
Iterative Linear Quadratic Regulator Design for Nonlinear Biological Movement Systems
Li, W. and Todorov, E
Cited in the paper.

Then

Graphical Newton
Original
Srinivasan, A. and Todorov, E · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…