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]:
'Fast Training of Convolutional Networks through FFTs' compares Fourier-domain vs. spatial-domain convolutions in terms of speed in convnet applications.
 
The question of the relative speed of Fourier vs. Spatial convolutions is common among engineers and researchers, and to my knowledge no one has attempted to characterize (at least in convnet-specific terms) the settings when each approach is preferred.  Spatial domain convolutions have been the standard in multiple implementations over 30 years of research by scores of researchers.  This paper claims, surprisingly, that FFTs are nearly always better in modern convnets.  At the same time, the authors of the paper introduce a strategy for FFT parallelization on GPUs that is somewhat particular to the sorts of bulk FFTs that arise in convnet training, and the conclusions are based on that implementation running on GPU hardware.
 
 
CONTRIBUTIONS
 
1. Empirical comparison of spatial and Fourier convolutions for convnets
 
2. A fast Cooley-Tukey FFT implementation for GPU that's well-suited to convnet application                                
                                                                                                                                     
 
QUALITY        
 
The figures and formatting are not very polished.         
 
 
PRO            
 
1. The paper aims at an important issue for convnet researchers        
 
2. The claim that FFT-based convolutions are better will be broadly interesting                                            
 
 
CON            
 
1. The paper does not explain when spatial-domain calculations would be faster                                             
 
2. The paper does not discuss how the trade-offs would be different on single-core or multi-core CPUs, or on different GPUs.
 
3. Details of the Cooley-Tukey implementation are not given
 
4. No mention is made of downloadable source code, this work might be hard to reproduce


COMMENTS
 
- What about non-square images?
 
- Why use big-O notation in 2.2 when the approximate number of FLOP/s is easy to compute? Asymptotic performance isn't really the issue at hand, the relevant values of n and k are not very large. Consider falling back on big-O notation only after making it clear that the main analysis will be done on more precise runtime expressions.
 
- The phrase 'Our Approach' is surprising on page 3, because it does not seem like you are inventing a new Fourier-domain approach to convolution.  Isn't the spatial domain faster sometimes, Fourier faster sometimes, and you're writing a paper about how to know which is which?
 
- The last paragraph of section 3 is confusing: which of your experiments use and do not use the memory-intensive FFT-reuse trick?  The following sentence in particular makes the reader feel he is being duped 'All of the analysis in the previous section assumes we are using this memory-efficient approach [which you now tell is is infeasible in important practical applications]; if memory is not a constraint, our algorithm becomes faster.'  Faster than what? Faster than the thing that doesn't require prohibitive amounts of memory?
 
- Page 4: when you speak of 'another means to save memory' what was the first way? (Was the first way to recompute things on demand?)
 
- Page 5: Figure 3: This figure is hard to understand. The axes should be labeled on the axes, and the title should contain the contents of the current caption (not the names of the axes), and the caption should help the reader to understand the significance of what is being shown.
 
- Why is the Torch7 implementation called Torch7(custom), and not just Torch7?
 
- The memory access patterns entailed by an algorithm is at least as important for GPU performance as the number of FLOP/s. How does the Cooley-Tukey FFT algorithm work, and how did you parallelize it? These implementation details are really important for anyone trying to reproduce your  experiments.
 
- What memory layout do you recommend for feature maps and filters? This ties in with a request for more detail on the algorithm you used.