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

In this article, we investigate the spectral behavior of random features kernel matrices of the type K = E w [σ(w T x i )σ(w T x j )] n i,j=1 , with nonlinear function σ(•), data x 1 , . . . , x n ∈ R p , and random projection vector w ∈ R 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 K is independent of the distribution of the i.i.d. (zero-mean and unit-variance) entries of w, and only depends on σ(•) via its (generalized) Gaussian moments E z∼N (0,1) [σ ′ (z)] and E z∼N (0,1) [σ ′′ (z)]. As a result, for any kernel matrix 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 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 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. Published as a conference paper at ICLR 2022 Laplacian kernel for Cauchy distributed w with the same choice of σ) (Rahimi & Recht, 2008) ; for σ(x) = max(x, 0), one approximates the first order Arc-cosine kernel; and the zeroth order Arc-cosine kernel (Cho, 2012) with σ(x) = (1 + sign(x))/2, etc. As shall be seen subsequently, (random) neural networks are, to a large extent, connected to kernel matrices of the form (1). More specifically, the classification or regression performance at the output of random neural networks are functionals of random matrices that fall into the wide class of kernel random matrices. Perhaps more surprisingly, this connection still exists for deep neural networks which are (i) randomly initialized and (ii) trained with gradient descent, as testified by the recent works on neural tangent kernels (Jacot et al., 2018) , by considering the "infinitely many neurons" limit, that is, the limit where the network widths of all layers go to infinity simultaneously. This close connection between neural networks and kernels has triggered a renewed interest for the theoretical investigation of deep neural networks from various perspectives, including optimization (