why does training a convolutional neural network take much longer than training a recurrent neural network? I am currently comparing RNNs to CNNs on multiple criteria and I've come across something I find rather weird.
I have a 3dCNN and an LSTM. Both take a 29x30x60 input and classify it to 2 classes. For the LSTM the input is flattened per timestep so it receives a 29x1800 input.


*

*The LSTM has +- 250k parameters.

*The 3dCNN has +- 100k parameters.


Besides architecture, everything is exactly the same (optimizer and learning rate etc.). However, the LSTM does this in around 100 epochs and the 3dCNN does this is around 5 epochs.
But this is where the weird part comes in: an epoch for the LSTM is about 30 seconds, where an epoch for the 3dCNN is around 45 MINUTES! The CNN goes to near 100% accuracy in about 10 epochs, where the LSTM does this in around 50-70 epochs. 
Thus, the 3dCNN might train quicker epoch-wise, but is extremely slow in general compared to the LSTM. I did not expect this at all.
Yes I am training on a slow CPU in both cases but the difference in training time is my main concern here.
Is it the convolution that is so extremely more computationally expensive? Does anyone have a more detailed insight to this time difference in processing?
Thanks!
Edit: sorry for not including my network architecture.
My CNN is using 3 layers of convolution+maxpooling with 3D convolution, all using 3x3x3 kernels (stride 1 and zeropadding). The maxpooling is used on a 2x2x2 area. 1st layer of convolution extracts 16 feature maps, the 2nd 24, and the 3rd 32. This is followed by a dense layer of 16 nodes and a final dense layer of 2 nodes that perform the classification. The input is 29x30x60.
My LSTM uses 2 layers of lstm, with both layers having an output size of 16. The first is returning all its hidden states and the 2nd only returns its last hidden state. This is followed by a dense layer of 2 nodes. Input is 29x1800.
Hope this helps!
 A: Without knowing exact details about your architecture it is not possible to provide an exact explanation/calculation of what is going on, but roughly it can be justified as follows:
Convolution networks are so successful because they manage to do a lot with very little parameters. The key is sharing those parameters within the network1. That means even if you have less parameters than in a LSTM network, they are used many times: the proportion of number of parameters to amount of computation is not equal in 3D convnet and an LSTM.
CNN example:


*

*Let the input be of shape $(w,h,d)$, having a single channel.

*We use a convolution layer with $c$ filters of shape $(a,a,a)$, in total $p_\mathrm{CNN}=c(a^3 + 1)$ parameters (1 for bias). Note that the number of parameters does not grow with the input size.

*To evaluate this layer, we need to perform $w\cdot h\cdot d \cdot c (2a^3+1)$ operations ($a^3$ multiplications and $a^3+1$ additions per filter per spatial location). That means overall complexity of $\mathcal{O}(whdp_\mathrm{CNN})$.


LSTM example:


*

*Let the input be of shape $(wh,d)$, having a single channel.

*We use a LSTM layer with $c$ units, in total $p_\mathrm{LSTM}=4c(wh+c+1)$ parameters (4 matrices of shape $(wh,c)$, 4 matrices of shape $(c,c)$ and $4c$ biases). Note that the number of parameters linearly depends on the input size.

*To evaluate this network on the whole sequence of length $d$, we need to perform $d$ matrix-vector multiplications with complexity $\mathcal{O}(whc)$ and $d$ matrix-vector multiplications with complexity $\mathcal{O}(c^2)$, overall it is  $\mathcal{O}(dp_\mathrm{LSTM})$.


You can see that if the number of parameters is the same for both networks, $p_\mathrm{CNN}=p_\mathrm{LSTM}$, a CNN needs $wh$-times more computations to evaluate the result. In your case $wh=1800$ and $\frac{p_\mathrm{LSTM}}{p_\mathrm{CNN}} = 2.5$, you can therefore expect roughly 720x longer runtime for the CNN.

1 Recurrent networks also share parameters, but only in the temporal dimension. Convnets share parameters in the spatial dimensions.
