What is the computational complexity of the forward pass of a convolutional neural network?

Question

How do I determine the computational complexity (big-O notation) of the forward pass of a convolutional neural network?

Let's assume for simplicity that we use zero-padding such that the input size and the output size are the same.

Answer 1

What is the time complexity?

The time complexity of an algorithm is the number of basic operations, such as multiplications and summations, that the algorithm performs. The time complexity is usually expressed as a function of the input's size $n$ (but this does not always have to be the case: for instance, you can express the time complexity as a function of the output's size).

Example

Rather than giving you a full answer to your question, I will try to help you by explaining, with the simplest example, how you should calculate the time complexity.

For simplicity, let's assume that we have a kernel $\mathbf{H} \in \mathbb{R}^{3 \times 3}$ and input image $\mathbf{I} \in \mathbb{R}^{3 \times 3}$ (i.e. the kernel has the same dimensions as the input), we use a stride of $1$ and no padding. If we convolve $\mathbf{I}$ with $\mathbf{H}$, how many operations will we perform? The convolution is defined as a scalar product, so it is composed of multiplications and summations, so we need to count both of them. We have $9$ multiplications and $8$ summations, for a total of $17$ operations.

\begin{align} \mathbf{I} \circledast \mathbf{H} &= \begin{bmatrix} i_{11} & i_{12} & i_{13} \\ i_{21} & i_{22} & i_{23} \\ i_{31} & i_{32} & i_{33} \end{bmatrix} \odot \begin{bmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & h_{33} \end{bmatrix}\\ &= \sum_{ij} \begin{bmatrix} i_{11} h_{11} & i_{12} h_{12} & i_{13} h_{13} \\ i_{21} h_{21} & i_{22} h_{22} & i_{23} h_{23} \\ i_{31} h_{31} & i_{32} h_{32} & i_{33} h_{33} \end{bmatrix}\\ &= i_{11} h_{11} + i_{12} h_{12} + i_{13} h_{13} + i_{21} h_{21} + i_{22} h_{22} + i_{23} h_{23} + i_{31} h_{31} + i_{32} h_{32} + i_{33} h_{33} \end{align}

Time complexity

What is the time complexity of this convolution? To answer this question, you first need to know the input's size, $n$. The input contains $9$ elements, so its size is $n = 9$. How many operations did we perform with respect to the input's size? We performed $17$ operations, so the time complexity $\mathcal{O}(2*n) = \mathcal{O}(n)$, i.e. this operation is linear. If you are not familiar with the big-O notation, I suggest that you get familiar with it, otherwise, you will not understand anything about computational complexity.

To calculate the time complexity in the case the input's dimensions are different than the kernel's dimensions, you will need to calculate the number of times you slide the kernel over the input. You can't ignore this (as I ignored the constant $2$ above) because the number of times you slide the kernel over the input depends on the input's size, so it's a function of the input. Anyway, the paper A guide to convolution arithmetic for deep learning contains a lot of information about convolution arithmetic, so it will be helpful.

Non-linearities, pooling and fully connected layers

Note that, in the above example, I ignored the non-linearities and pooling layer. You can easily extend my reasoning to include these operations too. I also ignored the operations in the final fully connected layers. You can find how to calculate the number of operations in an MLP in this answer. If you also perform other operations or have other layers other than convolutional, pooling and fully connected, of course, you will also need to take them into account.

Forward pass

Moreover, the time complexity of the forward pass of a CNN depends on all these operations in these different layers, so you need to compute the number of operations in each layer first. However, once you know how to compute the number of operations for one convolutional layer, one pooling layer, and one fully connected layer, you can easily compute the number of operations for the other convolutional, pooling, and fully connected layers. Then you just need to sum all these operations and express your time complexity as a function of the input (and probably number of layers).

Space complexity

If you also want to compute the space complexity, you just need to do the same thing, but as a function of the space that you use, i.e. how many variables you use to perform the convolution.