Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory

Learning linear systems under heavy-tailed noise involves establishing non-asymptotic sample complexity bounds for least-squares estimation of vector autoregressive models using a single observed trajectory, which is crucial for understanding the statistical viability of model-based control in real-world scenarios where system noise exhibits heavy tails. The core finding demonstrates that under bounded pth moment conditions with p > 2, the estimation error is bounded by Oe(r(1/2T - 1/2 + 1/p)), showing that model-based approaches remain statistically viable even with moderately heavy-tailed noise distributions.

Problem Formulation and Motivation

The paper addresses the challenge of learning unknown system parameters from observations of a linear dynamical system described by a vector autoregressive (VAR) model:

z t = Θz t-1 + Ψξ t, where z 0 = Ψξ 0 and ξ t is the random noise vector. The estimation problem focuses on finding the parameter matrix Θ that minimizes the least-squares objective function:

Θb ∈ arg min X T t=1∥z t - Θz t-1∥2. The motivation stems from the limitations of classical asymptotic theory, which often assumes sub-Gaussian noise, and the practical necessity of analyzing finite-sample performance in model-based control applications where heavy-tailed disturbances like those modeled by the Pareto distribution are common.

Unifying Analysis Framework

The authors introduce a unifying approach to sample complexity analysis applicable to broad classes of noise distributions. This framework is built upon two main assumptions:

1. Assumption 1 establishes properties of the system, requiring i.i.d., zero-mean noise, exponential stability (∥Θ t∥ ≤ Lα t), bounded effect of noise (ΨΨ⊤ ⪯ σ2I), and persistent excitation (hΨ Θ Ψ · · · Θtc−1Ψ i hΨ Θ Ψ · · · Θtc−1Ψ i⊤ ⪰ β2I).

2. Assumption 2 introduces a Bounded Tail Probability condition on the augmented noise vectors, ensuring that the difference between empirical covariance and true covariance is bounded with high probability by a term dependent on T, r, and distribution-dependent variables.

Sample Complexity Bounds for Bounded Moments

The central result establishes the non-asymptotic estimation error bound under Assumption 1 and Assumption 2 for distributions with a bounded pth moment where p > 2. The resulting error bound is:

Θb − Θ ≤ Oe(r(1/2T - 1/2 + 1/p)), where T is the sample size and r is the noise dimension. This result shows that for fixed p, the estimation error deteriorates by a factor of T(1/p), suggesting slower convergence compared to sub-Gaussian cases. The analysis utilizes a fast mixing argument (via exponential stability) and a blocking strategy by introducing stacking of noise vectors to decouple temporal correlation completely.

Specialization to ARX Models

The general analysis is specialized for the Autoregressive with Exogenous Input (ARX) model, where the system parameters are estimated using OLS on augmented input-output data. A key contribution here is showing that under suitable excitation and stability conditions, the dimension factor of the sample complexity depends only on the combined state and input dimension and is independent of the autoregressive order. This provides an improvement over existing bounds that scale with the model order q.

Distribution Specific Results

The unifying lemma allows for explicit derivation of error bounds for specific noise classes:

1. For sub-Gaussian distributions, Theorem 3 yields a bound of Oe(r(1/2T - 1/2)) with high probability, showing a dependence on log(T).

2. For sub-exponential distributions (ν, ζ)-sub-exponential noise, Theorem 4 provides a bound of Oe((r/T)(1/2)) with an extra log(T) factor dependent on ζ.

3. For heavy-tailed distributions with bounded pth moment (p > 2), Theorem 1 yields the primary result: Oe(r(1/2T - 1/2 + 1/p)).

Numerical Verification and Implications

Numerical simulations confirm the theoretical framework for ARX models with various noise distributions, including Gaussian, Laplace, and Student’s t distributions (p=2.1). The results show that while the error decay is often observed to be near T(-1/2), the theoretical deterioration by T(1/p) for heavy-tailed noise does not clearly manifest in simulations for p > 2, suggesting potential tightness of the bounds or influence from rare tail events falling within the failure probability. The analysis also highlights that when covariance is unbounded (e.g., Cauchy distribution), convergence fails entirely.

