🤖 machine learning

Dynamic estimation of slowly varying sequences

This paper introduces a general, adaptive framework and a novel algorithm for dynamically estimating slowly varying sequences that improves upon prior state-of-the-art cost bounds by scaling the estimation budget with local variations and enabling on-the-fly change detection without significant overhead.

Original authors: Prashant Gokhale, Mikhail Khodak, Sandeep Silwal

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Prashant Gokhale, Mikhail Khodak, Sandeep Silwal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to keep a running score of a game that is changing very slowly over time. Every day, the game board shifts just a tiny bit. Your job is to estimate the total score of the board every single day, but you have a limited budget of "energy" (or computer time) to do the calculations.

In the past, if you wanted to be safe, you would assume the game board might change drastically every single day. So, you would spend a huge amount of energy re-calculating the entire score from scratch every morning. This is safe, but incredibly wasteful, especially if the board barely moved that day.

This paper introduces a smarter way to play the game. It's like having a smart assistant that knows: "Hey, the board only moved a tiny bit today, so I don't need to re-calculate everything. I'll just update the parts that changed."

Here is the breakdown of their idea using simple analogies:

1. The Problem: The "All-or-Nothing" Approach

Imagine you are tracking the temperature of a room.

The Old Way: Every morning, you walk outside, measure the temperature of every single spot in the room, and calculate the average again. Even if the room hasn't changed at all since yesterday, you do the full work. If you do this for 100 days, you've done 100 full days of work.
The Paper's Insight: If the room only got 1 degree warmer, you don't need to re-measure the whole room. You just need to measure the difference (the 1 degree change) and add it to yesterday's number.

2. The Solution: The "Adaptive Budget"

The authors created a framework (a set of rules) for this "smart assistant."

