Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces
Authors: Vladimir R Kostic
Pietro Novelli
Andreas Maurer
Carlo Ciliberto
Lorenzo Rosasco
Massimiliano Pontil
Venue: NeurIPS 2022 Accept (2022)
Keywords: Koopman operator
Markov transfer operator
DMD
supervised learning
dynamical systems
low rank approximation
spectral decomposition

Abstract: We study a class of dynamical systems modelled as stationary Markov chains that admit an invariant distribution via the corresponding transfer or Koopman operator. While data-driven algorithms to reconstruct such operators are well known, their relationship with statistical learning is largely unexplored. We formalize a framework to learn the Koopman operator from finite data trajectories of the dynamical system. We consider the restriction of this operator to a reproducing kernel Hilbert space and introduce a notion of risk, from which different estimators naturally arise. We link the risk with the estimation of the spectral decomposition of the Koopman operator. These observations motivate a reduced-rank operator regression (RRR) estimator. We derive learning bounds for the proposed estimator, holding both in i.i.d and non i.i.d. settings, the latter in terms of mixing coefficients. Our results suggest RRR might be beneficial over  other  widely used estimators as confirmed in numerical experiments  both for  forecasting and mode decomposition.

Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces
Vladimir R. Kostic Istituto Italiano di Tecnologia University of Novi Sad vladimir
Pietro Novelli
Istituto Italiano di Tecnologia novero.novelllin
Andreas Maurer Istituto Italiano di Tecnologia am@andreas-maures
Carlo Ciliberto
University College London d.cilii c.llibertouucl ac uk
Lorenzo Rosasco
Massimiliano Pontil Istituto Italiano di Tecnologia University College London
University of Genova
Massachusetts Institute of Technology
Istituto Italiano di Tecnologia Irosasco@mit.
mass iimiiimiiino...m itn.:liiiin.npiii111ee it
Abstract
We study class of dynamical systems modelled Markov chains that admit an invariant distribution via the corresponding transfer, Koopman, operator. While data-driven algorithms to reconstruct such operators are well known, their relation- ship with statistical learning is largely unexplored. We formalize framework learn the Koopman operator from finite data trajectories the dynamical system. We consider the restriction of this operator to reproducing kernel Hilbert space and introduce a notion of risk, from which different estimators naturally arise. We link the risk with the estimation of the spectral decomposition of the Koopman operator. These observations motivate a reduced-rant operator regression (RRR) estimator. We derive learning bounds for the proposed estimator, holding both in i..dd and non i.i.d. settings, the latter in terms mixing coefficients. Our results suggest RRR might be beneficial over other widely used estimators confirmed in numerical experiments both for forecasting and mode decomposition.
Introduction
Dynamical systems [26, 38] provide framework to study a variety of complex phenomena in science and engineering. For instance, they find wide applications in diverse fields such finance [46], robotics [6, 16], atomistic simulations [32, 36, 53], open quantum system dynamics [20, 28], and many more. Because of their practical importance, research around dynamical systems and has been abundant, see e.g. [17, 58] and references therein.
In light of recent machine learning progress, it is appealing to ask if the properties of dynamical systems can be estimated (learned) from empirical data. Beyond machine learning this question has long history in dynamical systems [7]. The go-to reference for data-driven algorithms to reconstruct dynamical systems is [25], where numerous methods based on so-called dynamic mode
'Equal contribution, corresponding authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

decomposition (DMD) are discussed along with interesting applications. The literature on various theoretical aspects of dynamical systems is also rich [35, 38]. Our starting observation is that although data-driven algorithms to reconstruct dynamical systems are well known, their relationship with statistical learning [61] is largely unexplored. Our broad goal is to build a tie between these two important areas of research and to establish firm theoretical grounds for data driven approaches, to derive statistical guarantees and a foundation in which learning dynamical systems can be tackled in great generality.
In this paper, we present a framework for learning dynamical systems from data obtained from one or multiple trajectories. The focus is both predicting the future states of the system and interpreting the underlying dynamic. The initial observation is the fact that, under suitable assumptions, dynamical system can be completely characterized by a linear operator, known as Koopman (or transfer) operator [8, 35J. More precisely, the Koopman operator describes how functions (observables) of the state of the system evolve over time along its trajectories. Further, the spectral decomposition of the Koopman operator, along with the mode decomposition, allows us to interpret the dynamical and spatial properties of the system [11, 39, 52]. In view of these results, learning dynamical system can be cast as the problem of learning the corresponding Koopman operator and associated mode decomposition.
key insight in our approach is to consider the restriction of Koopman operators to reproducing kernel Hilbert spaces. With this choice, Hilbert- Scchmtt- operators become the natural hypothesis space and kernel methods can be exploited [24]. We further link the proposed framework conditional mean embeddings [21, 24, 43]. This allows us to formalize the estimation of the Koopman operator as a risk minimization problem and derive a number of estimators as instances of classical empirical risk minimization under different constraints. We dub the problem Koopman operator regression. In our framework DMD and some of its variants [25] are recovered as special cases. Moreover, our analysis highlights the importance of rank constrained estimators, and, following this observation, we introduce and analyze an estimator akin to reduced rank regression (RRR) [22]. Within our statistical learning framework the learning properties of the studied estimators can be characterized in terms of non asymptotic error bounds derived from concentration of measure results for mixing processes. Theoretical results are complemented by numerical experiments where investigate the properties the estimators, and show they can be smoothly interfaced with deep learning techniques. We note that, both kernel methods [1, 5, 13, 23, 24, 67] and deep learning approaches [4, 15, 30), have been recently considered to learn Koopman operators. Compared to these works (notably [24], whose setting is closely related to ours), we provide statistical learning framework connecting to the classical notions of risk, which we further link to the estimation of the spectrum of the Koopman operator. Moreover, we derive non asymptotic and non-i.i.d. learning bounds and introduce and study a novel constrained rank estimator RRR.
Contributions. In summary main contributions are: 1) We present a statistical learning frame- work for Koopman operator regression: 2) We bound the error in estimating the Koopman mode decomposition and its cigenvalues by the risk of an estimator (Theorem 1); 3) We present novel reduced-rank estimator and show that it can be computed and used efficiently (Theorem 2); 4) We provide statistical risk bound supporting the proposed estimator (Theorem 3) and introduce new tool (Lemma 1) which is key in extending the bound to the non-i.id. setting.
Notation. For any non-negative integers n, with n > m we use the notation [m::]] = {m, ................................ n and [x] = [1:n]. xx) := (2x,X, π) is the space of real valued functions on X, that are square- integrable with respect to Given two separable Hilbert spaces H and G, we let HS (H, G) be the Hilbert space of Sallertt-chhidd (HS) operators from H to G endowed with the norm ||Alliis = ΣieN |l for A HS (H. G). where (et)ee is an orthonormal basis of H. We use the convention HS (7{ HSS (H, H). The standard norms in Hilbert spaces and operator norms are denoted by ||-I|, where the space is clear from the context. Given an operator A E HS (H), we denote with [A]] its r-truncated singular value decomposition and its i-th singualr value by (A).
2 Background on Koopman operator theory
We briefly recall the basic notions related to Markov chains and Koopman operators and refer to App. A and [26, 35, 38] for further details.
2

---

Let X = {Xt: NJ be a family of random variables with values in a measurable space (X' Ex), called state space. We call X Markov chain if P P(X++1 E B (1)) = ((X++1 E x Further, we call X time-homogeneous if there exists p: X x Ex + [0, 11, called transition kernel, such that, for every (z, B) E X x Ex and every t E N,
P(X++1 E B X, = x) p(r, B).
In this work we consider only discrete Markov chains with E N, but we note that any continuous
Markov process with E R can reduced to discrete chain by sampling at times in = nnA. with N and At fixed. For alternative approach to approximate continuous dynamics see e.g. [51].
For a set F of real valued and measurable functions on X. the Markov transfer operator AF: F is defined as
A=ʃ(x) = 1 pla, (V) - EIX( a), JEF
(1)
A possible choice is F = (X), the space of bounded functions on X [26]. We are inter- ested in another common choice related to the existence of an invariant measure satisfying π (BB)= fx क p(z,) B), B E Σx. In this case, it is possible to take F= = L (X), and easy to see that ||=l| S 1, that is the Markov transfer operator is bounded linear operator. In the following, we denote by Ar the Markov transfer operator L (2). and always assume the existence of an invariant measure. We note that, its existence can be proven for large classes of Markov chains, e.g. [12]. Also, to derive the statistical bounds in Sec. 5 we assume that the Markov chain is mixing [26].
Example 1. An important example of the above construction is given by discrete dynamical systems with additive noise. That is, given stale space X C Rd, mapping F: X + X and a probability distribution Ω on X' we let X = F(X,) + we, I. E N, where wi are i.i.d. zero mean random variables with law Q. The corresponding transition kernel is p(a,, B) ( Fx=)). for which the existence of an invariant measure is ensured e.g. when Q is absolutely continuous with respect to the Lebesgue measure and its density is strictly positive (see Remark 10.5.4 in [26]).
Remark 1. Whenever x (dxx)p(z; dy) x(dy) dx) the Markov chain is said to be reversible. In this case it readily follows that the Koopman operator is self-adjoint A₃ = A In statistical physics the reversibility condition is also called detailed balance and is linked to the symmetry with respect to time reversal. Since a large amount of microscopical equations of motion in both classical and quantum physics are time-rev reversal invariant, learning self-adjoint Koopman operators is of paramount importance in the field of machine learning for physical sciences.
Koopman Operator and Mode Decomposition. In dynamical systems, A, is known as the (stochastic) Koopman operator on the space of observables J. An important fact is that its linearity can be exploited to compute a spectral decomposition. Indeed, in many situations, and notably for compact Koopman operators. there exist scalars X E C. and observables diy E L (X') satisfying the eigenvalue equation a, = Aeyh,. Leveraging the eigenvalue decomposition, the dynamical system can be decomposed into superposition of simpler signals that can be used in different tasks such as system identification and control, see e.g. [7]. More precisely, given an observable I E span i E NJ there exist corresponding scalars ?f E C known as Koopman modes of J. such that
1+f(()) = Elf(X,) Xu = x| Σ Xo) +ENttEN.
(2)
EEN
This formula is known as Koopman Mode Decomposition (KMD) [2, 8). decomposes the expected dynamics observed by f into stationary modes 7f that are combined with temporal changes governed by eigenvalues A; and spatial changes governed by the eigenfunctions vú. We notice however that the Koopman operator, in general, is not a normal compact operator, hence its eigenfunctions may not form complete orthonormal basis of the space which makes learning KMD challenging.
In many practical scenarios the transition kernel p. hence Ar, is unknown, but data from one or multiple system trajectories are available. We are then interested into learning the Koopman operator, and corresponding mode decomposition, from the data. Next we discuss how to accomplish this task with the aid of kernel methods.
3

---

3 Statistical Learning Framework
In this section we choose the space of observables F to be a reproducing kernel Hilbert space (RKHS) and present a framework for learning the Koopman operator on (2)) restricted to this space and the associated Koopman mode decomposition.
Learning Koopman Operators. Let H. be an RKHS with kernel k : &' x X - R [3] and let : X' H. be an associated feature map, such that k(2,, y) = (Ø(z), (b)) for all x. X. We assume that that k(x,2 x) co, r-almost surely. This ensures that H. [ L (2) and the injection operator Sx: H + _ given by (x)) = f(x), x E X' is a well defined Hilbert-Schmidt operator [9, 55]. Then, the Koopman operator restricted H is given by
Zx == S
L (2).
Note that unlike A,, Zr is Hilbert-Schmidt since St is so. It is then natural to approximate Zg by means of Hilbert-Schmidt operators. More precisely, for G E HS (H) we approximate Za by S G, and measure the corresponding error as || Sz llis- To that end, given an an orthonormal basis (h,) of H. we introduce the risk
R(G)= == E
- (X,)) Ix, x]
(3)
iEN
as the cumulative expected one-step-ahead prediction error over all observables in H. One can show (see Prop. (4) in App. B) that such risk can be decomposed as R(G) = Ry + E(G). where
Ro liis 2| Ilis 2 0 and E(G) 1| - S, Gliss
(4)
are the irreducible risk and the excess risk, respectively. As clear from the above discussion, the Koopman operator and corresponding risk are typically not available in practice and what is available is dataset of observations D := (zi, ) E (X' X)) Here, 2; and yı are two consecutive observations of the state of the system. In classical statistical learning, the data is assumed sampled i..d. from the joint probability measure p(dx, dy) ;= π (dx)p(x, dy). In the case of dynamical systems, it is natural to assume the the data are obtained by sampling a trajectory y: = 2i+1, for i e [n- 1]. Then, the problem of learning A, on a RKHS, named here Koopman operator regression, reduces to:
Given the data D solve min R(G)..
(5)
GEHS((H)
As discussed in Sec. 2, a central idea associated to Koopman operators is the corresponding mode decomposition. It is then natural to ask whether approximate mode decomposition can be derived from a Koopman estimator. The following proposition provides a useful step in this direction. Here and in the rest of the paper by cll() we denote the closure of subspace of the Hilbert space, and we say that a finite rank operator G E HS (H) is non-defective if and only if its matrix representation is non-defective, i.c. (not necessarily unitarily) diagonalizable.
Proposition 1. Iflm(Zz) C el(Im( ()))), then for every 8 > 0 there exists a finite rank non-defective operator G E HS (H) such that (G) < 5.
The above proposition shows that if the RKHS H is, up to closure in T (2¹), an invariant subspace of the Koopman operator Az, then finite rank non-defective HS operators on H approximate arbitrarily well the restriction of Aμ onto H. In particular, this always true for a wide class of kernels, called universal kemnlss [55], for which H. is dense in L (2), i.. cl(Im(S.)) = (X²).
Remark 2. Since in the above proposition inf infGE E(G) = O. we can distinguish between two cases depending on whether the infimum attained or not. the former case, known in the literature as well-specified case, there exists GH E HS (H) such that Zz = S,GH, which implies that Gy: H > H. defines w-a.e. the Koopman operator on the observable space H. i.e. GHJ= = =[[([x++)+)) Xx = ---u.e for every E H. In the latter case, known misspecified case, H does not admit a Hilbert-Schhid Koopman operator H + H.
Remark In the misspecified case, a Koopman operator on H might still exist as a bounded albeit not Hilbert-SShhiid operator. In App. B.2 we show that for reversible Markav processes (see Rem. 1), if C cl(Im( ((Im(S))), )), there exists an estimator of the Koopman operator G such that 7 - is arbitrarily small and [|G]| < 1.
7 S

---

Learning the Koopman mode decomposition. Techniques to estimate the Koopman mode decom- position (2) from data, are broadly referred as Dynamic Mode Decomposition (DMD) [25]. We next introduce a DMD approach following the discussion above. Let E IN and non-defective G HS, := {G E HS (H) rank(G) S rr. Then, there exists spectral decomposition of G given by (A,, 1/ ())l= where A E C C'andd &, and 4/ are complex-valued function with components in H. such that G = Σ Ards @ E,, where Gti; Arthi, G* = > and (1hs, S3² = ōzj. where
6y is Kronecker delta symbol, i,j [r]. This implies, for any f E H. that
G* f = Mod
Vi. t 1.
(6)
The coefficients 7: == (J.E:) R.. i E [r], are called dynamic modes of the observable f and expres- sion (6) is known as the DMD corresponding to G. Next, we upper bound the error in estimating the mode decomposition of A (see Eq. (2)) by the DMD of non-defective operator G E (H). Theorem 1. Let G E (H) and (de, Es Di its spectral decomposition. Thenfor every f E H
E[f(x) Xo = x] = Σ
Xa. (x(x) + Z - S, er (z), x ZE,,
(7)
where err E 1. (X"), and ||er|/1| S (1 1)]|G/|| + [1]1 1. Moreover, for any iE(r),
1z - - S |G]| 1S
1A A:S. v
(8)
(S,
This theorem provides KMD approximation results for the DMD obtained from an estimator G in ISS.H), First, since 1| G S VE(G), equation (7) shows that DMD for an estimate G' E HSS(H)) incurs error which is at most proportional to the (square root) of the corresponding excess risk (G).. Further, the error degrades as increases. This implies that the prediction error (t= 1) is only controlled by the risk but forecasting (t 2 1) will get in general increasingly harder for larger t. Second, inequality (8) shows that (A,, S₂ e'r) is approximately an eigenpair of the Koopman operator Aq. Indeed, it guarantees that all the eigenfunctions of the estimator G. considered as an equivalence class in 2 (2)). approximately satisfy the Koopman eigenvalue equation. Inequality (8) provides a relative error bound controlled by the excess risk EG),, where the approximation quality worsen as higher ranks are considered. This provides additional motivation to study low rank estimators of Ar,, see Sec. 4. Moreover, we point out that the bounds in Thm. are tight, since on any RKHS H spanned by a finite-number of Koopman eigenfunctions it exists a finite rank GH yielding || S HSS = O. For additional discussions see Exm. 3 of App. B.
We conclude this section with two remarks regarding the estimation of the eigenvalues of A, and a connection to conditional mean embeddings [54].
Remark (Spectral Estimation). Eq. (8) alone is not sufficient to derive strong guarantees on how well the spectra of G estimutes the spectra of Az. While we address this in detail in App. B.I, I. here we comment that in general may happen that S.G R Sz while Sp(Aa) is far from Sp(G). If An is a normal compact operator, however, for G E (H) and every E [r). there exists An, E Sp(Ax) such that 12;- 12--xa -Ax,Jl S 12, S| [G]]/o,(S,, G). If additionally G is also normal, then \ - S VE(G) ||S
Remark 5 (Link to Conditional Mean Embeddings). The Koopman operator is specific form of conditional expectation operator and can be studied within the framework of conditional mean embeddings [54], Here, the goal is learn the function 9p:
X + H defined as
gp Elo(X++1) X, x] / p(z, dor.dy)(ly) EE
(9)
called the conditional mean embedding (CME) of the conditional probability into H. In App. B.2 we show a "duality" between Koopman operator regression and CME expressed by the reproducing property (x) = (f.gp(z) (x)) q. In particular, recalling that p is the joint probability measure on X x X defined by p(dx, dy) = p( dy) (dz), the risk we proposed in (3) can be written as
E F(u.)))vpll (y) - G d(=)) 12 IF (1 - a(yill + IF Fr (g)p))))))))))())) - G* (x)(1) (10)
R(G)
Ro
E(G)
In this sense the Koopman operator regression problem (5) is equivalent to learning CME of the Markov transition kernel p.
5

