arXiv CSopen access

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

· arxiv_cs

arXiv CS · Papers · License: Open Access

machine learning, deep learning, neural networks

arXiv:2609.08740v1 [cs.LG] 8 Sep 2026

Mihaly Petreczky CRIStAL, Centrale Lille, Université de Lille, France, [email protected] Mohamad Al Ahdab Department of Electronic Systems, Aalborg University, Denmark, [email protected] John Leth Department of Electronic Systems, Aalborg University, Denmark, [email protected]

Abstract 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. 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.

Introduction

PAC and PAC-Bayesian bounds are fundamental tools for analyzing learning algorithms. They provide generalization guarantees that relate the true error (performance on unseen data) to the empirical error (performance on training data), by bounding the generalization gap, the difference between true and empirical error, in a way that is independent of the specific learning algorithm. In this framework, learning is viewed as selecting a model from a data-dependent posterior distribution over hypotheses, which is a modification of a prior based on the observed data. Different learning algorithms correspond to different choices of priors, posteriors, and selection mechanisms (e.g., sampling, averaging, or maximizing the posterior). PAC-Bayesian bounds then provide a uniform upper bound on the average generalization gap with respect to any posterior, thus offering generalization guarantees for a broad class of learning and model selection methods. This generality makes PAC-Bayesian approaches especially useful for analyzing complex models, including neural networks, where they can yield non-vacuous generalization bounds [7]. Although PAC and PAC-Bayesian theory is well developed for i.i.d. settings [36, 2, 17], there are comparatively few results for dynamical systems. Contribution: In this paper, we derive PAC-Bayesian error bounds for learning discrete-time stochastic LTI state-space systems with sub-Gaussian noise and partial observations (the full states Preprint.

is not observed). Following standard practice in system identification, we view LTI systems as predictors that generate predictions for the current output based on past inputs and outputs. Our main contribution is a PAC-Bayesian bound showing that, with high probability (at least 1 − δ), for any )r posterior distribution over predictors, the average generalization gap is O( (ln√N ), where N is the N sample size, r = 0 for bounded noise, r = 1 for Lipschitz loss, and r = 3/2 for quadratic loss. The bound depends on the Kullback–Leibler (KL) divergence between prior and posterior distributions and on ln(1/δ). We subsequently derive generalization gap and parameter estimation error bounds for concrete learning algorithms (e.g., maximum likelihood, regularized prediction-error methods (PEM), and Bayesian methods). Related work: PAC and PAC-Bayesian bounds for autoregressive models with bounded signals or Lipschitz loss have been studied in [5, 44, 3, 1, 27, 29]. In contrast, our results address state-space models with partially observed states and with inputs, which are more general than autoregressive models, and we allow for unbounded (sub-Gaussian) noise, and handle quadratic loss. We also build on techniques from [3, 1]. In contrast to the literature on finite-sample parameter estimation bounds for specific least-squares based learning algorithms for LTI systems, e.g., [38, 37, 32, 24, 14, 19, 42, 20, 35], this papers presents bounds on both the parameter estimation and the generalization gap for a wide-range of algorithms, see Remark D.12, Appendix D.5 for a detailed comparison. PAC bounds for recurrent neural networks, of which LTI state-space representations are a subclass, have been developed using VC dimension [23, 41], Rademacher complexity [23, 41, 6], and PACBayesian approaches [7]. However, existing results assume noiseless models, fixed prediction horizons, i.i.d. training data samples, and bounded signals. In contrast, this paper considers noisy models, infinite-horizon prediction errors, a single observed time series, and unbounded signals with sub-Gaussian noise. In [12], bounds based on Rényi divergence were proposed, but the resulting probabilistic guarantees scale as O(1/δ) with the confidence level, rather than the standard O(ln(1/δ)), and it applies only to quadratic losses as opposed to general Lipschitz losses, and it provides parameter estimation bounds only in terms of the empirical error. In contrast, the bound of this paper depends on the confidence level O(ln(1/δ)) and it provides an absolute bound on the parameter estimation error. The works [11, 8] provide PAC-Bayesian generalization gap bounds for RNNs and LTI systems with bounded noise, respectively. In contrast, the present paper addresses unbounded (sub-Gaussian) noise and also derives parameter estimation error bounds. Even for bounded signals, our results refine the constants used in [11, 8] (see Remark D.11, Appendix D.5). PAC-Bayesian bounds for autonomous LTI systems without inputs were considered in [9] but those bounds did not converge to zero as N → ∞. Paper Outline: We start by defining the problem formulation in Section 2, followed by the main results in Section 3 and discussion of the bounds in Section 4. The technical proofs are presented in the appendices.

Problem formulation

2.1

Notation and terminology

We occasionally use ≜ to denote ”defined by”. Let F denote a σ-algebra on the set Ω and P be a probability measure on F. Unless otherwise stated, all probabilistic considerations will be with respect to the probability space (Ω, F, P), and we let E[z] denote expectation of the stochastic variable z. We use bold face letters to indicate stochastic variables/processes relative to (Ω, F, P). Each euclidean space is associated with the topology generated by the 2-norm ∥ · ∥2 , and the Borel σ-algebra generated by the open sets. The induced matrix 2-norm is also denoted ∥ · ∥2 . Let BΘ be the σ-algebra of Lebesgue-measurable subsets of Θ ⊂ Rnθ , and m the Lebesgue measure. For a probability R density ρ on (Θ, BΘ , m) and a measurable, integrable function g : Θ → R, define Eθ∼ρ [g(θ)] ≜ Θ ρ(θ)g(θ)dm(θ) as the expectation of g under ρ. For a density π on Θ, let Mπ denote the set of all densities on Θ whose probability measure is absolutely continuous w.r.t. the probability measure of π. 2

R Let vol(A) = A dm(θ) denote the Lebesgue measure of A ⊆ Rnθ . The uniform distribution on a χA (θ) measurable set A ∈ BΘ is ρ(θ) = vol(A) , where χA is the indicator function. For A = Θ, this is the uniform distribution on Θ. The phrase probability over data refers to probability under P on (Ω, F). Specifically, for measurable functions {Xi , Yi }i∈I and a binary relation ⋄, we say ∀i ∈ I : Xi ⋄ Yi holds with probability at least 1 − δ over data if the set F = {ω ∈ Ω : ∀i ∈ I, Xi (ω) ⋄ Yi (ω)} satisfies P(F ) ≥ 1 − δ. 2.2

Problem formulation

The problem formulation follows [11, 8, 12]. Let us fix stationary stochastic processes y(t) ∈ Rny , and u(t) ∈ Rnu , that share a time axis t ∈ Z, that is, for any t ∈ Z, y(t) : Ω → Rny ; ω 7→ y(t)(ω), and u(t) : Ω → Rnu ; ω 7→ u(t)(ω) are random vectors on (Ω, F, P): y represents outputs (labels), and u represents inputs (features). The −1 goal is to learn models from the finite sample D = {y(t)(ω), u(t)(ω)}N t=0 , ω ∈ Ω, such that the learned model predicts y from past measurements of (y, u) sufficiently well. Predictor class: To simplify notation, let us define a stochastic process w(t) ∈ Rnw by w(t) = yT (t),

uT (t)

when nw = ny + nu and both past y and u are used for prediction,

w(t) = u(t) when nw = nu , when only past u is used for prediction. Note that with a trivial extension of the results of this paper one can define w(t) to consist of only some of the components of y(t), extending the results to not only prediction but also filtering. Assumption 2.1 (Predictors). The class of predictors is the class of LTI systems parametrized by θ ∈ Θ ⊆ Rnθ which generate predictions ŷθ (t|t0 ) of y(t) based on {w(s)}ts=t0 x̂(t + 1) = Âθ x̂(t) + B̂θ w(t), x̂(t0 ) = 0,

ŷθ (t|t0 ) = Ĉθ x̂(t) + D̂θ w(t),

t ≥ t0 ,

(1)

where Âθ ,B̂θ , Ĉθ , D̂θ are n̂ × n̂, n̂ × nw , ny × n̂ and ny × nw matrices respectively, they are are continuous in θ, and Âθ is Schur (all its eigenvalues are inside the unit disk). Moreover, if w(t) = [yT (t) uT (t)]T , then D̂θ = [0 D̂u,θ ] for some ny ×nu matrix D̂u,θ . 1 Moreover, there exist constants M, C > 0, γ ∈ (0, 1) such that for all θ ∈ Θ, ∥Âkθ ∥2 ≤ M γ k , max{∥B̂θ ∥2 , ∥Ĉθ ∥2 , ∥D̂θ ∥2 } ≤ C. Intuitively, our assumption expresses that the predictors are stable LTIs and we have a uniform upper bound on the matrices and on the spectral radius of Âθ . These assumptions are standard in system identification, see Remark A.3, Appendix A. Note that the predictors are started at the zero initial state at inital time t0 . The latter represents the time instant at which the predictor was applied to generate predictions, or when learning started. Most of the time, we will set t0 = 0 to simplify notation. Data generator: Intuitively, we would like the data y to be generated by an LTI system ŝg (t + 1) = A0 ŝg (t) + B0 u(t) + K0 es (t),

y(t) = C0 ŝg (t) + D0 u(t) + es (t),

t ∈ Z,

(2)

where A0 , B0 , K0 , C0 , D0 are matrices of suitable dimension, A0 and A0 − K0 C0 are both Schur, and es (t) is a zero-mean i.i.d. sub-Gaussian process. The Schur conditions ensure stationarity of x and that es (t) is the innovation process (see [26, Chapter 4, p. 87]), i.e., the difference between y(t) and its best linear predictor based on past inputs and outputs. Thus, (2) is in steady-state Kalman filter form. Unlike predictors, the data generator (2) is assumed to operate in steady state, i.e., it has run for infinite time prior to prediction. This standard assumption in system identification (e.g., [26]) reflects that the physical system has been subject to noise and inputs long before learning begins. This subtle difference has significant theoretical implications. Assuming the data is generated by a system of the same form as the predictors is a realizability assumption, as (2) yields the optimal predictor. ŝg (t + 1 | t0 )=Â0 ŝg (t) + B̂0 w(t), ŝg (t0 |t0 ) = 0, 1 The latter assumption is necessary, as it guarantees that D̂

ŷ(t | t0 )=Ĉ0 ŝg (t | t0 ) + D̂0 w(t),

(3)

θ w(t) depends only on u(t) and hence it does not depend on y(t), since otherwise we would be using y(t) to predict y(t), which is not meaningful.

where t ≥ t0 , Â0 = A0 , B̂0 = B0 , Ĉ0 = C0 , D̂0 = D0 if nw = nu and Â0 = A0 − K0 C0 , B̂0 = [K0 B0 − K0 D0 ], Ĉ0 = C0 , D̂0 = [0 D0 ] if nw = nu + ny . When w(s) = [yT (s), uT (s)]T , the predictor (3) corresponds to stationary Kalman-filter and it is an optimal predictor of y(t) in the mean square error sense. Formally, instead of assuming the existence of (2), for the data generator we use the following assumption, which is essentially equivalent to the existence of (2). Assumption 2.2. Let y(t) and u(t) be generated by an autonomous stochastic LTI system y(t) x(t + 1) = Ag x(t) + Kg eg (t), = Cg x(t) + eg (t) (4) u(t) with Ag ∈ Rn×n , Kg ∈ Rn×ne , Cg ∈ Rne ×n , for some n > 0, and ne = ny + nu ≥ 2, Ag and Ag − Kg Cg are Schur. Moreover, x(t) has finite variance, eg (t) is independent of x(t) for all t ∈ Z, and eg is square integrable, i.i.d process, ∥eg (t)∥2 is sub-Gaussian and the sub-Gaussian norm of ∥eg (t)∥2 [43, Definition 2.6.4] is denoted by ∥eg ∥ψ2 . If eg (t) is sub-Gaussian, then ∥eg (t)∥2 is also sub-Gaussian, see [21, Lemma 1]. Under Assumption 2.2, y and u are jointly stationary and square integrable processes [4]. Under mild conditions, Assumption 2.2 is equivalent to the existence of an LTI system (2), see Remark A.2 in Appendix A. Assumption 2.2 is more convenient, and it is often used in system identification [22, Chapter 9]. Measure of prediction accuracy: Following standard practice in system identification [26], we measure the predictive accuracy using a loss function ℓ : Rny × Rny → [0, ∞) which is continuous and satisfies ℓ(y, y) = 0. Typical choices are ℓ(y, ŷ) = ∥y − ŷ∥2 , to which we refer to as ℓ2 loss, and ℓ(y, ŷ) = ∥y − ŷ∥22 to which we refer to as the quadratic loss. Assumption 2.3 (Qudaratic or Lipschitz loss functions). The loss function ℓ is either quadratic or it is Lℓ -Lipschitz, i.e., for all y1 , y2 , ŷ1 , ŷ2 ∈ Rny , |ℓ(y1 , ŷ1 ) − ℓ(y2 , ŷ2 )| ≤ Lℓ (∥y1 − y2 ∥2 + ∥ŷ1 − ŷ2 ∥2 ). We define the true error as the limit L(θ) ≜

lim E[ℓ(y(t), ŷθ (t | t0 ))].

t0 →−∞

(5)

The true error captures the long-term, steady-state prediction error obtained during the deployment of the predictor on an increasing number of past inputs. Lemma 2.4. Let Assumptions 2.2, 2.1, and 2.3 hold. Then the limits ŷθ (t) = limt0 →−∞ ŷθ (t | t0 ) and limt→∞ (ŷθ (t) − ŷθ (t | 0)) = 0 exist in the mean-square sense for all t and θ, the process ŷθ (t) is stationary, and L(θ) = E[ℓ(y(t), ŷθ (t))] = limt→∞ E[ℓ(y(t), ŷθ (t | 0))]. The proof of Lemma 2.4 is presented in Appendix A. Intuitively, ŷθ (t) is the output predicted by the LTI system corresponding to θ, if the latter is started from zero at −∞, and as t grows, ŷθ (t) and ŷθ (t | 0) converge to each other. The Learning Problem is to find a parameter θ⋆ from sampled data D of the sequence of random −1 variables {y(t), u(t)}N t=0 which minimizes the true error, i.e., θ⋆ ∈ arg min L(θ). Note that we do not assume the knowledge of the matrices Ag , Kg , Cg and noise process eg when learning. Since the true error is unknown, a standard practice is to use the empirical error N −1

L̂N (θ) =

1 X ℓ(y(t)(ω), ŷθ (t|0)(ω)) N t=0

(6)

as a proxy for the true error, and try to find a model θ̂ for which the empirical error L̂N (θ̂) is small. While doing so, we would like to keep the generalization gap L(θ) − L̂N (θ), i.e., the difference between a model’s performance on the training data (empirical error) and its expected performance (true error) on unseen test data, small. The PAC-Bayesian approach provides a framework to derive such guarantees. 2.3

Constants used in PAC-bounds

In order to present the main result, we will need several constants, many of which have an interesting system-theoretic interpretation. 4

Definition 2.5 (Convolution and ℓ1 norm). Let α = {α(k)}∞ k=0 be a sequence of matrices. Define the ℓ1 norm ∥α∥ℓ1 and the weakly dependent mixing coefficient (WDMC) θ∞ (α) of α as ∥α∥ℓ1 =

∞ X

∥α(k)∥2 ,

θ∞ (α) =

k=0

∞ X

k∥α(k)∥2 .

k=0

If ∥α∥ℓ1 < ∞ and r is a stationary square integrable stochastic P∞ process, then define the convolution (α ⋆ r) of α with r as the stochastic process (α ⋆ r)(t) = k=0 α(k)r(t − k). By [4, Theorem 1.1], (α ⋆ r) is well-defined and stationary. Intuitively, the ℓ1 norm of a sequence is the extension of the standard norm on the space of absolutely summable scalar sequences to the case of matrix valued ones. The convolution (α ⋆ r) represents the response of a linear filter with impulse response α to the noise r, and ∥α∥ℓ1 represents the ℓ1 norm of the filter. If r is bounded, i.e., ∥r(t)∥2 < C, then the convolution (α ⋆ r)(t) is bounded, i.e., ∥(α ⋆ r)∥2 < ∥α∥ℓ1 C, and it is a weakly dependent process, in the sense of [3], whose mixing coefficients {θ∞,n (1)}∞ n=1 are bounded by 2θ∞ (α)C, [3, Proposition 4.12]. Intuitively, the smaller θ∞ (α) is, the closer (α ⋆ r)(t) is to being i.i.d., if r is i.i.d. If α is the sequence of Markov parameters of a stable LTI system, then both ∥α∥ℓ1 and θ∞ (α) are finite and can be upper bounded in terms of bounds on the norms of the system matrices and the spectral radius of the system matrix A, see Remark B.1. Definition 2.6 (Auxiliary definitions). Let us consider the Markov-parameters αg and αθ of the data generator (4) and predictor (1) corresponding to θ ∈ Θ respectively: bθ A bk−1 B bθ k > 0 C Cg Ak−1 Kg k > 0 g θ αg (k) = , αθ (k) = (7) bθ k = 0 I k=0 D Let ᾱ(k) = supθ∈Θ ∥αθ (k)∥2 . With notation as above Ge (θ) ≜ (1 + ∥αθ ∥ℓ1 )∥αg ∥ℓ1 , Ge ≜ (1 + ∥ᾱ∥ℓ1 )∥αg ∥ℓ1 ,

Ge,1 (θ) ≜ θ∞ (αθ )∥α∥ℓ1 + θ∞ (αg )(∥αθ ∥ℓ1 + 1)

Ge,1 ≜ θ∞ (ᾱ)∥αg ∥ℓ1 + θ∞ (αg )(∥ᾱ∥ℓ1 + 1)

For the definition of the upcoming bounds, we are going to use the quantities ∥α∥ℓ1 , θ∞ (α) for α ∈ {αg , ᾱ} ∪ {αθ | θ ∈ Θ} and the constants Ge (θ), Ge,1 (θ), Ge , Ge,1 defined above. Note that all these quantities are well-defined, see Lemma B.2. In addition, they are related to the true T outputs y(t) and predicted outputs ŷθ (t), ŷθ (t | t0 ) as follows: yT (t) uT (t) = (αg ⋆ eg )(t), ŷθ (t) = (αθ ⋆ w)(t), ŷθ (t | t0 ) = (αθ,t−t0 ⋆ w)(t). The formal relationship between the constants is provided in Lemma B.3, Appendix B. The interpretation of the various terms appearing in Definition 2.6 is as follows • ∥αg ∥ℓ1 , θ∞ (αg ) are the ℓ1 norm and the mixing coefficients of Markov-parameters of the data generator: both quantities decrease with stability of the data generator, see Remark B.1. • ∥αθ ∥ℓ1 is the ℓ1 norm of the predictor (1). This term decreases with the spectral radius of the predictor, see Remark B.1. • θ∞ (αθ ) describes the mixing properties of the output generated by the predictor, and it also PN −1 bounds the sum of differences between the infinite and finite past prediction t=0 ∥ŷθ (t)− ŷθ (t | 0)∥. Intuitively, the smaller θ∞ (αθ ) is, the closer ŷθ (t | 0) is to ŷθ (t). This quantity decreases with the spectral radius of the predictor by Remark B.1. • Ge,1 (θ) characterizes mixing properties (short memory condition [1]) of the prediction error y(t) − ŷθ (t). Intuitively, the smaller Ge,1 (θ) is, the more the prediction error behaves like an i.i.d process. This constant is related to stability of the generator and the predictor, the smaller the spectral radius of those systems are , the smaller this constant is. • ∥ᾱ∥ℓ , θ∞ (ᾱ), Ge , Ge,1 are uniform upper bounds on ∥αθ ∥ℓ1 , θ∞ (αθ ), Ge (θ), Ge,1 (θ) respectively.

Main result

We start by presenting the main result of the paper, which is the following theorem. 5

Theorem 3.1 (Main result). Let Assumptions 2.2, 2.3 and 2.1 hold. For any a prior distribution π over Θ, confidence level δ ∈ (0, 0.5), integer ϵ ∈ {−1, 1}, and N ≥ Kδ , the inequality ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ)+ 2 Cδ 1 1X KL(ρ∥π) + ln + ln Eθ∼π exp (Ci (2λ, θ, N, δ, ϵ)) λ δ 2 i=1

(8)

ρ(θ) holds with probability at least 1 − 2δ over data, with KL(ρ∥π) = Eθ∼ρ ln π(θ) the Kullback–Leibler divergence and the constants Kδ , Ci (λ, θ, N, δ, ϵ), i = 1, 2 and Cδ are defined as follows:

Bounded noise: If ∥eg (t)∥∞ ≤ ce , then Cδ = 1, Kδ = 2, λ > 0, and Cm,b,i (λ, αθ , Ge (θ) + 2Ge,1 (θ), L(θ), ce ) Ci (λ, θ, N, δ, ϵ) ≜ Cb,i (λ, θ, L(θ), ce , N ) ≜ N √ 2Ge (θ)ce ne ℓ is quadratic loss L(θ) ≜ Lℓ ℓ is Lℓ -Lipschitz √ λLce ne θ∞ (α)∥αg ∥ℓ1 i = 1 2 √ Cm,b,i (λ, α, X, L, ce ) ≜ λ2 L2 X( ne ce )2 i = 2 N Lipschitz loss: If ℓ is Lℓ -Lipschitz, then Cδ = 1, Kδ = 2, 0 < λ < 16L , and ℓ 2 ln(N ) 1 , N + C¯ub (λ, L(θ), N ) Ci (λ, θ, N, δ, ϵ) ≜ Cub,i (λ, θ, L(θ), N ) ≜ Cb,i 2λ, θ, L(θ), 2 ∥αg ∥ℓ1 K 2

2 2

λ 32L(θ) Cu,1 4λL(θ)Cu,2 ln(N ) λ 32Lℓ Cu,1 4λLℓ Cu,2 ln(N ) C¯ub (λ, L(θ), N ) ≜ + = + N N N N where the constants, K,Cu,j , j = 1, 2 are defined as follows: Cu,1 ≜ Ψ̄eg (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 ) + Ψ̄eg (∥αg ∥ℓ1 ), Cu,2 ≜ Ψ̄e (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 )

Ψ̄eg (s) = e14 s ∥eg ∥ψ2 +3s∥eg ∥ψ2

∥ᾱ∥2ℓ1 ∥αg ∥ℓ1 ∥αg ∥ℓ1 + Ψ̄eg (∥αg ∥ℓ1 ) , K K

(9) K = min{1, ∥ᾱ∥ℓ1 }

N , Quadratic loss: if ℓ is the quadratic loss, then Cδ = 32 , Kδ = 3, 0 < λ < 16L qd

λL2qd max{0, ϵ} Ci (λ, θ, N, δ, ϵ) ≜ + Cub,i (λ, θ, Lqd , N ) , 2N

s 3N 2 Lqd = 12Ge ∥eg ∥ψ2 ln 2δ