Dynamic Scaling: The assistant looks at how much the system changed today (let's call this the "step size").
- If the change was huge (a storm blew in), the assistant spends a lot of energy to get a precise new measurement.
- If the change was tiny (a gentle breeze), the assistant spends very little energy, just checking the small difference.
The Result: Instead of the cost being based on the worst possible day (which might never happen), the total cost is based on the sum of all the small changes. If the system is mostly stable with only a few big jumps, you save a massive amount of energy.

3. The "Magic Trick": Guessing the Change

Usually, to know how much energy to spend, you need to know exactly how much the system changed before you start measuring. But what if you don't know that?

The paper shows a clever trick: You can spend a tiny, almost free amount of energy to get a "rough guess" of how much the system changed.
Even if this guess isn't perfect, it's good enough to tell the assistant whether to spend a little or a lot of energy. This allows the system to work even when you don't have a crystal ball.

4. Where This Works (The Applications)

The paper proves this "smart assistant" works for many different types of problems, not just one:

Matrix Traces (The "Hidden Sum"): In math and AI, matrices are giant grids of numbers. Sometimes you need the sum of the numbers on the diagonal (the trace). This is crucial for understanding how neural networks learn. The paper shows how to track this sum as the network trains, saving huge amounts of computer time.
Spectral Density (The "Sound of the System"): This is about understanding the "vibrations" or frequencies of a system. The paper shows how to track these frequencies as they slowly shift.
Monte Carlo Integration (The "Average Guess"): Imagine trying to guess the average height of people in a city by asking a few random people. If the city's population changes slowly, you don't need to ask 1,000 new people every day. You just ask a few to see how the average shifted.
Solving Physics Equations (The "Dirichlet Problem"): This is about predicting how heat or electricity spreads through a shape. If the boundary of the shape changes slowly, the paper shows how to update the prediction efficiently without re-solving the whole physics problem from scratch.

5. The Proof: Real-World Tests

The authors didn't just do the math; they tested it.

Synthetic Tests: They created fake data where the system was mostly stable but had a few "bursts" of big changes. Their method used significantly fewer computer resources (queries) than the old "worst-case" method.
Real AI Tests: They applied this to a real neural network training on a computer. As the network learned, the "Hessian" (a complex math object describing the network's shape) changed slowly. Their method tracked this shape efficiently, saving time compared to the standard method, especially during the quiet periods between big learning jumps.

Summary

Think of this paper as a budget-conscious accountant for dynamic systems.

Old Method: "I don't know if the numbers changed, so I'll re-count the whole vault every day." (Expensive, wasteful).
New Method: "I'll check how much the numbers moved. If it's a penny, I'll spend a penny to check. If it's a million dollars, I'll spend a million. My total cost is exactly what I needed to spend, no more, no less."

This makes it possible to track complex, evolving systems (like AI models or physical simulations) much faster and cheaper, provided the system doesn't change wildly every single second.

Technical Summary: Dynamic Estimation of Slowly Varying Sequences

Problem Statement

The paper addresses the problem of sequentially approximating functions of elements in a slowly varying sequence. Specifically, given a sequence of states $v_1, \dots, v_m$ in a normed vector space $V$ , where the distance between consecutive elements is bounded by a local step size $\alpha_t = \|v_t - v_{t-1}\|_V$ , the goal is to maintain estimates $\tilde{L}_t$ of a linear map $L(v_t)$ (or certain nonlinear functions reducible to such) with additive error $\epsilon$ at every step $t$ . The objective is to minimize the total cumulative sample complexity (e.g., number of queries or function evaluations) required to guarantee these bounds with high probability.

This setting arises in various contexts, including estimating evolving probability distributions, tracking metrics on dynamic social networks, maintaining statistics of drifting data streams, and tracking loss curvature during neural network optimization. A representative instance is implicit trace estimation, where one has matrix-vector product (MVP) access to a sequence of matrices and wishes to track their traces.

Methodology

1. General Adaptive Framework

The authors propose a general framework that accepts a "well-concentrated" static estimator and dynamically adjusts the query budget based on the local change $\alpha_t$ .

Well-Concentrated Estimator: The framework assumes the existence of a randomized static estimator $E(v, k)$ for a linear map $L$ that is unbiased and exhibits sub-exponential concentration. Specifically, the error parameters (variance $\nu$ and scale $\beta$ ) must scale with the norm of the input $v$ and the inverse of the sample budget $k$ (e.g., $\nu \propto \|v\|/\sqrt{k}$ ).
Adaptive Update Mechanism: Instead of recomputing the estimate from scratch at every step (which incurs a cost proportional to $m$ $m$ ), the algorithm updates the running estimate by:
1. Damping: Scaling the previous estimate $\tilde{L}_{t-1}$ by a factor $(1-\gamma_t)$ , where $\gamma_t$ is related to the step size.
2. Residual Estimation: Estimating the "residual" state $u_t = v_t - (1-\gamma_t)v_{t-1}$ using a fresh sample budget $k_t$ .
3. Recombination: The new estimate is $\tilde{L}_t = (1-\gamma_t)\tilde{L}_{t-1} + \hat{L}_t$ , where $\hat{L}_t$ is the estimate of the residual.
Budget Scaling: Crucially, the local sample budget $k_t$ is scaled proportionally to the local step size $\alpha_t$ . This ensures that when the sequence is stable ( $\alpha_t$ is small), the algorithm spends very few resources, whereas it allocates more resources only when significant changes occur.

2. Handling Unknown Step Sizes

In many practical scenarios, the exact step size $\alpha_t$ is unknown. The authors introduce a two-phase approach:

Norm Estimation Oracle: A lightweight procedure estimates the magnitude of the change $\alpha_t$ on-the-fly using a constant number of queries (independent of $\epsilon$ in many cases).
Proxy Step Size: This estimate is used as a proxy $\tilde{\alpha}_t$ to set the parameters for the main adaptive algorithm. Theoretical analysis shows that approximating $\alpha_t$ within a constant factor is sufficient to maintain correctness with only a constant factor increase in sample complexity.

Key Contributions

General-Purpose Adaptive Framework: The paper introduces a meta-algorithm for sequential stochastic approximation that works for diverse vector spaces (e.g., matrices, $L_\infty$ functions) and both linear and nonlinear maps (via reduction).
Improved Complexity Bounds: The primary theoretical contribution is a query complexity bound that scales with the sum of local changes $\sum_{t=2}^m \alpha_t$ , rather than the worst-case bound $m \cdot \max_t \alpha_i$ used in prior works (e.g., Dharangutte & Musco, 2021). This results in a "path-length-style" bound $O(\sum \alpha_i)$ , which is significantly sharper for sequences with rare bursts of change.
On-the-Fly Estimation: The paper demonstrates how to estimate step sizes dynamically with (nearly) no added cost, removing the assumption that a global bound on $\alpha_i$ is known a priori.
Diverse Applications: The framework is applied to:
- Dynamic Trace Estimation: Improving upon state-of-the-art bounds for matrix traces.
- Matrix Powers: Tracking $\text{tr}(A_t^k)$ by showing that powers of slowly varying matrices also evolve slowly.
- Spectral Density Estimation: Estimating eigenvalue distributions by tracking spectral moments.
- Monte Carlo Integration: Maintaining estimates of integrals for evolving functions.
- Dirichlet Problems: Solving boundary value problems for PDEs with changing boundary conditions.

Results

Theoretical Results

Theorem 1 (Known Step Sizes): For a sequence of length $m$ with step sizes $\alpha_t$ , the total sample complexity is bounded by $O\left( \left(\frac{1}{\epsilon^2} + \frac{1}{\epsilon}\right) \log(m/\delta) (1 + \sum \alpha_t) \right)$ . This improves upon the $O(m \cdot \max \alpha_t)$ baseline.
Theorem 2 (Unknown Step Sizes): The two-phase algorithm achieves the same complexity bounds up to an additive overhead of $\sum k_{norm}$ , where $k_{norm}$ is the cost of estimating the step size.
Corollaries: Specific bounds are derived for matrix powers (scaling with $k \sum \alpha_t$ ), spectral density (scaling with $e^{O(1/\epsilon)} \sum \alpha_t$ ), and Monte Carlo integration.

Empirical Results

The authors validate their approach through experiments:

Synthetic Matrices: On a sequence of $2000 \times 2000$ matrices with rare, large perturbations, the adaptive algorithm significantly reduces the cumulative Matrix-Vector Product (MVP) cost compared to a fixed-budget baseline (DeltaShift).
Pareto Frontier: The adaptive method achieves strictly lower errors (Maximum, Mean, and Weighted Mean) for equivalent computational budgets.
Neural Network Training: In tracking the Hessian trace during SGD with Warm Restarts (SGDR), the adaptive method dynamically reduces queries during stable periods and increases them during restarts (where the Hessian changes rapidly), maintaining error levels comparable to the baseline but with lower total cost.

Significance and Claims

The paper claims to make the sequential approximation toolkit general-purpose and adaptive. By shifting the complexity dependence from the worst-case step size to the cumulative path length of changes, the framework offers a more efficient solution for "stable sequences with rare bursts," a common pattern in real-world dynamic systems.

The authors emphasize that their approach:

Generalizes previous implicit trace estimation results to a broad class of linear and nonlinear problems.
Adapts to the actual dynamics of the system without requiring prior knowledge of the maximum change.
Improves upon state-of-the-art guarantees for dynamic trace estimation, providing a theoretical foundation for why reusing past queries is effective when changes are small.

The work does not claim to solve all dynamic estimation problems but provides a robust framework for any setting where a well-concentrated static estimator exists and the underlying sequence evolves slowly.