  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.
