Dynamic estimation of slowly varying sequences

arXiv:2606.23655v2 Announce Type: replace Abstract: 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. 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 the form $\mathcal{O}\left(\tfrac1{\epsilon^2}\sum_{i=1}^m \alpha_i\right)$ on the cost of estimating a sequence of length $m$ to accuracy $\epsilon$. This improves upon the earlier implicit trace estimation dependence on $\tfrac m{\epsilon^2}\max_i\alpha_i$, 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.