Fast Training of Convolutional Networks through FFTs
Authors: Michael Mathieu, Mikael Henaff, Yann LeCun
ICLR 2014

Abstract: Convolutional networks are one of the most widely employed architectures in computer vision and machine learning. In order to leverage their ability to learn complex functions, large amounts of data are required for training. Training a large convolutional network to produce state-of-the-art results can take weeks, even when using modern GPUs. Producing labels using a trained network can also be costly when dealing with web-scale datasets. In this work, we present a simple algorithm which accelerates training and inference by a significant factor, and can yield improvements of over an order of magnitude compared to existing state-of-the-art implementations. This is done by computing convolutions as pointwise products in the Fourier domain while reusing the same transformed feature map many times. The algorithm is implemented on a GPU architecture and addresses a number of related challenges.


Peer review:
[Review]:
Thank you all for the constructive comments.

Soumith,
We added details as to how we addressed the memory issues. It's true that the method requires some extra memory, but you can preallocate a block of memory once and re-use it to store the frequency representations at each layer. So the amount of extra memory needed is equal to the maximum amount of memory required to store the frequency representations of a single layer. This is small compared to the amount of memory needed to store a large network.

Rodrigo and Anonymous c809,
We added a number of results reporting the running times for several different configurations of image and kernel sizes, as well as different numbers of input and output feature maps. We also added the running times for a training iteration of a whole network (not just a single layer). This is to account for memory accesses, padding and other implementation details. We also mention the results of our unit tests which compare the outputs of the FFT-based convolution and the direct method (the differences are very small). Concerning the 'additional heuristic', this case is actually included in the analysis section so we removed it to avoid confusion.

Concerning the border effects, we simply computed the circular convolution using the product of frequency representations and crop the output to only include coefficients for which the weight filter is contained within the image. We will clarify this in the paper.

We will also edit the graphs in Figure 3 to make the axis labels clearer.