Online Bootstrap Inference for the Trend of Nonstationary Time Series

Thomas Nagler, Tobias Brock, Nicolai PalmarXiv 2026 · DOI · arXiv

TL;DR

This paper introduces a scalable, online bootstrap method for calculating real-time confidence intervals for trends in nonstationary data streams. By using an autoregressive resampling scheme with $O(1)$ time and memory complexity, the authors provide a way to perform reliable statistical inference (like anomaly detection or A/B testing) on live data without assuming the world stands still.

What Problem Does This Paper Address?

In the world of streaming data—think heart rate monitors, financial tickers, or industrial sensors—we often use "smoothers" like Exponentially Weighted Moving Averages (EWMA) to track the underlying trend. While we are great at estimating these trends, we are surprisingly bad at quantifying our uncertainty about them in real-time.

Standard statistical tools (like the classic bootstrap) are "offline" and "batch-oriented," meaning they require re-processing old data, which is too slow and memory-intensive for a high-speed stream. Furthermore, most existing methods assume stationarity (the statistical properties don't change over time) and independence (data points don't influence each other). In reality, data streams are often nonstationary—trends shift, seasonality kicks in, and shocks happen—and highly correlated. This paper fills the gap by providing a "uniform-in-time" inference framework that handles these real-world complexities while remaining computationally "cheap."

Methods

The authors propose an Online Nonstationary AR-Bootstrap. The algorithm works in three main layers:

  1. The Estimator: It targets a broad class of level estimators that can be written as weighted averages (like EWMA or Brown’s double exponential smoothing).
  2. The Bootstrap Engine: Instead of resampling data points, it generates "bootstrap replicates" of the estimation error using autoregressive Gaussian multipliers.
  3. Innovation: To handle non-Gaussian noise, they apply a heavy-tailed transformation ($T$) to these multipliers.
  4. Local Adaptation: They center bootstrap innovations on the lagged smoother ($\hat{\mu}_\eta(t-1)$), which allows the variance estimate to respond quickly to sudden shifts in the trend.
  5. Calibration: To ensure "uniform-in-time" validity (meaning the confidence band is valid over a whole interval, not just at a single point), they partition time into blocks of increasing length. They use data from past blocks to recalibrate the "critical values" (the width of the bands) for the next block.

Crucially, every update happens in $O(1)$ time and memory, meaning the cost per new data point doesn't increase as the stream grows.

Datasets

The paper evaluates the method using several simulated Data Generating Processes (DGPs) designed to mimic real-world challenges:

  • Stationary AR(1): A baseline with serial dependence but no trend shift.
  • Trend + Seasonality: A linear trend combined with a sine-wave seasonal component.
  • Trend + Shocks: A linear trend interrupted by random, sudden jumps (shocks).
  • Heart Rate Proxy: The authors use the example of heart rate monitoring to motivate the nonstationary scenarios.

No specific real-world benchmark datasets were introduced, as the focus is on the theoretical and algorithmic framework.

Key Insights and Ideas

  • The "Effective Sample Size" ($\nu_\eta$): In a stream, the total number of observations ($n$) is less important than the "effective" number of samples currently influencing the smoother. The authors show that uncertainty scales with $1/\sqrt{\nu_\eta}$.
  • Uniformity is Hard: Pointwise confidence intervals are often "violated" simply because you are checking them thousands of times. By using a block-based recalibration and union bounds, this method provides "confidence bands" that remain valid even under continuous monitoring.
  • Robustness via Transformation: The use of a Student-t transformation ($T$) on Gaussian multipliers is a clever "small-sample correction." It prevents the bootstrap from being too optimistic when the smoothing window is small or the noise is "spiky."
  • Centering Matters: Traditional bootstraps center on the global mean. In nonstationary streams, centering on the previous smoothed estimate is the "secret sauce" that allows the model to adapt to local changes without losing track of the overall trend.

Key Results

  • Coverage Accuracy: In simulations (Figure 2), the proposed method ("ours") maintained a uniform coverage near the target 90% across stationary, seasonal, and shock-heavy scenarios.
  • Comparison to Baselines: Standard "iid" bootstraps and existing martingale-based confidence sequences (WS) suffered from severe undercoverage (often dropping to 0-40% coverage) because they couldn't account for the temporal dependence in the data.
  • Power: The method detects non-constant trends (jumps or slopes) very quickly. As the trend slope ($a$) increases, the "power" to reject the null hypothesis of a flat trend approaches 1.0 almost immediately after the burn-in period.
  • Efficiency: The $O(1)$ complexity was verified, showing stable performance even as the series length reached $n=5000$.

Limitations and Future Work

  • Conservatism: Under very strong, rapidly changing trends, the bootstrap variance can become an overestimate, leading to "over-conservative" (wider than necessary) confidence bands. The authors acknowledge this is a trade-off for maintaining validity under general nonstationarity.
  • Asymptotic Reliance: The formal proofs rely on the effective sample size ($\nu_\eta$) being relatively large. While the small-sample corrections help, performance may still degrade if the smoothing is extremely aggressive (very small $\nu_\eta$).
  • Integration: The authors suggest future work should integrate this bootstrap scheme with modern online learning techniques like Online Gradient Descent or Bandit algorithms to create self-correcting, uncertainty-aware autonomous systems.

Summary updated

Abstract

This article proposes an online bootstrap scheme for nonparametric level estimation in nonstationary time series. Our approach applies to a broad class of level estimators expressible as weighted sample averages over time windows, including exponential smoothing methods and moving averages. The bootstrap procedure is motivated by asymptotic arguments and provides well-calibrated uniform-in-time coverage, enabling scalable uncertainty quantification in streaming or large-scale time-series settings. This makes the method suitable for tasks such as adaptive anomaly detection, online monitoring, or streaming A/B testing. Simulation studies demonstrate good finite-sample performance of our method across a range of nonstationary scenarios. In summary, this offers a practical resampling framework that complements online trend estimation with reliable statistical inference.
BibTeX
@misc{nagler2026online,
  author = {Thomas Nagler and Tobias Brock and Nicolai Palm},
  title = {{Online Bootstrap Inference for the Trend of Nonstationary Time Series}},
  year = {2026},
  eprint = {2602.23911},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.23911},
}
Figure