Title: The Effects of Nonlinearity on Approximation Capacity of Recurrent Neural Networks. Abstract: We study the effects of nonlinear recurrent activations on the approximation properties of recurrent neural networks (RNNs). Previous works indicate that in the linear setting, RNNs show good approximation performance when the target sequential relationship is smooth and has fast decaying memory. Otherwise, RNNs may suffer from the so-called “curse of memory”, meaning that an exponentially large number of neurons is required for accurate approximation. A natural question is whether the recurrent nonlinearity has a substantial effect on RNNs’ approximation capacity and approximation speed. In this paper, we present some negative results in this direction. We discover that, while the addition of nonlinearity does not shrink the hypothesis space, in the sense that nonlinear RNNs can still approximate linear functionals with the same approximation rates established for linear RNNs, it does not essentially alleviate the limitations of RNNs either. In particular, we prove that nonlinear RNNs fail to be universal approximators of arbitrary nonlinear functionals, and any linear functional that can be efficiently approximated must also possess an exponentially decaying memory. 