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的假设略强一些。我们用实验结果支持我们的理论,在机器学习和网络科学的三个应用方面展示了重大的计算改进:在神经网络优化、计算三角和动态变化的图表中估算赫森光谱密度的时刻。