Answers.Body: <p>The time complexity of an algorithm always depends on its implementation (e.g. searching in a red-black tree has a different time complexity than searching in an unbalanced binary search tree). This also applies to the case of computing the time complexity of the algorithm that tests a neural network with multiple LSTM layers, so one may need to assume how an algorithm or data structure is implemented in order to provide the right time complexity.</p>
  <p>Now, note that testing a neural network typically means performing a forward pass. So, basically, if you have the time complexity for the forward pass, you are almost done. In <a href="https://ai.stackexchange.com/q/13612/2444">this answer</a>, I provide details of how you can compute the time complexity of the forward pass of a feedforward neural network with no recurrent layers, so you can read it in order to have an idea of how you might do this in general.</p>
  <p>Now, in the case of a neural network with LSTM layers, we also need to take into account the recurrent connections in the LSTM units. This would also be the case for the vanilla RNN units, which are simpler than LSTM units, so the time complexity is smaller.</p>
  <p>I will assume that the equations used to perform the forward pass of an LSTM layer are the ones given in <a href="https://pytorch.org/docs/stable/generated/torch.nn.LSTM.html" rel="nofollow noreferrer">the PyTorch documentation</a></p>
  <p><span class="math-container">$$
  \begin{aligned}
  i_{t} &amp;=\sigma\left(W_{i i} x_{t}+b_{i i}+W_{h i} h_{t-1}+b_{h i}\right) \\
  f_{t} &amp;=\sigma\left(W_{i f} x_{t}+b_{i f}+W_{h f} h_{t-1}+b_{h f}\right) \\
  g_{t} &amp;=\tanh \left(W_{i g} x_{t}+b_{i g}+W_{h g} h_{t-1}+b_{h g}\right) \\
  o_{t} &amp;=\sigma\left(W_{i o} x_{t}+b_{i o}+W_{h o} h_{t-1}+b_{h o}\right) \\
  c_{t} &amp;=f_{t} \odot c_{t-1}+i_{t} \odot g_{t} \\
  h_{t} &amp;=o_{t} \odot \tanh \left(c_{t}\right)
  \end{aligned}
  $$</span></p>
  <p>Now, let's break these operations down. Note that the dimensionality and type of the objects (matrices and vectors) are important. I will start with the computation of <span class="math-container">$i_{t}$</span> (the output of the input gate). The computation of <span class="math-container">$f_{t}$</span> (forget gate), <span class="math-container">$g_{t}$</span> (cell) and <span class="math-container">$o_{t}$</span> (output gate) is the same, in terms of time complexity.</p>
  <p><span class="math-container">$$i_{t} =\sigma\left(W_{i i} x_{t}+b_{i i}+W_{h i} h_{t-1}+b_{h i}\right)$$</span></p>
  <ul>
  <li><span class="math-container">$W_{i i} \in \mathbb{R}^{h \times d}$</span> is the matrix that represents the forward connections for the input gate</li>
  <li><span class="math-container">$x_{t} \in \mathbb{R}^d$</span> is the input vector with <span class="math-container">$d$</span> entries (this could be e.g. the embedding of a word)</li>
  <li><span class="math-container">$b_{i i} \in \mathbb{R}^h$</span> is a bias vector for this forward connetions</li>
  <li><span class="math-container">$W_{h i} \in \mathbb{R}^{h \times h}$</span> is the matrix for the recurrent connections; note that this matrix has a different dimensionality than <span class="math-container">$W_{i i}$</span></li>
  <li><span class="math-container">$h_{t-1} \in \mathbb{R}^h$</span> is the hidden state</li>
  <li><span class="math-container">$b_{h i} \in \mathbb{R}^h$</span> is the bias vector for the recurrent operations</li>
  </ul>
  <p>Here is an estimate of the time complexities of the operations inside the non-linearity</p>
  <ul>
  <li><span class="math-container">$W_{i i} x_{t}$</span> has time complexity <span class="math-container">$\mathcal{O}(h d)$</span> (matrix-vector multiplication)</li>
  <li><span class="math-container">$W_{i i} x_{t}+b_{i i}$</span> has time complexity <span class="math-container">$\mathcal{O}(h)$</span> (sum of two vectors, both with size <span class="math-container">$h$</span>)</li>
  <li><span class="math-container">$W_{h i} h_{t-1}$</span> has time complexity <span class="math-container">$\mathcal{O}(h^2)$</span></li>
  <li><span class="math-container">$W_{h i} h_{t-1}+b_{h i}$</span> has time complexity <span class="math-container">$\mathcal{O}(h)$</span></li>
  </ul>
  <p>Now, let <span class="math-container">$N = \max(d, h)$</span>, then the time complexity of the operations inside the non-linearity is <span class="math-container">$\mathcal{O}(hN)$</span>. More precisely, it would be</p>
  <p><span class="math-container">$$\mathcal{O}(h d + h + h^2 + h) = \mathcal{O}(h d + 2h + h^2) = \mathcal{O}(h(d + 2 + h)).$$</span></p>
  <p>Actually, in this case, as I explain in the other answer, you could use <span class="math-container">$\Theta(hN)$</span> because this is an upper and lower bound in the limit.</p>
  <p>Now, what is the time complexity of <span class="math-container">$\sigma$</span>? It depends on what <span class="math-container">$\sigma$</span> is. If we assume it's a ReLU, then you perform basically the following operation</p>
  <p><span class="math-container">$$\displaystyle \sigma(x) = \max(0,x)$$</span></p>
  <p>Let's assume that <span class="math-container">$\max(0,x)$</span> has a constant time complexity, so, if you apply the ReLU element-wise, you get a time complexity of <span class="math-container">$h$</span>.</p>
  <p>So, basically, the computation of <span class="math-container">$i_t$</span> has time complexity <span class="math-container">$\mathcal{O}(hN)$</span>. The same applies to <span class="math-container">$f_{t}$</span> (forget gate), <span class="math-container">$g_{t}$</span> (cell) and <span class="math-container">$o_{t}$</span> (output gate), as stated above, so you could multiply this time complexity by <span class="math-container">$4$</span>, but constant factors don't affect the time complexity. However, this is in theory, i.e. in the limit, in practice, they affect, so you probably want to include those. So, the time complexity, let's say, is</p>
  <p><span class="math-container">$$\mathcal{O}(4h(d + 2 + h))$$</span></p>
  <p>so far (ignoring there's a tanh there: for simplicity, I assume it has the same time complexity as the ReLU even though that may not be the case: you can work out the details!)</p>
  <p>Now, we have the following operation</p>
  <p><span class="math-container">$$c_{t} =f_{t} \odot c_{t-1}+i_{t} \odot g_{t},$$</span></p>
  <p>where</p>
  <ul>
  <li><span class="math-container">$c_t \in \mathbb{R}^h$</span> is the cell vector</li>
  <li><span class="math-container">$\odot$</span> is an element-wise multiplication</li>
  </ul>
  <p>So, this operation has time complexity</p>
  <p><span class="math-container">$$\mathcal{O}(2 h)$$</span></p>
  <p>Similarly, the operation</p>
  <p><span class="math-container">$$h_{t} =o_{t} \odot \tanh \left(c_{t}\right)$$</span></p>
  <p>has time complexity</p>
  <p><span class="math-container">$$\mathcal{O}(2 h)$$</span></p>
  <p>One <span class="math-container">$h$</span> for the tanh and the other for the element-wise multiplication.</p>
  <p>So, overall, the forward pass of a single LSTM layer has time complexity</p>
  <p><span class="math-container">$$\mathcal{O}(4h(d + 2 + h) + 4h) = \mathcal{O}(4h(d + 3 + h))$$</span></p>
  <p>Now, you can work out the time complexity for multiple LSTM layers stacked one after the other. Just make sure that you understand that what is passed to the successive layer is not the input <span class="math-container">$x_t$</span> but the output of the previous layer.</p>
  <p>In the end, you will also have to sum the complexity of the computation of the metric you're interested, which can be the loss or accuracy. If you understood my reasoning above, it should not be difficult to do that. The same applies for the case of a batch size and sequence size greater than 1.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-22T07:12:27.180Z
Answers.Text: what is your source ? I search a paper or course on "big O notation on deep learning" and I haven't found anything reliable.
  Thanks for the advance :)
