⚡ electrical engineering

A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems

This paper introduces a memory-efficient unified online algorithm for predicting general unknown linear dynamical systems that achieves sublinear regret with a parameter count scaling only with the system's intrinsic instability complexity ( $k$ ) rather than its full dimension, a regime where stabilization is feasible and which is proven to be a fundamental lower bound for filter-based predictors.

Original authors: Yuval Ran-Milo, Angelos Assos, Elad Hazan

Published 2026-07-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuval Ran-Milo, Angelos Assos, Elad Hazan

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

The Big Picture: Predicting the Unpredictable

Imagine you are trying to predict the path of a ball rolling down a hill. If the hill is smooth and flat (a stable system), it's easy to guess where the ball will go next. You just need a simple rule: "It rolls forward."

But what if the hill is bumpy, has a few steep cliffs, and maybe even a few spots where the ball might suddenly shoot upward (an unstable system)? Predicting the ball's path becomes a nightmare.

In the world of engineering and control theory, this "ball" is a Linear Dynamical System (LDS). These are mathematical models used to describe everything from the temperature in a room to the movement of a robot arm. The goal of this paper is to build a "super-predictor" that can guess the future of these systems, even when they are unstable, without needing a supercomputer to do the math.

The Problem: The "Memory" Trap

To predict the future of a system, you usually need to remember its past.

The Old Way (The Library of Babel): Previous methods tried to remember everything. If a system had 500 hidden variables (like 500 different gears turning), the predictor needed to store information about all 500 gears. This is like trying to memorize every book in a massive library just to predict the weather. It's slow, expensive, and requires too much memory.
The Limitation: Some systems are mostly stable (99% of the gears are fine), but they have a few "rogue" gears that spin wildly or get stuck. Old methods couldn't ignore the 497 good gears; they had to track all 500, wasting energy on the easy parts while struggling with the hard ones.

The Solution: The "Instability Complexity" (The $k$ Factor)

The authors realized that you don't need to remember the whole library. You only need to remember the troublemakers.

They introduced a concept called Instability Complexity, which they call $k$ .

Think of $k$ as the number of "rogue gears" in your machine.
Maybe you have a machine with 1,000 parts, but only 3 of them are unstable or weird. In this case, $k = 3$ .
The rest of the 997 parts are well-behaved and predictable.

The paper argues that if you focus only on those $k$ troublemakers, you can predict the whole system's future with a tiny amount of memory, regardless of whether the machine has 10 parts or 10,000 parts.

The Unified Algorithm: The "Swiss Army Knife" Predictor

The authors built a new algorithm (Algorithm 1) that acts like a Swiss Army knife. It combines three different tools into one package to handle every type of system:

The Spectral Filter (The Long-Range Telescope): This tool is great for the "stable" parts of the system. It looks at the distant past to see patterns that repeat slowly. It's very efficient and doesn't care how big the system is.
The Finite-Memory Filter (The Short-Term Memory): This tool looks at the very recent past (the last few seconds). It's perfect for parts of the system that settle down quickly.
The Autoregressive Correction (The "Rogue Gear" Specialist): This is the new, special part. It focuses only on the $k$ unstable or weird modes. It uses a small amount of memory to track exactly those few difficult parts.

How they work together:
Imagine you are driving a car.

The Spectral Filter is your knowledge of the road layout (the stable part).
The Finite-Memory Filter is your reaction to the car in front of you (the fast-decaying part).
The Autoregressive Correction is your hand on the steering wheel, making tiny, precise adjustments because the car has a slightly wobbly wheel (the $k$ unstable modes).

By combining these, the algorithm predicts the future with high accuracy, but its "memory footprint" (the number of things it needs to remember) depends only on $k$ , not on the total size of the system.

Why This Matters: The "Explosion" Warning

The paper also proves a scary but important fact: If you have too many unstable gears ( $k$ is large), you can't control the system at all.

