Search papers, labs, and topics across Lattice.
This paper introduces a general framework for sequentially approximating functions of slowly-varying sequences, significantly extending previous work on implicit trace estimation. By developing a novel algorithm that adapts the estimation budget based on the local variation of the sequence, the authors achieve improved cost bounds for estimating various functions, including matrix powers and Monte Carlo integration. The key result is a sharper bound of \(\mathcal{O}(\sum_{i=1}^m \alpha_i)\), which outperforms the existing \(\mathcal{O}(m \cdot \max_i \alpha_i)\) bound, particularly for stable sequences with infrequent bursts of variation.
Adaptive estimation of slowly-varying sequences can cut costs by leveraging local variations, achieving a new bound that outperforms traditional methods.
We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude $α_i$ of the difference between the elements at positions $i$ and $i-1$ is small. Recent work on implicit trace estimation shows that when $α_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 $α_t$, obtaining sharper path-length-style variation bounds of form $\mathcal O(\sum_{i=1}^mα_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α_i)$ [Dharangutte \& Musco, NeurIPS~2021], which is achieved by fixing the query budget using the worst-case $α_i$ and is thus inefficient for stable sequences with rare bursts. Lastly, while all past work assumes a known bound on $α_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.
