Research map / Bandits and online learning / Online convex optimization and games
A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a unified online predictor for linear dynamical systems combining autoregressive, finite-memory, and spectral-filter features, achieving sublinear regret with ~O(k) learnable parameters where k is the instability complexity, plus lower bounds motivating k.
Problem
Online prediction of outputs of unknown linear dynamical systems with memory that adapts to the number of unstable/non-semisimple modes (instability complexity) rather than the full hidden dimension, in a controlled (bounded-output) regime.
Approach
Combine spectral filtering for stable real semisimple modes, finite-memory input filters for fast-decaying modes, and a small order-k autoregressive correction for the few exceptional modes, learned per output coordinate with the VAW forecaster, so parameter count scales with k instead of d.
Key results
- On a 503-dimensional controlled LDS with k=3 and 16 learned parameters, the unified predictor reaches normalized MSE of 7.88e-9 to 1.65e-8 (best to worst seed), versus 1.73e-5 to 9.08e-5 for autoregressive, 5.20e-3 to 6.13e-2 for spectral filtering, and 0.376 to 0.960 for finite-memory filters.
- Theorem claims average loss O(k^2 log^3(k) log^3(T)/T) with O(k polylog(T,k)) learnable parameters.
- Lower bound: any bounded-coefficient filter predictor with fewer than k total filters fails to achieve vanishing average loss on some LDS.
Surprising findings
- The stated experimental unified predictor is only evaluated on one synthetic system, and the plain autoregressive predictor beats spectral filtering by a wide margin at equal budget.
Limitations
- Upper and lower bounds match only up to polylogarithmic factors in k and do not settle optimal log dependence or regret constants.
- Results concern prediction rather than closed-loop control.
- Experiments are limited to a single synthetic system and trajectory.
Experimental setup
Datasets: synthetic controlled 503-dimensional LDS trajectory
Benchmarks: synthetic controlled k=3 LDS (d=503)
Metrics: normalized mean-squared error
Baselines: Finite-memory input filters Autoregressive predictor Spectral filtering
Builds on: spectral filtering Vovk-Azoury-Warmuth forecaster Cayley-Hamilton autoregressive representation
Closest papers by meaning
- Memory-Efficient Learning of Stable Linear Dynamical Systems for Prediction and Control (NeurIPS 2020 · similarity 0.90)
- Universal Learning of Nonlinear Dynamics (ICML 2026 · similarity 0.90)
- Online Linear Quadratic Control (ICML 2018 · similarity 0.89)
- The Power of Second Order Methods for Sequence Preconditioning (NeurIPS 2026 · similarity 0.87)
- Universal Sequence Preconditioning (NeurIPS 2025 · similarity 0.86)
- Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.