Source-linked AI summary
Fast Training of Convolutional Networks through FFTs
Michael Mathieu, Mikael Henaff, Yann LeCun
TL;DR
Large convolutional networks can require weeks to train, and applying trained models to web-scale datasets can be costly. The paper introduces FFT-based convolution with reused transforms to accelerate training and inference, reporting faster performance than state-of-the-art implementations. Its current implementation is suboptimal for image sizes that are not powers of two.
Problem
Large datasets make convolutional-network training time-consuming, while producing labels across internet-scale image collections requires substantial time and resources.
Method
The paper computes convolutions as pointwise products in the Fourier domain while reusing transformed feature maps across repeated pairings.
Results
The method outperforms known state-of-the-art implementations in speed across numerical experiments for convolutional-network training and inference.
Takeaways & Limitations
FFT-based convolution is especially suited to inference on very large datasets because its forward-pass improvement is particularly substantial.
Takeaways & Limitations
The current implementation pads non-power-of-two input images to the next highest power of two, making some sizes suboptimal in speed.
Abstract
from arXiv · showhide
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.
1 Introduction
Modern vision and machine-learning models require increasingly large datasets, making convolutional-network training and web-scale inference costly. The paper addresses this need with an FFT-based algorithm that reuses transformed feature maps to accelerate both tasks.
- Training large convolutional networks can take weeks on ImageNet, while assigning labels across internet-scale image collections also consumes substantial time and resources.
- The proposed algorithm computes convolutions as Fourier-domain products and reuses transformed feature maps across many pairwise convolutions.The method applies to convolutions involving feature maps, loss gradients, and weight kernels.
- When modern networks use many feature maps, FFTs can accelerate training and inference significantly, with reported speedups exceeding an order of magnitude.Earlier FFT approaches focused on first-layer inference and were less effective when networks had few feature maps.
2 Theory
The paper reformulates convolutional-network forward and backward computations as Fourier-domain products, exploiting repeated pairings among feature maps and kernels. Its complexity analysis and implementation address operation count, cropping, GPU parallelism, and memory reuse.
- 2.1 Backpropagation: A convolutional layer maps input feature maps x_f to output maps y_f′ using trainable k × k kernels w_f′f, while backpropagation computes input and weight gradients through further convolutions.The forward pass sums convolutions, the backward input gradient uses transposed kernels, and the weight gradient convolves inputs with output gradients.
- 2.2 Algorithm: The Convolution Theorem replaces circular spatial convolutions with pointwise Fourier-domain products followed by an inverse transform.The theorem is typically advantageous when the kernel size is close to the input-image size.
- 2.2 Algorithm: The algorithm computes each matrix’s FFT once, then reuses those transforms for all pairwise convolutions between f input and f′ output feature maps.This reuse can outweigh FFT overhead even when FFTs are not optimal for an individual convolution.
- 2.2 Algorithm: The direct forward computation requires S·f′·f·(n−k+1)^2·k^2 operations, whereas the FFT approach combines transform costs with 4S·f′·f·n^2 frequency-domain operations.The direct method’s complexity multiplies five terms, while the FFT method uses a sum of products with at most four terms.
- 2.3 Implementation and Memory Considerations: A custom CUDA Cooley–Tukey implementation parallelizes over feature maps, minibatches, and the rows and columns of each 2-D transform.This design addresses the limitations of GPU FFT implementations optimized for fewer transforms on larger inputs.
- 2.2 Algorithm: The FFT method crops circular-convolution outputs to match direct-convolution dimensions without additional computation.The output excludes coefficients for which the kernel is not fully contained within the input image.
- 2.3 Implementation and Memory Considerations: Frequency-domain representations are stored for inputs, outputs, and kernels, while shared memory reuse limits allocation to the largest convolution layer.Real-input FFT symmetry can reduce storage to n(n+1)/2 complex numbers; the additional memory is described as relatively small compared with large networks.
3 Experiments
Experiments compare the FFT-based method with two direct spatial-domain GPU implementations across convolution settings and network configurations. The FFT-based method consistently achieves faster performance, including complete training iterations.
- Experimental setup: The experiments compared the proposed method with CudaConv and a Torch 7 implementation on the same GeForce GTX Titan GPU.Both comparison implementations used direct spatial-domain convolutions.
- Speed comparisons: The speed tests varied input-image size, kernel size, and minibatch size using 96 input and 256 output feature maps.These feature-map counts represent a typical deep-network second-layer configuration.
- Speed comparisons: The FFT-based method significantly outperformed both alternatives in nearly all cases, especially for the computationally expensive accGradParameters operation.The authors attribute the especially strong improvement to the operation’s large kernel, for which FFTs are better suited.
- Speed comparisons: The FFT-based method’s speed was invariant to kernel size because kernels were padded to the input-image size before applying the FFT.This also enables use of much larger kernels.
- Layer configurations: Across configurations typical of different network layers, the FFT-based method was faster in total for every configuration.The improvement was especially significant on the forward pass, making the method suited to inference on very large datasets.
- End-to-end iteration: The FFT-based method still significantly outperformed both alternatives when measuring complete training iterations in a composed network.The composed network included the tested layers, max-pooling, rectified linear units, and a 1000-output fully connected prediction layer.
4 Discussion and Future Work
The paper presents FFT-based convolution as a fast approach for both training and inference, supported by numerical experiments. It identifies non-power-of-two input sizes as an implementation limitation and proposes larger-kernel and Fourier-domain extensions for future work.
- Discussion: The paper presents a simple, fast algorithm for training and inference that outperforms known state-of-the-art implementations in speed.The authors report verification through numerical experiments.
- Limitations: Current FFT implementation requires non-power-of-two input images to be padded to the next highest power of two.For example, a 34 × 34 input is padded to 64 × 64, which is suboptimal in speed; the authors plan to support other sizes.
- Future work: Kernel-size-invariant speed enables larger kernels at different network layers, which the authors plan to investigate further.They also plan to study how input-image and kernel sizes affect performance.