Dynamic estimation of slowly varying sequences

In many scientific and engineering fields, such as neural network optimization or dynamic graph analysis, one must track properties of a system that evolves over time. When the system changes slowly—meaning the distance between consecutive states is small—it is inefficient to recompute estimates from scratch at every step. This paper asks: how can we develop a general, adaptive framework to minimize the total computational cost of maintaining these estimates while providing strong theoretical guarantees?

The authors propose a meta-algorithm for sequential stochastic approximation. Instead of recomputing estimates, the algorithm maintains a running estimate by sampling only the 'residual' (the difference between consecutive states) and reusing past information. By dynamically scaling the estimation budget based on the local change between steps, the algorithm achieves a total sample complexity that scales with the path-length of the sequence (the sum of local changes) rather than the product of the sequence length and the maximum local change. The authors also provide a two-phase procedure that estimates these local changes on-the-fly, removing the need for a known global bound on the system's evolution.

The framework provides a unified approach to dynamic estimation. For trace estimation, the authors improve the previous query complexity bound of O(m * max(α_i)) to O(Σ α_i), where α_i represents the local change. They demonstrate that this framework is broadly applicable, deriving novel results for:

• Matrix powers and spectral densities.
• Monte Carlo integration.
• Boundary value problems in PDEs.

Empirical results on synthetic matrix sequences and neural network Hessian trajectories confirm that the algorithm is significantly more efficient than static baselines, especially when the sequence is stable with only rare bursts of change.