---

4 Empirical Risk Minimization
We next describe different estimators for the Koopman operator. Let 3, E HS (H, RT)) be the sampling operators of the inputs and outputs defined, for every f E H. Sf (n f(z))) and f (n à f(u)) - respectively. The Koopman operator is estimated by minimizing. under different constraints, the empirical risk
R(G)= = 2 Sc SC
it = E (lo(v)) Gr 6(;;)l G HS (H).
(11)
(E(M)
The first expression the empirical version of the risk in (3), while the second expression is the empirical version of the risk as in (10), with a remark that sampling operator Ž is not an estimator of the regression operator Z- and that, since æ is an invariant measure, we have E E Z] = E($ S² Further, notice that for the linear kernel 6(x) Eq. (11) is essentially the problem minimized by the classical DMD, whereas if 6 is built from a dictionary of functions it is minimized by the extended DMD [25].
Before discussing further, we introduce the empirical input, output and cross covariances, given by S S, 5 = 7. 7 and T == 5 Z, respectively, and the corresponding kernel Gram matrices given by K := SS* L == -2 and M := 25. We also let C, := Ö + yIu be the regularized empirical covariance and K, := K + 7/n the regularized kernel Gram matrix.
Kernel Ridge Regression (KRR). A natural approach is to add a Tikhonov regularization term to (11) obtaining Kernel Ridge Rregression (KRR) estimator
G == min (R) + 7 ||Gllis Ge (H)))
(12)
It is easy to that G. = 3 Ž. One issue with the above estimator is that the compu- tation of its spectral decomposition becomes unstable with large datasets, see below. Consequently, low rank estimators have been advocated [25] way to overcome these limitations.
Principal Component Regression (PCR). standard strategy to obtain a low-rank estimator is Principal Component Regression (PCR). Here, the input data are projected to the principal subspace of the covariance matrix C, and ordinary least squares the projected data is performed, yielding the estimator G.CR [ī = S- [ In the context of dynamical systems, this estimator is known as kernel Dynamic Mode Decomposition, and is of utter importance in a variety of applications [7, 25]. Note, however, that PCR does not minimize the empirical risk under the low-rank constraint.
Reduced Rank Regression (RRR). The optimal rank r empirical risk minimizer is
Gry == arg min { (RG)) + || G E (H))
(13)
In classical linear regression this problem known as reduced rank regression (RRR) [22]. While extensions to infinite dimensions have been considered [44, 65), we are not aware of any work considering the HS operator setting presented here. The minimizer of (13) is given by G.,, Ō, C,,IC $ = UU 2. Here V, KU, and U, [un I... |u,] Raxr is the matrix whose columns are the r leading eigenvectors of the generalized eigenvalue problem LKu; = of K, normalized as u. K KK, = 1, E [r].
Forecasting and Modal Decomposition. The above estimators are all of the form & = S-W 2, for some n n matrix W. Given f E H. the one-step-ahead expected value [[](X++1) |x, x]] estimated by
(= (S (S > ( (Z.,),
where fn = (f))) and we used the definition of S and 2. Computing the above estimator demanding in large scale settings, mostly because a large kernel matrix needs be stored and manipulated. Predicting with KRR, therefore, is tantamount to solve linear system of dimension whereas for rank r estimators we only need matrix multiplications. Notice that the computational complexity of both PCR and RRR estimators is of order 2r² which is better than the (

---

complexity of KRR. However, number of recent ideas for scaling kernel methods can be applied for KRR, see e.g. [18. 37] and references therein. Perhaps more importantly, specific the context of dynamical systems is the fact that an approximate mode decomposition needs to be further computed, requiring the spectral decomposition of G. As showed in App. C.2, this reduces computing the spectral decomposition of an n. matrix W M, where recall M Z For KRR computing the spectral decomposition, in general, has complexity ((n") and may become numerically ill- conditioned for theoretically optimal regularization parameters. In contrast, the low rank structure of PCR and RRR estimators allows efficient and numerically stable spectral computation of complexity O(r²n²) as we show next.
Theorem 2. Let G = -.UUVV Z, with U,, V, E (Roxr. Vf, E R is full rank and non- defective, the spectral decomposition (Ae, Si (A)EE') of can be expressed in terms of the spectral decomposition (N,, Ug Us)ke(r) of V, MU,. Namely, & = VVuu X and v, = U, oe for all i [r]. In addition, for every f H. its dynamic modes given by y ū V, fn/(Avm)) E C.
In addition to the estimators presented above, several other popular DMD methods are captured by our Koopman operator regression framework. In App. C we review some of them providing also the proof of Thm. 2. We now turn to the study of risk bounds for the proposed low rank estimators.
Learning Bounds
In this section, bound the deviation of the risk from the empirical risk, uniformly over prescribed set of HS operators on H. The analysis here is presented for Ivanov regularization for simplicity, but our results can be linked to Tikhonov regularization (see [29] and reference therein for discussion). To state the result, we denote (true) input, output and cross covariances by C := Eg-= (Ø(x) @ (()),
D = F TF>==(ob (o(v) @ (v)) and T F F (2.g)><p(((( ((b))) @ ((v)], respectively. Note that since ı is invariant measure, the input covariance and output covariance are the same C = = St,r, while for the
cross covaraince we have T 5 Ze. Without loss of generality
present the results in the case
that [[x(z)] < 1, for all x E X' (the bounds below need otherwise to be rescaled by a constant).
We start by presenting thcorem holding in the setting where the data is sampled i.i.d. from the joint probability measure p(dr, dy) = π (dx)p(( dy).
Theorem 3. Let Gr., = {G E (SL ||G||иs S Sn} and define 0² E(Ilo(v)) Ell With probability at least 1 - 8 in the i.d.d draw of (Ii, 1 from p. we have for every G E gy.r
20 In
24n [
+ (1+247 (T) In 2 6-21 In 24n²
(R(G)- $
n
A key tool in the proof is the following proposition, which is a natural extension of [34, Theorem 7] who provided concentration inequalities for classes of positive operators.
Proposition 2. With probability at least 1 in the i.i.d. draw of (x,, v. from p.
8n2 In
|| In 8n2
| --T T
<
12
+ +61
n
Sketch of the proof of Thm. 3. Recalling the definition of the true and empirical risk, direct com- putation gives
- R
= tr [D Dj + [GG - θ)] - 2r [G*(T (T-(TT-T) - î)).
We use Hölder incquality to bound the last two terms in the r.h.s., obtaining
R(G) - R(( < tr D - D + + -
(14)
We then bound the first term as Lr Dj < In to bound the second term, and Prop. 2 for the last term. The result then follows by union bound. 0
20 +
see App. D.I. use [34, Theorem 7-(i)]
3n
We state several remarks this theorem and its implications.
7

---

1. is interesting to compare the bound for RRR and PCR estimators. Assuming that both estimators have the same HS norm, then they will satisfy the same uniform bound. However, the empirical risk may be (possibly much) smaller for the RRR estimator and hence preferable, see Fig. 1.
2. Using the reasoning in [33, 34] and [41] we can replace the variance term and the term ||C|| in the bound with their empirical estimates, obtaining a fully data dependent bound. Notice also that the bound readily applies the more general CME case, which could be subject of future work.
3. A related bound can be derived using Cor. 3.1 in [40] in place of Prop. This essentially replaces the term ||C|]| with ||EAA' || where A := (ω(x) & o(y) - T)). This bound is more difficult to turn into data dependent bound, but it allows for more direct comparison to bounds without the rank constraint, which may be potentially much larger; see the discussion in App. D.I.
4. One can use the uniform bound to obtain an excess risk bound. In the setting of Thm. 3 and well specified case in which 2g = Sr this requires studying the approximation error minges,,r ||S, (GH G)
now study ERM with time dependent data. We con- sider that trajectory T1,... In++1 has been sampled from the process Ii т, V/-1 2& p(zx-1, ), E [2:n]. For a strictly stationary Markov process the 8-mixing coefficients are the numbers fx (T) defined for NN by
Dealing with Sampled Trajectories.
(x)
sup
l0- (B) - (i x T (B)),
BEDGΣ
where Py is the joint distribution of X1 and X1+7. The basic strategy, going back to at least [68], to transfer concentration result for i.d. variables to the non-i.i.d case represents the process X by interlaced block- processes and Y', which are constructed in a way that Yj and Yý-1 are sufficiently separated to be regarded as independent. Specifically, they defined as
1)r
2jr X,
Y
Σ 10)
X and ry==
Σ (22--1)r+1
for E N.
This construction naturally yields the following key lemma, which allows to extend several results from the i..dd case to time dependent stationary Markov chains. The proof is presented in App. D.2.
Lemma 1. Let X be strietly stationary with values in normed space (X, I1-l)), and assume n 2mT for T,m. m E N. Moreover. let Zi...., Zm be m independent copies of Z1 = Ei= X,. Then for > 0
R|| Σ > 8) 2P
P
Σ
m
$ 2 (m
- 1)
As an application of this result we transfer Prop. 2, which was key in the proof of Thm. 3 to give an estimation bound for |T]], to the non-i..d. setting. Fix E N and let Z,...., Zm be independent copies of 71 Σ - ((x;) @ Φ(x++1) T. Applying Lem. I with ((x)) @ ((x+1)) T in place of X, we obtain the following.
Proposition 3. Let > (m (T - 1). With probability at least
the draw in n,
p(zi-1,)) ),, E [2:n].
48 In
4m
2 2||C m
4mn
7| T
12
In
(m 1) Bx
(m 1) Bx (T 1)
We notice that, apart from slightly larger numerical constants and logarithmic term, Prop. is conceptually identical to Prop. 2 provided the sample size is replaced by the effective sample size m n2/27. Similar conclusions can be made to bound the other random terms appearing (14), see App. D.2 for discussion.
Experiments
In this section we show that the proposed framework can be applied to dissect and forecast dynamical systems. While we keep the presentation concise, all the technical aspects, well as additional

---

Training vs. Test errors
Excess risk
0.525
10-2
PCR Train error
0.500
PCR Test ertur
RRR Train
PCR RRR
0.475
Test
10-1
0.450
n 1/2 decay
10
10
10 Training samples n
10
Traning samples
Figure I: Numerical verification of the uniform bound presented in Thm. for the noisy Logistic map. Left panel: the training and test risk for RRR consistently than PCR. Right panel: the deviation between training and test risk as function of the number of training samples have = n n-2 decay.
experiments, are deferred to App. E. Along with the code to reproduce the experiments, at the url https//gttubbcoo/CSMML------ /oooollla,,, we release a Python module implementing sk sklearn- compliant [47] estimators to learn the Koopman operator.
Noisy Logistic Map. We study the noisy logistic map, a non-linear dynamical system defined by the
.z) + +x) mod over the state space X' = [0, 1J. Here, & is i.i.d. trigonometric noise supported in (-0.5, 0.5] and is proportional to cos (TE), N being an even integer. In this setting, the true invariant distribution, transition kernel and Koopman eigenvalues are casily computed. In Tab. we compare the performance of KRR, PCR and RRR (see Sec. 4) trained with a Gaussian kernel. We average over 100 different training datasets each containing 10 data points and evaluate the test error 500 unseen points. In Tab. we show the approximation error for the three largest eigenvalues of the Koopman operator, A1 = and 22.3 = -0.193 193 + 0. 0.191i as well as training and test errors. The following eigenvalues A4,5| ~ 0.027 are order of magnitude smaller than [22,s/- Both PCR and RRR have been trained with the rank constraint r = 3. The regularization parameter for KRR and RRR is the value ? [10-7, minimizing the validation error. The RRR estimator always outperforms PCR, and in the estimation of the non-trivial eigenvalues X2.3 (A corresponding to the equilibrium mode is well approximated by every estimator) attains the best results. In Fig. 1 we report the results of a comparison between PCR and RRR performed under Ivanov regularization. This experiment was designed empirically test the uniform bounds presented in Sec. Again, RRR consistently outperforms the PCR estimator.
recursive relation 1 (4x,, (1 (1-xx)
additive trigonometric noise as defined in [45]. The probability distribution
Table I: Comparison of the estimators proposed in Section on the noisy logistic map.
Estimator
Training error
Test error
D] - >11/|/al
122. Sa.al/ |22.
PCR
0.2 = 0.003
0.18 + 0.00051
9.6 10-5 + 7.2 10-5
0.85 - 0.03
RRR
0.13 4 0.002
0.13 + 0.00032
5. 3.8 10-6
0.16 + 0.1
KRR
0.032 + 0.00057
0.13 + 0.00068
7.9. 5.7 10-7
0.48 = 0.17
The molecule Alanine Dipeptide. We analyse a simulation of the small molecule Alanine dipeptide reported in Ref. [66]. The dataset, here, is time series of the Alanine dipeptide atomic positions. The trajectory spans an interval of 250 ns and the number of features for each data point is 45. The dynamics is Markovian and governed by the Langevin equation [27]. The system supports an invariant distribution, known as the Boltzmann distribution, and the equations are simne-revesallinvarrii latter implies that the true Koopman operator self-adjoint and has real eigenvalues. For Alanine dipeptide it is well known that the dihedral angles play special role, and characterize the state of the molecule. Broadly speaking, we can associate specific regions of the dihedral angles space to metastable states, i.e. configurations of the molecule which are "stable" over an appreciable span of time. To substantiate this claim we point to the left panel Figure From this plot is evident that the molecule spend large amount of time around specific values of the angle v and transitions from one region to another are quite rare. We now try to recover the same informations from the spectral decomposition of the Koopman operator. We train the RRR estimator with rank
The

---

Evolution of the angle
Seed -=
=
4=4 r=5
i
7
9
0
Linear Kemeel
Ditedral angle y
x/2
II
0
/
0
9
9 0
Ganssan Kenel
x/2-
0
2
3 4
5
CNX Kerne
100
Time (06)
Figure 2: Left: dihedral angle vi of the Alanine dipeptide as function of time. Right: comparison of different kernels in the generation of a series of digits. Starting from seed image, the next ones are obtained by iteratively using the rank-10 RRR Koopman operator estimator.
5 and standard Gaussian kernel (length scale L = 0.2). We remark that the dataset is comprised of atomic positions, and not dihedral angles. We show that the computed eigenfunctions are highly correlated with the dihedral angles, meaning that our estimator was able to learn the correct physical quantities starting only from the raw atomic positions. The estimated eigenvalues are X = 0.99920, X2 = 0.7177, À 0.4731, X -0.0042 and À5 -0.0252. Notice that they are all real (as they should be, since the system is www.eveersal-iirrianne the (non-trivial) cigenfunctions corresponding to X2 and A3 in the dihedral angle space. From these plots is clear that the eigenfunctions are to a good approximation piecewise constant and identify different metastability regions, as expected.
In Fig. of App. E.4 we report the plots of
Koopman Operator Regression with Deep Learning Embeddings. To highlight the importance of choosing the kernel, here we consider computer vision setting, where standard kernels (e.g. Matérn or Gaussian), are less suitable than features given by pre-trained deep learning models. We take sequence (Iz))eN of images from the MNIST dataset [14] starting from wi corresponding to an image depicting digit and such that for every x, depicting digit & E (o...., ...,.,,) 9} we sample T(+1 from the set of images depicting the digit e + 1 (mod 10). We compare the rank-10 10 RRR estimators using Linear and Gaussian kernels, with a Convolutional Neural Network (CNN) kernel (0 := (áe (z), d (x')), where de is a feature map obtained from the last layer of convolutional neural network classifier trained on the same images in (ze (Zt)teN. We trained the three Koopman estimators starting from a digit 0. Only the forecasts by the CNN kernel maintain a sharp (and correct) shape for the predicted digits. In contrast, the other two kernels are less suited to capture visual structures and their predictions quickly lose any resemblance to a digit. This effect can be appreciated starting from other digits, too (see App. E).
1000 samples. The right panel of Fig. 2 shows the first 4 forecasting steps
7 Conclusions
We proposed a statistical framework to learn Koopman operators in RKHS. In addition, we inves- tigated how the spectral and modal decompositions of the Koopman estimators approximate the true ones, providing novel perturbation bounds. In particular, we studied three Koopman operator estimators, KRR, PCR and the newly proposed RRR. We observed that KRR and PCR correspond to well-established estimators from the dynamical systems literature. Then, by leveraging recent results from kernel operator learning we observed that such estimators enjoy strong statistical guarantees. provided generalization bounds, both in i.i.d. and non i.i.d.
Focusing on the RRR estimator, settings, one of the key novel contributions of this work.
In this work we consider only time- homo-eoomge dynamical systems admitting an invariant distribu- tion. Weakening these assumptions would allow the study of more general systems. Moreover, the extension of our results to continuous dynamical systems and in general to non-uniformly sampled datapoints deserves further investigations. Finally, the choice of the kernel fundamental for efficient learning. Designing kernel function incorporating prior knowledge of the dynamical system (such as structure of the data points, symmetries, smoothness assumptions etc.) is a topic of paramount interest.
10

---

Acknowledgements: This work was supported in part by the EU Projects ELISE and ELSA. We thank all anonymous reviewers for their useful insights and suggestions.
References
[1] Alexander, R. and Giannakis, D. (2020). Operator-theoretic framework for forecasting nonlinear time series with kernel analog techniques. Physica D: Nonlinear Phenomena, 409: 132520.
[2] Arbabi, H. and Mezić, I. (2017). Ergodic theory, dynamic mode decompasition, and computation of spectral properties of the koopman operator. SIAM Journal on Applied Dynamical Systems, 16(4):2096-2126.
[3] Aronszajn, N. (1950). Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337-404.
[4] Bevanda, P., Beier, M., Kerz, S., Lederer, A., Sosnowski, S., and Hirche, S. (2021). Koop- manizingFlows: Diffeomorphically Learning Stable Koopman Operators. arXiv preprint arXiv.2112.04085.
[5] Bouvrie, J. and Hamzi, B. (2017). Kernel Methods for the Approximation of Nonlinear Systems. SIAM Journal on Control and Optimization, (540)-2460-2492.
[6] Bruder, D., Fu, X., Gillespie, B., Remy, C. D., and Vasudevan, R. (2021). Data-Driven Control of Soft Robots Using Koopman Operator Theory. IEEE Transactions on Robotics, 37(3):948
[7] Brunton, S. L., Budišić, M., Kaiser, E., and Kutz, J. N. (2022), Modern Koopman Theory for Dynamical Systems. SIAM Review, 64(2):229-34)
[8] Budišié, M., Mohr, R., and Mezić, I. (2012). Applied Koopmanism. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(4):047510.
[9] Caponnetto, A. and De Vito, E. (2007). Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 733):331-368.
[10] Carmeli, C., De Vito, E., Toigo, A., and Umanitá, V. (2010). Vector valued reproducing kemnll Hilbert spaces and universality. Analysis and Applications, 8(01):19-61.
[11] Črnjaric-Zic, N., Maćešić, S., and Mezić, I. (2019). Koopman operator spectrum for random dynamical systems. Journal of Nonlinear Science, 30(5):2007-2056
[12] Da Prato, G. and Zabczyk, J. (1996). Ergodicity for Infinite Dimensional Systems. London Mathematical Society Lecture Note Series. Cambridge University Press.
[13] Das, S. and Giannakis, D. (2020). Koopman spectra in reproducing kernel Hilbert spaces. Applied and Computational Harmonic Analysis, 49(2)6573-607.
[14] Deng, L. (2012). The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 1966)1411142.
[15] Fan, F., Yi, B., Rye, D., Shi, G., and Manchester, I. R. (2021). Learning Stable Koopman Embeddings. arXiv preprint arXiv.2 10.06509.
[16] Folkestad, C., Chen, Y., Ames, A. D., and Burdick, J. W. (2021). Data-Driven Lafety-Critical Control: Synthesizing Control Barrier Functions with Koopman Operators. IEEE Control Systems Letters, 2012)220122017.
[17] Fuchs, A. (2012). Nonlinear Dynamics in Complex Systems: Theory and Applications for the Life- Neuro- and Natural Sciences. Springer complexity. Springer Berlin Heidelberg.
[18] Giannakis, D., Henriksen, A., Tropp. A., and Ward, R. (2021). Learning to Forecast Dynamical Systems from Streaming Data. arXiv preprint
[19] Gonzalez, E., Abudia, M., Jury, M., Kamalapurkar, R., and Rosenfeld, J. A. (2021). Anti- koopmanism.
11

---

[20] Gorini, V. and Kossakowski, A. (1976). Completely positive dynamical semigroups of N-level systems. Journal of Mathematical Physies, 17(5):821.
[21] Grünewälder, S., Lever, G., Baldassarre, L.,, Patterson, S., Gretton, A., and Pontil, M. (2012). Conditional mean embeddings as regressors. In Proceedings of the 29th International Conference on International Conference on Machine Learning, pages 1803-1810.
[22] Izenman, A. J. (1975). Reduced-rank regression for the multivariate linear model. Journal of multivariate analysis, 5(2):248-264,
[23] Kawahara, Y. (2016). Dynamic Mode Decomposition with Reproducing Kernels for Koopman Spectral Analysis. In Lee, D., Sugiyama, M., Luxburg. U., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc.
[24] Klus, S., Schuster, L., and Muandet, K. (2019). Eigendecomposiiions of transfer operators in reproducing kernel Hilbert spaces. Journal of Nonlinear Science, 30(1) 30(1):283-315.
[25] Kutz, J. N., Brunton, S. L., Brunton, B. W., and Proctor, J. L. (2016). Dynamic Mode Decompo- sition. Society for Industrial and Applied Mathematics.
[26] Lasota, A. and Mackey, M. C. (1994). Chaos, Fractals, and Noise, volume 97 of Applied Mathematical Sciences. Springer New York.
[27] Lemons, D. S. and Gythiel, A. (1997). Paul langevin's 1908 paper "on the theory of brownian motion" ['sur la théorie du mouvement brownien," " c. acad. sci. (paris) 146. 530-533 (1908)]. American Journal of Physics, (5(11))107--1081
[28] Lindblad, G. (1976). On the generators of quantum dynamical semigroups. Communications in Mathematical Physics, 48(2): 1 19-130.
[29] Luise, G., Stamos, D., Pontil, M., and Ciliberto, (2019). Leveraging low-rank relations between surrogate tasks in structured prediction. In International Conference on Machine Learning. pages 4292-4202.
[30] Lusch, B., Kutz, J. N., and Brunton, S. L. (2018). Deep learning for universal linear embeddings of nonlinear dynamics, Nature Communications, 9(1).
[31] Luzzatto, S., Melbourne, L., and Paccaut, F. (2005). The lorenz attractor is mixing. Communica- tions in Mathematical Physics, 260
[32] Mardt, A., Pasquali, L., Wu, H., and Noé, F. (2018). VAMPnets for deep learning of molecular kinetics. Nature Communications, 9(1).
[33] Maurer, A. and Pontil, M. (2009). Empirical Bernstein bounds and sample variance penalization. In Proc. 22nd Anmual Conference on Learning Theory.
[34] Maurer, A. and Pontil, M. (2013). Excess risk bounds for multitask learning with trace norm regularization. In Conference Learning Theory, pages 55-76.
[35] Mauroy, A., Mezić, I., and Susuki, Y., editors (2020). The Koopman Operator in Systems and Control. Springer International Publishing.
[36] McCarty, J. and Parrinello, M. (2017). A variational conformational dynamics approach the selection of collective variables in metadynamics. The Journal of Chemical Physics, 147(20):204109,
[37] Meanti, G., Carratino, L., Rosasco, L., and Rudi, A. (2020). Kernel methods through the roof: handling billions of points efficiently. Advances in Neural Information Processing Systems, 33:14410-14422.
[38] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Communica- tions and Control Engineering. Springer London.
[39] Mezić, I. (2019). Spectrum of the koopman operator, spectral expansions in functional spaces, and state-space geometry. Journal of Nonlinear Science, 200
12

---

[40] Minsker, S. (2017). On some extensions of Bernstein's 's inequality for self-adjoint operators. Statistics & Probability Letters, 127:111-119.
[41] Mnih, V., Szepesvári, C., and Audibert, J.-Y. (2008). Empirical Bernstein stopping. In Proc. 25th International Conference Machine Learning, pages 672-679
[42] Mollenhauer, M., Schuster, Klus, S., and Schütte, C. (2020). Singular value decomposition of operators on reproducing kernel Hilbert spaces. In Junge, O., Schütze, O., Froyland, G., Ober-Blöbaum, S., and Padberg Gehle, K., editors, Advances in Dynamics, Optimization and Compulation, pages 109-131, Cham. Springer International Publishing.
[43] Muandet, K., Fukumizu, K., Sriperumbudur, B., and Schölkopf, B. (2017). Kernel Mean Embedding of Distributions: A Review and Beyond. Foundations and Trends@ in Machine Learning, 10(1-2):1-14.
[44] Mukherjee, A. and Zhu, J. (2011). Reduced rank ridge regression and its kernel extensions. Statistical analysis and data mining: the ASA data science journal, 4(6):612-62
[45] Ostruszka, A., Pakoński, P., Stomczyáski, W., and Zyczkowski, K. (2000). Dynamical entropy for systems with stochastic perturbation. Physical Review E, 62(2))
[46] Pascucci, A. (2011). PDE and Martingale Methods in Option Pricing. Springer Milan.
[47] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V.. Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2:2825-2830.
[48] Proctor, J. L. and Eckhoff, P. A. (2015). Discovering dynamic patterns from infectious disease data using dynamic mode decomposition. International Health, 1(2):139-145.
[49] Reed, M. and Simon, B. (1980). I: Functional Analysis. Academic Press.
[50] Riley, K. F., Hobson, M. P., and Bence, S. J. (2006). Mathematical Methods for Physics and Engineering. Cambridge University Press.
[51] Rosenfeld, A., Kamalapurkar, R., Gruss, L. F., and Johnson, T. T. (2021). Dynamic mode decomposition for continuous time systems with the liouville operator. Journal of Nonlinear Science, 32(1).
[52] Rowley, C. W., Mezić, I., Bagheri, S., Schlatter, P., and Henningson, D. S. (2009). Spectral analysis of nonlinear flows. Fluid Mech., 641:115-127.
[53] Schütte, C., Huisinga, W., and Deuflhard, P. (2001). Transfer Operator Approach to Conforma- tional Dynamics in Biomolecular Systems. In Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, pages 191-223. Springer Berlin Heidelberg.
[54] Song, L., Huang, J., Smola, A., and Fukumizu, K. (2009). Hilbert space embeddings of conditional distributions with applications dynamical systems. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 961-968.
[55] Steinwart, I. and Christmann, A. (2008). Support Vector Machines. Springer New York.
[56] Stewart, G. W. (1971). Error bounds for approximate invariant subspaces, of closed linear operator. SIAM Journal on Numerical Analysis, 8(4):796-80.
[57] Stewart, G. W. and Sun, J.-G. (1990). Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic Press.
[58) Strogatz, S. (2014). Nonlinear Dynamics and Chaos: Chemistry, and Engineering. Studies in Nonlinearity, Avalon Publishing.
With Applications to Physics, Biology,
[59] Trefethen, N. and Embree, M. (2020). Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press.
13

---

[60] Tucker, W. (1999). The lorenz attractor exists. Comptes Rendus de l'Académie des Sciences Series 1- Mathematics, 328(12):1197-12)
[61] Vapnik, (1998), Statistical learning theory. Wiley,
[62] Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press.
[63] Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, I., Feng, Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E. A.. Harris, C. R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F., van Mulbregt, P., and SciPy 1.0 Contributors (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272.
[64] Walcek, C. J. (2002). Effects of wind shear on pollution dispersion. Atmospheric Environment, 36(3):511-517.
[65] Wang, W. and Zhou, Y.H. (2020). Reduced Rank Multivariate Kernel Ridge Regression. arXiv preprint arXiv:200.001559
[66] Wehmeyer, C. and Noé, (2018). Time-lagged autoencoders: Deep learning of slow collective variables for molecular kinetics. J. Chem. Phys., 148:241703.
[67] Williams, M. O., Rowley, C. W., and Kevrekidis, I. G. (2015). A kernel-based method for data-driven Koopman spectral analysis. Journal of Computational Dynamics, 2(2):247-265.
[68] Yu, B. (1994). Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pages 116.
[69] Zhang, S., Guo, B., Dong, A., Hc, J., Xu, Z., and Chen, S. X. (2017). Cautionary tales air-quality improvement Beijing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473(2205):20170457.
Checklist
1. (a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. (a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. (a) Did you include the code, data, and instructions needed to reproduce the main experi- URL.? [Yes]
mental results (either in the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. (a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
14

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. (a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "x1uz90Joxej", "reviewer": "Reviewer_Sfxe", "summary": "In this paper, entitled \"Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces\", the authors connect the popular and successful theory of Koopman operator theory (and the numerical tool dynamic mode decomposition [DMD]) with statistical learning. This enables a new way to view the estimation of the spectral decomposition of the Koopman operator. In addition, the authors develop new approaches to approximate this spectral decomposition, and find learning bounds for such methods that hold for both i.i.d. and non i.i.d. dynamical systems. ", "questions": "I have no additional questions other than the ones asked in the Strengths and Weakness section above. ", "limitations": "The authors did a nice job making it clear where their work required the samples to be i.i.d., and where they did not. I especially appreciated that they had some bounds in the non i.i.d. setting. \n\nAs the author's illustrated at the end of Sec. 6, the choice of kernel is very important. The authors mention this, but it would be helpful to have additional discussion around this. \n\nThe authors compared their proposed numerical methods to a standard approach PCR. However, there are other existing methods that they could also compare against. While I do not think the author's need to exhaustively test their proposed methods against these, I do think they should mention the existence of these other approaches (e.g. Extended DMD, Hankel-DMD) and be up-front with the fact that how their proposed method compares is unknown. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS:\n1. This paper provides a novel connection between Koopman operator theory and statistical learning theory. The authors convincingly demonstrate that this can be leveraged to not only provide a new view on approximating the Koopman mode decomposition, but also inspires new numerical methods for computing such approximation. Given that many of the problems that the community of researchers who use Koopman for forecasting and analysis fit very naturally into this statistical learning framework, I believe this work will be of considerable interest. \n\n2. The bounds developed in the case of the non i.i.d. case represent an exciting direction that I believe the community will be excited about pursuing. \n\n3. The theoretical development of Secs. 3, 4, and 5 are well done. In addition, the appendices provide considerable additional material and background. \n\n4. The emphasis in Sec. 6 on how the proposed numerical methods could improve BOTH forecasting and analysis was appreciated. Not only does it provide support that this framework will be generally useful, but reminds the reader that Koopman operator theory is not just a tool for prediction. \n\nWEAKNESSES:\n1. I found the results on the Beijing Air Quality data set somewhat hard to interpret and lacking a real punch. While I understand that wind would disperse PM2.5, why would there be a consistent period over which peaks of PM2.5 would precede peaks in wind speed? It is mentioned that this is in-line with what was argue in Ref. [52], but that paper \"argues that pollution concentration is fully readjusted on the basis of wind conditions already after 4 hours\". I didn't get how that was related or how the 2 hour estimate found by the Koopman regression agrees with the 4 hour estimate of Ref. [52]. I'm wondering if there might be another result in the data set that would be more interesting and conceptually more straightforward. Are there any modes where the distance between stations is correlated with their corresponding magnitude in the mode? If not, maybe it'd be worth while looking at another data set (like the Washington DC bike share data set) to find something that makes it especially clear what benefits the proposed methods can bring for analysis. \n\n2. In Sec. 6, a nice example of the importance of choosing the kernel is provided. This then makes me want to hear more about the choice of kernels. How should one go about choosing a kernel? For the noisy logistic map and the Beijing Air Quality data, what led the authors to choose the kernel they did? Do other kernels perform differently? This is, of course, a problem in any kernel method, but I think since the author's illustrate its importance, it is necessary to provide a little more discussion on this consideration. \n\nLikewise, how did the author's determine the rank constraint (r)? The value is given, but without any intuition or explanation.\n\n3. The paper was lacking a few references that I thought were relevant and important. In particular, there has been a decent amount of work done recently on Koopman operator theory in reproducing kernel Hilbert spaces. While some of these references were included, the following were not: \n   - Gonzalez, et al. 2021 (https://arxiv.org/abs/2106.00106)\n   - Mezić, 2020 (https://link.springer.com/article/10.1007/s00332-019-09598-5)\nAdditionally, inclusion of reference to work on Koopman operator theory for random dynamical systems [Črnjarić-Žic et al., 2020 (https://link.springer.com/article/10.1007/s00332-019-09582-z)] and Koopman operator theory in relation to learning [Mezić, 2022 (https://arxiv.org/abs/2010.05377)] would be helpful for giving the reader a larger picture view of what is already known. \n\n4. The nature of $Z_1, ..., Z_m$ in Lemma 1 is confusing to me.  If they are identical copies, why not represent it as $m Z_1$? I think I'm missing something here. \n\nMINOR POINTS:\n1. It would be helpful to define what mixing, with respect to Markov chains is.\n\n2. DMD is one class of methods for approximating the Koopman mode decomposition. There are others (e.g. Generalized Laplace Analysis). Therefore, lines 148-149 should be changed to reflect this. \n\n3. The origin of the square root dependence of R in Eq. 6 is not very clear to me. It would be helpful to provide a sentence or two on why we might expect it to be the case. \n\n4. Do you mean \"error increases\" as opposed to \"error degrades\" in line 163?  \n\n5. $k(x, \\cdot)$ should be defined before it is used (line 183). \n\n6. Should Eq. 13 have an $<$ sign instead of an equality? \n\n7. It should be \"using\" instead of \"use\" on line 256. \n\n8. ERM should be defined before it is used in line 273. \n\n9. It should be \"shown\" instead of \"showed\" on line 323.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "wXSrbPAc_1M", "reviewer": "Reviewer_VeMo", "summary": "This paper introduces a class of algorithms to learn dynamical systems from observation data. One of the common approaches for this problem is to rely on Koopman operator theory, giving algorithms related to the well-known Dynamic Mode Decomposition (DMD). Here, the authors work in the setting of stationary (discrete time) Markov chains with a continuous state. In this framework, they analyze the problem of approximating the (stochastic) Koopman operator when the hypothesis space is that of Hilbert-Schmidt operators over a RKHS, from a statistical learning perspective. They study how to define a notion of risk for this problem, show connections to the usual one-step-ahead prediction error which is often used to learn such dynamic representations. They introduce several algorithms generalizing existing approaches, and study a number of its theoretical properties, such as the approximation capabilities of the risk minization, what happens for the empirical risk estimation and derive learning bounds in that case. They also address the (usual case) of when the data are not only pairs (x_t, x_t+1) sampled at random points, but a full trajectory with regular sampling, in which case the effective sample size is reduced. An experimental part shows how the proposed method perform to approximate the actual Koopman operator for a version of the logistic map, and prediction capabilities for a real time series dataset and a dynamic version of the MNIST data.", "questions": "- Maybe the authors could provide practical examples of systems satisfying some of the key hypotheses or not (e.g. discrete/continuous time, existence of a stationary distribution, stochasticity or not, time homogeneity of the markov chain, time reversibility that makes the spectral analysis easier), or state which ones are satifsied in the experiments.\n\n- What is Ivanov regularization compared to Tikhonov (mentioned in Sec. 5)\n\n- How hard would it be to test the sharpness of the learning bounds on the logistic map case ? I believe it would make for an interesting experimental analysis, as a function of the number of trajectories, the time, the rank of the operator, the kernel, etc\n\n- Similarly, indicating the complexity as a function of the number of samples and other factors (rank…) would be interesting.\n\n- In table 1, it looks like KRR is overfitting the training data, while obtaining comparable performance on test data to RRR (except on the eigenvalues estimation). How do the authors explain this behavior and the fact that low rank is preferable here?", "limitations": "The authors did not discuss specifically limitations, but the working hypotheses are clearly stated. As such, the analysis is limited to discrete time systems, which does not seem that big a problem, though it would have been nice to test the approaches on data arising from the integration of ODEs.    The complexity of the algorithms are not discussed directly either, it would help having an idea of how well the method would scale to larger data. These limitations are relatively minor and the depth of the results presented here is extensive already.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths :\n\n- The authors introduce a very nice theoretical framework to study Koopman operators as Hilbert Schmidt operators, allowing to endow a norm to the space of bounded operators (of finite rank) on a Hilbert space, corresponding to the space of observables. This in turns allows to precisely define a notion of risk in this case, that is consistent with intuition. Overall the theoretical analysis is extensive and well presented.\n\n- They show the approximation capabilities of such a framework (in terms of approximation of the operator, and the corresponding spectrum) and derive learning bounds, both in expectation and in the empirical case, including in the (susual in practice) non i.i.d. case.\n\n- There are clear connections with existing approaches aimed at learning dynamical systems from data, among them the classical (kernel) DMD. The framework encompasses and unifies these different approaches nicely.\n\n- The kernel point of view is not restrictive since in practice it can correspond to features learned by a neural network, which is a common strategy when learning dynamical systems from data.\n\nWeaknesses :\n\n- The framework that is introduced is limited to discrete time dynamical systems, which is sufficient in most cases. I wonder how hard it would be to extend all the theory to continuous time systems. I am not that familiar with continuous Koopman operator theory but maybe the authors could discuss this and the additional difficulties that would arise.\n\n- The experimental part, though interesting, only considers one non-standard real dataset. While I appreciate the application to real data, it feels like the paper would benefit having experiments of standard benchmarks in the field, e.g. the Lorenz-63 model (possibly noisy, as e.g. in [1]), or other systems arising from differential equations.\n\n- On a related note, the three competing methods (PCR, RRR,KRR) can all be interpreted in the proposed theoretical framework, which is nice, but other classical approaches could have been compared, e.g. more empirical deep-learning based estimations of a Koopman operator, e.g. ref [27] in the paper. It would have been nice to position such works, if possible, within the framework that is proposed here.\n\n[1] Li, X., Wong, T. K. L., Chen, R. T., & Duvenaud, D. (2020, June). Scalable gradients for stochastic differential equations. In International Conference on Artificial Intelligence and Statistics (pp. 3870-3882). PMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nQjuCSqODdf", "reviewer": "Reviewer_bVru", "summary": "The paper provides the formalism and statistical learning theory of learning a dynamical systems in RKHS where the problem of estimating the Koopman Operator in the Hilbert space turns into a nonparametric kernel regression. The mathematical framework encompasses DMD and kernel DMD as special cases and enjoys the connections to classical conditional mean embeddings where some developed theory already exists. Based on the formalism several estimators for the Koopman Operators are provided and the advantages of Reduced Rank Regression (RRR) estimator over others are discussed. Finally some experiments on toy data and sequential generation of MNIST digits are provided showing that deep learning kernels can be plugged into the algorithms for the kernel regression.", "questions": "**Numbers are line numbers in PDF**\n\n77 Is the transition kernel simply the conditional probability distribution $p(X_{t+1}|X_t)$?\n\n79 In Eq. 1, I hadn't seen the notation $p(x,dy)$; is it the same as $p(x,y)dy$? Can you clarify this or change the notation?\n\n101 I don't quite understand the decomposition described in Eq. 2. I thought after lifting nonlinear dynamical system using the observables the Koopman Operator evolves the dynamics in the lifted space linearly. If this is the case then why is there a superscript $t$ on the left side and what do the $\\lambda_i^t$'s correspond to?\n\n108 interested into -> interested in\n\n121 Why do we approximate $Z_{\\pi}$ via $S_{\\pi}G$ and not with $G$ itself if we want $Z_{\\pi}$ to be a  Hilbert Schmidt operator?\n\n129 Multiple measures are introduced throughout the paper making it confusing; $\\rho,p,\\pi,dx,dy$ can you clarify in words what each of these means?\n\n147 later -> latter\n\n164 the error degrades as t increases ... forecasting will gets [get] increasingly harder for larger t; aren't these two in contradiction?\n\n160 How should we interpret the RHS of Eq. 7 and the bound in line 160? Aren't we expecting these to vanish with $r \\rightarrow \\infty$?\n\n175 Remark 2 is providing other bounds for normal $A_{\\pi}$ and $G$ but still it's not clear that the error vanishes for large $r$.\n\n194 In Eq. 10, the function $\\phi$ is imposed by the choice of the kernel; while this is common in kernel regression problems, I thought that the nonlinear dynamical system dictates the what the Koopman Operator observables or lifting function are; meaning that the choice of kernel is not arbitrary; can you clarify this?\n\n248 In Thm. 3, the error again doesn't seem to go zero with n going to infinity, isn't expected for the error to vanish with large data size? Same for Prop. 2 and 3.\n\n", "limitations": "* Empirical validation of the theoretical results and bounds.\n* Tighter bounds going to zero with increased approximation precision or data size.\n* Complex notation with minimal intuitive arguments helping the reader going through the logical flow of the mathematical arguments.\n* Limited experiments on toy examples.\n\n**After rebuttal**\n\n* New experiments address my first and last points.\n* My second point was a technical oversight on my side, no action in needed from authors' side.\n* I still think that the notation is too heavy and makes it hard to follow the arguments on an intuitive level for the broader community.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* The proposed contributions are significant and natural next steps of the transport operator theory. The empirical risk minimization helps providing a statistical foundation to learning dynamical systems using Koopman Operators. It further allows for the extension of existing kernel regression methods for learning dynamical systems as proposed by the authors.\n\n* The paper is mathematically rigorous, theorems are accompanied with proofs and statistical bounds are given providing statistical guarantees.\n\n\n**Weaknesses**\n\n* Overall the notation is too complex and heavy, I would suggest communicating the main ideas through a lighter notation and moving the full notation to the supplementary. More comments about the notation are in the questions section.\n\n* The experimental part of the paper is quite limited. Although I understand that most of the contributions of the paper are theoretical but I think some of the mathematical notation can be moved to the supplementary and more experiments can be added to 1) confirm the theoretical results empirically by plotting the errors for known cases as a function of r, data size, and other variables 2) show applications in time series which is the main motivation of the theoretical developments in the paper 3) compare different Koopman Operator estimation methods with existing ones such as extended DMD and the neural net-based ones. At least a discussion on under what circumstances kernel based methods should be preferred to existing ones would be helpful.\n\n* Some of the bounds provided are quite loose and they don't vanish with infinite data or infinite rank precision. Am I missing something or are the bounds indeed weak?\n\n* There are a few mentions of statistical guarantees missing from dynamical systems literature. I don't know to what extent this is true given that many statistical time series methods are developed (such as variants of HMM, LDS, SLDS, etc.) with their corresponding theoretical bounds and inference algorithms. Can the authors be more clear about what they exactly mean by this and also include a short summary of the above-mentioned methods and how they compare to Koopman Operator based methods?\n\n* In table 1 the $\\lambda_{2,3}$ error seems pretty large, shouldn't we expect to see excellent performance on this toy example? Also can the authors report the relative errors instead of the absolute ones?\n\n* In Fig. 1, why are the images so blurry even for the CNN kernel?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CVlTrQ9T2J", "reviewer": "Reviewer_bsCx", "summary": "In this paper the question of learning the Koopman operator of a Markov chain from samples is studied. \n\n* It is proposed to introduce an appropriate RKHS $\\mathcal{H}$ and to restrict the domain of the operator to be $\\mathcal{H}$, \nwhile the image would still be in the full $L_2(\\pi)$ where  $\\pi$ is the stationary measure of the chain. \n* This has the advantage that such a restriction is compact and hence can be approximated by finite dimensional operators. \n\n* A risk measure is introduced which measures the quality of the approximation. This measure is equivalent to a risk used in the field of Conditional Mean Embeddings. \n\n* The main novelty is that in this framework it is proposed to approximate the Koopman operator by a finite dimension operator that minimizes the risk, and is regularized by the Hilbert Schmidt norm as an operator $\\mathcal{H} \\mapsto \\mathcal{H}$. This is different from kernel PCA approximation, for instance. \n\n* Results are proved on matrix stability (i.e. small risk implies closeness of eigendecompositions in a certain sense), and generalization properties for the above finite rank regularized operator empirical risk minimization.   \n\n", "questions": "Please see the questions above. \n\n\n**EDIT Post rebuttal and discussion**\n\n\n**1 -  Novelty**\n\n\nIt is important to note that studying dynamical systems in RKHS is not new. \nCompletely equivalent setting, with equivalent risk function, is studied in the field of Conditional Mean Embeddings (CME), which by now is a well developed field.  This is discussed in the paper in Remark 3, and in lines 189-191 in particular. \n\n**1a)** This has consequences, since experiments need to present comparison to other methods. In particular the KRR and PCR. Experiments on Beijing Air Quality data,  and Alanine Dipeptide do not do this (no comparison to KRR) and thus contribute very little to establishing novelty. Other experiments are discussed in what follows. \n\n**1b)**  What is new, is the proposal to minimize the risk among low rank operators $G$, i.e. eq. (12). \n The authors study this proposal in three parts:   \n   * **1b1)** How properties of $G$ translate to properties of true Koopman operator (Theorem 1).\n   * **1b2)** How empirical risk relates to true risk for this approximation (Theorem 3). \n   * **1b3)** Some experiments with this approximation. \n   \nWe now discuss the issues.\n\n**2 - Issues**\n\nThe paper has a critical problem in points (1b1) and (1b2) above.\nSpecifically, in Theorem 1 it is shown that properties related to spectral decomposition of the true  operator can be reconstructed from $G$ if all the quantities $\\|G\\|$, $\\|Gf\\|$ and risk $R(G)$ are small. \n   \n   \n**2a)** However, as pointed out in my review, *and confirmed by the authors*, there is no apriori reason \n       why these quantities should be small. They can be arbitrarily large, no matter how large the rank $r$ is. \n       As a consequence, it may happen that $G$ is useless for reconstructing the true operator. \n\nSimilarly, the quantity $|G|_{HS}$ is key in Theorem 3 (via $\\gamma$). It is not clear that both risk and $|G|_H$ can be \nsmall together. This also is not sufficiently investigated empirically. \n       \n**2b)** In their response to the review, the authors state a new result, that the above issue does not happen \n       when the true Koopman is self-adjoint. However, Koopman operators are almost never self-adjoint. \n       This, for instance, is *explicitly* stated in reference [A] below, see third paragraph of Section 2.2.\n       \nThis is a standard fact, and the authors should have been aware of this. \n\nNote also that even if $\\|G\\|$ were small, as the authors claim in the self-adjoint case, this does not solve the issue of Theorem 3 with $\\|G\\|_{HS}$.\n   \n**2c)**  Note that when the true operator is not known, Theorem 1 is the only basis upon which one may conclude that  $G$ represents the true operator. Moreover, while there is no aprori way to bound $\\|G\\|$, $\\|Gf\\|$ and  $R(G)$, these bounds may be computed empirically. \n       \n Thus, all that is needed, is to present experiments where we see that empirically, the quantities $\\|G\\|$,$\\|G\\|_{HS}$, $\\|Gf\\|$ and  $R(G)$ take values that imply practical  bounds in Theorems 1,3.\n       \nHowever, there is not nearly enough experimental evidence that Theorems 1,3 are useful, and and consequently that the paper is useful. \n       \nI am not completely convinced that indeed the quantities can be small in realistic situations. To put it simply, working in RKHS instead of the full function space $L_2$, has computational advantages. However, it has also a price, that the $G$ norm can explode. The authors failed to verify that there exist useful situations where the price is not too high. \n       \n\nTherefore in my opinion this paper should not be accepted.\n      \n\n\n[A] Mauroy, Alexandre and Susuki, Yoshihiko and Mezi{\\'{c}}, Igor, \n    Introduction to the Koopman Operator in Dynamical Systems and Control Theory,\n    The Koopman Operator in Systems and Control: Concepts, Methodologies, and Applications,2020,\n    Springer International Publishing.\n\nopen access at: https://link.springer.com/chapter/10.1007/978-3-030-35713-9_1\n\n\n\n\n", "limitations": "No discussion of negative societal impact was included. ", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a well written paper, and the idea using the kernel in this way is elegant. \n\nAt the same time, I believe the paper would benefit significantly from additional empirical evaluation. \n\nTo better understand the significance of the results, and the theoretical novelty, I have the following questions.\nBased on this, I will be glad to reevaluate the review following the author feedback period. \n\n1) In Proposition 1, it is shown that there is always a finite rank operator $G$ making the risk arbitrary small. \nHowever, the norm of $G$ as an operator $\\mathcal{H} \\mapsto \\mathcal{H}$ can become arbitrarily large. Is this correct?\n\n2) In Theorem 1, are the norms that are used for $\\|Gf\\|$ and $\\|G\\|$ norms in $\\mathcal{H}$? \n3) In that case, when rank $r$ grows, is it even clear that the bounds go to $0$? This is not obvious, since when the rank grows, \n the risk would go to $0$, but the norm of $G$ can grow to infinity. Correct?\n  Then, is the only way to determine whether the bounds are non-trivial empirical? I.e computing the norm and using generalization bounds?\n\n4) Can the authors describe the novelty/difference in methods used to show generalization results, compared to existing literature on CME? \n\n5) It is claimed (line 260) that the proposed RRR should have better risk than the PCR estimator for the same HS norm. While this is reasonable, I would expect this do be verified experimentally, since this is the proposed novelty of the paper. \nSimilarly, in view of question 3 above, it is not clear there exist $G$ with small rank, risk, and HS norm. This should be shown empirically. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept