ACDC: A Structured Efficient Linear Layer

By Marcin Moczulski, Misha Denil, Jeremy Appleyard, Nando de Freitas. 2015

107 citations recorded by the source corpus.

The linear layer is one of the most pervasive modules in deep learning representations. However, it requires $O(N^2)$ parameters and $O(N^2)$ operations. These costs can be prohibitive in mobile applications or prevent scaling in many domains. Here, we introduce a deep, differentiable, fully-connected neural network module composed of diagonal matrices of parameters, $\mathbf{A}$ and $\mathbf{D}$, and the discrete cosine transform $\mathbf{C}$. The core module, structured as $\mathbf{ACDC^{-1}}$, has $O(N)$ parameters and incurs $O(N log N )$ operations. We present theoretical results showing how deep cascades of ACDC layers approximate linear layers. ACDC is, however, a stand-alone module and can be used in combination with any other types of module. In our experiments, we show that it can indeed be successfully interleaved with ReLU modules in convolutional neural networks for image recognition. Our experiments also study critical factors in the training of these structured modules, including initialization and depth. Finally, this paper also provides a connection between structured linear transforms used in deep learning and the field of Fourier optics, illustrating how ACDC could in principle be implemented with lenses and diffractive elements.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Efficiency & Compression

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Efficiency & Compression

Citations in the corpus

HyperNetworks (2016, background): “, 2016), and ACDC-Networks (Moczulski et al., 2015), where linear layers are compressed with DCT and the parameters are learned.”
Initialization and Regularization of Factorized Neural Layers (2021, background): “The success of SI and FD for both low-rank and tensor decomposition also suggests that these schemes may be useful for other types of factorized neural layers, such as ACDC (Moczulski et al., 2015) or K-matrices (Dao et al.”
Multiplicative LSTM for sequence modelling (2016, background): “The standard RNN units in an mRNN do not provide an easy way for information to bypass its complex transitions, resulting in the potential for difﬁculty in retaining long term information.”
Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization (2019, methodology): “, 2014), ACDC transform (Moczulski et al., 2015), HashedNet (Chen et al.”
FNet: Mixing Tokens with Fourier Transforms (2021, background): “For example, Moczulski et al. (2015) approximate individual linear layers with multiple sublayers of diagonal parameter matrix multiplications in the real and frequency domains, facilitated by discrete cosine transforms.”
Moonshine: Distilling with Cheap Convolutions (2017, background): “Future work could investigate more complicated approximate operations, such as those described in Moczulski et al. (2016); which could make a difference for the 1 × 1 convolutions in the ﬁnal layers of a network.”
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, background): “, 2013), ACDC (Moczulski et al., 2016)).”
Text Generation with Exemplar-based Adaptive Decoding (2019, unknown): “It is later revisited with representation learning (Moczulski et al., 2015; Fer-nando et al., 2016; Al-Shedivat et al., 2017, inter alia ), and successfully applied to classiﬁcation (Jia et al., 2016; Liu et al., 2017) and machine translation (Platanios et al., 2018).”
Building Efficient Deep Neural Networks With Unitary Group Convolutions (2018, methodology): “’s ACDC used cosine transforms to avoid complex values that arise with DFTs and added a second channel-wise filter [16].”
Small-Footprint Deep Neural Networks with Highway Connections for Speech Recognition (2015, background): “This work is in line with the argument that neural networks with dense connections are over-parameterised, and the linear layer may be replaced by structured efficient linear layers (SELLs) [14, 15, 16].”
A Survey of Model Compression and Acceleration for Deep Neural Networks (2017, methodology): “Most work used the average training time per epoch to measure the running time, while in [30], [71], the average testing time was used.”
Strongly-Typed Recurrent Neural Networks (2016, methodology): “Finally, (Moczulski et al., 2015) propose to accelerate matrix computations in feedforward nets by interleaving diagonal matrices, A and D, with the orthogonal discrete cosine transform, C.”
Model Compression and Acceleration for Deep Neural Networks: The Principles, Progress, and Challenges (2018, methodology): “Most work used the average training time per epoch to measure the running time, while in [30], [71], the average testing time was used.”
Separable Layers Enable Structured Efficient Linear Substitutions (2019, methodology): “Approaches for structured efficient linear layers (SELLs), such as ACDC (Moczulski et al., 2016), differ from other work in efficiency in that they provide a substitute to a fully connected layer, but are trained using the same methods that would otherwise be used (e.”
Learning Low-rank Deep Neural Networks via Singular Vector Orthogonality Regularization and Singular Value Sparsification (2020, background): “Early works in this field focus on designing the matrix and tensor decomposition scheme, especially for the 4-D tensor of convolution kernel, so that the operation of a pretrained network layer can be closely approximated with cascaded low-rank layers [15, 39, 26, 4, 19].”
A Two-pronged Progress in Structured Dense Matrix Vector Multiplication (2018, background): “Many ad-hoc paradigms exist for representing structured matrices in neural networks [36], and it turns out several of them are instances of a displacement rank structure.”
Monarch: Expressive Structured Matrices for Efficient and Accurate Training (2022, background): “The matrix class MM∗ can represent convolution, Hadamard transform, Toeplitz matrices (Gray, 2006), and AFDF matrices (Moczulski et al., 2016).”