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

arXiv:2607.02050 · cs.LG, cs.SY, eess.SY · Submitted 2026-07-02 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems".

Jane: Here's the gist of the paper. A unified online algorithm is introduced to handle every linear dynamical system (LDS) with a learnable parameter count that adapts to the intrinsic complexity of its dynamics rather than the full hidden-state dimension, achieving sublinear regret in the practically central regime where instability complexity is small.

Tom: The Problem and Motivation The primary motivation for this work is achieving sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics rather than the full hidden-state dimension.

Jane: The focus is on systems with few modes that are unstable, non-semisimple, or not rapidly decaying, which is considered the primary setting in which stabilization is plausible.

Tom: Existing predictors fall into three families—spectral filtering, finite-memory input filters (FIR), and autoregressive (AR) predictors—none of which alone handles the mixed case of systems with many decaying modes and few hard ones.

Paper summary: Tom: So, wrapping up this discussion on "A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems." The authors are showing that by combining spectral filtering, finite-memory filters, and autoregressive predictors into one class of predictor with only O(k) parameters, they can achieve sublinear regret in this small instability complexity setting <ref:2607.02050#pg1>.

Jane: The implication for us is that we don't have to use memory that scales with the entire state space d if we are working with systems where the instability is localized to a small number of modes, k <ref:2607.02050#pg1>.

Lu: They explicitly state that this unified algorithm handles ever class of systems with many exploding modes being essentially impossible to keep bounded in practice <ref:2607.02050#pg2>, which makes the small-k regime even more important <ref:2607.02050#pg1>.

Meng: From a deployment standpoint, if we can control the memory cost by k instead of d, that drastically changes what we can actually run on real hardware <ref:2607.02050#pg1>.

Lalam: The final regret bound they derive is O(k plus L plus h) times log T times k plus L plus T h over k plus L plus h, which shows how the total error scales with time and complexity <ref:2607.02050#pg1>.

Tom: It's a sophisticated approach because they decompose the total loss into estimation error controlled by logarithmic regret in T and approximation error controlled by something else <ref:2607.02050#pg1>.

Jane: The main thing we learned is that prediction isn't always about needing to see every single part of the system at once; sometimes it’s just about capturing the few modes that are causing trouble <ref:2607.02050#pg1>.

Conclusion: Tom: So, this paper is about combining three different ways to predict how a linear system will behave online—spectral filtering, finite memory filters, and autoregressive predictors—into one single algorithm that uses way less memory than you'd think.

Jane: It sounds like they’ve managed to do something clever by cutting down the required parameters from depending on the whole hidden state dimension down to just dependent on a small number called k.

Lu: Exactly. They define this unified class of predictors using a feature vector that mixes spectral features, a finite window of past inputs, and some autoregressive lags, and it only needs O k times polylog T times k parameters in total.

Meng: That’s interesting because when we talk about deploying things on real hardware at scale, we usually have to worry about the full state dimension being huge. If this works by scaling with just k, that could make a massive difference for practical use cases.

Lalam: The theoretical guarantee they have is sublinear regret against the best possible predictor in hindsight, which means over a long time T, their total prediction error doesn't grow linearly with time.

Tom: That’s what we want to hear from an online learning algorithm, because if the error grows slower than linear in time, it means we can keep making good predictions indefinitely without needing more and more data.

Jane: It shows that you don't necessarily need to model every tiny detail of the system’s internal state when you are only interested in its main unstable modes.

Lu: The paper points out that this approach is most effective for systems where the instability complexity, k, is small compared to the total dimension d. That’s their main focus area.

Meng: So they aren't claiming this works for every single chaotic system out there, just the ones where you can actually manage it by focusing on those few unstable modes?

Tom: Right. And they give us a way to measure that complexity k through the required parameters of the filter itself, which is a smart way to characterize what makes a problem solvable.

Tel Aviv University · Princeton University

cs.LG, cs.SY, eess.SY

Submitted: 2026-07-02

Updated: 2026-11-05

Comments: 34 pages, 1 figure

Code: https://github.com/YuvMilo/UnifiedLearningLDS

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: A unified online algorithm is introduced to handle every linear dynamical system (LDS) with a learnable parameter count that adapts to the intrinsic complexity of its dynamics rather than the full…

Key concepts

