This article introduces a framework for sequentially approximating functions in slowly-varying sequences, leveraging the reuse of past queries to reduce overall computational cost. The authors present novel sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and partial differential equation boundary value problems.
- Generalizes implicit trace estimation to diverse linear and nonlinear functions on various vector spaces.
- Develops an algorithm that locally scales the estimation budget with the sequence difference magnitude α_t.
- Achieves sharper variation bounds of O(∑α_i) compared to the previous worst-case bound of O(m·max α_i).
- Demonstrates how changes can be estimated on-the-fly with nearly no added cost, removing the need for a known bound on α_i.
The framework makes sequential approximation general-purpose and adaptive while improving upon state-of-the-art guarantees for dynamic trace estimation.