1
$\begingroup$

In particular, what is the complexity of a bi-directional recurrent neural network taking into account the variants of LSTM and GRU as well for training?

I am hoping if I can get links to some additional research papers which talk or have mentioned the computational complexity of these methods in their works. I have been searching, but haven't come across anything meaningful till now

$\endgroup$
2
  • $\begingroup$ What do you mean by "complexity"? Do you mean computational complexity in terms of big-O notation? $\endgroup$
    – noe
    Commented Oct 9, 2020 at 9:41
  • $\begingroup$ Thank you for pointing this out @ncasas. This is indeed what I meant, Computational complexity in terms of Big-O $\endgroup$ Commented Oct 9, 2020 at 12:00

1 Answer 1

1
$\begingroup$

The computational complexity of simple single-layer recurrent networks, either vanilla RNNs, LSTMs or GRUs is linear with the length of the input sequence, both at training time and inference time, so $O(n)$, where $n$ is the length of the input sequence. This is because in order to get the last time step output, you need to compute all the previous ones.

This is assuming that there is a single output. If there are multiple output time steps, then it is linear on the sum of both input and output lengths.

Take into account that, inside LSTMs and GRUS there are internal steps that account for a multiplication by a constant in the complexity.

You can complicate the network architecture in many different ways (more layers, skip connections, etc), and this can affect its computational complexity. Here you can find an in-depth study of the computational complexity of different architectural variations.

$\endgroup$
3
  • $\begingroup$ Thank you for your reply @ncasas. It is indeed helpful. But I was hoping if I can get links to some additional research papers which talk or have mentioned the computational complexity of these methods in their works. I have been searching, but haven't come across anything meaningful till now. $\endgroup$ Commented Oct 9, 2020 at 13:11
  • $\begingroup$ Please, add these details to your question so that people can take them into account in their answers. $\endgroup$
    – noe
    Commented Oct 9, 2020 at 13:38
  • $\begingroup$ This is a very good answer. $\endgroup$
    – hH1sG0n3
    Commented Nov 10, 2021 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.