Computing the Newton-step faster than Hessian accumulation

Srinivasan, Akshay; Todorov, Emanuel

数学 > 优化与控制

arXiv:2108.01219 (math)

[提交于 2021年8月2日 ]

标题：以比Hessian累积更快的速度计算牛顿步

标题： Computing the Newton-step faster than Hessian accumulation

Authors:Akshay Srinivasan, Emanuel Todorov

摘要：计算具有$N$个决策变量的通用函数的牛顿步长需要$O(N^3)$次浮点运算。在本文中，我们表明，给定该函数的计算图，此界限可以降低到$O(m\tau^3)$，其中$\tau, m$是该图的树分解的宽度和大小。所提出的算法将基于LQR的非线性最优控制方法推广到一般的优化问题，并且即使在Hessian矩阵是稠密的情况下，也能在迭代复杂度上提供非平凡的改进。

摘要： 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.

评论：	在ICML '21 Beyond First-order Methods研讨会中发表
主题：	优化与控制 (math.OC) ; 机器学习 (cs.LG); 符号计算 (cs.SC); 系统与控制 (eess.SY)
引用方式：	arXiv:2108.01219 [math.OC]
	(或者 arXiv:2108.01219v1 [math.OC] 对于此版本)
	https://doi.org/10.48550/arXiv.2108.01219

提交历史

来自： Akshay Srinivasan [查看电子邮件]
[v1] 星期一， 2021 年 8 月 2 日 11:22:08 UTC (37 KB)

全文链接：

获取论文：

查看许可

当前浏览上下文:

eess

新的 | 最近的 | 2021-08

切换浏览方式为:

cs
cs.LG
cs.SC
cs.SY
eess.SY
math
math.OC

参考文献与引用

导出 BibTeX 引用

数学 > 优化与控制

标题：以比Hessian累积更快的速度计算牛顿步

标题： Computing the Newton-step faster than Hessian accumulation

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

数学 > 优化与控制

标题： 以比Hessian累积更快的速度计算牛顿步 显示英文标题

标题： Computing the Newton-step faster than Hessian accumulation

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

标题：以比Hessian累积更快的速度计算牛顿步