PaperlayerView exact revision on arXiv

Source-linked AI summary

PAC-Bayesian Bounds for Learning Partially Observed Stochastic Linear Time-Invariant State-Space Systems with Inputs and Sub-Gaussian Noise

Mihaly Petreczky, Mohamad Al Ahdab, John Leth

arXiv:2609.08740v1cs.LGmath.OC

TL;DR

PAC-Bayesian guarantees for dynamical systems are comparatively limited, despite their use in relating empirical prediction error to expected error. This paper derives bounds for partially observed stochastic LTI systems with inputs and sub-Gaussian noise, with bound tightness depending on system stability and noise, and extensions to parameter estimation.

  • Problem

    PAC-Bayesian results are comparatively few for dynamical systems, although such bounds characterize predictive performance learned from finite data.

    Source: §1 · p. 1

  • Method

    The paper derives PAC-Bayesian generalization-gap bounds for partially observed stochastic LTI systems with inputs and sub-Gaussian noise, then extends them to parameter estimation for concrete learning algorithms.

    Source: §1 · p. 2, §4 · p. 9

  • Results

    Bounds tighten with greater system stability and lower noise; parameter-estimation bounds additionally improve with richer inputs and greater separation between models.

    Source: §4 · p. 9

  • Takeaways & Limitations

    The bounds provide finite-sample generalization and parameter-estimation guarantees for a wide range of system-identification algorithms.

    Source: §1 · p. 2, §4 · p. 10

    The guarantees are formulated for the paper's parametrized LTI predictor class.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

In this paper we derive a Probably Approximately Correct (PAC)-Bayesian error bound for partially observed linear time-invariant (LTI) stochastic dynamical systems in state-space form with inputs and sub-Gaussian noise. Such bounds are widespread in machine learning, and they are useful for characterizing the predictive power of models learned from finitely many data points. The bound derived in this paper relates the expectation of prediction errors with the prediction error generated by the model on the data used for learning. In addition, we show that it can also be used to derive bounds for the parameter estimation error. In turn, this allows us to provide finite-sample error bounds for the prediction error and parameter estimation error for a wide class of system identification algorithms. Furthermore, as LTI systems are a sub-class of recurrent neural networks (RNNs), these error bounds could be a first step towards PAC-Bayesian bounds for RNNs.

1 Introduction

PAC-Bayesian bounds relate empirical prediction error to expected error, but comparatively few results address dynamical systems. This paper derives bounds for partially observed stochastic LTI systems and connects them to parameter estimation across a wide range of learning algorithms.

1 Introduction

  • PAC-Bayesian bounds offer algorithm-independent guarantees relating true and empirical error through a posterior-average generalization gap.The framework accommodates different priors, posteriors, and model-selection mechanisms.Source: §1 · p. 1
  • Prior PAC-Bayesian results for dynamical systems are comparatively few relative to the well-developed i.i.d. setting, while existing RNN bounds assume noiseless models, fixed horizons, i.i.d. samples, and bounded signals.This paper instead considers noisy models, infinite-horizon prediction errors, a single observed time series, and unbounded signals with sub-Gaussian noise.Source: §1 · pp. 1–2
  • The paper derives PAC-Bayesian bounds for partially observed stochastic LTI systems with inputs and sub-Gaussian noise, including generalization-gap and parameter-estimation bounds.The results apply to a wide range of learning algorithms, including maximum likelihood, regularized prediction-error methods, and Bayesian methods.Source: §1 · pp. 1–2
  • The paper's bounds depend logarithmically on confidence through ln(1/δ), and their rates vary with the noise and loss setting.The stated rate exponent is r = 0 for bounded noise, r = 1 for Lipschitz loss, and r = 3/2 for quadratic loss; the bounds also depend on the prior-posterior KL divergence.Source: §1 · p. 2
  • Compared with prior bounds for autoregressive models, the paper handles partially observed state-space models with inputs, sub-Gaussian noise, and quadratic loss.It also contrasts with finite-sample parameter-estimation bounds for specific least-squares algorithms by covering both estimation error and generalization gap across a wider range of algorithms.Source: §1 · p. 2

2 Problem formulation

The problem is to learn predictors from a finite sequence of inputs and outputs, using empirical prediction error to target long-term expected performance. The formulation specifies the data generator, predictor class, loss, and system quantities used in the bounds.

