Technical Summary: AdaKoop

Problem Definition

The paper addresses the challenge of modeling complex nonlinear dynamics within nonstationary data streams under strict computational and latency constraints. Real-world applications, such as precipitation nowcasting and wearable health monitoring, generate semi-infinite time series where statistical properties change continuously or abruptly. Existing methods face two primary limitations:

1. Nonlinearity: Real-world dynamics (e.g., Lorenz systems, chaotic physiological signals) are too complex for simple linear models. While deep learning and polynomial regressions exist, they often require computationally intensive optimization or are highly sensitive to noise, making them suboptimal for single-pass stream processing.
2. Nonstationarity: Data streams exhibit concept drift due to external influences or mechanism shifts. Models trained on historical data degrade as patterns change. Most state-of-the-art time series forecasting methods focus on offline optimization and lack the ability to adaptively handle time-varying patterns in a streaming fashion.

The core problem is defined as: How to estimate complex nonlinear dynamics while remaining computationally efficient enough to quickly adapt to both continuous and abrupt changes in a nonstationary data stream?

Methodology: AdaKoop

The authors propose AdaKoop, an efficient streaming algorithm that bridges nonlinear complexity and computational tractability using Koopman Operator Theory (KOT).

1. Probabilistic Dual-View State Space Model

Instead of modeling nonlinear transitions directly, AdaKoop lifts the state space to a higher-dimensional feature space where dynamics become linear.

• Dual-View Formulation: The model treats both raw observations ($x_t$) and Reproducing Kernel Hilbert Space (RKHS) features ($\psi(x_t)$) as emissions from a shared, low-dimensional latent linear dynamical system ($z_t$).
• Linear Representation: The system is governed by:
  • $z_{t+1} = Az_t + \xi_t$ (Linear latent transition)
  • $y_t = Hz_t + \eta_t$ (Augmented observation, where $y_t = [x_t, \psi(x_t)]^T$)
• Advantage: This formulation allows complex nonlinear dynamics to be expressed as a tractable linear system, enabling stable modeling via closed-form updates rather than iterative nonlinear optimization.

2. Static Optimization Framework

To initialize and refine model parameters ($\Theta$) for a specific dynamic pattern, AdaKoop employs a three-stage static optimization:

• Feature Space Basis Orthogonalization: To ensure computational stability and avoid redundancy in the RKHS, the algorithm maintains a sparse dictionary of selected observations. It uses a threshold-based criterion (based on the residual error of projecting new points onto the current dictionary) to add or reject data points, effectively constructing a finite-dimensional feature space.
• Regression-Based Initialization: The model parameters are initialized using Reduced Rank Regression (RRR) on the feature matrices. This provides a spectral initialization for the latent transition matrix ($A$) and observation matrices ($C, W$), serving as a "warm start" to avoid local optima.
• Probabilistic Refinement: The initialized parameters are refined using the Expectation-Maximization (EM) algorithm. The E-step uses Kalman filtering and Rauch–Tung–Striebel (RTS) smoothing to infer latent states, while the M-step updates parameters in closed form to maximize marginal likelihood.

3. Streaming Algorithm for Nonstationarity

To handle the semi-infinite nature of data streams, AdaKoop integrates the static optimizer into a streaming loop with two adaptive mechanisms:

• Statistical Hypothesis Testing for Switching: The algorithm monitors the Normalized Innovation Squared (NIS) derived from the Kalman filter. Using a one-sided CUSUM test, it detects abrupt shifts in the data distribution. If the current model's NIS exceeds a threshold, the algorithm searches a repository of stored models ($\Theta$) to find the best fit for the current window. If no existing model fits, a new model is trained via static optimization and added to the repository.
• Adaptive Parameter Updates: For continuous changes, the selected model undergoes recursive updates using an online EM algorithm with a forgetting factor ($\gamma$). This updates sufficient statistics ($S_1, S_2, S_3$) and model parameters in constant time relative to the stream length.
• Forecasting: Future values are predicted by projecting the current latent state forward using the linear transition matrix $A$, then mapping back to the observation space via $C$.

Key Contributions

1. Probabilistic Dual-View Model: Introduction of a state space model that treats raw observations and RKHS features as emissions from a shared latent linear system, enabling stable and efficient modeling of nonlinear dynamics.
2. AdaKoop Algorithm: An efficient streaming algorithm with constant time complexity per process (independent of stream length) that handles time-varying nonlinear dynamics. It combines statistical hypothesis testing for abrupt change detection with closed-form updates for continuous adaptation.
3. Empirical Validation: Extensive experiments on 71 practical benchmark datasets (from the dysts benchmark) demonstrating superior performance over state-of-the-art methods in both forecasting accuracy and computational efficiency.

Experimental Results

The authors evaluated AdaKoop against seven baselines, including deep learning models (OneNet, PAttn, WPMixer), streaming methods (ModePlait, sKAF), and Koopman-based approaches (Koopa).

• Accuracy: AdaKoop achieved the lowest Mean Squared Error (MSE) and Mean Absolute Error (MAE) across 20, 25, and 30-step-ahead forecasting tasks. For instance, at 20 steps, AdaKoop achieved an MSE of 0.0763, significantly outperforming the next best method (ModePlait at 0.279). The results indicate that deep learning models degrade on datasets with distinct dynamic patterns due to a lack of adaptability, while AdaKoop's adaptive switching maintains high accuracy.
• Scalability: Computational time analysis showed that AdaKoop's wall-clock time remains constant as the data stream length increases, whereas methods like OneNet (which uses two complementary models) and ModePlait (which discovers causal relationships) exhibit higher computational costs.
• Nonlinear Capability: Experiments with different kernel functions confirmed that the RBF kernel (an infinite-dimensional kernel) yields the best performance, validating the necessity of the RKHS framework for capturing complex nonlinearities. Linear and sigmoid kernels performed poorly, failing to capture the underlying dynamics.
• Sensitivity: The algorithm is sensitive to the forgetting factor ($\gamma$) and the dictionary threshold ($\nu$). Optimal performance was found with $\gamma \in [10^{-3}, 10^{-2}]$, balancing adaptation speed and stability.

Significance and Claims

The paper claims that AdaKoop successfully bridges the gap between the theoretical expressiveness of Koopman operator theory and the practical constraints of real-time data stream processing. By transforming nonlinear dynamics into a tractable linear system via a probabilistic dual-view framework, AdaKoop avoids the prohibitive costs of iterative nonlinear optimization.

The authors emphasize that their approach is scalable for semi-infinite data streams because its computational complexity does not grow with the history length of the data. The method is presented as a robust solution for real-time forecasting in nonstationary environments, offering a significant improvement in both accuracy and efficiency over existing state-of-the-art methods. The work is positioned as a practical tool for applications requiring rapid adaptation to changing dynamic patterns, such as environmental monitoring and health analytics.