Instability Complexity (k)
This is the intrinsic complexity of an LDS, representing the number of modes that are unstable or not rapidly decaying. The algorithm's memory and parameter count scale with this small number k rather than the entire hidden state dimension, making it efficient for systems where only a few modes cause instability.
Unified Algorithm Construction
The algorithm merges three predictor types: spectral filtering (for stable modes), finite-memory input filters (for fast decaying modes), and autoregressive predictors (to handle the k exceptional unstable modes). This combination allows the system to capture dynamics using only O(k · polylog(T, k)) parameters.
Sublinear Regret
This means the algorithm's cumulative prediction error grows slower than a linear rate with time (T). Specifically, the loss is bounded by O(k^2 log3(k) log3(T) / T), indicating that as time goes on, the average error converges to zero relative to the best possible predictor in hindsight.

Terminology

Summary

A unified online algorithm is introduced to handle every linear dynamical system (LDS) with a learnable parameter count that adapts to the intrinsic complexity of its dynamics rather than the full hidden-state dimension, achieving sublinear regret in the practically central regime where instability complexity is small. p. 0

Where the paper says it

A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems Yuval Ran-Milo∗ Tel Aviv University Angelos Assos∗ Princeton University Elad Hazan Princeton University Abstract Motivated by the challenge of stabilizing a general unknown linear dynamical system (LDS) from observations, we study the natural prerequisite of online prediction. Our goal is to achieve sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics rather than the full hidden-state dimension.

The Problem and Motivation

The primary motivation for this work is achieving sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics rather than the full hidden-state dimension. The focus is on systems with few modes that are unstable, non-semisimple, or not rapidly decaying, which is considered the primary setting in which stabilization is plausible. p. 0

Where the paper says it

We focus on the practically central regime of systems with low instability complexity—eigenvalues outside the real stable interval that do not decay rapidly, together with non-semisimple modes—potentially embedded in an otherwise stable real spectrum of much higher dimension; we write k for this count. This regime is the primary setting in which stabilization is plausible: we show that many systems with high instability complexity cannot be stabilized without exponentially large controls.

Existing predictors fall into three families—spectral filtering, finite-memory input filters (FIR), and autoregressive (AR) predictors—none of which alone handles the mixed case of systems with many decaying modes and few hard ones. p. 1
Where the paper says it

Autoregressive (AR) predictors [Ho and Kalman, 1966, Kailath, 1980], and system identification methods [Overschee, 1996, Simpkins, 2012] can represent any observable LDS exactly, but at the cost of memory proportional to d—even if only one out of d modes is non-stable. None of these tools alone handles the mixed case: a system with d − k easily filtered modes and k ≪ d hard ones.

Unified Algorithm Construction

The unified algorithm combines the strengths of spectral filtering, finite-memory filtering, and autoregressive predictors to capture any LDS with instability complexity k using only O(k · polylog(T, k)) parameters. The feature vector at time t is defined as at i = Y T t,i F T t U˜ T t for each output coordinate i. p. 5

Where the paper says it

At time t, the feature vector contains the k autoregressive output lags, a finite-memory input window of length L + k + 1, and the spectral-filter features of the current input window. We run one copy of the Vovk–Azoury–Warmuth forecaster per output coordinate; see Appendix H for the definition of the algorithm and its regret guarantee.

The total number of learnable parameters is O(k · polylog(T, k)) because the memory complexity is O(k + h + L) where h and L are bounded by functions of k and T. p. 5
Where the paper says it

Consider any observable LDS with state dimension d, of which the instability complexity is k, and any input sequence whose generated outputs satisfy Assumption 2. With filter count h = O(k · log T · log(poly(T, k))) and finite-memory length L = O(k · polylog(T, k)), Algorithm 1 achieves loss 1 T X T t=1 ℓ 2 2 (ybt, yt) = O k 2 log3 (k) · log3 (T) T assuming the parameters of the LDS are constants except T, k, and uses O(k · polylog(T, k)) learnable parameters.

Theoretical Guarantees

The algorithm achieves a loss of O(k squared log3(k) log3(T) / T), which is sublinear regret against the best LDS predictor in hindsight. The lower bound shows that at least a linear dependence on k is unavoidable for filter-based predictors, meaning any filter-based predictor with bounded coefficient mass needs at least k filter directions to achieve sublinear regret. p. 1

Where the paper says it

Finally, in Section 5 we show that the instability complexity k is a natural and well-motivated parameter from both a theoretical and practical perspective. On the theoretical side, we prove a lower bound showing that the dependence on k is unavoidable: any filter-based predictor with bounded coefficient mass needs at least k filter directions to achieve sublinear regret (Proposition 11).

Furthermore, the input dynamic range grows exponentially in k for systems that are practically uncontrollable due to exploding modes. p. 9
Where the paper says it

