# PAC bounds of continuous Linear Parameter-Varying systems related to neural
ODEs

Dániel Rácz  Mihály Petreczky  Bálint Daróczy

###### Abstract

We consider the problem of learning Neural Ordinary Differential Equations
(neural ODEs) within the context of Linear Parameter-Varying (LPV) systems in
continuous-time. LPV systems contain bilinear systems which are known to be
universal approximators for non-linear systems. Moreover, a large class of
neural ODEs can be embedded into LPV systems. As our main contribution we
provide Probably Approximately Correct (PAC) bounds under stability for LPV
systems related to neural ODEs. The resulting bounds have the advantage that
they do not depend on the integration interval.

Machine Learning, Neural ODE, LPV

##  1 Introduction

In this paper we consider the learning problem for a class of ODEs called LPV
systems (Tóth, 2010; Mohammadpour & Scherer, 2012) and connect them to Neural
Ordinary Differential Equations (neural ODE) (Chen et al., 2018; Weinan,
2017). The inputs of such systems are functions of time, and the can be
divided into two categories: control input and scheduling signal. The output
is linear in the control input, but it is non-linear in the scheduling signal.
The differential equations which describe the system are linear in the state
and the control input, and they are non-linear in the scheduling signal. This
class of ODEs represent a bridge between linear ODEs and non-linear ones, and
they are widely used in control theory (Tóth, 2010; Mohammadpour & Scherer,
2012). The reason behind their popularity is the ability to model highly non-
linear phenomena while allowing much simpler theory. In particular, LPV
systems include bilinear systems as a special class. In turn, the latter
system class is a universal approximator for a large class of nonlinear
systems including many commonly used classes of neural ODEs. In addition, many
classes of neural ODEs can be rewritten as LPV systems by choosing a suitable
class of scheduling signals. In particular, neural ODEs with Rectified Linear
Unit (ReLU) activation functions can be viewed as LPV systems, where the
scheduling signal represents the activation regions of the underlying ReLU
network. Neural ODEs have gained popularity in the recent years, see e.g.,
(Massaroli et al., 2020; Kidger, 2022; Chen et al., 2018; Weinan, 2017) and
the references therein. There is a strong connection between Residual Networks
(ResNet) and discrete-time neural ODEs, see e.g. (Wong & Kolter, 2018). A
recent result (Sander et al., 2022) indicate that within the context of
discrete-time ODE and ReLU activations the connection is more tight and the
achievable accuracy is very similar, well above the threshold of comparable
performance.

As the neural ODEs originate from the field of dynamical system it is worth to
discuss the plausible advantage of these methods. In comparison to traditional
deep learning, where the models are trained with some form of back propagation
on a fixed network structure and therefore the networks have constant depth,
neural ODEs avoid the problem of vanishing gradients and the their variable
depth can interpreted are not even discrete. The idea of studying neural LPV
as a system for neural ODE is motivated by the wonderful properties of ReLU
networks, namely that the structure of convex polytopes formed in the input
space by a ReLU network will be non-exponentially complex in the number of
neurons. More so that under some realistic conditions, e.g. Gaussian
initialization of the parameters, non-memorization problem or no-noisy target,
the number of convex activation regions is in expectation not growing
exponentially with the depth of the network. This property was theoretically
and empirically shown in (Hanin & Rolnick, 2019) and recently the authors in
(Balestriero & LeCun, 2023) described a practically feasible algorithm to
enumerate the number of regions. Additionally we may exploit this phenomena by
bounding the number of linear transformations in the LPV system. Our main
contribution is a PAC bound, Theorem 4.3, for LPV system, using Rademacher
complexity and assuming stability of the underlying systems. The obtained
error bound does not depend on the integration interval. In addition, we
present some preliminary results on applying the obtained bounds to prove our
PAC bounds for neural ODEs which can be represented by LPV systems. In
particular, this extension may apply to neural ODEs with ReLU activation
function, under suitable assumptions on the activation regions.

##  2 Related results

There are several recent advancements in the literature of neural ODEs. The
main challenges include robustness, capacity, stability constraints while
maintaining performance, e.g., in (Kang et al., 2021; Rodriguez et al., 2022;
Huang et al., 2022; Zakwan et al., 2022) stability and robustness of neural
ODEs were investigated. For instance, in (Rodriguez et al., 2022) the authors
suggest a novel loss function corresponding to Lyapunov stability. In their
experiments the classification performance increases significantly.
Generalization gaps for neural ODEs were investigated in (Hanson et al., 2021;
Fermanian et al., 2021; Marion, 2023) and earlier in (Sontag, 1998; Koiran &
Sontag, 1998; Kuusela et al., 2004). The paper (Hanson et al., 2021; Sontag,
1998; Koiran & Sontag, 1998) used Vapnik-Chervonenkis (VC) dimensions and
approximations of the input and output signals by their high-order derivatives
while stability was not assumed. As a result, the PAC bounds contain terms
which depend on the ability of the hypothesis class to approximate input-
output pairs by their derivatives, and the bounds are exponential in the
integration time and in the order of derivatives. In contrast, in this paper
we use Rademacher complexity instead of VC dimensions and the resulting bounds
are not exponential in the integration time and they do not involve
approximating continuous-time input and output signals by their derivatives.
In (Kuusela et al., 2004) PAC bounds for linear ODEs were derived for
classification. In contrast we consider regression despite a more general
class of systems. Note that LPV systems include linear ODEs as a special case
(Kuusela et al., 2004). In (Fermanian et al., 2021; Marion, 2023) path
controlled neural ODEs were considered and PAC bounds using Rademacher
complexity were derived. Since stability was not assumed in (Fermanian et al.,
2021; Marion, 2023), these bounds depend exponentially on the integration
time, and their system theoretic interpretation is not obvious. In contrast,
the bounds of this paper can be interpreted in terms of the well-known $H_{2}$
norm of LPV systems. However, the class of systems in (Fermanian et al., 2021;
Marion, 2023) is more general than that of LPV systems. Note that bilinear and
linear systems are both subclasses of LPV systems and are special cases of
systems (Fermanian et al., 2021; Marion, 2023; Hanson et al., 2021; Sontag,
1998). There is a rich body of literature on finite-sample bounds for learning
discrete-time dynamical systems from time-series (Vidyasagar & Karandikar,
2006; Simchowitz et al., 2019; Foster & Simchowitz, 2020; Tsiamis & Pappas,
2019; Sarkar et al., 2021; Lale et al., 2020; Campi & Weyer, 2002; Oymak &
Ozay, 2022), but the learning problem considered in those papers is different
from the one in this paper.

##  3 Problem statement

Linear parameter-varying (LPV) systems are special linear systems where the
coefficients of the linearities - referred to as scheduling signal \- are
time-varying functions. Concretely, an LPV system has the form

$\displaystyle\begin{cases}\dot{\mathbf{x}}(t)=A(\mathbf{p}(t))\mathbf{x}(t)+B(\mathbf{p}(t))\mathbf{u}(t)+\mathbf{b}(\mathbf{p}(t)),\\\
\mathbf{x}(0)=0,\\\
y_{\Sigma}(\mathbf{u},\mathbf{p})(t)=C(\mathbf{p}(t))\mathbf{x}(t),\\\
\end{cases}$ (1)

where $\mathbf{x}(t)\in\mathbb{R}^{n_{x}}$ is the state vector,
$\mathbf{u}(t)\in\mathbb{R}^{n_{in}}$ is the input and
$y_{\Sigma}(\mathbf{p},\mathbf{u})(t)\in\mathbb{R}^{n_{out}}$ is the output of
the system for all $t\in[0,T]$. The vector
$\mathbf{p}(t)=(p_{1}(t),\dots,p_{n_{p}}(t))^{T}\in\mathbb{P}\subseteq\mathbb{R}^{n_{p}}$
is the scheduling variable. The matrices belonging to the system are defined
as

$\displaystyle A(\mathbf{p}(t))$
$\displaystyle=A_{0}+\sum\limits_{i=1}^{n_{p}}p_{i}(t)A_{i}$ $\displaystyle
B(\mathbf{p}(t))$ $\displaystyle=B_{0}+\sum\limits_{i=1}^{n_{p}}p_{i}(t)B_{i}$
$\displaystyle C(\mathbf{p}(t))$
$\displaystyle=C_{0}+\sum\limits_{i=1}^{n_{p}}p_{i}(t)C_{i}$
$\displaystyle\mathbf{b}(\mathbf{p}(t))$
$\displaystyle=\mathbf{b}_{0}+\sum\limits_{i=1}^{n_{p}}p_{i}(t)\mathbf{b}_{i},$

such that the matrices $A_{i}\in\mathbb{R}^{n_{x}\times
n_{x}},B_{i}\in\mathbb{R}^{n_{x}\times
n_{in}},C_{i}\in\mathbb{R}^{n_{out}\times n_{x}}$ and the vectors
$\mathbf{b}_{i}\in\mathbb{R}^{n_{x}}$ are time-independent and constant.
Furthermore, we require $\mathbf{x}(t)$ to be an absolutely continuous
function of the time domain, while
$y_{\Sigma}(\mathbf{u},\mathbf{p})(t),\mathbf{u}(t)$ and $\mathbf{p}(t)$
should be piecewise continuous. Note that for given $\mathbf{u}$ and
$\mathbf{p}$ the system admits a solution
$(\mathbf{x},y_{\Sigma}(\mathbf{u},\mathbf{p}),\mathbf{u},\mathbf{p})$
satisfying (1). In principle we could have allowed the initial state
$\mathbf{x}(0)$ to be a non-zero vector, but for the sake of simplicity we
prefer to assume that $\mathbf{x}(0)=0$.

