← 研踪 PaperTrailarXiv:2606.23655 · v2
Dynamic estimation of slowly varying sequences
首次提交 2026-06-23 01:40
版本更新 2026-11-03 01:52
雷达观测 2026-11-04 23:41
摘要
We consider the problem of sequentially approximating a target function 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$, measured in an appropriate norm, is small. Recent work on implicit trace estimation shows that when $α_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 $α_i$, obtaining sharper path-length-style variation bounds of the form $\mathcal{O}\left(\tfrac1{ε^2}\sum_{i=1}^m α_i\right)$ on the cost of estimating a sequence of length $m$ to accuracy $ε$. This improves upon the earlier implicit trace estimation dependence on $\tfrac m{ε^2}\max_iα_i$, which results from fixing the query budget using the worst-case step size $α_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.
作者备注：Preprint. 14 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 01:52 · 最新观测版本
Dynamic estimation of slowly varying sequences
We consider the problem of sequentially approximating a target function 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$, measured in an appropriate norm, is small. Recent work on implicit trace estimation shows that when $α_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 $α_i$, obtaining sharper path-length-style variation bounds of the form $\mathcal{O}\left(\tfrac1{ε^2}\sum_{i=1}^m α_i\right)$ on the cost of estimating a sequence of length $m$ to accuracy $ε$. This improves upon the earlier implicit trace estimation dependence on $\tfrac m{ε^2}\max_iα_i$, which results from fixing the query budget using the worst-case step size $α_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.
查看此版本解读 →查看此版本原文 ↗