2.1 Notation and terminology

  • The notation defines expectations under densities and the event-based meaning of probability-over-data guarantees.It also fixes the probability space and uses boldface for stochastic variables and processes.Source: §2.1 · pp. 2–3

2.2 Problem formulation

  • The data consist of stationary output and input processes, where outputs are labels and inputs are features, and predictions use past measurements.The prediction input w(t) may contain inputs alone or both past outputs and inputs.Source: §2.2 · p. 3
  • Predictors are parametrized LTI systems initialized at zero, with stability and boundedness conditions imposed on their matrices.The formulation also allows a trivial extension from prediction to filtering by using only some output components.Source: §2.2 · p. 3
  • The data generator is modeled as a steady-state stochastic LTI system with stable dynamics and zero-mean i.i.d. sub-Gaussian noise.Assuming the data come from the same form as the predictors is a realizability assumption, since that system yields the optimal predictor.Source: §2.2 · p. 3
  • Prediction accuracy is measured by a continuous loss that vanishes at exact predictions; the paper treats quadratic and Lipschitz losses.True error is the long-term steady-state expected loss of the predictor.Source: §2.2 · p. 4
  • The learning objective is to select a model from finite input-output data that minimizes true error, using empirical error as a proxy while controlling the generalization gap.The learner is not assumed to know the data-generating system matrices or noise process.Source: §2.2 · p. 4

2.3 Constants used in PAC-bounds

  • Convolution of Markov parameters with a process represents the response of a linear filter, with its ℓ1 norm bounding response size for bounded inputs.Its weak-dependence coefficient indicates how close the filtered process is to i.i.d. when the input is i.i.d.Source: §2.3 · p. 5
  • The bounds use Markov-parameter norms and mixing coefficients to characterize system stability and dependence in predictors, the data generator, and prediction errors.These quantities decrease with greater stability; smaller prediction-error mixing constants indicate behavior closer to an i.i.d. process.Source: §2.3 · p. 5

3 Main result

Theorem 3.1 gives high-probability PAC-Bayesian bounds on posterior-average prediction error, with terms for posterior-prior divergence and model complexity. The results also yield bounds for common system-identification algorithms and, under additional conditions, parameter estimation error.

3 Main result

  • With probability at least 1 − 2δ, Theorem 3.1 bounds posterior-average generalization gaps using the KL divergence between posterior and prior and a model-complexity term.The two signs of ϵ bound opposite directions of the gap.Source: §3 · p. 6
  • For unbounded data, truncation bounds deviations between the original and truncated empirical and auxiliary errors, which are combined with bounded-case bounds.The approach yields PAC-Bayesian guarantees for unbounded data.Source: §3 · pp. 6–7
  • Corollary 3.4 provides generalization-gap, excess-error, and parameter-estimation bounds for MAP, MEP, and single draws from the Gibbs posterior.The parameter bounds require additional conditions, including strong convexity for one MEP result and realism and persistence of excitation for another.Source: §3 · pp. 8–9
  • The parameter-estimation bounds follow by relating parameter error to loss difference through strong convexity or persistence of excitation.The generalization and excess-error bounds for these choices use oracle inequalities and data-dependent posteriors.Source: §3 · p. 9

4 Discussion on the bound and conclusions

The paper derives PAC-Bayesian error bounds for stochastic LTI systems with inputs and sub-Gaussian noise. Bound rates depend on noise and loss type, improve for more stable and less noisy systems, and extend to parameter estimation with a more conservative rate than classical asymptotic theory.

4 Discussion on the bound and conclusions

  • The bounds improve with greater system stability, lower sub-Gaussian noise, and logarithmic dependence on the confidence level.Bounds increase with the noise norm and with predictor and data-generator Markov-parameter norms and mixing coefficients.Source: §4 · p. 9
  • Convergence is fastest for bounded noise, slower for Lipschitz losses, and slowest for quadratic losses with general sub-Gaussian noise.Table 2 summarizes convergence rates by noise and loss type.Source: §4 · p. 9, Table 2 · p. 10
  • Parameter-estimation bounds depend additionally on input persistence of excitation and model identifiability; richer inputs and greater model separation yield tighter bounds.The bounds can use H2 distance between systems or Euclidean distance between parameters, and can bound system matrices up to similarity.Source: §4 · p. 9
  • The parameter-estimation rate is more conservative than classical asymptotic theory, in exchange for high-probability, nonasymptotic guarantees across a broad class of algorithms and a simultaneous generalization-gap bound.The authors contrast this with existing finite-sample bounds that are often algorithm-specific and do not address the generalization gap.Source: §4 · pp. 9–10

