mlsanityData to 7 Oct 2026

Random matrices in service of ML footprint: ternary random features with no performance loss

arXiv 2110.01899 ↗First posted 5 Oct 2021stat.ML cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

In this article, we investigate the spectral behavior of random features kernel matrices of the type bf K = mathbbE_bf w left[σleft(bf wsf Tbf xiright)σleft(bf wsf Tbf xjright)right]i,j=1n, with nonlinear function σ(·), data bf x1, ldots, bf xn ∈ ℝp, and random projection vector bf w ∈ ℝp having i.i.d. entries. In a high-dimensional setting where the number of data n and their dimension p are both large and comparable, we show, under a Gaussian mixture model for the data, that the eigenspectrum of bf K is independent of the distribution of the i.i.d.(zero-mean and unit-variance) entries of bf w, and only depends on σ(·) via its (generalized) Gaussian moments mathbbEz~ mathcal N(0,1)[σ'(z)] and mathbbEz~ mathcal N(0,1)[σ''(z)]. As a result, for any kernel matrix bf K of the form above, we propose a novel random features technique, called Ternary Random Feature (TRF), that (i) asymptotically yields the same limiting kernel as the original bf K in a spectral sense and (ii) can be computed and stored much more efficiently, by wisely tuning (in a data-dependent manner) the function σ and the random vector bf w, both taking values in -1,0,1. The computation of the proposed random features requires no multiplication, and a factor of b times less bits for storage compared to classical random features such as random Fourier features, with b the number of bits to store full precision values. Besides, it appears in our experiments on real data that the substantial gains in computation and storage are accompanied with somewhat improved performances compared to state-of-the-art random features compression/quantization methods.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 39 of its 77 references that are in the map. First posted on arXiv 5 Oct 2021.

Builds on

39 of 77 references.

References · 39

  1. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2015Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Codingcited by 2,291
  4. 2015Learning both Weights and Connections for Efficient Neural Networkscited by 1,998
  5. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  6. 2017Deep Neural Networks as Gaussian Processescited by 617
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  9. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  10. 2015Deep Learning with Limited Numerical Precisioncited by 368
  11. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  12. 2018Gaussian Process Behaviour in Wide Deep Neural Networkscited by 314
27 more
  1. 2017High-dimensional dynamics of generalization error in neural networkscited by 238
  2. 2018Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learningcited by 211
  3. 2016Trained Ternary Quantizationcited by 203
  4. 2014Compressing Deep Convolutional Networks using Vector Quantizationcited by 189
  5. 2020Binary Neural Networks: A Surveycited by 184
  6. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  7. 2018Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processescited by 164
  8. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 107
  9. 2019Traditional and Heavy-Tailed Self Regularization in Neural Network Modelscited by 104
  10. 2016Orthogonal Random Featurescited by 89
  11. 2017A Random Matrix Approach to Neural Networkscited by 80
  12. 2020Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networkscited by 76
  13. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 69
  14. 2020Implicit Regularization of Random Feature Modelscited by 54
  15. 2020Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixturescited by 47
  16. 2015Neural Networks with Few Multiplicationscited by 46
  17. 2020Kernel regression in high dimensions: Refined analysis beyond double descentcited by 39
  18. 2019Exact expressions for double descent and implicit regularization via surrogate random designcited by 35
  19. 2018On the Spectrum of Random Features Maps of High Dimensional Datacited by 27
  20. 2018The Dynamics of Learning: A Random Matrix Approachcited by 15
  21. 2020On Random Matrices Arising in Deep Neural Networks. Gaussian Casecited by 14
  22. 2020Sparse Quantized Spectral Clusteringcited by 9
  23. 2018Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximationcited by 7
  24. 2021Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clusteringcited by 7
  25. 2021Quantization Algorithms for Random Fourier Featurescited by 7
  26. 2018Data-dependent compression of random features for large-scale kernel approximationcited by 3
  27. 2019Inner-product Kernels are Asymptotically Equivalent to Binary Discrete Kernelscited by 2

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 2; 2024: 3.

7 papers.

  1. 2022Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networkscited by 12
  2. 2022Overparameterized random feature regression with nearly orthogonal datacited by 6
  3. 2023Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumptioncited by 6
  4. 2024Deep Equilibrium Models are Almost Equivalent to Not-so-deep Explicit Models for High-dimensional Gaussian Mixturescited by 6
  5. 2024"Lossless" Compression of Deep Neural Networks: A High-dimensional Neural Tangent Kernel Approachcited by 3
  6. 2024Deep Neural Network Models Trained With A Fixed Random Classifier Transfer Better Across Domainscited by 2
  7. 2023On the Equivalence between Implicit and Explicit Neural Networks: A High-dimensional Viewpointcited by 0