A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
Pith reviewed 2026-07-03 17:09 UTC · model grok-4.3
The pith
A unified online algorithm predicts any linear dynamical system using only O~(k) parameters when instability complexity is low.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Within the regime of systems with low instability complexity k, 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 O~(k). We prove sublinear regret and that any filter-based predictor needs at least k filters. This regime is where stabilization from observations is plausible.
What carries the argument
Unified online algorithm adapting parameter count to instability complexity k
Load-bearing premise
The premise that systems with high instability complexity cannot be stabilized without exponentially large controls.
What would settle it
Finding a high-dimensional LDS with small k on which the algorithm fails to achieve sublinear regret with O~(k) parameters, or a system with large k that can be stabilized with bounded controls.
read the original 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 $\widetilde{O}(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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online prediction as a prerequisite for stabilizing unknown linear dynamical systems (LDS). It focuses on the regime of low instability complexity k (eigenvalues outside the stable interval that do not decay rapidly, plus non-semisimple modes). Within this regime it claims a single online algorithm that achieves sublinear regret for every LDS—including non-diagonalizable systems with complex or exploding modes—while using only ilde{O}(k) learnable parameters. It also proves a matching lower bound that any filter-based predictor requires at least k filters, shows that high-k systems cannot be stabilized without exponentially large controls, and reports experiments in which the new predictor outperforms prior methods on a high-dimensional system at equal parameter budget.
Significance. If the central claims hold, the work would be significant for online learning and adaptive control: it supplies a memory-efficient, unified method whose complexity tracks intrinsic instability rather than ambient state dimension, together with a matching lower bound that validates k as a complexity measure. The explicit handling of non-diagonalizable, complex, and exploding modes and the link between prediction and stabilization plausibility are notable strengths.
minor comments (3)
- The abstract states that experiments corroborate the theory on a high-dimensional system, but supplies no details on system dimension, choice of k, baselines, or performance metrics; these should be summarized with a table or figure reference in the main text.
- The notation ilde{O}(k) for the learnable parameter count is used without an explicit definition of the hidden constants or the precise dependence on other problem parameters (e.g., time horizon, noise variance).
- The lower-bound statement that “any filter-based predictor needs at least k filters” should clarify whether the result applies only to a specific class of filters or to all linear filters; a brief proof sketch or reference to the relevant theorem would help.
Simulated Author's Rebuttal
We thank the referee for the positive review, accurate summary of our contributions, and recommendation of minor revision. No major comments were raised in the report.
Circularity Check
No significant circularity identified
full rationale
The derivation chain in the abstract presents an algorithm achieving sublinear regret with ilde{O}(k) parameters for low-instability-complexity LDS, together with an independent lower bound that any filter-based predictor requires at least k filters. No self-definitional reduction, fitted-input prediction, or load-bearing self-citation is visible; the regime definition, algorithm, and complexity lower bound are stated as separate results without equations or citations that collapse one into the other by construction. The paper is self-contained against external benchmarks on this point.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Many systems with high instability complexity cannot be stabilized without exponentially large controls.
Reference graph
Works this paper leans on
- [1]
-
[2]
John S. White , title =. The Annals of Mathematical Statistics , number =. 1958 , doi =
work page 1958
-
[3]
Philosophical Transactions of the Royal Society of London , number =
Cayley, Arthur , title =. Philosophical Transactions of the Royal Society of London , number =. 1858 , month =. doi:10.1098/rstl.1858.0002 , url =
-
[4]
Gradient Descent Learns Linear Dynamical Systems , author=. 2019 , eprint=
work page 2019
-
[5]
Learning Linear Dynamical Systems via Spectral Filtering , author=. 2017 , eprint=
work page 2017
-
[6]
Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification , author=. 2018 , eprint=
work page 2018
-
[7]
Finite Time Identification in Unstable Linear Systems , author=. 2018 , eprint=
work page 2018
-
[8]
Doyle, John and Glover, Keith and Khargonekar, P. and Francis, Bruce , year =. State Space Solution to Standard. Automatic Control, IEEE Transactions on , doi =
-
[9]
at - Automatisierungstechnik , doi =
Editorial: Effective construction of linear state-variable models from input/output functions , author =. at - Automatisierungstechnik , doi =. 1966 , lastchecked =
work page 1966
-
[10]
Kailath, Thomas , year =
-
[11]
A Tutorial on the Non-Asymptotic Theory of System Identification , author=. 2024 , eprint=
work page 2024
-
[12]
Online Learning of the Kalman Filter with Logarithmic Regret , author=. 2020 , eprint=
work page 2020
-
[13]
No-Regret Prediction in Marginally Stable Systems , author=. 2020 , eprint=
work page 2020
-
[14]
Learning to Control Linear Systems can be Hard , author=. 2022 , eprint=
work page 2022
-
[15]
Ng, Jerry and Asada, H. Harry , year=. Learned Lifted Linearization Applied to Unstable Dynamic Systems Enabled by Koopman Direct Encoding , volume=. doi:10.1109/lcsys.2022.3231641 , journal=
-
[16]
Theory and Algorithms for Forecasting Time Series , author=. 2018 , eprint=
work page 2018
-
[17]
Online Control with Adversarial Disturbances , author=. 2019 , eprint=
work page 2019
-
[18]
Black-Box Control for Linear Dynamical Systems , author=. 2021 , eprint=
work page 2021
-
[19]
Adaptive Regret for Control of Time-Varying Dynamics , author=. 2022 , eprint=
work page 2022
-
[20]
Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator , author=. 2020 , eprint=
work page 2020
-
[21]
Active Learning for Identification of Linear Dynamical Systems , author=. 2020 , eprint=
work page 2020
-
[22]
Learning the Kalman Filter with Fine-Grained Sample Complexity , author=. 2023 , eprint=
work page 2023
-
[23]
On the Sample Complexity of the Linear Quadratic Regulator , author=. 2018 , eprint=
work page 2018
-
[24]
Certainty Equivalence is Efficient for Linear Quadratic Control , author=. 2019 , eprint=
work page 2019
-
[25]
Logarithmic Regret for Adversarial Online Control , author=. 2020 , eprint=
work page 2020
- [26]
-
[27]
Proceedings of the 24th Annual Conference on Learning Theory , pages =
Regret Bounds for the Adaptive Control of Linear Quadratic Systems , author =. Proceedings of the 24th Annual Conference on Learning Theory , pages =. 2011 , editor =
work page 2011
-
[28]
Near optimal finite time identification of arbitrary linear dynamical systems , author=. 2019 , eprint=
work page 2019
- [29]
-
[30]
Lusch, Bethany and Kutz, J. Nathan and Brunton, Steven L. , year=. Deep learning for universal linear embeddings of nonlinear dynamics , volume=. Nature Communications , publisher=. doi:10.1038/s41467-018-07210-0 , number=
-
[31]
Champion, Kathleen and Lusch, Bethany and Kutz, J. Nathan and Brunton, Steven L. , year=. Data-driven discovery of coordinates and governing equations , volume=. Proceedings of the National Academy of Sciences , publisher=. doi:10.1073/pnas.1906995116 , number=
-
[32]
Forecasting Sequential Data using Consistent Koopman Autoencoders , author=. 2020 , eprint=
work page 2020
-
[33]
Advances in Neural Information Processing Systems , volume=
Neural Ordinary Differential Equations , author=. Advances in Neural Information Processing Systems , volume=
- [34]
-
[35]
International Statistical Review , volume =
Vovk, Volodya , title =. International Statistical Review , volume =. doi:https://doi.org/10.1111/j.1751-5823.2001.tb00457.x , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1751-5823.2001.tb00457.x , abstract =
-
[36]
Spectral Filtering for Complex Linear Dynamical Systems , author=. 2026 , eprint=
work page 2026
-
[37]
Subspace Identification for Linear Systems , author=. 1996 , publisher=
work page 1996
-
[38]
System Identification: Theory for the User, 2nd Edition (Ljung, L.; 1999) [On the Shelf] , volume =
Simpkins, Charles , year =. System Identification: Theory for the User, 2nd Edition (Ljung, L.; 1999) [On the Shelf] , volume =. Robotics & Automation Magazine, IEEE , doi =
work page 1999
-
[39]
Provable Benefits of Complex Parameterizations for Structured State Space Models , author=. 2024 , eprint=
work page 2024
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.