We study a dynamic version of the implicit trace estimation problem. Given access to an oracle for computing matrix-vector multiplications with a dynamically changing matrix A, our goal is to maintain an accurate approximation to A's trace using as few multiplications as possible. We present a practical algorithm for solving this problem and prove that, in a natural setting, its complexity is quadratically better than the standard solution of repeatedly applying Hutchinson's stochastic trace estimator. We also provide an improved algorithm assuming slightly stronger assumptions on the dynamic matrix A. We support our theory with empirical results, showing significant computational improvements on three applications in machine learning and network science: tracking moments of the Hessian spectral density during neural network optimization, counting triangles, and estimating natural connectivity in a dynamically changing graph.


翻译:我们研究隐性追踪估计问题的动态版本。鉴于我们有机会使用一个神器来计算矩阵-矢量乘数,并使用动态变化的矩阵A,我们的目标是尽可能少地使用乘数来保持对A跟踪的准确近似。我们提出了解决这一问题的实用算法,并证明在自然环境中,其复杂性比反复应用哈钦森的随机微量估计仪的标准解决方案要好四倍。我们还提供了一种改进的算法,假设对动态矩阵A的假设略强一些。我们用实验结果支持我们的理论,在机器学习和网络科学的三个应用方面展示了重大的计算改进:在神经网络优化、计算三角和动态变化的图表中估算赫森光谱密度的时刻。

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
52+阅读 · 2020年11月3日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
CVPR 2019 | 34篇 CVPR 2019 论文实现代码
AI科技评论
21+阅读 · 2019年6月23日
CVPR 2019 | 重磅!34篇 CVPR2019 论文实现代码
AI研习社
11+阅读 · 2019年6月21日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【跟踪Tracking】15篇论文+代码 | 中秋快乐~
专知
18+阅读 · 2018年9月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年12月23日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
Viewpoint Estimation-Insights & Model
Arxiv
3+阅读 · 2018年7月3日
Arxiv
3+阅读 · 2018年4月9日
Arxiv
6+阅读 · 2018年2月8日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
CVPR 2019 | 34篇 CVPR 2019 论文实现代码
AI科技评论
21+阅读 · 2019年6月23日
CVPR 2019 | 重磅!34篇 CVPR2019 论文实现代码
AI研习社
11+阅读 · 2019年6月21日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【跟踪Tracking】15篇论文+代码 | 中秋快乐~
专知
18+阅读 · 2018年9月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员