######  Assumption 3.1 (Scalar output).

In the rest of the paper we work with systems with scalar output, i.e. let
$n_{out}=1$.

LPV systems contain linear control systems and bilinear control systems as
special cases (Isidori, 1985). Indeed, by taking $\mathbf{u}=0$, (1) becomes a
bilinear system. In turn, it is known that bilinear systems can be used to
approximate any non-linear control systems (Krener, 1974).

######  Remark 3.2.

Without loss of generality we can assume $\mathbf{b}(\mathbf{p}(t))=0$ for all
$t\in[0,T]$ as otherwise we concatenate an extra coordinate to $\mathbf{u}(t)$
with value $1$ and replace $B_{i}$ with $[B_{i}|\mathbf{b}_{i}]$, i.e we
append $\mathbf{b}_{i}$ to the columns of $B_{i}$ for all $i$.

######  Assumption 3.3.

The scheduling signal $\mathbf{p}(t)\in[-1,1]$ for all $t\in[0,T]$.

In the sequel, we fix a family $\mathfrak{L}$ of LPV systems of the form (1).
For this family of LPV systems, we make the following stability assumptions.

######  Assumption 3.4.

There exists $\lambda\geq n_{p}$ such that for any $\Sigma\in\mathfrak{L}$ of
the form (1) there exists $Q\succ 0$ such that

$\displaystyle
A_{0}^{T}Q+QA_{0}+\sum\limits_{i=1}^{n_{p}}A_{i}^{T}QA_{i}+\sum\limits_{i=1}^{n_{p}}C_{i}^{T}C_{i}+C_{0}^{T}C_{0}\prec\lambda
Q$

Due to our demand of $\mathbf{u}(t)$ being piecewise continuous, for all $T$,
$\sup\limits_{t\in[0,T]}\left\lVert\mathbf{u}(t)\right\rVert_{2}$ and
$\left\lVert\mathbf{u}(t)\right\rVert_{L_{2}([0,T],\mathbb{R}^{n_{in}})}$ are
finite.

At last we state a crucial lemma based on the previous assumptions which also
implies additional useful properties of our system.

######  Lemma 3.5.

If Assumption 3.4 holds, then for any $\Sigma\in\mathfrak{F}$, let us define
the following: for any $k>0$, $i_{1},\ldots,i_{k}\in\\{1,\ldots,n_{p}\\}$, for
any $i_{u},i_{y}\in\\{0,\ldots,n_{p}\\}$,

$\displaystyle w_{i_{u},i_{y}}(t)=C_{i_{y}}e^{A_{0}t}B_{i_{u}}$ $\displaystyle
w_{i_{1},\ldots,i_{k},i_{y},i_{y}}(t,\tau_{1},\ldots,\tau_{k})=$
$\displaystyle
C_{i_{y}}e^{A_{0}(t-\tau_{k})}A_{i_{k}}e^{\tau_{k}-\tau_{k-1}}\cdots
A_{i_{1}}e^{A_{0}\tau_{1}}B_{i_{u}}$

Then the following holds:

$\displaystyle\|\Sigma\|_{\lambda,H_{2}}^{2}=(\sum_{i_{y},i_{u}=0}^{n_{p}}\int_{0}^{\infty}w_{i_{y},i_{u}}(t)$
$\displaystyle+\sum_{k=1}^{\infty}\sum_{i_{1},\ldots,i_{k}=1}^{n_{p}}\int_{0}^{\infty}\int_{0}^{t}\int_{0}^{\tau_{k}}\cdots\int_{0}^{\tau_{2}}$
$\displaystyle\|w_{i_{1},\ldots,i_{k},i_{y},i_{y}}(t-\tau_{k},\ldots,\tau_{1})\|^{2}_{2}e^{\lambda
t}d\tau_{1}\cdots d\tau_{k}dt)$
$\displaystyle=\sum_{i_{u}=0}^{n_{p}}\mathrm{trace}(B_{i_{u}}^{T}QB_{i_{u}})<+\infty$

Moreover, for any $p\in\mathcal{P}$, $u\in\mathcal{U}$,

$|y_{\Sigma}(\mathbf{u},\mathbf{p})(t)|\leq\|\Sigma\|_{\lambda,H_{2}}\|\mathbf{u}\|_{L_{2}([0,T],\mathbb{R}^{n_{in}})}$
(2)

The proof can be found in Appendix A. Lemma 3.5 states that any LPV system
$\Sigma$ from $\mathfrak{L}$ have a finite weighted _$H_{2}$ norm_
$\|\Sigma\|_{\lambda,H_{2}}$. Indeed, $\|\Sigma\|_{0,H_{2}}$ is just the
classical $H_{2}$ norm (Gosea et al., 2021) for LPV systems. For bilinear
systems, $\|\Sigma\|_{0,H_{2}}$ coincides with the $H_{2}$ norm defined in
(Zhang & Lam, 2002). Intuitively, the $H_{2}$ norm is an upper bound on the
peak output for inputs which have unit energy (Antoulas, 2009). The quantity
$\|\Sigma\|_{\lambda,H_{2}}$ can be thought of as a weighted version of the
$H_{2}$ norm, where the past contribution of inputs is multipled by an
exponential forgetting factor. Note that if $\Sigma$ is of the form (1) and we
replace $A_{0}$ by $A_{0}+\frac{\lambda}{2}I$, then the classical $H_{2}$ norm
of the obtained system coincides with the weighted norm
$\|\Sigma\|_{\lambda,H_{2}}$.

Now let us consider the following learning problem for systems of the form
(1). To this end, let
$\mathbf{S}=\\{\mathbf{p}_{i},\mathbf{u}_{i},y_{i})\\}_{1\leq i\leq N}$, drawn
independently from some unknown distribution
$\mathcal{P}\times\mathcal{D}=(\mathcal{P},\mathcal{U},\mathcal{Y})$, along
with an elementwise loss function
$\ell:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$. The learning problem
assumes the availability of i.i.d. input trajectories. The empirical risk is
defined for a system $\mathcal{S}$ at a fixed timestep $T$ as
$\mathcal{L}_{N}(\Sigma)=\frac{1}{N}\sum\limits_{i=1}^{N}\ell(y_{\Sigma}(\mathbf{p}_{i},\mathbf{u}_{i})(T),y_{i})$,
while the true risk is defined as
$\mathcal{L}(\Sigma)=\mathbb{E}_{(\mathcal{P},\mathcal{U},\mathcal{Y})}[\ell(y_{\Sigma}(\mathcal{P},\mathcal{U})(T),\mathcal{Y})]$.
Our main interest is in the generalization gap
$\sup_{\Sigma\in\mathfrak{L}}|\mathcal{L}(\Sigma)-\mathcal{L}_{N}(\Sigma)|$.

Finally, we state the following assumptions on the data distribution and
hypothesis class $\mathfrak{L}$.

######  Assumption 3.6.

The elementwise loss function $\ell$ is $K_{\ell}$-Lipschitz-continuous and
$\ell(y,y)=0$.

######  Assumption 3.7.

There exist constants $L_{\mathbf{u}}>0$, $K_{\mathbf{u}}>0$ $c_{1}>0$,
$c_{2}>0$ such that the following holds:

$\sup_{\Sigma\in\mathfrak{L}}\|\Sigma\|_{\lambda,H_{2}}=c_{1},$

and for almost any sample $(\mathbf{p},\mathbf{u},y)$ from
$\mathcal{P}\times\mathcal{D}$

$\displaystyle\sup\limits_{t\in[0,T]}\left\lVert\mathbf{u}(t)\right\rVert_{2}\leq
K_{\mathbf{u}}$
$\displaystyle\left\lVert\mathbf{u}(t)\right\rVert_{L_{2}([0,T],\mathbb{R}^{n_{in}})}\leq
L_{\mathbf{u}}$ $\displaystyle|y|<c_{2},$

##  4 Rademacher complexity of LPVs

In this section we bound the Rademacher complexity of our LPV system under the
conditions we stated in the last section. First we define the Rademacher
complexity.

######  Definition 4.1.

(e.g. see definition 26.1 in (Shalev-Shwartz & Ben-David, 2014)) The
Rademacher complexity of a bounded set $\mathcal{A}\subset\mathbb{R}^{m}$ of
vectors is defined as

$\displaystyle
R(\mathcal{A})=\mathbb{E}_{\mathbf{\sigma}}\Bigg{[}\sup_{a\in\mathcal{A}}\frac{1}{m}\sum\limits_{i=1}^{m}\sigma_{i}a_{i}\Bigg{]},$

where the random variables $\mathbf{\sigma}_{i}$ are i.i.d such that
$\mathbb{P}[\sigma_{i}=1]=\mathbb{P}[\sigma=-1]=0.5$. The Rademacher
complexity of a set of functions $\mathcal{F}$ over a set of samples
$S=\\{s_{1}\dots s_{m}\\}$ is defined as

