3
$\begingroup$

What is the complexity of a 1D convolutional layer?. I'm getting $\mathcal{O}(n \cdot k \cdot d)$, but in Attention Is All You Need, Vaswani et al. report that it is $\mathcal{O}(k \cdot n \cdot d^2 )$:

enter image description here

To me, a 1D convolution is the sum of the row-wise dot products of a filter $W \in \mathbb{R}^{k \times d}$ with a region matrix $A \in \mathbb{R}^{k \times d}$, where $k$ is the length of the filter and $d$ is the depth dimension (e.g, dimensionality of word embedding space).

That gives us:

  • $\mathcal{O}(d)$ for one dot product ($d$ multiplications + $d-1$ additions)
  • we perform in total $k$ dot products (there are $k$ rows in $W$ and $A$), which amounts to $\mathcal{O}(k \cdot d)$
  • and finally, at the layer level, we apply the filter over the input $n-k+1$ times (where $n$ is the length of the input), let' say $n$ times since $n>>k$. This gives us a final complexity of $\mathcal{O}(n \cdot k \cdot d)$.

What am I missing? Where does the extra $d$ of the authors come from?

Note: it is not clear exactly in the paper whether the authors refer to standard convolutions or dilated convolutions. But while this may affect the max path length, I don't think this has an impact on complexity.

$\endgroup$
2
$\begingroup$

I realized what may be missing is the number of filters in the layer.

Even though they don't have a letter for it in the table, the authors might be assuming implicitly that the order of magnitude of the number of filters is the same as that of the number of depth dimensions. Or even more simply, that the number of filters is equal to $d$ (in that case, the conv layer does not change the depth dimensionality).

So, in that case, the time complexity indeed amounts to $\mathcal{O}(k\cdot n \cdot d^2)$ because we're repeating the $\mathcal{O}(k\cdot n \cdot d)$ routine described in the question for each of the $d$ filters.

$\endgroup$
1
  • 2
    $\begingroup$ Yes, a single convolution is $\mathcal{O}(nkd)$, and convolution with $f$ filters is $\mathcal{O}(nkdf)$. I guess they are being conservative about the number of filters by assuming it is $\leq d$ and that $d \geq n \geq k$. So, in that case, it makes sense that the worst case time complexity of convolution with multiple filters is $\mathcal{O}(nkd^2)$. $\endgroup$ Jan 24 '20 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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