How does the number of stacked LSTM layers or units in each layer affect the model complexity?

I playing around sequence modeling to forecast the weather using LSTM.

How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I increase the number of layers and decrease the number of units, how will the model complexity be affected?

I am not interested in rules of thumb for choosing the number of layers or units. I am interested in theoretical guarantees or bounds.

In computational learning theory, the VC dimension is a formal measure of the capacity of a model. The VC dimension is defined in terms of the concept of shattering, so have a look at the related Wikipedia article, which briefly describes the fundamental concept of shattering. See also my answer to the question How to estimate the capacity of a neural network? for more details.

The paper Vapnik-Chervonenkis dimension of recurrent neural networks (1998), by Pascal Koirana and Eduardo D. Sontag, partially (because they do not take into account more advanced recurrent neural network architectures, such as the LSTM) answers your question.

In the paper, the authors show and prove different theorems that state the VC dimension of (standard) recurrent neural networks (RNNs), with different activation functions, such as non-linear polynomials, piecewise polynomials and the sigmoid function.

For example, Theorem 5 (page 70) states

Let $$\sigma$$ be an arbitrary sigmoid. The VC dimension of recurrent architectures with activation $$\sigma$$, with $$w$$ weights and receiving inputs of length $$k$$, is $$\Omega(wk)$$.

The proof of this theorem is given on page 75.

What does this theorem intuitively tell you? If you are familiar with big-O notation, then you are also familiar with the notation $$\Omega(wk)$$, which means that $$wk$$ is, asymptotically, a lower bound on the capacity of the RNN. In other words, asymptotically, the capacity of an RNN with $$w$$ weights receiving inputs of length $$k$$ is at least $$wk$$. How does the capacity of the RNN increase as a function of $$w$$?

Of course, this is a specific result, which only holds for RNNs with the sigmoid activation function. However, this at least gives you an idea of the potential capacity of an RNN. This theorem will hopefully stimulate your appetite to know more computational learning theory!

The paper On Generalization Bounds of a Family of Recurrent Neural Networks may also be useful, although it has been rejected for ICLR 2019.

• Hmm, so it scales with number of weights? Therefore, can we say VC-dim (RNN with k layers) = k * VC-dim (RNN with 1 layer)? Apr 12 '20 at 2:15
• Yes, it scales with weights and length of the input. But, again, note that $wk$ is a lower bound, so the capacity of the RNN may actually be higher (but only asymptotically).
– nbro
Apr 12 '20 at 2:39