$\displaystyle
R_{S}(\mathcal{F})=R(\left\\{(f(s_{1}),\dots,f(s_{m}))\middle|f\in\mathcal{F}\right\\})$

Our main contribution is a bound to the Rademacher complexity derived from the
following theorem under Assumptions 3.3, 3.6, 3.4 and 4.4.

######  Theorem 4.2.

(e.g. see Theorem 26.5 in (Shalev-Shwartz & Ben-David, 2014)) Let
$\mathcal{E}$ be a compact set of hypotheses and $T$ is a timestep. For any
$\delta\in]0,1[$ and we have

$\displaystyle\mathbb{P}_{\mathcal{S}}\Bigg{(}\forall\Sigma\in\mathcal{E}:\mathcal{L}(\Sigma)-\mathcal{L}_{N}(\Sigma)\leq
R(T,N,\delta)\Bigg{)}\geq 1-\delta,$

where

$\displaystyle
R(T,N,\delta)=2R_{S}(L_{0}(\Sigma,T))+B(T)\sqrt{\frac{2log(\frac{4}{\delta})}{N}}$
$\displaystyle
L_{0}(\Sigma,T)=\\{(\ell(y_{\Sigma}(\mathbf{u}_{N},\mathbf{p}_{N})(T),y_{1}),$
$\displaystyle\hskip 60.0pt\dots,$ $\displaystyle\hskip
60.0pt\ell(y_{\Sigma}(\mathbf{u}_{N},\mathbf{p})(T),y_{N}))^{T}|\text{
}\Sigma\in\mathfrak{F}\\}$

and $B(T)$ is an upper bound on the loss at time $T$.

Now we state our main theorem.

######  Theorem 4.3.

Under assumptions 3.3, 3.6, 3.4 and 3.7 and let $T$ be a timestep. Then for
for any $\delta\in]0,1[$, Theorem 4.2 holds with the bound of

$R(T,N,\delta)=\frac{c_{3}}{\sqrt{N}}\Big{(}2+\sqrt{2\log\big{(}\frac{4}{\delta}\big{)}}\Big{)}$

where

$c_{3}=\max\\{2K_{\ell}c_{2},2K_{\ell}c_{1}L_{\mathbf{u}}(n_{p}+1)\\}$

The bound in Theorem 1 depends on the maximal (weighted) $H_{2}$ norm of the
LPV systems from $\mathfrak{L}$, the maximal energy of the inputs $\mathbf{u}$
and on the maximal possible value of the outputs $y$. The smaller the $H_{2}$
norms are of the LPV systems involved the smaller is the generalization gap.
Likewise, the smaller the input energy is, the smaller is the generalization
gap. Note that the bound does not depend on $T$. However, the constant
$L_{\mathbf{u}}$ may depend on $T$, if we consider inputs $\mathbf{u}$ for
which the global energy $\int_{0}^{\infty}\|u(s)\|_{2}^{2}ds$ is either
infinite or too large.

The computation of the upper bound of Theorem 4.3 involves estimating the
constant $c_{1}$ which represents the maximal $H_{2}$ norms of the elements of
$\mathfrak{L}$. In practice, this not always easy. Below we present some
additional assumption which allows us to compute the bounds of Theorem 4.3.

######  Assumption 4.4.

There exists a positive real number $\gamma>0$ and $\Gamma>0$ such that
$\gamma\geq\Gamma+n_{p}$ and for every $\Sigma\in\mathfrak{L}$ of the form
(1), $\Gamma\geq\sup_{i=1}^{n_{p}}\left\lVert A_{i}\right\rVert^{2}n_{p}$ and

$\displaystyle\left\lVert\mathrm{e}^{A_{0}t}\right\rVert\leq\mathrm{e}^{-\frac{\gamma}{2}t}$

######  Lemma 4.5.

If Assumption 4.4 holds then Assumption 3.4 holds with any
$n_{p}\leq\lambda\leq\gamma-\Gamma$ and $Q$ being equal to the identity
matrix, and

$\displaystyle c_{1}\leq K^{2}_{\omega}$
$\displaystyle:=(n_{p}+1)^{2}K^{2}_{C}K^{2}_{B}\Big{(}\frac{1}{\lambda}+\frac{1}{\gamma-\lambda+\Gamma}\Big{)}$

where $K_{B}=\sup_{i=1}^{n_{p}}\|B_{i}\|$,
$K_{C}=\sup_{i=1}^{n_{p}}\|C_{i}\|$.

The proof can be found in Appendix C.

### Proof of Theorem 4.3

In order to prove Theorem 4.3 \- according to Theorem 4.2 \- it is sufficient
to find an upper bound to the Rademacher complexity of $L_{0}(\Sigma,T)$ and
to the loss function $l$ at time $T$. Before we prove the main theorem at the
end of this section we will state a lemma about the upper bound of the
Rademacher complexity. To identify the bound we reformulate our system and
show that our system is bounded. The following lemma is another key component
in our proof which states that our output is an inner product in a Hilbert
space.

######  Lemma 4.6.

There exists a Hilbert space $\mathcal{H}$ such that

$\displaystyle y_{\Sigma}(\mathbf{u},\mathbf{p})(t)$
$\displaystyle=\langle\omega^{T,\Sigma},\varphi^{T,\mathbf{u},\mathbf{p}}\rangle_{\mathcal{H}}$

where $\omega^{T,\Sigma}$ does not depend on $\mathbf{u}$ and $\mathbf{p}$,
$\varphi^{T,\mathbf{u},\mathbf{p}}$ does not depend on $\Sigma$ and they are
respectively elements of the space $\mathcal{H}$.
Furthermore
$\left\lVert\varphi^{T,\mathbf{u},\mathbf{p}}\right\rVert_{\mathcal{H}}\leq
L_{\mathbf{u}}(n_{p}+1)$ and
$\left\lVert\omega^{T,\mathbf{u}}\right\rVert_{\mathcal{H}}\leq\left\lVert\Sigma\right\rVert_{\lambda,H_{2}}$.

The proof can be found in Appendix B.

Next we state a useful lemma about the Rademacher complexity of Lipschitz
continuous functions.

######  Lemma 4.7.

(e.g. see Lemma 26.9 in (Shalev-Shwartz & Ben-David, 2014)) Under Assumption
3.6 for all $\mathbf{p}$

$\displaystyle R_{S}(L_{0}(\Sigma,T))\leq K_{\ell}\cdot
R_{S}(\\{S(\Sigma,T)|\Sigma\in\mathcal{E}\\})$

where
$S(\Sigma,T)=(y_{\Sigma}(\mathbf{u}_{1},\mathbf{p})(T),\dots,y_{\Sigma}(\mathbf{u}_{N},\mathbf{p})(T))^{T}$.

Next we state a crucial lemma about the upper bound of the complexity given
bounded linear transformations.

######  Lemma 4.8.

(e.g. see Lemma 26.10 in (Shalev-Shwartz & Ben-David, 2014)) Let
$S=(\mathbf{x}_{1},\dots,\mathbf{x}_{m})$ be vectors in a Hilbert space. Then

$\displaystyle
R(\\{\langle\mathbf{w},\mathbf{x}_{1}\rangle,\dots,\langle\mathbf{w},\mathbf{x}_{m}\rangle)^{T}|\left\lVert\mathbf{w}\right\rVert_{2}\leq
1\\})\leq\frac{\max_{i}\left\lVert\mathbf{x}_{i}\right\rVert_{2}}{\sqrt{m}}$

Based on the previous results we can upper bound the empirical Rademacher
complexity of $L_{0}(\Sigma,T)$.

######  Lemma 4.9.

For $c_{4}=L_{\mathbf{u}}K_{\ell}c_{1}(n_{p}+1)$,

$\displaystyle R_{S}(L_{0}(\Sigma,T))\leq\frac{c_{4}}{\sqrt{N}}$

###### Proof.

Let $R=R_{S}(\\{S(\Sigma,T)|\Sigma\in\mathcal{E}\\})$ where
$S(\Sigma,T)=(\langle\omega^{T,\Sigma},\varphi^{T,\mathbf{u}_{1},\mathbf{p}}\rangle_{\mathcal{H}},\dots,\langle\omega^{T,\Sigma},\varphi^{T,\mathbf{u}_{N},\mathbf{p}}\rangle_{\mathcal{H}})^{T}$
based on Lemma 4.6. Using Lemma 4.7 and Lemma 4.8 we have

$\displaystyle R_{S}(L_{0}(\Sigma))$ $\displaystyle\leq
K_{\ell}R_{S}(\\{S(\Sigma,T)|\Sigma\in\mathcal{E}\\})\leq K_{\ell}R$
$\displaystyle\leq\frac{K_{\ell}}{\sqrt{N}}L_{\mathbf{u}}(n_{p}+1)c_{1}$

therefore $c_{4}=L_{\mathbf{u}}K_{\ell}c_{1}(n_{p}+1)$. ∎

The final element to apply Theorem 4.2 is to bound $B(T)$.

######  Lemma 4.10.

Under Assumption 3.7

$\displaystyle B(T)\leq 2K_{\ell}\max\\{c_{2},L_{\mathbf{u}}c\\}$

###### Proof of Lemma 4.10.

Due to Assumption 3.6 we have

