We study discrete time dynamical systems governed by the state equation h t+1 = φ(Ah t + Bu t ). Here A, B are weight matrices, φ is an activation function, and u t is the input data. This relation is the backbone of recurrent neural networks (e.g. LSTMs) which have broad applications in sequential learning tasks. We utilize stochastic gradient descent to learn the weight matrices from a finite input/state trajectory {u t , h t } N t=0 . We prove that SGD estimate linearly converges to the ground truth weights while using near-optimal sample size. Our results apply to increasing activations whose derivatives are bounded away from zero. The analysis is based on i) a novel SGD convergence result with nonlinear activations and ii) careful statistical characterization of the state vector. Numerical experiments verify the fast convergence of SGD on ReLU and leaky ReLU in consistence with our theory.
This paper studies the ability of SGD to learn dynamics of a linear system + non-linear activation. That is, in the standard LTI setting, the dynamics of a system evolve according to
h_{t+1} = Ah_t + Bu_t,
on input u_t.
In addition, this paper considers the setting where the evolution is:
h_{t+1} = \phi(Ah_t + Bu_t)
for \phi a non-linear activation function. 
This is a difficult problem. Though system identification was for many decades a large and active area in the control community, the understanding of system identification from a modern statistical perspective (understanding sample complexity and computational complexity simultaneously) is surprisingly lacking. This is evidenced by the fact that the first results along these lines for the simplest possible (SISO, LTI) system, came only recently (Hardt, Ma, Recht ’16). 
This paper attacks a more general setting, due to the presence of the nonlinearity.
However, the present setting is significantly limited in another sense: the authors assume that the state is observed directly. This is in contrast to the typical situation where we observe only a projection of the state, or possibly even a noisy such projection. Indeed, this is one of the critical complications in the work of Hardt, Ma and Recht. Without it, i.e., under the assumption that the entire state trajectory can be directly observed, much more is possible, and indeed much more has been done. For example, work by Bento, Ibrahimi and Montanari ’10, solves a more difficult problem in that they estimate sparse dynamics (in appropriate sample complexity). Jalali and Sanghavi ’11 generalized the work of Bento et al., to the setting where some of the components of the state are not all observed, but rather some are latent.
The motivating application for this work is estimating RNNs. In this case, the state variable represents the critical information that is carried from one time to the next in the RNN. Presumably the setting here is to show that if indeed data are generated by an RNN, then we can compute this using SGD and backprop. Towards this, the assumption of having access to the internal state is a difficult one. On the one hand, this is a hard and important problem. On the other, we really won’t have access to such an internal state. There are of course other problematic aspects, such as robustness, the inability to use ReLU (Defn 3.1). But the observation model seems important. Again, I believe this is especially so, because the considerable complications present in Hardt, Ma, Rect ’16 specifically seemed to be a consequence of the observation model being partial.
The inability to use ReLU at first look does not seem like a great limitation. But then one problematic aspect here seems that the proof concept and direction critically rely on this, as they basically reduce to the setting of linear activations — something which, presumably, is impossible for something like ReLU. So it is not only the results, but also the developed machinery, that seem to be inherently limited.
This is, overall, an interesting paper, attacking an important and also very challenging area. As with all papers in this vein, we are left with having to make a judgement call on whether this simplified scenario is indeed a good first step towards solving the problems we are hoping to solve. Is it developing the right insight, right tools, etc. While I find there is a lot of interesting and good work in this paper, I am not completely convinced about this last point.