最適化arXiv:1508.00952
グラフ的ニュートン法
Graphical Newton
関数の計算構造をグラフで表し、その木幅に基づいてニュートン法の計算量を削減する手法を提案した論文。
著者: Akshay Srinivasan, Emanuel Todorov
分類: math.OC, cs.RO, cs.SY, eess.SY
原文アブストラクト
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.
