Finite-Sample Identification of Unstable Linear Systems

This direction is split into other directions: stability-constrained system identification. Its last version stays readable and citable here.

Version 1 of 148 papers50 conceptsfrozen 2026-10-04

In classical control theory and statistics, the safety net of "stability" is almost always present. We assume that a system, if left alone, will eventually return to equilibrium. This assumption allows researchers to use tools from stationary time-series analysis, relying on the fact that the system "mixes"—meaning it eventually forgets its initial state and provides samples that are effectively independent.

However, a growing body of research is dismantling the requirement for stability, proving that we can identify the parameters of a system even when it is "explosive" or "marginally stable." Counter-intuitively, these unstable systems are often easier to learn than stable ones because their rapid growth provides a massive signal-to-noise ratio.

The Failure of Mixing

Traditional statistical guarantees for learning Linear Dynamical Systems (LDS) rely on mixing times. If a system is stable (its spectral radius $\rho(A) < 1$), the influence of past noise decays exponentially. This allows us to treat a single long trajectory as a collection of nearly independent data points.

But as Max Simchowitz, Horia Mania, and Benjamin Recht argued in Learning Without Mixing, mixing is a sufficient but not necessary condition for learning. They demonstrated that Ordinary Least Squares (OLS) can identify system parameters even when the system does not mix. The key insight is that the "information" in a trajectory is captured by the covariance of the state. In stable systems, this covariance stays bounded; in unstable systems, it grows, which actually helps the estimator converge faster.

The Paradox of Instability

If a system is unstable ($\rho(A) > 1$), the state $x_t$ grows exponentially. While this is a nightmare for a controller trying to keep a drone from crashing, it is a boon for a statistician trying to identify the system's transition matrix $A$.

Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis showed in Finite Time Identification in Unstable Linear Systems that for explosive systems, the identification error can decay doubly exponentially with time. Because the signal (the state) grows so much faster than the noise, the true parameters of the system reveal themselves almost immediately. The "instability" acts as a natural amplifier for the underlying dynamics.

The Boundary of Marginal Stability

The most difficult regime is neither strictly stable nor wildly explosive, but "marginally stable"—where eigenvalues lie exactly on the unit circle (unit roots). These systems, like simple integrators or oscillators, do not decay, but they also do not explode fast enough to drown out noise easily.

Oğuz Kaan Yüksel, Mathieu Even, and Nicolas Flammarion have pushed the frontier here, particularly in the context of Long-Context Linear System Identification. They provide guarantees for systems with long-range dependencies, showing that even when the system "remembers" its past for a very long time, we can still achieve sharp statistical bounds. This bridges the gap between the fast learning of explosive systems and the steady learning of stable ones.

From Identification to Adaptive Control

Understanding how to learn unstable systems is not just a mathematical curiosity; it is a prerequisite for safe reinforcement learning. In partially observable settings (LQG), the challenge is doubled: we must estimate the hidden state while simultaneously learning the dynamics.

Algorithms like ADAPTON, developed by Sahin Lale, Anima Anandkumar, and colleagues in Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems, attempt to bridge this. The difficulty in the unstable case is the "exploration-exploitation" trade-off: to learn the system, you might need to let it deviate, but if it is unstable, a small deviation can lead to catastrophic failure before you have enough data to correct it.

Robustness and Hidden States

Real-world systems rarely provide clean, full-state observations. We often deal with:

  1. High-dimensional observations: Learning latent linear dynamics from pixels, as explored in the "RichLQR" framework by Wen Sun and Akshay Krishnamurthy.
  2. Censored data: Learning when states are only visible in certain regions, a problem addressed by Orestis Plevrakis.
  3. Spectral Filtering: Using techniques like those proposed by Elad Hazan to handle systems where the hidden state doesn't dissipate quickly, avoiding the non-convexity of traditional EM methods.

The unifying theme across these papers is a shift toward non-asymptotic analysis. Instead of asking what happens as we collect infinite data, researchers are providing explicit bounds on how many samples $N$ are needed to reach a specific error $\epsilon$, regardless of whether the system is settling down or blowing up.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_finite_sample_identification_of_unstable_53d2c841,
  title = {Finite-Sample Identification of Unstable Linear Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-sample-identification-of-unstable-linear-systems/rdr_53d2c8413d54436f8c076c90f164553b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_finite_sample_identification_of_unstable_53d2c841_v1,
  title = {Finite-Sample Identification of Unstable Linear Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-sample-identification-of-unstable-linear-systems/rdr_53d2c8413d54436f8c076c90f164553b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}