A Proofs of Section 2

These proofs relate the paper’s state-space representations to innovation form and establish conditions for stable predictors and their limiting errors. They also show that stable filtering preserves stationarity and supports the definition of true prediction error.

A Proofs of Section 2

  • With zero-mean noise, the model is in innovation form: the noise is the difference between the joint output-input process and its best linear prediction from its past.The appendix also relates the innovation-form and steady-state Kalman-filter representations when there is no feedback from output to input.Source: A Proofs of Section 2 · p. 13
  • Stable parameterizations can be constructed using canonical forms or balanced forms with diagonal observability and controllability Gramians.The balanced-form construction ensures stability by using diagonal quadratic Lyapunov functions and bounded parameterization quantities.Source: A Proofs of Section 2 · p. 13
  • For stable predictors, the limiting output is a causal, time-invariant, stable LTI filter of the stationary input, and therefore is stationary.The proof obtains the limit in mean square and shows that finite-start predictions converge to it.Source: A Proofs of Section 2 · p. 13
  • The true error is the limiting expected loss as predictions use an increasingly long past, with the limiting prediction process defining that error.The appendix also gives a converse representation for an input generated by an ARMA process without feedback, and describes the feedback case.Source: A Proofs of Section 2 · pp. 13–14

B Proofs of Section 2.3

These proofs establish that stability and the stated assumptions make the quantities used in the bounds well-defined. They also relate prediction residuals to filter differences and establish stationarity of the filters.

B Proofs of Section 2.3

  • For a stable deterministic LTI system, the Markov-parameter sequence has finite ℓ1 norm and finite WDMC θ∞, with both bounded using matrix norms and a geometric stability rate.The bounds decrease as the spectral radius of the system matrix decreases.Source: B Proofs of Section 2.3 · p. 14
  • Under Assumptions 2.1 and 2.2, the predictor and envelope impulse-response norms and the constants used in the learning bounds are well-defined real numbers.The proof uses uniform bounds on the system matrices and geometric decay of powers of the predictor matrix.Source: B Proofs of Section 2.3 · p. 15
  • The output prediction residuals equal the convolution of the data-generator output filter minus the predictor filter with the generator innovation.For finite-start prediction, the predictor filter is truncated according to the elapsed prediction horizon.Source: B Proofs of Section 2.3 · p. 15
  • The two LTI filters in the lemma are stationary, as stable LTI filtering preserves stationarity.The proof also establishes the required filter identities and bounds on the constants.Source: B Proofs of Section 2.3 · pp. 15, 16, 18

C Proof of Theorem 3.1

The proof of Theorem 3.1 introduces an unbiased infinite-past empirical error and applies a general PAC-Bayesian argument. It handles bounded noise and Lipschitz losses directly, and reduces quadratic loss to the Lipschitz case.

C Proof of Theorem 3.1

  • The infinite-past empirical error VN(θ) is an unbiased estimate of the true error L(θ).The proof first introduces this auxiliary quantity as a step toward the theorem.Source: C Proof of Theorem 3.1 · p. 18
  • A general theorem bounds the gap between true, infinite-past empirical, and finite-past empirical errors with probability at least 1 − 2δ.Its bound includes the prior-posterior KL divergence, the confidence term, and moment-generating-function terms; an out-of-domain moment-generating function makes the bound trivially true.Source: C Proof of Theorem 3.1 · p. 18
  • For bounded innovation noise or Lipschitz loss, the proof bounds the relevant moment-generating functions; for quadratic loss, it reduces to Lipschitz loss with probability δ/3.The quadratic-loss step applies the Lipschitz result using δ/3 in place of δ.Source: C Proof of Theorem 3.1 · p. 18

C.1 Proof of Theorem 3.1: bounded case

The bounded-case proof establishes conditions that make the loss-based prediction error amenable to concentration bounds. It then combines the bounded-case lemmas to prove Theorem 3.1.

