2018

On the Spectrum of Random Features Maps of High Dimensional Data

Liao, Zhenyu, Couillet, Romain

Understand

Random feature maps are ubiquitous in modern statistical machine learning, where they generalize random projections by means of powerful, yet often difficult to analyze nonlinear operators.

In this paper, we leverage the "concentration" phenomenon induced by random matrix theory to perform a spectral analysis on the Gram matrix of these random feature maps, here for Gaussian mixture models of simultaneously large dimension and size.
Our results are instrumental to a deeper understanding on the interplay of the nonlinearity and the statistics of the data, thereby allowing for a better tuning of random feature-based techniques.

Built on

Distribution of eigenvalues for some sets of random matrices
Marčenko, V. A. and Pastur, L. A · 1967
Earlier work this paper cites.
On the empirical distribution of eigenvalues of a class of large dimensional random matrices
Silverstein, J. W. and Bai, Z · 1995
Earlier work this paper cites.
Computing with infinite networks
Williams, C. K · 1997
Earlier work this paper cites.
The MNIST database of handwritten digits, 1998
LeCun, Y., Cortes, C., and Burges, C. J · 1998
Earlier work this paper cites.
Indications of nonlinear deterministic and finite-dimensional structures in time series of brain electrical activity: Dependence on recording region and brain state
Andrzejak, R. G., Lehnertz, K., Mormann, F., Rieke, C., David, P., and Elger, C. E · 2001
Earlier work this paper cites.
On spectral clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., and Weiss, Y · 2002
Earlier work this paper cites.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Schölkopf, B. and Smola, A. J · 2002
Earlier work this paper cites.
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Baik, J., Arous, G. B., Péché, S., et al · 2005
Earlier work this paper cites.

Similar

Random features for large-scale kernel machines
Rahimi, A. and Recht, B · 2008
Cited alongside, same era.
The spectrum of kernel random matrices
El Karoui, N. et al · 2010
Cited alongside, same era.
Matrix analysis
Horn, R. A. and Johnson, C. R · 2012
Cited alongside, same era.
Extreme learning machine for regression and multiclass classification
Huang, G.-B., Zhou, H., Ding, X., and Zhang, R · 2012
Cited alongside, same era.
Imagenet classification with deep convolutional neural networks
Krizhevsky, A., Sutskever, I., and Hinton, G. E · 2012
Cited alongside, same era.
Efficient additive kernels via explicit feature maps
Vedaldi, A. and Zisserman, A · 2012
Cited alongside, same era.
The spectrum of random inner-product kernel matrices
Cheng, X. and Singer, A · 2013
Cited alongside, same era.
Rectifier nonlinearities improve neural network acoustic models
Maas, A. L., Hannun, A. Y., and Ng, A. Y · 2013
Cited alongside, same era.

Then

Deep learning in neural networks: An overview
Schmidhuber, J · 2015
Later among the works it cites.
Kernel spectral clustering of large dimensional data
Couillet, R., Benaych-Georges, F., et al · 2016
Later among the works it cites.
Sketching for large-scale learning of mixture models
Keriven, N., Bourrier, A., Gribonval, R., and Pérez, P · 2016
Later among the works it cites.
Random synaptic feedback weights support error backpropagation for deep learning
Lillicrap, T. P., Cownden, D., Tweed, D. B., and Akerman, C. J · 2016
Later among the works it cites.
Spectral community detection in heterogeneous large networks
Original
Tiomoko Ali, H. and Couillet, R · 2016
Later among the works it cites.
Nonlinear random matrix theory for deep learning
Pennington, J. and Worah, P · 2017
Later among the works it cites.
Randomness in neural networks: an overview
Scardapane, S. and Wang, D · 2017
Later among the works it cites.
A random matrix approach to neural networks
Louart, C., Liao, Z., Couillet, R., et al · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…