We identified a new regime that captures an important middle ground: systems with only k modes outside the real stable interval that do not decay rapidly, together with non-semisimple modes, embedded in an arbitrarily large stable real semisimple component. We show that this regime is central not only because it is broader than the classical stable setting, but also because it is provably the primary regime in which stabilization is practically possible: already in a broad scalar-input diagonalizable class, many exploding modes force stabilizing inputs to span exponentially many scales (Proposition 9), making such dynamics practically uncontrollable due to acute sensitivity to finite precision, actuator limits, and noise.

Experimental Validation

Experiments on a high-dimensional system with small instability complexity confirmed the theory, showing that the unified predictor sharply outperforms prior methods at an equal parameter budget. The comparison showed the unified predictor attained orders-of-magnitude lower error than spectral filtering, finite-memory, and autoregressive predictors. p. 1

Where the paper says it

We complement these results with experiments (Section 6) on a high-dimensional system with small instability complexity. Given the same number of learned parameters, the unified predictor attains orders-of-magnitude lower error than spectral filtering, finite-memory, and autoregressive predictors, confirming that it captures the few hard modes without paying for the full state dimension, unlike existing methods.

Conclusion

The paper concludes that prediction does not need to pay for the full hidden dimension by combining dimension-free spectral filtering for stable modes, finite-memory input filtering for fast decaying modes, and a small autoregressive correction for the k exceptional modes. This yields a unified online predictor that achieves sublinear regret with a learnable parameter count of Oe(k), completely independent of the full hidden-state dimension. p. 9

Where the paper says it

Our algorithm combines dimension-free spectral filtering for stable real semisimple modes, finite-memory input filtering for fast decaying semisimple modes, and a small autoregressive correction for the k exceptional modes. This yields a unified online predictor for general LDSs that achieves sublinear regret with a learnable parameter count of Oe(k), completely independent the full hidden-state dimension.

The memory complexity is O(k + h + L) = O˜(k) because log Lustb = O˜(k). p. 5
Where the paper says it

Consider any observable LDS with state dimension d, of which the instability complexity is k, and any input sequence whose generated outputs satisfy Assumption 2. With filter count h = O(k · log T · log(poly(T, k))) and finite-memory length L = O(k · polylog(T, k)), Algorithm 1 achieves loss 1 T X T t=1 ℓ 2 2 (ybt, yt) = O k 2 log3 (k) · log3 (T) T assuming the parameters of the LDS are constants except T, k, and uses O(k · polylog(T, k)) learnable parameters.

The final regret bound is RT = O((k + L + h) [log T + log(k + L + T h) + log(k + L + h) + k log k]). p. 2
Where the paper says it

Definition 1 (Instability complexity). The instability complexity of an LDS, denoted k, is the smallest integer k ≥ 0 such that at most k eigenvalues of A (counted with algebraic multiplicity) either lie outside (−1, 1) with |λi | > 1 − 1/ log (k + 2), or are non-semisimple.

The total number of learnable parameters is Oe(k), which is determined by the feature dimension times the number of output coordinates. p. 1
Where the paper says it

We complement these results with experiments (Section 6) on a high-dimensional system with small instability complexity. Given the same number of learned parameters, the unified predictor attains orders-of-magnitude lower error than spectral filtering, finite-memory, and autoregressive predictors, confirming that it captures the few hard modes without paying for the full state dimension, unlike existing methods.

How the training signal is built

The algorithm learns coefficients from the unified predictor class defined in Theorem 6, which combines spectral filtering, finite-memory filtering, and autoregressive predictors. The feature vector at time t contains k autoregressive output lags, a finite-memory input window of length L + k + 1, and spectral-filter features of the current input window. p. 5

Where the paper says it

The algorithm learns the coefficients of the unified predictor class from Section 4. At time t, the feature vector contains the k autoregressive output lags, a finite-memory input window of length L + k + 1, and the spectral-filter features of the current input window.

These features are exactly the parameters of a predictor in the unified class of Theorem 6. p. 5
Where the paper says it

(4) The window Ft subsumes the k recent inputs originally used by the AR component and additionally carries the lags needed by the finite-memory predictor for strictly stable modes. These features are exactly the parameters of a predictor in the unified class of Theorem 6.

Where the gains come from

The gains come from decomposing the cumulative loss into two parts: (I) estimation error controlled by logarithmic regret in T, and (II) approximation error controlled by Theorem 20. The total regret is bounded by combining these terms, resulting in a final bound of O(k squared log3(k) log3(T) / T). p. 6

Where the paper says it

This term is controlled by Theorem 20, which gives that f ⋆ achieves total squared error P t ℓ 2 2 (f ⋆ t , yt) ≤ ε against y1:T . Choosing the optimal ε and combining the two terms yields the claimed o(T) regret.

The complexity of the algorithm is O(k + h + L), which scales with the instability complexity k rather than the full state dimension d. p. 6
Where the paper says it