C.1 Proof of Theorem 3.1: bounded case

  • For quadratic loss, the proof uses Cauchy–Schwarz; for Lℓ-Lipschitz loss, the loss already has the required Lipschitz property.The proof defines L(θ) as 2Ge(θ)√nece for quadratic loss and Lℓ for Lℓ-Lipschitz loss.Source: §C.1 · p. 19
  • The observed and predicted output pairs lie within a set whose maximum distance is Ge(θ)√nece.This bounded-distance property also holds for the predictor initialized at a finite past time.Source: §C.1 · p. 19
  • For quadratic loss, the proof extends the error function from the bounded output-pair set to a 1-Lipschitz function on the full domain.For an Lℓ-Lipschitz loss, the function is already defined on that full domain.Source: §C.1 · p. 20
  • Theorem 3.1 follows by applying the bounded-case lemmas to bound the moment generating functions of the prediction-error deviations.The proof substitutes the bounds from Lemmas C.5 and C.6 into Theorem C.1.Source: §C.1 · p. 20

C.2 Proof of Theorem 3.1: unbounded processes and Lipschitz loss functions

For sub-Gaussian but potentially unbounded noise, the proof reduces the prediction-error bounds to the bounded-noise case by truncating the noise. It then uses the resulting moment-generating-function bounds to establish Theorem 3.1 for Lipschitz losses.

C.2 Proof of Theorem 3.1: unbounded processes and Lipschitz loss functions

  • The argument assumes sub-Gaussian noise but does not assume that the noise process is bounded.Bounded processes are included because they also have the stated sub-Gaussian property.Source: §C.2 · p. 20
  • Truncating the unbounded noise reduces the two prediction-error deviation bounds to the corresponding bounded-noise problem.The proof reuses Lemmas C.5 and C.6 for the truncated noise.Source: §C.2 · p. 21
  • The proof bounds moment-generating functions of the differences between the original and truncated errors using the Lipschitz property of the loss.The differences considered include both empirical and true errors, uniformly over θ.Source: §C.2 · p. 21
  • The theorem statement follows from Theorem C.1 by replacing E[e2λϵ(VN(θ)−ˆ LN(θ))] and E[e2λϵ(L(θ)−VN(θ))] with their upper bound from (44).Source: §C.2 · p. 23

C.3 Proof of Theorem 3.1: quadratic loss

For quadratic loss, the proof controls prediction errors using sub-Gaussian tail bounds, then replaces the quadratic loss with a Lipschitz-truncated loss. This permits application of the Lipschitz-loss result to obtain the stated high-probability bound.

C.3 Proof of Theorem 3.1: quadratic loss

  • The quadratic-loss proof replaces the loss with ℓC, which is 2C-Lipschitz.The proof applies Theorem 3.1 for Lipschitz loss to this replacement.Source: §C.3 · pp. 29–30
  • The proof establishes that the quadratic-loss inequality (8) holds with probability at least 1 − 2δ over the data.The conclusion is stated for both ϵ values in {−1, 1}.Source: §C.3 · p. 31
  • The proof bounds prediction-error norms using sub-Gaussian tails, with their sub-Gaussian norms bounded by 6Ge∥eg∥ψ2.The bound applies to both the steady-state and finite-past predictors.Source: §C.3 · p. 33

C.4 Proof of Corollary 3.2

The appendix derives Corollary 3.2 by selecting and bounding the theorem’s constants, then establishes uniform bounds under additional model and noise assumptions. It also explains how probability guarantees over data extend to posterior-sampled parameters.

C.4 Proof of Corollary 3.2

  • The proof of Corollary 3.2 selects λ and upper-bounds the right-hand side of inequality (8).The proof considers the Lipschitz-loss and quadratic-loss cases separately.Source: §C.4 · pp. 34–35

C.5 Uniform bounds derived from Corollary 3.2

  • The uniform PAC bounds require (LipModel) and either (Gauss) or (Uni), and include continuity bounds for true and empirical errors.The continuity result is stated in Lemma C.23.Source: §C.5 · pp. 36, 38

D Proof of Corollary 3.4

  • A relationship that holds with probability at least 1 − δ over data also holds with that probability over data and samples from a data-dependent posterior.The appendix introduces this joint probability interpretation for random posterior densities.Source: D Proof of Corollary 3.4 · p. 42

D.1 Proof of the (11) on empirical error