$\displaystyle|\ell(y_{\Sigma}(\mathbf{u},\mathbf{p})(T),y)|$
$\displaystyle\leq
2K_{\ell}\max\\{|y_{\Sigma}(\mathbf{u},\mathbf{p})(T)|,|y|\\}$
$\displaystyle\leq 2K_{\ell}\max\\{L_{\mathbf{u}}c_{1},c_{2}\\}$

The last inequality follows from applying Lemma 3.5. ∎

Finally, we can prove the main theorem.

###### Proof of Theorem 4.3.

The theorem follows from Lemmas 4.9 and 4.10 together with Theorem 4.2 for
$B(T)=L_{\mathbf{u}}K_{\ell}K_{\omega}(n_{p}+1)$. ∎

##  5 Connection to VC-dimension and Neural ODEs

A major motivation for studying LPV systems is that they can be used for
embedding neural ODEs. More precisely, we consider the following dynamical
system

$\displaystyle\mathcal{S}\begin{cases}\dot{\mathbf{x}}(t)=f(\mathbf{x}(t),\mathbf{u}(t))\\\
y(\mathbf{x}(0),t)=h(\mathbf{x}(t))\end{cases}$ (3)

where $\mathbf{x}\in\mathbb{R}^{n_{x}}$, $\mathbf{u}\in\mathbb{R}^{n_{in}}$
and $y\in\mathbb{R}$ respectively denote the state, input and output vectors.
We refer to $\psi:\mathbb{R}^{n_{in}}\rightarrow\mathbb{R}^{n_{x}}$ and
$h:\mathbb{R}^{n_{x}}\rightarrow\mathbb{R}$ as the input and output
transformations corresponding to the first and last layer of regular deep
networks. A common choice of $f$ and $h$ are (deep) neural networks. For a
wide variety of choice of $f$ and $h$, (3) can be embedded into an LPV system
as follows: there exists the square matrices $A_{i},B_{i},C_{i}$ and vectors
$\mathbf{b}_{i}$ of appropriate size along with the functions
$p_{i}^{\mathbf{u}}:[0,T]\rightarrow[0,1]$ for all $\mathbf{u}$, such that the
following hold for all $t\in[0,T]$.

