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

arXiv: https://arxiv.org/abs/2607.02050 · HTML: https://mlsanity.com/paper/2607.02050/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 2 Jul 2026.

## Builds on (most cited first, 21 of 21)

- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Learning Linear Dynamical Systems via Spectral Filtering](https://mlsanity.com/paper/1711.00946/) (2017)
- [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (2020)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [Active Learning for Identification of Linear Dynamical Systems](https://mlsanity.com/paper/2002.00495/) (2020)
- [Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator](https://mlsanity.com/paper/2003.07937/) (2020)
- [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020)
- [Introduction to Online Control](https://mlsanity.com/paper/2211.09619/) (2022)
- [No-Regret Prediction in Marginally Stable Systems](https://mlsanity.com/paper/2002.02064/) (2020)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [Learning the Kalman Filter with Fine-Grained Sample Complexity](https://mlsanity.com/paper/2301.12624/) (2023)
- [Provable Benefits of Complex Parameterizations for Structured State Space Models](https://mlsanity.com/paper/2410.14067/) (2024)
- [Theory and Algorithms for Forecasting Time Series](https://mlsanity.com/paper/1803.05814/) (2018)
- [Spectral Filtering for Complex Linear Dynamical Systems](https://mlsanity.com/paper/2601.22400/) (2026)

## Abstract (arXiv)

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 widetildeO(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.