  Overparameterization in deep learning typically refers to settings where a
trained neural network (NN) has representational capacity to fit the training
data in many ways, some of which generalize well, while others do not. In the
case of Recurrent Neural Networks (RNNs), there exists an additional layer of
overparameterization, in the sense that a model may exhibit many solutions that
generalize well for sequence lengths seen in training, some of which
extrapolate to longer sequences, while others do not. Numerous works have
studied the tendency of Gradient Descent (GD) to fit overparameterized NNs with
solutions that generalize well. On the other hand, its tendency to fit
overparameterized RNNs with solutions that extrapolate has been discovered only
recently and is far less understood. In this paper, we analyze the
extrapolation properties of GD when applied to overparameterized linear RNNs.
In contrast to recent arguments suggesting an implicit bias towards short-term
memory, we provide theoretical evidence for learning low-dimensional state
spaces, which can also model long-term memory. Our result relies on a dynamical
characterization which shows that GD (with small step size and near-zero
initialization) strives to maintain a certain form of balancedness, as well as
on tools developed in the context of the moment problem from statistics
(recovery of a probability distribution from its moments). Experiments
corroborate our theory, demonstrating extrapolation via learning
low-dimensional state spaces with both linear and non-linear RNNs.
