A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
summary
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…
In short
A unified online algorithm is introduced to stabilize linear dynamical systems (LDS) by adapting its memory usage to the system's intrinsic complexity, specifically the number of unstable modes (k). It combines spectral filtering, finite-memory filtering, and autoregressive predictors into one framework. This results in sublinear regret with a learnable parameter count scaling only with k, not the full state dimension.
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 used across episodes
This episode discusses
- A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems · Paper Radio
- 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 · Paper Radio
- 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
The paper
A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems · Read on arXiv
Tel Aviv University · Princeton University
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.
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.
More episodes
- 2603.29765-Training-Free Dynamic Upcycling of Expert Language Models
- 2605.00778-Observable Performance Does Not Fully Reflect Adaptive System Organization: A Multi-Level Analysis of Gait Dynamics Under Occlusal Constraint
- 2605.06906-TraXion: Rethinking Pre-training Frameworks for Mobility and Beyond
- 2605.09165-Sparse Layers are Critical to Scaling Looped Language Models
- 2605.09439-Inverse Design for Conditional Distribution Matching
- 2605.10313-Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewards: Regret Bound and Statistical Inference
- 2605.10878-Minimum Neural Weight Norm = Kolmogorov Complexity
- 2605.11617-MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound
- 2605.15085-From Data to Action: Accelerating Refinery Optimization with AI
- 2605.23500-GRTO: Bootstrapped Group Relative Tool Optimization for Referring Segmentation