For ϵ = 1, (8) bounds the average generalization gap Eθ∼ρ (L(θ) − L̂N (θ)); for ϵ = −1, it bounds Eθ∼ρ (L̂N (θ) − L(θ)). The latter is useful for deriving oracle inequalities. By applying the union bound to both cases, we obtain a bound on Eθ∼ρ (L(θ) − L̂N (θ)) . Note that except for the quadratic loss case with potentially unbounded data, Ci (λ, θ, N, δ, ϵ) is independent of δ and ϵ. Intuition behind the proof: The proof of Theorem 3.1 is in Appendix C. The key idea is to dePN −1 compose the generalization gap using an auxiliary empirical error VN (θ) = N1 t=0 ℓ(y(t), ŷθ (t)) where the predictor has run for infinite time (started at t0 = −∞). Since E[VN (θ)] = L(θ), we have ϵ(L(θ) − L̂N (θ)) = ϵ(L(θ) − VN (θ)) + ϵ(VN (θ) − L̂N (θ)). The constants exp(C1 ) and exp(C2 ) bound the moment generating functions of these two differences. The PAC-Bayesian bound then follows by standard concentration arguments [2, Chapter 2]. Bounded case: C1 is obtained by direct calculation, and C2 via Rios’s concentration inequality for weakly-dependent processes [1, Prop. 4.2], improving upon constants in [11, 8]. Unbounded case: We employ a truncation approach [3]. Define truncated data ȳ(t), ū(t) generated 2 ln(N ) from truncated noise ēg (t) = eg (t)χ(∥eg (t)∥ ≤ C) with C = K∥α , where K = min{1, ∥ᾱ∥ℓ1 }. g ∥ ℓ1 We bound the moment generating functions of the differences sup |L̄ˆ (θ) − L̂ (θ)| and θ∈Θ

supθ∈Θ |VN (θ) − V̄N (θ)| by exp(C¯ub (λ, Lℓ , N )). Combining with the bounded-case bounds yields PAC-Bayesian guarantees for unbounded data. Quadratic case: We show that with probability at least 1 − 2δ errors 3 over data, the prediction q 3N 2 satisfy ∥y(t) − yθ (t)∥2 ≤ C and ∥y(t) − yθ (t | 0)∥2 ≤ C for C = 6Ge ∥eg ∥ψ2 ln( 2δ ). The empirical quadratic loss then coincides with the empirical error for the truncated Lipschitz loss ℓC (y, y ′ ) = min{∥y − y ′ ∥22 , C 2 }. The result follows by union bound and the Lipschitz case, noting that the true error difference between the quadratic loss and the truncated loss is O(C 2 /N ). r

) Interpretation and O( ln(N N ) rates: The interpretation of Theorem 3.1 is similar to other PACBayesian bounds [2]: we view learning algorithms as choices of parameters from a data-dependent probability density on model parameters, referred to as posterior ρD , for which the right-hand side of (8) is small for ϵ = 1. One option is to choose ρD as the Gibbs posterior which minimizes of the right-hand side of (8) and which is given by [2, Definition 2.1]: 1 π(θ) exp(−λL̂N (θ)) ρGibbs ≜ argminρ∈Mπ Eθ∼ρ L̂N (θ) + KL(ρ∥π) , ρGibbs (θ) = , λ Eθ∼π exp(−λL̂N (θ))

Once a posterior ρD is obtained, the learned model θ⋆ can be chosen as follows: Mean posterior (MEP): as the mean of the posterior ρD , i.e. θ⋆ = Eθ∼ρD θ, Single draw: draw θ⋆ randomly from ρD , and D Gibbs Maximum posterior (MAP): choose θ⋆ as θ⋆ = argmaxρD (θ). For , it minimizes the ρ =ρ

empirical error regularized using the prior, i.e., θ⋆ = arg minθ∈Θ L̂N (θ) − λ1 ln π(θ) ,

These choices represent well-known classes of system identification algorithms, such as regularized PEM, maximimum likelihood estimation for state-space models, and Bayesian methods, see Remarks D.8, D.5, and D.6 in Appendix D.5. Theorem 3.1 bounds the average generalization gap Eθ∼ρ L(θ) − L̂N (θ) by a sum of two terms: the KL divergence λ1 KL(ρ∥π) between the posterior and the prior, and a complexity term Ci (2λ, θ, N, δ, ϵ) that depends on the data and the prior. For bounded noise, Ci = O(1/N√ ); for ln N ) (ln N )3 Lipschitz loss, Ci = O( N ); and for quadratic loss, Ci = O( N ). By choosing λ = L(lnNN )r with appropriately selected L and r, and thus forcing λ1 KL(ρ∥π) to tend to zero as N → ∞, we obtain an O

(ln N )r √ N

√ Corollary 3.2 (O((ln(N ))r / N ) bound). With the notation and assumptions of Theorem 3.1, L(ln(N ))r Cδ √ ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ) + KL(ρ||π) + ln + C(δ, ϵ) (10) δ N holds with probability at least 1 − 2δ over data, for any prior π, δ ∈ (0, 0.5), and for any ϵ ∈ {−1, 1}, and N ≥ Kδ , where C(δ, ϵ), L, r are defined as follows. Bounded noise: If ∥eg (t)∥∞ ≤ ce , then r ≜ 0, L ≜ 1, and 2 √ 1X 2Ge ce ne ℓ is the quadratic loss Cm,b,i (2, ᾱ, Ge + 2Ge,1 , Lb , ce ), Lb ≜ C(δ, ϵ) ≜ Lℓ ℓ is Lℓ -Lipschitz 2 i=1 Lipschitz loss: If ℓ is Lℓ -Lipschitz, then r ≜ 1, L ≜ 16Lℓ , and ! 2 1X 1 1 ¯ C(δ,ϵ) ≜ Cub = Cu,1 + Cu,2 + Cm,b,i , ᾱ, Ge + 2Ge,1 , 1, , 2 i=1 4 ∥αg ∥ℓ1 K √ q 3 Quadaratic loss: If ℓ is quadratic, then L ≜ 192Ge ∥eg ∥ψ2 2 1 + ln 2δ , r ≜ 3/2, 2 L max{0, ϵ} 1X 1 1 C(δ, ϵ) ≜ + Cu,1 + Cu,2 + Cm,b,i , ᾱ, Ge + 2Ge,1 , 1, 128 2 i=1 4 ∥αg ∥ℓ1 K 7

√

