# Dynamic estimation of slowly varying sequences

arXiv: https://arxiv.org/abs/2606.23655 · HTML: https://mlsanity.com/paper/2606.23655/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 22 Jun 2026.

## Builds on (most cited first, 13 of 13)

- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Scalable Log Determinants for Gaussian Process Kernel Learning](https://mlsanity.com/paper/1711.03481/) (2017)
- [Approximating the Spectrum of a Graph](https://mlsanity.com/paper/1712.01725/) (2017)
- [Dynamic Trace Estimation](https://mlsanity.com/paper/2110.13752/) (2021)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [Nonparametric Density Estimation under Distribution Drift](https://mlsanity.com/paper/2302.02460/) (2023)
- [Entropic Trace Estimates for Log Determinants](https://mlsanity.com/paper/1704.07223/) (2017)
- [Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand](https://mlsanity.com/paper/2103.16084/) (2021)
- [Low-rank updates of matrix functions](https://mlsanity.com/paper/1707.03045/) (2017)
- [An Improved Algorithm for Learning Drifting Discrete Distributions](https://mlsanity.com/paper/2403.05446/) (2024)

## Abstract (arXiv)

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(sumi=1mαi) on the cost of estimating a sequence of length m. This improves upon the previous implicit trace estimation bound of mathcal O(m·maxiα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.