这篇论文让序列估计变得更智能了：它能根据变化大小自动调整计算量，比之前方法节省不少成本，特别适合那种大部分时间稳定、偶尔突变的序列。
该论文提出一个通用框架，用于逐次近似缓慢变化序列中每个元素的函数，其中相邻元素差异幅度α_i较小。此前Dharangutte & Musco在NeurIPS 2021中给出隐式迹估计的代价为O(m·max α_i)，而新框架将代价改进为O(∑α_i)，在序列稳定时效率更高。框架适用于矩阵幂、谱密度、蒙特卡洛积分和偏微分方程边界值问题等线性与非线性函数。此外，算法能够局部化调整估计预算，并可在某些情况下在线估计变化量，几乎不增加额外成本。
Dynamic estimation of slowly varying sequences
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.