The proof of Corollary 3.2 follows by substituting λ = L(lnNN )r into Theorem 3.1 and simplifying theresulting 3.2 makes the bounds (see Appendix C.4 for the proof). Note that while Corollary √ (ln N )r N O √N rates explicit, Theorem 3.1 may give a tighter bound even for λ = L(ln N )r [2]. The previous results bound the average generalization gap with respect to a posterior ρD . For practical learning, however, we are interested in the generalization gap for a specific choice of θ⋆ (e.g., MEP, MAP, or a single draw from ρD ). Below, we provide such bounds when ρD is the Gibbs posterior √ N with λ = L(ln N )r , where L, r are as in Corollary 3.2. This yields a generalization gap for θ⋆ of order N )r+1 . We now introduce the necessary assumptions for these results. O (ln √ N Assumption 3.3. The following conditions are used in the sequel. (Opt) An optimal model θtrue = arg minθ∈Θ L(θ) exists. (LipModel) The map θ 7→ αθ is Lα -Lipschitz w.r.t. to the ∥ · ∥ℓ1 norm, i.e., ∥αθ1 − αθ2 ∥ℓ1 ≤ Lα ∥θ1 − θ2 ∥2 ,

∀θ1 , θ2 ∈ Θ.

(Gauss) Θ = Rnθ and π is Gaussian N (θm , P ). (Uni) Θ is compact and π is the uniform density on Θ. (SConv) The true error L(θ) is smooth and strongly convex in θ and its Hessian is bounded from below mΘ I ⪯ ∇2θ L(θ) for all θ ∈ Θ. (Real) The predictor Σ(θtrue ) equals the predictor (3) corresponding to the data generator. (PE) The spectral density Φw of w satisfies Φw (iz) ≥ mw I for all z ∈ [−π, π]. Corollary 3.4. Assume the following (1) Assumptions 2.2, 2.1, 2.3 and (Opt) and (LipModel) of Assumption 3.3 hold, and (2) either (Gauss) or (Uni) of Assumption 3.3 holds, and (3) θ⋆ be selected from ρGibbs using MEP, MAP or a single draw, and ρGibbs is computed using √ N λ = λN = 2L(ln(N ))r with r, L, Kδ are as defined in Corollary 3.2. (4) Furthermore, if θ⋆ is chosen using MEP, then assume that (SConv) of Assumption 3.3 holds. Consider the constants Cem (δ, σ), Cor (δ, σ), rLip,1 , rLip,2 as in Table 1, and consider the inequalities L(ln(N ))r+1 √ Cem (θ⋆ , δ) N L(ln(N ))r+1 √ Oracle bound: L(θ⋆ ) − L(θtrue ) ≤ Cor (δ, σ) N L(ln(N ))r+1 Parameter estimation error: ∥θ⋆ − θtrue ∥22 ≤ √ Cor (δ, σ), N mΘ L(ln(N ))r+1 √ H2 error bound: ∥Hθtrue − Hθ⋆ ∥2H2 ≤ Cor (δ, σ) mw N Empirical bound:

L(θ⋆ ) − L̂N (θ⋆ ) ≤

(11) (12) (13) (14)

Then the following holds: (A) (11) holds with probability at least 1 − (2 + rLip,1 )δ, (B) (12) holds with probability at least 1 − 2δ for single draw and MEP, and with probability at least 1 − (2 + rLip,1 )δ for MAP, (C) (13) holds with probability at least 1 − 2δ for single draw and MEP, and with probability at least 1 − (2 + rLip,1 )δ for MAP, if (SConv) of Assumption 3.3 holds, (D) (14) holds with probability at least 1 − 2δ for single draw and MEP, and with probability at least 1 − (2 + rLip,1 )δ for MAP, if (Real) and (PE) of Assumption 3.3 holds, ℓ is the quadratic loss, and Hθ the transfer function of the predictor corresponding to θ, and denote by ∥H∥H2 the H2 norm of the transfer function H. Here, the probability is taken over data for MEP and MAP, and over the data and over all samples θ⋆ drawn from ρGibbs for the single draw. 2 2 The precise meaning of probability over data and samples drawn from ρ Gibbs is explained in Remark D.1

Table 1: Constants for learning bounds under different algorithm choices (Corollary 3.4) Constant LΘ (δ) C(θ) rLip,1 , rLip,2 CL,emp CL,true CL (δ, ϵ) Cem (θ⋆ , δ) C(θtrue , θ⋆ ) Cor (δ, σ)

MEP / Single Draw MAP √ Lα Lℓ ∥αg ∥ℓ1 ne ce bounded noise √ 1 1 Lipschitz/quadratic 16 Lα ne K ) 1 2 −1 T −1 ) − nθ + (θm − θ) P (θm − θ) + ln det(P + nθ (Gauss) 2 σ trace(P σ 2nθ ln (√πσ2 nvol(Θ) + n2θ (Uni) θ Γ(nθ /2+1) 0 eg is bounded 2 ℓ is quadratic and eg is unbounded rLip,1 = rLip,2 = 1 otherwise 0 otherwise LΘ (δ)σ + 2rLip,1 (Cu,1 + Cu,2 ) L CL,emp + 2rLip,2 512 Cδ ln δ + CL,emp + C(θ⋆ ) + C(δ, ϵ) CL (δ, 1) + 2rLip,1 ln 1δ CL (δ, 1) + CL,true + 2rLip,1 ln 1δ CL,true − 2CL,emp

2CL,true − C(θtrue ) + C(θ⋆ ) + ln

π(θtrue ) π(θ⋆ )

C(θtrue , θ⋆ ) + CL ( 2δ , 1) + CL ( 2δ , −1)

In summary, for any outcome θ⋆ obtained via MAP, MEP, or a single draw from the Gibbs posterior, (ln N )r+1 √ Corollary 3.4 yields O bounds on: (1) the generalization gap (11), (2) the excess true N error over the optimal model (12), and (3) the parameter estimation error (13)–(14). The constants for the learning bounds, as given by Corollary 3.4, are in Table 1. The influence of system properties and convergence rates is discussed in Section 4. Intuition behind the proof: The proof of Corollary 3.4 is in Appendix D. For MAP, (11)–(12) are derived from Corollary 3.2 by constructing suitable data-dependent posteriors and applying oracle inequality techniques from [2, Theorem 4.1]. For single draw and MEP, similar arguments apply using [2, Theorems 2.7 and Corollary 2.6] combined with the moment generating function bounds from the proof of Theorem 3.1. Finally, the parameter estimation bounds (13)–(14) follow from the oracle inequality (12) by relating the parameter error to the loss difference through strong convexity (for (13)) or persistence of excitation (for (14)).

Discussion on the bound and conclusions

In this paper, we derived PAC-Bayesian error bounds for stochastic LTI systems with inputs and sub-Gaussian noise. The convergence rates are fastest for bounded noise, slower for Lipschitz losses, and slowest for quadratic losses with general sub-Gaussian noise (see Table 2). All bounds in Theorem 3.1, Corollary 3.2, and Corollary 3.4 improve with increased system stability, lower sub-Gaussian noise norm, and depend logarithmically on the confidence level δ via ln(1/δ). Specifically, the bounds increase monotonically with the sub-Gaussian norm ∥eg ∥ψ2 of the noise, and with the ℓ1 norms and mixing coefficients of the Markov parameters of both the predictors and the data generator (∥αθ ∥ℓ1 , ∥αg ∥ℓ1 , θ∞ (αθ ), θ∞ (αg )). Smaller ℓ1 norms and mixing coefficients correspond to more stable systems and weaker dependence on past inputs, making learning easier. Similarly, a smaller sub-Gaussian norm (i.e., lower noise variance) yields tighter bounds. In summary, the bounds are tighter for less noisy and more stable systems, aligning with intuition: learning is easier when the system is less noisy and more stable. Additionally, if the goal is to bound not only the generalization gap but also the parameter estimation error (in terms of the H2 distance between the true and learned systems (14), or the Euclidean distance between parameters (13)), the bounds also depend on the persistence of excitation of the input w (mw ) and the identifiability constant (mΘ ). Larger values of mw (richer input) and mΘ (greater separation between models) yield tighter bounds. The bound (14) can also be used to bound the system matrices (up to similarity), see Remark D.10, Appendix D.5. √ r+1 For parameter estimation error, our obtained rate O((ln √ N ) / N ) is more conservative than classical asymptotic theory [26, 4] (which yields O(1/ N ) asymptotic consistency) and existing 9

Table 2: Summary of convergence rates for different noise and loss function types Scenario Bounded noise Lipschitz loss Quadratic loss

Empirical PAC-Bayesian Bound O √1N ) √ O ln(N N (ln(N ))3/2 √ O N

PAC/Oracle/parameter est./H2 bounds ln(N ) √ O N ))2 √ O (ln(N N ))5/2 √ O (ln(N N

√ finite-sample bounds [32, 24, 39, 42](which achieve O(ln N/ N )) . However, this is the expected price for generality: our bound applies to a broad class of learning algorithms, provides nonasymptotic guarantees with high probability, and simultaneously bounds the generalization gap (properties not offered by prior results). In addition, most existing finite-sample bounds are algorithmspecific (e.g., for least-squares only) and do not address the generalization gap.

References [1] P. Alquier, X Li, and O. Wintenberger. Prediction of time series by statistical learning: general losses and fast rates. Dependence Modeling, 1(2013):65–93, 2013. [2] Pierre Alquier. User-friendly introduction to PAC-bayes bounds. arXiv:2110.11216, 2021. [3] Pierre Alquier and Olivier Wintenberger. Model selection for weakly dependent time series forecasting. Bernoulli, 18(3):883 – 913, 2012. [4] P. E. Caines. Linear Stochastic Systems. John Wiley and Sons, 1988. [5] Marco C Campi and Erik Weyer. Finite sample properties of system identification methods. IEEE Transactions on Automatic Control, 47(8):1329–1334, 2002. [6] Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds of a family of recurrent neural networks. In Proceedings of AISTATS 2020, volume 108 of PMLR, pages 1233–1243, 8 2020. [7] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In UAI. AUAI Press, 2017. [8] Deividas Eringis, John Leth, Zheng-Hua Tan, Rafael Wisniewski, and Mihaly Petreczky. PACbayesian bounds for learning lti-ss systems with input from empirical loss. arXiv:2303.16816, 2023. [9] Deividas Eringis, John Leth, Zheng-Hua Tan, Rafal Wisniewski, Alireza Fakhrizadeh Esfahani, and Mihaly Petreczky. PAC-Bayesian theory for stochastic LTI systems. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 6626–6633, 2021. [10] Deividas Eringis, John Leth, Zheng Hua Tan, Rafal Wisniewski, and Mihaly Petreczky. Explicit construction of the minimum error variance estimator for stochastic LTI-ss systems. Automatica, 153, July 2023. [11] Deividas Eringis, John Leth, Zheng-Hua Tan, Rafal Wisniewski, and Mihaly Petreczky. PACBayes Generalisation Bounds for Dynamical Systems Including Stable RNNs. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, number 11, pages 11901–11909, March 2024. [12] Deividas Eringis, John Leth, Zheng-Hua Tan, Rafal Wisniewski, and Mihály Petreczky. PACBayesian Error Bound, via Rényi Divergence, for a Class of Linear Time-Invariant State-Space Models. In 41st International Conference on Machine Learning, volume 235, pages 12560– 12587, Vienne, Austria, July 2024. PMLR. 10

[13] Herbert Federer. Geometric Measure Theory. Classics in Mathematics. Springer Berlin Heidelberg, Berlin, Heidelberg, 1 edition, 1996. eBook ISBN: 978-3-642-62010-2. Originally published as volume 153 in the series Grundlehren der mathematischen Wissenschaften. IV, 677 pages. Springer-Verlag Berlin Heidelberg, 1996. [14] Dylan Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In Proceedings of the 37th ICML, volume 119 of PMLR, page 3211–3221. PMLR, 7 2020. [15] P. Germain, F. Bach, A. Lacoste, and S. Lacoste-Julien. PAC-bayesian theory meets bayesian inference. In NIPS, pages 1876–1884, 2016. [16] I. I. Gikhman and A. V. Skorokhod. Introduction to the Theory of Random Processes. Dover, 1st edition, 1996. [17] B. Guedj. A Primer on PAC-Bayesian Learning. arXiv:1901.05353, 2019. [18] B. Hanzon. On the differentiable manifold of fixed order stable linear systems. Systems & Control Letters, 13(4):345–352, 1989. [19] Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Spectral filtering for general linear dynamical systems. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. [20] Jiabao He, Ingvar Ziemann, Cristian R. Rojas, S. Joe Qin, and Håkan Hjalmarsson. Finite sample analysis of open-loop subspace identification methods. IEEE Transactions on Automatic Control, pages 1–16, 2026. [21] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. A short note on concentration inequalities for random vectors with subgaussian norm, 2019. [22] Tohru Katayama. Subspace methods for system identification. Communications and control engineering. Springer, Berlin, London, 2005. [23] Pascal Koiran and Eduardo D. Sontag. Vapnik-chervonenkis dimension of recurrent neural networks. Discrete Applied Mathematics, 86(1):63–79, 1998. [24] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Logarithmic regret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 33:20876–20888, 2020. [25] A. Lindquist and G. Picci. Linear Stochastic Systems: A Geometric Approach to Modeling, Estimation and Identification. Springer, 2015. [26] L. Ljung. System Identification: Theory for the user (2nd Ed.). PTR Prentice Hall., Upper Saddle River, USA, 1999. [27] Louis Massucci, Fabien Lauer, and Marion Gilson. A statistical learning perspective on switched linear system identification. Automatica, 145:110532, 2022. [28] Tomas McKelvey, Anders Helmersson, and Thomas Ribarits. Data driven local coordinates for multivariable linear systems and their application to system identification. Autom., 40(9):1629– 1635, 2004. [29] Abdelkader Metakalard, Fabien Lauer, Kevin Colin, and Marion Gilson. Uniform error bounds for quantized dynamical models. IFAC Journal of Systems and Control, 35:100373, 2026. [30] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2004. [31] Brett Ninness and Soren Henriksen. Bayesian system identification via markov chain monte carlo techniques. Automatica, 46(1):40–51, 2010. [32] Samet Oymak and Necmiye Ozay. Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis. IEEE Transactions on Automatic Control, 67(4):1914–1928, 4 2022. 11

[33] R. L. M. Peeters. System Identification Based on Riemannian Geometry: Theory and Algorithms. PhD thesis, Free University, Amsterdam, 1994. [34] Gianluigi Pillonetto, Tianshi Chen, Alessandro Chiuso, Giuseppe De Nicolao, and Lennart Ljung. Regularized system identification: Learning dynamic models from data. Springer Nature, 2022. [35] Tuhin Sarkar, Alexander Rakhlin, and Munther A. Dahleh. Finite time LTI system identification. J. Mach. Learn. Res., 22:26:1–26:61, 2021. [36] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. [37] Max Simchowitz. Statistical Complexity and Regret in Linear Control. University of California, Berkeley, 2021. [38] Max Simchowitz, Ross Boczar, and Benjamin Recht. Learning linear dynamical systems with semi-parametric least squares. In Conference on Learning Theory, pages 2714–2802. PMLR, 2019. [39] Max Simchowitz and Dylan Foster. Naive exploration is optimal for online lqr. In Proceedings of the 37th ICML, volume 119 of PMLR, page 8937–8948. PMLR, 7 2020. [40] David J. Smith and Mavina K. Vamanamurthy. How small is a unit ball? Mathematics Magazine, 62(2):101–107, 1989. [41] Eduardo D Sontag. A learning result for continuous-time recurrent neural networks. Systems & control letters, 34(3):151–158, 1998. [42] A. Tsiamis, I. Ziemann, N. Matni, and G. J. Pappas. Statistical learning theory for control: A finite-sample perspective. IEEE Control Systems Magazine, 43(6):67–97, 2023. [43] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2 edition, 2026. [44] Mathukumalli Vidyasagar and Rajeeva L Karandikar. A learning theory approach to system identification and stochastic adaptive control. Probabilistic and randomized methods for design under uncertainty, pages 265–302, 2006.

Proofs of Section 2

Remark A.1 (LTI in innovation form). Let us assume that eg has zero mean. It follows that eg (t) is the innovation process of [yT (t) uT (t)]T and (4) is in the so called (forward) innovation form, see [22, Section 8.5.2]. Intuitively, it means that eg is the difference between [yT (t) uT (t)]T and its best linear prediction based on its own past values. Remark A.2 (Equivalence of (4) and (2)). Let us assume that eg and es are both zero mean. More precisely, if there is no feedback from y to u according to Definition 17.1.1. of [25], then (2) holds and by [10] the matrices A0 , B0 , C0 , K0 , C0 , D0 can be computed from the matrices Ag , Kg , Cg . Conversely, if (2) holds and u(t) is generated by an ARMA process, and there is no feedback from y(t) to u(t), then Assumption 2.2 holds and Ag , Kg , Cg can be computed from those of (2) and the ARMA representation of u(t), again by reversing the equations from [10]. As a passing remark, if there is a feedback from y(t) to u(t) and u(t) is generated by an LTI systems driven by y(t), i.e., su (t + 1) = Au su (t) + Ku y(t),

u(t) = Cu su (t)

(15)

then again the generator described in Assumption 2.2 can be obtained by adding (15) to (2). Remark A.3 (Methods for stable parametrisations). The construction of [33, Section 3.2.3] relies on canonical forms based on structure indices, to which the diffeomorphism from [18] between general and stable parametersations are applied. Intuitively, the latter transformation maps (A, B, C, D) to ( A µ , B, C, D), where µ is the maximum of moduli of the eigenvalues of A. The construction of [28, Section 4.6] uses Ober’s balanced canonical forms, and it relies on fixing the observability and controllability Grammians to being equal and diagonal. That is, stability is assured by using diagonal quadratic Lyapunov functions. In this case, by fixing upper bounds on the diagnonals of the Grammians and on the norms of the system matrices occurring in the parameterisation, we ensure existence of constants M, C, γ mentioned in Assumption 2.1. Pt−1 Proof of Lemma 2.4. We have yθ (t | t0 ) = = k=t0 Hθ (t − 1 − k) w(k) + Dθ w(t) Pt−1−t0 k Hθ (k) w(t − 1 − k) + Dθ w(t) with the impulse response Hθ (k) ≜ Cθ Aθ Bθ for k ≥ 0. k=0 Because Aθ is Schur, there exist M > 0 and ρ ∈ (0, 1) such that ∥Akθ ∥2 ≤ M ρk , hence P∞ ρs k=s ∥Hθ (k)∥2 ≤ ∥Cθ ∥2 ∥Bθ ∥2 M 1−ρ → 0 as s → ∞. For t1 < t2 ≤ t we get, using sta2 tionarity of w (σw = E∥w(s)∥22 ) and setting β = ρ2 , that   2 t−1−t 1 X 2 E[∥yθ (t | t2 ) − yθ (t | t1 )∥2 ] = E  Hθ (m)w(t − 1 − m)  (16a) m=t−t2

≤ (t2 − t1 )E

" t−1−t X1

# ∥Hθ (m)∥22 ∥w(t − 1 − m)∥22

(16b)

m=t−t2 2 ≤ σw (∥Cθ ∥2 ∥Bθ ∥2 M )2 (t2 − t1 )

t−1−t X1

βm

(16c)

m=t−t2 2 = σw (∥Cθ ∥2 ∥Bθ ∥2 M )2

βt (t2 − t1 )(β −t2 − β −t1 ) 1−β

(16d)

Therefore {yθ (t | t0 )}t0 ≤t is Cauchy and hence converges in mean square to yθ (t) = Pt−1 P∞ k=−∞ Hθ (t − 1 − k) w(k) + Dθ w(t) = k=0 Hθ (k) w(t − 1 − k) + Dθ w(t). This representation shows that yθ is the output of a causal, time-invariant, stable LTI filter (with impulse response {Hθ (k)} and feed-through Dθ ) driven by the stationary input w. Hence yθ is stationary, since stable LTI filtering preserves stationarity. Moreover, it follows that yθ (t) − yθ (t | t0 ) =

∞ X

Hθ (k) w(t − 1 − k).

k=t−t0

so yθ (t) − yθ (t | 0) → 0 in mean square as t → ∞ by arguments as in (16). 13

(17)

Finally, consider E ℓ y(t), yθ (t) − E ℓ y(t), yθ (t | t0 ) ≤ E ℓ y(t), yθ (t) − ℓ y(t), yθ (t | t0 )

(18)

E[∥yθ (t | t0 )∥22 ] ≤ E[(∥yθ (t)∥2 + ∥yθ (t | t0 ) − yθ (t)∥2 )2 ] ≤ 2(E[∥yθ (t)∥22 ] + E[∥yθ (t) − yθ (t | t0 )∥22 ]) < 2E[∥yθ (t)∥22 ] + 2ϵ2 Hence, it follows that for t > Tϵ or −t0 > Tϵ , q q (E[∥yθ (t)∥22 ] + 2E[∥yθ (t)∥2 ]∥yθ (t | t0 )∥2 ] + E[∥yθ (t | t0 )∥22 ] ≤ 6E[∥yθ (t)∥22 ] + 4ϵ2 p and 6E[∥yθ (t)∥22 ] + 4ϵ2 = C does not depend on t. Hence, if t > Tϵ or −t0 > Tϵ , then E ℓ y(t), yθ (t) − ℓ y(t), yθ (t | t0 ) ≤ ϵ(2E[∥y(t)∥22 ] + C) from which it follows that E ℓ y(t), yθ (t) − ℓ y(t), yθ (t | t0 ) → 0 as either t0 → −∞ or t → ∞. That is, in all cases, lim E ℓ y(t), yθ (t | 0) = E ℓ y(t), yθ (t) = t→∞

lim E ℓ y(t), yθ (t | t0 )

t0 →−∞

(19)

proving the lemma since L(θ) is the right hand side of (19) by definition.

Proofs of Section 2.3

Remark B.1 (α as Markov-parameters). If α is the sequence of Markov parameters of a stable deterministic LTI system determined by matrices (A, B, C, D), i.e., α(0) = D, α(k) = CAk−1 B, k ≥ 1, then the ℓ1 norm ∥α∥ℓ1 and the WDMC θ∞ (α) are both finite. In this case, ∥α∥ℓ1 is the classical ℓ1 norm of the underlying LTI system. Moreover, if M > 0, γ ∈ [0, 1) are such that ∥Ak ∥2 < M γ k , then ∥α∥ℓ1 ≤ ∥D∥2 + M ∥B∥2 ∥C∥2 /(1 − γ) and θ∞ (α) ≤ ∥D∥ + γM ∥B∥2 ∥C∥2 /(1 − γ)2 . In turn, such M always exist if A is a Schur matrix, and γ can be chosen to be the spectral radius of A. In particular, ∥α∥ℓ1 , θ∞ (α) decrease as the spectral radius of A decreases. 14

Finally, as promised before Lemma B.3, we can state that all the constants from Definition 2.6 are well-defined. Lemma B.2. If Assumption 2.2 and 2.1 hold, then the quantities ∥αθ ∥ℓ1 and θ∞ (αθ ), ∥ᾱ∥ℓ1 , θ∞ (ᾱ), Ge (θ), Ge,1 (θ), Ge , Ge,1 are well defined real numbers.

Proof. From Remark B.1 and the assumption that Ag is Schur it follows that ∥αg ∥ℓ1 and θ∞ (αg ) are well-defined. By Assumption 2.1 there exists constants M, γ, C such that for all θ ∈ Θ, ∥Akθ ∥2 ≤ M γ k , ∥Bθ ∥2 ≤ C, and ∥Cθ ∥2 ≤ C. Therefore, ᾱ(k) = sup ∥αθ (k)∥2 ≤ M γ k C 2 and hence, by P∞ P∞ C2 using the argument of Remark B.1, ∥αθ ∥ℓ1 ≤ k=0 ∥α∥ℓ1 ≤ k=0 ᾱ(k) = ∥ᾱ∥ℓ1 ≤ M 1−γ < ∞ P∞ P∞ M C2 and θ∞ (αθ ) = k=0 k∥αθ (k)∥2 ≤ k=0 k ᾱ(k) = θ∞ (ᾱ) ≤ (1−γ)2 < ∞. Therefore, the quantities ∥αθ ∥ℓ1 and θ∞ (αθ ), ∥ᾱ∥ℓ1 , θ∞ (ᾱ) defining Ge (θ), Ge,1 (θ), Ge , Ge,1 are well-defined, and hence so are Ge (θ), Ge,1 (θ), Ge , Ge,1

Lemma B.3. Let αg,y (k) and αg,w (k) be the matrix formed by the first ny and the last n is the number of entries of w(t). Let cθ,s (k) = w rows of αg (k) respectively, P where nw P min{k,s} k αθ (k)αg,w (k − l) and cθ (k) = l=0 αθ (k)αg,w (k − l). l=0

y(t) αg,y = ⋆ eg (t), cθ ŷθ (t)

y(t) αg,y = ⋆ eg (t), cθ,t−t0 ŷθ (t | t0 )

y(t) − ŷθ (t) = ((αg,y − cθ ) ⋆ eg )(t),

(20)

y(t) − ŷθ (t | t0 ) = ((αg,y − cθ,t−t0 ) ⋆ eg )(t)

Moreover, the constants from Definition 2.6 satisfy: max{∥cθ ∥ℓ1 , ∥cθ,s ∥ℓ1 } ≤ ∥αθ ∥ℓ1 ∥αg ∥ℓ1 , αg,y αg,y max{ , , ∥αg,y − cθ ∥ℓ1 , ∥αg,y − cθ,s ∥ℓ1 } ≤ Ge (θ) ≤ Ge cθ cθ,t−t0 ℓ ℓ1 1 αg,y αg,y max{θ∞ , θ∞ , θ∞ (αg,y − cθ ), θ∞ (αg,y − cθ,s )} ≤ Ge,1 (θ) cθ cθ,t−t0 NX +t0

∥cθ,t−t0 − cθ ∥ℓ1 ≤ θ∞ (αθ )∥αg ∥ℓ1

(21) (22) (23) (24)

t=t0

In particular, the two LTI filters in (20) are stationary.

Proof of Lemma B.3. Let Cw denote the matrix formed by the last nw rows of Cg . From Assumption 2.2 and the proof of Lemma 2.4 we get that w(t) = y(t) =

ŷθ (t | t0 ) =

∞ X k=1 ∞ X k=0 t−t X0

Cw Ak−1 Kg eg (t − k) + eg (t) = g

∞ X

αg,y (k)eg (t − k) Ĉθ Âk−1 B̂θ w(t − k) + D̂θ w(t) = θ

t−t X0

k=1

ŷθ (t) =

αg,w (k)eg (t − k) = (αg,w ⋆ eg )(t)

k=0

lim ŷθ (t | t0 ) =

t0 →−∞

k=0 ∞ X

αθ (k)w(t − k)

k=0

αθ (k)w(t − k)

It then follows using the new index n = k + j ≥ 0 and the standard argument involving Cauchy products of series, ŷθ (t | t0 ) =

t−t X0

αθ (k)



αθ (k)αg,w (n − k) eg (t − n)

 ∞ X



min(n,t−t0 )

n=0

αg,w (j)eg (t − k − j)

j=0

k=0 ∞ X

∞ X

k=0

cθ,t−t0 (n)eg (t − n) = (cθ,t−t0 ⋆ eg )(t)

n=0

P∞ P∞ Notice that since Ag and Aθ are Schur, the series k=0 αθ (k) and k=0 αg,w (k) are absolutely convergent. With a similar argument, using that absolutely convergent series can be rearranged, it follows that ∞ ∞ X X ŷθ (t) = αθ (k) αg,w (j)eg (t − k − j) j=0

k=0

= =

∞ X

n X

n=0 ∞ X

k=0

! αθ (k)αg,w (n − k) eg (t − n)

cθ (n)eg (t − n) = (cθ ⋆ eg )(t)

n=0

From this the first claim of the lemma, i.e., (20), follows. The first inequality of the second claim, i.e., (21), follows by first noticing that ∥cθ (k)∥2 ≤

k X

∥αθ (i)∥2 ∥αg,w (k − i)∥2 ,

i=0 min(k,t−t0 )

∥cθ,t−t0 (k)∥2 ≤

∥αθ (i)∥2 ∥αg,w (k − i)∥2 ≤

i=0

k X

∥αθ (i)∥2 ∥αg,w (k − i)∥2

i=0

Pk P∞ SinceP i=0 ∥αθ (i)∥2 ∥αg,w (k−i)∥2 is the k’th coefficient of the Cauchy-product of k=0 ∥αθ (k)∥2 ∞ and k=0 ∥αg,w (k)∥2 , we obtain (21) by ∥c∥ℓ1 =

∞ X k=0

∥c(k)∥2 ≤

∞ X

∥αθ (i)∥2

i=0

∞ X

∥αg,w (j)∥2 = ∥αθ ∥ℓ1 ∥αg,w ∥ℓ1 ≤ ∥αθ ∥ℓ1 ∥αg ∥ℓ1 (25)

j=0

with c denoting either cθ or cθ,t−t0 . Concerning the second inequality (22), notice that αg,y (k) ≤ ∥αg,y (k)∥2 + ∥cθ (k)∥2 , ∥αg,y (k) − cθ (k)∥2 ≤ ∥αg,y (k)∥2 + ∥cθ (k)∥2 (26a) cθ (k) 2 αg,y (k) ≤ ∥αg,y (k)∥2 + ∥cθ,t−t0 (k)∥2 , (26b) cθ,t−t0 (k) 2 ∥αg,y (k) − cθ,t−t0 (k)∥2 ≤ ∥αg,y (k)∥2 + ∥cθ,t−t0 (k)∥2

(26c)

and hence, ( ) αg,y max , ∥αg,y − cθ ∥ℓ1 ≤ ∥αg,y ∥ℓ1 + ∥cθ ∥ℓ1 cθ ℓ1 ( ) αg,y max , ∥αg,y − cθ,t−t0 ∥ℓ1 ≤ ∥αg,y ∥ℓ1 + ∥cθ,t−t0 ∥ℓ1 cθ,t−t0 ℓ

(27a)

(27b)

From (27) and (25), the inequality of (22) follows by using the definition of Ge (θ) and the fact that max{∥αg,y ∥ℓ1 , ∥αg,w ∥ℓ1 } ≤ ∥αg ∥ℓ1 . 16

Concerning (23), notice that by definining d1 (i) = i∥αθ (i)∥2 and d2 (i) = i∥αg,w (i)∥2 , θ∞ (cθ,t−t0 ) =

∞ X

k∥cθ,t−t0 (k)∥2 ≤

k=0 ∞ min(k,t−t X X 0)

∞ X

min(k,t−t0 )

∞ min(k,t−t X X 0) i∥αθ (i)∥2 ∥αg,w (k − i)∥2 + (k − i)∥αθ (i)∥2 ∥αg,w (k − i)∥2 =

d1 (i)∥αg,w (k − i)∥2 +

i=0

k=0 ∞ X k X

i=0

k=0

∞ min(k,t−t X X 0)

∥αθ (i)∥2 ∥αg,w (k − i)∥2 =

i=0

k=0

i=0

k=0

∞ min(k,t−t X X 0)

d1 (i)∥αg,w (k − i)∥2 +

k=0 i=0

∞ X k X

d2 (k − i)∥αθ (i)∥2 ≤

i=0

k=0

d2 (k − i)∥αθ (i)∥2

k=0 i=0

Similarly, θ∞ (cθ ) =

∞ X

k∥cθ (k)∥2 ≤

k=0 k ∞ X X

∞ k X X k ∥αθ (i)∥2 ∥αg,w (k − i)∥2 = i=0

k=0

i∥αθ (i)∥2 ∥αg,w (k − i)∥2 +

k=0 i=0 ∞ X

(k − i)∥αθ (i)∥2 ∥αg,w (k − i)∥2 =

k=0 i=0

k=0 i=0 ∞ X k X

k ∞ X X

d1 (i)∥αg,w (k − i)∥2 +

∞ X k X

d2 (k − i)∥αθ (i)∥2 ≤

k=0 i=0

d1 (k)

k=0

∞ X

! ∥αg,w (k)∥2

k=0

! d2 (k)

k=0

∞ X

! ∥αθ (k)∥2

k=0

θ∞ (αθ )∥αg,w ∥ℓ1 + θ∞ (αg,w )∥αθ ∥ℓ1 ≤ θ∞ (αθ )∥αg ∥ℓ1 + θ∞ (αg )∥αθ ∥ℓ1 In particular, max{θ∞ (cθ ), θ∞ (cθ,t−t0 )} ≤ θ∞ (αθ )∥αg ∥ℓ1 + θ∞ (αg )∥αθ ∥ℓ1

(28)

Moreover, using (26) it follows that αg,y αg,y max θ∞ , θ∞ , θ∞ (αg,y − cθ ), θ∞ (αg,y − cθ,t−t0 ) ≤ cθ cθ,t−t0 θ∞ (αg,y ) + max{θ∞ (cθ ), θ∞ (cθ,t−t0 )} from which inequality (23) follows by using (28). Finally, notice that 0 Pk cθ (k) − cθ,t−t0 (k) = i=t−t0 +1 αθ (i)αg,w (k − i)

k ≤ t − t0 k > t − t0

Hence, by setting d3 (k) = ∥αθ (k + t − t0 + 1)∥2 ∥cθ − cθ,t−t0 ∥ℓ1 =

∞ X

∥

k=t−t0 +1

≤

∞ X

k X

αθ (i)αg,w (k − i)∥2

i=t−t0 +1 k X

∥αθ (i)∥2 ∥αg,w (k − i)∥2

k=t−t0 +1 i=t−t0

∞ X

k−(t−t0 +1)

k=t−t0 +1

i=0

∞ X k X

d3 (i)∥αg,w (k − i − (t − t0 + 1))∥2

d3 (i)∥αg,w (k − i)∥2 =

k=0 i=0

∞ X k=t−t0 +1

! ∥αθ (k)∥2

· ∥αg,w ∥ℓ1

By noticing that NX +t0

∞ X

∥αθ (k)∥2 ≤

t=t0 k=t−t0 +1

∞ X

min{k, N }∥αθ (k)∥2 ≤

k=1

∞ X

k∥αθ (k)∥2 = θ∞ (αθ )

k=1

the last inequality (24) follows. Finally, the stationarity of the two LTI filters is a concequence of the standard result that stable LTI filters maps stationary process to stationary process, see e.g., [16, Section 5.6].

Proof of Theorem 3.1

The proof of Theorem 3.1 is organized as follows. First, we define an auxiliary quantity called the infinite past empirical error N −1 1 X VN (θ) = ℓ(y(t), ŷθ (t)) N t=0 It follows that VN (θ) is an unbiased estimate of L(θ), i.e., E[VN (θ)] = L(θ). As the first step, we show the following general theorem. Theorem C.1. Given a parameter set Θ, a prior distribution π over Θ, δ ∈ [0, 0.5), λ > 0 and ϵ ∈ {−1, 1}. Then with probability at least 1 − 2δ, the following holds ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ) + B̃N (ρ, π, λ, ϵ) 1 1 B̃N (ρ, π, λ, ϵ) ≜ KL(ρ∥π) + ln + Ψ(λ, π, N, ϵ) λ δ 1 Ψ(λ, π, N, ϵ) ≜ ln Eθ∼π E[e2ϵλ(VN (θ)−L̂N (θ)) ] 2 + ln Eθ∼π E[e2ϵλ(L(θ)−VN (θ)) ] ,

(29) (30)

(31)

ρ(θ) with KL(ρ∥π) = Eθ∼ρ ln π(θ) the Kullback–Leibler divergence.

In the theorem above, the moment generating functions E[e2ϵλ(L(θ)−VN (θ)) ] and E[e2ϵλ(VN (θ)−L̂N (θ)) ] in the right-hand side are interpreted as ∞ whenever 2ϵλ falls outside of their domain of definition. In this case, Ψ(λ, π, N, ϵ) is taken to mean ∞ and the bounds are trivially true. Proof of Theorem C.1. By [15, Theorem 3], for any measurable functions X(θ, ω), Y (θ, ω), λ̃ > 0, and ϵ ∈ {−1, 1}, with probability at least 1 − δ we have: 1 1 ∀ρ ∈ Mπ : Eθ∼ρ X(θ, ω) ≤ Eθ∼ρ Y (θ, ω) + KL(ρ∥π) + ln + ΨX,Y (λ̃) , (32) δ λ̃ with ΨX,Y (λ̃) = ln Eθ∼π E[eλ̃(X(θ,ω)−Y (θ,ω)) ]. Now apply the above theorem for X = ϵL(θ), Y = ϵVN (θ), and X = ϵVN (θ), Y = ϵL̂N (θ). Then by applying a union bound on the two obtained probabilistic inequalities, we obtain with probability at least 1 − 2δ ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ) 1 1 + 2KL(ρ∥π) + 2 ln + ΨϵVN ,ϵL̂N (λ̃) + ΨϵL,ϵVN (λ̃) δ λ̃ With some algebraic manipulation and λ̃ = 2λ, we obtain the statement of the theorem. For the case of bounded innovation noise or Lipschitz loss function, we then show that E[e2λ(VN (θ)−L̂N (θ)) ] and E[e2λ(L(θ)−VN (θ)) ] can be both upper bounded by Ci (θ, λ, N, δ, ϵ), from which the statement of the theorem follows. For the case of quadaratic loss function, we will show that it can be reduced to the case of Lipschitz loss function with probability δ/3 and then we apply the result for Lipschitz loss with δ/3 instead of δ. 18

C.1

Proof of Theorem 3.1: bounded case

For the sake of readability, we repeat below the basic assumptions for the case of bounded data. Assumption C.2 (Bounded noise and Lipschitz loss). The innovation noise eg (t) from (4) is essentially bounded , i.e., ∥eg (t)∥∞ ≤ ce , ∀t ∈ Z

(33)

and the loss function ℓ is either Lℓ -Lipschitz or quadratic. The following Lemma is obvious in the Lℓ -Lipschits case, and follow by applying Cauchy–Schwarz in the quadratic case. √ Lemma C.3. Let B = {(z, z ′ ) ∈ Rny × Rny | ∥z − z ′ ∥2 ≤ Ge (θ) ne ce }. Then (y(t), yθ (t)), (y(t), yθ (t | 0)) ∈ B for all t, t0 ≤ t, and for all (z1 , z2 ), (z3 , z4 ) ∈ B, ℓ(z1 , z2 ) − ℓ(z3 , z4 ) ≤ L(θ) (∥z1 − z3 ∥2 + ∥z2 − z4 ∥2 ) √ where L(θ) is as in Theorem 3.1, i.e., L(θ) = 2Ge (θ) ne ce if ℓ-quadratic, and L(θ) = Lℓ if ℓ is Lℓ -Lipschitz. Remark C.4 (Norm loss Lℓ -Lipschitz). Note that if the loss ℓ is the p norm of the difference, i.e., √ ℓ(y, ŷ) = ∥y − ŷ∥p , then ℓ(y, ŷ) ≤ Cp ∥y − ŷ∥2 with Cp = ny if p = 1, and Cp = 1 if p = ∞ or p = 2. Lemma C.5. Let assumptions 2.2, 2.1 and C.2 hold. Then L(θ)λ E[e(ϵλ|VN (θ)−L̂N (θ)|) ] ≤ e( N θ∞ (αθ )∥αg ∥ℓ1 (ce

√

ne ))

= eCb,1 (λ,θ,L(θ),ce ,N )

Proof C.5 . Using the Lipschitz property of the loss function it follows that N −1

1 X |ℓ(y(t), ŷθ (t)) − ℓ(y(t), ŷθ (t | 0))| ≤ ϵ(VN (θ) − L̂N (θ)) ≤ |VN (θ) − L̂N (θ)| ≤ N t=0 N −1

(34)

L(θ) X ∥ŷθ (t) − ŷθ (t | 0)∥2 N t=0 From Lemma B.3 it follows that ŷθ (t) − ŷθ (t | 0) = ((cθ − cθ,t ) ⋆ eg )(t) =

∞ X

(cθ − cθ,t )(k)eg (t − k)

k=0

and hence N −1 X

∥ŷθ (t) − ŷθ (t | 0)∥2 ≤

t=0

N −1 X ∞ X

∥(cθ − cθ,t )(k)∥2 ∥eg (t − k)∥2 ≤

t=0 k=0

N −1 X

√ ∥cθ − cθ,t ∥ℓ1 ne ce

t=0

From (24) it follows that N −1 X

∥cθ − cθ,t ∥ℓ1 ≤ θ∞ (αθ )∥αg ∥ℓ1

t=0

and hence, N −1 X

√ ∥ŷθ (t) − ŷθ (t | 0)∥2 ≤ θ∞ (αθ )∥αg ∥ℓ1 ne ce

t=0

from which the statement of the lemma follows using the definition of Cb,1 (λ, θ, L(θ), ce , N ). Lemma C.6. Let assumptions 2.2, 2.1 and C.2 hold. Then E[eϵλ(L(θ)−VN (θ)) ] ≤ e

√ (L(θ))2 λ2 (Ge (θ)+2Ge,1 (θ))(ce ne )2 2N

= eCb,2 (λ,θ,L(θ),ce ,N )

(35)

T T T Proof of Lemma C.6 . For each Σ(θ) ∈ F, consider zt = y (t) ŷθ (t) . Then by Lemma αg,y αg,y B.3, zt = ⋆ eg (t) and zt is stationary. Moreover, as ≤ Ge (θ) < ∞ and cθ cθ ℓ1 αg,y θ∞ ≤ Ge,1 (θ) < ∞, it follows that zt is a Bernoulli-shift. In particular, ∥zt ∥∞ ≤ cθ √ Ge (θ)ce ne , and by [1, Proposition 4.2] zt is a weakly dependent process in the terminology of √ [1], with ∥z√0 ∥∞ ≤ Ge (θ)ce ne , and the mixing coefficient θ∞,N (1) of zt satisfies θ∞,N (1) < 2Ge,1 (θ)ce ne . If ℓ is Lℓ -Lipschitz, then let B = Rny × Rny . If ℓ is quadratic, then consider the set PN −1 1 ′ ′ B from Lemma C.3. Define the function h(z0 , z0′ , . . . , zN −1 , zN −1 ) = ϵ L(θ) i=0 ℓ(zi , zi ), ′ ny z0 , . . . , zN −1 , z0′ , . . . , zN on B N . We claim that h has Lipschitz constant 1 in the following −1 ∈ R sense: ′ ′ ′ |h(z0 , z0′ , . . . , zN −1 , zN −1 ) − h(z̃0 , z̃0 , . . . , z̃N −1 , z̃N −1 )| ≤

N −1 X

∥zi − z̃i ∥2 + ∥zi′ − z̃i′ ∥2

i=0

Indeed, using Lemma C.3, N −1

′ ′ ′ |h(z0 , z0′ , . . . , zN −1 , zN −1 ) − h(z̃0 , z̃0 , . . . , z̃N −1 , z̃N −1 )| =

≤

ϵ X ℓ(zi , zi′ ) − ℓ(z̃i , z̃i′ ) L(θ) i=0

N −1 N −1 X 1 X L(θ)(∥zi − z̃i ∥2 + ∥zi′ − z̃i′ ∥2 ) = ∥zi − z̃i ∥2 + ∥zi′ − z̃i′ ∥2 L(θ) i=0 i=0

If ℓ is Lℓ -Lipschitz, then h is already defined on (Rny × Rny )N . If ℓ is quadratic, we can use Kirszbraun’s theorem for scalar valued functions [13, 2.10.44,page 202], from which it then follows that h can be extended to a 1-Lipschitz map on (Rny × Rny )N without changing its values on B N . In fact, such an extension can be defined as hext (z) = inf x∈B N {h(x) + ∥z − x∥2 }. By abuse of notation this extension will be denote by h too. Notice that by Lemma C.3, (y(t), yθ (t)) ∈ B for all PN −1 ϵ ϵ t, hence h(y(0), yθ (0), . . . , y(N − 1), yθ (N − 1)) = L(θ) i=0 ℓ(y(i), yθ (i)) = L(θ) N VN (θ). Notice that, ϵλ(E[VN (θ)] − VN (θ)) =

λL(θ) (E[h] − h) . N

Now we can apply [1, Theorem 6.6], from which it follows that for any q ≥ 0 q2 N

E[eq(E[h]−h) ] ≤ e 2 (∥zt ∥∞ +θ∞,N (1))

(36)

By choosing q = λL(θ) and using the definition of Cb,2 (λ, θ, L(θ), ce , N ), we obtain the statement N of the lemma . Proof of Theorem 3.1: bounded processes. The statement of the theorem follows from Theorem C.1 by replacing E[e2λϵ(VN (θ)−L̂N (θ)) ] and E[e2λϵ(L(θ)−VN (θ)) ] with their upper bound from Lemma C.5 and Lemma C.6 respectively. C.2

Proof of Theorem 3.1: unbounded processes and Lipschitz loss functions

Recall that according to our assumptions, the 2-norm of the noise process eg is subgaussian. Bounded processes have this property, however, in this section we will not assume that the process eg is bounded. Recall that we also consider Lipschitz losses. Assumption C.7 (Lipschitz loss). We assume that the loss function ℓ is Lℓ -Lipschitz, i.e., for all y, ŷ, y ′ , ŷ ′ ∈ Rny , |ℓ(y, ŷ) − ℓ(y ′ , ŷ ′ )| ≤ Lℓ (∥y − y ′ ∥2 + ∥ŷ − ŷ ′ ∥2 ). 20

The main idea is to use Theorem C.1 and to derive bounds for moment generating functions of E[2λϵ(VN (θ) − L̂N (θ))] and E[2λϵ(L(θ) − VN (θ))]. In order to achieve this, we will reduce the problem of bounding E[2λϵ(VN (θ) − L̂N (θ))] and E[2λϵ(L(θ) − VN (θ))] to the same problem for bounded noises, by truncating the unbounded noise eg which drives the data generator. This problem was solved in Lemma C.5 and Lemma C.6, which thus can be re-used. To this end, let C > 0 be any constant and let ēg (t) be the truncated version of eg (t), i.e., ēg (t) = eg (t)χ{∥eg (t)∥<C} (t) := eg (t)χ(∥eg (t)∥ < C). (37) T ȳ (t) Let w̄(t) = be the output of the data generator, if eg (t) is replaced by ēg (t), and let ūT (t) ˆ θ (t | t0 ) be the output of the predictor (1) parametrized by θ with w replaced by w̄, and let ȳ ˆ θ (t) ȳ ˆ be the limit limt0 →−∞ ȳθ (t | t0 ). Note that Lemma 2.4 applies, as ēg (t) satisfies all the assumptions ˆ θ (t)) be the corresponding infinite past empirical error, of Assumption 2.2. Let V̄N (θ) = N1 ℓ(ȳ(t), ȳ P N −1 ˆ θ (t | 0)) the finite past empirical error, and L̄(θ) = E[ℓ(ȳ(t), ȳ ˆ (t))] L̄ˆN (θ) = N1 t=0 ℓ(ȳ(t), ȳ the true error for the model corresponding to θ ∈ Θ, if it is fed with the truncated signal w̄ instead of w. It turns out that we can bound the difference between these quantities and their non-truncated counterparts. The basic steps are as follows: First, using Lipschitz properties of the loss function, we bound the moment generating functions of the differences supθ∈Θ |L̂N (θ) − L̄ˆN (θ)|, supθ∈Θ |VN (θ) − V̄N (θ)| by the corresponding quantity for the ℓ2 loss, i.e.; by the moment generatPN −1 P −1 ˆ θ (t | t0 )∥2 and supθ∈Θ N ing functions of supθ∈Θ t=0 ∥ŷθ (t | 0) − ȳ t=0 ∥y(t) − ȳ(t)∥2 . Lemma C.8. ˆ

E[eλ supθ∈Θ |L̂N (θ)−L̄N (θ)| ] ≤ q q PN −1 2λLℓ PN −1 2λLℓ t=0 (∥y(t)−ȳ(t)∥2 ] E[e N E[e N supθ∈Θ t=0 ∥ŷθ (t|0)−ȳˆ θ (t|t0 )∥2 ]

(38)

E[eλ supθ∈Θ |VN (θ)−V̄N (θ)| ] ≤ q q PN −1 2λLℓ PN −1 2λLℓ t=0 (∥y(t)−ȳ(t)∥2 ] E[e N E[e N supθ∈Θ t=0 ∥ŷθ (t)−ȳˆ θ (t)∥2 ]

(39)

Then, using the technique of [3] we bound the moment generating functions of the truncation errors PN −1 P −1 ˆ θ (t | t0 )∥2 and supθ∈Θ N supθ∈Θ t=0 ∥ŷθ (t | 0) − ȳ t=0 ∥y(t) − ȳ(t)∥2 . To this end, we use the following bound on the moment generating function of ∥eg (t)∥2 . Lemma C.9 (Subgaussian noise). If ∥eg (t)∥2 is sub-Gaussian then Ψea (λ) = E[eλ∥eg (0)∥2 ] is well-defined for all λ > 0. In fact, 2

Ψeg (λ) ≤ Ψ̄eg (λ) = e(λ 14 ∥eg ∥ψ2 +3λ∥eg ∥ψ2 ) Using this bound, the moment generating function of the truncation error can be bounded as follows: Lemma C.10. For any λ < 0.5N λ

E[e N λ

E[e N supθ∈Θ λ

E[e N supθ∈Θ

PN −1

t=0

∥y(t)−ȳ(t)∥2

] ≤ eC(∥αg,y ∥ℓ1 ,λ,N,C)

ˆ (t)∥2 ∥ŷ(t)−ȳ

] ≤ eC(∥αg,w ∥ℓ1 ∥ᾱ∥ℓ1 ,λ,N,C)

ˆ (t|0)∥2 ∥ŷ(t|0)−ȳ

] ≤ eC(∥αg,w ∥ℓ1 ∥ᾱ∥ℓ1 ,λ,N,C)

t=0

PN −1

t=0

where C(s, λ, N, C) = λ

Ψ̄eg (s)s2 C λ2 + 2Ψ̄eg (s) (esC − 1) N

From this we derive Lemma C.11. For any λ < N/4Lℓ ˆ

max{E[eλ supθ∈Θ |L̂N (θ)−L̄N (θ)| ], E[eλ supθ∈Θ |VN (θ)−V̄N (θ)| ], eλ supθ∈Θ |L(θ)−L̄(θ)| } ≤ 1 e 2 (C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 ,2Lℓ λ,N )+C(∥αg,y ∥ℓ1 ,2Lℓ λ,N )) 21

(40)

In order to go back to bounding the moment generating functions of ϵ(VN (θ) − L̂N (θ)) and ϵ(L(θ) − VN (θ)), we use the previous lemma, and the following inequality which we derive using the CauchyScwhartz inequality: Lemma C.12. For ϵ = {−1, 1} E[eλϵ(L(θ)−VN (θ)) ] ≤ rq q q 2λϵ( L̄(θ)− V̄ (θ)) N E[e ] E[e4λ supθ∈Θ |V̄N (θ)−VN (θ)| ] e4λ supθ∈Θ |L̄(θ)−L(θ)| ]

(41)

E[eλϵ(VN (θ)−L̂N (θ)) ] ≤ rq q q ˆ ˆ 4λ sup | V̄ (θ)−V (θ)| 2λϵ( V̄ (θ)− L̄ (θ)) N N N N θ∈Θ E[e ] E[e ] e4λ supθ∈Θ |L̄N (θ)−L̂N (θ)| ]

