Dynamic estimation of slowly varying sequences
2026-06-22 • Machine Learning
Machine LearningData Structures and Algorithms
AI summaryⓘ
The authors study how to estimate functions of items in a sequence where each item changes only a little from the previous one. They build on past work showing that reusing previous calculations helps when changes are small. Their new approach works for many types of functions and problems, including matrices and equations from physics, and adapts how much effort is spent based on how much the sequence changes at each step. This makes estimations more efficient compared to older methods that assumed a fixed worst-case change. They also show how to estimate the amount of change as the sequence progresses without much extra work.
sequential estimationslowly-varying sequenceimplicit trace estimationmatrix powersspectral densityMonte Carlo integrationboundary value problempartial differential equationspath-length variation boundsadaptive query budget
Authors
Prashant Gokhale, Mikhail Khodak, Sandeep Silwal
Abstract
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.