Answers.UserDisplayName: user75427
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-22T19:21:32.493Z
Answers.Text: @user75427 My source is my background in Computer Science (bachelor) and AI (master). Every computer scientist student learns how to compute the Big-O notation of algorithms. But honestly I don't remember what I wrote in this answer anymore. It was already a long time ago. If there's anything unclear about my answer, let me know, and I'll read it again and try to clarify your doubts.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-27T11:22:44.307Z
Answers.LastActivityDate: 2021-12-27T13:03:48.767Z
Answers.LastEditDate: 2021-12-27T13:03:48.767Z
Answers.UserDisplayName: nbro
Body: <p>In the data preparation phase, we have to divide the dataset into two parts: the training dataset and the test dataset.</p>
  <p>I have seen <a href="https://ai.stackexchange.com/q/5728/2444">this post</a> regarding the time complexity for training a model.</p>
  <p>However, I couldn't find any good source for the time complexity for testing a model, specifically, a stacked LSTM model (with 1 input, 3 layers, 4 LSTM units per LSTM layer, 1 output, sequence 18, and batch size 32 for MSE loss), based on the test set, e.g. the computation of the accuracy/loss on the test set given <span class="math-container">$N$</span> test examples.</p>
  <p>Is there any source to check that?</p>
  
Tags: <long-short-term-memory><time-complexity><computational-complexity><testing>
Title: What is the time complexity for testing a stacked LSTM model?
UserDisplayName: Anik Islam Abhi
ThreadText: # What is the time complexity for testing a stacked LSTM model?
  
  (Asked by: username_0 on 2021-12-27)
  
  In the data preparation phase, we have to divide the dataset into two parts: the training dataset and the test dataset.
  
  I have seen [this post](https://ai.stackexchange.com/q/5728/2444) regarding the time complexity for training a model.
  
  However, I couldn't find any good source for the time complexity for testing a model, specifically, a stacked LSTM model (with 1 input, 3 layers, 4 LSTM units per LSTM layer, 1 output, sequence 18, and batch size 32 for MSE loss), based on the test set, e.g. the computation of the accuracy/loss on the test set given $N$ test examples.
  
  Is there any source to check that?
  
  **Tags:** long-short-term-memory, time-complexity, computational-complexity, testing
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-12-27. Score: 2 | Accepted answer
  
  The time complexity of an algorithm always depends on its implementation (e.g. searching in a red-black tree has a different time complexity than searching in an unbalanced binary search tree). This also applies to the case of computing the time complexity of the algorithm that tests a neural network with multiple LSTM layers, so one may need to assume how an algorithm or data structure is implemented in order to provide the right time complexity.
  
  Now, note that testing a neural network typically means performing a forward pass. So, basically, if you have the time complexity for the forward pass, you are almost done. In [this answer](https://ai.stackexchange.com/q/13612/2444), I provide details of how you can compute the time complexity of the forward pass of a feedforward neural network with no recurrent layers, so you can read it in order to have an idea of how you might do this in general.
  
  Now, in the case of a neural network with LSTM layers, we also need to take into account the recurrent connections in the LSTM units. This would also be the case for the vanilla RNN units, which are simpler than LSTM units, so the time complexity is smaller.
  
  I will assume that the equations used to perform the forward pass of an LSTM layer are the ones given in [the PyTorch documentation](https://pytorch.org/docs/stable/generated/torch.nn.LSTM.html)
  
  $$
  \begin{aligned}
  i\_{t} &=\sigma\left(W\_{i i} x\_{t}+b\_{i i}+W\_{h i} h\_{t-1}+b\_{h i}\right) \\
  f\_{t} &=\sigma\left(W\_{i f} x\_{t}+b\_{i f}+W\_{h f} h\_{t-1}+b\_{h f}\right) \\
  g\_{t} &=\tanh \left(W\_{i g} x\_{t}+b\_{i g}+W\_{h g} h\_{t-1}+b\_{h g}\right) \\
  o\_{t} &=\sigma\left(W\_{i o} x\_{t}+b\_{i o}+W\_{h o} h\_{t-1}+b\_{h o}\right) \\
  c\_{t} &=f\_{t} \odot c\_{t-1}+i\_{t} \odot g\_{t} \\
  h\_{t} &=o\_{t} \odot \tanh \left(c\_{t}\right)
  \end{aligned}
  $$
  
  Now, let's break these operations down. Note that the dimensionality and type of the objects (matrices and vectors) are important. I will start with the computation of $i\_{t}$ (the output of the input gate). The computation of $f\_{t}$ (forget gate), $g\_{t}$ (cell) and $o\_{t}$ (output gate) is the same, in terms of time complexity.
  
  $$i\_{t} =\sigma\left(W\_{i i} x\_{t}+b\_{i i}+W\_{h i} h\_{t-1}+b\_{h i}\right)$$
  
  * $W\_{i i} \in \mathbb{R}^{h \times d}$ is the matrix that represents the forward connections for the input gate
  * $x\_{t} \in \mathbb{R}^d$ is the input vector with $d$ entries (this could be e.g. the embedding of a word)
  * $b\_{i i} \in \mathbb{R}^h$ is a bias vector for this forward connetions
  * $W\_{h i} \in \mathbb{R}^{h \times h}$ is the matrix for the recurrent connections; note that this matrix has a different dimensionality than $W\_{i i}$
  * $h\_{t-1} \in \mathbb{R}^h$ is the hidden state
  * $b\_{h i} \in \mathbb{R}^h$ is the bias vector for the recurrent operations
  
  Here is an estimate of the time complexities of the operations inside the non-linearity
  
  * $W\_{i i} x\_{t}$ has time complexity $\mathcal{O}(h d)$ (matrix-vector multiplication)
  * $W\_{i i} x\_{t}+b\_{i i}$ has time complexity $\mathcal{O}(h)$ (sum of two vectors, both with size $h$)
  * $W\_{h i} h\_{t-1}$ has time complexity $\mathcal{O}(h^2)$
  * $W\_{h i} h\_{t-1}+b\_{h i}$ has time complexity $\mathcal{O}(h)$
  
  Now, let $N = \max(d, h)$, then the time complexity of the operations inside the non-linearity is $\mathcal{O}(hN)$. More precisely, it would be
  
  $$\mathcal{O}(h d + h + h^2 + h) = \mathcal{O}(h d + 2h + h^2) = \mathcal{O}(h(d + 2 + h)).$$
  
  Actually, in this case, as I explain in the other answer, you could use $\Theta(hN)$ because this is an upper and lower bound in the limit.
  
  Now, what is the time complexity of $\sigma$? It depends on what $\sigma$ is. If we assume it's a ReLU, then you perform basically the following operation
  
  $$\displaystyle \sigma(x) = \max(0,x)$$
  
  Let's assume that $\max(0,x)$ has a constant time complexity, so, if you apply the ReLU element-wise, you get a time complexity of $h$.
  
  So, basically, the computation of $i\_t$ has time complexity $\mathcal{O}(hN)$. The same applies to $f\_{t}$ (forget gate), $g\_{t}$ (cell) and $o\_{t}$ (output gate), as stated above, so you could multiply this time complexity by $4$, but constant factors don't affect the time complexity. However, this is in theory, i.e. in the limit, in practice, they affect, so you probably want to include those. So, the time complexity, let's say, is
  
  $$\mathcal{O}(4h(d + 2 + h))$$
  
  so far (ignoring there's a tanh there: for simplicity, I assume it has the same time complexity as the ReLU even though that may not be the case: you can work out the details!)
  
  Now, we have the following operation
  
  $$c\_{t} =f\_{t} \odot c\_{t-1}+i\_{t} \odot g\_{t},$$
  
  where
  
  * $c\_t \in \mathbb{R}^h$ is the cell vector
  * $\odot$ is an element-wise multiplication
  
  So, this operation has time complexity
  
  $$\mathcal{O}(2 h)$$
  
  Similarly, the operation
  
  $$h\_{t} =o\_{t} \odot \tanh \left(c\_{t}\right)$$
  
  has time complexity
  
  $$\mathcal{O}(2 h)$$
  
  One $h$ for the tanh and the other for the element-wise multiplication.
  
  So, overall, the forward pass of a single LSTM layer has time complexity
  
  $$\mathcal{O}(4h(d + 2 + h) + 4h) = \mathcal{O}(4h(d + 3 + h))$$
  
  Now, you can work out the time complexity for multiple LSTM layers stacked one after the other. Just make sure that you understand that what is passed to the successive layer is not the input $x\_t$ but the output of the previous layer.
  
  In the end, you will also have to sum the complexity of the computation of the metric you're interested, which can be the loss or accuracy. If you understood my reasoning above, it should not be difficult to do that. The same applies for the case of a batch size and sequence size greater than 1.
  
  > **Comments:**
  > **username_2**: what is your source ? I search a paper or course on "big O notation on deep learning" and I haven't found anything reliable. Thanks for the advance :)  
  > **username_1**: @user75427 My source is my background in Computer Science (bachelor) and AI (master). Every computer scientist student learns how to compute the Big-O notation of algorithms. But honestly I don't remember what I wrote in this answer anymore. It was already a long time ago. If there's anything unclear about my answer, let me know, and I'll read it again and try to clarify your doubts.  
  
  ---
  
  