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

• URL: http://arxiv.org/abs/2607.02050v2
• Date: Sat, 04 Jul 2026 11:17:44 GMT
• Title: A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
• Abstract summary: We study the natural prerequisite of online prediction.<n>Our goal is to achieve sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics.
• Score: 14.967168108174464
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• Sub-linear Regret in Adaptive Model Predictive Control [56.705978425244496]
  We present STT-MPC (Self-Tuning Tube-based Model Predictive Control), an online oracle that combines the certainty-equivalence principle and polytopic tubes. We analyze the regret of the algorithm, when compared to an algorithm initially aware of the system dynamics.
  arXiv  Detail & Related papers  (2023-10-07T15:07:10Z)
• Neural System Level Synthesis: Learning over All Stabilizing Policies for Nonlinear Systems [0.0]
  We propose a Neural SLS (Neur-SLS) approach guaranteeing closed-loop stability during and after parameter optimization. We exploit recent Deep Neural Network (DNN) models based on Recurrent Equilibrium Networks (RENs) to learn over a rich class of nonlinear stable operators.
  arXiv  Detail & Related papers  (2022-03-22T15:22:31Z)
• Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics [0.0]
  We present a computationally efficient algorithm that attains an optimal $sqrtT$ regret-rate against the best stabilizing linear controller. In contrast to previous work, our algorithm is based on the Optimism in the Face of Uncertainty paradigm.
  arXiv  Detail & Related papers  (2022-03-02T15:19:20Z)
• Globally Convergent Policy Search over Dynamic Filters for Output Estimation [64.90951294952094]
  We introduce the first direct policy search algorithm convex which converges to the globally optimal $textitdynamic$ filter. We show that informativity overcomes the aforementioned degeneracy.
  arXiv  Detail & Related papers  (2022-02-23T18:06:20Z)
• Robust Online Control with Model Misspecification [96.23493624553998]
  We study online control of an unknown nonlinear dynamical system with model misspecification. Our study focuses on robustness, which measures how much deviation from the assumed linear approximation can be tolerated.
  arXiv  Detail & Related papers  (2021-07-16T07:04:35Z)
• Learning Stabilizing Controllers for Unstable Linear Quadratic Regulators from a Single Trajectory [85.29718245299341]
  We study linear controllers under quadratic costs model also known as linear quadratic regulators (LQR) We present two different semi-definite programs (SDP) which results in a controller that stabilizes all systems within an ellipsoid uncertainty set. We propose an efficient data dependent algorithm -- textsceXploration -- that with high probability quickly identifies a stabilizing controller.
  arXiv  Detail & Related papers  (2020-06-19T08:58:57Z)
• Adaptive Control and Regret Minimization in Linear Quadratic Gaussian (LQG) Setting [91.43582419264763]
  We propose LqgOpt, a novel reinforcement learning algorithm based on the principle of optimism in the face of uncertainty. LqgOpt efficiently explores the system dynamics, estimates the model parameters up to their confidence interval, and deploys the controller of the most optimistic model.
  arXiv  Detail & Related papers  (2020-03-12T19:56:38Z)
• No-Regret Prediction in Marginally Stable Systems [37.178095559618654]
  We consider the problem of online prediction in a marginally stable linear dynamical system. By applying our techniques to learning an autoregressive filter, we also achieve logarithmic regret in the partially observed setting.
  arXiv  Detail & Related papers  (2020-02-06T01:53:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.