  We prove an inverse approximation theorem for the approximation of nonlinear
sequence-to-sequence relationships using recurrent neural networks (RNNs). This
is a so-called Bernstein-type result in approximation theory, which deduces
properties of a target function under the assumption that it can be effectively
approximated by a hypothesis space. In particular, we show that nonlinear
sequence relationships that can be stably approximated by nonlinear RNNs must
have an exponential decaying memory structure - a notion that can be made
precise. This extends the previously identified curse of memory in linear RNNs
into the general nonlinear setting, and quantifies the essential limitations of
the RNN architecture for learning sequential relationships with long-term
memory. Based on the analysis, we propose a principled reparameterization
method to overcome the limitations. Our theoretical results are confirmed by
numerical experiments. The code has been released in
https://github.com/radarFudan/Curse-of-memory
