Generalization bounds for neural ordinary differential equations and deep residual networks
Authors: Pierre Marion
Venue: NeurIPS 2023 poster (2023)
Keywords: residual neural networks
neural ODEs
generalization bound
TL;DR: We provide generalization bounds for a class of neural ODEs and of deep residual networks.

Abstract: Neural ordinary differential equations (neural ODEs) are a popular family of continuous-depth deep learning models.  In this work, we consider a large family of parameterized ODEs with continuous-in-time parameters, which include time-dependent neural ODEs.  We derive a generalization bound for this class by a Lipschitz-based argument. By leveraging the analogy between neural ODEs and deep residual networks, our approach yields in particular a generalization bound for a class of deep residual networks. The bound involves the magnitude of the difference between successive weight matrices. We illustrate numerically how this quantity affects the generalization capability of neural networks.

Generalization bounds for neural ordinary differential equations and deep residual networks
Pierre Marion
Sorbonne Université, CNRS. Laboratoire de Probabilités. Statistique Modélisation, LPSM,
F-75005 Paris, France
pierre mar wwt.:e/maa.ooeeooooommmmmeeeees
Abstract
Neural ordinary differential equations (neural ODEs) are a popular family of continuous-depth deep learning models. In this work, we consider a large family parameterized ODEs with continuous-in-iin dependent neural ODEs. We derive a generalization bound for this class by a Lipschitz-based argument. By leveraging the analogy between neural ODEs and deep residual networks, our approach yields in particular generalization bound for class of deep residual networks. The bound involves the magnitude the difference between successive weight matrices. We illustrate numerically how this quantity affects the generalization capability of neural networks.
parameters, which include time-
Introduction
Neural ordinary differential equations (neural ODEs, Chen et al., 2018) are flexible family of neural networks used in particular model continuous-time phenomena. Along with variants such as neural stochastic differential equations (neural SDEs, Tzen and Raginsky, 2019) and neural controlled differential equations (Kidger et al., 2020), they have been used diverse fields such as pharmokinetics (Lu et al., 2021; Qian et al., 2021), finance (Gierjatowicz et al., 2020), and transportation (Zhou et al., 2021). We refer to Massaroli et al. (2020) for a self-contained introduction to this class of models.
Despite their empirical success, the statistical properties of neural ODEs have not yet been fully investigated. What is more, neural ODEs can be thought of as the infinite-depth limit of (properly scaled) residual neural networks (He al., 2016 a connection made by, e-g.. E (2017); Haber and Ruthotto (2017); Lu et al. (2017). Since standard measures of statistical complexity of neural networks grow with depth (see, e.g., Bartlett et al., 2019), it is unclear why infinite-depth models, including neural ODEs, should enjoy favorable generalization properties.
To better understand this phenomenon, our goal in this paper study the statistical properties of class of time- tmeedependentt neural ODEs that write
dH, = Wio (H,)dt
(1)
where We E d is weight matrix that depends on the time index t, and a RR + R is an activation function applied component-wise -eme-dependent neural ODEs were first introduced by Massaroli et al. (2020) and generalize line-independent neural ODEs
dH, = W (oooHHH)d
as formulated in Chen et al. (2018), where W E dddd now denotes weight matrix independent of f. There are two crucial reasons consider time-dependent neural ODEs rather than the more
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

restrictive class of time- indeeeeded neural ODEs. On the one hand, the time -eneeddenddent formulation more flexible, leading to competitive results on image classification tasks (Queiruga al., 2020, 2021). As a consequence, obtaining generalization guarantees for this family of models is a valuable endeavor by itself. On the other hand, time dependence is required for the correspondence with general residual neural networks to hold. More precisely, the time-dependent neural ODE (1) is the limit, when the depth L goes to infinity, of the deep residual network
Ha+1 H& + (Ha))(HH), 0 O
(3)
where (Wi)) 1kggr Raxd are weight matrices and is still an activation function. We refer to Marion et al. (2022, 2023); Sander et al. (202)); Thorpe and van Gennip (2022) for statements that make precise under what conditions and in which sense this limit holds, as well as its consequences for learning. These two key reasons compel us to consider the class of time-dependent ODEs (1) for our statistical study, which in turn will inform us on the properties of the models (2) and (3).
In fact, we extend our study to the larger class of parameterized ODEs, which we define as the mapping from Rd to the value at time t 1 of the solution of the initial value problem
Ho z. dH, Σ O.(O))(H))dd
(4)
where H, is the variable of the ODE, 0, are functions from [0, 1] into that parameterize the ODE, and fr are fixed functions from Rd into Rd. Time-dependent neural ODEs (I) are obtained by setting a specific entrywise form for the functions f; in (4).
Since the parameters 0g belong to basis of functions. For example, the residual neural networks (3) can
frfiitt-diimesioone space, in practice they need to be approxi-
mated in a unite-dimension be seen as an approximation of the neural ODEs (1) on piecewise-constant basis of function. But more complex choices are possible, such as B-splines (Yu et al., 2022). However, the formulation (4) is agnostic from the choice of fiite-dimensional approximation. This more abstract point of view is fruitful to derive generalization bounds, for at least two reasons. First, the statistical properties of the parameterized ODEs (4) only depend on the characteristics of the functions 0, and not on the specifics of the approximation scheme, so it is more natural and convenient to study them at the continuous level. Second, their properties can then be transferred to any specific discretization, such as the deep residual networks (3), resulting in generalization bounds for the latter.
Regarding the characteristics of the functions 6,, make the structural assumption that they Lipschitz-continuous and uniformly bounded. This is a natural assumption to ensure that the initial value problem (4) has unique solution in the usual sense of the Picard-Lindedd 1992). Remarkably, this assumption on the parameters also enables us to obtain statistical guarantees despite the fact that we are working with an infinite-dimensional set of parameters.
theorem (Amold,,
Contributions. We provide generalization bound for the large class of parameterized ODEs (4), which include time-dependent and time-independent neural ODEs (1) and (2). To the best of our knowledge, this is the first available bound for neural ODEs in supervised learning. By leveraging on the connection between (time-dependent) neural ODEs and deep residual networks, our approach allows us to provide a iepph-indeeendentt generalization bound for the class of deep residual net- works (3). The bound is precisely compared with earlier results. Our bound depends in particular on the magnitude of the difference between successive weight matrices, which is. to our knowledge. novel way of controlling the statistical complexity of neural networks. Numerical illustration provided to show the relationship between this quantity and the generalization ability of neural networks.
Organization of the paper. Section 2 presents additional related work. In Section 3, we specify our class of parameterized ODEs, before stating the generalization bound for this class and for neural ODEs as corollary. The generalization bound for residual networks is presented in Section 4 and compared to other bounds, before some numerical illustration. Section 5 concludes the paper. The proof technique is discussed in the main paper, but the core of the proofs is relegated to the Appendix.

---

2 Related work
Hybridizing deep learning and differential equations. The fields of deep learning and dynamical systems have recently benefied from sustained cross-fertiiization. On the one hand, a large line of work is aimed at modeling complex continuous-timm phenomena by developing specialized neural architectures. This family includes neural ODEs, but also et al., 2019), neural operators (Li et al., 2021) and neural flows (Biloš et al., 2021). On the other hand, successful recent advances in deep learning, such as diffusion models, are theoretically supported by ideas from differential equations (Huang et al., 2021).
informed neural networks (Raissi
Generalization for continuous-time neural networks. Obtaining statistical guarantees for continuous-time neural networks has been the topic of a few recent works. For example, Fer- manian et al. (2021) consider recurrent neural networks (RNNs), a family of neural networks handling time series, which is therefore a different setup from our work that focuses on vector-valued inputs. These authors show that a class of continuous-time RNNs can be written as input-driven ODEs, which are then proved to belong to a family of kernel methods, which entails generalization bound. Lim al. (2021) also show a generalization bound for ODF-like RNNs, and argue that adding stochasticity (that is, replacing ODEs with SDEs) helps with generalization. Taking another point of view, Yin et al. (2021) tackle the separate (although related) question of generalization when doing transfer learning across multiple environments. They propose a neural ODE model and provide a generalization bound in the case of linear activation function. Closer our setting, Hanson and Raginsky (2022) show a generalization bound for parameterized ODEs for manifold learning, which applies in particular for neural ODEs. Their proof technique bears similarities with ours, but the model and task differ from our approach. In particular, they consider stacked iime-independent parameterized ODEs, while we are interested in a time-dependent formulation. Furthermore, these authors do not discuss the connection with residual networks.
Lipschitz-based generalization bounds for deep neural networks. From a high-level perspective, our proof technique is similar to previous works (Bartlett et al., 2017: Neyshabur et al., 2018) that show generalization bounds for deep neural networks. which scale at most polynomially with depth. More precisely, these authors show that the network satisfies some Lipschitz continuity property (either with respect to the input or to the parameters), then exploit results on the statistical complexity of Lipschitz function classes. Under stronger norm constraints, these bounds can even be made depth- independent (Golowich et al., 2018). However, their approach differs from ours insofar as we consider neural ODEs and the associated family of deep neural networks, whereas they are solely interested in finite-depth neural networks. As a consequence, their hypotheses on the class of neural networks differ from ours. Section 4 develops a more thorough comparison. Similar Lipschitz- bapee techniques have also been applied to obtaín generalization bounds for deep equilibrium networks (Pabbaraju et al., 2021). Going beyond statistical guarantees, Béthune et al. (2022) study approximation and robustness properties of Lipschitz neural networks.
3 Generalization bounds for parameterized ODEs
We start by recalling the usual supervised learning setup and introduce some notation Section 1.1, before presenting our parameterized ODE model and the associated generalization bound in Sec- tion 3.2. We then apply the bound to the specific case of time-invariant neural ODEs in Section 3.3.
3.1 Learning procedure
We place ourselves in a supervised learning setting. Let us introduce the notation that are used throughout the paper (up to and including Section 4.1). The input data a sample of i.i.d. pairs (z,, V:) with the same distribution as some generic pair (z, y). where x (resp. y) takes its values in some bounded hall X' = (O, Rx)) (resp. y = B(0, Ry)) of Rdd, for some Rx, Ry > O. This setting encompasses regression but also classification tasks by (one-hot) encoding labels in Rd. Note that we assume for simplicity that the input and output have the same dimension, but our analysis easily extends to the case where they have different dimensions by adding (parameterized) projections at the beginning or at the end of our model. Given parameterized class of models Fe (Fe. A E θ).
the parameter 0 is fitted by empirical risk minimization using loss function E: _d x R + R that
3

---

we assume to be Lipschitz with respect to its first argument, with a Lipschitz constant K 0. In the following, we write for the sake of concision that such function is Kz-Lisschitz. We also assume that {(r, ..) = 0 for all x E R.d The theoretical and empirical risks are respectively defined, for any 0 E e by
" = Σ (Fo
20 B[((Fo()),)) vll and (n)
where the expectation E is evaluated with respect to the distribution of (zz y). Letting 0, minimizer of the empirical risk, the generalization problem consists in providing an upper bound on the difference A (0n) Rt (6x).
3.2 Generalization bound
Model. We start by making more precise the parameterized ODE model introduced in Section 1. The setup presented here can easily be specialized the case of neural ODEs, as we will see in Section 3.3. Let fi,..., Sn. RRd -> Rd be fixed y--Lipschitz functions for some K 0. Denote by M their supremum on X' (which finite since these functions are continuous). The parameterized ODE Fg is defined by the following initial value problem that maps some E IRd to (x(x) RR:
Ho
d.H, Σ 1=1
O,(1).(H))ddt
(5)
Fe(x)= H1.
where the parameter 0 (01..... fm) is function from [0, R" We have to impose constraints on 0 for the model Fg to be well-defined. To this aim, we endow (essentially bounded) functions from [0, to I with the following (1, -noor
1011,,00
sup 0
(((t)|-
(6)
We can now define the set of parameters
+ (0: [0. RM, 110|1,,0 & Re and 0, is Ko-Lipschitz for i {1....., m}},
for some Re > and Ke > Then, for E O, the following Proposition, which is consequence of the Picard-Lindelöf Theorem, shows that the mapping x + (x(x) is well-defined.
Proposition 1 (Well-posedness of the parameterized ODE). For e O and æ E Rd, there exists unique solution to the initial value problem (5).
An immediate consequence of Proposition is that is legitimate to consider Fe = (Fo, 0 E {} for model class.
When Ke 0. the parameter space is dimens-ammniional since each 9; is constant. This setting corresponds to the time-independent neural ODEs of Chen et al. (2018). In this case, the norm (6) reduces to the || || norm over R Note that, to exactly the formulation of Chen et al. (2018), the time can be added as variable of the functions fi, which amounts to adding new coordinate to H,- This does not change the subsequent analysis. In the richer time-dependent case where Ke > the set θ belongs to a finite basis of functions, such as Fourier series, Chebyshev polynomials, and splines. We refer to Massaroli et al. (2020) for more detailed discussion. including formulations of the backpropagation algorithm (a.k.a the adjoint method) in this setting.
space and therefore, in practice, 0 is approximated in
Note that we consider the case where the dynamics at time are linear with respect to the param- eter (t). Nevertheless, we emphasize that the mapping æ +> Fo(x) remains a highly non-linear function of each (C). To fix ideas, this setting can be seen as analogue to working with pre-activation residual networks instead of post-activation (see He al., 6b, for definitions of the terminology), which is mild modification.

---

Statistical analysis Since θ is subset of an Sriinit-dimmnsiione space, complexity measures based on the number of parameters cannot be used. Instead, our approach to resort Lipschitz- based complexity measures. More precisely, to bound the complexity of our model class, we propose two building blocks: we first show that the model F6 is Lipschitz-continuuus with respect to its parameters 0. This allows us to bound the complexity of the model class depending on the complexity of the parameter class. In second step, we assess the complexity of the class parameters itself.
Starting with our first step, we show the following estimates for our class of parameterized ODEs. Here and in the following, || denotes the & norm over R.
Proposition 2 (The parameterized ODE is bounded and Lipschitz). Let 0 and 0 E e. Then, for any E X.
[Fo())] & Rx + Me exp( K Re)
and
Fy(=)l < 2MK, x
0111.0..
The proof, given in the Appendix, makes extensive use of Grönwall's inequality (Pachpatte and Ames, 1997), a standard tool to obtain estimates in the theory of ODEs, in order to bound the magnitude of the solution H2 of (5).
The next step is to assess the magnitude of the covering number of O. Recall that, for E > 0, the e-covering number of a metric space is the number of balls of radius needed to completely cover the space, with possible overlaps. More formally, considering a metric space Al and denoting by ( e) the ball of radius centered at E M, the e-covering number of Al is equal to (n > [[rr,,..,, In E M. M C C B(x;, e)
Proposition (Covering number of the ODE parameter class). For O, let ((e) be the e-covering number of θ endowed with the distance associated to the (1, norm (6). Then
log lo) & m log (16mRe)
m Ke log(4)
Proposition 3 is consequence of a classical result, see, e.g., Kolmogorov and Tikhomirov (1959, example 3 of paragraph 2). A self-contained proof is given in the Appendix for completeness, We also refer Gottlieb et al. (2017) for more general results on covering numbers of Lipschitz functions.
The two propositions above and an E-net argument allow to prove the first main result of our paper (where we recall that the notations defined in Section 3.1).
Theorem (Generalization bound for parameterized ODEs). Consider the class of parameterized ODEs Fe {Fa, 8 E θ}. where Fg given by (5) and by (7). Let
Then, for n > 9
1), with probability at least 1 5,
* ( & (0.) + BV (m + 1) log( Remm)
/y/e + 1/4
1
V log
log
Vn
where a constant depending on K₁, K,, RØ Rx, Roy, M. More precisely, B K ( Re) Rx Re x Ry).
Three terms appear in our upper bound of -0m))
- En (see, e.g. Bach, 2023, Sections 4.4 and 4.5). On the contrary, the second term more surprising with its convergence rate in On This slower convergence rate is due to the fact that the space of parameters is infinitediimensional. In particular, for Ke = O, corresponding to a finite- dimensional space of parameters, we recover the usual (n22) convergence rate, however at the cost of considering much more restrictive class of models. Finally, it is noteworthy that the dimensionality appearing in the bound is not the input dimension d but the number of mappings m.
The first and the third ones are classical
Note that this result is general and may be applied in a number of contexts that go beyond deep learning, as long as the instantaneous dependence of the ODE dynamics to the parameters is linear. One such example is the predator-pee pprtt model, describing the evolution of two populations of animals, which reads dr, = aa Byy )dl and dyt - (7 8x;, )dl, where 2; and yt are real-valued variables and 3, 7 and 6 are model parameters. This ODE falls into the framework of this section,
5

---

if one were to estimate the parameters by empirical risk minimization. We refer to Deufthard and Röblitz (2015, section for other examples of parameterized biological ODE dynamics and methods for parameter identification.
Nevertheless, for the sake of brevity, focus applications of this result to deep learning, and more precisely to neural ODEs, which is the topic of the next section.
3.3 Application to neural ODEs
As explained in Section 1, parameterized ODEs include both dime-dependent and time-independent neural ODEs. Since the time- imme-independent model is more common in practice, we develop this case here and leave the time-dependent case to the reader. We thus consider the following neural ODE:
Ho dHl, Wo
(x) = H1.
where W E Rdxd is weight matrix, and IR + R is an activation function applied component- wise. We assume be Ko-Lipschitz for some K₂ > 0. This assumption satisfied by all common activation functions. To put the model in the form of Section 3.2, denote e1,..., the canonical basis of Rd. Then the dynamics (8) can reformulated as
dH, Σ Woyot(Hiidtt f5=1
where (x) = (sy))s. Each oi is itself Ko-Lipschitz, hence we fall in the framework of Section 3.2. In other words, the functions fi of our general parameterized ODE model form shallow neural network with pre-activation. Denote by ||W][1,1 the sum the absolute values the elements of W. We consider the following set of parameters, which echoes the θ of Section 3.2:
W ( Raddd ||Wl,,, & Rw).
for some Rw > O. We can then state the following result as a consequence of Theorem 1. Corollary (Generalization bound for neural ODEs). Consider the class of neural ODEs Fw (Fw, W E W}, where Fw is given by (8) and W by (9). Let 5 >
Then, for n 2 9Ry' max(d Rwy 2, 1), with probability at least - 8,
log(Rwdts (wwdn)
B
1 8 log
((..) < R. (w,) + B(d+
Vn
n
where a constunt depending on Ke, Ko, Rw, Rx, Ry, M. More precisely,
B= B=6v2KeK, exp( K2 ( + MBw exp(K, + Ry).
Note that the term in (n-1//) from Theorem is now absent. Since we consider a iime-independent model, we are left with the other two terms, recovering a standard O(n -1/2) convergence rate.
Generalization bounds for deep residual networks
As highlighted in Section 1, there is a strong connection between neural ODEs and discrete residual neural networks. The previous study of the continuous case in Section 3 paves the way for deriving generalization bound in the discrete setting of residual neural networks, which of great interest given the pervasiveness of this architecture in modern deep learning.
We begin by presenting our model and result Section 4.1, 1, before detailing the comparison of our approach with other papers in Section 4.2 and giving some numerical illustration in Section 4.3.

---

4.1 Model and generalization bound
Model. We consider the following class of deep residual networks:
Hu =
Hk+1 = H₂ + 1
L (Hx)) O
(10)
Fw (x: = HI.
where the parameter W = (WE)LENEL E RLxdxd set of weight matrices and a still a Ka-Lipschitz activation function. To emphasize that W is here third-order tensor, as opposed to the case of time-invariant neural ODEs in Section 3.3, where W was a matrix, we denote with a bold notation. We also assume in the following that ø (0) O. This assumption could be alleviated at the cost of additional technicalities. Owing to the 1/2 scaling factor, the deep limit of this residual network is (time-dependent) neural ODE of the form studied in Section 3. We refer Marion et al. (2022) for further discussion on the link between scaling factors and deep limits. We simply note that this scaling factor is not common practice, but preliminary experiments show it does not hurt performance and can even improve performance in a weight-tied setting (Sander et al., 2022). The space of parameters is endowed with the following (1, 1, )n)-morm
W 1 = sup Σ Weatl I 1,
(11)
Also denoting || Il the wise maximum norm for a matrix, we consider the class of matrices
W w R Lxxxdd | & Rw and
(12)
Kw W - Wa & L
for 1< 1
for some Rlw > 0 and Kw 2 0, which is a discrete analogue of the set & defined by (7).
In particular, the upper bound on the difference between successive weight matrices is to our knowledge novel way of constraining the parameters of neural network. It corresponds to the discretization of the Lipschitz continuity of the parameters introduced in (7). By analogy, we refer it as a constraint on the Lipschitz constant of the weights. Note that, for standard initialization schemes, the difference between two successive matrices is of the order (1)) and not O(1/L), or, in other words, Kw scales as (T)). This dependence of Kw on can be lifted by adding correlations across layers at initialization. For instance, one can take, for k E {1...., L.} and i, E (1.....d}, Wk.,, fi, where fi, is smooth function, for example a Gaussian process with the RBF kernel. Such non-i.i.d. initialization scheme is necessary for the correspondence between deep residual networks and neural ODEs to hold (Marion et al., 2022). Furthermore, Sander et al. (2022) prove that, with this initialization scheme, the constraint trained network, with Kw independent of L. Finally, we emphasize that the following developments also hold in the case where Kw depends on L (see also Section 4.2 for related discussion).
the Lipschitz constant also holds for the
Statistical analysis. At first sight, a reasonable strategy would be to bound the distance between the model (10) and its limit L - oo that is parameterized ODE, then apply Theorem 1. This strategy is straightforward, but comes at the cost of an additional (1/LL) term in the generalization bound, as a consequence of the discretization error between the discrete iterations (10) and their continuous limit. For example, we refer to Fermanian et al. (2021) where this strategy is used to prove a generalization bound for discrete RNNs and where this additional error term is incurred. We follow another way by mimicking all the proof with a finite L. This is a longer approach but it yields a sharper result since we avoid the ((1LL) discretization error. The proof structure is similar to Section 3: the following two Propositions are the discrete counterparts of Propositions 2 and 3.
Proposition 4 (The residual network is bounded and Lipschitz). Let W and W E W. Then, for any X.
[Fw(x)] < Rx exp(K,
and
Rx Rw
Fw (z) - Fw(x)) <
exp(2K, Rw) W - -Wl111.
7

---

Proposition (Covering number of the residual network parameter class), Let (E)) be the covering number of W endowed with the distance associated to the (1)1,00)-nomm (11). Then
logN(s)) & dl log (1 Rw
d Kw log(4)
The proof of Proposition is discrete analogous of Proposition 2. On the other hand, Proposition can be proven as consequence of Proposition 3, by showing the existence of an injective isometry from W into set of the form (7). Equipped with these two propositions, we are now ready state the generalization bound for our class of residual neural networks.
Theorem 2 (Generalization bound for deep residual networks). Consider the class of neural networks Fw (Fw, W E W), where Fw is given by (10) and W by (12). Let 8 0.
Then, n > 9Rw max(d -Rw 1), with probability at least 1 - 5,
log (RwdR))
d VKW
B
1 8'
2 W Ln W + B(d 1)v
B
log
(13)
1//4
Vn
where a constant depending on Ke; Ko, Rw, Rx, Ry. More precisely,
(exp(Ka Rw) 1)) (Rx exp(Kx, + Ry).
B B max
Rww
We emphasize that this result is non-asymptotic and valid for any width d and depth L. Furthermore, the depth L does not appear in the upper bound (13). This should not surprise the reader since Theorem can be seen as the deep limit - oo of this result, hence we expect that our bound remains finite when L -> oo (otherwise the bound of Theorem 1 would be infinite). However, I appears scaling factor in the definition of the neural network (10) and of the class of parameters (12). This is will comment further on in the next section.
crucial for the depth independence to hold,
Furthermore, the depth independence comes at the price of a O( convergence rate. Note that, by taking Kw we obtain a generalization bound for weight-tied neural networks with a faster convergence rate in since the term in Onn-1/1) vanishes.
4.2 Comparison with other bounds
As announced Section 2, we now compare Theorem 2 with the results of Bartlett et al. (2017) and Golowich et al. (2018). Beginning by Bartlett et al. (2017), we first state slightly weaker version of their result to match our notations and facilitate comparison.
Corollary 2 (corollary of Theorem 1.1 of Bartlett et al. (2017)). Consider the class of neural networks Fw = (Fw. W E W), where Fw is given by (10) and W (W E RLxxxd (WI,,,,s & Rw)- Assume that L 3 Rw and K, = 1, and let 7, 8 > 0. Consider (z,, v), (21, y2),..., (Ins Vn) drawn i..d. from any probability distribution over Rd [l,...d} such that a.s. ||a||| < Rx.
Then, with probability at least for every W W.
P arg max Fw (x)1 + < (. + C Rx Rw exp( Rw) log(d)VL. LEjEd
1o8 V (14)
C vn
where (W) wn Σi= (a;)), max f(z,) and C is universal constant.
We first note that the setting is slightly different from ours: they consider large margin predictor for loss f. This
a multi-class classification problem, whereas we consider a general Lipschitz being said, the model class is identical ours, except for one notable difference: the constraint the Lipschitz constant of the weights appearing in equation (12) not required here.
Comparing (13) and (14), we see that our bound enjoys better dependence on the depth L but a worse dependence on the width d. Regarding the depth, our bound (13) does not depend on L, whereas the bound (14) scales as O(VT). This comes from the fact that we consider a smaller set of parameters (12), by adding the constraint on the Lipschitz norm of the weights. This constraint

---

allows us to control the complexity of our class of neural networks independently of depth, as long as Kw is independent of L. If Kw scales as O(L). which the case for i.i.d. initialization schemes, our result also features scaling in (V)L). As for the width, Bartlett et al. (2017) achieve better dependence by a subtle covering numbers argument that takes into account the geometry induced by matrix norms, Since our paper focuses on a depth-wise analysis by leveraging the similarity between residual networks and their infinite- depth counterpart, improving the scaling of our bound with width left for future work. Finally, note that both bounds have a similar exponential dependence in Ry-
As for Golowich et al. (2018), they consider non-residual neural networks of the form M MM o (Mær))) These authors show that the generalization error of this class scales as
ORE
1F log
(Rx
1/4
where 1 is an upper-bound on the product of the Frobenius norms I || F and TT is lower-bound on the product of the spectral norms Ih [|M&]]. Under the assumption that both I and Hr/zs are bounded independently of L, their bound is indeed hypth-inddeendent, similarly to ours. Interestingly, as ours, the bound presents a ((nn1//1 convergence rate instead of the more However, the assumption that Hr is bounded independently of L does not hold in our residual setting, since we have M I+ + We and thus we can lower-bound
usual
L II k=1
II (14I1=-1IMM 1IMM)l+) > (Vd Rw Th x "
die
L
In our setting, it is totally different assumption, the constraint that successive weight matrices should be close to one another, which allows us to derive depth-indepen intbeeddddeednnt bounds.
4.3 Numerical illustration
The bound of Theorem 2 features two quantities that depend the class of neural networks, namely Ry that bounds a norm of the weight matrices and Kw that bounds the maximum difference between two successive weight matrices, i.e. the Lipschitz constant of the weights. The first one be- longs to the larger class of norm-based bounds that has been extensively studied (see, e.g., Neyshabur al., 2015). We are therefore interested in getting better understanding of the role of the second quantity, which is much less common, in the generalization ability of deep residual networks.
To this aim, train deep residual networks (10) (of width d 30 and depth L 1000) on MNIST. We prepend the network with an initial weight matrix to project the data æ from dimension 768 to dimension 30, and similarly postpend it with another matrix to project the output Fw (I:) into dimension 10 (i.e. the number of classes in MNIST). Finally, we consider two training settings: either the initial and final matrices are trained, they fixed random projections. We use the initialization scheme outlined in Section 4.1. Further experimental details are postponed to the Appendix.
We report in Figure la the generalization gap of the trained networks, that is, the difference between the test and train errors (in terms of cross entropy loss), as a function of the maximum Lipschitz constant of the weights supog&&L (|] k+1 oo We observe a positive correlation between these two quantities. To further analyze the relationship between the Lipschitz constant of the weights
and the generalization gap. we then add the penalization term X (Eto || Wx 1/2 to the loss, for some X > 0. The obtained generalization gap is reported in Figure 1b as a function of x. We observe that this penalization allows reduce the generalization gap. These two observations go in support of the fact that a smaller Lipschitz constant improves the generalization power of deep residual networks, in accordance with Theorem
However, note that we were not able to obtain an improvement on the test loss by adding the penalization term. This is not all too surprising since previous work has investigated related penalization, in terms of the Lipschitz norm of the layer sequence (Hx)ogket, and was similarly not able to report any improvement on the test loss (Kelly et al., 2020).
Finally, the proposed penalization term slightly departs from the theory that involves suPoEkEL-1( ([[We+ W)lloo). This is because the maximum norm is too irregular to be used

---

0.4
Trained projections
Random projections
0.3
0.125
Generalization gap
Generalization gap
0.100
0.070
0.0
0.050
-0.1
0.025
0.000
-0.
-0.025
0.75
1.25
0.0
0.01 0.1
SuPasAsA-1 We-1
Welloo)
(a) Generalization gap function of the maximum Lipschitz constant the weights. Each dot corresponds to a network trained with a varying number of epochs (between and 30).
(b) Generalization gap function of the penalization factor experiment is repeated 20 times each value of x. Each time, the network is trained for 50 epochs. The initial and final matrices are random. The value
corresponds weight tied network.
Figure I: Link between the generalization gap and the Lipschitz constant of the weights.
in practice since, any one step of gradient descent, it only impacts the maximum weights and not the others. As illustration, Figure 2 shows the generalization gap when penalizing with the maximum max-norm suppę*
(I|W (- k+1
&x and the L2 norm the max-norm
(Ek- | - ) 1/2 The factor is scaled appropriately to reflect the scale difference of the penalizations. The results are mixed: the L2 norm of the max-norm is effective contrarily the maximum max-norm. Further investigation of the properties of these norms is left for future work.
0.15
0.150
0.125
Generalization gop
Generalization gap
0.13
0.100
0.12
0.075
0.11
0.050
0.10
0.025
0.000
1.0
0.0
1.0
(a) Penalizing by the maximum max-norm.
(b) Penalizing by the L2 norm of the max-norm.
Figure Generalization gap as a function of the penalization factor for other penalizations.
5 Conclusion
We provide generalization bound that applies to a wide range of parameterized ODEs. As consequence, we obtain the first generalization bounds for time-independent and time-dependent neural ODEs in supervised learning tasks. By discretizing our reasoning, we also provide bound for class of deep residual networks. Understanding the approximation and optimization properties of this class of neural networks is left for future work. Another intriguing extension is to relax the assumption linearity the dynamics at time / with respect to 0c(1), that is, to consider general formulation dH, = Em fe( H,, (()). In the future, it should also be interesting to extend our results to the more involved case of neural SDEs, which have also been found be deep limits of large class of residual neural networks (Cohen et al., 2021: Marion et al., 2022).
10

---

Acknowledgments and Disclosure of Funding
The author is supported by grant from Région (le-de-France, by Google PhD Fellowship. and by MINES Paris PSL. The author thanks Eloise Berthier, Gérard Biau, Adeline Fermanian, Clément Mantoux, and Jean-Philippe Vert for inspiring discussions, thorough proofreading and suggestions on this paper.
References
V. Arnold Ordinary Differential Equations. Springer Textbook. Springer Berlin Heidelberg, 1992.
Bach. Learning theory from first principles, 2023. Book draft. URL: https://w/it ens fr/ "fbach/Itfpp maacch/ttp_booot book. pdf (version: 2023-02-05).
L. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-normalizee margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
P. L.. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight VC-dimension and pseudodimen- sion bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63): 1-17, 2019.
L. Béthune, T. Boissin, M. Serrurier, F. Mamalet, C. Friedrich, and G. Sanz. Pay attention your loss: : understanding misconceptions about lipschitz neural networks. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
M. Biloš, J. Sommer, S. S. Rangapuram, T. Januschowski, and S. Günnemann. Neural flows: Efficient alternative to neural ODEs. M. Ranzato, A. Beygelzimer, Y. Dauphin, S. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. K. Duvenaud. Neural ordinary differential equations. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
A.-S. Cohen, R. Cont, A. Rossier, and R. Xu. Scaling properties of deep residual networks. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139, pages 2039-2048. PMLR, 2021.
P. Deuflhard and S. Röblitz. Parameter identification in ODE models. In A Guide to Numerical Modelling in Systems Biology, pages 138. Springer International Publishing, 2015.
W. F. A proposal on machine learning via dynamical systems. Communications Mathematics and Statistics, 5(1): 11, 2017. ISSN 2194-671X.
A. Fermanian, P. Marion, J.-P. Vert, and G. Biau. Framing RNN as a kernel method: A neural ODE approach. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
P. Gierjatowicz, M. Sahate-Vidales, D. Šiška, I. Szpruch, and 7. Zurič. Robust pricing and hedging via neural sdes. arXiv preprint vrXiv:2007.04154 2020.
N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research. PMLR, 2018.
L.A. Gottlieb A. Kontorovich, and R. Krauthgamer. Efficient regression in metric spaces via approximate lipschitz extension. JEFE Transactions on Information Theory, 63(8):4838-488 4849, 2017.
11

---

E. Haber and L. Ruthotto. Stable architectures for deep neural networks. Inverse problems. 34(1): 014004, 2017.
Hanson and M. Raginsky. Fitting an immersed submanifold to data via sussmann's 's orbit theorem. In 2022 IEEE 61st Conference Decision and Control (CDC), pages 5323-5328, 2022.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 20/6 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016a.
K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. In B. Leibe, Matas, N. Sebe, and M. Welling, editors, Computer Vision ECCV 2016, pages 630-645. Springer International Publishing, 2016b.
C.-W. Huang. J. H. Lim, and A. C. Courville. A variational perspective on diffusion-based generative models and score matching. In M. Ranzato, A. Beygelzimer, Dauphin, S. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
J. Kelly, J. Bettencourt, M. J. Johnson, and D. K. Duvenaud. Learning differential equations that easy solve. In H. Larochllle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33. Curran Associates, Inc., 2020.
P. Kidger, J. Morrill, J. Foster, and T. Lyons. Neural controlled differential equations for irregular time series. H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, Curran Associates, Inc., 2020.
D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR), 2015.
A. Kolmogorov and Tikhomirov. e-entropy and E-capacity of sets in functional spaces. Uspekhi Mat. Nauk, 14:3-86, 1959.
Z. Li, N. B. Kovachki, K. Azizzadenesheli, B. liu, K. Bhattacharya, A. Stuart, and A. Anandkumar. Fourier neural operator for parametric partial differential equations. In International Conference on Learning Representations, 2021.
H. Lim, N. B. Erichson, I.. Hodgkinson, and M. W. Mahoney. Noisy recurrent neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
J. Lu, K. Deng, X. Zhang, G. Liu, and Y. Guan. Neural-ODE for pharmacokinetics modeling and its advantage alternative machine learning models in predicting new dosing regimens. iScience, 24 (7):102804, 2021.
Y. Lu, A. Zhong, Q. Li, and B. Dong. Beyond finite layer neural networks: Bridging deep architectures and numerical differential equations. arXiv preprint arXiv: 1710. 2017.
Luk. Notes on existence and uniqueness theorems for ODEs, 2017. URL: http: // /web. stanf edu/"jluke wwlukmamtth3oMsprinnggoom htt.:///sppiing/////itttentoooo /ttp///xxxttteeeeeeeeeeeeeeeeeee 170408 pdf (version: 2023-01-19).
P. Marion, A. Fermanian, G. Biau, and J.-P. Vert. Scaling ResNets in the large-depth regime, arXiv preprint arXiv:2206.08 06929, 2022.
Marion, Y.H. WU, M. E. Sander, and B. Gérard. Implicit regularization of deep residual networks towards neural odes. arXiv preprint wxXiv:2309002/13 2023.
S. Massaroli, M. Poli, J. Park, A. Yamashita, and H. Asama. Dissecting neural ODEs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33. Curran Associates, Inc., 2020.
B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control neural networks. In
P. Grünwald, E. Hazan, and S. Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1376-1401, Paris, France, 03 06- Jul 2015. PMLR.
12

---

B. Neyshabur, S. Bhojanapalli, and N. Srebro. A PAC-bayesian approach to pecctraly-normallie margin bounds for neural networks. International Conference on Learning Representations. 2018.
C. Pabbaraju, E. Winston, and J. Z. Kolter. Estimating lipschitz constants of monotone deep equilibrium models. In International Conference on Learning Representations, 2021.
B. G. Pachpatte and W. Ames. Inequalities for Differential and Integral Equations. Elsevier, 1997.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, 7. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf. E. Yang, Z. Vito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Z. Qian, W. Zame, L. Fleuren, P. Elbers, and M. van der Schaar. Integrating expert ODEs into neural ODEs: Pharmacology and disease progression. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. W. Vaughan, editors, Advances Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
A. F. Queiruga, N. B. Erichson, D. Taylor, and M. W. Mahoney. Continuous-in-depth neural networks. arXiv preprint wxXiv2208.002350 2020.
A. F. Queiruga, N. B. Erichson, L. Hodgkinson, and M. W. Mahoney. Stateful ODE-nets using basis function expansions. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, Curran Associates, Inc., 2021.
M. Raissi, P. Perdikaris, and G. E. Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378:686-707, 2019.
M. E. Sander, P. Ablin, and G. Peyré. Do residual neural networks discretize neural ordinary differen- tial equations? In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
M. Thorpe and Y. van Gennip. Deep limits of residual neural networks. Research in the Mathematical Sciences, 10(1):6, 2022.
B. Tzen and M. Raginsky. Neural stochastic differential equations: Deep latent gaussian models in the diffusion limit. arXiv preprint arXiv: arXiv:1905.09883, 2019.
M. J. Wainwright. High-Diieensonal Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
Y. Yin, I. Ayed, E. de Bézenac, N. Baskiotis, and P. Gallinari. LEADS: Learning dynamical systems that generalize across environments. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
D. Yu, H. Miao, and H. Wu. Neural generalized ordinary differential equations with layer-varying parameters. arXiv preprint arXiv:2209. 1063333309.10033,, 20033,20221 2022.
F. Zhou, L. Li, K. Zhang, and G. Trajcevski. Urban flow prediction with spatial-tempol temporal neural ODEs. Trunsportation Research Part C: Emerging Technologies, 124:102912. 2021.
13

---

Appendix
Organization the Appendix Section A contains the proofs of the results of the main paper.
Section B contains the details of the numerical illustrations presented in Section 4.3.
A Proofs
A.1 Proof of Proposition 1
The function
m (t, Σ (.0))(()))
is locally hipschitz-continuuw with respect to its first variable and globally Lipschitz-continuour with respect to its second variable. Therefore, the existence and uniqueness of the solution of the initial value problem (5) for > 0 comes consequence of the Picard-Lindele theorem (see, e.g.. Luk, 2017 for a self-contained presentation and Arnold, 1992 for textbook).
A.2 Proof of Proposition 2
For E X, let H be the solution of the initial value problem (5) with parameter & and with the initial condition Hg x. Let us first upper-bound (H,))l for all E {1....,m) and >> To this aim, for > O, we have
m
He Holl
Σ
m
(: lds -/> m
(0(())]1[((I1)))) fi(Ho)llds
< M (s(s)lds + K3 ( ( Holl Σ (,(5)))
ds
1=1
LM K2 Re /' |H, Hollds.
Next, Grönwall's inequality yields, for E [0.
||, Holl < LM Roy exp(IK Re) & M Me exp(Ky
Hence
[1,1| & |oo + |11, - Holl < Rx + MR yielding the first result of the proposition. Furthermore, for any (1....,m)) m).
(H,(())II < (IA(H) - f((H))ll + [[A(H))) < (M, exp Ro) +1) =: C.
Now, let A be the solution of the initial value problem (5) with another parameter and with the same initial condition Ho x. Then, for any L > 0.
H. il, = 1 m
m
(H.))
Σ
14

---

Hence
Hr Hell = -11 Σ (0((s) ((ss) ["- Th
((s))(((HH)) - ft.H)))ds
1=1
" Σ
(0(s)) [.()))]] J' (
Σ (s(s) (f(s)]ll((HH))ll KK S/" (1 Hell Σ (c(s)) ds
MR
< 1C i 11,00 + KyKK, / ||,, - Hallds.
Then Grönwall's inequality implies that, for E 1).
H H.l & tC| 1, exp(tK Ra)
< M (K Re expl exp(K K Re)) + exp( 1
< y Re (xp(2K Re) 10 0 1,00
since < Ry exp(K) K Rg) because j > 1, Re >
A.3 Proof of Proposition? 3
We first prove the result for m = 1. Let G. be an E/ e/2K of [0, 1] and Gy an e/2-grid of [- Re: Re]. Formally, we can take
{
ke <
2Ke and G - Rs
ky
4R
G
2
Our cover consists of all functions that start at point of Gy, are piecewise linear with kinks in Ga. where each piece has slope Ke -Ke. Hence our cover is of size
Wi(e) |Gyl2/c.ll 4Re 2
+2
16Re
4 Ka
Now take function f : [0, 1] R that is uniformly bounded by Re and Ke-Lipschitz. We construct a cover member at distance e from f as follows. Choose point in G, at distance at most 2/2 from (0). Since f(0) E [RRe, Re). this is clearly possible, except perhaps the end of the interval. To verify that it is possible at the end of the interval, note that Re is at distance less than e/2 of the last element of the grid, since
Re (-Ro+ 4Re -
2R 4Re
4R - [R
-
2R
2
E 2
Then, among the cover members that start at yo. choose the one which is closest to f at each point of G2 (in case of equality, pick any one). Let denote this cover member as f. Let us show recursively that ff is at -distanne most from More precisely, let first show by induction on k that for all & E {O..... 2Ka
KE ((kee)
ke 2K
f(
f(
(15)
2K
First, [S(0) f(0) < Then, assume that (15) holds for some Then we have the following inequalities:
kE 2Kg
KE E - < f(
(by induction)
2Kg
2
(k + 1)E
< f(
(f is Kg-Lipschitz)
2k
hs
f( 2Kg
) +
(f is Kg-Lipschitz)
2
ke
+
(by induction).
2K
15

---

Moreover, by definition, f( is the closest point to f among
(
{
ks 6 Ke
ks Ke
2
2
The bounds above show that, among those two points, least one is at distance more than 8/2 from f( ((++1))). This shows (15) at rank k + 1.
Ke
To conclude, take now [0, 1]. There exists k {O..... ..... e/ e/4Ke from ke_ Again, this is clear except perhaps the end of the interval, where it also true since
2K }} such that æ is at distance at most
2Kg
2K
2K E
<
0,
2Ke
2K
meaning that is located between elements of the grid Gz. showing that it is at distance most e/ from one element of the grid. Then, we have
If(x) f(x) < f(x) - 2Kg
((2Kg ke
kε 5(
2Kg ) -
)|+ 2Kg -(2ke)
ke f(
[(2kg)
Kε
F(x))
8
2 4'
where the first and third terms are upper-bounded because f and f are Ke-Lip, while the second term is upper bounded by (15). Hence |l fl proving the result for m 1.
Finally, to prove the result for general m, note that the Cartesian product e/m-covers for each coordinate of 0 gives an e-cover for 0. Indeed, consider such covers and take 0 E θ. Since each coordinate of uniformly bounded by Re and Key-Lipschitz, the proof above shows the existence of cover member such that, for all i E (l,...,m,, |10, - 0,1100 < s/m. Then
|0 10
sup 10((1) - 0.(1) < sup o 1=1
10: - 0:1lo E.
As consequence, we conclude that
N(s) < (M)( m
(16mRg) m m²Ko
Taking the logarithm yields the result.
A.4 Proof of Theorem
First note that, for any O X and y E V.
(((Fo()). < [((F(()) v) - Ely, w)1 + [((,,w] < KellPa(x) =ll. since, by assumption, l is Kę-Lipschitz with respect its first variable and Ely. v) 0. Thus
(((Fo(z) v)1 & (=)) + lIvll) < Kr (R + M Ri RR) Ry) =: M
by Proposition 2.
Now, taking > 0, classical computation involving McDiarmid's inequality (see, e.g., Wainwright, 2019, proof of thm 4.10) yields that, with probability least 1 ō,
MV2 1 Vn
2(O.) (O.)) + E sup
(0) o0e
(01)
V log
Denote C' 22M, (2K(2K Re). Then we show that H and En CKe-Lipschiz with respect -11,,-)) for 0,0 O
(0) (0) < ([(((Fo(z))))) (
< (((()) - Fb(x)]l]
< CK2 0 - -01 1,00
16

---

according to Proposition 2.
The proof for the empirical risk is very similar.
Let now e and (e) be the covering number of θ endowed with the (1, o0)-orm. By Proposi- tion 3,
16mRo m2 Ke log(4)
lo) & m log
Take ((1), ,..., element at distance at most from 0,
, ((M())) the associated cover elements. Then, for any A E O denoting ((+) the cover
[S((0) Rnn (0) < (0) 38 (B(0)) + (3((0()))
L. (0(0)) (0(()))) L (0)
(0)
< 2CK,s +
sup
(8(0()) 2n (0()))
xE ((e))..N((e)))
Hence
E
sup 8E8
(0) (00)
2CK +
sup ((())...NN(E))
((0 R, (0(0))
Recall that real-valued random variable X is said to be 5² sub-Gaussian (Bach, 2023, Section 1.2.1) for all E R. E(exp(A(XX (X((X((X)))) < ex)((>"'/2). Since (0) is the average of independent random variables, which are each almost surely bounded by M, it is M² /n sub-Gaussian, hence we have the classical inequality on the expectation of the maximum of sub-Gaussian random variables (see, e.g., Bach, 2023, Exercise 1.13)
2 2log(2N(E))
E sup ((e)
( C. (0(0)) My
The remainder of the proof consists in computations to put the result in the required format. More precisely, have
2 2log(2N()))
E sup (0) [0]) A
& 2CKe M.
2ogg(2) + 2m log [16mRs) + 2m log (4)
< 2CKe + M
n
2(m 1o (16mBa)
2m2 Ka log(4)
< 2CK + M
n
The third step is valid if 16mRa > 2. We will shortly take to be equal to vn thus this condition holds true under the assumption from the Theorem that mRe n 2/ 3. Hence we obtain
((O.)) (O.) 2CKre +CCKet + My
2(m + 1) log [16mRa) ) + 2m log(4)
M
log
n
Vn
(16)
Now denote B , exp( ( Re). Then CK2 < and 2M < B. Taking &
we obtain
Vn
2B
B
2(m + 1) (ow.oooogo/nmmn 2m log(4)
B
1
< < (..
Vn
+
V
n
Vn
Vn
log
j
2B
B
2(m + log (16mgg1
B m m 2K log(4)
< ( +
Vn
+
2
V
2
n-/4
Vn
log
3B
2(m + 1) log(16mRevn)
my K
B
(0,) +
V
B
log
2
n 1/4
Vn
8'
since 2 < lo) <
/2(m + 1) log n since 16m v > 2 by the Theorem's assumptions, and (2) < 2. We finally obtain that
2(0,) < (..) + 3B
(m + 1) log(mRan) B
my
Ke
+
B
1og
I log
1/4
Vn
17

---

by noting that n > 9 max(m 2
RRg. 1) implies that
log (e1166Reevl vn) & 2log(m
The result unfolds since the constant in the Theorem is equal to 3B.
A.5 Proof of Corollary
The corollary is an immediate consequence of Theorem 1. To obtain the result, note that m d, thus in particular vm + vi² +1 & 1, and besides log( RwdPn) < 2 log( Rwydn) since Rwn & Ryn?? by assumption
A.6 Proof of Proposition 4
For x X, let (Hæ)oskst be the values of the layers defined by the recurrence (10) with the weights W and the input Ho I. We denote by || the ε2-norm for vectors and the spectral norm for matrices. Then, for {0...... 1}, have
H || & || + 7. [Weo(H<)ll < || + 7, FIlW & (1+ Kolw
||
T.
where the last inequality uses that the spectral norm of matrix is upper-bounded by its (1, 1)-mr and that (0) = 0. As consequence, for any l E (O....,I).
||H < (1+ ===K |Holl exp(K, Row)
R Rx =: C,
yielding the first claim of the Proposition.
Now, let H be the values of the layers (10) with another parameter W and with the same input Ho Then, for any {0, ................................ L 1}.
Ha+1 Hk+1 = HA H + 7, (W (Hx) - (ao((H))
Hence, using again that the spectral norm of matrix is upper-bounded by its (1, 1) -omm and that (0) 0,
Ha++ Matill |l < |1 - Hall + + (1Wa) - ((H)))] - Wa)o(fl
< 1 + Ko Rw
K₂
||H| - 11xl1
I|W W&ll |1 L
L
< + Ka Row
CK.
Hr Hall
I W&ll
L
L
Then, dividing by + K2 2=) yk+ and using the method of differences, we obtain that
H4 Hxll
& 1o Holl + CK. L
IW, W
K2 1.
+ K2 Rw Rwist
CK2 w - W1l.1.0
1
(1 Kr Row p01
1=
Finally note that
(1 + K2 Rw )*
Rw I
I
Σ (1
K.
(1 + K
Rw j+1
j=0
L
Kr (1+KKo
((1
R. y -1)
K2 KgRw
L
(exp(KoRw) -1).
Kollw
We conclude that
(exp(K, Rw) - 1) W| < Rx
Hg
Hxll < Rw
Rxp(2K,Rw)) W W|
Rw
18

---

A.7 Proof of Proposition 5
For two integers and b, denote respectively / and a%o the quotient and the remainder of the Euclidean division of a by b. Then, for W E Rlxxddd let @ (W) [00 Red the piecewise-affine
function defined as follows: (( affine on every interval
L for {0..... I. 1]; for
A+1
E (1,..., and (1..... d.
W): W E. +0//00++
and (W) = ((W), Then @ () satisfies two properties. First, it is linear function of W. Second, for W E IR bxxxd
| 1, = 1
because, for [0, 1], of (z) is norm by [ so it is itself bounded f-oor by || implying that [[(W)]],,,o & [W]11,0 Reciprocally,
combination of two vectors that bounded in 4--
h I (W)
| (, = sup | (()() 0
>
sup IEREL
||
1,00 & Rw. Moreover, each coordinate of @f W) is Kw-Lipshhizz, since the slope of each piece of o(W); is at most Kw. As consequence, of W) belongs
Now, take W W. The second property of & implies that || (W)I
θw = (0: |0, Rd" |10]1,,0 & Rw and 0, is Ww-Lipschitz for i (1....,,]]] d).
Therefore ((W) a subset of Ow, thus its covering number is less than the one of Ow. Moreover, is clearly injective, thus
define d-1 its image. Consider s-cover (0I,..., 0n) of (o(W), oo)) Let us show that (0-)()))) (01),.... ...,. Φ (0x())) is an e-cover of (W, 111,1,0)): take W E W and consider 0; cover member distance less than from o( (W). Then
|| - o (01)ll... [ o 1o.))
((o(W) 0,11 E,,
where the second equality holds by linearity of ø. Therefore, the covering number of (W, || (,))) upper bounded by the of (6(W), o1,, which itself is upper bounded by the one of (Ow-l) (. yielding the result by Proposition 3.
A.8 Proof of Theorem
The proof structure is the same the of Theorem 1, but some constants change. Similarly (16), we obtain that, if 164 Rw > 2 (which holds true for 1/v5 and under the assumption of the Theorem),
2(d2 1) log [6dPRw) + 20 1og(4)
M M
Ww.) & (.(W.) +CCK M/
log g
with
M Kr + Ry)
and
Rx C Rw
exp(2KaBin) Rww)
Finally denote
exp(KK Rw)) 1).
B 2M max
Ry
Then CK₃ B and 2M < B. Taking
vo. we obtain in the proof of Theorem that
(dl + logg( Rww))
+ B L VVW
B log
(Ww,) & C.(, (W.) + 3B /
1/4
19

---

for n 2 Ry max(d "R 1). Thus
+ +322B(d+ D log log(d(wwn))
Kw
B
1
B
log
n1/4
Vn
8
since Vdl2 +1 & d +1 and Rwn & Ryyn? by assumption The result unfolds since the constant B in the Theorem is equal to 3v 22..
A.9
Proof of Corollary 2
Let
2/3 W
3/2
A(W)= =
II +
W4
221
L2 |I 1 W
where || 112.1 denotes the (2, -omm defined as the fi-norm of the lg-norms of the columns, and is the identity matrix (and recall that || denotes the spectral norm). We apply Theorem 1.1 from Bartlett et al. (2017) by taking as reference matrices the identity matrix. The theorem shows that, under the assumptions of the corollary,
Rx A(W) log(d)
C
P arg max Fw (2), * v) < ( C 1
log 8'
where, as in the corollary, R. (W) E constant. Let upper bound A W) to conclude. On the one hand, we have
E
1 (us)) - max su f(z), and C is a universal
WE
<
( + T. |Well)
k=1
|Willla)
+
L
km
[ _ Row
x exp( (Bw)
On the other hand, for any ls E LL....,L}.
|| < | 11,1 & Rw,
while
Rw || + 7, Wv/ > 1 Ww > 1-
1
>
L 2
under the assumption that > Rw. All in all, we obtain that
A(W) < cxp(Rw) (2 (2 1/3 (112R113) R2 3/2 = 2R exp Rw) VI,
which yields the result.
B
Experimental details
Our code is available
https:// trutthu..... tat..ttu...........
We use the following model, corresponding to model (10) with additional projections at the beginning
and at the end:
Ho Ar
1 H&t1 = H T. (Hs)) 0
Fw(z) = -BH,,
20

---

Name
Value
30
L 1000
ReLU
Table 1: Values of the model hyperparameters.
where x' E R768 is vectorized MNIST image. A E Rdx768 and B E Rloxd, Table I gives the value the hyperparameters.
We use the initialization scheme outlined in Section 4.1: we initialize, for E {1,.... L) and i (1.....d)
WA.
Vd
where fi, are independent Gaussian processes with the RBF kernel (with bandwidth equal to 0.1). We refer Marion et al. (2022) and Sander et al. (2022) for further discussion this initialization scheme. However, and are initialized with more usual scheme, namely with i.dd ((0,, 1/c) random variables, where denotes the number of columns of A (resp. B).
In Figure la, we repeat training times independently. Each time, we perform 30 epochs, and compute after each epoch both the Lipschitz constant of the weights and the generalization gap. This gives 300 pairs (Lipschitz constant, generalization gap), which each corresponds to one dot in the figure. Furthermore, we report results for two setups: when A and B are trained or when they are fixed random matrices.
In Figure 1b, A and B are not trained. The reason is to assess the effect of the penalization on W for a fixed scale of A and penalization might be neutralized by a scale increase of A and B during training.
we allow A and vary, then possible that the effect of the
For all experiments, samples). We train using the cross entropy loss, mini-batches of size 128, and the optimizer Adam (Kingma and Ba, 2015) with default parameters and learning rate of 0.02.
the standard MNIST datasplit (60k training samples and 10k testing
use PyTorch (Paszke et al., 2019) and PyTorch Lightning for our experiments.
The code takes about 60 hours to run on standard laptop (no GPU).
21


Reviews:
[{"review_id": "MHeIOyaYda", "reviewer": "Reviewer_W2zB", "summary": "The paper provides a generalization bound for the large class of time-dependent and time-independent neural ODEs. In addition, by leveraging on the connection between neural ODEs and deep residual networks, the paper provides a depth-independent generalization bound for the class of deep residual networks. The bound is compared with some earlier results, showing its novelty. The paper introduces a novel way of controlling the statistical complexity of neural networks and the bound depends on the magnitude of the difference between successive weight matrices. Numerical experiments are provided to show the relationship between this bound and the generalization ability of neural networks.", "questions": "1. In Proposition 2 and Theorem 1, what do $R_X$ and $R_Y$ mean? The reviewer guesses that $R_X$ is the bound of the set of initial values $x$, but these two notations as well as $X$ and $Y$ do not have clear definitions.\n\n2. A clear definition of $n$ in Theorem 1 is missing. If the data is any $n$ samples, the conclusion of Theorem 1 is obviously wrong.\n\n3. The condition in Corollary 1 is too strong. The reviewer think Neural ODE should contains at least one hidden layer. And the reviewer think that the generalization of Neural ODE with one hidden layer can be obtained by using Theorem 1, by studying the Lipschitz constant of $\\sigma(Wx)$. \n\n4. The reviewer thinks that some existing definitions or symbols, such as covering number, subGaussian, should be briefly explained.\n\n5. The numerical experiments show the correlation between the generalization gap and the maximum Lipschitz constant of the weight. However, the generalization gap proved in this paper mainly depends on the number of samples $n$. Could the paper provide experiments to show the correlation between these two quantities as well as the convergence order?\n\n6. Some abnormal result points can be found in the experimental results, such as the point in the bottom left corner of Figure 1. Is there any explanation for this？\n\n7. Theory and numerical experiments show small Lipschitz constant of the weights reduce the generalization gap. Does this indicate that time independent coefficients ($K_{\\Theta}=0$?) have better generalization?\n\n", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper provides a generalization bound for the large class of time-dependent, time-independent neural ODEs and deep residual networks. The bound is compared with some earlier results, showing its novelty. The paper introduces a novel way of controlling the statistical complexity of neural networks and the bound depends on the magnitude of the difference between successive weight matrices. Numerical experiments are provided to show the relationship between this bound and the generalization ability of neural networks.", "weaknesses": "Some expressions are not very clear, and some results have too strong conditions. Please see Questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The notations $X$, $Y$, $R_X$ and $R_Y$ are defined in Section 3.1 (lines 111-113). \n2. $n$ is indeed the sample size (defined in Section 3.1, line 111), and the training sample is drawn i.i.d. from the same distribution as the test sample (as specified in Section 3.1). Does this answer your concern on Theorem 1? If not, we would be very interested if you could elaborate on your statement.\n3. Our parameterized ODE model (5) does not include the case where there are weights inside the non-linearity, since we assume the dynamics at time $t$ to be linear with respect to the parameters (which still makes the input-output mapping highly nonlinear, see Section 3.2, lines 150-154). As a consequence, the extension to the case you mention is non trivial, and we agree it would be very interesting. We leave it for future work and will mention this possible extension in the conclusion of the paper.\n4. The covering number is informally defined on lines 172-174, we will add a more formal definition, as well as the definition of sub-Gaussianity.\n5. Following your suggestion, we performed some experiments varying the sample size $n$. We observe a smaller generalization gap when increasing $n$, as expected by the theory. Unfortunately, it is difficult to say more and in particular to report a convergence rate because of a large amount of noise in the experiments (due to the data splitting used to vary the sample size and to the optimization algorithm).\n6. The points in the bottom left corner of Figure 1a correspond to a very small number of training epochs (typically equal to 1). At this early stage in the training process, the model is underfitted, and the generalization gap is very negative.\n7. Your statement is correct: we do observe that time independent coefficients have better generalization (however at the cost of a less expressive model). We will report this in the experiments by adding data points corresponding to time-independent coefficients (which can be thought of as taking $\\lambda$ to infinity in Figure 1b).\n"}, {"review_id": "nunoXdTwui", "reviewer": "Reviewer_d5dy", "summary": "The paper explores the generalization ability of neural ordinary differential equations and deep residual networks through Lipschitz-based complexity arguments. The bound, specifically for the discretized version, involves the maximum magnitude of the difference between successive weight matrices, which is not commonly seen. The paper also uses numerical experiments to investigate how this quantity relates to the generalization capability of deep residual networks. The generalization gap is smaller when the quantity is smaller, but adding the quantity as a penalization term did not improve the prediction performance.", "questions": "Have you conducted any experiments of Figure 1b using the maximum max-norm of the weights as a penalty term (or a sum of the max-norm of the weights) instead of the squared sum of Frobenius norms? While I acknowledge the equivalence between matrix norms, and although it may not be strictly necessary for the paper, I believe that readers (including myself) would be interested in seeing whether the behavior is different when the quantity that appeared directly in deriving the theoretical guarantee is used.\n\n[minor suggestions]\n\n- Line 112 “takes values into” → “takes values in”\n- Line 285 “Corollary 2 (of Theorem 1.1 of Bartlett et al. (2017))” → “Corollary 2 (corollary of Theorem 1.1 of Bartlett et al. (2017))”\n- Line 319 “a.k.a.” → “i.e.,” may be more appropriate?", "limitations": "None in particular", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "[originality]\n\n- To the best of my knowledge, this paper is the first to present a generalization error bound for neural ODEs. The proof techniques used in this work are rather standard, but they are combined in new ways to derive the results.\n- The potential importance of the Lipschitzness of the weights (i.e., the maximal magnitude of the differences between successive weight matrices) is newly proposed.\n\n[quality]\n\n- The analysis and results seem reasonable, and the mathematical setup is adequately explained.\n\n[clarity]\n\n- The paper is well-organized and articulately written. Its concise abstract enhances the paper's accessibility and ease of comprehension.\n\n[significance]\n\n- Neural ODEs and deep residual networks are now among the standard tools in the machine learning community. Therefore, theoretical results that advance our understanding of the behavior of these models are relevant and can improve their reliability for use in various applications.\n- The analysis in Theorem 1 reveals a term whose convergence rate is O(n^{-1/4}). Corollary 1 exemplifies that the slow-rate term can be eliminated by making the coefficient parameter time-independent in the infinite-dimensional case, partly elucidating the consequences of having time-dependent component in the model.", "weaknesses": "[originality]\n\n- None in particular\n\n[quality]\n\n- The paper would benefit from additional citations, particularly where named theorems are mentioned in the main text. For instance, it would be helpful to add citations to the Picard-Lindelof theorem at Line 59 and to Gronwall's inequality at Line 166 for the convenience of the reader.\n\n[clarity]\n\n- None in particular\n\n[significance]\n\n- None in particular", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper would benefit from additional citations, particularly where named theorems are mentioned in the main text.\n\nWe will add citations for the Picard-Lindelöf theorem (actually the citation is present in the appendix but not in the main paper) and Grönwall’s inequality.\n\n> Have you conducted any experiments of Figure 1b using the maximum max-norm of the weights as a penalty term (or a sum of the max-norm of the weights) instead of the squared sum of Frobenius norms?\n\nWe had not previously conducted an experiment with the max-norm penalization, because we thought that this penalization may be too irregular, in the sense that, at any one step of the backpropagation, it only impacts the maximum weights and not the others. Nevertheless, this is a very relevant remark, and we performed the suggested experiment. The results are mixed: we observe a similar effect of the regularization on the generalization gap as in the paper when using the $L_2$ norm of the max-norm of the weights. On the other hand, penalizing by the maximum max-norm of the weights does not have an effect on the generalization gap. We interpret this last result as a consequence of the fact that the maximum max-norm is too irregular (it only acts on two scalar weights at each step) to be used in practice. We will report these results and discussion in the next version of the paper.\n\nThe minor suggestions are well noted."}, {"review_id": "K8m6y2jSDp", "reviewer": "Reviewer_EEyp", "summary": "The authors present a generalization bound for a large class of ODEs in this work. They connect ODEs to residual architectures to control the generalization with the differences between weight matrices.", "questions": "Have you measured how the bounds fare in time series problems?", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The authors present a theoretical bound, which is something worth highlighting when everybody is just building ad hoc pipelines and then testing them against some benchmark. From this point of view, this work represents a clear advance over other results.", "weaknesses": "Even though the results are strong, the consequences and how they can be used are not done in a way that can help the reader to fully understand the applications of these results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We consider in this paper a residual network model that is not adapted for time series: the input is a vector $x \\in \\mathbb{R}^d$ that is used on the first layer of the network. On the contrary, models for time series typically input data at each layer, corresponding to a new time step. The time series setup requires different models (such as ODE-like RNNs, which are mentioned in the related work section), which are not in the scope of the current paper. We will specify this more clearly in the related work section where we mention RNNs, to avoid inducing any confusion."}, {"review_id": "ALqCd56a4W", "reviewer": "Reviewer_wvQq", "summary": "【Post-rebuttal Comments】\n\n I thank the authors for the discussions after the authors' rebuttal. My questions are appropriately answered. So, I want to keep my score and vote for acceptance.\n\n\n【Original Comments】\n\nThis paper evaluates the generalization performance of the class of functions represented as solutions of time-dependent parametrized ODEs (including time-dependent Neural ODEs) and their discretized variants, that is, Residual Network, that smoothly changes weight parameters with respect to layer index. The obtained generalization bound is $O(1/n^4)$ for the general case and $O(1/n^2)$ for the time-independent case (for sample size $n$.) Numerical experiments were conducted to examine the relationship between the smoothness of weights between successive layers and generalization performance. Also, a learning method was proposed to add the difference in weights between successive layers as a regularization.", "questions": "In l.84--91, this paper refers to existing studies of the generalization bound of continuous-time NNs. However, their relationship with this study has yet to be discussed extensively. Is the novelty of this compared with them that the former is a time-independent ODE while the latter is a time-dependent one? Also, is there any study that dealt with time-independent ODEs?", "limitations": "Limitations are discussed in the experiment section (l.338) and conclusion section (l.346.)", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The derived results are consistent with classical statistical learning theory. Specifically, setting $K_\\Theta=0$ yields the classical $O(1/n^2)$ rate.\n- Numerical experiments verify the relationship between the smoothness of weights and generalization performance. These results align with the theory.\n- Comparisons with existing results (Bartlett et al. (2017), Golowich et al. (2018)) are carefully considered. In particular, this study is novel in that it provides generalization bounds for a class of depth-independent models to which Golowich et al. (2018) are not applicable.\n- The paper is well-written. The organization and mathematical description of the paper are appropriate, and it was easy to understand the paper's main point.", "weaknesses": "- To the best of my knowledge, it is rare to impose smoothness between the weights of successive layers in a discretized ResNet model. In addition, the prediction accuracy of those models has yet to be confirmed to be sufficient. Therefore, it is difficult to say that this paper provides a theoretical guarantee for practical models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> To the best of my knowledge, it is rare to impose smoothness between the weights of successive layers in a discretized ResNet model. In addition, the prediction accuracy of those models has yet to be confirmed to be sufficient.\n\nWe agree that imposing smoothness between successive layers is not a very common setup in residual networks, although it is the right framework for residual networks to approximate neural ODEs, which are commonly used models. We leave for future work the task of evaluating the prediction accuracy on real-world data of residual networks in this setting. \n\n> In l.84--91, this paper refers to existing studies of the generalization bound of continuous-time NNs. However, their relationship with this study has yet to be discussed extensively. Is the novelty of this compared with them that the former is a time-independent ODE while the latter is a time-dependent one?\n\nTwo of the three papers cited in lines 84--91 tackle recurrent neural networks, which handle time series, contrarily to our residual networks that handles vectors. The time series setup requires significantly different models and analysis. The last paper answers a separate (although related) question regarding the generalization across environments, and only gives a generalization bound for linear ODEs. We will make the comparison with these works more detailed.\n\n> Also, is there any study that dealt with time-independent ODEs?\n\nWe were made aware after submission time of another work (reference below) that shows a generalization bound for parametrized ODEs for manifold learning, which applies in particular for neural ODEs. Their proof technique bears some similarities with ours, but the model (time-independent versus time-dependent ODEs), task (unsupervised manifold learning versus supervised learning), as well as the absence of connection with residual networks, differ from our approach. We will of course include the reference and discuss differences in the next version of the paper. \n\nJ. Hanson and M. Raginsky. Fitting an immersed submanifold to data via sussmann’s orbit theorem. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 5323–5328, 2022\n\nWe are not aware of any other generalization bound for neural ODEs, be it in the time-dependent or time-independent setting.\n"}]

Author rebuttal:
Dear reviewers,

We warmly thank you for your time and relevant comments, which will help us improve our work. If accepted, we intend to take into account your suggestions, making use of the additional page. 

We answer the specifics of questions pointed out by the reviewers in individual responses. 

Thank you again,

Sincerely,

The authors

Meta-review: This paper provides generalization bounds for neural ODEs and ResNets. The reviewers appreciate the novel and solid technical contributions, and unanimously recommend acceptance and weak acceptance. The questions from the initial reviews were satisfactorily addressed.
Decision: Accept (poster)