This section establishes properties of Gibbs posteriors and uses them to prove empirical-error bounds for posterior draws and related estimators. It also combines probability bounds to establish the result in (12).

D.1 Proof of the (11) on empirical error

  • The Gibbs posterior is defined by exponentially weighting the prior by empirical loss, and its variational identity relates expected empirical loss and KL divergence to the prior.The second equality is identified as Donsker–Varadhan’s variational formula [2, Lemma 2.2].Source: §D.1 · p. 43
  • The single-draw bound holds with probability at least 1 − 2δ over the data and draws from a data-dependent posterior, under the stated condition on λ.For the Gibbs posterior, the passage also states a bound when ϵ = 1.Source: §D.1 · p. 43
  • The proof of (116) applies the relevant exponential-moment bounds for bounded, Lipschitz, and quadratic losses.The quadratic-loss argument uses the Lipschitz-loss case and the corresponding loss definitions.Source: §D.1 · p. 44

D.2 Proof of (12)

  • For (12), replacing δ with δ/2 gives probability at least 1−(2+rLip,1)δ; for MEP, (12) follows with probability at least 1−4δ.When θ⋆ is MEP, L(θ⋆) ≤ Eθ∼ρGibbs L(θ).Source: §D.2 · pp. 47–48

D.3 Proof of (13)

The proof derives (13) from (12) under the stated strong-convexity condition, then derives (14) using the quadratic-loss setting. These steps rely on the true system being optimal in mean square for that loss.

D.3 Proof of (13)

  • Under (SConv), the proof obtains (13) from (12).The passage cites results on strong convexity before making this implication.Source: §D.3 · p. 49

D.4 Proof of (14)

  • For quadratic loss, the true system yields the best possible prediction in the mean-square sense.The true parameter therefore corresponds to the smallest possible generalization loss for this loss function.Source: §D.4 · p. 49

D.5 Remark on relationship with system identification and learning

The remarks connect the bounds to system-identification estimators and optimization methods, and compare their scope and conservatism with prior finite-sample results. They also identify assumptions and conditions relevant to interpreting parameter bounds.

FIR and likelihood connections

  • For the stated FIR setting with finite parameter-space volume, maximum likelihood equals the MAP estimate of the Gibbs posterior with a uniform prior.The likelihood is proportional to an exponential weighting of empirical quadratic loss.Source: §D.5 · pp. 49–50
  • For the stated Bayesian LTI identification setting, a random draw, MEP, or MAP from the conditional parameter density corresponds to the same estimator from the Gibbs posterior.The passage states that bounds (11)–(14) apply to these estimators.Source: §D.5 · p. 50

PEM methods

  • A PEM cost of empirical loss plus a regularizer can correspond to a Gibbs-posterior MAP estimate; random initialization can also induce a posterior distribution covered by a single-draw bound.A quadratic regularizer corresponds to a Gaussian prior, and the latter bound requires the induced distribution to have a density in Mπ.Source: §D.5 · p. 50

Assumptions and parameter bounds

  • Strong convexity of true error is described as an identifiability and persistence-of-excitation assumption, implying no parameter has the same input-output behavior as the true system.The passage also notes that local strong convexity is a standard assumption for studying asymptotic parameter-estimation error.Source: §D.5 · p. 50
  • Assuming all LTI systems in the family are minimal, (14) can yield a high-probability bound on the difference between learned and true system matrices.The passage also offers structure-index parameterizations as an alternative route using local approximation by H2 norms.Source: §D.5 · p. 50

Comparison with related bounds

  • The bound in is more conservative, while the constants used here are easier to estimate or upper bound in practice.For [8], the bound uses cθ, which depends on the unknown data generator and is difficult to evaluate in practice.Source: §D.5 · p. 51

Comparison with finite-sample bounds

  • Earlier finite-sample bounds typically target specific algorithms and often assume a deterministic initial state, whereas these results assume stationarity and include stochastic components.The passage notes that process noise can make the initial state random through past disturbances.Source: §D.5 · p. 51

System-identification connections and scope

  • The results cover a broad class of algorithms, assume a stationary data-generating regime, account for deterministic and stochastic components, and provide generalization-gap bounds.The stated trade-off is a more conservative bound on the square of parameter-estimation error than the rates in the cited works.Source: §D.5 · p. 51
Loading 2609.08740v1…