Fast Training of Convolutional Networks through FFTs

By Michaël Mathieu, Mikael Henaff, Yann LeCun. 2013

657 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition (2014, methodology): “To our knowledge, our method is the first one that trains a single network with input images of multiple sizes.”
Deep Convolutional Networks on Graph-Structured Data (2015, background): “Fourier implementations of Convnets [13, 19] bring the complexity to O ( N log N ) thanks again to the speciﬁc symmetries of the grid.”
Speeding up Convolutional Neural Networks with Low Rank Expansions (2014, methodology): “[23] performs convolutions in the Fourier domain through FFTs computed efficiently over batches of images on a GPU.”
Joint Training of a Convolutional Network and a Graphical Model for Human Pose Estimation (2014, methodology): “Therefore for such large kernels we use FFT convolutions based on the GPU implementation by [20].”
ShuffleNet: An Extremely Efficient Convolutional Neural Network for Mobile Devices (2017, methodology): “Without modifying the parameters, optimized convolution algorithms implemented by FFT [26, 36] and other methods [2] decrease time consumption in practice.”
cuDNN: Efficient Primitives for Deep Learning (2014, background): “The FFT can significantly lower the work complexity of the convolutions, and with clever engineering can be used effectively for deep neural networks [16].”
Pruning Filters for Efficient ConvNets (2016, methodology): “Other approaches to reduce the convolutional overheads include using FFT based convolutions (Mathieu et al. (2013)) and fast convolution using the Winograd algorithm (Lavin & Gray (2016)).”
Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation (2014, background): “[5] have shown that convolution can be efficiently computed in Fourier domain, where it becomes element-wise multiplication (and there is no cost associated with size of receptive field).”
Compressing Deep Convolutional Networks using Vector Quantization (2014, background): “Mathieu et al. (2013) showed that the convolutional operation can be efﬁciently carried out in the Fourier domain, which leads to a speed-up of 200%.”
Recent advances in convolutional neural networks (2015, methodology): “, [32]) that employ FFT for convolution kernels.”
AMC: AutoML for Model Compression and Acceleration on Mobile Devices (2018, background): “10, 41] and special convolution implementations [36, 48, 29, 3] can also speed up the neural networks.”
Conditional Time Series Forecasting with Convolutional Neural Networks (2017, methodology): “…for longer time series the prediction of the autoregressive model may be sped up by implementing a recent variation that exploits the memorization structure of the network, see [21] or speeding up the convolutions by working in the frequency domain emloying Fourier transforms as in [19], [22].”
Group Equivariant Convolutional Networks (2016, methodology): “Here we present the details for a G-convolution implementation that can leverage recent advances in fast computation of planar convolutions (Mathieu et al., 2014; Vasilache et al., 2015; Lavin & Gray, 2015).”
Spectral Representations for Convolutional Neural Networks (2015, background): “More recently, Mathieu et al. (2013); Vasilache et al.”
Compressing Convolutional Neural Networks in the Frequency Domain (2015, methodology): “[38] convert the filter to its frequency domain of size n × n by oversampling the frequencies, which is necessary for doing element-wise multiplication with a larger image but also increases the memory overhead at test time.”
Fast ConvNets Using Group-Wise Brain Damage (2015, methodology): “In parallel to the lowering-based approaches mentioned above, which reduce convolutions to matrix multiplications, several works investigate the use of fast Fourier transforms [36, 44].”
Accelerating Very Deep Convolutional Networks for Classification and Detection (2015, background): “Besides, the layers of a very deep model may exhibit a great diversity in filter numbers, feature map sizes, sparsity, and redundancy.”
Speeding-up Convolutional Neural Networks Using Fine-tuned CP-Decomposition (2014, background): “Consequently, there is a strong interest to the task of improving the efﬁciency of this operation (Chintala, 2014; Mathieu et al., 2013; Chellapilla et al., 2006).”
Channel Pruning for Accelerating Very Deep Neural Networks (2017, methodology): “Optimized implementation based methods [36, 48, 27, 4] accelerate convolution, with special convolution algorithms like FFT [48].”
Dynamic Network Surgery for Efficient DNNs (2016, background): “[18] explore the fast Fourier transforms (FFTs) on GPUs and improve the speed of CNNs by performing convolution calculations in the frequency domain.”