Dynamic estimation of slowly varying sequences

Abstract

We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude $\hat{I}{\pm }_i$ of the difference between the elements at positions $i$ and $i-1$ is small. Recent work on implicit trace estimation shows that when $\hat{I}{\pm }_t$ is small, reusing queries to past sequence elements can reduce the overall cost [Dharangutte \& Musco, NeurIPS~2021; Woodruff et al., NeurIPS~2022]. We introduce a framework generalizing this to a variety of linear and nonlinear functions on diverse vector spaces, obtaining novel sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and a boundary value problem from partial differential equations~(PDEs). Furthermore, we develop a novel algorithm for use with this framework that locally scales the estimation budget with $\hat{I}{\pm }_t$, obtaining sharper path-length-style variation bounds of form $\mathcal{O}({\sum }_{i=1}^m\hat{I}{\pm }_i)$ on the cost of estimating a sequence of length $m$. This improves upon the previous implicit trace estimation bound of $\mathcal{O}(m\cdot {\max }_i\hat{I}{\pm }_i)$ [Dharangutte \& Musco, NeurIPS~2021], which is achieved by fixing the query budget using the worst-case $\hat{I}{\pm }_i$ and is thus inefficient for stable sequences with rare bursts. Lastly, while all past work assumes a known bound on $\hat{I}{\pm }_i$, we show in certain cases how the changes can be estimated on-the-fly with (nearly) no added cost. In summary, our framework makes the sequential approximation toolkit general-purpose and adaptive while improving upon state-of-the-art-guarantees for dynamic trace estimation.

Preprint. 14 pages, 4 figures