They show that if a system has many "exploding" modes, the control inputs required to keep it stable would need to be impossibly precise. It would be like trying to balance a stack of 100 falling dominos by blowing on them; you'd need to blow with such varying intensity (from a whisper to a hurricane) that no real machine could do it.

Therefore, the only systems that are worth trying to control are the ones where $k$ is small. This validates the authors' approach: their algorithm is designed exactly for the "controllable" world.

The Proof: Experiments

To prove this works, the authors tested their algorithm on a massive system with 503 dimensions (503 hidden variables), but only 3 unstable modes ( $k=3$ ).

They compared their "Unified Predictor" against three other methods:

Spectral Filtering alone: Failed because it couldn't handle the unstable modes.
Autoregressive (AR) alone: Failed because it tried to remember all 503 variables, wasting memory.
Finite-Memory alone: Failed because it couldn't see far enough into the past.

The Result: The Unified Predictor was orders of magnitude more accurate than the others, even though it used the exact same amount of "learning parameters" (memory). It successfully ignored the 500 boring parts and focused entirely on the 3 tricky ones.

Summary

The Goal: Predict the future of complex, unstable machines.
The Problem: Old methods try to remember everything, which is too heavy.
The Insight: You only need to remember the few "unstable" parts ( $k$ ).
The Tool: A new algorithm that mixes three prediction styles to focus only on the troublemakers.
The Result: It predicts better than anyone else, using a tiny amount of memory, proving that for control to be possible, the "instability complexity" must be low.

Technical Summary: A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems

1. Problem Statement

The paper addresses the challenge of online prediction for unknown Linear Dynamical Systems (LDS) with the ultimate goal of facilitating system stabilization. The core problem is to design an algorithm that observes inputs ( $u_t$ ) and outputs ( $y_t$ ) sequentially and predicts the next output ( $\hat{y}_t$ ) with sublinear regret against the best possible LDS predictor in hindsight.

A critical constraint in this work is memory efficiency. Existing methods face a dichotomy:

Spectral filtering: Achieves dimension-free memory but fails on systems with unstable, complex, or non-semisimple modes.
Autoregressive (AR) and System Identification: Can represent any observable LDS exactly but require a memory footprint proportional to the full hidden-state dimension $d$ , which is inefficient when $d$ is large but the system's "hard" dynamics are few.

The authors focus on a practically relevant regime: systems where the open-loop dynamics may be unstable, yet the chosen input sequence keeps the realized trajectory bounded. The goal is to achieve sublinear regret with a parameter count that adapts to the instability complexity ( $k$ ) rather than the full state dimension $d$ .

2. Methodology

2.1 Instability Complexity ( $k$ )

The authors define a new complexity measure, instability complexity $k$ , which counts the number of eigenvalues that are difficult to learn or control. Specifically, $k$ is the count of eigenvalues that either:

Lie outside the interval $(-1, 1)$ (unstable) or are close to the boundary ( $|\lambda| > 1 - 1/\log(k+2)$ ).
Are non-semisimple (associated with Jordan blocks of size $>1$ ).

All other eigenvalues are considered "easy" (strictly stable, semisimple, and rapidly decaying).

2.2 The Unified Predictor Class

The paper constructs a hybrid predictor class that combines three distinct approximation strategies to handle different spectral components of the LDS:

Spectral Filters: Used for the "spectral group" of real, semisimple modes that are stable but decay slowly (near the unit circle). This component is independent of $d$ .
Finite-Memory Input Filters (FIR): Used for strictly stable, semisimple modes that decay rapidly. This component is also independent of $d$ .
Autoregressive (AR) Correction: Used for the $k$ "hard" modes (unstable, non-semisimple, or near-boundary). This component captures the exact dynamics of these exceptional modes but is limited to order $k$ .

Theorem 6 (Approximation): The paper proves that any LDS with instability complexity $k$ can be approximated to arbitrary accuracy $\epsilon$ using a predictor with $O(k \cdot \text{polylog}(T, k, 1/\epsilon))$ parameters. This count depends linearly on $k$ and logarithmically on $T$ , but is independent of the state dimension $d$ .

