CoChat
Sign Up
PreprintCited by 21Advanced Neural Network ApplicationsNeural Networks and ApplicationsStochastic Gradient Optimization Techniques

Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps

Open access
Dao, Tri, Sohoni, Nimit S., Gu, Albert, Eichhorn, Matthew, Blonder, Amit, Leszczynski, Megan, Rudra, Atri, Ré, Christopher·2020·arXiv
DOI 10.48550/arxiv.2012.14966arXiv 2012.14966
Open this paper in CoChat — free accountOpen PDF

Abstract

Modern neural network architectures use structured linear transformations, such as low-rank matrices, sparse matrices, permutations, and the Fourier transform, to improve inference speed and reduce memory usage compared to general linear maps. However, choosing which of the myriad structured transformations to use (and its associated parameterization) is a laborious task that requires trading off speed, space, and accuracy. We consider a different approach: we introduce a family of matrices called kaleidoscope matrices (K-matrices) that provably capture any structured matrix with near-optimal space (parameter) and time (arithmetic operation) complexity. We empirically validate that K-matrices can be automatically learned within end-to-end pipelines to replace hand-crafted procedures, in order to improve model quality. For example, replacing channel shuffles in ShuffleNet improves classification accuracy on ImageNet by up to 5%. K-matrices can also simplify hand-engineered pipelines -- we replace filter bank feature computation in speech data preprocessing with a learnable kaleidoscope layer, resulting in only 0.4% loss in accuracy on the TIMIT speech recognition task. In addition, K-matrices can capture latent structure in models: for a challenging permuted image classification task, a K-matrix based representation of permutations is able to learn the right latent structure and improves accuracy of a downstream convolutional model by over 9%. We provide a practically efficient implementation of our approach, and use K-matrices in a Transformer network to attain 36% faster end-to-end inference speed on a language translation task.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2012.14966

Cites

