Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification

Max Simchowitz; Horia Mania; Stephen Tu; Michael I. Jordan; Benjamin Recht

Source-linked AI summary

Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification

Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht

arXiv:1802.08334v4Feb 22, 2018cs.LGmath.OCstat.ML

TL;DR

The paper asks how efficiently linear dynamical systems can be identified from a single correlated trajectory, where sharp non-asymptotic guarantees are scarce. It analyzes OLS using a dependent-data generalization of Mendelson's small-ball method rather than standard mixing arguments. The resulting upper and lower bounds match up to logarithmic factors and capture the signal-to-noise behavior that more unstable systems can be easier to estimate.

Problem
Sharp non-asymptotic sample-complexity guarantees for identifying unknown linear systems from a single trajectory remain limited, although such bounds are important for robust control.
Method
The paper analyzes OLS for linear dynamical systems using a dependent-data generalization of Mendelson's small-ball method, avoiding standard mixing-time arguments.
Results
Up to logarithmic factors, OLS attains an information-theoretic lower bound, while its performance is governed by the minimum eigenvalue of the finite-time controllability Gramian.
Takeaways & Limitations
More unstable linear systems can be easier to estimate because larger state magnitudes increase the signal-to-noise ratio; the technique also covers broader linear response time-series.
Takeaways & Limitations
When B∗ is unknown, the guarantee bounds the operator norm of the concatenated errors and does not distinguish errors in A∗ from errors in B∗.

Abstract

from arXiv · show

We prove that the ordinary least-squares (OLS) estimator attains nearly minimax optimal performance for the identification of linear dynamical systems from a single observed trajectory. Our upper bound relies on a generalization of Mendelson's small-ball method to dependent data, eschewing the use of standard mixing-time arguments. Our lower bounds reveal that these upper bounds match up to logarithmic factors. In particular, we capture the correct signal-to-noise behavior of the problem, showing that more unstable linear systems are easier to estimate. This behavior is qualitatively different from arguments which rely on mixing-time calculations that suggest that unstable systems are more difficult to estimate. We generalize our technique to provide bounds for a more general class of linear response time-series.

1 Introduction

The paper studies sharp, non-asymptotic sample complexity for identifying linear dynamical systems from a single correlated trajectory. It develops an OLS analysis that avoids mixing-time arguments and shows that system excitability and instability can improve estimation.

Motivation: Sharp sample-complexity bounds for linear system identification remain rare, despite the problem's importance in time-series analysis, control, robotics, and reinforcement learning.Accurate bounds matter because trajectory measurements can be time-consuming and expensive, while robust control requires reliable error guarantees.
Problem setting: The model evolves as X_t+1 = A∗X_t + B∗u_t + η_t, with unknown dynamics matrices and process noise.The paper focuses on identifying a discrete-time linear dynamical system from an observed trajectory.
Motivation: The relationship between the spectral properties of A∗ and the statistical rate for estimating A∗ is poorly understood, although larger states relative to noise suggest higher signal-to-noise ratios.The paper argues that larger systems, in an appropriate sense, produce larger-norm states and may therefore be easier to estimate.
Main approach: The analysis avoids standard mixing-time arguments, whose bounds deteriorate for slower mixing and fail to capture the behavior near or beyond instability.The paper instead couples the covariate and noise processes rather than analyzing them separately.
Main approach: For marginally stable systems, OLS performance is governed by the minimum eigenvalue of the finite-time controllability Gramian Γ_T.The Gramian's eigenvalues quantify how strongly white process noise can excite the system.
Results: Up to logarithmic factors, OLS is minimax optimal, and the analysis extends to a broader class of linear response time-series.Related analyses can have qualitatively suboptimal spectral dependence, while the paper's bounds degrade only logarithmically in the finite-time Gramian's condition number.

2 Results

The paper analyzes OLS for estimating linear dynamical systems from a single trajectory, using finite-time controllability Gramians and dependent-data small-ball arguments. Its results provide finite-sample guarantees, near-minimax rates, and extensions to general linear-response time series.