$\Sigma_{\mathcal{S}}\left\\{\begin{split}&\dot{\mathbf{x}}(t)=A_{0}\mathbf{x}(t)+B_{0}\mathbf{u}(t)+\mathbf{b}_{0}\\\
&\hskip
18.0pt+\sum\limits_{i=1}^{n_{p}}p_{i}^{\mathbf{u}}(t)(A_{i}\mathbf{x}(t)+B_{i}\mathbf{u}(t)+\mathbf{b}_{i})\\\
&y(t)=C_{0}\mathbf{x}(t)+\sum\limits_{i=1}^{n_{p}}p_{i}^{\mathbf{u}}(t)C_{i}\mathbf{x}(t)\\\
&|p_{i}^{\mathbf{u}}|\leq 1\end{split}\right.$

That is, for any input $\mathbf{u}$ there exist a scheduling signal
$p^{\mathbf{u}}=\begin{bmatrix}p_{1}^{\mathbf{u}}&\ldots&p_{n_{p}}^{\mathbf{u}}\end{bmatrix}^{T}$
such that the output of $\mathcal{S}$ corresponding to $\mathbf{u}$ is the
output of the LPV $\Sigma_{\mathcal{S}}$ corresponding to the input
$\mathbf{u}$ and scheduling $p^{\mathbf{u}}$, i.e.

$y_{\Sigma_{\mathcal{S}}}(0,\mathbf{u},p^{\mathbf{u}})(t)=y(t).$

For instance, $f$ and $h$ could be chosen as
$f(x,\mathbf{u})=\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(Ax+B\mathbf{u})$,
$h(x)=Cx$ with
$\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(z)=(\sigma(z_{1}),\ldots,\sigma(z_{n}))^{T}$
and $\sigma$ is one of the common activation functions, e.g., $ReLU$, $tanh$
etc. If $\sigma$ is ReLU, then $p^{\mathbf{u}}(t)$ is the linear region of
$f$, i.e., $n_{p}=n$, $A_{i},B_{i}$ are the $i$th rows of $A$ and $B$ and

$p^{\mathbf{u}}(t)=\left\\{\begin{array}[]{rl}1&(Ax(t)+B\mathbf{u}(t))_{i}\geq
0\\\ 0&\mbox{otherwise}\end{array}\right.,$

where $\mathbf{x}(t)$ is the solution of (3). If $\sigma$ is $\tanh$, then
again $n_{p}=n$ and $A_{i}$, $B_{i}$ are the $i$th rows of $A$ and $B$ and

$p^{\mathbf{u}}(t)=\left\\{\begin{array}[]{rl}\frac{\tanh((Ax(t)+B\mathbf{u}(t))_{i})}{(Ax(t)+B\mathbf{u}(t)_{i}}&\mbox{if}(Ax(t)+B\mathbf{u}(t))_{i}\neq
0\\\ 0&\mbox{otherwise,}\end{array}\right.$

see (Yin et al., 2022; Verhoek et al., 2023). Note that the embedding of
$\mathcal{S}$ into an LPV system is not unique, various choices will result in
LPV systems with different properties. The construction of such embeddings is
an active research area in the field of control of LPV systems (Verhoek et
al., 2023; Abbas et al., 2021; Koelewijn, 2023). Motivated by this remark, in
this section we consider the following extended version of the LPV learning
problem. We assume that there exists a set $\Phi$ of maps
$\psi_{p}:L_{2}([0,+\infty),\mathbb{R}^{n_{u}})\rightarrow
PC([0,+\infty),[-1,1]^{n_{p}})$ and we consider a family $\mathfrak{S}$ of
systems of the form (3) and a family of LPV systems $\mathfrak{L}$ such that
for any $\mathcal{S}\in\mathfrak{S}$ there exists an LPV
$\Sigma_{\mathcal{S}}$ and $\psi\in\Phi$ such that for any $\mathbf{u}\in
L_{2}([0,T]$,
$y_{\mathcal{S}}(\mathbf{u})=y_{\Sigma_{\mathcal{S}}}(0,\mathbf{u},p^{\mathbf{u}})$
with $p^{\mathbf{u}}=\psi(\mathbf{u})$.

We assume that for any input $\mathbf{u}$, the scheduling $p^{\mathbf{u}}$
which generates the output of $\mathcal{S}$ as an output of an LPV system
originates from one of the functions from $\Phi$. That is, we can identify
systems (3) viewed as a hypothesis class as the sub-family of pairs
$(\phi,\Sigma)$, $\phi\in\Phi$, $\Sigma\in\mathfrak{L}$. Then we can use the
results on the generalization gap for LPV systems for deriving a PAC bound for
systems of the form (3) which can be embedded into LPV systems. More
precisely, let us consider the learning problem defined previously. problem
again assumes the availability of The main idea to bound the generalization
gap is as follows. Let us define

$\begin{split}\mathcal{L}_{N}(\Sigma,\phi)&=\frac{1}{N}\sum\limits_{i=1}^{N}\ell(y_{i},y_{\Sigma}(\mathbf{u}_{i},p_{i},T)),\\\
&p_{i}=\phi(\mathbf{u}_{i}),i=1,\ldots,N\\\
\mathcal{L}(\Sigma,\phi)&=\mathbb{E}_{(\mathcal{U},\mathcal{Y})}\ell(\mathcal{Y},y_{\Sigma}(\mathcal{U},\phi(\mathcal{U}),T))\end{split}$

It then follows that for any $\mathcal{S}\in\mathfrak{S}$ there exists
$\phi\in\Phi$ and $\Sigma\in\mathfrak{L}$, such that

$\mathcal{L}_{N}(\Sigma,\phi)=\mathcal{L}_{N}(\mathcal{S}),\quad\mathcal{L}(\Sigma,\phi)=\mathcal{L}(\mathcal{S}).$

Therefore the generalization gap for systems from $\mathfrak{S}$ satisfies the
following

$\begin{split}&\sup_{\mathcal{S}\in\mathfrak{S}}\mathcal{L}(\mathcal{S})-\mathcal{L}_{N}(\mathcal{S})\leq\\\
&\sup_{\Sigma\in\mathfrak{L},\phi\in\Phi}\mathcal{L}(\Sigma,\phi)-\mathcal{L}_{N}(\Sigma,\phi)\end{split}$
(4)

In order to estimate the latter generalization gap, we can use the PAC bound
derived for LPV systems. To this end, we need to assume that $\Phi$ has a
finite VC dimension.

######  Assumption 5.1.

Assume that the $\Phi$ is either finite or for any $T>0$, the set
$\Phi_{T}=\\{(\mathbf{u},\phi(\mathbf{u}))\mid\mathbf{u}\in
L_{2}([0,T],\mathbb{R}^{n_{in}}),\phi\in\Phi\\}$ has a finite VC-dimension
$d_{T}$.

######  Theorem 5.2.

Under Assumption 5.1 and the assumptions of Theorem 4.3 for any
$\delta\in[0,\delta)$

$\displaystyle\mathbb{P}_{S}\Bigg{(}\forall\mathcal{S}\in\mathfrak{S}:\mathcal{L}(\mathcal{S})-\mathcal{L}_{N}(\mathcal{S})\leq\bar{R}(T,N,\delta)\Bigg{)}\geq
1-\delta,$

where $\bar{R}(T,N,\delta)$ is defined as follows. If $\Phi$ is finite, then

$\displaystyle\bar{R}(T,N,\delta)$
$\displaystyle=\frac{2\mathrm{card}(\Phi)K_{\ell}c_{1}L_{\mathbf{u}}(n_{p}+1)}{\sqrt{N}}$
$\displaystyle+B(T)\sqrt{\frac{2\ln(2/\delta)}{N}}$

where $B(T)\leq 2K_{\ell}\max\\{c_{2},c_{1}L_{\mathbf{u}}\\}$. If $\Phi$ is
possibly infinite, but the set $\Phi_{T}$ defined in Assumption 5.1 has finite
VC dimension $d_{T}$, then

$\displaystyle\bar{R}(T,N,\delta)=\sqrt{2}B(T)(2+\sqrt{\log(2eN/d_{T})d_{T}})+$
$\displaystyle\frac{2K_{\ell}c_{1}L_{\mathbf{u}}(n_{p}+1)}{\sqrt{N}}+B(T)\sqrt{\frac{2\ln(2/\delta)}{\sqrt{N}}}$

The proof can be found in Appendix D. The bound above suggests that the VC-
dimension of the set of scheduling signals $\Phi$ together with the weights of
the systems from $\mathfrak{L}$ determine the generalization power of system
(3). If $\Phi$ is a finite set, i.e., there are only finitely many possible
different scheduling signals for each input, then the PAC bounds are
$O(\frac{1}{\sqrt{N}})$. In comparison in case of classical deep ReLU networks
the number of linear regions are always finite and under some realistic
conditions the number of linear regions are not necessarily increasing
exponentially with depth (Hanin & Rolnick, 2019). If $\Phi$ is possibly
infinite, but has a finite VC dimension, then the PAC bound is
$O(\sqrt{\log(N)d_{T})}$, where $d_{T}$ is the VC dimension of $\Phi$. This
conclusion is especially interesting for neural ODEs which correspond to
neural networks with ReLU activation function. For such systems, the set
$\Phi$ can be taken as the set of all sequences of activation regions of the
ReLU network. There are some empirical evidence that ReLU networks tend to
visit few regions as their depth grow. This means that neural ODEs which are
represented by ReLU networks could also exhibit the same behavior, i.e., the
set $\Phi$ would have a small VC dimension, or possibly it would be finite
with a small cardinality. All this remains a topic of future research.

##  6 Discussion

Viewing neural ODEs within the context of bilinear LPVs, we established novel
PAC and Rademacher complexity bounds under stability conditions. The resulting
PAC bounds do not depend on the integration interval. The generalization
bounds indicate the importance of the scheduling signal in LPV systems and we
intend to continue to examine how the scheduling affect the performance and
the generalization gap. We believe that analogous results hold for marginally
stable systems and for highly overparametrizated neural ODE systems.

## References

  * Abbas et al. (2021) Abbas, H. S., Tóth, R., Petreczky, M., Meskin, N., Mohammadpour Velni, J., and Koelewijn, P. J.  Lpv modeling of nonlinear systems: A multi-path feedback linearization approach.  _International Journal of Robust and Nonlinear Control_ , 31(18):9436–9465, 2021.  doi: https://doi.org/10.1002/rnc.5799.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/rnc.5799.
  * Antoulas (2009) Antoulas, A.  _Approximation of Large-Scale Dynamical Systems_.  Advances in Design and Control. 2009.  ISBN 9780898716580.  URL https://books.google.fr/books?id=HntlsoAR0NoC.
  * Balestriero & LeCun (2023) Balestriero, R. and LeCun, Y.  Fast and exact enumeration of deep networks partitions regions.  In _ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 1–5, 2023.  doi: 10.1109/ICASSP49357.2023.10095698.
  * Campi & Weyer (2002) Campi, M. C. and Weyer, E.  Finite sample properties of system identification methods.  _IEEE Transactions on Automatic Control_ , 47(8):1329–1334, 2002.
  * Chen et al. (2018) Chen, R. T., Rubanova, Y., Bettencourt, J., and Duvenaud, D. K.  Neural ordinary differential equations.  _Advances in neural information processing systems_ , 31, 2018.
  * Fermanian et al. (2021) Fermanian, A., Marion, P., Vert, J.-P., and Biau, G.  Framing rnn as a kernel method: A neural ode approach.  _Advances in Neural Information Processing Systems_ , 34:3121–3134, 2021.
  * Foster & Simchowitz (2020) Foster, D. and Simchowitz, M.  Logarithmic regret for adversarial online control.  In _Proceedings of the 37th ICML_ , volume 119 of _PMLR_ , pp. 3211–3221. PMLR, 7 2020.
  * Gosea et al. (2021) Gosea, I. V., Petreczky, M., and Antoulas, A. C.  Reduced-order modeling of lpv systems in the loewner framework.  In _2021 60th IEEE Conference on Decision and Control (CDC)_ , pp. 3299–3305. IEEE, 2021.
  * Hanin & Rolnick (2019) Hanin, B. and Rolnick, D.  Deep relu networks have surprisingly few activation patterns.  _Advances in neural information processing systems_ , 32, 2019.
  * Hanson et al. (2021) Hanson, J., Raginsky, M., and Sontag, E.  Learning recurrent neural net models of nonlinear systems.  In _Learning for Dynamics and Control_ , pp. 425–435. PMLR, 2021\.
  * Huang et al. (2022) Huang, Y., Yu, Y., Zhang, H., Ma, Y., and Yao, Y.  Adversarial robustness of stabilized neural ode might be from obfuscated gradients.  In Bruna, J., Hesthaven, J., and Zdeborova, L. (eds.), _Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference_ , volume 145 of _Proceedings of Machine Learning Research_ , pp. 497–515. PMLR, 16–19 Aug 2022.  URL https://proceedings.mlr.press/v145/huang22a.html.
  * Isidori (1985) Isidori, A.  _Nonlinear control systems: an introduction_.  Springer, 1985.
  * Kang et al. (2021) Kang, Q., Song, Y., Ding, Q., and Tay, W. P.  Stable neural ode with lyapunov-stable equilibrium points for defending against adversarial attacks.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 14925–14937. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/7d5430cf85f78c4b7aa09813b14bce0d-Paper.pdf.
  * Kidger (2022) Kidger, P.  On neural differential equations.  _arXiv preprint arXiv:2202.02435_ , 2022.
  * Koelewijn (2023) Koelewijn, P.  _Analysis and Control of Nonlinear Systems with Stability and Performance Guarantees: A Linear Parameter-Varying Approach_.  PhD thesis, Electrical Engineering, February 2023.  Proefschrift.
  * Koiran & Sontag (1998) Koiran, P. and Sontag, E. D.  Vapnik-chervonenkis dimension of recurrent neural networks.  _Discrete Applied Mathematics_ , 86(1):63–79, 1998.
  * Krener (1974) Krener, A.  Bilinear and nonlinear realization of input-output maps.  _SIAM Journal on Control_ , 13(4), 1974.
  * Kuusela et al. (2004) Kuusela, P., Ocone, D., and Sontag, E. D.  Learning complexity dimensions for a continuous-time control system.  _SIAM journal on control and optimization_ , 43(3):872–898, 2004.
  * Lale et al. (2020) Lale, S., Azizzadenesheli, K., Hassibi, B., and Anandkumar, A.  Logarithmic regret bound in partially observable linear dynamical systems.  _Advances in Neural Information Processing Systems_ , 33:20876–20888, 2020.
  * Marion (2023) Marion, P.  Generalization bounds for neural ordinary differential equations and deep residual networks.  _arXiv preprint arXiv:2305.06648_ , 2023.
  * Massaroli et al. (2020) Massaroli, S., Poli, M., Park, J., Yamashita, A., and Asama, H.  Dissecting neural odes.  _Advances in Neural Information Processing Systems_ , 33:3952–3963, 2020.
  * Mohammadpour & Scherer (2012) Mohammadpour, J. and Scherer, C.  _Control of Linear Parameter Varying Systems with Applications_.  Springer, 2012.
  * Oymak & Ozay (2022) Oymak, S. and Ozay, N.  Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis.  _IEEE Transactions on Automatic Control_ , 67(4):1914–1928, 4 2022.
  * Rodriguez et al. (2022) Rodriguez, I. D. J., Ames, A., and Yue, Y.  Lyanet: A lyapunov framework for training neural odes.  In _International Conference on Machine Learning_ , pp. 18687–18703. PMLR, 2022.
  * Sander et al. (2022) Sander, M., Ablin, P., and Peyré, G.  Do residual neural networks discretize neural ordinary differential equations?  _Advances in Neural Information Processing Systems_ , 35:36520–36532, 2022.
  * Sarkar et al. (2021) Sarkar, T., Rakhlin, A., and Dahleh, M. A.  Finite time LTI system identification.  _J. Mach. Learn. Res._ , 22:26:1–26:61, 2021.
  * Shalev-Shwartz & Ben-David (2014) Shalev-Shwartz, S. and Ben-David, S.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Simchowitz et al. (2019) Simchowitz, M., Boczar, R., and Recht, B.  Learning linear dynamical systems with semi-parametric least squares.  In _Conference on Learning Theory_ , pp. 2714–2802. PMLR, 2019\.
  * Sontag (1998) Sontag, E. D.  A learning result for continuous-time recurrent neural networks.  _Systems & control letters_, 34(3):151–158, 1998.
  * Tóth (2010) Tóth, R.  _Modeling and identification of linear parameter-varying systems_ , volume 403.  Springer, 2010.
  * Tsiamis & Pappas (2019) Tsiamis, A. and Pappas, G. J.  Finite sample analysis of stochastic system identification.  In _2019 IEEE 58th Conference on Decision and Control (CDC)_ , pp. 3648–3654, 2019.
  * Verhoek et al. (2023) Verhoek, C., Wang, R., and Tóth, R.  Learning stable and robust linear parameter-varying state-space models, 2023.
  * Vidyasagar & Karandikar (2006) Vidyasagar, M. and Karandikar, R. L.  A learning theory approach to system identification and stochastic adaptive control.  _Probabilistic and randomized methods for design under uncertainty_ , pp. 265–302, 2006.
  * Weinan (2017) Weinan, E.  A proposal on machine learning via dynamical systems.  _Communications in Mathematics and Statistics_ , 1(5):1–11, 2017.
  * Wong & Kolter (2018) Wong, E. and Kolter, Z.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In _International conference on machine learning_ , pp. 5286–5295. PMLR, 2018.
  * Yin et al. (2022) Yin, H., Seiler, P., and Arcak, M.  Stability analysis using quadratic constraints for systems with neural network controllers.  _IEEE Transactions on Automatic Control_ , 67(4):1980–1987, 2022.  doi: 10.1109/TAC.2021.3069388.
  * Zakwan et al. (2022) Zakwan, M., Xu, L., and Ferrari-Trecate, G.  On robust classification using contractive hamiltonian neural odes.  _arXiv preprint arXiv:2203.11805_ , 2022.
  * Zhang & Lam (2002) Zhang, L. and Lam, J.  On $\mathcal{H}_{2}$ model reduction of bilinear systems.  _Automatica_ , 38:205–216, 2002.

##  Appendix A Proof of Lemma 3.5

If Assumption 3.4 holds, then $A_{0}^{T}Q+QA_{0}\prec-\lambda Q$, and hence
$A_{0}+\lambda I$ is Hurwitz. Let
$S=A_{0}^{T}Q+QA_{0}+\sum\limits_{i=1}^{n_{p}}A_{i}^{T}QA_{i}+\sum\limits_{i=1}^{n_{p}}C_{i}^{T}C_{i}+C_{0}^{T}C_{0}+\lambda
Q$. Then $S\prec 0$ and hence $S=-VV^{T}$ for some $V$. Define
$\tilde{C}=\begin{bmatrix}C_{0}^{T}&\ldots&C_{n_{p}}^{T}&V^{T}\end{bmatrix}^{T}$,
$\tilde{A}=(A+0.5\lambda I)$ and $N_{i}=A_{i}$, $i=1,\ldots,n_{p}$. Then

$\tilde{A}^{T}Q+Q\tilde{A}+\sum_{i=1}^{n_{p}}N_{i}^{T}QN_{i}+\tilde{C}^{T}\tilde{C}=0$

and hence by Zhang & Lam (2002, Theorem 2) the $H_{2}$-norm of the Volterra-
series of the bilinear system

$\displaystyle\dot{z}=\tilde{A}z+\sum_{i=1}^{n_{p}}\left(N_{i}zp_{i}(t)+G_{i}p_{i}(t)\right)$
$\displaystyle\tilde{y}=\tilde{C}z$

for any choice of the matrices $\\{G_{i}\\}_{i=1}^{n_{p}}$, i.e., for

$\displaystyle g^{i}(t)=\tilde{C}e^{\tilde{A}t}G_{i}$

and for all $i_{1},\ldots,i_{k}=1,\ldots,n_{p}$, $k>0$

$\displaystyle
g^{i_{1},\ldots,i_{k},i}(t_{k},\ldots,t_{1})=\tilde{C}e^{\tilde{A}t_{k}}N_{i_{k}}\cdots
e^{\tilde{A}t_{1}}N_{i_{1}}e^{\tilde{A}t_{1}}G_{i}$

the following infinite sum of infinite integrals is convergent:

$\displaystyle\sum_{i=1}^{n_{p}}\int_{0}^{\infty}\|g^{i}(t)\|_{2}^{2}dt+\sum_{k=1}\int_{0}^{\infty}\cdots\int_{0}^{\infty}\|g^{i_{1},\ldots,i_{k},i}(t_{k},\ldots,t_{1})\|_{2}^{2}dt_{1}\cdots
dt_{k}<+\infty$

By choosing $G_{i}=B_{i_{u}}$, $i=0,1,\ldots,n_{p}$ it follows that
$w_{i_{1},\ldots,i_{k},i_{u},i_{y}}(t,\tau_{1},\ldots,\tau_{k})e^{\lambda t}$
is the $(i_{y}+1)$th block row of
$g^{i_{1},\ldots,i_{y}}(t-\tau_{k},\tau_{k}-\tau_{k-1},\ldots,\tau_{2}-\tau_{1},\tau_{1})$
and hence it follows that the right-hands side of

$\displaystyle\|\Sigma\|_{\lambda,H_{2}}^{2}=\left(\sum_{i_{y},i_{u}=0}^{n_{p}}\sum_{k=0}^{\infty}\sum_{i_{1},\ldots,i_{k}=1}^{n_{p}}\int_{0}^{\infty}\int_{0}^{t}\int_{0}^{\tau_{k}}\cdots\int_{0}^{\tau_{2}}\right.\left.\|w_{i_{1},\ldots,i_{k},i_{y},i_{y}}(t-\tau_{k},\ldots,\tau_{1})\|^{2}_{2}e^{\lambda
t}d\tau_{1}\cdots d\tau_{k}dt\right)<+\infty$

is convergent.

From Lemma 4.6 it follows that $y_{\Sigma}(0,\mathbf{u},p)(T)$ can be
represented by the scalar product
$y_{\Sigma}(0,\mathbf{u},p)(T)=\langle\omega^{T,\Sigma},\varphi^{T,\mathbf{u},\mathbf{p}}\rangle_{\mathcal{H}_{2}}$
in a suitably defined Hilbert-space. From the definition of
$\omega^{T,\Sigma}$ and $\varphi^{T,\mathbf{u},\mathbf{p}}$ it follows that
$\|\omega^{T,\Sigma}\|_{\mathcal{H}_{2}}\leq\|\Sigma\|_{\lambda,H_{2}}$, and
$\|\varphi^{T,\mathbf{u},\mathbf{p}}\|_{\mathcal{H}_{2}}\leq\|u\|_{L_{2}}$ and
hence by the Cauchy-Schwartz inequality for any $p\in\mathcal{P}$,
$u\in\mathcal{U}$

$\displaystyle|y_{\Sigma}(0,u,p)(t)|\leq\|\Sigma\|_{\lambda,H_{2}}\|u\|_{L_{2}}$

follows.

##  Appendix B Proof of Lemma 4.6

The transition matrix $\Phi^{\mathbf{u}}(t,\tau)$ belonging to the system (1)
for a fixed input function $\mathbf{u}$ is the unique solution of the system
$\dot{\Phi}^{\mathbf{u}}(t,\tau)=A(\mathbf{p}(t))\Phi^{\mathbf{u}}(t,\tau)$
such that $\Phi^{\mathbf{u}}(\tau,\tau)=I$ for all $\tau\in[0,T]$.

######  Lemma B.1.

(see Chapter 3.3.1.1 in (Tóth, 2010)) For a system of form 1 we have

$\displaystyle y_{\Sigma}(\mathbf{u},\mathbf{p})(t)$
$\displaystyle=\int_{0}^{T}C(\mathbf{p}(\tau))\Phi^{\mathbf{u}}(t,\tau)B(\mathbf{p}(\tau))\mathbf{u}(\tau)\,d\tau=:T_{2}$

We will show that for which

$\displaystyle y_{\Sigma}(\mathbf{u},\mathbf{p})(t)$
$\displaystyle=\langle\omega_{2}^{T,\Sigma},\varphi_{2}^{T,\mathbf{u},\mathbf{p}},\rangle_{\mathcal{H}_{2}}$

where $\omega_{2}^{T,\Sigma}$ does not depend on $\mathbf{u}$ or $\pi$,
$\varphi_{i}^{T,\mathbf{u},\mathbf{p}}$ does not depend on $\Sigma$ and they
are respectively of $\mathcal{H}_{2}$ . Consider the system of the following
form for all $1\leq i_{0}\leq n_{p}$.

$\displaystyle\begin{cases}\dot{\mathbf{x}}(t)=A_{0}\mathbf{x}(t)+\sum\limits_{i=1}^{n_{p}}A_{i}\mathbf{x}(t)\mathbf{p}_{i}(t)\\\
\mathbf{x}(0)=\psi(\mathbf{u})\\\
y_{i_{0}}(\mathbf{x}(0),t)=C_{i_{0}}\mathbf{x}(t)\end{cases}$ (5)

We know from (Isidori, 1985) that for such systems

$\displaystyle
y_{i_{0}}(\mathbf{x}(0),t)=\omega_{i_{0}}^{t}+\sum\limits_{k=1}^{\infty}\sum\limits_{i_{1},..,i_{k}=1}^{n_{p}}\int_{0}^{t}\int_{0}^{\tau_{k}}\dots\int_{0}^{\tau_{2}}\omega_{i_{0},i_{1}\dots
i_{k}}^{t,\tau_{k},\dots\tau_{1}}\mathbf{p}_{i_{k}}(\tau_{k})\dots\mathbf{p}_{i_{1}}(\tau_{1})\,d\tau_{k}\dots\,d\tau_{1}\text{,
where}$
$\displaystyle\omega_{i_{0},\dots,i_{k}}^{t,\tau_{k},\dots,\tau_{1}}=\omega_{i_{0},\dots,i_{k}}(t,\tau_{k},\dots,\tau_{1})\in
L_{2}([0,T]^{k+1},\mathbb{R}^{n})$
$\displaystyle\omega_{i}^{t}=\tilde{\omega}_{i}^{t}\psi(\mathbf{u}),\quad\tilde{\omega}_{i}^{t}=C_{i}\mathrm{e}^{A_{0}t},\quad\omega_{i_{0},\dots
i_{k}}^{t,\tau_{k},\dots,\tau_{1}}=\tilde{\omega}_{i_{0},\dots
i_{k}}^{t,\tau_{k},\dots,\tau_{1}}\psi(\mathbf{u})$
$\displaystyle\tilde{\omega}_{i_{0},\dots
i_{k}}^{t,\tau_{k},\dots,\tau_{1}}=C_{i_{0}}\mathrm{e}^{A_{0}(t-\tau_{k})}\Big{(}\prod\limits_{j=k}^{1}A_{i_{j}}\mathrm{e}^{A_{0}(\tau_{j}-\tau_{j-1})}\Big{)}\mathrm{e}^{A_{0}\tau_{1}}$
$\displaystyle\text{if }t\geq\tau_{k}\geq\dots\geq\tau_{1}\text{ and 0
otherwise.}$

###  B.1 $T_{2}$ as scalar product

In this section let $\mathbb{Q}$ denote the set of integers between $0$ and
$n_{p}$, and $\mathbb{Q}^{\times}$ the set of all multiindices over
$\mathbb{Q}$. Let us define the Hilbert space $\mathcal{H}_{2}$ equipped with
an inner product as follows. Let $\mathcal{H}_{2}$ consist of functions of the
form
$f:\mathbb{Q}^{\times}\setminus\mathbb{Q}\rightarrow\cup\bigcup_{k=1}^{\infty}L_{2}([0,T]^{k},\mathbb{R}^{n})$
such that for any $q,r\in\mathbb{Q}$ $f(qr)\in L_{2}([0,T],\mathbb{R}^{n})$,
for any $r,q_{0},\ldots,q_{k}\in\mathbb{Q}$, $k>0$, $f(rq_{0}\cdots q_{k})\in
L_{2}([0,T]^{k+1},\mathbb{R}^{n})$, and if $q_{i}=0$ for some $i=1,\ldots,k$,
then $f(rq_{0}\cdots q_{k})=0$. For such function $f$

$\displaystyle
f\in\mathcal{H}_{1}\Leftrightarrow\sum\limits_{q\in\mathbb{Q}}\left\lVert
f(q)\right\rVert_{\mathbb{R}^{n}}^{2}+\sum\limits_{\begin{subarray}{c}q\in\mathbb{Q}^{\times}\\\
|w|>1\end{subarray}}\left\lVert f(w)\right\rVert_{L_{2}}<+\infty$

The inner product on $\mathcal{H}_{1}$ is defined as

$\displaystyle\langle f,g\rangle=\sum\limits_{q\in\mathbb{Q}}\langle
f(q),g(q)\rangle_{\mathbb{R}^{n}}+\sum\limits_{w\in\mathbb{Q}^{\times}\setminus\mathbb{Q}}\langle
f(w),g(w)\rangle_{L_{2}}$

Analogously to the previous case we will show that $T_{2}$ has the an inner
product formalization over a suitable choice of a Hilbert space. The
definition of $\mathcal{H}_{2}$ is similar to the definition of
$\mathcal{H}_{1}$ with the exception of $n=n_{in}$. The inner product in this
case is

$\displaystyle\langle f,g\rangle=\sum\limits_{q,r\in\mathbb{Q}^{2}}\langle
f(q,r),g(q,r)\rangle_{L_{2}([0,T],\mathbb{R}^{n})}+\sum\limits_{w\in\mathbb{Q}^{\times}\setminus(\mathbb{Q}\cup\mathbb{Q}^{2})}\langle
f(w),g(w)\rangle_{L_{2}([0,T]^{|w|+1},\mathbb{R}^{n})}$

Let us use the notation of Lemma 3.5 Let
$\omega_{2}^{T,\Sigma}(q,r)(\tau)=w_{q,r}(T-\tau)e^{\lambda(T-\tau)}$ and for
$r,q_{0}\in\mathbb{Q}$ and any $q_{1},\ldots,q_{k}\in\mathbb{Q}$, let
$\omega_{2}^{T,\sigma}(r,q_{0},\dots q_{k})\in
L_{2}([0,T]^{k+1},\mathbb{R}^{n})$ for $(r,q_{0},\dots
q_{k})\in\mathbb{Q}^{\times}$ such that $\omega_{2}^{T,\Sigma}(r,q_{0},\dots
q_{k})(\tau,\tau_{1},\dots,\tau_{k})=$ $=w_{q_{1},\dots
q_{k},q_{0},r}(T-\tau,\tau_{k},\dots\tau_{1})e^{\lambda(T-\tau)}$ if
$T-\tau\geq\tau_{k}\geq\ldots\geq\tau_{1}$ and $q_{1},\ldots,q_{k}$ are all
difference from zero, and $\omega_{2}^{T,\Sigma}(r,q_{0},\dots
q_{k})(\tau,\tau_{1},\dots,\tau_{k})=0$ otherwise. Let
$\varphi_{2}^{T,\tau,\mathbf{u},\mathbf{p}}(q,r)=p_{q}^{\mathbf{u}}(T)p_{r}^{\mathbf{u}}(\tau)\mathbf{u}(\tau)\mathrm{e}^{-\lambda(T-\tau)}$
(as a function of $\tau$) and
$\varphi_{2}^{T,\tau,\mathbf{u},\mathbf{p}}(r,q_{0},\dots q_{k})\in
L_{2}([0,T]^{k+1},\mathbb{R}^{n})$ for $(r,q_{0},\dots
q_{k})\in\mathbb{Q}^{\times}$ such that $\varphi_{2|r,q_{0},\dots
q_{k}}^{T,\tau,\mathbf{u},\mathbf{p}|\tau_{1},\dots,\tau_{k}}=\varphi_{2}^{T,\mathbf{u},\mathbf{p}}(r,q_{0},\dots
q_{k})(\tau,\tau_{k},\dots,\tau_{1})=p_{q_{k}}^{\mathbf{u}}(\tau_{k}+\tau)\dots
p_{q_{1}}^{\mathbf{u}}(\tau_{1}+\tau)p_{q_{0}}^{\mathbf{u}}(T)p^{\mathbf{u}}_{r}(\tau)\mathbf{u}(\tau)\mathrm{e}^{-\lambda(T-\tau)}$
if $T>\tau_{k}\geq\dots\geq\tau_{1}\geq\tau$ and 0 otherwise. Let
$y_{i_{0},j_{0}}^{\tau}(t)$ be the output of the system 5 starting from the
initial value $x(0)=0$. Applying the Volterra series expansion and taking the
linear combination we formally have
$T_{2}=\langle\omega_{2}^{T,\Sigma},\varphi_{2}^{T,\mathbf{u},\mathbf{p}}\rangle_{\mathcal{H}_{2}}$.
We will show that they have finite $\mathcal{H}_{2}$ norm.

######  Lemma B.2.

$\varphi_{2}^{T,\mathbf{u},\mathbf{p}}\in\mathcal{H}_{2}$.

###### Proof.

Using the notations $\tau_{k+1}=T-\tau$, and the definition of
$\mathcal{H}_{2}$ we have

$\displaystyle\left\lVert\varphi_{2}^{T,\mathbf{u},\mathbf{p}}\right\rVert_{\mathcal{H}_{2}}^{2}$
$\displaystyle=\sum\limits_{r,q=0}^{n_{p}}\int_{0}^{T}p_{q}^{\mathbf{u}}(T)(p_{r}^{\mathbf{u}})^{2}(\tau)\left\lVert\mathbf{u}(\tau)\right\rVert_{2}^{2}\mathrm{e}^{-\lambda(T-\lambda)}\,d\tau$
$\displaystyle+\sum\limits_{k=1}^{\infty}\sum_{r,q_{0}=0}^{n_{p}}\sum\limits_{q_{1}\dots,q_{k}=1}^{n_{p}}\int_{0}^{T}\int_{0}^{\tau_{k+1}}\dots\int_{0}^{\tau_{2}}\left\lVert\varphi_{2|r,q_{0},\dots
q_{k}}^{T,\mathbf{u},\mathbf{p}|\tau_{1},\dots,\tau_{k}}\right\rVert^{2}\prod\limits_{i=1}^{k+1}\,d\tau_{i}\,d\tau$
$\displaystyle\leq(n_{p}+1)^{2}\left\lVert\mathbf{u}(\tau)\right\rVert_{L_{2}}^{2}+\sum\limits_{k=1}^{\infty}\left\lVert\mathbf{u}(\tau)\right\rVert_{L_{2}}^{2}\sum\limits_{r,q_{0}\dots
q_{k}=0}^{n_{p}}\int_{0}^{T}\mathrm{e}^{-\lambda(T-\tau)}\int_{0}^{\tau_{k+1}}\dots\int_{\tau}^{\tau_{2}}\,d\tau_{1}\dots\,d\tau_{k+1}\,d\tau$
$\displaystyle\leq\left\lVert\mathbf{u}(\tau)\right\rVert_{L_{2}}^{2}(n_{p}+1)^{2}\frac{\mathrm{e}^{(n_{p}+1-\lambda)T}-1}{\lambda-
n_{p}-1}=:K_{\varphi_{2}}^{2}(T)\leq\left\lVert\mathbf{u}(\tau)\right\rVert_{L_{2}}^{2}(n_{p}+1)^{2}=:K_{\varphi_{2}}^{2}<+\infty$

for a suitable choice of $\lambda$ as long as
$\left\lVert\mathbf{u}(\tau)\right\rVert_{L_{2}}^{2}$ is bounded. ∎

######  Lemma B.3.

$\omega_{2}^{T,\Sigma}\in\mathcal{H}_{2}$.

###### Proof.

Using the notation $\tau_{k+1}=T-\tau$ and the definition of $\mathcal{H}_{2}$
and Lemma 3.5we have

$\displaystyle\left\lVert\omega_{2}^{T,\Sigma}\right\rVert_{\mathcal{H}_{2}}^{2}$
$\displaystyle=\sum\limits_{r,q=0}^{n_{p}}\int_{0}^{T}\|w_{r,q}(T-\tau)\|_{2}^{2}e^{\lambda(T-\tau)}d\tau$
$\displaystyle+\sum\limits_{k=1}^{\infty}\sum\limits_{q_{1}\dots,q_{k}=1}^{n_{p}}\int_{0}^{T}\int_{0}^{\tau_{k+1}}\dots\int_{0}^{\tau_{2}}\|w_{q_{1},\ldots,q_{k}}(\tau_{k+1},\tau_{k},\ldots,\tau_{1})e^{\lambda\tau_{k+1}}d\tau_{k+1}\cdots\tau_{1}\leq$
$\displaystyle\int_{0}^{\infty}\|w_{r,q}(T-\tau)\|_{2}^{2}e^{\lambda(T-\tau)}d\tau$
$\displaystyle+\sum\limits_{k=1}^{\infty}\sum\limits_{q_{1}\dots,q_{k}=1}^{n_{p}}\int_{0}^{\infty}\int_{0}^{\tau_{k+1}}\dots\int_{0}^{\tau_{2}}\|w_{q_{1},\ldots,q_{k}}(\tau_{k+1},\tau_{k},\ldots,\tau_{1})e^{\lambda\tau_{k+1}}d\tau_{k+1}\cdots\tau_{1}\leq
c_{1}$

∎

##  Appendix C Proof of Lemma 4.5

Follows from the proof of Lemma B.3.

##  Appendix D Proof of Theorem 5.2

From (4) it follows that it is enough to show that

$\displaystyle\mathbb{P}_{S}\Bigg{(}\forall\Sigma\in\mathfrak{L},\phi\in\Phi:\mathcal{L}(\Sigma,\phi)-\mathcal{L}_{N}(\Sigma,\phi)\leq\bar{R}(T,N,\delta)\Bigg{)}\geq
1-\delta.$

To this end, notice that according to the classical argument (e.g. see the
proof of Lemma 26.2 in (Shalev-Shwartz & Ben-David, 2014))

$\displaystyle G_{\mathfrak{L},\Phi}$
$\displaystyle:=E_{S}[\sup_{\Sigma\in\mathfrak{L},\phi\in\Phi}\mathcal{L}(\Sigma,\phi)-\mathcal{L}_{N}(\Sigma,\phi)]$
$\displaystyle\leq\frac{1}{N}E_{S,S^{{}^{\prime}}}[E_{\sigma_{i}\in\\{+1,-1\\}}[\sup_{\Sigma\in\mathfrak{L},\phi\in\Phi}\sum_{i=1}^{N}\sigma_{i}\left(\ell(y_{i},y_{\Sigma}(\mathbf{u}_{i},\phi(\mathbf{u}_{i}),T)-\right.\left.\ell(y_{i}^{{}^{\prime}},y_{\Sigma}(\mathbf{u}_{i}^{{}^{\prime}},\phi(\mathbf{u}_{i}^{{}^{\prime}}),T)\right)]$

where $\sigma_{i}$, $i=1,\ldots,N$ are i.i.d uniformly distributed and taking
values in $\\{-1,1\\}$, $S=\\{y_{i},\mathbf{u}(i)\\}_{i=1}^{N}$
$S=\\{y^{{}^{\prime}}_{i},\mathbf{u}^{{}^{\prime}}(i)\\}_{i=1}^{N}$ are
independent i.i.d. samples from $\mathcal{D}=(\mathcal{U},\mathcal{Y})$ Define

$\displaystyle
Z_{\phi}=\frac{1}{N}\sup_{\Sigma\in\mathfrak{L}}\sum_{i=1}^{N}\sigma_{i}(\ell(y_{i},y_{\Sigma}(\mathbf{u}_{i},\phi(\mathbf{u}_{i}),T)-\ell(y_{i},y_{\Sigma}(\mathbf{u}_{i}^{{}^{\prime}},\phi(\mathbf{u}_{i}^{{}^{\prime}}),T))$
$\displaystyle\mu_{\phi}=E_{\sigma_{i}\in\\{+1,-1\\}}[Z_{\phi}]$

If $\Phi$ is a finite set, then

$\displaystyle G_{\mathfrak{L},\Phi}\leq
E_{S,S^{{}^{\prime}}}E_{\sigma_{i}\in\\{+1,-1\\}}[\sup_{\phi\in\Phi}Z_{\phi}]\leq\mathrm{card}(\Phi)E_{S,S^{{}^{\prime}}}[\sup_{\phi}\mu_{\phi}]$

If $\Phi$ is not necessarily finite, then

$\displaystyle G_{\mathfrak{L},\Phi}\leq
E_{S,S^{{}^{\prime}}}E_{\sigma_{i}\in\\{+1,-1\\}}[\sup_{\phi\in\Phi}Z_{\phi}]\leq
E_{S,S^{{}^{\prime}}}E_{\sigma_{i}\in\\{+1,-1\\}}[\sup_{\phi\in\Phi}(Z_{\phi}-\mu_{\phi})]+E_{S,S^{{}^{\prime}}}[\sup_{\phi\in\Phi}\mu_{\phi}]$

Let $H_{\phi}=Z_{\phi}-\mu_{\phi}$. It then follows that
$E_{\sigma_{i}\in\\{+1,-1\\}}[Z_{\phi}-\mu_{\phi})]$ and
$|H_{\phi}|=|Z_{\phi}-\mu_{\phi}|\leq B$. Then by Hoeffding’s lemma
$P(|H_{\phi}\|>\rho)<2e^{-2\frac{\rho^{2}}{4B^{2}}}$ and hence by the union
bound $P(\sup_{\phi\in\Phi}|H_{\phi}\|>\rho)\leq
2\tau(2N)e^{-2\frac{\rho^{2}}{4B^{2}}}$, where

$\displaystyle\tau(2N)=\sup_{\\{\mathbf{u}_{i}\\}_{i=1}^{2N}\in
L_{2}([0,T],\mathbb{R}^{n_{u}})}|\\{(\mathbf{u}_{i},\phi(\mathbf{u}_{i}))\mid\phi\in\Phi\\}\|\leq(2eN/d_{T})^{d_{T}}$

Then by Lemma A.4 in (Shalev-Shwartz & Ben-David, 2014)

$\displaystyle
E_{\sigma_{i}\in\\{+1,-1\\}}[\sup_{\phi\in\Phi}(Z_{\phi}-\mu_{\phi})]\leq\sqrt{2}B(T)(2+\sqrt{\log(2eN/d_{T})d_{T}})$

As to $\sup_{\phi}\mu_{\phi}$, from standard theory of Rademacher complexity
and Lemma 4.3 it follows that

$\sup_{\phi}\mu_{\phi}\leq\frac{2K_{\ell}c_{1}(n_{p}+1)L_{\mathbf{u}}}{\sqrt{N}}$

That is, if $\Phi$ is finite, then

$G_{\mathfrak{L},\Phi}\leq
2\frac{\mathrm{card}(\Phi)2K_{\ell}c_{1}(n_{p}+1)L_{\mathbf{u}}}{\sqrt{N}}$

and otherwise,

$G_{\mathfrak{L},\Phi}\leq\sqrt{2}B(2+\sqrt{\log(2eN/d_{T})d_{T}})+\frac{2K_{\ell}c_{1}(n_{p}+1)L_{\mathbf{u}}}{\sqrt{N}}$

Applying McDiarmid inequality to $\sup_{\phi\in\Phi}Z_{\phi}$ the statement of
the theorem follows.