Dynamic estimation of slowly varying sequences
cs.LG, cs.DS
Submitted: 2026-06-22
Updated: 2026-11-02
Comments: Preprint. 14 pages, 4 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: We consider the problem of sequentially approximating a target function of each element in a slowly-varying sequence, i.e.
Terminology
Abstract
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 O (1 ε 2 sum from i=1 to m α i) on the cost of estimating a sequence of length m to accuracy ε. This improves upon the earlier implicit trace estimation dependence on m ε 2 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.
Sources
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis