  We introduce algorithms for learning nonlinear dynamical systems of the form
$x_{t+1}=\sigma(\Theta^{\star}x_t)+\varepsilon_t$, where $\Theta^{\star}$ is a
weight matrix, $\sigma$ is a nonlinear link function, and $\varepsilon_t$ is a
mean-zero noise process. We give an algorithm that recovers the weight matrix
$\Theta^{\star}$ from a single trajectory with optimal sample complexity and
linear running time. The algorithm succeeds under weaker statistical
assumptions than in previous work, and in particular i) does not require a
bound on the spectral norm of the weight matrix $\Theta^{\star}$ (rather, it
depends on a generalization of the spectral radius) and ii) enjoys guarantees
for non-strictly-increasing link functions such as the ReLU. Our analysis has
two key components: i) we give a general recipe whereby global stability for
nonlinear dynamical systems can be used to certify that the state-vector
covariance is well-conditioned, and ii) using these tools, we extend well-known
algorithms for efficiently learning generalized linear models to the dependent
setting.
