BriefGPT.xyz
Aug, 2021
比Hessian积分计算更快的Newton步骤计算
Computing the Newton-step faster than Hessian accumulation
HTML
PDF
Akshay Srinivasan, Emanuel Todorov
TL;DR
本文提出了一种新的算法，通过计算函数的计算图，可以将计算Newton步骤的时间复杂度从$O(N^3)$ 降至 $O(m\tau^3)$，并将非线性最优控制方法推广到一般优化问题，并在Hessian矩阵密集的情况下提供非平凡的迭代复杂度收益。
Abstract
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
→