Linear Dynamical Systems: OLS estimation error is measured in operator norm for a system observed through X_{t+1}=A*X_t+η_t, with marginal stability ρ(A*)≤1.The analysis first considers systems without inputs and Gaussian process noise.
Linear Dynamical Systems: The estimation rate is governed by λmin(Γ_k), the minimum eigenvalue of the finite-time controllability Gramian.This quantity lower-bounds covariate covariance and measures how strongly process noise excites the system.
Lower Bounds: The OLS upper bounds are minimax optimal up to logarithmic factors in many regimes, including matching upper and lower bounds for orthogonal systems outside a narrow transition regime.The scalar analysis also gives sharper constants and applies to unstable systems.
Noise Dependence: The bounds do not depend on σ² for isotropic Gaussian noise because scaling the noise also rescales the covariates, cancelling in the signal-to-noise ratio.For general noise covariance, the more general linear-response theorem gives a more precise dependence on Γ_t and Σ.
General Time Series with Linear Responses: A martingale small-ball condition extends the analysis beyond linear dynamical systems to arbitrary dependent covariates with linear responses.The condition quantifies covariate excitation and supports uniform high-probability bounds through discretization.
Linear Dynamical Systems: Larger Gramian eigenvalues or greater system excitability yield faster estimation of A*, while longer blocks improve excitation but weaken high-probability guarantees.The block length k therefore balances statistical rate against probability control.

3 Theorem 2.1 as a corollary of Theorem 2.4

The theorem follows by verifying the dependent-data assumptions for linear dynamical systems and identifying the finite-time controllability Gramian as the relevant covariance scale.

The noise process satisfies the required sub-Gaussian tail condition, enabling application of the general meta-theorem.
The expected state covariance is bounded using the finite-time controllability Gramian ΓT.Linearity of trace and E[X⊤X] = σ2∑T_t=1Γt yield the comparison used in the theorem.
The block martingale small-ball condition follows from monotonicity of Γt and a Paley-Zygmund lower bound.

4 Proof of Theorem 2.4

The proof combines singular-value control, covering arguments, and data-dependent concentration to bound OLS error without separately controlling covariates and noise.

OLS error is bounded by the inverse smallest singular value of the data matrix times the projected noise operator norm.
The proof controls the relevant events through set-theoretic inclusions and probability decomposition, with the BMSB assumption handling one intersection term.
A covering lemma converts pointwise quadratic-form bounds into a uniform bound over directions using upper and lower Loewner bounds.
A martingale-Chernoff argument uses the data-dependent variance proxy σ2·∥Xw∥2, producing cancellation between numerator and denominator.
The technical lemmas and remaining proof details are supplied in the appendices.

5 Discussion and future work

The paper concludes that OLS is nearly information-theoretically optimal in the stable regime, while identifying gaps for unstable systems, separate parameter errors, partial observations, and input design.

Up to logarithmic factors, OLS attains an information-theoretic lower bound when ρ(A∗) < 1 and T ≳ d 1−ρ(A∗).
The lower and upper bounds do not perfectly match even when ρ(A∗) < 1.
For unknown B∗, the rates do not distinguish estimation error in A∗ from estimation error in B∗.
The operator norm may be too coarse for control applications requiring mode-specific error guarantees.
Convergence rates degrade for ρ(A∗) > 1 despite identifiability with OLS, leaving stable and unstable modes without a unified analysis.
Limited observations of CXt leave sample complexity for estimating arbitrary matrices as an open direction.
Choosing control inputs that maximize estimation accuracy could inform adaptive and low-regret online algorithms.
The appendix develops consistency and diagonalizable-matrix corollaries through bounds involving Jordan structure and the condition number of S.

A.1 Proof of Corrollary A.2

The corollary proof reduces the required horizon conditions to elementary inequalities, then specializes the argument to Jordan and diagonalizable decompositions.

Theorem 2.1 imposes an inequality relating the time horizon T and block length k.
Proposition A.1 supplies the key bound used to establish the corollary's conditions and burn-in requirement.
The resulting conditions depend on dimension, the condition number of S, and the Jordan-block structure.
A calculus lemma shows T ≥ α log T once T ≥ 2α log 4α, enabling explicit horizon bounds.
For diagonalizable A∗, the Jordan-block contribution vanishes and the corollary follows from the specialized bounds.
The proof expands the Jordan decomposition block by block and applies a Loewner diagonal bound to control the resulting matrices.
The block calculations use T ≥ d and the dimension of each Jordan block to complete the bound.

B Specialized Analysis in Scalar Linear Systems

The appendix develops specialized upper and lower bounds for scalar linear systems, with an explicit high-probability upper-bound theorem and a matching lower-bound framework.

The scalar model is xt+1 = a∗xt + ηt with Gaussian noise ηt ∼ N(0, σ2) and initial state x0 = 0.
Theorem B.1 gives a high-probability condition under which the scalar estimator satisfies |ba(T) − a∗| ≤ ϵ.
The unstable-system analysis applies when a∗ > 1 + ϵ.
The lower-bound construction matches the upper bound and establishes optimal rates using local alternatives in the scalar setting.
The appendix states that Theorem B.1 and Theorem B.2 are proved in Sections C and F.1, respectively.

