A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
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 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.Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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). 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. (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 paper says it
Where the paper says it
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 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. 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. 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. 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. 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. , 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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
- Online Control with Adversarial Disturbances
- Black-Box Control for Linear Dynamical Systems
- On the Sample Complexity of the Linear Quadratic Regulator
- Universal Learning of Nonlinear Dynamics
- Finite Time Identification in Unstable Linear Systems
- Logarithmic Regret for Adversarial Online Control
- No-Regret Prediction in Marginally Stable Systems
- Adaptive Regret for Control of Time-Varying Dynamics
- Gradient Descent Learns Linear Dynamical Systems
- Spectral Filtering for Complex Linear Dynamical Systems
- Learning Linear Dynamical Systems via Spectral Filtering
- Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator
- Theory and Algorithms for Forecasting Time Series
- Certainty Equivalence is Efficient for Linear Quadratic Control
- Provable Benefits of Complex Parameterizations for Structured State Space Models
- Near optimal finite time identification of arbitrary linear dynamical systems
- Naive Exploration is Optimal for Online LQR
- Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
- Online Learning of the Kalman Filter with Logarithmic Regret
- Learning to Control Linear Systems can be Hard
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis