Search papers, labs, and topics across Lattice.
This paper introduces a unified online algorithm for predicting linear dynamical systems (LDS) that achieves sublinear regret while maintaining a memory footprint that scales with the intrinsic complexity of the system rather than its full state dimension. The authors focus on systems with low instability complexity, demonstrating that stabilization is feasible only when this complexity is small, as many high-complexity systems require exponentially large controls. Experimental results validate the theoretical claims, showing that the proposed method significantly outperforms existing approaches within the same parameter budget on high-dimensional systems.
Stabilization of complex linear dynamical systems becomes feasible with a memory-efficient algorithm that adapts to the system's intrinsic complexity, outperforming traditional methods.
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.
