Dynamic estimation of slowly varying sequences

We consider the problem of sequentially approximating a target function of each element in a slowly-varying sequence, i.e. one where the magnitude ${\alpha }_i$ of the difference between the elements at positions $i$ and $i-1$, measured in an appropriate norm, is small. Recent work on implicit trace estimation shows that when ${\alpha }_i$ is small in Frobenius norm, reusing queries to past sequence elements can reduce the overall cost (Dharangutte and Musco, 2021; Woodruff et al., 2022). We introduce a framework that generalizes this approach to linear and nonlinear functions on normed vector spaces, obtaining sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and certain boundary value problems from partial differential equations (PDEs). Furthermore, we develop an algorithm that locally scales the estimation budget with ${\alpha }_i$, obtaining sharper path-length-style variation bounds of form $\mathcal{O}\left(\frac{1}{{ϵ}^2}{\sum }_{i=1}^m{\alpha }_i\right)$ on the cost of estimating a sequence of length $m$ to accuracy $ϵ$. This improves upon the earlier implicit trace estimation dependence on $\frac{m}{{ϵ}^2}{\max }_i{\alpha }_i$ (Dharangutte and Musco, 2021), which results from fixing the query budget using the worst-case step size ${\alpha }_i$ and is thus inefficient for stable sequences with rare bursts. Furthermore, while prior theoretical guarantees assume a known bound on the step sizes, we show in certain cases how to estimate them on the fly with (nearly) no added cost. Lastly, we complement our theoretical results with experiments demonstrating improved accuracy–cost trade-offs over prior baselines on trace estimation and Hessian tracking. In summary, our framework makes sequential approximation general-purpose and adaptive while sharpening state-of-the-art guarantees for dynamic trace estimation.