2.3 The Unified Algorithm (Algorithm 1)

The learning algorithm operates online using the Vovk–Azoury–Warmuth (VAW) forecaster.

Feature Vector: At each time step $t$ $t$ , the feature vector combines:
- $k$ autoregressive output lags ( $y_{t-1}, \dots, y_{t-k}$ ).
- A finite-memory input window of length $L+k+1$ .
- Spectral filter features derived from the current input history.
Learning: The algorithm maintains $p$ copies of the VAW forecaster (one for each output coordinate) to learn the coefficients of the unified predictor.
Regret: The algorithm achieves a cumulative squared loss of $O(k^2 \log^3(k) \log^3(T))$ , resulting in an average regret that vanishes as $T \to \infty$ .

3. Key Contributions and Results

3.1 Theoretical Guarantees

Sublinear Regret with Low Memory: The unified algorithm achieves sublinear regret with a learnable parameter count of $\tilde{O}(k)$ , significantly improving upon AR methods that scale with $d$ .
Lower Bound on Filter Count: The paper establishes that the dependence on $k$ is unavoidable. Proposition 11 proves that any filter-based predictor with bounded coefficient mass requires at least $k$ filter directions to achieve sublinear regret. This validates $k$ as a fundamental complexity measure for this problem.

3.2 Practical Motivation: Controllability

The paper argues that the regime of small $k$ is not just a mathematical convenience but a practical necessity for stabilization.

Proposition 9: For a broad class of scalar-input diagonalizable systems with many exploding modes (large $k$ ), any stabilizing input sequence must have an Input Dynamic Range (IDR) that grows exponentially with $k$ .
Implication: Systems with large $k$ are essentially uncontrollable in practice due to extreme sensitivity to noise, actuator limits, and finite precision. Therefore, the setting where $k \ll d$ is the primary regime where stabilization is plausible, making the proposed memory-efficient predictor highly relevant.

3.3 Experimental Validation

Experiments were conducted on a high-dimensional system ( $d=503$ ) with small instability complexity ( $k=3$ ), containing one exploding mode and one slow complex pair.

Setup: The unified predictor was compared against pure Finite-Memory, pure Autoregressive, and pure Spectral Filtering predictors, all constrained to the same number of learned parameters (16).
Result: The unified predictor achieved orders-of-magnitude lower normalized mean-squared error (best seed: $7.88 \cdot 10^{-9}$ ) compared to the other methods (best seeds ranging from $10^{-5}$ to $10^{-1}$ ). This confirms that combining the three components allows the algorithm to capture the few "hard" modes without paying the cost of the full state dimension.

4. Significance and Limitations

Significance

The paper bridges a fundamental gap in online learning for control theory. It demonstrates that one does not need to identify the full system matrix (which scales with $d$ ) to predict well. Instead, by focusing on the instability complexity, one can construct a unified predictor that is:

General: Handles non-diagonalizable systems, complex eigenvalues, and exploding modes.
Efficient: Memory footprint scales with the intrinsic difficulty of the system ( $k$ ), not its size ( $d$ ).
Necessary: Theoretical lower bounds show that this dependence on $k$ is unavoidable for filter-based methods.

Limitations

The authors explicitly note the following limitations:

Prediction vs. Control: The current results are strictly for prediction. While prediction is a prerequisite for stabilization, the paper does not provide a closed-loop control policy or prove that these regret guarantees directly translate to control objectives (e.g., keeping the system bounded).
Optimality: The upper and lower bounds on the parameter count match up to polylogarithmic factors. The optimal logarithmic dependence and sharp regret constants remain open questions.
Assumptions: The results rely on the assumption that the input sequence keeps the system outputs bounded (Assumption 2).

In summary, this work provides a theoretically grounded, memory-efficient framework for online prediction of general LDS, identifying the instability complexity $k$ as the correct parameter for measuring system difficulty in the context of stabilization.