C Proof of Theorem B.1

The proof of Theorem B.1 controls scalar estimation error through conditional moment-generating-function bounds and a recursively defined sequence whose behavior differs between stable and unstable regimes.

The proof decomposes the estimation error E = ˆa − a and bounds the probability that |E| exceeds ϵ through two component events.
A Chernoff bound controls the relevant probabilities after the moment-generating function is bounded.
Proposition C.1 defines a recursive sequence ρt that upper-bounds |a − ba| with high probability.
The MGF argument uses conditional expectation, induction, and a Gaussian-noise lemma for scalar variables.
Stable regime: For stable systems, geometric-series bounds control the accumulated sequence terms and yield the stated conclusion.
Unstable regime: For |a| > 1 + ϵ, choosing α so that r > 1 makes ρt grow exponentially until it reaches α/ϵ2.
The recursive sequence satisfies the required inequality, completing the MGF upper bound used in the proof.

D Proof of Theorem 2.4

The proof of Theorem 2.4 combines event decompositions, controllability-Gramian bounds, discretization, and covering arguments to control dependent quadratic forms and operator norms.

The proof reduces the theorem to showing that two specified intersection-event probabilities are at most δ.
A condition on k ensures k⌊T/k⌋ ≥ 9/10T, preserving a constant fraction of the trajectory after block partitioning.
The argument applies Proposition 2.5 and Equation (2.7) after substituting the definitions of the relevant events.
Discretization and covering: The proof uses a 1/4-net of a Gramian-defined shell and bounds its size through ellipsoidal covering numbers and volumetric arguments.
Operator-norm control: Operator-norm control uses a variational formulation together with coverings of the sphere and parameter space.
Good-event bounds: On the defined good event, the empirical Gram matrix is bounded between a scaled minimum Gramian and TΓmax.
Probability estimates: The remaining probability estimates combine pointwise bounds, metric-entropy terms, determinant expressions, and optimized exponential bounds.
Probability estimates: The proof records additional determinant and logarithmic terms in the resulting exponential bounds.

E.1 Proof of Proposition 2.5

The proof of Proposition 2.5 partitions dependent observations into blocks and applies a block martingale small-ball condition, Chernoff bounds, and MGF optimization.

The sequence Z1, Z2, …, ZT is partitioned into ⌊T/k⌋ blocks of size k, discarding remainder terms.
A Chernoff bound converts the block indicators into an exponential-moment estimate.
Conditional expectations of the block indicators are lower-bounded using the (k, ν, p)-BMSB condition.
The tower property of conditional expectation is applied across the block filtration to control the MGF recursively.
The bound is substituted into the prior exponential inequality and optimized over λ to obtain the conclusion.

E.2 Proof of Martingale Concentration (Lemma 4.2)

The proof derives a martingale concentration inequality using a Chernoff argument and conditional sub-Gaussianity, then obtains a tail bound for {S_T ≥ α} and {R_T ≤ β}.

A Chernoff optimization over λ>0 produces the exponential tail bound from the controlled exponential moment.
The conditional zero-mean σ-sub-Gaussian assumption implies E[e^(λS_T−λ^2σ^2R_T/2)] ≤ 1.The argument uses the tower rule to control the exponential process recursively.
P[{S_T ≥ α} ∩ {R_T ≤ β}] ≤ e^(−α^2/2σ^2β).

F.1 Proof of Information Theoretic Lower Bounds, Theorems B.2 and 2.3

The section proves information-theoretic lower bounds by combining Birge’s inequality with KL-divergence calculations and carefully constructed packings. The packing is built in the skew-symmetric matrix space and transferred to orthogonal matrices through the matrix exponential.

Information-theoretic lower bounds: Birge’s inequality converts estimation error over a 2ϵ-separated parameter set into constraints involving KL divergences between trajectory laws.The lower-bound setup uses disjoint estimation-success events for separated parameters.
Information-theoretic lower bounds: A one-dimensional lower bound is obtained by comparing two scalar systems separated by 2ϵ.
Information-theoretic lower bounds: A 1/2-packing of the (d−1)-dimensional unit ball is lifted to a packing of orthogonal matrices with controlled operator and Frobenius distances.
Information-theoretic lower bounds: The resulting packing argument yields a lower-bound scaling involving d + log(1/δ) for δ ≤ 1/4.
Information-theoretic lower bounds: The packing strategy constructs points in Skew(d) and maps them into O(d) using the matrix exponential.The exponential map is described as an approximate isometry near zero, preserving the relevant local separations.