Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
Authors: Suhas S Kowshik
Dheeraj Mysore Nagaraj
Prateek Jain
Praneeth Netrapalli
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Non-Linear Dynamical Systems
Learning with Dependent Data
Streaming Algorithms
Experience Replay

Abstract: We consider the setting of vector valued non-linear dynamical systems $X_{t+1} = \phi(A^{*} X_t) + \eta_t$, where $\eta_t$ is unbiased noise and $\phi : \mathbb{R} \to \mathbb{R}$ is a known link function that satisfies certain {\em expansivity property}. The goal is to learn $A^{*}$ from a single trajectory $X_1,\cdots , X_T$ of {\em dependent or correlated} samples.
	While the problem is well-studied in the linear case, where $\phi$ is identity, with optimal error rates even for non-mixing systems, existing results in the non-linear case hold only for mixing systems. In this work, we improve existing results for learning nonlinear systems in a number of ways: a) we provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) we significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting we study a SGD with Reverse Experience Replay (SGD-RER) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) we justify the expansivity assumption by showing that for the popular ReLU  link function --- a non-expansive but easy to learn link function with i.i.d. samples --- any method would require exponentially many samples (with respect to dimension of $X_t$) from the dynamical system. We validate our results via. simulations and  demonstrate that a naive application of SGD can be highly sub-optimal. Indeed, our work demonstrates that for correlated data, specialized  methods designed for the dependency structure in data can  significantly outperform  standard SGD based methods. 

Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
Prateek Jain Google Al Research Lab, Bengaluru, India 560016
Suhas Kowshik Department of EECS MIT, Cambridge, MA 02139 suhask@mit. edu
prajainggoogle.com com
Dheeraj Nagaraj Department of EECS MIT, Cambridge, MA 02139 dheeraj @mit t. edu
Praneeth Netrapalli Google AI Research Lab, Bengaluru, India 560016 pnetrapalli@google. com
Abstract
We consider the setting of vector valued non-linear dynamical systems X 6(A* X,) + hh, where is unbiased noise and Φ TR - IR is a known link function that satisfies certain expansivity property. The goal to learn A" from a single trajectory XI,,.. Xr of dependent correlated samples. While the problem is well-studied
linear case, where is identity, with optimal error rates even for non-mixing systems, existing results in the non-linear case hold only for mixing systems. In this work, we improve existing results for learning nonlinear systems number of ways: a) we provide the first offline algorithm that can learn non- -on-iinear dynamical systems without the mixing assumption, b) we significantly improve upon the sample complexity of existing results for mixing systems, in the much harder one-pass, streaming setting we study a SGD with Reverse Experience Replay (SGD RER) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) we justify the expansivity non-expansive
assumption by showing that for the popular ReLU link function but easy to learn link function with i.i.d. samples - any method would require exponentially many samples (with respect to dimension of X;) from the dynamical system. We validate our results via simulations and demonstrate that a naive application of SGD can be highly sub-optimal. Indeed, our work demonstrates that for correlated data, specialized methods designed for the dependency structure in data can significantly outperform standard SGD based methods.
Introduction
Non-linear dynamical systems (NLDS) are commonly used model the data variety of domains like control theory, time-series analysis, and reinforement learning (RL.) (14. Standard NLDS models the data points (Xp, X1,..., Xr) as:
X = 6(Axx,) + Th
(1)
where X, E Rd are the states, 1). E Rd are i.i.d. noise vectors, A E Rdxd and Φ R - R is an increasing function called the 'link function'. Here, is supposed act component wise over Rd.
System identification problem is foundational problem for NLDS, i... given (Xo, Xi.... XI...., XT) generated from I the goal is to estimate A' accurately from single trajectory (Xo, XI,..., XT). 35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The system identification problem is heavily studied in control theory [5 as well as time-series analysis D. For instance. the non-linear dynamical system considered here has an application in modeling non-linear distortions in power amplifiers [0]]. The problem is challenging as data points Xo, X1,..., XT are not i.i.d. as usually encountered in machine learning, but form a Markov process, If the mixing time Tmix of the process is finite (Tmix < oo). then we can make the data approximately i..d. by considering only the points separated by O(Tmix) time. While this allows using standard techniques for i...d data, it reduces the effective number of samples to O - which typically gives an error of the order O (miss ). In fact, even the state-of-the-an results have error bounds which are sub-optimal by a factor of Tmix-
Time
Interestingly, for the special case of linear systems, i.e., when σ(x) z. the results are significantly stronger. For example, [T] 12] showed that the matrix A can be estimated with an error O(1/T) even when the mixing time Tmix > T. But these results rely on the fact that for linear systems, the estimation problem reduces to an ordinary least squares (OLS) problem for which a closed form expression is available and can be analyzed effectively.
On the other hand, NLDS do not admit such closed form expressions. In fact the existing techniques mostly rely on mixing time arguments to induce i.i.d. like behavior in a subset of the points which leads sub-optimal rates by Tmix factor. Similarly, a direct application of uniform convergence results [3] to show that the minimizer of the empirical risk is close to the population minimizer still gives sub-optimal rates as off-the-shelf concentration inequalities (cf. (I4) incur an additional factor of mixing time. Finally, existing results are mostly focused on offline setting, and do not apply to the case where the data points are streaming which is critical in several practical problems like reinforcement learning (RI.) and control theory.
In this work, we provide algorithms and their corresponding error rates for the NLDS system identification problem in both offline and online setting, assuming the link function to be expansive (Assumption [ The main highlight of our results that the error rates are independent of the mixing time Tmix which to the best of our knowledge is first such result for any non-linear system identification in any setting. In fact, for offline setting, our analysis holds even for systems which do not mix within time T and even for marginally stable systems which do not mix at all. Furthermore, we analyze SGD-Reverse Experience Replay (SGD-RER) method, we provide the first streaming method for NLDS identification with error rate that is independent of Tmix (in the leading order term) while still ensuring small space and time complexity. This algorithm was first discovered in the experimental RL setting in [15] based on Hippocampal reverse replay observed in biological networks
[6118] It was introduced independently in [9] for the case of linear systems and efficiently unravels the complex dependency structure present in the problem. Finally, through a lower bound for ReLU- a non-expansive function-we provide strong justification for why expansivity might be necessary for non-trivial result.
Instead of mixing time arguments, our proofs for learning NLDS without mixing use natural exponential martingale of the kind considered in the analysis of self normalized process ([20) 21
For streaming setting, while we do use mixing time arguments (proof of Theorems 2 and 3) we
combine them with a delicate stability analysis of the specific algorithm and the machinery developed
in [19 to obtain strong error bounds. See Section 6 for a description of these techniques.
Our Contributions. Key contributions of the paper are summarized below:
1. Assuming expansive and monotonic link function á and sub-Gaussian noise, we show that the offline Quasi Newton Method (Algorithm [ estimates the parameter A with near optimal errors of the order OLLTT), even when the dynamics does not mix within time T.
2. Assuming mixing NLDS, finite fourth moment on the noise, and expansive monotonic link function, we show that offline Quasi Newton Method again estimates the parameter A" with near-optimal error of O(1/T), independent of mixing time Tmix-
3. We give one-pass, streaming algorithm inspired by SGD RER method by 19., and show that it achieves near-optimal error rates under the assumption of sub-Gaussee aab-auussian noise, NLDS stability (see section 2. for the definition), uniform expansivity and second differentiability of the link function.
We then show that learning with ReLU link function, which is non-expansive but known to be easy to learn with if data points are all i...d. [22). requires exponential (in d) many samples.

---

We believe that the techniques developed in this work can be extended to provide efficient algorithms for learning with dependent data more general settings.
Related Works. NLDS has been studied in a variety of domains like time-series and recurrent neural networks (RNN). 9 studies specifie NLDS models from a time series perspective and establishes non-asympiotic convergence bounds for natural estimators; their enror rates suffer from mixing time factor mixx-
23 considers asymptotic learning of NLDS via neural networks trained
using SGD, whereas [2 shows that overparametrized LSTTs trained with SGD learn memorize
the given data. [25 27 consider learning dynamical systems of the form 1++1 = (A4h,, + B²)
study. (28 for states h, and inputs wes this setting is different from standard NLDS model
considers the non linear dynamical systems of the form T++1 Ao(æ,, U³) + T) which 6 is known non-linearity and matrix A is be estimated. [29 30 consider essentially linear dynamics but allow for certain non-linearities that can be modeled as process noise, All these again differ from the model we consider.
Standard NLDS identification (I has received a lot of attention recently, with results by [31 32 being the most relevant. [31 uses uniform convergence results via. mixing time arguments to obtain parameter estimation error for offline SGD. 32 obtains similar bounds via. the analysis of the GLMtron algorithm (33. However, both these works suffer from sub-optimal dependence on the mixing time. We refer to Table for a comparison of the results.
(44, which appeared after the initial manuscript of this work, considers the question from a perspective of time series forecasting. This work considers sparsity in A and an unknown link function which is estimated with isotonic regression. Their recovery guarantees eschew the mixing time dependence. However, the setting, assumptions and the error rates are incomparable to our setting.
32 also obtains within sample prediction error in the case when @ is not uniformly expansive along with parameter recovery bounds when é is the ReLU function and the driving noise is Gaussian. However, the parameter estimation bounds for ReLU suffer from an exponential dependence on the dimension d and mixing time miix- In Theorem 4 we establish that indeed we cannot improve the exponential dependence in the dimension d for the case of parameter estimation. We note that the exponential dependence arises due to the dynamics present in the system since ReL U regression with isotropic i.i.d. data in well specified case has only a polynomial dependence in d (22).
Linear system identification (LSI) literature has been well studied with strong minimax optimal bounds 11 35 36). These results primarily consider the (convex) empirical square loss which has a closed form solution. However, the square loss in the non-linear case is non-convex. Under the assumption that the link function is increasing, we consider convex proxy loss which is widely used in generalized linear regression literature [22 33 37]. Similarly, GtMMro algorithm for learning NLDS in 32 (see Equation (3)) also considers similar proxy loss. In 38 the authors consider family of GLMtron-like algorithms call Reflectron under the i.i.d. data setting. But they compare the performance of these algorithms experimentally
NLDS similar to considered in this work under low rank assumption on the system matrix.
Finally, streaming setting for LSI has been recently studied in different model settings 19 39 These methods observe that by exploiting techniques like experience replay ((40)) along with squared loss error, one obtain strong error rates. SGD RER method studied in this work is inspired by similar method by 19 which was primarily studied for the linear case.
2 Problem Statement
Let Φ IR + R be an increasing, 1- 1-Lipschitz function such that (0) = 0. Suppose Xo E Rd is a random variable and A E Rddxd We consider the following non-linear dynamical system (NLDS):
X = = + T/
where the noise sequence il..... ,r is i.i.d random vectors independent of Xy- The noise ny is such that Eni- 0, En,, = o²1 for some a > O. We will also assume that M2 := E|[me|l* < co. Let j be the law of noise n). We denote the model above as NLDS(A*, μr, Φ). Whenever a stationary distribution exists for the process, we will denote it by x(A", n, Φ) or just π when the process is clear from context. We will call the trajectory Xo, XI...., XT 'stationary" if X, is distributed according to the measure a (A", n, Φ). Unless specified otherwise, we take Xo = 0 almost surely.
3

---

Paper
Guarantee
Link Function
System
Noise
Algorithm
Prais T
INCREASING, INCRHASING.LPSCCHIZZ LIPSCHITZ
THEOREM 6.2
EXPANSIVE
MIXING
SUB-GALSSIAN
[32
T T
INCREASING,
THEOREM 2
EXPANSIVE
MIXING
SUB-GAUSSIAN
OILIINE
THIS PAPER
d
INCREASING,
THEOREM 1
TAmin (G)
EXPANSIVE
NON-MIXING
SUR-GAUSSIAN
OFFLINE
THIS PAPER
d²
INCREASING,LPPSHHIT
THEOREM 2
Thmin
EXPANSIVE
MIXING
4-TH MOMENT
OFFLINE
INCKEASING.LPSCHHIZ
THIS PAPER
d'o² TAmin
THEOREM 3
EXPANSIVE
MIXING
SUB-GAUSSIAN
STREAMING
BOUNDED SECOND DERIVATIVE
Table 1: Comparison of our results with existing results in terms of mixing time Tmix stablility and number of samples T. Here, take mix 52 1- flop a proxy for the mixing time. Note that
Amin (G) 2 o² in the worst case, and hence our bounds are better by factor of Tmix-
The goal to estimate A" given a single trajectory Xo. X1..... Xy. A natural approach would be
to minimize the empirical square loss, ie, Lzg (A; X) == + - (Ix(Ax)) Xx+1ll However, when the link function é is not linear, then this would be non non-convex and hard optimize. Instead, we use a convex proxy loss given by:
Cprox X) = T
Σ 1=0 1=1
Σ
(((a, (es, Xa,
(3)
where e is the indefinite integral of the link function & and a; is the i-th row of A. Note that the gradient of pro (A; X) with respect to A is given by:
T + Σ (o(AX,) X X
(A: (P:prox(:33
When the model is clear from context and the stationary distribution exists, we will denote the second moment matrix under the stationary distribution by G == E[X,X,]] Note that G 2 B[nen. = I²I. Also, the empirical second moment matrix is denoted by G = 1 Ei= X,X,T
2.1 Assumptions
We now state the assumptions below and use only a subset of the assumptions for each result. Assumption (Lipschitzness and Uniform Expansivity). & is 1-Lipschitz and (Ø(z) < 2
Ç|æ y/. for some Ç 0.
Note that when o is only weakly differentiable but satisfy Assumption 1 with a slight abuse of notation, will write down 6(z) p(y) ('3 y) for some 1c. Assumption 2 (Bounded 2nd Derivative). & is twice continuously differentiable and [Ø") bounded.
Assumption (Noise Sub-Gaussianity). For any unit norm vector æ e IRd, we have (Ne. x) to be lub-Gaussian with variance proxy C,
Next, we extend the definition of exponential stability in 31 to 'exponential regularity to allow unstable systems.
Assumption (Exponential Regularity). Let XT = hT (Xo, .o..... .TT) be the function repre- sentation of Xx. We say that NLDS(A", 11, Φ) (CpsP) exponentially regular if for any choice of E N and Xa, Xb, To....., Wr I
[ .o...., - for (X,, To. no..... S Cpp -ppT-11100 - -X/l22
When p < 1, we will call the system stable. When = we will call it 'possibly marginally stable' and when 1, will call it 'possibly unstable'.

---

Algorithm 1: Quasi Newton Method
Input :Offline data (Xo....,XT)) horizon T, no. of iterations m, link function o, step size "
Output : Estimate Am
begin
Ag /"Initiaaiization"
G - + Ei=0 x,X;" If Ô is not invertible, then return A. = 0
3
for +- to m - do
A + A, 27
G-
Note that when Assumption 4 holds with < 1, the system necessarily mixes and converges to stationary distribution as 30. Such systems forget their initial conditions time scales of the order Tmix O( - ( [2) O [++og Cg and hence use this as proxy for the mixing time. In log
I-p
what follows, when say 'the system does not mix' either mean that it does mix within time T or it does not converge to a stationary distribution (ex: p 2 1).
Assumption (Norm Boundedness).
||A" llo - <
That is, if A" satisfies Assumption we have for arbitrary X, E Rd: - - p X X'I and ( (x)Il
p |X|] Hence, for such A", NLDS necessarily stable.
Offline Learning with Quasi Newton Method
In this section we consider estimating 4 using a single trajectory (X1,..., Xx) from NLDS(A", μr, 6). To this end, we study an offline Quasi Newton Method (Algorithm where the iterates descend in the directions of the gradient of Lprox normalized by the inverse of the empiri- cal second moment matrix G = + -T-1 X,X, That is, the iterates follow an approximation of the standard Newton update.
We now present analysis of Algorithm I in two settings: a) Theorem provides estimation error for possibly unstable systems with sub-Gaussian noise that is close to the minimax optimal error incurred in the linear system identification case, b) Theorem provides similarly tight estimation error for mixing systems but with heavy-tailed noise.
Theorem (Learning Without Mixing). Suppose Assumptions 7 and 4 hold with expansivity factor Ç and regularity parameters (Cps p). Let C, C' be constants depending only Cyp and let E (0, ()) Let R = C.
(Ei-))) p²)
log(
4Td and assume
1. The number samples T 2 O3s (dlog (5:) + log }
2. Step size 7 =
3. 2 10. log
AA00-"11ETTR o²d
Then, the output Am of Algorithu 1 after iterations and Amin
satisfy with probability at-least
2 8:
Amm
1
Co2 T (G)
d [ log [+
R*
d log (24)
0² 2
Amin
G
Note that as Amin Z o², the error rate scales as Rs d independent of Tmix R 1/(1 p). The theorem also holds for non-mixing or possibly unstable systems as long as p < 1 C Furthermore, the error bound above is similar to the minimax optimal bound by [I] for the linear setting, i.c., when
5

---

6(x) = I. As the link function & tends to decrease the information in intuitively lower bound for linear setting should apply for NLDS as well, which would imply our error rate be optimal: we leave further investigation into lower bound of NLDS identification for future work. Interestingly, in the linear case whenever the smallest singular value min mA*) + it can be show than Amin (G) grows exponentially with T, leading to an exponentially small error. It is not clear how to arrive at such a growth lower bound in the non-linear case.
The computational complexity of the algorithm scales as T which depends only logarithmically on Tmix- Interestingly, the algorithm is almost hyperparameter free, and does not require knoweldge of parameters o, Tmix:
Also note that the stationary points of Algorithm]] 1 and GL.Moron ( (22 are the same. So, the stronger rate in the result above compared to the result by 62 is due sharper analysis. However, in dynamical systems of the form | the squared norm of the iterates grow as T-p even in the stable
case. Hence, the GLMtron algorithm requires step sizes to be R 1ff which implies significantly slower convergence rate for large Tmix = 1/(1 - p). contrast, convergence rate for Algorithm
depends at most logarithmically on Tmix-
Theorem (Learning with Heavy Tail Noise). Suppose Assumptions 7 and 4 hold. In Assumption f
let 1. Let Xuy..., XT be a stationary trajectory drawn from NLDS(A A", , Φ) and Am be the m-th iterate of Algorithm For some universal constants C, C1 Co > O, whenever ō E (0, 2) 4T 11- and
R"
12' CiCpp )p) log
10 (1-p)\1-p")0""
1. T Co log( oz) max
log
2. Step size 7 =
11
3. m 2 log
o²dd²
There exists an event W E (Xa, No...., 11)
with with .or... 21 1- and
CadRo2
E [II AT A S (2Tduun (G)
The bound above shows that the expectation of the error restricted to high probability set is small. This, along with Markov inequality, shows that Cd can have an error of at-most (²T'Amis(G) with probability at-least 2 This can boosted to a high 3-
Obtaining High Probability Bounds:
probability bound by splitting the horizon T into к contiguous segments with a gap of ( log T) to maintain approximate independence (see Section C.2 We then run the Quasi Newton method on each of these 'split' data sets to obtaín nearly independent estimates Á,...., Ak, which each have error at-most CafoRK with probability at-least 3. Using standard high-dimensional median (TTAmin(G)
of means estimator (see [41] Algorithm 3]) for Ai...., Ak. we obtain error bounds of the order CdooK with probability least 1 - -S(
(G)
We refer to Section 6 for high-level exposition of the key ideas in the analysis and Section B for the
full proof of Theorems and 2
4 Streaming Learning with SGD-RER
In this section, we consider the one-pass, streaming setting, where the data points are presented in streaming fashion. The goal is to continuously produce better estimates of A" while also ensuring that the space and the time complexity of the algorithm small. This disallows approaches that would just store all the observed points and then apply offline Algorithm to produce strong estimation error. Such one-pass streaming algorithms are critical in variety settings like large-scale and online time-scries analysis [42 43), TD learning in RL 44 econometrics.

---

SOur
Buffer
Gap
Buffer
Figure I: Data order in SGD RER, where each block represents a data point. Blue arrows indicate the data processing order. The gaps ensure approximate independence between successive buffers.
Algorithm SGD RER
Input :Streaming data {X+), , horizon T, buffer size B, buffer gap u, bound R, tail start:
to S N/2, link function Φ step size 7
Output: EEstmatte At for all to S S N 1; N Ti(B + u)
begin
2
Total buffer size: S -- B + u, Number of buffers: + T/S
3
A8 = /MInitialiiaation"
for L 4- to N do
Form buffer But f- (Xi (X1-1 ...., ..- where, Xi- S(1-1)
If 3i, s.t., |xx--11²= for to B do
then return A =0
1 A! 2%
[o(A) 1 1-11)) X X-
10
A/ = B Ift to + then A 1 Ex= AB
t-1
To address this problem, we consider SGD RER (Algorithm) 2 which was introduced in 19 the context of linear system identification (LSI). We apply the method for NLDS identification well. SGD RER uses SGD like updates, but the data is processed in different order than it is received from the dynamical system. This algorithm based the observation made in [19 that for LSI, when SGD is run on the least squares loss in the forward order, there are spurious correlations which prevent the algorithm's 's convergence the optimum parameter A*. Surprisingly, considering the data in the reverse order exactly unravels these correlations to resolve the problem. Reverse order traversal of data, even though one pass, does not give streaming algorithm. Hence, we divide the data into multiple buffers of size B and leave of size between the buffers (See Figure T The data within each buffer processed in the reverse order whereas the buffers themselves are processed in the order received. See Figure for an illustration of the processing order. The gaps u are set large enough so that the buffers behave approximately independently. Setting 2 10u we note that this simple strategy improves the sample efficiency compared to naive data dropping since use most of the samples for estimating A*. We now present the main result for streaming setting.
Theorem 3 (Streaming Algorithm). Suppose Assumptions
2 3 and log
5 hold and that the 2eclog T B
data points are stationary. Set = 100, R 16(a+2
2
1-p
log -)
(CIT--RA--T) log -
100 )
for global constant Ō₁ dependent only C. and a. Let N
T/(B + u) be the number of buffers. Finally, step-size y fo where 6.5/7 and let T be 1 1/ 1f > to > then output Åip.N of Algorithm satisfies:
large enough such that 7 I min 1BR(1+3] 2R
T
( log 1)) for
some large enough constant
Log
| - 11 < TDmin (2)
+ Lower Order Terms
(5)
where C' is a constant dependent on CT,,
Remark 1. The lower order terms are of the order B,3.1/C. 7/22 72 Ro Rood d + A - A²1
eg BAmin
We refer to the proof Section for details.
7

---

Remark 2. Although the bound in Theorem 3 is given for the algorithmic iterate at the end of the horizon, the proof shows that in fact we can bound the ervor of the iterates the end of each buffer after (1 + c)ta i.e. if 1/2 coto some >> 0 then we obtain
d log
E | - A I C
+ Lower Order Terms
(tB))min (2)
Note that the estimation error above matches the error by offline method up to log factors (see Theorem 2). Furthermore, while the method requires NLDS be mixing, i.c., P but the leading term in error rate does not have an explicit dependence on it. Moreover, the space complexity of the 0) method only B dd which scales d ((]1=)) - ())) i... is (1((=)))(-p))) worse than the obvious lower bound of O(d2) to store A. We leave further investigation into space complexity optimization
Tiix factor
tightening the lower bound for future work. Also, note that S B/10, so SGD RER wastes only about 10% of the samples. Finally, the algorithm requires a reasonable upper bound on p to set up various hyperparameters like R, u, B. However, it is not clear how to estimate such an upper bound only using the data, and seems like an interesting open question.
See Section 6 for explanation of the elements involved in the analysis of the algorithm and to Section C.I for detailed overview of the proof.
Exponential Lower Bounds for Non-Expansive Link Functions
The previous results showed that efficiently recover the matrix A given that the link function is uniformly expansive. We now consider non-expansive functions and show that parameter recovery hard in this case. In particular, we show that even for the case of Φ ReLU, the noise being N I), and ||A""| S 2. the error has an information theoretic lower bound which is exponential in the dimension. We note that this is consistent with Theorem in 32 which has an exponential dependence on the dimension (since the matrix K ž= I).
Before stating the results, introduce some notation. Consider any algorithm A. with accepts input (Xo....; XT) and outputs estimate Á Rdxd, For simplicity of calculation, Xo = and X = ReLU(A" X₂) + Th- Since the mixing time is O(1), similar results should hold for stationary sequences. We define the loss C,A,T,AA = ElI - A I| where the expectation is over the randomness in the data and the algorithm. By ( we denote all the the elements of B E IRdxd such that |B|| < 2. The minimax loss is defined as:
will assume that
L(0()) T) = inf sup x
C(A,T.
Theorem (ReLU Lower Bound). For universal constants co, 01 > we have:
((O()), 2 co min (1, exp(cid)
T
We prove the theorem above using the two point method. We find a family of A" in O 7) such that (X ea) (1 with probability at-least exp((s((d)) Therefore, with large probability, we only observe noise in the last co-ordinate and hence do not obtain any information regarding the last row of A (i.e, az). We refer Section for full proof.
6 Proof Sketch
Quasi Newton Method. Let at be the i-th row of A and a:(() be the i-th row of A both in column vector form. The proofs of Theorems and 2 follow once consider the Iyapunov function
A,, = ((1/(((((()))) at and show that
AtLL s 11-2210 (1-2)))A, + +
(6)
Where N; : ET- (ee, nt) X,. In the case of Theorem 1 we use the aub-Gaussianity of the noise
sequence and martingale argument to obtain a high probability upper bound on >d
(,-1/22,11

---

(see Lemma D. In the heavy tailed case considered in Theorem 2 we use mixing time arguments along with Payley-Zygmund inequality to show the high probability lower isometry & = cgG for some universal constant (see Lemma 2. Using this lower isometry, we can replace G in Equation 6 with G. The upper bounds follow once we note that EN; G- atd.
SGD-RER. Due to the observations made in Section we can split the analysis into the following parts, which are explained in detail below.
1. Analyze the reverse order SGD within the buffers.
Treat successive buffer as independent samples.
3. Give biri-variance decomposition similar to the case of linear regression.
4. Use algorithmic stability to control 'spurious' coupling introduced by non-linearity in the bias- variance decomposition.
Coupled Process. We deal with the dependence between buffers using a fictitious coupled process, constructed just for the sake of analysis (see Definition Leveraging the gap u, this process (X,) is constructed such that X, 2 X, with high probability and the 'coupled buffers' containing data X instead of X are exactly independent. Since X, x X,, the output of SGD RER run with the fictitious coupled process should be close output of SGD RER run with the actual data points. We then use the strategy outlined above to analyze SGD RER with the coupled process. In the analysis given for SGD RER, all the quantities with involve the coupled process X instead of the real process X.
Non-Linear Bias Variance Decomposition. We use the mean value theorem to lincarize the non- linear problem. This works effectively when the step size is a vanishing function of the horizon T. Observe that the a single SGD/ SGD RER step for single row can be written as:
df a =a =a a - 27(0( X+)) <((a Xx))) + 2) = 11-220'S,,)
(a; - ao) + (nr,,)))
In the second step, we have used the mean value theorem. Equation 7 can be interpreted as follows: the matrix (T 2' (8,)x,X,) 'contracts' the distance between a; and at whereas the noise 27(0-, (e)n,,,))X, X, is due to the inherent uncertainty. This gives bias-variance decomposition similar to the case of SGD with linear regression. We refer to Section C.5 for details on unrolling the recursion in Equation 7 to obtain the exact bias-varianes decomposition.
Algorithmic Stability: Unfortunately, non-linearities result in a 'coupling' between the contraction matrices through the iterates via the first derivative d'(3,) due reverse order traversal. This is an important issue since unrolling the recursion in 7 we encounter terms such as (M/: e;) which have zero mean in the linear case. However, in the non-linear case, 1 depends !)- due to reverse order traversal. We show that such dependencies are 'weak' using the idea of algorithmic stability 45 (66). In particular, we establish that the output of the algorithm is not affected too much if we re-sample the entire data trajectory by independently re-sampling a single noise co-ordinate (n)- becomes v/ and 3 becomes 8 1) when step size is small enough (in other words, the output is stable under small perturbations). Via second derivative arguments, we show that 3 R -
2nd
Now observe that resampling noise т), does not affect the past value of data i.c, X,, X,-1 and is independent of 3 by construction. Therefore
E(n. e,) (I 2'yo' (8,- x e.) (1-276(6--1Xx X,
Such a resampling procedure is also explored in [4 for the analysis of SGD with random reshuffling.
We put together all the ingredients above in order to prove the error bounds given in Theorem 3
7 Experiments
In this section, we compare performance of our methods SGD RER and Quasi Newton method on synthetic data against the performance of standard baselines SGD (called 'Forward SGD' here),

---

Loaky&eLU AR meditated H. F-156, diormie d-2
LakoReLU AR, medeldddd A 638 doreki d-6
10
5:0
SCD4EER
SKE-SER
||Ar A"
11 A'll"
Quea Nevian
12
Rooal
FCD-R
50030
10
10"
10
10"
Compute Time
10"
10'
10
10'
10F
Number SGD Stere
10f
10
(a) Error vs. Computation
(b) Error vs. SGD updates
Figure 2: Performance of various algorithms for the case of Φ LeakyReLU
GLMtron, along with the SGD ER method that applies standard experience replay technique i.e, the points from buffer are sampled randomly instead of the reverse order. Since GLMtron and Quasi Newton Method are offline and SGD RER, SGD and SGD ER are streaming, we compare the algorithms by plotting parameter error measured by the Frobenius norm with respect to the compute time. We also compare error vs. number of iterations for the streaming algorithms, We show the results of additional experiments by considering various buffer sizes and heavy tailed noise in Section A
Synthetic data: We sample data from NLDS(A" (A",, 14, Φ) where μ (N0, and A E RRdd is generated from the "RandBiMod" distribution. That is, A = UAUT with random orthogonal U, and A is diagonal with dd2] entries on diagonal being P and the remaining diagonal entries are set x1(x 0). We set d =
to p/3. 6 is the leaky ReLU function given by Φ(x) = 0.5x1(x
= 0.98 and x² = 1. We set a horizon of T 10
Algorithm Parameters We set B = 240 and u = 10 for the buffer size and gap size respectively for both SGD RER and SGD ER and use full averaging (i.e, in Algorithm 2 We set the step size 7
5 T for SGD, SGD - RER, and SGD ER and "newton = 0.2 and "GLMrron = 0.017.
T
From Figure 2 observe that SGD ER and SGD obtain sub-optimal results compared SGD - RER, Quasi Newton Method and GLMtron. After single pass, the performance SGD RER almost matches that of the offline algorithms. The step sizes for GLMtron have to be chosen to be small in-order to ensure that the algorithm does not diverge as noted in Section 3 which slows down its convergence time compared to the Quasi Newton method. We set the step size to be as large as possible without obtaining divergence infinity.
Conclusion
In this work, studied the problem of learning non-linear dynamical systems of the form from a single trajectory and analyzed offline and online algorithms to obtain near-optimal error guarantees. In particular we showed that mixing time based arguments are not necessary for learning certain classes of non-linear dynamical systems. Even though we show that one cannot hope for efficient parameter recovery with non-expansive link functions like ReLU, do not deal with the problem of minimizing the 'prediction' error where we output a good predictor based on samples, without parameter recovery. We believe that this problem would require significantly different set of techniques than the ones established in this work and hope to investigate this in future work. Presently work only deals with specific kinds of Markovian time evolution. It would also be interesting to understand in general, the kind of structures which allow for learning without mixing based arguments. Another related direction is to design simple and efficient algorithms like SGD RER for learning with various models of dependent data by unraveling the dependency structure present in the data.
Acknowledgments and Disclosure of Funding
D.N. was supported in part by NSF grant 202-4422448.
S.S.K K was supported in part by Teaching Assistantship (TA) from EECS, MIT.
10

---

References
[1] Mathukumalli Vidyasagar. Nonlinear systems analysis. SIAM, 2002.
[2] Sheng Chen and Steve Billings. Representations non-linear systems: the NARMAX model. International journal of control, 49(3):1013-1032, 1989.
[3] Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):179-211 1990.
[4] Michael Jordan. Serial order: A parallel distributed processing approach. In Advances in psychology, volume 121, pages 471-495. Elsevier, 1997.
[5] Lennart Ljung. System identification. Wiley encyclopedia of electrical and electronics engi- neering, pages 1-19, 1999.
[6] Äström, Karl Johan and Eykhoff, Peter. System identification- a survey, Automatica, 7(2):123- 162, 1971.
[7] Marco C Campi and Erik Weyer. Finite sample properties of system identification methods. IEEE Transactions on Automatic Control, 47(8):1322-1333 2002.
[8] Mathukumalli Vidyasagar and Rajeeva Karandikar. A learning theory approach to system identification and stochastic adaptive control. In Probabilistic and randomized methods for design under unceriainly, pages 265-302. Springer, 2006.
[9] Eric Hall, Garvesh Raskutti, and Rebecca Willett. Inference of high-dimensional autoregres- sive generalized linear models. arXiv preprint arXiv:1605.02699 2016.
[10] John Wood. Behavioral modeling and linearization of RF power amplifiers. Artech house, 2014.
[11] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. arXiv preprint arXiv:180.008334, 2018.
[12] Tuhin Sarkar and Alexander Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In International Conference on Machine Learning, pages 5610-5618. PMLR, 2019.
[13] Shai Shalev-Shwartz. Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic Convex Optimization. In COLT, 2009.
[14] Daniel Paulin et al. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20, 2015.
[15] Egor Rotinov. Reverse experience replay. arXiv preprint 1rXiv:191000878,, 2019.
[16] Ellen Ambrose, Brad E Pfeiffer, and David Foster. Reverse replay of hippocampal place cells is uniquely modulated by changing reward. Neuron, 92(4:1112-11136, 2016.
[17] Tatsuya Haga and Tomoki Fukai. Recurrent network model for learning goal-directed sequences through reverse replay. Elife, 7:e34171, 2018.
[18] Matthew T Whelan, Tony Prescott, and Eleni Vasilaki. A robotic model of hippocampal reverse replay for reinforcement learning. arXiv preprint arXiv:2102. /1914, 2021.
[19] Prateek Jain, Suhas Kowshik, Dheeraj Nagaraj, and Praneeth Netrapalli. Streaming Linear System Identification with Reverse Experience Replay. arXiv preprint arXiv:2103.05880 2021.
[20] Abbasi-Yadkorii Yasin and Pál. Dávid and Szepesvári. Csaba. Online least squares esti- mation with self-normalized processes: An application to bandit problems. arXiv preprint arXiv: /ttp:///22.67707 2011.
[21] Victor Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer Science & Business Media, 2008.

---

[22] Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. In Conference on Learning Theory, pages 1452- 1485. PMLR, 2020.
[23] Sheng Chen, Stephen A Billings, and PM Grant. Non-linear system identification using neural networks. International journal of control, 51 (6):11991-1214 1990.
[24] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. arXiv preprint arXiv: 12065, 2018.
[25] Sohail Bahmani and Justin Romberg. Convex programming for estimation in nonlinear recurrent models, arXiv preprint arXiv: 1908:vv:98....... 19980099995 2019.
[26] Samet Oymak. Stochastic gradient descent learns state equations with nonlinear activations. In Conference Learning Theory, pages 2551 2551-2579. PMLR, 2019.
[27] John Miller and Moritz Hardt. Stable recurrent models. arXiv preprint arXiv:1805. 2018.
[28] Horia Mania, Michael Jordan, and Benjamin Recht. Active learning for nonlinear system identification with guarantees. arXiv preprint (rXiv:2006.10277 2020.
[29] Arnab Sarker, Joseph E Gaudio, and Anuradha M Annaswamy. Parameter Estimation Bounds Based on the Theory of Spectral Lines. arXiv preprint arXiv:2006. 126277700..277,, 2020.
[30] Yanbing Mao, Naira Hovakimyan, Petros Voulgaris, and Lui Sha. Finite-Timi Model Inference From A Single Noisy Trajectory. arXiv preprint arXiv:2010.06616, 2020.
[31] Yahya Sattar and Samet Oymak. Non-asymptotic and accurate learning of nonlinear dynamical systems. arXiv preprint arXiv:2002.0s:: 085388 2020.
[32] Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Learning nonlinear dynamical systems from single trajectory. In Learning for Dynamics and Control, pages 851-861. PMLR, 2020.
[33] Sham Kakade, Adam Tauman Kalai, Varun Kanade, and Ohad Shamir. Efficient learning of gen- eralized linear and single index models with isotonic regression. arXiv preprint arXiv: /04.20// 2011.
[34] Yue Gao and Garvesh Raskutti. Improved prediction and network estimation using the monotone single index multi-variate autoregressive model. arXiv preprint arXiv:2106. 2.0.::2006..4600 2021.
[35] Max Simehowitz, Ross Boczar, and Benjamin Recht. Learning linear dynamical systems with semi-parametric least squares. In Conference Learning Theory, pages 27 1714-2 PMLR. 2019.
[36] Tuhin Sarkar, Alexander Rakhlin, and Munther A Dahleh. Finite-time system identification for partially observed Iti systems of unknown order. arXiv preprint arXiv:1902.01848, 2019.
[37] Adam Tauman Kalai and Ravi Sastry. The Isotron Algorithm: High-Dimensional Isotonic Regression. In COLT. Citeseer, 2009.
[38] Nicholas M Boffi, Stephen Tu, and Jaan-Jasques E Slotine. The Reflectron: Exploiting geometry for learning generalized linear models. arXiv preprint arXiv:2006.08375. 2020.
[39] Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms. Advances in Neural Information Processing Systems, 33, 2020.
[40] Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3-4):293-321, 1992.
[41] Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. The Journal of Machine Learning Research, 17(15543-582, 2016.
[42] James Douglas Hamilton. Time series analysis. Princeton university press, 1994.
12

---

[43] Vitaly Kuznetsov and Mehryar Mohri. Time series prediction and online learning. In Conference on Learning Theory, pages 1190-1213, PMLR, 2016.
[44] Richard Sutton, Andrew Barto, et al. Introduction to reinforcement learning, volume 135. MIT press Cambridge, 1998.
[45] Bousquet, Olivier and Elisseeff, André. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[46] Moritz Hardt, Ben Recht, and Yoram Singer. 'rain faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225- 1234. PMLR, 2016.
[47] Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. International Conference on Machine Learning, pages 1770344711 PMLR, 2019.
[48] Boucheron, Stéphane and Lugosi, Gábor and Massart, Pascal. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
[49] Aymeric Dieuleveut, Alain Durmus, Francis Bach, et al. Bridging the gap between constant step size stochastic gradient descent and markov chains. Annals of Statistics, 48(3):1348-1333)
2020.
[50] Roman Vershynin. High-dimensions probability, 2019.
[51] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: [01 1.302,, 2010.
13

---

Checklist
1. For all authors...
(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] Currently this is purely theoretical work with multiple applications but right now they are not fully fleshed out.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] The experiments run on a standard computer within 1 min.
4. If you using existing assets code, data, models) or curating/releasing assets...
(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 assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "ibPq7x35Dgq", "reviewer": "Reviewer_iKUq", "summary": "This work has four major contributions: a) authors provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) authors significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting authors study a SGD with Reverse Experience Replay (SGD − RER) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) authors justify the expansivity assumption by showing that for the popular ReLU link function — a non-expansive but easy to learn link function with i.i.d. samples — any method would require exponentially many samples (with respect to dimension of Xt) from the dynamical system. \n\nThis paper is comprehensive with both solid theoretical analysis and simulations. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: authors studied the problem of learning non-linear dynamical systems from a single trajectory and analyzed offline and online algorithms to obtain near-optimal error guarantees. The results are original.\n\nQuality: Overall the quality is good. However, compared to the theoretical analysis, the empirical experiments are bit too short. \nIt would be helpful to consider multiple different data generating system, instead of just one simple case study. In addition, it would be great if authors can provide some ablation study on the impact of the hyper-parameters of the algorithm, and how they are selected in the simulation (e.g. B = 240 and u = 10). \nAlso authors claimed \"step sizes for GLMtron have to be chosen to be small in-order to ensure that the algorithm does not diverge\", it would be helpful to add some results to help understand how the step size can influence the performance for the GLMtron in appendix, as a smaller step size usually lead to slower convergence.\nAlso in the theoretical analysis authors proved the convergence rate with heavy tail noise, while only studied Gaussian noise in the empirical study. It would be great to have multiple experiments with different noise.\n\nClarity: Overall the paper is clear. My only concern is this paper contains too much results,so a 8-page conference paper might not be the best venue compared to journal article. \n\nSignificance: this works has both theoretical contribution, and methodological contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not observed any potential negative societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "Not observed", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "UzNQPiEQqsH", "reviewer": "Reviewer_99Uh", "summary": "The authors study a very special case of \"non-linear dynamical systems\" where there is no hidden state and there is some expansive, component-wise \"link function\" \\phi in the evolution X(t+1) = \\phi(AX(t)) + noise. For this very special case, they show both off-line and on-line algorithms. They also show lower bounds on the sample complexity of learning systems with with non-expansive link functions (such as ReLU). \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors study a very special case of \"non-linear dynamical systems\" where there is no hidden state and there is some expansive, component-wise \"link function\" \\phi in the evolution X(t+1) = \\phi(AX(t)) + noise. For this very special case, they show both off-line and on-line algorithms. They also show lower bounds on the sample complexity of learning systems with with non-expansive link functions (such as ReLU). \n\nOriginality:\n\nThe work seems very original. \n\nQuality and significance:\n\nRemoving the T_mix term in the sample complexity is a major contribution, albeit to a problem where real-world applications are \"yet to be found\".\n\nClarity:\n\nWhile I have not checked the proofs in the supplementary material in detail, the main body of the text is very well written.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None. ", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Ol7NpGLigY_", "reviewer": "Reviewer_mBux", "summary": "This work considers learning NLDS. Previous works can only learn mixing systems with sub-gaussian noise in the offline setting, with sample complexity depending on the mixing time. This work improves existing results in several ways, assuming the link function is expansive:\n1, it's shown that the offline Quasi Newton Method achieves near-optimal convergence rate for non-mixing systems.\n2, the offline Quasi Newton Method still achieves near-optimal convergence rate with heavy-tail noise, assuming mixing systems.\n3, a new algorithm SGD-RER is introduced, which achieves near-optimal convergence rate in the online setting.\n4, an exponential lower bound is proven for the ReLU link function, showing the expansivity assumption is necessary.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: This work focuses on a classic problem: learning NLDS. Nevertheless, the settings considered in this paper are less touched in previous works, and the use of SGD-RER is novel.\n\nQuality: Although the authors claim that the upper bounds in this work is independent of the mixing time, a new term $\\lambda_{min} (\\hat{G})$ is introduced which would make the upper bounds vacuous when being very small. It's unclear whether we can give a good lower bound for $\\lambda_{min} (\\hat{G})$, thus the result in this work isn't a $\\text{strict}$ improvement over previous works. In line 164 there is no support why $\\lambda_{min} (\\hat{G})\\ge \\sigma^2$ should hold. In line 165, $\\rho<1+C/T$ seems problematic.\n\nThe assertion of Theorem 2 is non-standard (and actually weaker). High-probability upper bounds of errors are preferred in common. The secondary choice is proving an upper bound for the expectation of error. However, Theorem 2 proves a high-probability bound for the expectation of errors, which might fail in the two settings above.\n\nClarity: The notations are heavy. Hiding ignorable variables and the parameter setting can improve the readability of theorems. The proof sketch of Section 3 is too brief compared with that of Theorem 4. More details should be included, for example, why can we use the convex proxy loss in line 127?\n\nSignificance: This work improves existing results for learning NLDS in several ways. The new algorithms/improved analyses can be useful for solving practical problems in RL and control.\n\nOther comments: in line 163, number 'of' samples. \nIn line 179, $\\tau_{mix} \\approx 1/(1-\\rho)$.\nIn line 180, the probability measure should be specified for the sigma algebra.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "-fTwVd-cVO", "reviewer": "Reviewer_WJnt", "summary": "The authors consider non-linear dynamical systems of the form $X_{t+1} = \\phi(A^* X_t) + \\eta_t$, where $\\eta_t$ is a noise term, $A$ is a $d \\times d$ matrix and $\\phi$ acts component-wise, and provide some results relating to the estimation of $A^* $ under certain assumptions. A key assumption is that $\\phi$ is \"expansive\", which I understand to be a sort of converse Lipschitz condition. (Since 1-Lipschitzness is also assumed, this means that $\\zeta |x - y| \\le |\\phi(x) - \\phi(y)| \\le |x - y|$ for some $\\zeta \\in (0, 1)$. I wasn't sure why this was called \"expansive\", because it seems to me more to be a limit on contraction than expansion per se, but this seemed understandable.) Under these conditions, they provide:\n\n1. An algorithm that, given sub-Gaussian noise, can recover $A^*$ with squared-norm error scaling in $O(d^2/T)$ (though I have questions about this, see main review).\n2. An algorithm that, given system stability and finite-fourth-moment noise, can recover $A^*$ with squared-norm error scaling in $O(d^2/T)$ (though I have questions about this too).\n3. A _streaming_ algorithm that, given sub-Gaussian noise, system stability and twice-differentiable $\\phi$, can recover $A^*$ with squared-norm error scaling in $O(d^2/T)$.\n4. A negative result with the non-expansive ReLU function, showing a lower bound on squared-norm error in this case of $\\Theta(e^{cd}/T)$, implying a need for exponentially many samples to recover $A^*$ satisfactorily.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Firstly—there are a lot of results in this paper. Some of the proofs are very involved and the authors had space only for just over one page for all four proof sketches, leaving 36 pages for the supplementary material. I congratulate the authors on their work. I suspect this could have comfortably been two papers if the authors had so wished. On the other hand, this volume made it an apparent challenge for the authors to structure the paper and highlight the key ideas in their work. For this reason, I wonder if this may even have been a stronger submission with just half its content but more thoroughly explained.\n\n**Clarity:** The summary Table 1 was very helpful in understanding how the results fit together. The main assumptions of the paper are listed in one place, which makes for some back-and-forth reference, but I can appreciate why this structure was chosen. The notation was generally clear and I didn't find it too confusing. If the authors can find a way to make pagination/space work, a minor suggestion is to show most the auxiliary definitions in Theorems 1 and 2 in display mode (rather than inline).\n\nI had a couple of clarifying questions about the results:\n\n1. In Theorem 1, $R^*$ appears in the $d^2$ term, and it is proportional to $d (\\sum_{t=1}^T \\rho^t)^2$ (ignoring log terms). If $\\rho < 1$ this would not be an issue but I believe this theorem is specifically about the case where $\\rho > 1$, which if I'm not mistaken would make $R^* = O(d \\rho^{2T})$ (ignoring log terms), $\\rho^T$ being the dominating term in the summation (and then squared). But that makes $R^*$ exponential in $T$. Then wouldn't we have $$\\log\\left(1 + \\tfrac{R^*}{\\sigma^2}\\right) = O(\\log d + 2T \\log \\rho),$$  (ignoring log-log terms) thereby cancelling out the $T$ in the denominator of the squared error expression? Then we would have an error in $O(d^2 \\log d)$ rather than $O(d^2/T)$ as claimed? I have probably missed something here and politely invite the authors to clarify.\n\n2. The left-hand side of the main line of this theorem has $\\mathbb{1}(\\mathcal{W})$ in it, which if I'm not mistaken is a random variable (being the indicator of an event). This makes the left-hand side of that expression a random variable (since it is an expectation multiplied by a random variable). Then is the inequality in this theorem intended to be an almost-sure inequality? Or are the authors trying to say that with probability at least $1 - \\delta$, \n$$\\mathbb{E}\\lVert A_m - A^* \\rVert_F^2 \\le \\frac{C_0 d^2 \\sigma^2}{\\zeta^2 T \\lambda_\\mathrm{min}(G)}?$$\nI again hope the authors can clarify.\n\n**Significance:** Since there were so many results, the implications and significance were sometimes hard to follow. Since all of the results appear to be interrelated and highly specific, I would have appreciated a section explicitly discussing how results fit into existing knowledge and what gaps remain—preferably for all of the results of the paper in one place. I appreciate that this may necessitate even further trimming some sections to allow it to fit, but I think it would be helpful.\n\nMy impression in general is that the results are significant and likely to be built on, but I think this paper would be much stronger with a clearer discussion of what the authors envisage with respect to this.\n\n**Quality:** I could not check any of the proofs in the supplementary material in detail, but there was nothing unsound that I could detect from my review of the main paper (except perhaps question 1 above), and a quick scroll through the section A of the supplementary material. I tend to think the nature of the assumptions makes the weaknesses of these results somewhat self-explanatory, and the authors make references to these in passing, though this is part of the discussion that I mentioned above might be useful.\n\n**Originality:** As far as I can tell, the proof techniques aren't brand new but their applications in this setting may be somewhat new, and the cases addressed in the paper are new contributions. However, I am not sufficiently familiar with the surrounding literature to provide a confident assessment of how original this is given the prior art.\n\n**Typos:** (not part of assessment, just for benefit of authors)\n- Line 17, stray period after \"via\".\n- Line 160–161, \"for _a_ possibly unstable\".\n- Line 162, \"in _the_ linear system\".\n- Line 163, \"mixing _systems_\" (plural).\n- Theorem 1, \"Assumptions _1, 3_ and 4\" (missing comma).\n- Theorem 2, the expression for $m$ has $R^*$ in it, I assume this was meant to be $R$?\n- Line 181, Section B.1, I assume this was meant to say Section A.2.\n- Also, a reference to the proof of Theorem 1 was omitted.\n- Remark 2, \"_Theorem_ 3\" (missing capital letter).\n- Line 273, missing period.\n- Line 277, \"SGD-ER\".\n\n_Edit, 02 Sep 2021: Raised rating from 6 to 7, as discussed in below responses/comments._", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is almost entirely theoretical in nature and I don't foresee any direct societal impact as a result of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The contributions were considered to be significant with high potential for impact. The main concern was that the paper contains, in a sense, "too much": there are many results, which made it harder for some reviewers to appreciate the level of contribution/improvement, and which raises the question of how to package the results into a coherent final version of the paper. Perhaps the authors can also consider submitting to a journal.
Decision: Accept (Spotlight)