(42)

If we apply Lemma C.11 to the right-hand sides of the latter inequalities, then we obtain. N Lemma C.13. For ϵ ∈ {1, −1}, for λ < 16L , ℓ

E[eλϵ(VN (θ)−L̂N (θ)) ] ≤ 1

e 4 (C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 ,8Lℓ λ,N,C)+C(∥αg,y ∥ℓ1 ,8Lℓ λ,N,C)) 1

E[e2λϵ(V̄N (θ)−L̄N (θ)) ] q

E[eλϵ(L(θ)−VN (θ)) ] ≤ e 4 (C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 ,8Lℓ λ,N,C)+C(∥αg,y ∥ℓ1 ,8Lℓ λ,N,C))

E[e2λϵ(L̄(θ)−V̄N (θ) )]

Finally, Lemma C.5 and Lemma C.6 derived for the bounded case can be applied to the moment generating functions of ϵ(L̄ˆ(θ) − V̄N (θ)) and ϵ(V̄N (θ) − L̄ˆN (θ)), for a suitable choice of C. The detailed proof is presented below.

Proof of Theorem 3.1: unbounded noise and Lipschitz loss. Let C min{1, ∥ᾱ∥ℓ1 }. Then C∥αg ∥ℓ1 ≥ 2 ln(N ),

2 ln(N ) K∥αg ∥ℓ1

where K

C∥ᾱ∥ℓ1 ∥αg ∥ℓ1 ≥ 2 ln(N )

and hence for N ≥ 2, eC∥αg ∥ℓ1 − 1 ≥ e2 ln(N ) − 1 = N 2 − 1 ≥ N,

eC∥αg ∥ℓ1 ∥ᾱ∥ℓ1 − 1 ≥ e2 ln(N ) − 1 = N 2 − 1 ≥ N

and therefore 1 e

C∥αg ∥ℓ1

−1

≤

1 , N

1 e

C∥αg ∥ℓ1 ∥ᾱ∥ℓ1

−1

≤

1 N

Therefore, as C∥ᾱ∥ℓ1 ∥αg ∥ℓ1 = 2 ln(N ) max{1, ∥ᾱ∥ℓ1 }, C(∥αg ∥ℓ1 , 8Lℓ λ, N, C) ≤

8Lℓ λ 2 ln(N ) (8Lℓ λ)2 Ψeg (∥αg ∥ℓ1 )∥αg ∥2ℓ1 + 2Ψeg (∥αg ∥ℓ1 ) ≤ N K∥αg ∥ℓ1 N

∥αg ∥ℓ1 8Lℓ λ 128L2ℓ λ2 Ψeg (∥αg ∥ℓ1 ) Ψeg (∥αg ∥ℓ1 ) 2 ln(N ) + N min{1, ∥ᾱ∥ℓ1 } N C(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 , 8Lℓ λ, N, C) ≤ 8Lℓ λ (8Lℓ λ)2 Ψeg (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 )(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 )2 C + 2Ψeg (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 ) = N N 8Lℓ λ 128L2ℓ λ2 Ψeg (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 )∥ᾱ∥ℓ1 ∥αg ∥ℓ1 2 ln(N ) max{1, ∥ᾱ∥ℓ1 } + Ψeg (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 ) N N 22

Hence, 1 (C(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 , 8Lℓ λ, N, C) + C(∥αg ∥ℓ1 , 8Lℓ λ, N, C)) ≤ 4 



 ∥αg ∥ℓ1 4λ ln(N )Lℓ    Ψ̄eg (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 )∥ᾱ∥ℓ1 max{1, ∥ᾱ∥ℓ1 }∥αg ∥ℓ1 + Ψ̄eg (∥αg ∥ℓ1 )  N min{1, ∥ᾱ∥ℓ1 }   | {z } Cu,2

32λ2 L2ℓ + Ψ̄eg (∥ᾱ∥ℓ1 ∥αg ∥ℓ1 ) + Ψ̄eg (∥αg ∥ℓ1 ) = C¯ub (λ, Lℓ , N ) N | {z } Cu,1

(43) 2 ln(N ) From Lemma C.5 and Lemma C.6 applied to V̄N (θ), L̄(θ), L̄ˆN (θ), with ce = C = K∥α and g ∥ ℓ1 L(θ) = Lℓ , it follows that q q 2 ln(N ) ,N ) g ℓ1

Cb,1 (2λ,θ,Lℓ , K∥α ∥

E[e2λϵ(V̄N (θ)−L̄N (θ)) ] ≤ e q q E[eϵ2λ(L̄(θ)−V̄N (θ)) ] ≤

2 ln(N ) ,N ) g ℓ1

Cb,2 (2λ,θ,Lℓ , K∥α ∥

= e2 1

= e2

2 ln(N ) ,N ) g ℓ1

Cb,1 (2λ,θ,Lℓ , K∥α ∥

2 ln(N ) ,N ) g ℓ1

Cb,2 (2λ,θ,Lℓ , K∥α ∥

Using Lemma C.13 with ∥αg,y ∥ℓ1 and ∥αg,w ∥ℓ1 replaced by their upper bound ∥αg ∥ℓ1 it follows that for any λ < Lℓ /16N , 2 ln(N ) ,N ) g ℓ1

C̄ub (2λ,Lℓ ,N )+ 12 Cb,1 (4λ,θ,Lℓ , K∥α ∥

E[e2λϵ(VN (θ)−L̂N (θ)) ] ≤ e E[e2λϵ(L(θ)−VN (θ)) ] ≤ e

2 ln(N ) ,N ) g ℓ1

C̄ub (2λ,Lℓ ,N )+ 12 Cb,2 (4λ,θ,Lℓ , K∥α ∥

= eC1 (2λ,θ,N,δ,ϵ)

(44)

= eC2 (2λ,θ,N,δ,ϵ)

The statement of the theorem follows from Theorem C.1 by replacing E[e2λϵ(VN (θ)−L̂N (θ)) ] and E[e2λϵ(L(θ)−VN (θ)) ] with their upper bound from (44).

The rest of the section is devoted to the proof of the lemmas used above. First, we prove Lemma C.9 Proof of Lemma C.9. First note that z(t) := ∥eg (t)∥2 − E[∥eg (t)∥2 ] is zero mean sub-Gaussian, and using sub-additivity of the sub-Gaussian norm we get ∥z(t)∥ψ2 ≤ ∥∥eg (t)∥2 ∥ψ2 + ∥E[∥eg (t)∥2 ]∥ψ2 = ∥eg ∥ψ2 + ∥E[∥eg (t)∥2 ]∥ψ2 . Now from the proof of [43, Proposition 2.6.1] it follows √ that E[∥eg (t)∥2 ] ≤ 3∥eg ∥ψ2 , and by [43, Exercise 2.24], ∥E[∥eg (t)∥2 ]∥ψ2 ≤ E[∥eg (t)∥2 ]/ ln 2 ≤ 2E[∥eg (t)∥2 ]. Hence ∥z(t)∥ψ2 ≤ 7∥eg ∥ψ2 . 2

Then fromq the proof of [43, Proposition 2.6.1] it follows that E[eλ(∥eg (t)∥2 −E[∥eg (t)∥2 ]) ] ≤ eλ K 2

3 (λ K +λE[∥eg (t)∥2 ]) and K = and the 2 ∥z(t)∥ψ2 ≤ 14∥eg ∥ψ2 . It then follows that Ψe (λ) ≤ e statement of the lemma follows.

In order to present the proof of Lemma C.8-C.13, we need the following sequence of results. Lemma C.14. Let z be positive valued random variable such that for all s ≤ λ̄ its moment generating function is well-defined. Then for any C > 0, E[zχ(z > C)] ≤

CE[eλ̄z ] eλ̄C − 1

Note that, as in (37), we use χ(z > C) as a shorthand for the indicator function χ{z>C} (z). This practices will be used in the sequel. 23

Proof of Lemma C.14. Let us consider ϕ(x) = e x−1 . It then follows that ϕ is a monotonically increasing function of x for x > 0. Hence, ϕ(λ̄z) ≥ χ(z > C). ϕ(λ̄C) ϕ(λ̄z) ϕ(λ̄z) Indeed, if z > C, then ϕ( ≥ 1 = χ(z > C). If z ≤ C, then 1 > ϕ( ≥ 0 = χ(z > C). It then λ̄C) λ̄C) follows that ϕ(λ̄z) z ≥ zχ(z > C) ϕ(λ̄C) and by taking expectations it follows that 1 E[zχ(z > C))] ≤ E[zϕ(λ̄z)] ϕ(λ̄C)

Note that

eλ̄z − 1 λ̄ and hence by using the inequality ex − 1 ≤ ex for x ≥ 0 it follows that zϕ(λ̄z) =

E[zϕ(λ̄z)] =

E[eλ̄z ] − 1 E[eλ̄z ] ≤ λ̄ λ̄

By noticing that λ̄ϕ(λ̄C) =

eλ̄C − 1 C

the statement of the lemma follows. Lemma C.15. E[e

s∥eg (t)∥2 χ(∥eg (t)∥2 >C)

]≤

1+s

Ψ̄eg (λ̄)C eλ̄C − 1

2Ψ̄eg (λ̄) + s2 λ̄2

:= Ψeg (s, λ̄, C)

for all s ∈ [0, 0.5λ̄). Proof Lemma C.15. First note that E[es∥eg (t)∥2 χ(∥eg (t)∥2 >C)) ] = 1 + sE[∥eg (t)∥2 χ(∥eg (t)∥2 > C))]+ ∞ X E[∥eg (t)∥k2 χ(∥eg (t)∥2 > C)]sk ] . k!

(45)

k=2

and E[∥eg (t)∥k2 χ(∥eg (t)∥2 > C) ≤ E[∥eg (t)∥k2 ]. As in Lemma C.9 let Ψeg (λ̄) = E[eλ̄∥eg (0)∥2 ] = E[eλ̄∥eg (t)∥2 ] be the moment generating function for ∥eg (t)∥2 . Then ∞ X E[∥eg (t)∥k2 ] k Ψeg (λ̄) = λ̄ k! k=0

and we get Ψeg (λ̄) E[∥eg (t)∥k2 ] ≤ . k! λ̄k It follows that for all k ≥ 2, E[∥eg (t)∥k2 χ(∥eg (t)∥2 > C)]sk E[∥eg (t)∥k2 ]sk sk ≤ ≤ Ψeg (λ̄) k . k! k! λ̄ Therefore, for all s ∈ [0, 0.5λ̄). ∞ X E[∥eg (t)∥k χ(∥eg (t)∥2 > C)]sk ] 2

k=2 2

≤

∞ X

Ψeg (λ̄)

k=2 2

s s s2 Ψeg (λ̄) ≤ Ψeg (λ̄) = 2Ψeg (λ̄) 2 2 λ̄(λ̄ − s) 0.5λ̄ λ̄ 24

sk s2 1 = Ψeg (λ̄) 2 = k λ̄ λ̄ 1 − λ̄s

(46)

where in the last inequality we used that as s < 0.5λ̄, λ̄ − s ≥ 0.5λ̄. Finally, use Lemma C.14 with z = ∥eg (t)∥2 to obtain E[∥eg (t)∥2 χ(∥eg (t)∥2 > C))] ≤

Ψeg (λ̄)C

(47)

eλ̄C − 1

The result now follows by combining (45), (46) and (47), and then use Lemma C.9. We will also need the following technical lemma P∞ Lemma C.16. Let ak ≥ 0 be a sequence of positive numbers such that the series k=0 ak is Pk PL PL convergent. For any N , define ck,N = l=max{0,k−N +1} al . Then k=0 ck,N ≤ N k=0 ak , the P∞ P∞ P∞ series k=0 ck,N is convergent, and k=0 ck,N ≤ N k=0 ak . Proof of Lemma C.16. We will prove by induction on L ≥ N − 1 that L X

ck,N =

L−N X+1

k=0

L X

N ak +

k=0

(L − k + 1)ak

(48)

k=L−N +2

For L = N − 1, by induction on N , it can be shown that N −1 X

ck,N =

k=0

N −1 X k X

al =

k=0 l=0

N −1 X

(N − k)ak .

k=0

which yield (48) for L = N − 1. Assume (48) holds for N − 1 ≤ L′ ≤ L. Notice that cL+1,N = PL l=L−N +2 al and hence L+1 X

ck,N =

k=0 L−N X+1

L X

ck,N + cL+1,N =

k=0

N ak +

k=0 L X

L−N X+1

(L − k + 2)ak =

L−N X+1

k=L−N +2

((L + 1) − k + 1)ak =

k=L−N +3

L X

(L − k + 1)ak +

k=L−N +2

k=0 L X

L X

N ak +

al =

l=L−N +2

N ak + (L − (L − N + 2) + 2)aL−N +2 +

k=0 L−N X+2

N ak +

k=0

L X

((L + 1) − k + 1)ak

k=L−N +3

The last expression is the right-hand side of (48) for L being replaced by L + 1, thus proving (48). Note that for k = L − N + 2, . . . , L we have L − k + 1 ≤ N , and hence (48) implies that PL PL P∞ k=0 ck,N ≤ N k=0 ak . Since ak and ck are nonnegative, and k=0 ak is convergent, the rest of the lemma follows. Lemma C.17. Let I be an index set, and {βi,t (k)}∞ k=0 , i ∈ I, be a sequence of matrices such that ∥β̄∥ℓ1 < ∞, where β̄(k) = supi∈I,t∈Z ∥βi,t (k)∥2 . Let zi (t) = (βi,t ⋆ eg )(t) and z̄i (t) = (βi,t ⋆ ēg )(t). Then for λ < 0.5N ∞ Y PN −1 λ c(k)λ E[e N supi∈I t=0 ∥z(t)−z̄i (t)∥2 ] ≤ Ψ̄eg , ∥β̄∥ℓ1 , C ≤ eC(∥β̄∥ℓ1 ,λ,N,C) N k=0

Ψ̄eg (s)s2 C λ2 C(s, λ, N, C) = λ sC + 2Ψ̄eg (s) (e − 1) N Pk where c(k) = l=max{0,k−N +1} ∥β̄(l)∥2 and the infinite product on the right-hand side is welldefined. Proof of Lemma C.17. Note that c(k) ≤ ∥β̄∥ℓ1 25

(49)

and by Lemma C.16 ∞ X

c(k) ≤ N

k=0

∞ X

∥β̄(k)∥2 = N ∥β̄∥ℓ1

(50)

k=0

Note now that N −1 X

∥zi,t (t) − z̄i,t (t)∥2

t=0 N −1 X ∞ X

≤

∥βi,t (k)∥2 ∥eg (t − k) − ēg (t − k)∥2

t=0 k=0 N −1 X ∞ X

≤

∥β̄(k)∥2 ∥eg (t − k)χ(∥eg (t − k)∥2 > C)∥2

t=0 k=0 ∞ X

c(k)∥eg (N − k − 1)χ(∥eg (N − k − 1)∥2 > C)∥2

k=0

Hence, λ

E[e N supi∈I,t∈Z

t=1 ∥∥zi,t (t)−z̄i,t (t)∥2

]≤

P∞ λ

≤ E[e N

k=0 c(k)∥eg (N −k−1)χ(∥eg (N −k−1)∥2 >C)∥2

L Y

= lim

L→∞

Ψ̄eg

k=0

c(k)λ , ∥β̄∥ℓ1 , C N

]

where we applied Lemma C.15 to E[e N c(k)∥eg (N −k−1)χ(∥eg (N −k−1)∥2 >C)∥2 ] with λ̄ = ∥β̄∥ℓ1 and s = c(k)λ < 0.5∥β̄∥ℓ1 since λ < 0.5N by assumption. N Note that dL = ln

L Y

Ψ̄eg

k=0

c(k)λ , ∥β̄∥ℓ1 , C N

! =

L X

rk ≤ ∥β̄∥ℓ1 λ

k=0

c(k)λ Ψ̄eg (∥β̄∥ℓ1 )∥β̄∥ℓ1 C rk := ln 1 + + N e∥β̄∥ℓ1 C − 1 We show that the series

L X

c(k)λ N

2Ψ̄eg (∥β̄∥ℓ1 ) ∥β̄∥2ℓ1

! ≥0

P∞

k=0 rk is bounded, more precisely,

Ψ̄eg (∥β̄∥ℓ1 )∥β̄∥ℓ1 C e∥β̄∥ℓ1 C − 1

k=0

2Ψ̄eg (∥β̄∥ℓ1 ) λ2 (∥β̄∥ℓ1 )2 = C(∥β̄∥ℓ1 , λ, N, C) N ∥β̄∥2ℓ1

From this it follows that dL is convergent, and from L Y

Ψ̄eg

k=0

c(k)λ , ∥β̄∥ℓ1 , C N

= edL

it follows that lim

L→∞

L Y k=0

Ψ̄eg

c(k)λ , ∥β̄∥ℓ1 , C N

≤ eC(∥β̄∥ℓ1 ,λ,N,C)

i.e., the infinite product is well-defined, and the statement of the lemma holds. In order to show (51), note that using ln(1 + x) ≤ x, it follows that 2 2Ψ̄eg (∥β̄∥ℓ1 ) c(k)λ Ψ̄eg (∥β̄∥ℓ1 )∥β̄∥ℓ1 C c(k)λ rk ≤ + ∥ β̄∥ C ℓ N N ∥β̄∥2ℓ1 1 e −1 26

(51)

Hence, L X

rk ≤

k=0

k=0 c(k) Ψ̄eg (∥β̄∥ℓ1 )∥β̄∥ℓ1 C + ∥β̄∥ℓ1 C N

k=0 (c(k)) N2

−1

2Ψ̄eg (∥β̄∥ℓ1 ) ∥β̄∥2ℓ1

From (49) it follows that c(k) ≤ ∥β̄∥ℓ1 . Hence 2 1 1 c(k) ≤ 2 c(k)∥β̄∥ℓ1 N N PL and as from (50) it follows that k=0 c(k) ≤ N ∥β̄∥ℓ1 , we get that 2 L L X 1 1 X 1 c(k) ≤ 2 c(k)∥β̄∥ℓ1 ≤ ∥β̄∥2ℓ1 N N N k=0

k=0

This completes the proof. Lemma C.17 provides the basis for several technical results. Proof of Lemma C.10. From Lemma B.3 it follows that y(t) = (αg,y ⋆ eg )(t) and ȳ(t) = (αg,y ⋆ ēg )(t). By setting I = {g}, βi,t = αg,y , i = g and using Lemma C.17, the first inequality follows. ˆ (t) = (cθ ⋆ ēg )(t). By setting Similar, from Lemma B.3 it follows that ŷ(t) = (cθ ⋆ eg )(t) and ȳ I = Θ, βi,t = cθ , i = θ ∈ Θ, it follows that λ

] ≤ eC(∥c̄∥ℓ1 ,λ,N,C) Pk where c̄(k) = supθ∈Θ ∥cθ (k)∥2 . Note that by definition cθ (k) = l=0 αθ (l)αg,w (k − l) and hence E[e N supθ∈Θ

∥cθ (k)∥2 ≤

k X

t=0 ∥ŷ(t)−ȳ(t)∥2

∥αθ (l)∥2 ∥αg,w (k − l)∥2 ≤

l=0

k X

∥ᾱ(l)∥2 ∥αg,w (k − l)∥2

l=0

In particular, c̄(k) ≤

k X

∥ᾱ(l)∥2 ∥αg,w (k − l)∥2

l=0

from which by the well-known property of Cauchy products of series (the infinite sum of the Cauchy product of two absolutely convergent series is equal to the product of their infinite sums) it follows that ∥c̄∥ℓ1 ≤ ∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 . By noticing that C(β, λ, N, C) is increasing in β, it follows that C(∥c̄∥ℓ1 , λ, N, C) ≤ C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 , λ, N, C), from which the second inequality follows. Finally, the proof of the third inequality is similar to the second one. By Lemma B.3 it follows that ˆ (t | 0) = (cθ,t ⋆ ēg )(t). By applying lemma C.17 to I = Θ, βi,t = cθ,t ŷ(t | 0) = (cθ,t ⋆ eg )(t) and ȳ it follows that PN λ ˆ ¯ E[e N supθ∈Θ t=0 ∥ŷ(t|0)−ȳ(t|0)∥2 ] ≤ eC(∥c̄∥ℓ1 ,λ,N,C) where c̄¯(k) = supθ∈Θ,t≥0 ∥cθ,t (k)∥2 . By noticing that min{k,t}

∥cθ,t (k)∥2 = ∥

min{k,t}

αθ (k)αg,w (k − l)∥2 ≤

l=0

≤

k X

∥ᾱ(k)∥2 ∥αg,w (k − l)∥2 ≤

l=0

∥αθ (k)∥2 ∥αg,w (k − l)∥2

l=0 k X

∥ᾱ(k)∥2 ∥αg,w (k − l)∥2 ,

l=0

from which it follows that ∥c̄¯∥ℓ1 ≤ ∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 From the monotonicity of C(s, λ, N, C) in s, it follows that C(∥c̄¯∥ℓ1 , λ, N, C) ≤ C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 , λ, N, C), which completes the proof. 27

and hence N −1 N −1 X Lℓ Lℓ X ˆ θ (t | t0 )∥2 ) (∥y(t) − ȳ(t)∥2 + sup sup |L̂N (θ) − L̄ˆN (θ)| ≤ ∥ŷθ (t | 0) − ȳ N t=0 N θ∈Θ t=0 θ∈Θ

Then ˆ

λLℓ

λLℓ PN −1

PN −1

|VN (θ) − V̄N (θ)| ≤

1 X ˆ θ (t))| ≤ |ℓ(y(t), ŷθ (t)) − ℓ(ȳ(t), ȳ N t=0

N −1 N −1 Lℓ X Lℓ X ˆ θ (t)∥2 ∥y(t) − ȳ(t)∥2 + ∥ŷθ (t) − ȳ N t=0 N t=0

and hence sup |VN (θ) − V̄N (θ)| ≤ θ∈Θ

N −1 N −1 X Lℓ X Lℓ ˆ θ (t)∥2 ) ∥ŷθ (t) − ȳ (∥y(t) − ȳ(t)∥2 + sup N t=0 N θ∈Θ t=0

so that λLℓ PN −1

λLℓ

PN −1

E[eλ supθ∈Θ |VN (θ)−V̄N (θ)| ] ≤ E[e N t=0 ∥y(t)−ȳ(t)∥2 e N supθ∈Θ t=0 ∥ŷθ (t)−ȳθ (t)∥2 ] ≤ q q PN −1 2λLℓ PN −1 2λLℓ (∥y(t)−ȳ(t)∥ 2 t=0 N ] E[e N supθ∈Θ t=0 ∥ŷθ (t)−ȳˆ θ (t)∥2 ] E[e from which (39) follows. Proof of Lemma C.11. From Lemma C.10 it follows that q 2λLℓ PN −1 1 C(∥αg,y ∥ℓ1 ,2Lℓ λ,N,C) t=0 ∥y(t)−ȳ(t)∥2 ] ≤ e 2 E[e N and

2λLℓ

PN −1

E[e N supθ∈Θ t=0 ∥ŷθ (t|0)−ȳˆ θ (t|t0 ) ] ≤ e 2 C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 ,2Lℓ λ,N,C) from which by using (38) it follows that ˆ

(52) (53)

E[eλ supθ∈Θ |L̂N (θ)−L̄N (θ)| ] ≤ e 2 (C(∥αg,y ∥ℓ1 ,2Lℓ λ,N,C)+C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 ,2Lℓ λ,N,C)) Likewise,from Lemma C.10 it follows that q PN −1 2λLℓ 1 E[e N supθ∈Θ t=0 ∥ŷθ (t)−ȳˆ θ (t)∥2 ] ≤ e 2 C(∥ᾱ∥ℓ1 ∥αg,y ∥ℓ1 ,2Lℓ λ,N,C) By combining this with (52), it follows by (39) that 1

θ∈Θ

≤ sup E[|VN (θ) − V̄N (θ)|] ≤ E[sup |VN (θ) − V̄N (θ)|] θ∈Θ

θ∈Θ

(54)

and hence

eλ supθ∈Θ |L(θ)−L̄(θ)| ≤ eλE[supθ∈Θ |VN (θ)−V̄N (θ)|] As the function ϕ : x 7→ eλx is convex, by Jensen’s inequality it follows that

(55)

eλE[supθ∈Θ |VN (θ)−V̄N (θ)|] = ϕ(E[sup |VN (θ) − V̄N (θ)|]) ≤ θ∈Θ

E[ϕ(sup |VN (θ) − V̄N (θ)|)] = E[eλ supθ∈Θ |VN (θ)−V̄N (θ)| ] θ∈Θ

and then the statement of the lemma follows from (54) and (55). Proof of Lemma C.12. Note that ϵ(VN (θ) − L̂N (θ)) = ϵ(L̄ˆN (θ) − L̂N (θ)) + ϵ(V̄N (θ) − L̄ˆN (θ)) + ϵ(VN (θ) − V̄N (θ)) ≤ sup |L̂ (θ) − L̄ˆ (θ)| + ϵ(V̄ (θ) − L̄ˆ (θ)) + sup |V̄ (θ) − V (θ)| N

θ∈Θ

Hence, by using monotonicity of x 7→ ex and Cauchy-Schwartz inequality for expectations, ˆ

≤ e 4 (C(∥ᾱ∥ℓ1 ∥αg,w ∥ℓ1 ,8Lℓ λ,N,C)+C(∥αg,y ∥ℓ1 ,8Lℓ λ,N,C)) By using (42) the first statement of the lemma follows. The proof of the second claim is similar. C.3

Proof of Theorem 3.1: quadratic loss

The core of the proof is to to show that the prediction errors ∥y(t) − yθ (t)∥2 and ∥y(t) − yθ (t | 0)∥2 are sub-Gaussian and hence they are bounded with high probablity as follows. Lemma C.18. For N ≥ 1 and δ ∈ (0, 0.5) P (∀θ ∈ Θ, ∀t = 0, . . . , N − 1 : s ! 2δ 3N 2 max{∥y(t) − yθ (t)∥2 , ∥y(t) − yθ (t | 0)∥2 } ≤ 6Ge (∥eg ∥ψ2 ) ln ≥1− 2δ 3

(56)

and E[∥y(t) − yθ (t)∥22 χ(∥y(t) − yθ (t)∥22 > (6Ge ∥eg ∥ψ2 )2 ln

2 2 · 62 G2e ∥eg ∥2ψ2 ln( 3N 3N 2 2δ ) )] ≤ 2δ N (57)

We then replace the quadratic loss with a loss which is Lipschitz for the case when ∥y(t) − yθ (t | 0)∥2 are bounded. More precisely, let us define the loss function ℓC as follows: ℓC (y, ŷ) = min{∥y − ŷ∥22 , C 2 } 29

Lemma C.19. For any C > 0, ℓC is 2C-Lipschitz. The proof then reduces the quadratic case to the case of Lipschitz loss ℓC for a suitable C and it goes as follows. q 2 Proof of Theorem 3.1:quadratic case. Let us set C = 6Ge ∥eg ∥ψ2 ln( 3N 2δ ) and let us consider the true and empirical errores for the loss function ℓC : N −1

L̂N (θ) =

1 X ℓC (y(t), ŷθ (t | 0)), N t=0

L(θ) = E[ℓC (y(t), ŷθ (t))]

(58)

By applying Theorem 3.1 for the case of Lipschitz loss function ℓC and with 2δ 3 instead of δ, it N follows that for all ϵ ∈ {−1, 1}, for all 0 < λ < 16·2C 3 1 C C ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ) + KL(ρ∥π) + ln + λ 2δ (59) 1 2δ 2δ ¯ ¯ ln Eθ∼π exp(C1 (2λ, θ, N, , ϵ)) + ln Eθ∼π exp(C2 (2λ, θ, N, , ϵ)) 2 3 3 holds with probability at least 1 − 4δ 3 , where for i = 1, 2. s 3N 2 C̄i (λ, θ, N, δ, ϵ) = Cub,i (λ, θ, 12Ge ∥eg ∥ψ2 ln , N) 2δ By using Lemma C.18, (59) and the union bound, it follows that 3 1 ∀ρ ∈ Mπ : ϵEθ∼ρ C L(θ) ≤ ϵEθ∼ρ C L̂N (θ) + KL(ρ∥π) + ln + λ 2δ 1 2δ 2δ ln Eθ∼π exp(C¯1 (2λ, θ, N, , ϵ)) + ln Eθ∼π exp(C¯2 (2λ, θ, N, , ϵ)) 2 3 3 and ∀θ ∈ Θ, ∀t = 0, . . . , N − 1 : ∥y(t) − ŷθ (t)∥2 ≤ C, ∥y(t) − ŷθ (t | 0)∥2 ≤ C

(60)

(61)

2δ holds with probability at least 1 − ( 4δ 3 + 3 ) = 1 − 2δ over data.

Notice that if ω ∈ Ω is such that ∀θ ∈ Θ, t = 0, . . . , N − 1 :

∥y(t)(ω) − ŷθ (t)(ω)∥2 ≤ C, ∥y(t)(ω) − ŷθ (t | 0)(ω)∥2 ≤ C

then ℓC (y(t)(ω), ŷθ (t | 0)(ω)) = ∥y(t)(ω) − ŷθ (t | 0)(ω)∥22 and hence L̂N (θ)(ω) = C L̂N (θ)(ω) Therefore, the event defined by (61) equals the event defined by 3 1 C KL(ρ∥π) + ln + ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ) + λ 2δ 1 2δ 2δ ¯ ¯ ln Eθ∼π exp(C1 (2λ, θ, N, , ϵ)) + ln Eθ∼π exp(C2 (2λ, θ, N, , ϵ)) 2 3 3 and ∀θ ∈ Θ, ∀t = 0, . . . , N − 1 : ∥y(t) − ŷθ (t)∥2 ≤ C, ∥y(t) − ŷθ (t | 0)∥2 ≤ C

(62)

For ϵ = −1 we will show (62) implies 1 3 ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ) + KL(ρ∥π) + ln + λ 2δ 1 2δ 2δ ln Eθ∼π exp(C¯1 (2λ, θ, N, , ϵ)) + ln Eθ∼π exp(C¯2 (2λ, θ, N, , ϵ)) 2 3 3 30

(63)

and as (62) holds with probability at least 1 − 2δ, it follows that (63) also holds with probability at least 1 − 2δ. To this end, notice that L(θ) = E[∥y(t) − ŷθ (t)∥22 ] = E[∥y(t) − ŷθ (t)∥22 χ(∥y(t) − ŷθ (t)∥2 ≤ C)]+ E[∥y(t) − ŷθ (t)∥22 χ(∥y(t) − ŷθ (t)∥2 > C)] (64) and that E[∥y(t) − ŷθ (t)∥22 χ(∥y(t) − ŷθ (t)∥2 > C)] ≥ C 2 P(∥y(t) − ŷθ (t)∥2 > C). Hence L(θ) ≥ E[∥y(t) − ŷθ (t)∥22 χ(∥y(t) − ŷθ (t)∥2 ≤ C)] + C 2 P(∥y(t) − ŷθ (t)∥2 > C) = E[ℓC (y(t), ŷθ (t))] = C L(θ)

(65)

i.e., ϵL(θ) ≤ ϵC L(θ) for ϵ = −1, from which it follows that (62) implies (63). For ϵ = 1, we will show that (62) implies 72G2e ∥eg ∥2ψ2 ln

3N 2 2δ

1 3 ∀ρ ∈ Mπ : ϵEθ∼ρ L(θ) ≤ ϵEθ∼ρ L̂N (θ) + + KL(ρ∥π) + ln + N λ 2δ 1 2δ 2δ ¯ ¯ ln Eθ∼π exp(C1 (2λ, θ, N, , ϵ)) + ln Eθ∼π exp(C2 (2λ, θ, N, , ϵ)) 2 3 3 (66) First note that 2 2    3N 2 2 ∥e ∥ ln 72G2e ∥eg ∥2ψ2 ln 3N 72G g e ψ 2δ 2δ 1 2  = ln exp λ N λ N and hence after algebraic manipulations 2 72G2e ∥eg ∥2ψ2 ln 3N 2δ 1 3 + KL(ρ∥π) + ln + N λ 2δ 2δ 1 2δ ¯ ¯ = ln Eθ∼π exp(C1 (2λ, θ, N, , ϵ)) + ln Eθ∼π exp(C2 (2λ, θ, N, , ϵ)) 2 3 3 1 3 1 KL(ρ∥π) + ln + (ln Eθ∼π exp(C1 (2λ, θ, N, δ, ϵ)) + ln Eθ∼π exp(C2 (2λ, θ, N, δ, ϵ))) λ 2δ 2 where for i = 1, 2, Ci (λ, θ, N, δ, ϵ) = λ

72G2e ∥eg ∥2ψ2 ln

3N 2 2δ

s 3N 2 + Cub,i (λ, θ, 12Ge ∥eg ∥ψ2 ln , N) 2δ

To show that (62) implies (66), notice that L(θ) = E[∥y(t) − ŷθ (t)∥22 ] = E[ℓC (y(t), ŷθ (t))χ(∥y(t) − ŷθ (t)∥2 ≤ C)] + E[∥y(t) − ŷθ (t)∥22 χ(∥y(t) − ŷθ (t)∥2 > C)] ≤ E[ℓC (y(t), ŷθ (t))] + E[∥y(t) − ŷθ (t)∥22 χ(∥y(t) − ŷθ (t)∥2 > C)] = C L(θ) + E[∥y(t) − ŷθ (t)∥22 χ(∥y(t) − ŷθ (t)∥2 > C)] (67) Using (57) it follows that L(θ) ≤ C L(θ) + 72G2e ∥eg ∥2ψ2 Hence, by adding 72G2e ∥eg ∥2ψ2

3N 2 2δ

(68)

to both sides of the inequality (62), it follows that (66) is N implied by (62). Combining the two case it follows that for quadratic loss and ϵ ∈ {−1, 1}, the inequality (8) also holds with probability at least 1 − 2δ over data. 31

We will conclude by presenting the proof of Lemma C.18-C.19. To this end, we need the following technical result. Lemma C.20. Let I be an index set, {βi,t (k)}∞ k=0 , i ∈ I, be a sequence of matrices such that ∥β̄∥ℓ1 < ∞, where β̄(k) = supi∈I,t∈Z ∥βi,t (k)∥2 , and let zi (t) = (βi,t ⋆ eg )(t). Then ∥zi (t)∥2 , i ∈ I and z(t) = supi∈I ∥zi (t)∥2 are sub-Gaussian with sub-Gaussian norm ∥∥zi (t)∥2 ∥ψ2 ≤ ∥z(t)∥ψ2 ≤ 6∥β̄∥ℓ1 ∥eg ∥ψ2 and the moments and the moment generating function of z2 (t) = supi∈I ∥zi (t)∥22 satisfy 2r E[z2r (t)] ≤ ∥β̄∥2r ℓ1 (3∥eg ∥ψ2 ) 2r!

(69) (70)

1 + λ∥β̄∥2ℓ1 (3∥eg ∥ψ2 )2 2 E[eλz (t) ] ≤ , 1 − λ∥β̄∥2ℓ1 (3∥eg ∥ψ2 )2

|λ| <

1 ∥β̄∥2ℓ1 (3∥eg ∥ψ2 )2

(71)

Moreover, for any C > 0, 2C 2

E[∥zi (t)∥22 χ(∥zi (t)∥22 > C 2 )] ≤

(72)

C2 2

e (6∥β̄∥ℓ1 ∥eg ∥ψ2 ) − 1 Proof Lemma C.20. Notice that ∞ X z(t) = sup ∥ βi,t (k)eg (t − k)∥2 i∈I

≤ sup i∈I

k=0 ∞ X

∥βi,t (k)∥2 ∥eg (t − k)∥2 ≤

k=0

∞ X

∥β̄(k)∥2 ∥eg (t − k)∥2

k=0

Hence, for any r ≥ 1, by using the arithmetic-geometric mean inequality we get a1 · · · ak ≤ Pk 1 k i=1 ai , a1 , . . . , ak ≥ 0, k !2r 2r ∞ ∞ Y X X 2r ∥β̄(kj )∥2 ∥eg (t − kj )∥2 ≤ z (t) ≤ ∥β̄(k)∥2 ∥eg (t − k)∥2 = k1 ,...,k2r =0 j=1

k=0 ∞ X k1 ,...,k2r =0

  2r 2r X 1 X  1 ∥β̄(kj )∥2r ∥eg (t − kj )∥2r 2 2 2r j=1 2r j=1

By taking expectations, using the fact that as ∥eg (t)∥2 is sub-Gaussian, and the proof of [43, Proposition 2.6.1] we obtain 2r 2r E[∥eg (t − kj )∥2r = 2r!(3∥eg ∥ψ2 )2r (73) 2 ] = E[∥eg (t)∥2 ] ≤ 2r(r − 1)!(3∥eg ∥ψ2 ) it follows that   ∞ 2r 2r X X 1 X   E[z2r (t)] ≤ ∥β̄(kj )∥2r E[∥eg (t − kj )∥2r 2 2 ]= 2r j=1 j=1 k1 ,...,k2r =0     ∞ 2r ∞ 2r X X X X   E[∥eg (t)∥2r   2r!(3∥eg ∥ψ2 )2r = ∥β̄(kj )∥2r ∥β̄(kj )∥2r 2 2 ]≤ 2 k1 ,...,k2r =0

(

∞ X

j=1

k1 ,...,k2r =0

j=1

2r ∥β̄(k)∥2 )2r 2r!(3∥eg (t)∥ψ2 )2r = ∥β̄∥2r ℓ1 2r!(3∥eg ∥ψ2 )

k=0

i.e., (70) holds. By noticing that ∞ ∞ 2r X X λr ∥β̄∥2r λr E[z2r (t)] ℓ1 (3∥eg ∥ψ2 ) 2r! λz2 (t) E[e ]=1+ ≤1+ = r! r! r=1 r=1 1 + 2λ∥β̄∥2ℓ1 (3∥eg (t)∥ψ2 )2

∞ X 2λ∥β̄∥2ℓ1 (3∥eg (t)∥ψ2 )2 (λ∥β̄∥2ℓ1 (3∥eg ∥ψ2 )2 )r = 1 + = 1 − λ∥β̄∥2ℓ1 (3∥eg ∥ψ2 )2 r=0

1 + λ∥β̄∥ℓ1 (3∥eg (t)∥ψ2 )2 1 − λ∥β̄∥2ℓ1 (3∥eg ∥ψ2 )2 32

1 it follows that (71) holds. Finally, for λ = 4∥β̄∥2 (3∥e g∥ ℓ1

E[eλz (t) ] ≤

2 ψ2 )

, the bound becomes

1 + 41 5 5/4 1 = 3/4 = 3 ≤ 2 1− 4

from which by the definition of sub-Gaussian norm of z(t) it follows r 1 ∥z(t)∥ψ2 ≤ = 6∥β̄∥ℓ1 ∥eg ∥ψ2 λ i.e., (69) holds. In particular, the sub-Gaussian norm of z(t) is bounded and hence by [43, Proposition 2.6.1] z(t) is sub-Gaussian. Moreover, as z2 (t) ≥ ∥zi (t)∥22 , it follows that the sub-Gaussian norm of ∥zi (t)∥2 is also bounded and it is also sub-Gaussian. Finally, from Lemma C.14 applied to ∥zi (t)∥2 it follows that 2

E[∥zi (t)∥22 χ(∥zi (t)∥22 > C 2 )] ≤

E[eλ̄∥zi (t)∥2 ]C 2 eC 2 λ̄ − 1

(74)

if λ̄ is such that the moment generating function E[es∥zi (t)∥2 ] is well-defined on [0, λ̄]. Note 2 2 that ∥zi (t)∥22 ≤ z2 (t) and hence E[es∥zi (t)∥ ] ≤ E[esz (t) ]. Now λ̄ can be chosen as λ̄ = 2 2 1 and hence E[eλ̄∥zi (t)∥ ] ≤ E[eλ̄z (t) ] ≤ 2. Combining (74) and the bound on 4∥β̄∥2 (3∥eg ∥ )2 ℓ1

ψ2

E[eλ̄∥zi (t)∥ ], we obtain (72). Proof of Lemma C.18. Let I = Θ × {1, 2}, z(θ,1) (t) = y(t) − yθ (t), z(θ,2) (t) = y(t) − yθ (t | 0), β(θ,1),t = αg,y − cθ , and β(θ,2),t = αg,y − cθ,t . Note that from the proof of Lemma B.3 it follows that ∥(αg,y + cθ )(k)∥2 ≤ ∥αg,y (k)∥2 +

k X

∥αθ (l)∥2 ∥αg,w (k − l)∥2

l=0

≤ ∥αg,y (k)∥2 +

k X

ᾱ(l)∥αg,w (k − l)∥2

l=0 min{k,t}

∥(αg,y + cθ,t )(k)∥2 ≤ ∥αg,y (k)∥2 +

∥αθ (l)∥2 ∥αg,w (k − l)∥2

l=0

≤ ∥αg,y (k)∥2 +

k X

ᾱ(l)∥αg,w (k − l)∥2 .

l=0

Hence β̄(k) = supi∈I ∥βi,t (k)∥2 ≤ ∥αg,y (k)∥2 + ∥β̄∥ℓ1 ≤

∞ X k=0

∥αg,y (k)∥2 +

∞ X k X

l=0 ᾱ(l)∥αg,w (k − l)∥2 and

ᾱ(l)∥αg,w (k − l)∥2 ≤ ∥αg ∥ℓ1 + ∥ᾱ∥ℓ1 ∥αg ∥ℓ1 = Ge

k=0 l=0

From this and Lemma C.20 and Lemma B.3 it follows that for any t = 0, . . . , N − 1 supθ∈Θ max{∥y(t) − yθ (t)∥2 , ∥y(t) − yθ (t | 0)∥2 } are sub-Gaussian random variable whose sub-Gaussian norms are upper bounded by 6Ge ∥eg ∥ψ2 . Hence, using the sub-Gaussian tail bound (proof of (iii) =⇒ (i) in [43, Proposition 2.6.1]), we obtain the desired result ! r 3N 2 P sup max{∥y(t) − yθ (t)∥2 , ∥y(t) − yθ (t | 0)∥2 } ≥ 6Ge ∥eg ∥ψ2 ln( ) ≤ 2δ θ∈Θ 2 2δ 2δ ≤ N 3N 3N Therefore, by applying a union bound over t = 0, . . . , N − 1, the first inequality (56) of the lemma follows. 3N 2

= 2e− ln( 2δ ) =

In order to obtain the second inequality, we use (72), and notice that 2

2C 2

2(6Ge ∥eg ∥ψ2 )2 ln( 3N 2δ ) 3N 2

eln( 2δ ) − 1

e (6Ge ∥eg ∥ψ2 ) − 1

2(6Ge ∥eg ∥ψ2 )2 ln( 3N 2δ )2δ = 3N 2 − 2δ

3N 2 2 2 ln( 2δ ) ≤ 72Ge ∥eg ∥ψ2

where we used that 2δ ≤ 1, 3N 2 − 2δ ≥ N 2 ≥ N , i.e., (57). Proof of Lemma C.19. Notice that |ℓC (y1 , ŷ1 )−ℓC (y2 , ŷ2 )| =  |∥y1 − ŷ1 ∥22 − ∥y2 − ŷ2 ∥22 | ∥y1 − ŷ1 ∥22 ≤ C 2 ,   |∥y2 − ŷ2 ∥22 − C 2 | ∥y1 − ŷ1 ∥22 > C 2 , 2 2 ∥y2 − ŷ2 ∥22 > C 2 ,   |∥y1 − ŷ1 ∥2 − C | 0 ∥y1 − ŷ1 ∥22 > C 2 ,

∥y2 − ŷ2 ∥22 ≤ C 2 ∥y2 − ŷ2 ∥22 ≤ C 2 ∥y1 − ŷ1 ∥22 ≤ C 2 ∥y2 − ŷ2 ∥22 > C 2

(75)

For each of the cases above we will show that the righ-hand side of (75) is bounded by 2C(∥y1 − y2 ∥2 + ∥ŷ1 − ŷ2 ∥2 ). First, consider the case when ∥y1 − ŷ1 ∥22 ≤ C 2 and ∥y2 − ŷ2 ∥22 ≤ C 2 . Then by repeated use of the triangle inequality, |∥y1 − ŷ1 ∥22 − ∥y2 − ŷ2 ∥22 | = |∥y1 − ŷ1 ∥2 − ∥y2 − ŷ2 ∥2 |(∥y1 − ŷ1 ∥2 + ∥y2 − ŷ2 ∥2 ) ≤ ∥(y1 − y2 ) − (ŷ1 − ŷ2 )∥2 (2C) ≤ 2C(∥y1 − y2 ∥2 + ∥ŷ1 − ŷ2 ∥2 ) Consider the case when ∥y1 − ŷ1 ∥22 > C 2 , ∥y2 − ŷ2 ∥22 ≤ C 2 . Then by the definition of ℓC , |ℓC (y1 , ŷ1 ) − ℓC (y2 , ŷ2 )| = |C 2 − ∥y2 − ŷ2 ∥22 | = (C − ∥y2 − ŷ2 ∥2 )(∥y2 − ŷ2 ∥2 + C) ≤ (C − ∥y2 − ŷ2 ∥2 )2C ≤ 2C(∥y1 − ŷ1 ∥2 − ∥y2 − ŷ2 ∥2 ) = 2C∥(y2 − y1 ) − (ŷ2 − ŷ1 )∥2 ≤ 2C(∥y1 − y2 ∥2 + ∥ŷ1 − ŷ2 ∥2 ) The case when ∥y2 − ŷ2 ∥22 > C 2 , ∥y1 − ŷ1 ∥22 ≤ C 2 is symmetric. Finally, consider the case when ∥y1 − ŷ1 ∥22 > C 2 , ∥y2 − ŷ2 ∥22 > C 2 . Then by the definition of ℓC , |ℓC (y1 , ŷ1 ) − ℓC (y2 , ŷ2 )| = |C 2 − C 2 | = 0 ≤ 2C(∥y1 − y2 ∥2 + ∥ŷ1 − ŷ2 ∥2 ) This completes the proof. C.4

Proof of Corollary 3.2

The corollary follows from Theorem 3.1 by choosing λ as follows:  √ N√  √   N N 16Lℓ ln(N ) = λ= √  L(ln(N ))r  q N  3 192Ge ∥eg ∥ψ2 1+ln( 2δ )(ln(N ))3/2

eg is bounded ℓ is Lℓ -Lipschitz

(76)

ℓis quadratic

and upper bounding the right-hand side of (8), i.e., by showing that 1 (ln Eθ∼π exp(C1 (λ, θ, N, δ, ϵ)) + ln Eθ∼π exp(C2 (λ, θ, N, δ, ϵ))) ≤ C(δ, ϵ) 2

(77)

To this end, note that from Lemma B.3 ∥αθ ∥ℓ1 ≤ ∥ᾱ∥ℓ1 ,

θ∞ (αθ ) ≤ θ∞ (ᾱ),

Ge (θ) ≤ Ge ,

Ge,1 (θ) ≤ Ge,1

(78) √ In addition, notice that the functions Cm,b,i (λ, α, X, L, c) has the following property; if λ ≤ λ̄ N , L1 ≤ L2 , X1 ≤ X2 , c1 ≤ c2 , and ∥α(k)∥2 ≤ ∥β(k)∥2 for all k ∈ N, then Cm,b,i (λ, α, X1 , L1 , c1 ) ≤ N Cm,b,i (λ̄, β, X2 , L2 , c2 ) 34

(79)

Bounded case Note that L(θ) ≤ Lb , any by using by using (78), it follows that ∥αθ (k)∥2 ≤ ᾱ(k) = ∥ᾱ(k)∥2 , Ge (θ) ≤ Ge , Ge,1 (θ) ≤ Ge,1 , and hence, by using (79), it follows that for all i = 1, 2 Ci (2λ, θ, N, δ, ϵ) =

Cm,b,i (N, αθ , Ge (θ) + 2Ge,1 (θ), L(θ), ce ) ≤ Cm,b,i (1, ᾱ, Ge + 2Ge,1 , Lb , ce ) N

Hence for i = 1, 2, ln Eθ∼π exp(Ci (2λ, θ, N, δ, ϵ)) ≤ ln Eθ∼π exp(Cb,m,i (2, ᾱ, Ge + 2Ge,1 , Lb , ce )) = Cb,m,i (2, ᾱ, Ge + 2Ge,1 , Lb , ce ) and hence (77). First, notice that for N ≥ 2, ln(N ) ≥ 1 and hence !2 √ √ 2 N 2 N 1 1 2 ¯ 32Lℓ Cu,1 + 4 Lℓ Cu,2 ln(N ) Cub (2λ, Lℓ , N ) = N 16Lℓ ln(N ) N 16Lℓ ln(N )

Lipschitz loss case:

(80)

1 1 1 = Cu,1 + Cu,2 √ ≤ Cu,1 + Cu,2 2 ln(N )2 2 N Moreover, using (79), √ 2 ln(N ) 2 N 2 ln(N ) Cb,i (2λ,θ, Lℓ , , N ) = Cb,i ( , θ, Lℓ , , N) ∥αg ∥ℓ1 K 16Lℓ ln(N ) ∥αg ∥ℓ1 K √

2 ln(N ) 2 N Cb,m,i ( 16L , αθ , Gθ + 2Ge,1 (θ), Lℓ , ∥α ) g ∥ℓ K ℓ ln(N ) 1

