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]:
The paper presents a technique for accelerating the processing of CNNs by performing training and inference in the frequency (Fourier) domain. The work argues that at a certain scale, the overhead of applying FFT  and inverse-FFT is marginal relative to the overall speed gain.  

As noted by the previous reviewers, the speedup is presented simply as that obtained for three functions that lie at the heart of each convolutional layer. It would be valuable if the speedup could also be presented in the context of a comparison to the overall training time of a CNN on a standard dataset.

Also noted is the lack of reference to the fact that Convolution Theorem refers to circular convolution and not linear (i.e. non-circular) convolution. It is assumed inconsequential since CNNs use neither circular convolution (weight filters do not wrap around images) nor linear convolution (weight filters are always fully contained within the image and do not 'hang off' the edges). Thus, the resulting differences between circular and linear convolution would not impact the feature map y_f. This seems to be hinted at by the n' term in section 2.2, but is not obvious.

The future work seems logical and would be interesting to pursue. One other direction to consider is approximations to the FFT (which there are many) that could retain most of the information needed in context of CNNs at a fraction of the computational cost.

Minor editorial issue: in figure 3 the axes are noted in the title of the figure rather than as labels for the x and y axis.