An Uncertainty Principle for Linear Recurrent Neural Networks
This work provides theoretical insights into the limitations of linear RNNs for long-range sequence modeling, which is incremental as it builds on classical signal models for a specific task.
The paper tackles the problem of approximating a shift-K filter with a linear recurrent neural network of order S on a copy task, deriving lower bounds and explicit filters that achieve optimal performance up to constants, revealing an uncertainty principle where the optimal filter's averaging range is proportional to K/S.
We consider linear recurrent neural networks, which have become a key building block of sequence modeling due to their ability for stable and effective long-range modeling. In this paper, we aim at characterizing this ability on a simple but core copy task, whose goal is to build a linear filter of order $S$ that approximates the filter that looks $K$ time steps in the past (which we refer to as the shift-$K$ filter), where $K$ is larger than $S$. Using classical signal models and quadratic cost, we fully characterize the problem by providing lower bounds of approximation, as well as explicit filters that achieve this lower bound up to constants. The optimal performance highlights an uncertainty principle: the optimal filter has to average values around the $K$-th time step in the past with a range~(width) that is proportional to $K/S$.