4 of 4 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Butterfly matrices and their products have been shown to be able to express any structured matrices with almost optimal runtime and number of parameters.

    “The butterfly pattern we use for our block-sparse attention is motivated by the fact that butterfly matrices [15, 64] and their products have been shown to be able to express any structured matrices with almost optimal runtime and number of parameters [16, 20].”

    From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [16]

  • The fixed butterfly sparsity pattern can approximate arbitrary sparsity.

    “For downstream experiments, we use the fixed butterfly sparsity pattern [17], which has been shown to be able to approximate arbitrary sparsity [16].”

    From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [16]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 80

  1. Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In International Conference on Machine Learning , pp. 1120-1128, 2016.
  2. Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271 , 2018. · arXiv
  3. Peter L. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piecewise polynomial networks. In Advances in Neural Information Processing Systems , pp. 190-196, 1999.
  4. Václav E Benes. Permutation groups, complexes, and rearrangeable connecting networks. Bell System Technical Journal , 43(4):1619-1640, 1964.
  5. Václav E Benes. Mathematical theory of connecting networks and telephone traffic . Academic press, 1965.
  6. Peter Bürgisser, Michael Clausen, and Mohammad A. Shokrollahi. Algebraic complexity theory , volume 315. Springer Science & Business Media, 2013.
  7. Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078 , 2014. · arXiv
  8. Krzysztof Choromanski, Mark Rowland, Wenyu Chen, and Adrian Weller. Unifying orthogonal Monte Carlo methods. In International Conference on Machine Learning , pp. 1203-1212, 2019.
  9. Ronan Collobert, Christian Puhrsch, and Gabriel Synnaeve. Wav2Letter: an end-to-end ConvNet-based speech recognition system. arXiv preprint arXiv:1609.03193 , 2016. · arXiv
  10. James W. Cooley, Peter A. W. Lewis, and Peter D. Welch. The fast fourier transform and its applications. IEEE Transactions on Education , 12(1), 1969.
  11. William James Dally and Brian Patrick Towles. Principles and practices of interconnection networks . Elsevier, 2004.
  12. Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Ré. Learning fast algorithms for linear transforms using butterfly factorizations. In The International Conference on Machine Learning (ICML) , 2019.
  13. Christopher De Sa, Albert Gu, Rohan Puttagunta, Christopher Ré, and Atri Rudra. A two-pronged progress in structured dense matrix vector multiplication. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pp. 1060-1079. SIAM, 2018.
  14. Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.04840 , 2019. · arXiv
  15. J. R. Driscoll, D. M. Healy, Jr., and D. N. Rockmore. Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comput. , 26(4):1066-1099, August 1997. ISSN 0097-5397. doi: 10.1137/S0097539792240121. URL http://dx.doi.org/10.1137/S0097539792240121 . · DOI
  16. Utku Evci, Trevor Gale, Jacob Menick, Pablo S. Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. arXiv preprint arXiv:1911.11134 , 2019. · arXiv
  17. Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations (ICLR) , 2019.
  18. Hormozd Gahvari, Mark Hoemmen, James Demmel, and Katherine Yelick. Benchmarking sparse matrix-vector multiply in five minutes. In SPEC Benchmark Workshop , 2007.
  19. Pegah Ghahremani, Vimal Manohar, Daniel Povey, and Sanjeev Khudanpur. Acoustic modelling from the signal domain using CNNs. In Interspeech , pp. 3434-3438, 2016.
  20. Robert M. Gray. Toeplitz and circulant matrices: A review. Foundations and Trends® in Communications and Information Theory , 2(3):155-239, 2006.
  21. Scott Gray, Alec Radford, and Diederik P. Kingma. GPU kernels for block-sparse weights. arXiv preprint arXiv:1711.09224 , 2017. · arXiv
  22. Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In International Conference on Learning Representations (ICLR) , 2016.
  23. Fredric J. Harris. On the use of windows for harmonic analysis with the discrete fourier transform. In Proceedings of the IEEE , 1978.
  24. Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension bounds for piecewise linear neural networks. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory , volume 65 of Proceedings of Machine Learning Research , pp. 1064-1068, Amsterdam, Netherlands, 07-10 Jul 2017. PMLR. URL http://proceedings.mlr.press/v65/harvey17a.html .
  25. David P. Helmbold and Manfred K. Warmuth. Learning permutations with exponential weights. Journal of Machine Learning Research , 10(Jul):1705-1736, 2009.
  26. Alston S. Householder. Unitary triangularization of a nonsymmetric matrix. J. ACM , 5(4):339-342, October 1958. ISSN 0004-5411. doi: 10.1145/320941.320947. URL http://doi.acm.org/10.1145/320941.320947 . · DOI
  27. Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljacić. Tunable efficient unitary neural networks (EUNN) and their application to RNNs. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 , pp. 1733-1741. JMLR. org, 2017.
  28. Dan Jurafsky and James H. Martin. Speech and language processing , volume 3. Pearson London, 2014.
  29. Thomas Kailath, Sun-Yuan Kung, and Martin Morf. Displacement ranks of matrices and linear equations. Journal of Mathematical Analysis and Applications , 68(2):395-407, 1979.
  30. Yuehaw Khoo and Lexing Ying. SwitchNet: a neural network model for forward and inverse scattering problems. SIAM Journal on Scientific Computing , 41(5):A3182-A3201, 2019.
  31. Donald Ervin Knuth. The art of computer programming, Volume 3: Sorting and Searching . Pearson Education, 1997.
  32. Quoc Le, Tamás Sarlós, and Alexander Smola. Fastfood-computing hilbert space expansions in loglinear time. In International Conference on Machine Learning , pp. 244-252, 2013.
  33. Quoc V. Le, Navdeep Jaitly, and Geoffrey E. Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv:1504.00941 , 2015. · arXiv
  34. Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research , 18(1): 6765-6816, 2017.
  35. Yingzhou Li, Haizhao Yang, Eileen R. Martin, Kenneth L. Ho, and Lexing Ying. Butterfly factorization. Multiscale Modeling & Simulation , 13(2):714-732, 2015.
  36. Yingzhou Li, Haizhao Yang, and Lexing Ying. Multidimensional butterfly factorization. Applied and Computational Harmonic Analysis , 44(3):737-758, 2018.
  37. Yingzhou Li, Xiuyuan Cheng, and Jianfeng Lu. Butterfly-Net: Optimal function representation based on convolutional neural networks. Communications in Computational Physics , 28(5):1838-1885, 2020.
  38. Fu-Hua Liu, Richard M. Stern, Xuedong Huang, and Alejandro Acero. Efficient cepstral normalization for robust speech recognition. In ARPA Workshop on Human Language Technology , 1993.
  39. Jiancheng Lyu, Shuai Zhang, Yingyong Qi, and Jack Xin. Autoshufflenet: Learning permutation matrices via an exact lipschitz continuous penalty in deep convolutional neural networks. arXiv preprint arXiv:1901.08624 , 2019. · arXiv
  40. J. Makhoul. A fast cosine transform in one and two dimensions. IEEE Transactions on Acoustics, Speech, and Signal Processing , 28(1):27-34, February 1980. ISSN 0096-3518. doi: 10.1109/TASSP.1980.1163351. · DOI
  41. Michael Mathieu and Yann LeCun. Fast approximation of rotations and Hessians matrices. arXiv preprint arXiv:1404.7195 , 2014. · arXiv
  42. Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with Gumbel-Sinkhorn networks. In International Conference on Learning Representations , 2018. URL https: //openreview.net/forum?id=Byt3oJ-0W .
  43. Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 , pp. 2401-2409. JMLR. org, 2017.
  44. Marcin Moczulski, Misha Denil, Jeremy Appleyard, and Nando de Freitas. ACDC: a structured efficient linear layer. In International Conference on Learning Representations , 2016.
  45. Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In The International Conference on Machine Learning (ICML) , 2019.
  46. Marina Munkhoeva, Yermek Kapushev, Evgeny Burnaev, and Ivan Oseledets. Quadrature-based features for kernel approximation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31 , pp. 9165-9174. Curran Associates, Inc., 2018.
  47. Vadim Olshevsky and Mohammad Amin Shokrollahi. Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA , pp. 573-581, 2000. doi: 10.1145/335305.335380. URL http://doi.acm.org/10.1145/335305.335380 . · DOI
  48. Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of NAACL-HLT 2019: Demonstrations , 2019.
  49. Dimitri Palaz, Ronan Collobert, and Mathew Magimai-Doss. Estimating phoneme class conditional probabilities from raw speech signal using convolutional neural networks. In Interspeech , 2013.
  50. Kuldip Paliwal. On the use of filter-bank energies as features for robust speech recognition. In International Symposium on Signal Processing and its Applications (ISSPA) , 1999.
  51. Victor Y. Pan. Structured Matrices and Polynomials: Unified Superfast Algorithms . Springer-Verlag New York, Inc., New York, NY, USA, 2001. ISBN 0-8176-4240-4.
  52. Victor M. Panaretos and Shahin Tavakoli. Fourier analysis of stationary time series in function space. The Annals of Statistics , 41(2):568-603, 2013.
  53. Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In Advances in Neural Information Processing Systems (NeurIPS) - Autodiff Workshop , 2017.
  54. Daniel Povey, Arnab Ghoshal, Gilles Boulianne, Lukas Burget, Ondrej Glembek, Nagendra Goel, Mirko Hannemann, Petr Motlicek, Yanmin Qian, Petr Schwarz, Jan Silovsky, Georg Stemmer, and Karel Vesely. The kaldi speech recognition toolkit. In IEEE 2011 Workshop on Automatic Speech Recognition and Understanding . IEEE Signal Processing Society, 2011.
  55. Mirco Ravanelli and Yoshua Bengio. Speaker recognition from raw waveform with sincnet. In IEEE Workshop on Spoken Language Technology , 2018.
  56. Mirco Ravanelli, Philemon Brakel, Maurizio Omologo, and Yoshua Bengio. Light gated recurrent units for speech recognition. In IEEE Transactions on Emerging Topics in Computational Intelligence , volume 2, pp. 92-102, 2018.
  57. Mirco Ravanelli, Titouan Parcollet, and Yoshua Bengio. The PyTorch-Kaldi speech recognition toolkit. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) , 2019.
  58. Vladimir Rokhlin and Mark Tygert. Fast algorithms for spherical harmonic expansions. SIAM Journal on Scientific Computing , 27(6):1903-1928, 2006.
  59. Leonid I. Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena , 60(1-4):259-268, 1992.
  60. Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV) , 115(3):211-252, 2015. doi: 10.1007/s11263-015-0816-y. · DOI · Paper page
  61. Tara N. Sainath, Ron J. Weiss, Andrew Senior, Kevin W. Wilson, and Oriol Vinyals. Learning the speech front-end with raw waveform CLDNNs. In Interspeech , 2015.
  62. Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. Green AI. arXiv preprint arXiv:1907.10597 , 2019. · arXiv
  63. Vikas Sindhwani, Tara N. Sainath, and Sanjiv Kumar. Structured transforms for small-footprint deep learning. In Advances in Neural Information Processing Systems , pp. 3088-3096, 2015.
  64. Anna T. Thomas, Albert Gu, Tri Dao, Atri Rudra, and Christopher Ré. Learning compressed transforms with low displacement rank. In Advances in Neural Information Processing Systems (NeurIPS) , 2018.
  65. Trieu H. Trinh, Andrew M Dai, Minh-Thang Luong, and Quoc V. Le. Learning longer-term dependencies in RNNs with auxiliary losses. arXiv preprint arXiv:1803.00144 , 2018. · arXiv
  66. Mark Tygert. Fast algorithms for spherical harmonic expansions, ii. Journal of Computational Physics , 227 (8):4260-4279, 2008.
  67. Mark Tygert. Fast algorithms for spherical harmonic expansions, iii. Journal of Computational Physics , 229 (18):6181-6192, 2010a.
  68. Mark Tygert. Recurrence relations and fast algorithms. Applied and Computational Harmonic Analysis , 28 (1):121-128, 2010b.
  69. Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. WaveNet: A generative model for raw audio. arXiv preprint arXiv:1609.03499 , 2016. · arXiv
  70. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS) , 2017.
  71. Scott Wisdom, Thomas Powers, John Hershey, Jonathan Le Roux, and Les Atlas. Full-capacity unitary recurrent neural networks. In Advances in Neural Information Processing Systems , pp. 4880-4888, 2016.
  72. Felix Wu, Angela Fan, Alexei Baevski, Yann N Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. In International Conference on Learning Representations (ICLR) , 2019.
  73. Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition , pp. 1492-1500, 2017.
  74. Felix X. Yu, Sanjiv Kumar, Henry A. Rowley, and Shih-Fu Chang. Compact nonlinear maps and circulant extensions. CoRR , abs/1503.03893, 2015. · arXiv
  75. Felix X. Yu, Ananda T. Suresh, Krzysztof M. Choromanski, Daniel N. Holtmann-Rice, and Sanjiv Kumar. Orthogonal random features. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29 , pp. 1975-1983. Curran Associates, Inc., 2016.
  76. Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , 2017.
  77. Neil Zeghidour, Nicolas Usunier, Iasonas Kokkinos, Thomas Schatz, Gabriel Synnaeve, and Emmanuel Dupoux. Learning filterbanks from raw speech for phone recognition. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) , 2018.
  78. Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , pp. 6848-6856, 2018.
  79. Ritchie Zhao, Yuwei Hu, Jordan Dotzel, Christopher De Sa, and Zhiru Zhang. Building efficient deep neural networks with unitary group convolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , pp. 11303-11312, 2019.
  80. Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01878 , 2017. · arXiv

Cited by

Sorted by citations

Authors
Dao, T., Sohoni, N. S., Gu, A., Eichhorn, M., Blonder, A., Leszczynski, M., Rudra, A., & Ré, C.
Affiliations
  • Stanford University (US)
  • Cornell University (US)
  • University at Buffalo, State University of New York (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2012.14966
arXiv
2012.14966
OpenAlex
W2996641029
Cited by
21
References
4
Citations by year
2026: 1 · 2025: 2 · 2024: 2 · 2023: 5 · 2022: 2 · 2021: 6 · 2020: 3
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1763315, 1563078, 1937301)
  • Gordon and Betty Moore Foundation
  • Accenture
  • Swiss Re
  • National Institutes of Health (N000141712266, CCF1563078, CCF1763315)
  • Defense Advanced Research Projects Agency (FA86501827882, FA8750-17-2-0095, FA86501827865)
  • Office of Naval Research (N000141712266)
  • National Institute of Biomedical Imaging and Bioengineering (U54EB020405)
Topics
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
Keywords
low-rank matrices, sparse matrices, permutation matrices, Fourier transform, channel shuffle, ShuffleNet, speech preprocessing, filter banks, latent structure, language translation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review