Choosing the optimal ε and combining the two terms yields the claimed o(T) regret. 5 Lower Bounds and Motivation Our unified algorithm, Algorithm 1, has learnable parameter count Oe(k), depending on the instability complexity rather than the full state dimension.

The memory required is O(k + h + L) = O˜(k). p. 0
Where the paper says it

A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems Yuval Ran-Milo∗ Tel Aviv University Angelos Assos∗ Princeton University Elad Hazan Princeton University Abstract Motivated by the challenge of stabilizing a general unknown linear dynamical system (LDS) from observations, we study the natural prerequisite of online prediction. Our goal is to achieve sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics rather than the full hidden-state dimension.

The lower bound on filter count shows that at least linear dependence on k is unavoidable for filter-based predictors. p. 7
Where the paper says it

2 Filter-count lower bound Our algorithm uses a filter class whose size grows linearly with k up to logarithmic factors. We now show that this linear dependence is unavoidable for predictors of the same broad type, even when the filters themselves are chosen arbitrarily.

The input dynamic range grows exponentially in k for systems with many exploding modes, making them practically uncontrollable. p. 1
Where the paper says it

On the theoretical side, we prove a lower bound showing that the dependence on k is unavoidable: any filter-based predictor with bounded coefficient mass needs at least k filter directions to achieve sublinear regret (Proposition 11). On the practical side, we show that a broad scalar-input diagonalizable class with many exploding modes is essentially impossible to stabilize: any stabilizing input must span exponentially many scales of magnitude—its input dynamic range (Definition 8) grows exponentially in k (Proposition 9)—making such controllers acutely sensitive to noise, actuator limits, and finite precision.

The final result is that the total regret is RT = O((k + L + h) logT (k + L + T h) / (k + L + h)) exp(O(k log k)). p. 1
Where the paper says it

, 2017] gives a particularly relevant result: stable LDS outputs can be predicted online using a small universal family of filters, with parameter count independent of the hidden-state dimension. Hazan and Marsden [2026] extend spectral filtering to systems with complex-valued eigenvalues, although their regret scales linearly with the sequence length.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Adaptive Memory Footprint for Prediction: The system can achieve sublinear regret with a learnable parameter count of Oe(k), which adapts to intrinsic instability complexity k rather than the full hidden-state dimension d. This allows for efficient online learning even when the state space is very large, focusing only on the modes that are hardest to learn.

  2. Unified Algorithm for General LDS Prediction: The unified algorithm handles every Linear Dynamical System (LDS), including non-diagonalizable systems and those with complex or exploding modes, by combining spectral filtering, finite-memory input filters, and autoregressive predictors into a single class. This provides generality without the memory cost proportional to d.

  3. Efficient Learning in Uncontrollable Regimes: The system can operate effectively in regimes where many exploding modes exist but are practically uncontrollable because any stabilizing input must span exponentially many scales (IDR(u) grows exponentially in k). The algorithm's efficiency is tied to this small complexity k, making it suitable for systems with mild resonance or a single unstable direction embedded in a large stable space.

  4. Parameter-Efficient Control: By focusing on the regime where instability complexity k is small, the system can learn control policies with a parameter budget of Oe(k), which is independent of d. This contrasts with prior methods that require memory proportional to d for exact autoregressive representation or spectral filtering for stable systems.

  5. Guaranteed Lower Bound on Predictor Complexity: The theoretical work provides a lower bound showing that any filter-based predictor needs at least k filters, proving that instability complexity k is a valid measure of required complexity. This justifies using k as the primary parameter instead of d when designing online predictors.

Abstract

Motivated by the challenge of stabilizing a general unknown linear dynamical system (LDS) from observations, we study the natural prerequisite of online prediction. Our goal is to achieve sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics rather than the full hidden-state dimension. We focus on the practically central regime of systems with low instability complexity -- eigenvalues outside the real stable interval that do not decay rapidly, together with non-semisimple modes -- potentially embedded in an otherwise stable real spectrum of much higher dimension; we write k for this count. This regime is the primary setting in which stabilization is plausible: we show that many systems with high instability complexity cannot be stabilized without exponentially large controls. Thus, prediction is meaningful for stabilization precisely when the instability complexity is small. Within this regime, we introduce a unified online algorithm that handles every LDS (including non-diagonalizable systems with complex or exploding modes) with a learnable parameter count of (k). Finally, we prove a lower bound showing that k is a valid complexity measure: any filter-based predictor needs at least k filters. Experiments corroborate our theory: on a high-dimensional system, our predictor sharply outperforms prior methods at an equal parameter budget.

Sources

Related papers