As a fastidious and diligent researcher, I have analyzed this paper, Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory. The core contribution is establishing non-asymptotic sample complexity bounds for Ordinary Least Squares (OLS) estimation of Vector Autoregressive (VAR) models when the underlying noise is heavy-tailed but has a bounded pth moment with p > 2.

Based on this theoretical foundation, here are specific, actionable improvements for AI systems:

),

1. Improved Robust System Identification for Critical Infrastructure:

While standard system identification often fails or provides unreliable bounds when faced with intermittent shocks (e.g., power grid blackouts modeled by Pareto distributions), this paper provides a rigorous framework to estimate the underlying dynamics of critical infrastructure (power grids, complex chemical processes) even when noise exhibits heavy tails.

• Specific Improvement: Implement OLS-based VAR model identification techniques for real-time monitoring and control in these systems, leveraging the derived sample complexity bounds. The bound is expressed in terms of the noise dimension (which is often smaller than the state dimension), making it more computationally tractable and robust against high-dimensional system states.

• AI System Capability: An AI controller can perform safe model-based predictive control (MPC) under severe, unpredictable external shocks without requiring overly conservative, overly complex models derived from light-tailed assumptions.

2. Enhanced Robustness in Real-Time Reinforcement Learning (RL):

Many modern RL algorithms rely on learning system dynamics or transition models from experience. If the noise in the environment is heavy-tailed (e.g., sudden, large state transitions), standard methods may diverge or produce wildly inaccurate models quickly.

• Specific Improvement: Develop a Heavy-Tailed Noise Aware model learning module for RL agents that utilizes the non-asymptotic bounds derived here. Instead of relying solely on asymptotic convergence guarantees, the agent can monitor its estimation error against these explicit finite-sample bounds to detect when the environment's noise characteristics are violating assumptions (like bounded pth moments) and trigger a switch to a more robust, perhaps model-free or distribution-specific, control policy.

• AI System Capability: Autonomous robotics or complex decision-making agents operating in unpredictable physical environments can maintain stability and safety guarantees even when sensor data is corrupted by extreme outliers.

3. Model Order Independent Identification for Complex Control Loops (ARX/VAR Models):

The paper specifically shows that the dimension factor of the error bound for ARX models is independent of the model order, unlike existing literature where complexity scales with the order of the model (e.g., Ziemann et al., 2024).

• Specific Improvement: Apply this technique to identify complex industrial control loops (which are often modeled as VAR/ARX systems) where the true system order is unknown or very large. This allows for the identification of high-order dynamics without incurring a sample complexity penalty proportional to that order.

• AI System Capability: Large-scale process optimization AI can learn and deploy highly complex, high-fidelity control models rapidly from limited, single trajectories of operational data.

4. Distribution-Specific Model Tuning and Risk Assessment:

The analysis provides explicit dependence on the moment parameter 'p'. This allows for quantifying the risk associated with different noise assumptions.

• Specific Improvement: Integrate a Noise Characterization Layer into an AI system's perception pipeline. This layer estimates the tail index 'p' of incoming sensor data streams. Based on this estimate, the system can dynamically adjust its internal variance or prediction confidence levels, directly mapping the current noise regime to the required sample size (T) needed for a desired level of estimation accuracy (e.g., 99% confidence).

• AI System Capability: Financial modeling AI or high-frequency trading algorithms can dynamically adjust their risk management parameters in response to shifts in market volatility (modeled as heavy-tailed noise), ensuring that the resulting parameter estimates used for trading decisions are statistically sound according to the derived error bounds.

5. Sub-Gaussian/Sub-Exponential Baseline Validation:

The paper establishes bounds for sub-Gaussian and sub-exponential distributions, providing a benchmark for comparison against the heavy-tailed result.

• Specific Improvement: Use these established results as baseline performance metrics when training new AI models on clean data (i.e., Gaussian noise). This validates that the complex heavy-tailed analysis is necessary specifically to handle rare, extreme events, rather than just being an overly conservative approach for benign noise.

• AI System Capability: Comprehensive AI development pipelines can be validated against known good performance metrics derived from simpler distributions before deploying them in high-risk environments.