1 2 ln(N ) ≤ Cb,m,i ( , ᾱ, Ge + 2Ge,1 , Lℓ , ) 8Lℓ ln(N ) ∥αg ∥ℓ1 K  2 ln(N ) √ 1  8L ln(N i=1 ) Lℓ ∥αg ∥ℓ1 K ne θ∞ (ᾱ)∥αg ∥ℓ1 ℓ 2 = 2 Lℓ 2 ln(N ) 1  ne i = 2 (8Lℓ ln(N ))2 2 (Ge + 2Ge,1 ) ∥αg ∥ℓ1 K ( 1 √ i=1 4K ne θ∞ (ᾱ) 2 = 1 (Ge +2Ge,1 ) 1 ne i = 2 16 2 ∥αg ∥2 K

(81)

1 1 ) ≤ Cb,m,i ( , ᾱ, Ge + 2Ge,1 , 1, 4 ∥αg ∥ℓ1 K From this it then follows that √ 2 N 1 1 1 Cub,i ( , θ, Lℓ , N ) ≤ Cu,1 + Cu,2 + Cb,m,i ( , ᾱ, Ge + 2Ge,1 , 1, ) 16Lℓ ln(N ) 2 4 ∥αg ∥ℓ1 K

(82)

and hence 1 (ln Eθ∼π exp(C1 (2λ, θ, N, δ, ϵ)) + ln Eθ∼π exp(C2 (2λ, θ, N, δ, ϵ))) 2 2 1X 1 1 ≤ Cu,1 + Cu,2 + Cb,m,i (1/4, ᾱ, Ge + 2Ge,1 , 1, ) = C(δ, ϵ) 2 i=1 2 ∥αg ∥ℓ1 K so (77) holds. Quadratic loss case: Notice that as N 2 ≥ 4, it follows that ln(N 2 ) ≥ 1, and hence 3N 2 3 3 ln = ln(N 2 ) + ln ≤ ln(N 2 ) 1 + ln 2δ 2δ 2δ 35

(83)

1/2

√

)) N By using (83) and applying (82) with Lℓ = L(ln(N and noticing that λ = 16Lℓ ln(N 16 ) it follows that s 3N 2 L(ln(N ))1/2 Cub,i (2λ,θ, 12Ge ∥eg ∥ψ2 ln , N ) ≤ Cub,i (2λ, θ, , N) 2δ 16 (84) 1 1 ≤ Cu,1 + Cu,2 + Cb,m,i 1/4, ᾱ, Ge + 2Ge,1 , 1, 2 ∥αg ∥ℓ1 K 2 ≥ 1, it follows that Moreover, from (83) and the fact that ln(N ) ≥ 1 and ln 3N 2δ

ln 2λ

3N 2 2δ

72G2e ∥eg ∥2ψ2 max{0, ϵ}

2 √ 3N ln 2δ 2 N 2 2 q = (72G ∥e ∥ max{0, ϵ}) g ψ2 e √ p N 3 192Ge ∥eg ∥ψ2 2 ln(N ) 1 + ln 2δ ln(N ) √ 3 (1 + ln 2δ ) ln(N 2 ) 2 N 2 2 q (72Ge ∥eg ∥ψ2 max{0, ϵ}) ≤ p N 3 192Ge ∥eg ∥ψ2 ln(N ) 1 + ln 2δ ln(N 2 ) q p 3 2 · 72G2e ∥eg ∥2ψ2 max{0, ϵ} 1 + ln 2δ ln(N 2 ) √ = 192Ge ∥eg ∥ψ2 ln(N ) N q √ 3 1/2 2G ∥e ∥ max{0, ϵ} 2(ln(N )) 1 + ln 2δ e g ψ2 6 √ = 16 ln(N ) N 6 L(ln(N ))1/2 √ max{0, ϵ} 8 · 192 N ln(N ) 1 L √ = max{0, ϵ} 128 N (ln(N ))1/2

(85) Hence, for i = 1, 2, L max{0, ϵ}+ 128 1 1 Cu,1 + Cu,2 + Cb,m,i 1/4, ᾱ, Ge + 2Ge,1 , 1, 2 ∥αg ∥2 K

Ci (2λ,θ, N, δ, ϵ) ≤

and thus 1 (ln Eθ∼π exp(C1 (λ, θ, N, δ, ϵ)) + ln Eθ∼π exp(C2 (λ, θ, N, δ, ϵ))) 2 2 L 1X 1 1 ≤ max{0, ϵ} + Cu,1 + Cu,2 + Cb,m,i 1/4, ᾱ, Ge + 2Ge,1 , 1, 128 2 i=1 2 ∥αg ∥2 K = C(δ, ϵ) which completes the proof. C.5

Uniform bounds derived from Corollary 3.2

In order to present the uniform bounds, we need the following assumptions from Assumption 3.3: (LipModel) and either (Gauss) or (Uni). Corollary C.21 (Uniform [PAC bounds, Example 2.1,2.2 [2]). With the Assumption (LipModel) and either (Gauss) or (Uni) from Assumption 3.3 the following holds. Let LΘ (δ), CL,emp , CL,true , C(θ), rLip,1 , rLip,2 be defined as in Table 1, and let L, Cδ , C(δ, ϵ), r be defined as in Corollary 3.2 For any 36

δ ∈ (0, 0.5), λ, σ > 0, N ≥ 3, ϵ ∈ {−1, 1}, ∀θ ∈ Θ :ϵL(θ) ≤ ϵL̂N (θ)+ L(ln(N ))r+1 Cδ √ + C(δ, ϵ) CL,emp + CL,true + C(θ) + ln δ 2rLip,1 +1 N

(86)

holds with probability at least 1 − (2 + rLip,1 )δ over data. The proof of Corollary C.21 is based on a number of technical lemmas, which will also be used for the proof of Corollary 3.4. Lemma C.22 (KL divergence). Assume that either (Gauss) or (Uni) holds. For every θ ∈ Θ, define the density ρθ as follows ( 2 N (θ, σN I) if (Gauss) holds ρθ = U(θ, √σN I) if (Uni) holds where N (m, σ 2 I) denotes the Gaussian distribution with mean m and variance σ 2 I, and U(m, r) denotes the uniform distribution on the ball with center in m and radius r. Then for N ≥ 3, KL(ρθ | π) ≤ C(θ) ln(N ) Proof of Lemma C.22. If (Gauss) holds, then using KL divergence for Gaussian densities ([25, Lemma 11.3.4]) it follows that KL(ρθ | π) = 2 1 σ −1 det(P )N nθ T −1 trace P + (θm − θ) P (θm − θ) − nθ + ln 2 N σ 2nθ 2 σ −1 det(P ) 1 T −1 trace = P + (θm − θ) P (θm − θ) − nθ + ln 2n + nθ ln(N ) 2 N σ θ ≤ ln(N )C(θ) where we used the fact that ln(N ) ≥ 1 and N1 ≤ 1 if N ≥ 3. Likewise, if (Uni) holds, and we denote by C2 the volume of the ball of radius √σN centered at θ̃, then ! Z 1 ρθ (θ̃) KL(ρθ | π) = ln dm(θ̃) 2 σ π(θ̃) C2 ∥θ̃−θ∥2 ≤ √ N Z 1 vol(Θ) vol(Θ) ln dm(θ̃) = ln = σ 2 C2 C2 C2 ∥θ̃−θ∥2 ≤ √ N

From the formula for the volume of a high-dimensional ball [40] it follows that nθ π nθ /2 σ √ C2 = Γ(nθ /2 + 1) N and hence KL(ρθ | π) = ln

vol(Θ) C2



= ln 

 vol(Θ) n /2

π θ Γ(nθ /2+1)

√σ N

nθ 

√ nθ vol(Θ)Γ(nθ /2 + 1) = ln + ln N π nθ /2 (σ)nθ vol(Θ)Γ(nθ /2 + 1) nθ = ln + ln(N ) ≤ C(θ) ln(N ) √ nθ 2 2 πσ

Another ingredient is the following: 37

Lemma C.23 (Lipschitz continuity of the true and empirical errores). Using the constants defined in Corollary 3.2-C.21, the following inequality holds ∀θ1 , θ2 ∈ Θ : |L̂N (θ1 ) − L̂N (θ2 )| ≤ LΘ (δ)L(ln(N ))r ∥θ1 − θ2 ∥2 + L ln(N )r 1 2rLip,1 √ Cu,1 + Cu,2 + ln , δ N

(87)

with probability 1 − rLip,1 δ over data, where 0 eg is bounded rLip,1 = 1 otherwise and ∀ θ1 , θ2 ∈ Θ : |L(θ1 ) − L(θ2 )| ≤ LΘ (δ)L(ln(N ))r ∥θ1 − θ2 ∥2 + 2rLip,1

L ln(N )r √ (Cu,1 + Cu,2 ) + N

(88)

2rLip,2

L L(ln(N )) √ 512 N

where

rLip,2 =

2 0

ℓ is quadratic and eg is unbounded . otherwise

Moreover, the inequalities below (10) from Corollary 3.2 holds, and ∀θ1 , θ2 ∈ Θ : |L̂N (θ1 ) − L̂N (θ2 )| ≤ LΘ (δ)L(ln(N ))r ∥θ1 − θ2 ∥2 + L ln(N )r 1 2rLip,1 √ , Cu,1 + Cu,2 + ln δ N (89)

and ∀ θ1 , θ2 ∈ Θ : |L(θ1 ) − L(θ2 )| ≤ LΘ (δ)L(ln(N ))r ∥θ1 − θ2 ∥2 + 2rLip,1 2rLip,2

L ln(N )r √ (Cu,1 + Cu,2 ) + N

L L(ln(N ))r √ 512 N

hold simultaneously with probability at least 1 − (2 + rLip,1 )δ. Proof of Lemma C.23. Bounded noise case: If ℓ is Lℓ -Lipschitz and eg is bounded, then using (LipModel) and the argument of the proof from Lemma B.3, it follows that |ℓ(y(t), yθ1 (t)) − ℓ(y(t), yθ2 (t))| ≤ Lℓ ∥yθ1 (t) − yθ2 (t)∥2 ≤ Lℓ

∞ X

∥cθ1 (k) − cθ2 (k)∥2 ∥eg (t − k)∥2 ≤ Lℓ

k=0

∞ X k X

√ ∥αθ1 (l) − αθ2 (l)∥2 ∥αg,w (k − l)∥2 ce ne

k=0 l=0

√ √ ≤ Lℓ ∥αθ1 − αθ2 ∥ℓ1 ∥αg ∥ℓ1 ce ne = Lα Lℓ ∥αg ∥ℓ1 ce ne ∥θ1 − θ2 ∥2 | {z } LΘ (δ)

From this it then follows that |L(θ1 ) − L(θ2 )| ≤ LΘ (δ)∥θ1 − θ2 ∥

∀θ1 , θ2 ∈ Θ

|L̂N (θ1 ) − L̂N (θ2 )| ≤ LΘ (δ)∥θ1 − θ2 ∥

∀θ1 , θ2 ∈ Θ

By noticing that r = 0 and L = 1 for the bounded case, the claim of the lemma follows. 38

(90) (91)

Unbounded noise case: Assume that the noise is not necessarily bounded and ℓ is Lℓ -Lipschitz. From Subsection C.2, recall the definition of truncated empirical and true errors L̄N (θ) and L̄(θ), corresponding to the output ȳ(t) and ȳθ (t) and ȳθ (t | 0) generated for the truncated noise ēg (t) = ln(N ) eg (t)χ(eg (t) < C) for C = K∥α . Using Chernoff’s inequality and Lemma C.11, it follows that g ∥ℓ 1

eλ 2 (C(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 ,2Lℓ λ,N )+C(∥αg ∥ℓ1 ,2Lℓ λ,N )) P(∀θ ∈ Θ : L̂N (θ) − L̄N (θ) > c) ≤ eλc and hence 1 (C(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 , 2Lℓ λ, N )+ P ∀θ ∈ Θ : L̂N (θ) − L̄N (θ) ≤ 2λ 1 C(∥αg ∥ℓ1 , 2Lℓ λ, N ) + ln ≥1−δ δ Similarly, from Lemma C.11 it follows that 1 ∀θ ∈ Θ : |L(θ) − L̄(θ)| ≤ (C(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 , 2Lℓ λ, N ) + C(∥αg ∥ℓ1 , 2Lℓ λ, N )) 2λ ln(N ) From (43) in Subsection C.2 for C = K∥α it follows that g ∥ℓ 1

(92)

(93)

(94)

λ 1 (C(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 , 2Lℓ λ, N ) + C(∥αg ∥ℓ1 , 2Lℓ λ, N )) = 2C¯ub ( , Lℓ , N ) 2 8 √ N and hence by setting λ = 16Lℓ ln(N ) it follows that 1 1 ( (C(∥ᾱ∥ℓ1 ∥αg ∥ℓ1 , 2Lℓ λ, N ) + C(∥αg ∥ℓ1 , 2Lℓ λ, N )) λ 2 1 1 16Lℓ ln(N ) 16Lℓ ln(N ) √ √ ≤ ( Cu,1 + Cu,2 ) ≤ (Cu,1 + Cu,2 ) (95) 2 8 N N and hence, appplying it to (93)-(94) and recalling that L = 16Lℓ results in 1 16Lℓ ln(N ) √ P ∀θ ∈ Θ : L̂N (θ) − L̄N (θ) ≤ (Cu,1 + Cu,2 + ln( )) ≥1−δ δ N (96) L ln(N ) ∀θ1 , θ2 ∈ Θ : |L(θ1 ) − L(θ2 )| ≤ (Cu,1 + Cu,2 ) √ N √ ¯ ln(N ) Note that (90)-(91) holds for L̄N (θ) and L̂N (θ) with LΘ (δ) = Lα Lℓ ne K∥α and hence by g ∥ℓ1 using (96) and the observation ¯ ¯ ¯ ¯ |L̂N (θ1 ) − L̂N (θ2 )| ≤ |L̂N (θ1 ) − L̂N (θ1 )| + |L̂N (θ1 ) − L̂N (θ2 )| + |L̂N (θ2 ) − L̂N (θ2 )| |L(θ1 ) − L(θ2 )| ≤ |L(θ1 ) − L̄(θ1 )| + |L̄(θ1 ) − L̄(θ2 )| + |L̄(θ2 ) − L(θ2 )| it follows 1 16Lℓ ln(N ) √ P ∀θ1 , θ2 ∈ Θ : L̂N (θ1 ) − L̂N (θ1 ) ≤ 2(Cu,1 + Cu,2 + ln( )) )+ δ N √ ln(N ) Lα Lℓ ne ∥θ1 − θ2 ∥2 ≥ 1 − δ K∥αg ∥ℓ1 (97) ∀θ1 , θ2 ∈ Θ : |L(θ1 ) − L(θ2 )| √ 1 L ln(N ) ln(N ) ≤ 2(Cu,1 + Cu,2 + ln( )) √ ) + Lα Lℓ ne ∥θ1 − θ2 ∥2 δ K∥αg ∥ℓ1 N √ ln(N ) Since Lα Lℓ ne K∥α = LΘ L ln(N ) with the definition of LΘ as in Corollary C.21, (97) can be g ∥ ℓ1 rewritten as 1 L ln(N ) P ∀θ1 , θ2 ∈ Θ : L̂N (θ1 ) − L̂N (θ1 ) ≤ 2(Cu,1 + Cu,2 + ln( )) √ )+ δ N LΘ (δ)L ln(N )∥θ1 − θ2 ∥2 ≥ 1 − δ (98) ∀θ1 , θ2 ∈ Θ : |L(θ1 ) − L(θ2 )| 1 L ln(N ) ≤ 2(Cu,1 + Cu,2 + ln( )) √ ) + LΘ (δ)L ln(N )∥θ1 − θ2 ∥2 δ N 39

hence (87)-(88). By using the union bound, and that (10) holds with probability 1 − 2δ, (89) follows. Quadratic case Recall from (58), Subsection C.3 the definition of the lossq function ℓC and the true and empirical errors C L(θ) and C LN (θ). Recall that for C = 6Ge ∥eg ∥ψ2

ln( 3N 2δ ).

Recall that by Lemma C.18 that sup max{∥y(t) − yθ (t)∥2 , ∥y(t) − yθ (t[0])∥∞ } ≤ C

(99)

t=0,...,N −1,θ∈Θ

holds with probability at least 1 − 3δ . q 2 12Ge ∥eg ∥ψ2 ln 3N 2δ .

Also recall that ℓC is Lℓ -Lipschitz with Lℓ =

By applying (98) to C LN (θ) and C L(θ) and replacing δ with 2δ 3 and using the union bound, it follows that s 3N 2 sup max{∥y(t) − yθ (t)∥2 , ∥y(t) − yθ (t[0])∥∞ } ≤ 6Ge (∥eg ∥ψ2 ) ln 2δ t=0,...,N −1,θ∈Θ sup θ1 ,θ2 ∈Θ

LN (θ1 ) − C LN (θ2 ) √

ne 16Lℓ ln(N ) √ ≤ Lα Lℓ ln(N )∥θ1 − θ2 ∥ + 2 K∥αg ∥ℓ1 N

Cu,1 + Cu,2 + ln

2 3δ

, (100)

holds with probability at least 1 − δ, and sup C L(θ1 ) − C L(θ2 ) θ1 ,θ2 ∈Θ

√

ne 16Lℓ ln(N ) √ (Cu,1 + Cu,2 ) ln(N )∥θ1 − θ2 ∥ + 2 K∥αg ∥ℓ1 N q 2 where Lℓ = 12Ge ∥eg ∥ψ2 ln 3N 2δ . By using s s √ 3N 2 3 1/2 ln 1 + ln ≤ 2(ln(N )) 2δ 2δ it follows that s √ √ ne 3 √ ne ln(N ) ≤ 12Lα Ge ∥eg ∥ψ2 1 + ln 2 (ln(N ))3/2 Lα Lℓ K 2δ K Recall from Subsection C.3, proof of Theorem 3.1 that if ∀ : t = 0, 1, . . . , N − 1 : max{∥y(t) − yθ (t)∥2 , ∥y(t) − yθ (t | 0)∥∞ } ≤ C

(101)

≤ Lα Lℓ

holds, then C L̂N (θ) = L̂N (θ). Moreover, recall (67)-(68) holds, and thus using (83), it follows that 2 ln 3N 2δ L2 ln(N ) L(θ) − C L(θ) ≤ 72G2e ∥eg ∥2ψ2 ≤ 72 = N 1922 N (102) 3 6 L L(ln(N )) 2 2 ln(N ) √ L ≤ 16 · 192 N 512 N In then follows that |L(θ1 ) − L(θ2 )| ≤ L(θ1 ) − C L(θ1 ) + C L(θ1 ) − C L(θ2 ) + C L(θ2 ) − L(θ2 ) √ 3 (103) ne 16Lℓ ln(N ) 2L L(ln(N )) 2 √ √ L ln(N )∥θ1 − θ2 ∥ + 2 (Cu,1 + Cu,2 ) + ≤ K 512 N N By repeating the argument of the proof of Theorem 3.1 for the quadratic case, and using (103) and s √ 1 3 √ ne 12Lα Ge ∥eg ∥ψ2 1 + ln 2 = L 2δ K q √ √ne 3 √ 12Lα Ge ∥eg ∥ψ2 1 + ln 2δ 2 K ne q = L α √ 16K 192G ∥e ∥ 2 1 + ln 3 e

g ψ2

2δ

it then follows that (100) implies that (99) holds sup |LN (θ1 ) − LN (θ2 )|

(104) (105)

θ1 ,θ2 ∈Θ

≤ LΘ (δ)L(ln(N ))3/2 ∥θ1 − θ2 ∥ +

2L ln(N )r √ N

2 Cu,1 + Cu,2 + ln 3δ

(106)

which is implies (87), and (107) (108)

sup |L(θ1 ) − L(θ2 )| θ1 ,θ2 ∈Θ

≤ LΘ L(ln(N ))3/2 ∥θ1 − θ2 ∥ + +2

2L ln(N )3/2 √ (Cu,1 + Cu,2 ) + N

L L(ln(N ))3/2 √ 512 N

(109) (110)

which is equivalent to (88). Since (100) holds with probability at least 1 − δ, it then follows that (87) also holds with probability at least 1 − δ. Finally, from Corollary 3.2 it follows that (10) holds with probability at least 1 − δ, and hence by the union bound (100) follows.

Proof of Corollary C.21. Consider the inequality (89) which holds with probability at least 1 − (2 + rLip,1 )δ. If (89) holds, then for all θ ∈ Θ, ϵ(L(θ)) − (L(θ̃)) ≤ |ϵ(L(θ) − L(θ̃))| = |L(θ) − L(θ̃)| and hence ϵL(θ) ≤ ϵL(θ̃)+LΘ (δ)L(ln(N ))r ∥θ−θ̃∥2 +2rLip,1

L ln(N )r L L(ln(N ))r √ √ (Cu,1 + Cu,2 )+2rLip,2 512 N N

Then Eθ̃∼ρθ ∥θ̃ − θ∥22 ≤ σN and hence Eθ̃∼ρθ ∥θ̃ − θ∥2 ≤

q σ Eθ̃∼ρθ ∥θ̃ − θ∥22 ≤ √ N

Therefore L(θ) ≤ Eθ̃∼ρθ L(θ̃) + LΘ (δ)L(ln(N ))r ∥θ − θ̃∥2 L ln(N )r L L(ln(N ))r √ √ (Cu,1 + Cu,2 ) + 2rLip,2 512 N N σLΘ (δ) L ln(N )r L L(ln(N ))r √ ≤ √ + 2rLip,1 √ (Cu,1 + Cu,2 ) + 2rLip,2 512 N N N

+ 2rLip,1

(111)

Similary, L ln(N )r ϵL̂N (θ̃) ≤ ϵL̂N (θ) + LΘ (δ)L(ln(N )) ∥θ − θ̃∥2 + 2rLip,1 √ N r

and hence

1 Cu,1 + Cu,2 + ln δ

ϵEθ̃∼ρθ L̂N (θ̃) ≤ ϵL̂N (θ) + LΘ (δ)L(ln(N ))r Eθ̃∼ρθ ∥θ − θ̃∥2 1 L ln(N )r + 2rLip,1 √ Cu,1 + Cu,2 + ln δ N r σLΘ (δ) L ln(N ) 1 ≤ √ + 2rLip,1 √ Cu,1 + Cu,2 ln δ N N 41

(112)

In addition, since (10) also holds, it follows that ϵEθ̃∼ρθ L(θ̃) ≤ ϵEθ̃∼ρθ L̂N (θ̃) +

L(ln(N ))r √ N

KL(ρθ ∥π) + ln

Cδ + C(1, δ) δ

(113)

By combining (111), (112), and (113), it follows that L ln(N )r σLΘ (δ) √ + 2rLip,1 √ (Cu,1 + Cu,2 ) N N L L(ln(N ))r √ + 2rLip,2 512 N L(ln(N ))r Cδ √ ≤ ϵEθ̃∼ρθ L̂N (θ̃) + KL(ρθ ∥π) + ln + C(1, δ) + δ N σLΘ (δ) L ln(N )r L L(ln(N ))r √ + √ + 2rLip,1 √ (Cu,1 + Cu,2 ) + 2rLip,2 512 N N N σLΘ (δ) L ln(N )r 1 √ √ ≤ ϵL̂N (θ) + + 2rLip,1 Cu,1 + Cu,2 + ln δ N N r L(ln(N )) Cδ √ + KL(ρθ ∥π) + ln + C(1, δ) + δ N σLΘ (δ) L ln(N )r L L(ln(N ))r √ + √ + 2rLip,1 √ (Cu,1 + Cu,2 ) + 2rLip,2 512 N N N r 2σLΘ (δ) L ln(N ) L L(ln(N ))r √ + 4rLip,1 √ (Cu,1 + Cu,2 ) + 2rLip,2 = ϵL̂N (θ) + √ 512 N N N r L(ln(N )) Cδ √ + C(θ) ln(N ) + ln + C(ϵ, δ) δ 2rLip,1 +1 N L(ln(N ))r+1 √ (2σLΘ (δ) + 4rLip,1 (Cu,1 + Cu,2 ) ≤ ϵL̂N (θ) + N Cδ L +2rLip,2 + C(θ) + ln + C(ϵ, δ) 512 δ 2rLip,1 +1

ϵL(θ) ≤ϵEθ̃∼ρθ L(θ̃) +

where in the last step we used that r ≥ 0 and ln(N ) ≥ 1 for N ≥ 4.

Proof of Corollary 3.4

We start with the following remark explaining the notion of random models drawn from a datadependent posterior. Remark D.1 (Joint probability over data and parameters). Let ρD be a function on Ω × Θ which is measurable w.r.t. the direct product F × BΘ of σ-algebras, and such that for any ω ∈ Ω, ρD (ω) : Θ ∋ θ 7→ ρD (ω, θ) is a probability density on Θ. We refer to ρD as a random density on Ω. Let B be a subset of F × BΘ and denote by Pθ∼ρD (B) the random variable ω 7→ Pθ∼ρD (ω) ({θ | (ω, θ) ∈ B}), where Pθ∼ρD (ω) is the probability measure induced by the density ρD (ω). Define the probability measure P × Pθ∼ρD on F × BΘ as follows: P × Pθ∼ρD (B) ≜ E[Pθ∼ρD (B)] Similarly to the previous definition of relationship holding with probability over data, if ⋄ is a binary operator and {Xi , Yi }i∈I is family of functions taking values in R and which are measurable w.r.t. (Ω × Θ, F × BΘ ), then we say that ∀i ∈ I : Xi ⋄ Yi , holds with probability at least 1 − δ over data and over samples from ρD , if the set B = {(ω, θ) ∈ Ω × Θ | ∀i ∈ I : Xi (ω, θ) ⋄ Yi (ω, θ)} is measurable in (Ω × Θ, F × BΘ ) and P × Pθ∼ρD (B) ≥ 1 − δ. Note that if a relationship holds with a probability at least 1 − δ over data, then it also holds with a probability at least 1 − δ over data and sampled from ρD : if F is an event from F, then D P × Pθ∼ρ (F ) = P(F ) ≥ 1 − δ. 42

D.1

Proof of the (11) on empirical error

First, we present a useful property of Gibbs posteriors. Lemma D.2 (Property of Gibbs distribution). Gibbs 1 ρ (θ) 1 L̂N (θ) + ln = − ln Eθ∼π e−λL̂N (θ) λ π(θ) λ 1 = inf Eθ∼ρ L̂N (θ) + KL(ρ∥π) ρ∈Mπ λ 1 1 Gibbs −λL̂N (θ) Eθ∼ρGibbs L̂N (θ) + KL(ρ ∥π) = − ln Eθ∼π e = λ λ 1 = inf Eθ∼ρ (L̂N (θ)) + KL(ρ∥π) ρ∈Mπ λ −λL̂N (θ)

Proof of Lemma D.2. Using the definition of the Gibbs distribution ρGibbs (θ) = π(θ)e Z Eθ∼π e−λL̂N (θ) , it follows that Gibbs ρ (θ) ln = −λL̂N (θ) − ln Z π(θ)

(114)

(115)

,Z =

and hence L̂N (θ) +

1 ln λ

Gibbs ρ (θ) 1 1 = L̂N (θ) − L̂N (θ) − ln Z = − ln Z π(θ) λ λ

This gives the first equality of (114). As to the first equality of (115), it follows directly from the first equality of (114) taking i the h byGibbs ρ (θ) Gibbs Gibbs expectation with respect to θ ∼ ρ and recalling that KL(ρ ∥π) = Eθ∼ρGibbs ln π(θ) . The second equalities of (114)-(115) are Donsker-Varadhan’s variational formula [2, Lemma 2.2]

Next, we present a version of Theorem 3.1 where the inequality holds not only over data but over data and any model randomly drawn from a data-dependent posterior. Lemma D.3 (Single draw bound). Let ρD be a data-dependent posterior. For any prior π, any δ ∈ (0, 0.5) with a probability at least (1 − 2δ) over the data and over all samples θ⋆ drawn from ρD , for any λ satisfying the condition of Theorem 3.1 ! 2 1 ρD (θ⋆ ) Cδ 1X ϵL(θ⋆ ) ≤ ϵL̂N (θ⋆ )+ ln + ln + ln Eθ∼π exp(2λCi (2λ, θ⋆ , N, δ, ϵ)) (116) λ π(θ⋆ ) δ 2 i=1 In particular, with probability at least (1 − 2δ) over data and over all samples θ⋆ drawn from ρD , D L(ln(N ))r ρ (θ⋆ ) Cδ √ ϵL(θ⋆ ) ≤ ϵL̂N (θ⋆ ) + (ln + ln + C(δ, ϵ)) (117) π(θ ) δ N ⋆ for all N ≥ Kδ , where the constants Kδ , Cδ , L, r are defined as in Corollary 3.2. Moreover, if ϵ = 1 and ρD = ρGibbs , then with probability at least (1 − 2δ) over the data and over θ⋆ sampled from ρGibbs , ! 2 1 Cδ 1X (118) L(θ⋆ ) ≤ Eθ∼π L̂N (θ) + ln + ln Eθ∼π exp(Ci (2λ, θ, N, δ, ϵ)) λ δ 2 i=1 √

N In particular, if the Gibbs posterior ρGibbs is defined for λ = λN = L(ln(N ))r then for N ≥ Kδ 1 L(ln(N ))r Cδ √ L(θ⋆ ) ≤ − ln Eθ∼π e−λL̂N (θ) + ln + C(δ, 1) (119) λ δ N

Proof of Lemma D.3. Following the argument of the proof of [2, Theorem 2.7], it follows that for any measurable function X on Ω × Θ, Eθ∼π e2λX(ω,θ) = Eθ∼ρD e2λX(ω,θ)−ln

ρD (ω,θ) π(θ)

and hence

ρD (θ) 2λX(θ)−ln π(θ)

EEθ∼π e2λX(θ) = EEθ∼ρD e with the random variables X(θ) : ω ∋ Ω 7→ X(ω, θ). Notice that EEθ∼ρD is the expectation operator corresponding to the probability measure P × Pθ∼ρD , and that E[Eθ∼π X] = Eθ∼π E[X] , and hence, by Chernoff’s bound: P × Pθ∼ρD X <

1 1 ρD (θ) ln + ln + ln EEθ∼π e2λX 2λ δ π(θ) 2λX−ln

ρD (θ)

π(θ) EEθ∼ρD e 1 1 ρD (θ) 1 = P × Pθ∼ρD (X − ln + ln EEθ∼π e2λX ≤ ln )< 1 2λX 2λ π(θ) 2λ δ eln δ +ln EEθ∼π e 2λX EEθ∼π e = 1 =δ 2λX δ EEθ∼π e

Hence, X≤

1 1 ρD (θ) ln + ln + ln Eθ∼π Ee2λX(θ) 2λ δ π(θ)

(120)

with probability at least 1−δ over data and samples from ρD . Hence, by taking X = ϵ(L(θ)−VN (θ)) and then X = ϵ(VN (θ)) − L̂N (θ)), and by taking the union bound as in the proof of Theorem C.1, it follows that 1 1 ρD (θ) L(θ) ≤L̂N (θ) + ln + ln λ δ π(θ) (121) 1 2ϵλ(VN (θ)−L̂N (θ)) 2ϵλ(L(θ)−VN (θ)) + ln Eθ∼π E[e ] + ln Eθ∼π E[e ] 2 Proof of (116) for bounded noise Let us apply the inequality (121) and use the bound on E[e2ϵλ(VN (θ)−L̂N (θ)) ] and E[e2ϵλ(L(θ)−VN (θ)) ] from Lemma C.6-C.5, from which (116) follows. Proof of (116) for Lipschitz loss Let us apply (44) from Subsection C.2 to bound the bound on E[e2ϵλ(VN (θ)−L̂N (θ)) ] and E[e2ϵλ(L(θ)−VN (θ)) ], from which (116) follows. Proof of (116) quadratic loss Recall from Subsection C.3 the definition of the losses C L(θ), C L̂N (θ). corresponding to the loss ℓC . Note that by Lemma C.19 ℓC is 2C-Lipschitz. Notice that from the √ N statement of the present lemma proven for the case of Lipschitz losses for λ ≤ 16·2C ln(N ) , with q 2 4 D C = 6Ge ∥eg ∥ψ2 ln( 3N 2δ ) probability 1 − 3δ over data and parameters sampled from ρ , the following holds: 1 ρ(θ) 3 ϵC L(θ) ≤ϵC L̂N (θ) + ln + ln + λ π(θ) 2δ (122) ! 2 1X 2δ ln Eθ∼π exp C̄i (2λ, θ, N, , ϵ) 2 i=1 3 where C̄i (2λ, θ, N, 2δ 3 , ϵ) satisfies (60). From Lemma C.18 it follows that (56) holds with probability 2δ at least 1 − 3 over data and hence (C.18) holds with probability at least 1 − 2δ 3 over data and parameters sampled from ρθ . Hence, by using the union bound, it follows that (122) and (56) hold simultaneously with probability at least 1 − 2δ over data and parameters sampled from ρD . Moreover, if (57) holds, then it holds that C L̂N (θ) = L̂N (θ) and by and (68) – (67) 2 ln 3N 2δ C L(θ) ≤ L(θ) ≤ C L(θ) + 72G2e ∥eg ∥2ψ2 N Hence, 2 ln 3N 2δ ϵL(θ) ≤ ϵC L(θ) + 72G2e ∥eg ∥2ψ2 max{ϵ, 0} N 44

(123)

Hence, by using (122) and C L̂N (θ) = L̂N (θ), it follows that if (123) and (56) both hold, then (116) holds. Since (123) and (56) holds with probability at least 1 − 2δ over data and samples from ρD , so does (116). Proof of (116) implies (118) It follows by applying Lemma D.2. √

N Proof of (117) From the proof of Corollary 3.2 it follows that for λ = L(ln(N ))r where r is as in Corollary 3.2,

1 (ln Eθ∼π exp(C1 (2λ, θ, N, δ, ϵ)) + ln Eθ∼π exp(C2 (2λ, θ, N, δ, ϵ))) ≤ C(δ, ϵ) 2λ Using this inequality, it follows that (116) implies (117). Lemma D.4. If L(θ) is convex, ρ is a probability density over Θ, and θ⋆ = Eθ∼ρ θ is the mean of the density ρ, then L(θ⋆ ) ≤ Eθ∼ρ [L(θ)]. (124) Proof of Lemma D.4. If L(θ) is convex in θ, then L(θ⋆ ) = L(Eθ∼ρD θ) ≤ Eθ∼ρD L(θ) by Jensen’s inequality. Proof of (11). For the single draw case, from (118) of Lemma D.3, it follows that with probability at least 1 − 2δ over data and samples from ρGibbs , Cδ L(ln(N ))r −λL̂N (θ) √ ln + C(δ, ϵ) (125) L(θ⋆ ) ≤ − ln Eθ∼π e + δ N √ for λ = N /(L(ln(N ))r ) For the MEP case, using Lemma D.4 and Lemma D.2 and Corollary 3.2it follows that with probability at least 1 − 2δ over data, it holds that L(ln(N ))r Cδ Gibbs √ L(θ⋆ ) ≤ Eθ∼ρGibbs L(θ) ≤ Eθ∼ρGibbs L̂N (θ) + + C(δ, ϵ) KL(ρ | π) + ln δ N | {z } 1/λ

1 L(ln(N ))r Cδ Gibbs √ | π) + ln + C(δ, ϵ) Eθ∼ρGibbs L̂N (θ) + KL(ρ λ δ N | {z } Cem (δ,σ)

= − ln Eθ∼π e−λL̂N (θ) + with λ = ρ ∈ Mπ ,

√

L(ln(N )) √ Cem (δ, σ) N

(126) N /(L(ln(N ))r ). Using the second equality of (115), it follows that for any posterior

1 1 − ln Eθ∼π e−λL̂N (θ) ≤ Eθ∼ρ L̂N (θ) + KL(ρ∥π) λ λ Choose ρθ⋆ as in Lemma C.22, i.e., ( 2 N (θ⋆ , σN ) if (Gauss) holds ρθ ⋆ = σ U(θ⋆ , √N ) if (Uni) holds

(127)

From Lemma C.23 it follows that (87) holds with probability at least 1 − rLip,1 δ over data, and hence over data and samples from ρGibbs . In particular, as (87) implies Eθ∼ρθ⋆ L̂N (θ) ≤ L̂N (θ⋆ ) + LΘ (δ)L(ln(N ))r+1 Eθ∼ρθ⋆ ∥θ − θ⋆ ∥2 + | {z } ≤ √σ

L(ln(N ))r 1 √ 2rLip,1 Cu,1 + Cu,2 + ln , δ N 45

(128)

It then follows that (128) holds with probability at least 1 − rLip,1 δ over data and samples from ρGibbs . Then using the union bound on (125),(128), and (127) and Lemma C.22 it follows that L(ln(N ))r Cδ √ L(θ⋆ ) ≤ Eθ∼ρGibbs L̂N (θ) ≤ − ln Eθ∼π e−λ L̂N (θ) + ln + C(δ, ϵ) δ N 1 L(ln(N ))r Cδ √ ≤ Eθ∼ρθ⋆ L̂N (θ) + KL(ρθ⋆ ∥π) + ln + C(δ, ϵ) λ δ N σ L ln(N )r 1 ≤ L̂N (θ⋆ ) + LΘ (δ)L(ln(N ))r+1 √ + 2rLip,1 √ Cu,1 + Cu,2 + ln δ N N r+1 r L(ln(N )) L(ln(N )) Cδ √ √ + C(δ, ϵ) + C(θ⋆ ) + ln δ N N L(ln(N ))r+1 σ √ L̂N (θ⋆ ) + LΘ (δ)σ + 2rLip,1 (Cu,1 + Cu,2 ) +C(θ⋆ ) {z } | N

(129)

CL,emp

+ (ln(

Cδ 1 L(ln(N ))r+1 σ √ ) + 2rLin,1 ln( )) + C(δ, ϵ) ≤ L̂N (θ⋆ ) + Cem (δ, σ) δ σ N

with probability at least 1 − (2 + rLip,1 )δ over data and θ⋆ sampled from ρGibbs . Similarly, by using that (126) holds with probability at least 1 − 2δ, the fact that (87) holds with probability as least 1 − rLip,1 δ over data, and that (87) implies (127), it follows, using the union bound that for MEP, Cδ L(ln(N ))r √ ln + C(δ, ϵ) L(θ⋆ ) ≤Eθ∼ρGibbs L̂N (θ) ≤ − ln e + δ N L(ln(N ))r Cδ 1 √ ≤ Eθ∼ρθ⋆ L̂N (θ) + KL(ρθ⋆ ∥π) + ln + C(δ, ϵ) λ δ N L(ln(N ))r+1 σ √ ≤ L̂N (θ⋆ ) + LΘ (δ)L(ln(N ))r+1 √ + C(θ⋆ ) N N 1 L ln(N )r + 2rLip,1 √ Cu,1 + Cu,2 + ln δ N r Cδ L(ln(N ))r+1 σ L(ln(N )) √ √ ln + C(δ, ϵ) ≤ L̂N (θ⋆ + Cem (δ, σ) + δ N N −λEθ∼π L̂N (θ)

(130)

holds with probability at least 1 − (2 + rLip,1 )δ over data. Finally, the case of MAP follows from Lemma C.21 by applying it to the random model θ⋆ : as ∀θ ∈ Θ : L(θ) ≤ L̂N (θ)+

L(ln(N ))r+1 √ (σLΘ (δ) + 2rLip,1 (Cu,1 + Cu,2 ) N L Cδ 1 +2rLip,2 + C(θ) + ln( ) + 2rLip,1 ln( ) + C(δ, ϵ) 512 δ δ

holds with probability at least 1 − (2 + rLip,1 )δ over data, it then follows that for θ = θ⋆ , L(θ⋆ ) ≤ L̂N (θ⋆ )+

L(ln(N ))r+1 √ (σLΘ (δ) + rLip,1 (Cu,1 + Cu,2 ) N L Cδ +2rLip,2 + C(θ⋆ ) + ln 2rLip,1 +1 + C(δ, 1) 512 δ L(ln(N ))r+1 √ = L̂N (θ⋆ ) + Cem (δ, σ) N

D.2

Proof of (12)

From (10) it follows that each of the inequalities below hold with probability at least 1 − 2δ over data L(ln(N ))r Cδ √ + C(δ, 1)) (131) (KL(ρ||π) + ln δ N L(ln(N ))r Cδ √ ∀ρ ∈ Mπ : −Eθ∼ρ L(θ) ≤ − Eθ∼ρ L̂N (θ) + (KL(ρ||π) + ln + C(δ, −1)) (132) δ N ∀ρ ∈ Mπ : Eθ∼ρ L(θ) ≤Eθ∼ρ L̂N (θ) +

In particular, by using the union bound it follows that (131) and (132) hold simultaneously with probability at least 1 − 4δ. Using the fact that for any posterior ρ ∈ Mπ , Eθ∼ρGibbs L̂N (θ) +

L(ln(N ))r L(ln(N ))r √ √ KL(ρGibbs ||π) ≤ Eθ∼ρ L̂N (θ) + (KL(ρ||π) N N

it then follows that with probability at least 1 − 4δ over data L(ln(N ))r Cδ √ (KL(ρGibbs ||π) + ln + C(δ, 1)) δ N L(ln(N ))r Cδ L(ln(N ))r √ √ KL(ρ||π) + ln + C(δ, 1) ≤ Eθ∼ρ L̂N (θ) + δ N N r L(ln(N )) Cδ √ ≤ Eθ∼ρ L(θ) + + C(δ, −1) + KL(ρ||π) + ln δ N L(ln(N ))r Cδ √ + C(δ, 1) + KL(ρ||π) + ln δ N r L(ln(N )) Cδ √ = Eθ∼ρ L(θ) + 2KL(ρ||π) + 2 ln + C(δ, −1) + C(δ, 1) (133) δ N

∀ρ ∈ Mπ :Eθ∼ρGibbs L(θ) ≤ Eθ∼ρGibbs L̂N (θ) +

For the posterior ρθtrue from Lemma C.22, using (88) from Lemma C.23, it follows that Eθ∼ρθtrue L(θ) ≤ L(θtrue ) + LΘ (δ)L(ln(N ))r Eθ∼ρθtrue ∥θ1 − θ2 ∥2 L L(ln(N ))r L ln(N )r √ √ (Cu,1 + Cu,2 ) + 2rLip,2 512 N N L ln(N )r L L(ln(N ))r L(ln(N ))r √ + 2rLip,1 √ (Cu,1 + Cu,2 ) + 2rLip,2 ≤ L(θtrue ) + LΘ (δ)σ √ 512 N N N L ln(N )r CL,true (134) ≤ L(θtrue ) + √ N

+ 2rLip,1

By applying (133) with ρ = ρθtrue and using that by Lemma C.22 KL(ρθtrue ||π) ≤ C(θtrue ) ln(N ) and the fact that ln(N ) ≥ 1 it follows that Eθ∼ρGibbs L(θ) ≤L(θtrue )+ L ln(N )r+1 √ N

Cδ CL,true + 2C(θtrue ) + 2 ln + C(δ, −1) + C(δ, 1) δ

(135)

with probability at least 1 − 4δ. If θ⋆ is MEP, then by Lemma D.4 L(θ⋆ ) ≤ Eθ∼ρGibbs L(θ). Combining this with (135), (12) for MEP follows. For single draw, from Lemma D.3, (119), it follows that with probability at least 1 − 2δ overa data and samples θ⋆ from ρGibbs it holds that 1 L(ln(N ))r Cδ √ L(θ⋆ ) ≤ − ln Eθ∼π e−λL̂N (θ) + ln + C(δ, 1) (136) λ δ N 47

√

with λ = λN = L(lnNN )r . By using(114) from Lemma D.2, it follows that for ρθtrue from Lemma C.22 1 L(ln(N ))r √ − ln Eθ∼π e−λL̂N (θ) ≤ Eθ∼ρθtrue LN (θ) + KL(ρθtrue ||π) (137) λ N Using that 132 holds with probability at least 1 − 2δ over data, and using (134), and ln(N ) ≥ 1, it follows that 1 L(ln(N ))r √ − ln Eθ∼π e−λL̂N (θ) ≤ Eθ∼ρθtrue LN (θ) + KL(ρθtrue ||π) λ N L(ln(N ))r √ KL(ρθtrue ||π) ≤ Eθ∼ρθtrue L(θ) + N L(ln(N ))r Cδ √ + KL(ρθtrue ||π) + ln + C(δ, −1) δ N Cδ L(ln(N ))r+1 √ CL,true + 2C(θtrue ) + ln ≤ L(θtrue ) + + C(δ, −1) (138) δ N with probability at least 1 − 2δ over data and hence over data and samples from ρGibbs . By combining (136) and (138) using the union bounds, it follows that with probability 1 − 4δ over data and samples θ⋆ from ρGibbs , Cδ L(ln(N ))r+1 √ CL,true + 2C(θtrue ) + ln + C(δ, −1)) + L(θ⋆ ) ≤L(θtrue ) + δ N L(ln(N ))r Cδ √ + ln + C(δ, 1) δ N L(ln(N ))r+1 Cδ √ ≤ L(θtrue ) + CL,true + 2C(θtrue ) + 2 ln + C(δ, 1) + C(δ, −1) δ N from which the statement of (12) for single draw follows, by replacing δ by 2δ . Finally, we consider the case of MAP. Since (11), i.e., L(θ⋆ ) ≤ L̂N (θ⋆ )+ (139) 2L(ln(N ))r+1 Cδ √ C(θ⋆ ) + CL,true + CL,emp + ln 2rLip,1 +1 + C(δ, 1) δ N holds with probability at least 1 − (2 + rLip,1 )δ. From (86) applied to θ = θtrue and ϵ = 1 it also follows that L̂N (θtrue ) ≤ L(θtrue )+ (140) 2L(ln(N ))r+1 Cδ √ C(θtrue ) + CL,true + CL,emp + ln 2rLip,1 +1 + C(δ, −1) δ N holds with probability at least 1 − (2 + rLip,1 )δ over data. If θ⋆ is MAP, then θ⋆ minimizes L̂N (θ) − 1 1 1 λ ln π(θ) and hence L̂N (θ⋆ ) − λ ln π(θ⋆ ) ≤ L̂N (θtrue ) − λ ln π(θtrue ). Hence, 1 π(θ⋆ ) L̂N (θ⋆ ) ≤ L̂N (θtrue ) + ln λ π(θtrue ) √

L(ln(N )) 1 N √ and then by using (139)-(140) and the fact that λ = L(ln(N ))r and hence λ ≤ N that with probability 1 − (4 + 2rLip,1 )δ over data,

r+1

, it follow

L̂N (θ⋆ ) ≤ L(θtrue ) 2L(ln(N ))r+1 Cδ √ 2C(θtrue ) + 2CL,true + 2CL,emp + 2 ln (141) δ N 2L(ln(N ))r+1 π(θ ) ⋆ √ + C(δ, 1) + C(δ, −1) + ln π(θtrue ) N holds, hence, by replacing δ with δ/2, it follows that (12) holds with probability at least 1 − (2 + rLip,1 )δ. +

D.3

Proof of (13)

If (SConv) holds, then by [30, Theorem 2.1.11, Theorem 2.1.8] mΘ ∥θ⋆ − θtrue ∥2 ≤ L(θ⋆ ) − L(θtrue ) from which using (12) the inequality (13) follows. D.4

Proof of (14)

From [26, Chapter 4, page 87] it follows that σe2s = L(θtrue ) = inf θ∈Θ L(θ), where σe2s = E[∥es (t)∥22 ], if ℓ is the quadratic loss function, i.e. the true system yields the best possible prediction in mean square sense. ∀θ ∈ Θ : σe2s = L(θtrue ) ≤ L(θ) (142) 2 s where σes is the variance of e (t). That is, the parameter θtrue corresponding to the data generator results in the smallest possible generalisation loss for quadratic loss function. Let Hθ be the transfer function of the predictor parametrized by θ It can be shown (see [12, Appendix, (82)]) and [26, Chapter 4, page 87]) that 1 ∥Hθtrue − Hθ ∥2H2 ≤ (L(θ) − L(θtrue )), mw Then (14) follows from (12) and (143). D.5

(143)

Remark on relationship with system identification and learning

Remark D.5 (Identification of FIR models). Consider the SISO case (ny = nu = 1), fix an integer T0 and let Θ = RT0 and for any θ = (θ1 , . . . , θT0 )T ∈ Θ, let Dθ = θ1 ,      T 0 0 ··· 0 0 1 θ2 1 0 · · · 0 0 0  ..      .  A=  ... ... · · · ... ...  , B =  ...  , Cθ = θ  T0

0 0 ··· 1 0 0 1 PT0 −1 Then ŷθ (t) = u(t − T0 ) + i=0 θi+1 u(t − i). Assume that there exists θtrue ∈ Θ, such that y(t) = ŷθtrue (t) + e(t), where e(t) is i.i.d. with zero mean and variance σ 2 , and independent of u(s), s ∈ Z. Let û(t) = u(t) for t > 0 and let û(t) = 0 for t < 0. Let Φ be the regressor T matrix constructed from ũ as in [34, (3.45), page 48] and let Y = [y(0) · · · y(N − 1)] . Then L̂N (θ) = N1 ∥Y − Φθ∥22 . Assume that the prior π is the Gaussian density N (θ̃, P ), P = P T > 0. Then a lengthy but straightforward calculation reveal that the Gibbs posterior is the Gaussian N N density N (θ̃ + P ΦT (ΦP ΦT + 2λ I)−1 (Y − Φθ̃), P − P ΦT (ΦP ΦT + 2λ I)−1 ΦP ), which is the conditional density of θ w.r.t. Y, Φ presented in [34, (4.6), page 101], if Y = Φθ + E is assumed with N N E ∼ N (0, 2λ IT0 ). Then the MAP and MEP estimates are both θ⋆ = θ̃+P ΦT (ΦP ΦT + 2λ I)−1 (Y − Φθtrue ) and they solve the regularized optimization problem arg minθ∈Θ λL̂N (θ)+(θ−θ̃)P −1 (θ−θ̃). Moreover, they are also the maximum likelihood of the posterior P (θ | Y, Φ). r

)) √ Then Corollary 3.4 applies to θ⋆ , yielding a O( (ln(N ) bound on the generalization gap of θ⋆ and a N )) √ O( (ln(N N

r+1

) bound on the square parameter estimation error ∥θ⋆ − θtrue ∥22 .

Remark D.6. (Maximum likelihood estimates of state-space models). Consider the parametrization of LTI systems x̂(t + 1) = (Âθ + L̂θ Ĉθ )x̂(t) + (B̂θ + Lθ Dθ )u(t) + L̂θ eθ (t), yθ (t) = Ĉθ x̂(t) + D̂θ u(t) + eθ (t)

(144)

where Aθ and Aθ + Lθ Cθ are Schur, eθ (t) is i.i.d., zero mean Gaussian with variance λ1 , (u, eθ ) is jointly Gaussian, eθ (t) is independent of u(s) for s < t. We can associate with (144) the predictor x̂(t + 1) = Âθ x̂(t) + B̂θ u(t) + L̂θ y(t), ŷθ (t | 0) = Ĉθ x̂(t) + D̂θ u(t), 49

(145)

Assume that y is generated by an LTI system of the form (144) which satisfies [4, (1), INP B, page 427]. −1 In this case, by [4, (2.7), page 422, Chapter 7] the conditional likelihood function pθ ({y(t)}N t=−1 | N −1 N −1 N −1 {u(t)}t=0 ) {yθ (t)}t=0 w.r.t {u(t)}t=0 , evaluated at y(t) = y(t) and u(t) = u(t), t = Nλ −1, . . . , N − 1 equals Ze− 2 L̂N (θ) for a suitable constant Z, where the empirical error L̂N (θ) is defined for the quadratic loss. That is, i.e., up to an additive constant, its logarithm equals ln ρGibbs (θ). −1 N −1 In particular, the maximum likelihood estimate argmaxθ∈Θ pθ ({y(t)}N t=0 | {u(t)}t=0 ), see [4, Chapter 7,page 428] equals the MAP argmaxθ∈Θ ρGibbs (θ) of the Gibbs posterior corresponding to 1 the uniform distribution π = vol(Θ) as a prior. Here we assume that vol(Θ) is finite.

We can then use the bounds (11), (12), (13), (14), for the generalization gap, the gap between the true error of the learned model and the best true error and the parameter estimation error respectively. Remark D.7 (Bayesian methods for estimating LTI systems). The Bayesian method for system identification of LTI systems [31] corresponds to taking a single draw, MEP or MAP from the conditional distribution of the parameter given the past observations. If the parametrization is in innovation form, i.e., of the form (144) and all the signals are jointly Gaussian, then by Remark −1 N −1 D.6 the joint density of {y(t)}N t=−1 given {u(t)}t=0 and {y(s), u(s)}s<0 and a parameter θ is Ze−N λL̂N (θ) for a suitable constant, and hence by [31, Section 3, eq. (12)] the conditional density −N λL̂N (θ)

e pθ (y(−1))π(θ) −1 of θ with respect to {y(t), u(t)}N for the quadratic t=0 is the Gibbs posterior Eθ∈π e−λL̂N (θ) loss and a suitable prior, and hence Gibbs posterior for the predictors (145), and hence taking a random draw, MEP or MAP from this conditional density, as suggested by [31], corresponds to taking a random draw, MEP or MAP from the Gibbs posterior. In particular, the bounds (11), (12), (13), (14) apply. Remark D.8 (PEM methods). To begin with if a PEM algorithm can be reduced to optimizing a cost function L̂N (θ) + g(θ), then the algorithm is equivalent to taking the MAP estimate of the Gibbs posterior with a prior π such that − λ1 ln π(θ) = g(θ) λ . In particular, (11)-(14) from Corollary 3.4 applies in this case. For example, the quadratic regularization term g(θ) = (θ − θm )T P −1 (θ − θm ) corresponds to π ∼ N (θm , P/λ). If π can be interpreted as a Gaussian density, then MAP is MEP and the corresponding sharper bounds can be used.

Furthermore, many PEM algorithms rely on choosing randomly the initial parameter estimate. The outcomes of such algorithms can be viewed as drawing a sample from a suitable posterior distribution. More precisely, consoider an algorithm AN . For every initial value θ0 ∈ Θ and data D, the algorithm generates an estimate AN (θ0 , D). Most optimization algorithms used for PEM methods (Gradient, Gauss-Newton), etc. are of this form, if we fix the number of steps. Assume that the initial parameter values θinit are i.i.d., samples from a prior density π. ThenR the resulting parameter values AN (θinit , D) are i.i.d. samples from a distribution PAN (B) = A−1 (B,D) π(θ)dm(θ) for N any B ∈ Bθ . Assume that the latter distribution has a density ρ̂ which is in Mπ . Then Lemma D.3 provides an error bound for the true error of such an algorithm, when applied to an initial parameter value randomly sampled from π. Remark D.9 (Strong convexity of the true error). Strong convexity implies that there is a unique minimizer of the true error, which is the true system. It can be seen as an identifiability and persistence of excitation assumption, as it implies that there is no parameter value which gives the same inputoutput behavior as the true system (otherwise their true errores would be the same), and w is rich enough (the average response to w allows us to find the true system). In fact, strong convexity of the true error (at least locally), is a standard assumption for studying the asympotic distribution of the parameter estimation error [26, Theorem 9.1]. Remark D.10 (Bounds on the difference between system matrices). Assuming that the LTI systems Σ(θ) are all minimal, we can use (14) and [32, Theorem V.2] to derive an error bound (in highprobability) on the difference between the matrices of the learned and true system. Alternatively, if we consider parametrizations based on structure indices [33, Chapter 3] we could use the fact that H2 norms can be used to approximate locally the Riemannian distance between parameter values [33, Chapter 4, page 129]. Remark D.11 (Relationship with [11, 8]). For the case of bounded noise in the data generator, Theorem 3.1 provides a PAC-Bayesian bound on the generalization gap which is similar to [11, 50

Theorem 2, Corollary 1] and [8, Theorem 5.2]. However, [11] considers RNNs, and the corresponding constants Lv (θ), Lg,s (θ), Lg,v correspond to ∥B̂θ ∥2 , ∥Ĉθ ∥2 , and ∥D̂θ ∥2 , respectively, and τ (θ) corresponds to an upper bound on the spectrum of Âθ and C(θ) is such that ∥Âkθ ∥2 ≤ τ (θ)k C(θ). In our setting, Lv (θ), Lg,s (θ), Lg,v can be taken to be C from Assumption 2.1, C(θ) can be taken to be M and τ (θ) can be taken to be γ from Assumption 2.1. Then the constants Gθ , Hθ from [11] are upper bounds on ∥αθ ∥ℓ1 and θ∞ (αθ ) respectively. Hence the term Ψ̂π (λ, N ) of [11, Theorem P2 2, Corollary 1] is an upper bound on the term 12 i=1 ln Eθ∼π exp (Ci (2λ, θ, N, δ, ϵ)) from (8), i.e., the bound of [11, Theorem 2, Corollary 1] is more conservative than the one of this paper. As to [8, Theorem 5.2], it uses ∥αg,y − cθ ∥ℓ1 ≤ Ge (θ) and θ∞ (αg,y − cθ ) ≤ Ge,1 (θ) in the bounds, where cθ and αg,y are defined in Lemma B.3. While this may appear less conservative, the use of cθ makes the bound difficult to evaluate in practice, as cθ depends on the parameters of the unknown data generator. In contrast, our bound uses only ∥αg ∥ℓ1 and θ∞ (αg ), which, although they also depend on the data generator, are easier to estimate or upper bound in practice. Note that [11, 8] do not address the case of unbounded signals or parameter estimation errors. They also do not provide generalization bounds for single draw, MEP, or MAP estimators. Remark D.12 (Relationship with finite-sample bounds [32, 24, 39, 42, 20]). Recent works such as [32, 24, 39, 42, 20] provide finite-sample parameter estimation bounds for specific algorithms (e.g., least-squares for ARX models, subspace methods), typically assuming the data generator starts from a deterministic initial state and often neglecting the stochastic component. However, assuming a deterministic initial state can be problematic, since process noise generally drives the system to a random initial state determined by past disturbances. In contrast, our results: (1) apply to a broad class of learning algorithms (including PEM, maximum likelihood, Bayesian, and regularized FIR methods), (2) assume the data generator is in a stationary regime, (3) explicitly account for both deterministic and stochastic components, and (4) provide generalization bounds. The trade-off is that our bound on the square of the parameter estimation gapr+1 N) error is O (ln √ , which is more conservative than the O lnNN rates in the cited works. N

Record · ID 668053 · SHA-256 b11b81a45654f2dc
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.