Random matrices in service of ML footprint: ternary random features with no performance loss
Authors: Hafiz Tiomoko Ali
Zhenyu Liao
Romain Couillet
Venue: ICLR 2022 Poster (2022)
Keywords: Computationally efficient methods
kernel methods
random features
random matrix theory

Abstract: In this article, we investigate the spectral behavior of random features kernel matrices of the type ${\bf K} = \mathbb{E}_{{\bf w}} \left[\sigma\left({\bf w}^{\sf T}{\bf x}_i\right)\sigma\left({\bf w}^{\sf T}{\bf x}_j\right)\right]_{i,j=1}^n$, with nonlinear function $\sigma(\cdot)$, data ${\bf x}_1, \ldots, {\bf x}_n \in \mathbb{R}^p$, and random projection vector ${\bf w} \in \mathbb{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 ${\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 $\sigma(\cdot)$ via its (generalized) Gaussian moments $\mathbb{E}_{z\sim \mathcal N(0,1)}[\sigma'(z)]$ and $\mathbb{E}_{z\sim \mathcal N(0,1)}[\sigma''(z)]$. As a result, for any kernel matrix ${\bf K}$ of the form above, we propose a novel random features technique, called Ternary Random Features (TRFs), 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 $\sigma$ 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 methods.

Published as a conference paper at ICLR 2022
RANDOM MATRICES IN SERVICE OF ML FOOTPRINT:
TERNARY RANDOM FEATURES WITH NO PERFOR-
MANCE LOSS
Hafiz Tiomoko Ali
Zhenyu Liao
Huawei Noah's Ark Lab (London) hafiz. timmoko al @huawei. com
Huazhong University of Science & Technology, China liac@hust....... edu.
Romain Couillet
University Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France romain.
grenooleeeobleeeee alpes. fr
ABSTRACT
In this article, we investigate the spectral behavior of random features kernel matrices of the type K = Fo (a))o((' (wTxx))],, xy]] with nonlinear function
ol),, data XI,...,X,, E IRP, and random projection vector E IR having i.idd entries. In a high-dimensional setting where the number of data n and their dimension p are both large and comparable, we show, under Gaussian mixture model for the data, that the eigenspectrum K is independent of the distribution of the i.i.d. (zero-mean and unit-variance) entries of w, and only depends
a(-) via its (generalized) Gaussian moments F ( [a (z)] and E E=~A (o" (=)). As result, for any kernel matrix K of the form above, we propose novel random features technique, called Ternary Random Feature (TRF), that (i) asymptotically yields the same limiting kernel the original K in spectral sense and (ii) can be computed and stored much more efficiently. by wisely tuning (in data-dependee manner) the function and the random vector w, both taking values in (-1, 0, 1}. The computation of the proposed random features requires multiplication, and a factor of times less bits for storage compared to classical random features such as random Fourier features, with 6 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-an random features compression/quanization methods.
INTRODUCTION
Kernel methods are among the most powerful machine learning approaches with wide range of successful applications (Schölkopf & Smola 2018) which, however, suffer from scalability issues in large-scale problems, due to their high space and time complexities (with respect to the number of data rt). To address this key limitation, myriad of random features based kernel approximation techniques have been proposed (Rahimi & Recht 2008 Liu et al., 2021a): random features methods randomly project the data obtain low-dimenne diwdeennsional nonlinear representations that approximate the original kernel features. This allows practitioners to apply them, with a large saving in both time and space, various kernel-based downstream tasks such kernel spectral clustering (Von Luxburg 2007), kernel principal component analysis (Schölkopf et al. 1997), kereel canonical correlation analysis (Lai & Fyfe 22000), kernel ridge regression (Vovk] 2013). name a few. A wide variety of these kernels can be written, for data points x,, X, E R in the form
(1) with w E RP having i.idd entries, which can be "well approximated" by a sample mean L >Σ (w/x)) x;) a (w]x,) over m independent random features for m sufficiently large. For instance, taking (x) = [cos(z), sin(x)) and w with i.idd standard Gaussian entries, one ob- tains the popular Random Fourier Features (RFFs) that approximate the Gaussian kernel (and the
<(x, x,) Ew lor (w x;) (wTx,)
(w (wTx,)

---

Published as a conference paper at ICLR 2022
Laplacian kernel for Cauchy distributed w with the same choice of σ) (Rahimi & Recht 2008); for (z) = max( zr 0). one approximates the first order Are-cosine kernel; and the zeroth order Are-cosine kernel (Cho 2012) with (zx) (1 + sign(z))/2. etc.
As shall be seen subsequently, (random) neural networks are, to a large extent, connected to kemel matrices of the form (I. More specifically, the classification regression performance 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 al. 2018), by considering the "infinitely many neurons" limit, that is, the limit where the network widths of all layers go to infinity simultancously. 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 (Du et al. 2019; Chizat et al., (219), generalization (Allen-Zhu al. 2018 AArora et al. 2019 Bietti Mairal 2019), and learning dynamics (Lee et al. 2019 Advani et al. 2020: Liao & Couillet (018a). These works shed new light on the theoretical understanding of deep neural network models and specifically demonstrate the significance of studying networks with random weights and their associated kernels to assess the mechanisms underlying more elaborate deep networks.
In this article, we consider the random feature kernel of the type [ which can also be seen the limiting kernel of a single-hidden-llyer neural network with a random first layer. By assuming a high-dimensional Gaussian Mixture Model (GMM) for the data {x,) with x; IR", we show that the centered kernel matrix
1 PÅL 1 1
K A (xx(
is asymptotically (as n. + oo with p/n c (0, oo)) equivalent, in a spectral sense, to another random kernel matrix K which depends on the GMM data statistics and the generalized Gaussian moments [2)], Elo"(=)) of the activation function (-),, but is independent of the specific law of the i..d. entries of the random vector w, as long as they are normalized to have zero mean and unit variance. As such, one can design novel random features schemes with limiting kernels asymptotically K. For instance, define
equivalent to the original
K ter Xx) e Ewtee [oter (x. w o fer (x, w (cr)
(3)
with wee E RR having i.i.d. entries taking value wher (with probability e) and value
ter E { -) c) {
(4)
each with probability 1/2 e/2, where e [0, represents the level of sparsity of w, and
o ter (L) =-1 decs
(5)
for some thresholds s.. < 8. chosen to match the generalized Gaussian moments E|o (=)), of any function (e.g., ReLU, cos, sin) widely used in random features or neural network contexts. The proposed Ternary Random Features (TRFs, with limiting kernel matrices defined in (3) asymp- totically "matching" any random features kernel matrices in a spectral sense) have the computational advantage of being sparse and not requiring multiplications but only additions, as well as the storage advantage of being composed of only a finite set of words, e.g., {-1,0, 0, 1} for c c.
Given the urgent need for environmentally frriii but still efficient, neural networks such as binary neural networks (Hubara et al.) 2016 Lin et al. [015] Zhu al.] 2016]] Qin et al.) [0200] Hubaral al. 2016). pruned neural networks (Liu et al. 2015 Han et al. b), weights-quantized neural networks (Gupta et al. 2015) Gong et al. 2014), we hope that our analysis will open new door to a random matrix-impi improvedd framework of computationally efficient methods for machine learning and neural network models more generally.
Leftt and right- mightllulii the kernel matrices by P is equivalent to centering the data in the kernel feature space, which is a common practice in kernel learning and plays a crucial role in multidimensional scaling (Joseph) & Myron| 1978) and kernel PCA (Schlkopf et al. 1998). In the remainder of this paper, whenever we use kerel matrices, they are considered to have heen centered in this way.
2

---

Published as a conference paper at ICLR 2022
0.8
Accuracy
0.7
LP-RFF (8 bit)
LP-RFF bit)
Nyström (32 hits)
Nyström (16 bits)
0.6
Proposed TRF
10
10
10?
10
Memory (bits)
Figure 1: Test accuracy of logistic regression on quantized random features for different number of features m E (102, 10 5.10", ; 10", 5.10"), with LP-RFF (8-bit and 1 1-bit, in black) (Zhang et al. 2019). Nyström approximation (32 bits in red, 16 bits in green) (Williams Seeger (001), versus the proposed TRF approach (in blue), on the two-class Cov-Type dataset from UCI ML repo, with n 418 000 training samples, Nhtest = 116 000 test samples, and data dimension p = 54.
1.1 CONTRIBUTIONS
Our main results are summarized as follows.
By considering high-dimensional Gaussian mixture model for the data, we show (Theo- rem D that for K defined in (2) || K - as n,P -> Do, where K a random matrix independent of the law of w, and depends on the nonlinear a(-) only via its generalized Gaussian moments E[o' and E[a" (2)] for 2 ~ (0,
2. We exploit this result to propose computationally efficient random features approach, called Ternary Random Features (TRFs), with asymptotically the same limiting kernel as any random features-type kernel matrices K of the form (2). while inducing no multiplication and b times less memory storage for its computation, with b the number of bits to store full precision values, e.g., = 32 in the case of a Langle-precssin floating point format.
3.
We provide empirical evidence on various random-features based algorithms, showing the computational and storage advantages of the proposed TRF method, while achieving competitive performances compared to state-of-the-at random features techniques. As first telling example, in Figure D on the Cov-Type dataset from the UCI MI. rRpssitory.TRFss achieve similar logistic regression performance as the I.-RFF method proposed by /Zhang al. (2019), with 8 times less memory, and 32 16 times less memory than the Nyström approximation of the Gaussian kernel (using full precision of 32 or 16 bits) (Williams & Seeger 2001); see the shift in the x-axis (memory) of Figure
1.2 RELATED WORK
Random features kernel and random neural networks. Random features methods were first
proposed to relieve the computational and storage burden of kernel methods in large-scale problems when the number of training samples n is large (Schölkopf & Smola 2018 Rahimi & Recht 2008)] Liu et al. 2021a). For instance, Random Fourier Features can be used to approximate the popular Gaussian kernel, when the number of random features m is sufficiently large (Rahimi & Recht
2008). Since (deep) modern neural networks are routinely trained with random initialization, random features method is also considered a stylish model to analyze neural networks (Neal) 1996) Williams
1997 Novak et al., 2018 Matthews al. 2018 Lee al. 2017 Louart et al.) 2018). particular, by focusing on the large n. y regime, the analysis of such models led to the so-called double descent
theory Advani et al. 2020 Mei & Montanari 2019 Liao et 2020 for neural nets.
Computationally efficient random features methods. tion and storage costs of random features models, various quantization and binarization methods were proposed (Goemans & Williamson, 1995 Charikar
In effort to further reduce the computa-
2002
Li & Slawski] 2017 Li & Li 2019 2021
3

---

Published as a conference paper at ICLR 2022
Agrawal et al.
More precisely, (019) combined RFFs with a data-dependent feature selection approach to reduce the
2019: Zhang et al. 2019 Liao et al. 2021 Couillet al. 2021
Agrawal et al.
computational cost, while preserving the statistical guarantees of (using the original set of) RFFs. Zhang et al. 2019) proposed a low-precision approximation of RFFs to significantly reduce the storage while generalizing schemes of RFFs for arbitrary choice of the Gaussian kernel parameter. Our work improves these previous efforts by (i) considering broader family of random features kernels beyond RFFs and by (ii) proposing the TRF approach that is both sparse and quantized, while asymptotically yielding the same limiting kernel spectral structure, and thus algorithmic performances (Cortes al.))
well as full-precision RFFs. [L & Li (2021) designed quantization
Random matrix theory and neural networks. Random matrix theory (RMT), as a powerful and flexible tool to investigate the (asymptotic) behavior of large-scale systems, is recently gaining popularity in the analysis of (deep) neural networks (Martin & Mahoney 2018 2019). In this respect, Pennington & Worah (2017) derived the eigenvalue distribution of the Conjugate Kernel (CK) in a single-hicdenn-lyer random neural network model. This result then generalized to broader class of data distributions (Louart et al., 2018)) and to a multi-layer scenario (Benigni & Péché 2019) Pastur 2020). Fan & Wang (2020) went beyond the general i.i.d. assumption (on the entries of data vectors) and studied the spectral properties of the CK and neural tangent kernel for data that are approximately "pairwise orthogonal." Our work improves (Fan & Wang 2020) by studying the random features kernel for more structured GMM data, and is thus more adapted to machine learning applications such as classification. As far the study random features kernels under GMM data concerned, the closest work to ours is (Liao & Couillei 2018b) where the kernel matrix K defined in (2) is studied for GMM data, but only for few specific activation functions and Gaussian w, see Pootnote 5 below for a detailed account of the technical differences between this work and (Liao) & Couillet 2018b). Here, we provide a universal result with respect to the (much broader class of) activation functions and random w, and propose computation and storage efficient random features technique well tuned to match the performances of any commonly used random features kernels.
1.3 NOTATIONS AND ORGANIZATION OF THE ARTICLE
In this article, we denote scalars by lowercase letters, vectors by bold lowercase, and matrices by bold uppercase. We denote the transpose operator by (-) we use || to denote the Euclidean norm for vectors and spectral/operator norm for matrices. For random variable z, E[a] denotes the expectation of 2. The notation A is the Kronecker delta taking value 1 when E A and 0 otherwise. Finally. 1, and Ip are respectively the vector of all one's of dimension p and the identity matrix of dimension p X p.
The remainder of the article structured as follows. Section 2 we describe the random features model under study along with our working assumptions. We then present our main technical results in Section on the spectral characterization random features kernel matrices K and its practical consequences, in particular the design of cost-efficient ternary random features (TRFs) leading asymptotically to the same kernel as any generic random features. We provide empirical evidence in Section showing the computational and storage advantage along with competitive performance of TRFs compared to state-of-the --t-hhrttt hart random features approaches. Conclusion and perspective are placed in Section 5
SYSTEM SETTINGS
Let W E Rmxx be a random matrix having i.i.d. entries with zero mean and unit variance. The random features matrix Σ E RRmx of some data X Rox* is defined Σ & o(WX) for some nonlinear activation function a : R + R applied entry-wise on WX. We denote G the associated random features Gram matrix
1 m
G -
Σ
(XTw:) w:) a (w.x) E Rax
[
(6)
which is a sample mean of the expected kernel defined in With P & I, -1, we consider the expected and centered random features kernel matrix K defined in ( which plays fundamental
4

---

Published as a conference paper at ICLR 2022
role in various random features kernel- based learning methods such as kernel ridge regression, logistic regression, support vector machines, principal component analysis, or spectral clustering.
Let X1."." Xy RR be independent data vectors belonging to one of K distributional classes C,.... G.K..,CCK. with class C. having cardinality na- We assume that x; follows a Gaussian Mixture Model (GMM), that is, for X; Ca:
X; paa/ /P 2i
with 2, (Nppp, Ca/p) for some mean pa E R and covariance C. RPxP associated to class Ca-
In high dimensions, under "non triviality assumptions" the data vectors drawn from 7 can be shown to be neither very "close" nor very "far" from each other, irrespective of the class they belong to, see (Couillet et al. (2016). We place ourselves under such non-trivial conditions, by imposing, as in (Couillet et al. 2016 2018), the following growth rate conditions.
Assumption (Hligh-dimensional asymptotics) As n - oo, we have (i) p/n + c (0, and no/n - Ca E 1); (ii) ||el| O(1): (iii) for C = Ex= C. and C C. Cº ||Call = 0(1), tr(C.) = -(vP) and Ct) = O(p) for b (I, KKK. We denote
tr(C))/p that is assumed to converge in (0, oo).
Remark (Beyond Gaussian mixture data) While the theoretical results in this paper are derived for Gaussian mixture data in (7, under the non-trivial setting of Assumption 7 we conjecture that they can be extended much broader family of data distributions beyond the Gaussian setting, e.g., to the so-called concentrated random vector family (Seddik et al. 2020 Louart & Couiller 2018). under similar non triviality assumptions. See Section A.I in the appendix for more discussions.
To cover a large family of random features, we assume that the random projector matrix W has i.i.d. entries of zero mean, unit variance and bounded fourth-order moment, with no restriction on their particular distribution.
Assumption (On random projection matrix) The random matrix W has i.i.d. entries such that E[W,,] = 0. E[W?] and E[W]]] < Xw for some constant Xw < c0.
We consider the family of activation functions (.) satisfying the following assumption.
Assumption (On activation function) The function is at least twice differentiable (in the sense of distributions when applied to random variable having non-degenerate distribution function, Remark 3 in Section A l of the appendix), with for some constant Xo and z (0,
< X
MAIN RESULT
Our objective is to characterize the high-dimensional spectral behavior of the centered and expected random features kemel matrix K defined in (2). It turns out, somewhat surprisingly, that under the non-trivial setting of Assumption] [ one may mentally picture the high-dimensional data vectors as (i) being asymptotically pairwise orthogonal (i.e., x x, + for A j as p oo) and (ii) having asymptotically equal Euclidean norms (i.e., ||x,||2 r), independently of the underlying class they belong to. As we shall see, this high-dimensional "concentration" of x, x; - T Ö;mn plays a crucial role in "decoupling" the two dependent but asymptotically Gaussian random variables o( (TT)) xx; and a (wTx,, xy) in the definition (1p. This, up to some careful control on the higher-order (but well "concentrated") terms, leads to the following result on the asymptotic behavior of K, the proof of which is given in Section A.3 of the appendix.
Theorem (Asymptotic equivalent of K) Under Assumption for K defined in as n. + co.
K
K + 0.
"hht is, when classification is neither too hard ton casy.
5

---

Published as a conference paper at ICLR 2022
almost surely with P In /n
di (z+ M J )
( [2+M²)
K = P
+ d2 VAV + + In P,
(8)
vp
vp
and
V = [J/Dp, Φ E (Tx((k))
A
tt 2T
t
E ((*+))x(KH))
t.
where, for 2 ~ No,,
do F[o²(VF=)] (v=)) -ll(o'(V di =1= d2 4 Flo"
and "first-order" random matrix Z = (21, /nl E RPx as defined in 7 "second-order" random (fluctuation) vector Φ- {||z:|? -E[|z; j=1 E R", and GMM data statistics
M = M= _K] E R K t= tr( (r(C.))
ER" T Cr
K
E Rx (9)
P
a.b=l
as well as the class label vectors J lir... jkl E Raxk with [io]: 8x.EC..
First note that the "asymptotic equivalence" established in Theorem Toold for the expected kernel K, not on the empirical random feature kernel G defined in (6) and is thus independent of the number of random features m. On closer inspection of Theorem I we see that the data statisties for classification, i.e., the means (M) and covariances (tt _ T) are respectively weighted by the generalized Gaussian moments of first (d1) and second order (dz), while the coefficient du merely acts as a regularization term to shift all the eigenvalues and has thus asymptotically no impact on the performance of, e.g., kernel spectral clustering for which only eigenvector structures are exploited
Theorem Juveils surprising universal behavior of the expected kernel K in the large n. p regime. Specifically, the expression of K (and thus the spectral behavior of K, see our discussion in the paragraph that follows) is universal with respect to the distribution of W and the activation function when they are "normalized" to satisfy Assumptions 2 and This technically improves previous efforts such as (Liao & Couillet 2018b and allows us to design computationally more efficient random features approach by wisely choosing W and a.
As a direct consequence of Theorem I one has, by Weyl's inequality and Davis-Kahan theorem that (i) the difference between each corresponding pair of eigenvalues and (ii) the distance between the "isolated" eigenvectors the "angle" between the "isolated subspaces" of K and K vanish asymptotically as n, + oc. This is numerically confirmed in Figure 2 where one observes a close match between the spectra (eigenvalue "bulk" and isolated eigenvalue-eigennector pairs) of K and those of its asymptotic equivalent K given in Theorem 1 already for n, only in hundreds. In particular, we compare, in Figure 2 the eigenspectra of K and K for Gaussian versus Student-t distributed W, on GMM data. A close match of the spectra and the isolated eigen-pairs is observed, irrespective of the distribution of W, as predicted by our theory.
In the following corollary, we exploit the universal result in Theorem | to design computationally efficient Ternary Random Features (TRFs) by specifying the distribution of (the entries of) W to symmetric Bernoulli and a to ternary function, so as to obtain a limiting kernel K ter that is asymptotically equivalent to any random features kernel matrix K of the form (2). for the high- dimensional GMM data under study. This is proved in Section A.4 the appendix.
"This can be seen another manifestation of the implicit regularization in high-dimensional kernel and random features (Jacot al. 2020 Derezinski al. 2020 Liu al, (2021b).
*We provide in Table I [Section the appendix) the corresponding Gaussian moments da, d1, da for various commonly used activation functions in random features and neural network contexts.
From a technical perspective, Theorem iimproves (Liao & Couillet 20188 Theorem 1) the fact that the latter relies on the explicir forms of the expectation K in (2) and is thus limited to (i) a few nonlinear o for which K can be computed explicitly, see (Liao & Couillei 2018b] Table 1): and (ii) Gaussian distributed W in which case the p-dimensional integral can be easily reduced to two-dimensional one. Here, Theorem T holds for much broader family of random W and nonlinear a as long as Assumptions and hoold.

---

Published as a conference paper at ICLR 2022
Eigenvaluues
Figenvalues of K
5
10
10
5
0
200
400
600
800
1,000
200
400
600
800
1,000
Figure 2: Eigenvalue distribution (TOP) and cigenvector associated to the largest eigenvalue (BOTTOM) of the expected and centered kernel matrix K (blue) versus its asymptotic equiva- lent K (red) in Theorem 1 with (t) max(t, 0). (LEFT) W having Gaussian entries and (RIGHT) W having Student-t entries with 7 degrees of freedom, for two-class GMM data with fa 0a-1; 4; Op-a]; C. (1 4(a 1)/ /p)pppLL p, p 512 and 2048.
Corollary (Ternary Random Features) For a given random features kernel matrix of the form 2 with W and nonlinear satisfying Assumptions 3 with associated generalized Gaussian
moments do, d1, d2 defined in Theorem let ter be defined in (5) with s_ = =__ S+ = 84, and s_, 8+ satisfying the following equations
1 (- d1 -
2TT3 (84e Rt/7 & =2/))
1
d2
(10)
Define the Ternary Random Features matrix Dter geer (Wte with W defined in (4) having sparsity level e, the associated Gram matrix G Gerr = 1 (Eter) yter as in (6), and the limiting kernel
Kttrr P (xete (x Xj) 1
(11)
for her defined in 3 Then, there exists À E R such that 6 KK - Kier XPP| + 0 almost surely as n + cc.
Note that the system of equations in 10 defining 8_ and 8 is function of the key parameter
T = trC² /p defined in Assumption
which can be consistently estimated from the data; see Algorithm [below and proof in Lemma of the appendix (the intuition of which follows from the fact that ||x, 1 ||
11//p /pp 2 / + |22.12 E[tr(z,z,)) }] (1/2) according to 7 and Assumption D. This makes the proposed TRFs and its limiting kernel Keer data-statistics-deeeedde Yet, the system of equations (IO) does not have a closed-form solution and might have multiple solutions on the real line; we practically solve it using numerical least squares method, by gradually enlarging the search range (from say [-1, 1)) until a solution is found (the time complexity of which is independent of the dimension n. p and it is observed in the experiments in Section 4 to converge in a few iterations). The details of the proposed TRF approach are described in Algorithm
Algorithm 1 Ternary Random Features
Input: Data X and level of sparsity E 1).
Output: Ternary Random Features yter and Gram matrix Ger Estimate 7 as 1 Σ ||x
Solve for thresholds &_, $ using 10). which defines fer via (5).
Construct random matrix Wter Rmxp having i..dd entries distributed according to 4
Compute yter = ter (Wter X) and then TRFs Gram matrix Gter 1 ter
I T as in 6
'The parameter À characterizes the possihly different hetween K and Ker details Appendix A.4
7

---

Published as a conference paper at ICLR 2022
Computational and storage complexity For W E Rmxp a random matrix with i.d.. (O 1)
entries and Wier E RmxP with i.i.d. entries satisfying with sparsity level c E [0, 1), let G
m (WX) (WWX)"o(WWW (WX) for some given smooth function o (c.g., sine and cosine in the case of random
Fourier features) and G of (Wler (Wteer) ofer (W X) with data matrix X RRxx. it then beneficial to use G instead of G as the computation of a (WX) requires ((mp)) multiplications and ((mp)) additions, while the computation of of (W X) requires no multiplication and only O((1 - e)mpp) additions. In terms of storage, it requires factor of 32 times more bits to store a (WX) when computing G compared to storing of (ee((e))X) when computing Ge (assuming full precision numbers are stored using b = 32 bits).
m
The computationally and storage efficient TRFs g (W )X can then be used instead of the "expensive" random features a (WX) and lead (asymptotically)) to the same performance as the latter on downstream tasks, at least for GMM data, according to Theorem [T] In the following section, we provide empirical results showing that (i) this "performance match" between TRFs and random features of the form ( is not limited to Gaussian data and empirically holds when applied popular real-world datasets such as MNIST (LeCun et al.) 1998), some UCI MI. datasets, as well as DNN- features of CIFAR10 10 data in Section (ectionAA.6oof the appendix; and (ii) due the competitive performance of TRFs with respect to standard random features approaches, when compared to state-of- ofte--of-the-ar random feature compresiionquuanizatiin techniques (for which "performance-compleiii" generally arises, that is, as one compresses more the original random features, the performance decays), TRFs yield significantly better performances for given storage/computationall budget.
tradcoff"
EXPERIMENTS
The experiments in this section and Section A.6 of the appendix are performed on a Ubuntu 18.04 machine with (Rt)l(R) Core(TM) i9-9900X CPU 3.50GHz and 64 GB of RAM.
4.1 TRFS MATCHI THE PERFORMANCE OF POPULAR KERNELS WITH LESS BUDGET
We first consider ridge regression with random features Gram matrix G on MNIST data in Figure We compare RFFs with (())= = [cos((), sin(() and Gaussian Way ~> NO 1) to the proposed TRF method with ter (L) in (5) and ternary random projection matrix Wier defined in (4). with different sparsity levels e. The thresholds s_, s_ of geer are tuned in such away that the generalized Gaussian moments d1 and de match with those of RFFs as described in Corollary | and Algorithm Figure displays the test mean squared errors as function of the regularization parameter for our TRF method with different sparsity levels c compared to the RFF method, as well as to the baseline of Kernel Ridge Regression (KRR) using Gaussian kernel. Note that despite 90% sparsity in the projection matrix W, virtually no performance loss is incurred compared with RFFs. This is further confirmed in the right hand side of Figure 3 which shows the gains in running e using TRFs. These experiments show that the proposed TRF approach yields similar performance as popular random features such as RFFs, with significant reduction in terms of computation and storage.
I
4.2 COMPUTATIONAL AND STORAGE GAINS- COMPARISONS TO STATE- OHE
In this section, we compare TRFs with state-of-the-art quantized or non-quantized random features methods, for both random features-based logistic and ridge regressions. Specifically, in Figure 1 we compare logistic regression performance of TRFs versus the Low Precision Random Fourier Features (LP-RFFs) proposed by Zhang et al.] (2019), on the Cov-Type dataset from UCI ML repo As in Section 4.1, the TRFs are tuned to match the limiting Gaussian kernel of RFFs. For a single datum x E RD, the associated TRFs fer (Wierx) x) E RTM use m bits for storage while L.PRFFss use 8m bits. We follow the same protocol as in (Zhang et al., 2019) and use SGD with mini-batch size 250 in training logistic regressor and {1,8} bits precision for the LP-RFF approach. Figure] ! compares the
FFor given x;, Xj, we use (Wx:), sin(Wx; )] as the random Fourier features so that the (i. j) entry of the corresponding random features Gram matrix cos( Wx,) cos( Wx,) +in (W.)) T sin (ix)))) (Rahimi & Recht 2008). The generalized Gaussian moments of the RFFs are thus the sum of the di 's and d2 's corresponding
to sin and cos functions. Note that the do of RFFs and TRFs may be different.
'The running time is taken as the total clock-time of the whole ridge regression solver including the random features calculation.
8

---

Published as a conference paper at ICLR 2022
Baseline (KRR)
Baseline (KRR)
0.8
RFF
2,000
RFF
0.1 (TRF)
Running time (S)
TRF
0.6
0.5 (TRF)
MSRS
0.9 (TRF)
0.4
1,000
0.2
10-2
10
10a 10
0.1
0.3 0.5 0.7
0.9
Figure 3: Testing mean squared emrors (MSEs with #1 std, LEFT) and running time (RIGHT) of random features ridge regression
function of regularization parameter 7: p 512, 1024, Detsst = 512, m = 5.10". With W distributed according to (4) and c = [0.1, 0.5, 0.9], versus RFFs and KRR do = 0.39 for RFFs, making À in Corollary [ small. Results averaged over 5 independent runs.
2-class MNIST dataset digits (7, 9). We find that do 0.44 for TRFs and
logistic regression test accuracy function of the total memory budget for LP-RFF (1 bit and 8 bits) and the Nyström approximation of Gaussian kernel matrices (using 32 and 16 bits) (Williams) Seeger 2001) (see also Table in (Zhang al. 2019)), versus the proposed TRFs approach. As seen from the shift in the x-axis (memory). by using 8x less memory than L.PRFFss and 32x or 16x less memory than the Nyström method, TRFs achieve superior generalization performance on the logistic regression task. Similar comparisons are performed in Figure 4 on random features ridge regression task for the Census dataset (Rahimi Recht, 2008), confirming that TRFs outperform alternative approaches in terms of test mean square errors, with significant save in memory.
0.15
LP-RFF (1 bit)
LP-RFF (8 bit)
Nyström (32 bits)
MSEs
0.1
Nyström (16 bits)
Proposed TRF
0.05
10a
10
107
10a
Memory (hits)
Figure 4: Test mean square errors of ridge regression quantized random features for different
number of features m & (5. 10 5.10 103,5.10* 10t, 5.10"), using LP-RFF (Zhang et al. 2019). Nyström approximation (Williams & Seeger (001). versus the proposed TRF approach, the Census dataset, with n = 16 000 training samples, Thest 2 000 test samples, and data dimension 119.
5
CONCLUSION
Our large dimensional spectral analysis of the random features kernel matrix K reveals that its spectral properties only depend on the nonlinear activation through the corresponding generalized Gaussian moments and are universal with respect to zero-mean and unit-variance random projection vectors. This allows us to design the new TRF approach which turns both the random weights W and the activations a oWWX X) into ternary integers, thereby allowing to only perform addition operations and to only store bit for the activations. This drastically saves the storage and computation of random features while preserving the performances on downstream tasks with respect to their counterpart expensive kernels. Our article comes along with (Couillet et al. 2021) as first steps in re-designing machine learning algorithms using Random Matrix Theory, in order to be able to perform computations on massive data using desktop computers instead of relying on energy consuming giant servers.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
Z L would like to acknowledge the National Natural Science Foundation of China (NSFC-12141107)) the Fundamental Research Funds for the Central Universities of China (202IXXIS110), and CCF- Hikvision Open Fund (202 10008) for providing partial support. R C would like to acknowledge the MIAI LargeDATA chair SANR-19-P3IA-A project, as well as the ANR DARLING project for providing partial support of this work.
at University Grenobles-Alpes the HUAWEI LarDist
REFERENCES
Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. nigh-dimensiooal dynamics of generalization enror in neural networks. Neural Networks, 132:428-444 446, 2020. ISSN 0893-6080. doi: n0.1016/..euumet22000.0 20euuett.2220006 08.02..
Raj Agrawal, Trevor Campbell, Jonathan Huggins, and Tamara Broderick. Data-dependent com- pression of random features for large-scale kernel approximation. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 18822-131.. PMLR, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint /rXiv:/811.000 1,49/8, 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Zhidong Bai and Jack W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices, volume 20 of Springer Series in Statisties. Springer-Verte New York, 2 edition, 2010. ISBN 9781441906601. doi: 10.1007/978-1-44111 1-1199968--444--611-5--5
Lucas Benigni and Sandrine Péché. Eigenvalue distribution of nonlinear models of random matrices. arXiv preprint arXiv:1904.088:
2019.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. arXiv preprint 1.X.::1905.1277.. 2019,
Patrick Billingsley. Probability and Measure. Wiley Series in Probability and Statistics. John Wiley Sons, Ltd, 3 edition, 2012. ISBN 9781118122372. /ttptt
www.ww.wwww//eee....o us/
9781118122372
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 380-388, 2002.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming. In Advances in Neural Information Processing Systems, volume 32 of NIPS' pp. 2937-2947. Cur- ran Associates, Inc., 2019. URL
meurips ips cc//paper/2019/
pdf
Youngmin Cho. Kernel methods for deep learning. University of California, San Diego, 2012.
Corinna Cortes, Mehryar Mohri, and Ameet Talwalkar. On the Impact of Kernel Approximation on Learning Accuracy. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 113-120, Chia Laguna Resort, Sardinia, Italy. PMLR. URL https:: htttps://proceeddrntt mlr press/ v9/cortes .t..tmmllll.....m
Couillet, Cinar Romain, Gaussier Y., and Imran M. E. Word representations concentrate and this is good news! In Proceedings of the 24th Conference on Computational Natural Language Learning, pp. 325-334, 2020, November.
Romain Couillet, Florent Benaych- Benaych-Georges, Georges, et al. Kernel spectral clustering of large dimensional data. Electronic Journal of Statistics, (0(1):1333-1454 2016.
10

---

Published as a conference paper at ICLR 2022
Romain Couillet, Zhenyu Liao, and Xiaoyi Mai. Classification asymptotics in the random matrix regime. In 2018 26th European Signal Processing Conference (aaerrennee(EESSEEie (EUSIPCO), pp. 1875-1879. IEEE, 2018.
Romain Couillet, Florent Chatelain, and Nicolas Le Bihan. Two-way kemnll matrix puncturing: towards resource-efficient pea and spectral clustering. arXiv preprint arXiv:2102.12293. 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp. 248-255. Ieee, 2009.
Michal Derezinski, Feynman T Liang, and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. In Advances in Neural Information Processing Systems, volume 33, pp. 5152 5164. Curran Asso- ciates, Inc., 2020. URL 777T005555ee21144337222226222223
hewpriiiinnnnn.ui.ia..ee wws.scc/paee cc.papprr/222/FElee
pdf
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning, pp. 1675-1685. PMLR, 2019.
Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural tangent kernel for linear- width neural networks. arXiv preprint arXiv:2005. 1879, 2020.
Friedrich Gerard Friedlander, G Friedlander, Mark Suresh Joshi, M Joshi, and Mohan C Joshi. Introduction the Theory of Distributions. Cambridge University Press, 1998.
Michel Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev. Compressing deep convolutional networks using vector quantization, arXiv preprint arXiv: 14/2.6115, 2014.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International conference on machine learning, pp- 1737-1746. PMLR, 2015.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprini
2015a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both Weights and Connections for Efficient Neural Network. In Advances in Neural Information Processing Systems, volume 28 of NIPS' 15. Curran Associates, Inc., 2015b. URL
www.inngg...eeuree neuries cc/ pdf
Itay Hubara, Matthiu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized Neural Networks. In Advances in Neural Information Processing Systems, volume 29 of NIPS 16, pp. 4107-4115. Curran Associates, Inc., 2016. URL http://///pppceeeeingg..s. neurips cc /ttp:://0000/1111/333333555.2..2 wcwaa7755330
pdf
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.07572. 2018.
Arthur Jacot, Berfin Simsek, Francesco Spadaro. Clement Hongler, and Franck Gabriel. Implicit regularization of random feature models. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4631 4640. URL https: settpa://proceeddinng .mlrssss..rr........ mlr. wwtpss/wwee/aaaeeeptpppp
PMLR, 13-18 Jul 2020.
html

---

Published as a conference paper at ICLR 2022
Kruskal Joseph and Wish Myron. doi: 10.4135/97811112981130
Multidimensional Scaling. 1978. ISBN 9780803909403. URL [attps://methods sagepub. com/ book/
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Pei Ling Lai and Colin Fyfe. Kernel and nonlinear canonical correlation analysis. International Journal of Neural Systems, 10(05):365-377, 2000.
Yann LeCun, Leon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-25 2324,, 1998. ISSN 0018-9219. doi: 10.1109/5.72679.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv:1711.000 2017.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint (txXix:/902.06777 2019.
Ping Li and Martin Slawski. Simple strategies for recovering inner products from coarsely quantized random projections. Advances in Neural Information Processing Systems, 30:4567-4577, 2017.
Xiaoyun Li and Ping Li. Random projections with asymmetric quantization. Advances in Neural Information Processing Systems, 32: 10858-10867, 2019.
Xiaoyun Li and Ping Li. Quantization algorithms for random fourier features. arXiv preprint arXiv:2102. 13079, 2021.
Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis of random fourier features. Journal of Machine Learning Research, 22(108):1-51, 2021. URL http:
1369. html
Zhenyu Liao and Romain Couillet. The dynamics of learning: random matrix approach. In International Conference Machine Learning, pp. 3072-3081. PMLR, 2018a.
Zhenyu Liao and Romain Couillet. On the spectrum of random features maps of high dimensional data. In International Conference on Machine Learning, pp. 3063-3071. PMLR, 2018b.
Zhenyu Liao and Romain Couillet. Inner-product Kernels are Asymptotically Equivalent Binary Discrete Kemels. arXiv, 2019.
Zhenyu Liao, Romain Couillet, and Michael W Mahoney. A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double
descent. 13:13939-13988 13950. 2020. URL httpps:/prroceddinn www.:eedddiiinnn.iis..eoeeeoee.. www.nne...... wwweriis.ccppappeee wwtppppp//pppppcppptpettcce..eet
22000FF1eea003fa3333 1664 -Papee pdd
Zhenyu Liao, Romain Couillet, and Michael W. Mahoney, Sparse quantized spectral clustering. In International Conference on Learning Representations, 2021. URL /tttpss://ppeereeiiiie
net www.::iindddggsnnneeee....
Zhouhan Lin, Matthieu Courbariaux, Roland Memisevic, and Yoshua Bengio. Neural networks with few multiplications. arXiv preprint arXiv:1510.03009 2015.
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. Sparse convolu- tional neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 806-814, 2015.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A. K. Suykens. Random Features for Kernll Approximation: A Survey Algorithms, Theory, and Beyond. IEEE Transactions Pattern Analysis and Machine Intelligence, PP(99):1-1, 202 ISSN 0162-8828. doi: 10.1 109/tpami.
1021.309701..
12

---

Published as a conference paper at ICLR 2022
Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined
analysis beyond double descent. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistiic,, volume 130 of Proceedings of Machine Learning Research, pp. 649-657, PMLR, 13-15 Apr 2021b. URL https: fttt:s://prrceeeirgge ml wtt..reeess/vv///o1peo.. html
Cosme Louart and Romain Couillet. Concentration of measure and large random matrices with an application to sample covariance matrices. arXiv preprint arXiv: 0825,, 2018.
Cosme Louart, Zhenyu Liao, Romain Couillet, al. A random matrix approach neural networks. The Annals of Applied Probability, 28(2): 12499, 2018.
Yueming Lyu. Spherical structured feature maps for kernel approximation. In International Confer- ence on Machine Learning, pp. 2256-2264. PMLR, 2017.
Charles H Martin and Michael Mahoney. Implicit reffraegulrizattinn in deep neural networks: Ev- idence from random matrix theory and implications for learning. arXiv preprint arXiv: arXiv:1810.01075. 2018.
Charles H Martin and Michael W Mahoney. Traditional and heavy-tailed self regularization in neural network models. arXiv preprint 1xXiv:901100276 2019.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint 1.Xiv:8804.1222 2018.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprini arXiv: (w..//988005555 2019.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang. Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. arXiv preprint arXiv:1810.05149 2018.
Lconid Pastur. On random matrices arising in deep neural networks. gaussian case. arXiv preprint arXiv:2001.06188, 2020.
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. 2017.
Danil Prokhorov. Ijenn 2001 neural network competition. 2001.
Haotong Qin, Ruihao Gong, Xianglong Liu, Xiao Bai, Jingkuan Song, and Nicu Sebe. Binary neural networks: A survey, Pattern Recognition, 105:107281, 2020.
Ali Rahimi and Benjamin Recht. Random Features for Large-Scale Kernll Machines. In Advances in Neural Information Processing Systems, volume 20 of NIPS 08, pp. 1177-1184, Curran As- sociates, Inc., 2008, URL http:tss///rrccediiggggg.g. neurips cc/ http:/papp////0////LL... 013a006f03dbcct
pdf
Bernhard Schlkopf, Alexander Smola, and Klaus-Robert Miler. Nonlinear Component Analysis as Kernel Eigenvalue Problem. Neural Computation, 1095);1299-1319, 1998. ISSN 0899-7667. doi: 10.1 10.1166//899976993000777777
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Kernel principal component analysis. In International conference on artificial neural networks, pp. 583-588, Springer, 1997.
Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 2018. ISBN 9780262256933. doi: 10.755 htt5///mmipeee//1/55555 .0000...00......
Mohamed El Amine Seddik, Mohamed Tamaazousti, and Romain Couillet. A kernel random matrix- based approach for sparse pca. In International Conference on Learning Representations (ICLR), 2019.
13

---

Published as a conference paper at ICLR 2022
Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures. In International Conference on Machine Learning, pp. 8573-8582 PMLR, 2020.
Elias M Stein and Rami Shakarchi. Functional Analysis, Introduction to Further Topics in Analysis. 2012. doi: 10.1515/978 01115159784440845557-0000 400840557-005..
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416. 2007.
Vladimir Vovk. Kernel ridge regression. In Empirical inference, pp. 105-116. Springer, 2013.
Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. In Proceedings of the 14th annual conference on neural information processing systems, number CONE, pp. 682-688, 2001.
Christopher KI Williams, Computing with infinite networks. Advances in neural information processing systems, pp. 395-301, 1997.
Felix Xinnan X Yu, Ananda Theertha Suresh, Krzysztof M Choromanski, Daniel N Holtmann-Rice and Sanjiv Kumar. Orthogonal random features. Advances in neural information processing systems, 29: 29:1975-1983 2016.
Jian Zhang, Avner May, Tri Dao, and Christopher Ré. Low sow-precision random fourier features for memory-constrained kernel approximation. In The 22nd International Conference Artificial Intelligence and Statisties, pp. 1264-1274. PMLR, 2019.
Chenzhuo Zhu, Song Han, Huizi Mao, and William Dally. Trained ternary quantization. arXiv preprint arXiv:16/2.01066 2016.
A APPENDIX
We provide detailed discussions on our working assumptions in Section A. consistent estimator of the key parameter in Section A.2 the proof of Theorem D in Section A.3 and that of Corollary i Section A.4 as well as the generalized Gaussian moments for standard kernels arising from random features and neural net contexts in Section A.5 Additional numerical experiments placed in Section A.6
A.1 NOTES ON THE WORKING ASSUMPTIONS
For completeness, let us restate the working settings of the paper.
Let XI,'.., Xn E IR be n independent vectors belonging to of K distributional classes Cr,..., ,C,. Class a has cardinality Ra, and we assume that x; follows a Gaussian Mixture Model (GMM), i.e., for x4 Ca.
X; Ma/ / 2,
(12)
RPxx associated to class C.. We position ourselves in the non-trivial regime of high-dimensional classification described by the following growth rate conditions.
with z, NoO,,, C./p) for some mean pa E Rp and covariance C.
Assumption 4 ddiig-adimensionll asymptoties) As - co, we have (i) p/n c (0, oc) and n./n + Ca (0, 1): (ii) ||mا|| O()): (il)) for C EK ||Cal = 0(1), tr(C.) = O(vp) and C,. = O(p) for a, b E [l, K}. We denote
Ra C, and C² C.. O then
n
A tr(C))/p that is assumed converge in (0, co).
14

---

Published as a conference paper at ICLR 2022
Beyond Gaussian mixtures While the theoretical results in this paper are derived for Gaussian mixture data under the non-triviall setting, we conjecture that they can be extended to much broader family of data distributions beyond the Gaussian setting, e.g., the so-called concentrated random vector family (Seddik et al. 2020), under similar non triviality assumptions.
Definition (Concentrated vector) Given normed vector space 1-)..1). and 0, random vector x E X' is said to be q-exponentially concentrated if for any --Lipschittfunction function & X + R, there exists C > -0 independent of dim( (2) and a > O such that for all 2 0,
P (lo(x) E(((())) 1) S Ce-WoY.
Multivariate Gaussian distributed x ~ I)) can be checked to belong to the family of con- centrated random vectors. The major advantage of using concentrated random vectors for data modeling is that this concentration property is stable under Lipschitz transformation, that is, for any 1-Lipschitz map f: RP + RR9 x R is concentrated, so x' f(x). Among the broad family of concentrated random vectors, it has been particularly shown in (Seddik et al., (020)) that artificial images generated by Generative Adversarial Network (GAN) (Seddik et al. 2020), which look extremely close to real-world images (as they designed to), Lipshitz transformations of Gaussian vectors and can thus be, by definition, concentrated random vectors.
As result, concentrated random vectors more appropriate (than GMM for instance) in modeling realistic data, at least for those "close" to data generated by GANs.
The same shown experimentally for CNN representations of real images (Seddik al. 2019 2020) as well as words embeddings in Natural Language Processing (Couillet et al. 2020, November).
As for the random projector matrix, assume that the matrix W has ii.d. entries of zero mean, unit variance and bounded fourth-order moment, with no restriction on their particular distribution as follows.
Assumption (On random projection matrix) The random matrix W has i.i.d. entries such that E[W.g] = 0, E[W3] = 1 and F[W?)] < >w for some constant dw < CO.
Remark (On the i.i.d. assumption of entries W) Assumption we consider the setting where the entries of W are independently and identically distributed: this is the case for the popular vanilla random Fourier features in (Rahimi Recht 2008) and the arc-cosine kernels in neural network context; but not the case for, e.g., data dependent random features approaches such as leverage score based methods (Li et al. 2027).
We consider the family of activation functions o()) satisfying the following assumption.
Assumption (On activation function) The function least twice differentiable (in the sense of distributions when applied to random variable having a non-degenerate distribution func- tion), with
Elo? El)), (z)1} < Xa for some constant >a < 000 and
~ 1).
Remark (Activation functions not differentiable everywhere) Some popular activation func- tions used in machine learning such as ReLu, Sign, Absolute value, etc., are not differentiable everywhere. For those functions, we will use a derivative in the sense of distributions (Friedlander et al. 1998). A distribution is continuous linear functional on the set D of infinitely differentiable functions with bounded support
9: D R
a- 6 g( g(0)=
(()) dr.
The distributional derivative g0) is defined such that g' (() -g(d"). In particular, we will be interested here in the expectation of the derivatives of the activation function with respect to the Gaussian measure i.e., 1t of d'xx)e==* =² dx. Following the previous definition, have in this purticular case
toc
o'(x) x²/2 dr
(x)e x² x²/2 dx
15

---

Published as a conference paper at ICLR 2022
which can be evaluated by some integration by parts. This is also refereed the "weak derivative" in the functional analysis literature (Stein & Shakarchi 2012).
A.2 AUXILIARY RESULTS AND PROOFS
Lemma (Consistent estimation of r) Let Assumption 4 hold and define т 2 trC /p. Then as
+ with probubility 1,
1
| 2
O.
11
Proof (Proof of Lemma]
From equation
we have that
K
2
12 x
Ma 11
14
2
+
|2 |
(13)
vp
From Assumption 4 we have that 1 2 g 21 is weighted sum of independent zero mean random variables; thus vanishes with probability as n,p - do by a mere application of Chebyshev's inequality and the Borell Cantelli lemma. Finally, using the strong law of large numbers the last term of equation 73 we have almost surely,
Opp-1) The second term of equation
13
K
Th trC. + o(1)
a=1
K
1 trC
+
a
p
a=1
where the last line we use trC. = ((v)) from Assumption and thus 1 E. 12:12--5 + almost surely. This concludes the proof.
A.3 PROOF OF THEOREM 1
In the sequel, we will make use of Bachmann-Landau notations but specific for random variables in the asymptotic regime where > 00. For x In random variable and un 2 0, we write In = (u,,) if for any 7) and D > 0, nn 2 u²u,,) + 0 as - oc. For a vector v or a diagonal matrix with random entries, = Ouu,) means that the maximal entry of in absolute value (u,) in the sense defined above. When M is square matrix, M (u,,) means that the operator norm of M is (u,)). ). For æ a random variable, I = o(ux) means that there exists k > 0 such that Onn ). And the same definition for the o(-) notation applies for vectors and matrices having random entries.
Let us define X x= [x1,,..
[ [x,] R and define
Σ (WX)
where W W1. wml Rm with W satisfying Assumption 5 and a function satisfying Assumption We consider the gram matrix
G G= GILEVD E m
whose (i.j) entry is given by
Gij
a (w [(w[x)oow(xx)
k=1
We are interested in computing
<({;, Folo (wwwTxx)oxTx))
(14)
16

---

Published as a conference paper at ICLR 2022
under Assumptions 4
Under Assumption we have
x; x,
z. z
//-//+++//-// mb w:/ vp
(15)
O(p 7)
0G1-1)
and
|x:|12
+ tr( (r((C))/ + t; + 1/lllp + 2p1 24/ /.P
(16)
O(1) Olp +
O(p-2)
where di A -| (12))
can be checked that, for random vector w E IR having i.i.d. entries with E [[mag] = and E(w = 1, we have, conditioned on X,, that E [w[(w" x, )1 = [xx and
Ew((wT x = (m4 - 3) x 2||x.||**
(17)
with my [ Aw according to Assumption From the trace lemma, (Bai & Silverstein 2010 Lemma B.26), one has that
x x: -trC 0
(18)
p
almost surely as p + oo, for X; E C.. Thus, under Assumption we have in particular x! x, trC /p - 0 holds almost surely, regardless of the class of x,, see the proof of Lemma then follows from Lyapunov CLT (see, e.g., (Billingsley) 2012] Theorem 27.3)) that, under As- sumption and 5 (wTx, x;, w'x,) asymptotically bivariate Gaussian. We can thus perform, in the large limit, a Gram-Schmidt orthogonalization procedure for some standard Gaussian variables &a, E (0, 1). By construction, Ea. & are uncorrelated and thus independent by Gaussianity. Let us denote the shortcuts La w x; and Co = w w'x..
X5. We thus have
Sa = w T x; = uaCa + o(1)
w x, vbta 4bE2 + o(1)
with
Ua ||*|||
x_ Xj 26 ||x|||
(xxxx,)
||x,1|2
||x,
Since we have that ||x:|| /F + (1) and ||x;|| = VF () (from equation 16) we can perform a Taylor expansion of ((.)) (respectively of (G.)) around VTCa (resp. VTEw) giving
((sa) = ((VT(v((T))))))) +
VTEa) J " (Sa) VFEa)² + o((Sa VTEa)²)
o(G6) = [(VTEL) + o' - VT&L) + 2 " - VFEo)² + o(5o ))
We then have
<(xi, x,) = ((o(GN)((GG))
=[(o(VTE))O(VEE)) ElO(TTE)' (VTEE/) VTE6Il
2 " - V
+
+ (V VTC.)O + E(O' VTEa)o - Vv66]
[lo'EE)) - VFEA)O" - VF&6) clo - VFE.)
+
2
1
(V"(WVE)) (VFFE) VFEu)
2
1
+ 4
[(FF(VF - (VF - VFEN)& + +o((a VF
17

---

Published as a conference paper at ICLR 2022
where the expectation is with respect to as in the definition in 14 Using the independence between Ea: çb along with the following
Ua 1)
Ca VT
(19)
VT
S6 VTb =
VT
ub
1)V
VF
TTa
(20)
we have for & ~~ (00 1),
E(o(VTE.)o(VFE)) (F(o(VTE)))
(21)
Ll VFEo]] = (LOOWWFE)ELLFFE (V=
-11
+ (F VT
Ubb
(22)
Similarly writing down the products (Sa - VTE2)² ,,, (Sb
(So -
(C
(FEE)(G V=&))² (C.
( v (Sa VT ) " ) as in Equations 21 22
and using Equations 19 20
we obtain a complete expression of all the terms ((x,, X,) as follows
x,) = (LEOO(VFE))* + (EO (
ub 1) + (EL 8b
VF
(ELVTEO (1=
-1)
Uu
1)(
1)(
46 VF 11) +
(IE (mn- - 1)²)
2
(FEE
Ua
ub
2 (LLTEO'(VEEE)ETT (VFEI)
2
Ua
Wb
VF
VF
(E[TERO" (VTE)(?
Uaa -1) 1
+ (EIVFRO((FEEEVVVTTO
Ub
21
4
VT
VT
VT
(VE)
FE))
Ub
+ ([TOLVVEEDELVVESSOVVVE)) (0=1)
2
Pb (E(
Ua
1)
(7E (VTE)))
Ub
Ua
VT
VT
VF
VT
/ 1) + [IT (VFE))
Uaa
Uu
2
(VEO((/ V 0" (VTE)))
2bb
U 1
2
(VE) d" (VTE))
Un 1 2
Ub
4
(EVT o" (VTE)))
8b
Whb
1 1
( ( -1 -1)
Opp #).
(23)
18

---

Published as a conference paper at ICLR 2022
Since xx. x1 S for sufficiently small e, (following from equation 15 using Taylor approxima-
tion of ||x,|2
[x] x,
we obtain
|x
ub
1=
|x2,12
(x]xx)''
1=
| |l
-1)
1
(x xx]
+o
(xxTx;)
vF
|x511
VT
2 |
||<;| 1|
||x,12
VF
Ub
1
1
||x;|12
||x;
(x, x,y )2
X3 112
1
2
||>||| ||
VT
-1)
2
vv
x,1|
|x|||
1
[x] x )2
|| |
+
(x,xx,) )2
|xx|| 2
|x||
1 =
- 1.
V
VT
We thus have
Ub
x/xx
2 2j +
1 w
1b w; vD
+ O(p :)
VT
VF|1x;||
7
vD
O b)
O(p-1)
Uh 1
xx
1
/ tr( (C))
Di
+ 2T
1
| ||
241 T
+0(p-3)
T
V
2r
p
p
/p)
Olp 2)
O1p-1)
Ua -1) 1) (w=== -1) =
||x|||
-1)
(
||x,]|
- -1)
(r(C.)
+
Di)
[r(C;)
+ +4,)
+0(p-) B)
V
VF
V=
472
2
Ub
-
1
+(p
(24)
VF
All other terms in equation 23 are of order at most Opp-2) and thus vanish asymptotically. We thus get
<(x,,,)) = [(LIO(VTEN) + (EO(VEE))LL/FR ( Uh -
(-=
1bb
VF
+ (EIVFEO(VFFE)))) (1/
-11 11)
1)(
+ (Elo" (F
2b VT
2
VT
2
+ (ELO(WEE))ELLLEEOO (0i
Uu - 1 + O +)
(25)
Plugging the terms in equation 24 into equation 25 and rearranging in matrix form, we obtain for K ((((x,, 1,, 1 P and K defined in Theorem that | - K|| + O, as expected, where we
used the fact that A < 12/ ||oo for A E Ruux and TA m= |Ail.. This concludes the
proof of Theorem
A.4 PROOF OF COROLLARY II
Define the Ternary Random Features matrix teer_ = ter - (WteerWrrggg X) with Wter defined in having sparsity level e, the associated Gram matrix Gter 1 (Xter) Dter as in 6), and the limiting kernel
m
ker P (x x3) X P
(26)
19

---

Published as a conference paper at ICLR 2022
for xter defined in 3). After calculation similar to (Liao & Couillet 2019 2021.
Section 4) and
(Lia et al.
we obtain
a
2
El(oler) (VT2)}²=
ee
2
2
El(oter)) (VT2)}² 846
+ 8_
(27)
TV 2
Thus, according to Theorem for random features kernel matrix K of the form 2 with W and nonlinear satisfying Assumption 13 with associated generalized Gaussian moments do, d1, d2 defined in Theorem | by choosing s-, and s such that dj and d2 are respectively equal to the first and second term of equation 27 have that
K Ktar - XPII +
almost surely with
A = do
- (VT2)]² - rE((("err] (VT2))?)
where
El El(otor)² (VTz)] E((oter) (Vrz))² =E((oter)) (vFz))²
-1- erf
1
+
VF)
2
π
20

---

Published as a conference paper at ICLR 2022
A.5 GAUSSIAN MOMENTS OF POPULAR ACTIVATION FUNCTIONS
We provide in Table 1 the calculation of the generalized Gaussian moments do, d1, d2 for popular activation functions used in random features and neural network contexts. Note that Table 1 matches the results in (Liao & Couillet 20185 Table 2).
Table I: Values of do: d1, d2 for different activation functions.
(t))
do
dj
d2
[d]
(1 - +
1 2n7
m)
1 ( )
-1, 1<8_
1 - erf
+
2
2
+1, t> 84
-
846
TV
0, otherwise
a4 max(0, + a max(0,
T Ta+ + aa))
(3
(==2)
144-0_y
(0++a-)
4x
8
azl2 + on
27 2
2
2
exp(t)
0
V2r-I
4(7+1)9
cts
14e-2:
-
sin(t)
1-e-2r
7e
e
2
t
0
sign(t)
1 - 2
2.
1,50
1
2x
A.6 ADDITIONAL EXPERIMENTS
In this section, complement Section 4 by providing additional experiments on ridge regression and support vector machine, to support the robustness our TRF method compared to state-of-th saat--of-the-an art approaches.
Remark 4 (On the empirical and expected random features kernels) It is worth noting that our main results in Theorem 7 and Corollary [ characterize the behavior of the expected/limiting random features kernel K instead of the empirical Gram kernel matrix G defined in (6) obtained by averaging over m random features. The operator norm difference | G is then bound to vanish as m. p, n + 00 for a sufficiently large m (for example with m/ max (n, p) o0).
Random features based Ridge regression To complement the experiments in Section 4. we provide Figures 5 9 the test mean square error of random features kernel ridge regression with increasing number of random features m E {512, 4096, 104] for GMM data in Figure 5 and m E (512, 10a) for MNIST data in Figure and as a function of the regularization parameter y and for different choices of sparsity levels {0.1. 0.3, 0.5, 0.7, 0.9}. It is interesting note that, for both datasets, the performance gap between RFFs and TRFs significantly decreases as m the number of random features grows large: this is in agreement with our Theorem [ in which guarantee is provided only for the expected kernel matrix (that corresponds to m - oc), not the empirical Gram matrix as the sample mean random features.
21

---

Published as a conference paper at ICLR 2022
Baseline (KRR) RFF
0.8
TRF
80
Rusning timx (8)
0.8
60
Baseline (KRR)
RFF
(TRF)
40
0.2
0.9 (TRF)
20
10 2 10
10
0.1
0.3
0.5
0.7
Figure Testing MSE of kernel ridge regression a function of regularization parameter 7 512, = 1024, Neatt = 512, match gaussian moments of (cos, sin] function) with W distributed according equation 4 with E E {0.1, 0.3, 0.5, 0.7, 0.9} versus KRR and RFF. GMM dataset with Na -0a-1 1 4: Op. a C. (1 + 4(a 1)/ /p) p, P = 512, n 2048. Results averaged over independent runs.
512. Ternary function (with thresholds s 8+ chosen to
Baseline (KRR)
150
Raseline (KRR) RFF TRF
REF 0.1 (TRF)
0.5 (TRF)
Rumning time (S)
0.6
0.9 (TRF)
MSES
100
0.4
50
0 10
2
10 0.1
0.3
0.5
0.7
0.9
Figure 6: Testing MSE of kernel ridge regression a function of regularization parameter 7 p 512, n 1024, Reast 512, m 4096. Ternary function (with thresholds s-, 8+ chosen to match gaussian moments of [cos, sin| function) with W distributed according to equation 4 with e E {0.1, 0.3, 0.5, 0.7, 0.9) versus KRR and RFF. GMM dataset with 14, -0.-1: 4; Op- a (1 + 4(a 1)/ /D) Ip, 512, n 2048. Results averaged over independent runs.
Baseline (KRR)
500
Baseline (KRR) RFF TRE:
0.8
0.1 (TRF)
0.5 (TRF)
Running time (s)
400
= 0.9 (TRF)
MSEs
300
0.4
200
0.2
100
10-2
10-1
10a
10a
0.1
0.3
0.5
0.7
0.9
Figure Testing MSE of kernel ridge regression as a function regularization parameter 7 p 512, 1024, Nies 512, = 10a. Ternary function (with thresholds 8-,84 cho- sen to match gaussian moments of [cos, sin] function) with W distributed according to equa- {0.1, 0.3, 0.7, 0.9} versus KRR baseline and RFF. GMM dataset with μa 10,-1:400 Op-e], C. = (1 + 4(a 1)/vp) 512,n n = 2048.). Results averaged over independent runs.
tion 4 with
22

---

Published as a conference paper at ICLR 2022
Buseline (KRR) RFF
TRF
Running time
MSH
0.4
Baseline (KRR) RFF
0.1 (IRF)
0.2
0.5 (TRF)
0.9 (TRF)
10
10a
10
0.1 0.3 0.5 0.7 0.9
Figure 8: Testing mean squared errors (MSEs, LEFT) and running time (RIGHT) of kernel ridge regression as a function of regularization parameter y, p 512, 1024, Neest 512, m 512. Ternary function (with thresholds 8-, 84 chosen to match the Gaussian moments di d2 of (cos, sin] function) with W distributed according (4) with E {0.1, 0.3, 0.5, 0.7, 0.9), versus KRR and RFFs on MNIST dataset 2 classes digits (7.9). Results averaged over independent runs.
1
Baseline (KRR)
0.8
300
TRF
RFF
Running time
MSEs
0.4
Baseline (KRR) RFF
0.1 (TRF)
0.2
(TRF)
(TRF)
10-2
10-
10"
10
0.1
0.3
0.5
0.7
0.9
Figure 9: Testing mean squared errors (MSEs, LEFT) and running time (RIGHT) of kernel ridge regression as a function of regularization parameter 7, p 512, 1024, Nestt 512, m 10* Ternary function (with thresholds 8-, 84 chosen to match the Gaussian moments d1, d2 ícos, sin] function) with W distributed according (4) with E (0.1, 0.3, 0.5, 0.7, 0.9), versus KRR and RFFs on MNIST dataset classes digits (7, 9). Results averaged over independent runs.
23

---

Published as a conference paper at ICLR 2022
SSF - RFF
Lineur SVM accurccy (30)
884
0.8
ORF
TRF
Ronning time (5)
82
0.6
800
0.4
78x
0.2
log(m/p)
log(m//p)
Figure 10:
Test accuracy using libsvm on different state-of-the-att random features kernels. a8a (UCI)
dataset. Number of training samples 22696 number of test samples nh 9865, varying ratio log m/p number of random features over dimension p = 123. Note that the y-axis zoomed in to better distinguish the performance of different methods.
93
* SSF
(56)
0.8
RFF
4 ORF
92
TRF
Linear SVM accurccy
Running time (s)
0.6
91
0.4
90
0.20
89
2
4
log(m/p) /p)
log(m/p)
Figure 11: Test accuracy using libsvm on different state-of-the-ar random features kernels. IJCNN1 (Prokhorov) 2001) dataset. Number of training samples n 49990 number of test samples 91701, varying ratio log m/p number of random features over dimension p 22. Note that the y-axis is zoomed in to better distinguish the performance of different methods.
Random features based Support Vector Machine We empirically evaluate the classification
performance of various random features approximation algorithms,, several benchmark datasets. We compared the different algorithms (RFF (Rahimi & Recht ORF YYu et al. 2016). SSF (Lyu) 2017)) on 3 datasets IJCNNI (Prokhorov) 2001). Cov-Type, and a8a from the UCI ML. repository considered (Liu et al., 2021a), with our TRF method where we choose the thresholds coefficients
8-,84 84 according to Algorithm | (to match the generalized Gaussian moments of Gaussian kernel). Figure shows the results for the a8a dataset, Figure TT for the IJCNNI dataset and Figure [2 for the Cov-Type dataset. The lower running time along with higher SVM test accuracy indicates the superiority of our RMT-inspired TRF method over the other Gaussian kernel approximation methods.
Comparison of TRF with equivalent 0th order Are-cosine kernel (with ReLU function) We consider Support Vector Machine (SVM) classification with random features Gram matrix G on Fashion MNIST data (LeCun et al. 1998) and on VGG16 embeddings of CIFARIO (Krizhessky et 2009) and Imagenet (Deng et al. (209) datasets in Figures [4 [3 15 respectively. We use VGG16 with batch normalization (loffe & Szegedy 2015) pre-trained on ImageNet (Deng et al. 2009) as a feature extractor. We fine-tune this model on the CIFAR1O dataset with 240 epochs and a minc-batch size 64 with a SGD optimizer with momentum 0.9 and an initial learning rate of 0.1. We then extract the output of the first fully connected layer of the classifier as our features. For Imagenet, extract the features from the pretrained model. We compare (i) RF with (t)) = max(t, 0) (ReLU) and Gaussian W, A/0 1) (known the (thh order Arc-cosine kernel) to (ii) the proposed TRF
directly
24

---

Published as a conference paper at ICLR 2022
SSF
Linea SVM accuricy score (%)
8 RFF
TRF
Running time (5)
36
log(m/pp
log(m/p))
Figure 12: Test accuracy using libsvm on different sfate-of-the-ar random features kernels. Cov-Type dataset. Number of training samples 49990 number of test samples 91701, varying ratio log m/p number of random features over dimension p = 22.
* Arc Cusine RF (o(()) (e)
90
TRF (a((t) offr(())
Text SVM Accuracy (%6
80
Running time (5)
0.4
70
0.2
60
50
10
210
410
710
910
700
210
350
490
630
m
Figure 13: SVM test accuracy using different kernels. VGG-16 Embeddings of CIFARI0 dataset (Number features p = 4096). Number of samples n = 1024 fixed, varying number of random features from 10 to 1800.
method with fer 8-,84 of geer are tuned in such away that the generalized Gaussian moments d₁ and de are matched with those of ReLU (see Table [I, as described in Corollary [ and Algorithm Figures 14 13 I5 display the test SVM accuracy as function of the number of random features, for our TRF method compared to the random features corresponding to the Arc-Cosine kernel. We observe similar test performances with the two kernels while having a computation and storage gains for the ternary kernel.
(() (L) in and ternary random projection matrix Wter defined in (4 The thresholds
25

---

Published as a conference paper at ICLR 2022
Are-Cosine RF (a(f) ReLU(()) TRF (a(() س (0)
0.75
0.7
Test
0.65
0.29
0.07
Figure 14: SVM test accuracy using different kernels. Raw Fashion-MNIST dataset (Number of features = 784). Number of samples = 1024 fixed, varying number of random features from m 70 m 700. Note that the y-axis is zoomed to better distinguish the performance of different methods.
0.4
* Arc-Cosine RF (o(() = ReLU())
TRF (a(1) = o (t))())
Test SVM Accuacy
0.3
Running time (3)
0.1
10a
770
210
350
490
630
210
350
490
630
m
Figure 15: SVM test accuracy using different kernels. LeNet-64 Embeddings of Imagenet dataset (Number features p = 2018). Number of samples n 1024 fixed, varying number of random features from m 10 to 1800.
26


Reviews:
[{"review_id": "uNRyOpgsEpv", "reviewer": "Reviewer_2gn7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the ternary quantization idea and it seems to work great in the practical experiments. It seems to give roughly a 2x speedup and 8x memory decrease compared to RFF and other kernel methods, which is quite impressive. The theoretical results are interesting but they work under quite restrictive assumptions.\n\nI have concerns on the quality of presentation of the theoretical results. In particular, I am sure the statement of Theorem 1 can be made clearer. For example, the quantities defined after (8) seem to be in somewhat random order which makes it hard to read. Also, it would be good to flesh out what is the main *technical* insight of Theorem 1 compared to previous work. More importantly, I was not able to follow the proof of Theorem 1. My suggestion is to add more text to explain what is happening and re-write equations like (19) in a way that is easier to parse. Also, I don't see how Corollary 1 follows from Theorem 1. E.g. where is (10) coming from? but also there is a lot of explanation missing here since the approximate kernels in Theorem 1 and Corollary 1 are very different.\n\nI would like to see a discussion about the assumption that the entries of $w$ are i.i.d. In particular, when (and why) should I expect this assumption to hold?\n\nI didn't see any discussion on the minimum number of random features $m$ needed. Is this not necessary in the analysis?\n\nWhat is the time to compute the random features? It seems like it has some non-trivial parts like computing $\\hat{s}^+$, $\\hat{s}^{-}$, so it would be good to have a short discussion on this (with some sample runtimes), and also explain a bit more how $\\hat{s}^{+}, \\hat{s}^{-}$ are computed.", "summary_of_the_paper": "The authors present a resource-efficient approach for approximating kernels using random feature transformations. The random feature approach was introduced in a seminal paper by Rahimi and Recht, where each random feature is extracted from the input $x$ as $\\sigma(\\langle w, x\\rangle )$, for a random (appropriately distributed) vector $w$ and an activation function (e.g. sinusiod) $\\sigma$. In this paper, the goal is to save memory and time by restricting $w$ and $\\sigma$ to take values in {$-1,0,1$}, meaning that $\\sigma(\\langle w, x\\rangle )$: \n1. can be evaluated only with additions/subtractions (no multiplications) and\n2. only takes $1$ bit of storage. \n\nThe authors prove that under some conditions, their kernel estimate approaches the true kernel at the limit where the number of features and the number of data points are comparable and approach infinity. The assumptions are roughly:\n1. The data follows a Gaussian mixture model,\n2. the input features are approximately pairwise orthogonal,\n3. the entries of $w$ are chosen i.i.d. and have bounded fourth moment, and\n4. some boundedness assumptions on the generalized Gaussian moments of $\\sigma$.\n\nThe theoretical result is accompanied by numerical experiments on various tasks like kernel ridge regression and SVM on both real and synthetic datasets. The results demonstrate a significant advantage of the authors' approach compared to previous quantized random features approches, both in terms of runtime and memory, without a significant drop in accuracy.", "summary_of_the_review": "In summary, this paper is mostly well-written except for the theoretical parts which need some work. The idea is really interesting and relevant for resource-intensive applications. The experimental results look very promising. I am leaning towards acceptance, but I might change my rating based on if my concerns have been resolved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "qrTqq2xIOyd", "reviewer": "Reviewer_RdKc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1)\tThis paper provided self-contained theoretical guarantees for the asymptotic equivalent of the primal kernel and a delicate form of ternary random features. The asymptotic results are interesting, and the proofs seems to be correct.\n2)\tThis paper designed a simple and efficient framework to construct ternary random features. Due to the sparsity of ternary random features, the algorithm is benefit from both high computational efficiency and lower storage complexity.\n3)\tThis paper also provided experimental validations by comparing the training time, memory costs and MSE with SOTA methods. The empirical results coincided with the theoretical finding, that the proposed approach characterized both computational and storage gains.\n4)\tThe writing of this paper is clear, and most parts are easy to follow.\n\nWeakness:\n1)\tMy main concern is that the Gaussian mixture data assumption may be too strong. As shown in Eq. (7), this paper assumed the inputs are under multivariable Gaussian distribution. Many real-world datasets break this condition, such as long-tailed distribution. Moreover, the classic random features, for example random Fourier features, have no restriction on data distribution. Besides the Gaussian data assumption, Assumption 1 (iii) also seems to be strict. The authors are expected to provide more examples to illustrate the applicability of these assumptions.\n2)\tThe presented asymptotic theory requires the dimension of input space to approach infinity $p \\to \\infty$ is unfamiliar in practical. Because the dimension of input space is fixed, I wonder that is there still a good approximation between $K$ and $\\tilde K$ if $p$ is small? For a given task with a fixed $p$, is there a natural gap between $K$ and $\\tilde K$?\n3)\tIt seems both Theorem 1 and Corollary 1 are independent from the required number of random features $m$. In the existing random features literature, $m$ is crucial to the approximation ability and generalization ability. In general case, $m=O(\\sqrt{n})$ random features can guarantee the similar generalization ability (Rudi and Rosasco, 2017). The authors may illustrate how the number of ternary random features influence the approximation or generalization.\n4)\tThe kernel hyperparameters usually determine the performance of kernel methods, but the proposed random features approach seems to be independent from kernel hyperparameters and only depend on the kernel type. Can TRF approximate any kernel with different hyperparameters? How does TRF remove the influence of kernel hyperparameters?\n\nRudi A, Rosasco L. Generalization Properties of Learning with Random Features[C]//NIPS. 2017: 3215-3225.\n", "summary_of_the_paper": "With Gaussian mixture assumption for input data, this paper proposed a sparse random features approach where the approximated kernel is independent of the iid weights and depends on Gaussian moments of the activation functions. This paper provided a theoretical guarantee for the asymptotical equivalence with the centered kernel. And then, the authors derived the computationally efficient random features and devised a simple algorithm. Finally, they validate the accuracy and efficiency of the proposed random features by several experiments.", "summary_of_the_review": "This paper provided the sparse random features with theoretical guarantees, efficient algorithm and sufficient experimental validations. However, this paper assumed the input data with Gaussian mixture that may limit its applicability. Meanwhile, the influence of the number of random features has not been explored well.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "c-90PpwJUmT", "reviewer": "Reviewer_AjvY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Quality and Clarity\n\nThe paper is well written and clear. It was easy to follow. I'm not a fan of purely kernel oriented papers discussing deep learning in the introduction if that's not significant to the paper, but that's a personal subjective preference. Good marks for quality and clarity\n\n# Theory\n\nThe core theoretical claim is compelling in its generality and formality. While it wouldn't be enough to carry the paper on its own, it serves as a nice motivation for the TRF algorithm proposed. There's really only one theoretical claim in the paper, but that claim is all they need to show. It's well stated, clear, and to the point. Elegant.\n\nAmongst the theory, the only clarification I would like to see is why the estimator $\\hat\\tau = \\frac1n \\sum_{i=1}^n \\|x_i\\|^2$ is asymptotically correct. I assume this follows from some simple properties of the Gaussian distribution, but it would be nice to see at least this discussed in the paragraph before _Algorithm 1_.\n\nAs a side note: while I didn't review the full proof of Theorem 1, glancing at the appendix, the proof seems surprisingly (in a good way) simple and approachable for a RMT proof. Props.\n\n# Experiments\n\nThe theory in this paper serves as a motivation for the TRF algorithm which approximate the kernel matrix. Unlike most work on random features, this paper's theory requires data to be drawn from a gaussian mixture model (GMM). Since most theory of kernel approximations don't require this assumption, in my view, this paper lives and dies by its experiments: is the GMM essential to the proposed approach, or is it a mathematical simplification to make the math more tractable and motivation a pragmatic algorithm?\n\nThe experiments are largely convincing. There's several points I would very much like to see (frankly I expect to see) fixed up in a camera-ready version. But overall, the experiments are compelling, so I think the overall paper works well. This suggests the GMM assumption in the theory was just a simplification to make the math tractable.\n\nOverall, the experiments compare three statistics: running time, space complexity, and the statistical performance of the resulting kernel matrix. The proposed TRF algorithm is compared usually against classical Random Fourier Features (RFF), and sometimes against a few other kernel approximation algorithms.\n\nThe experiments suggest that TRF is notably faster and uses less space than RFF. Further, they can tune a sparsity parameter to tradeoff the accuracy of the kernel matrix with the space of the kernel matrix. Some interesting takeaways from these experiments:\n- A very sparse kernel sometimes does not impact accuracy a lot, and sometimes is very important (figures 5, 6, and 7 show sparsity control accuracy for only moderate amounts of regularization). Is there a rational about _when_ sparsity impacts accuracy a lot?\n- Sparsity helps speed up computation, but not a huge amount. Going from a $90\\%$ nonzero matrix to a $10\\%$ nonzero matrix can shave off $\\frac13$ of the computation time. It's a good boost, but maybe bad value if this can increase error by $50\\%$?\n    - The $50\\%$ number comes from Figure 5, $\\gamma\\approx5$, where the triangle has MSE $0.5$ and the $\\otimes$ has error $0.75$.\n- The running time improvements are especially encouraging across the board.\n\nThese experiments are strong enough (suggesting that the theory -- as they conjecture -- is more general than the GMM setting) that I support clearly accepting the paper.\n\nThat said, here are the changes I would like/expect to see in an experiment driven paper like this:\n1. Better baselines. We see most plots use classical RFF as a baseline, but this doesn't always make sense. In Figure 3, we see the $\\varepsilon=0.1$ data fall below the baseline MSE, suggesting that TRF outperforms RFF. That makes for a weird baseline. I would like to see the true optimal MSE, computed without any random features at all. I would like to see this on all the statistical efficiency (MSE and accuracy) plots.\n    - This will add a good deal more of valuable information: like in Figure 3 on the left plot, we see a gap between all TRF models and the RFF model. Is the RFF model close to the true baseline, or do TRF and RFF both have a large gap from the baseline? I understand there is some approximation error, but I don't understand if there's a lot of approximation error.\n1. Confidence intervals. TRF and RFF are both randomized algorithms. RFF has many well studied concentration inequalities, so I'm reasonably confident it's well concentrated. I don't know that about TRF though. What do the $25^{th}$ and $75^{th}$ quantiles look like? Also, how many repetitions did you run these algorithms for?\n1. For Figures 5, 6, and 7, where there's a lot of series of data, these plots are too hard to read. I would recommend reducing the number of series (i.e. drop $\\varepsilon=0.3,0.7$) to make the lines more legible when the confidence intervals are added, and to color code the series instead of using different markers.\n\n---\n# Extra Tidbits\n\n## Some Technical Questions I Have\n1. In the experiments, you mention using 32 bit floats for Nystrom approximation. To reduce space complexity, can you just perform the same computations with 16 bit floats or 8 bit floats. Does this have a disastrous statistical impact, or could we close the gap between TRF and Nystrom a bit, very easily?\n1. Are you aware of Michael Mahoney's work on Random Matrix Theory for deep learning? I read one or two of those papers a while back, and they might also fit into this world of RMT to understand efficient estimators (e.g. in the end of your Section 1.3)? Not totally sure, and I don't want to force you to add in a reference to an unrelated paper. Just want to bring up a possibly interesting connection existing in the literature.\n1. When does TRF give better statistical performance than RFF? (Figure 3 left image, large $\\gamma$ and small $\\varepsilon$)\n\n## Typos and small recommended edits\n1. [Page 2 footnote] \"is equivalent to _centering_ the data\" not \"center\"\n1. [Figure 4] Replace \"$0.5 \\cdot 10^{-2}$\" with \"$0.05$\"\n1. [Figures 11-15] Mention in the captions that the y-scale is zoomed in a lot. Explicit is better than implict.\n1. [Figure 12] Add the dataset name to the caption. I know it's mentioned in the text of the appendix, but it should be here too.\n", "summary_of_the_paper": "The paper proposes a way to approximate common kernel matrices in a way that is (1) Sparse (2) Low Bit-Complexity (i.e. the nonzero entries have few bits) (3) efficient to compute.\n\nThe theoretical justification from this model comes from a random matrix theory (RMT) analysis of kernel matrices for datasets of vectors drawn iid from a fairly general gaussian mixture model. The RMT analysis shows that the true kernel matrix is asymptotically distributed as the approximation described above. No non-asymptotic results are given.\n\nThe introduction mentions deep networks, but this paper really has no strong connection to deep learning. View it as a kernel paper.\n\nA good amount of supporting experiments are given to demonstrate that the approximate kernel matrix has the same statistical performance as (eg) a Random Fourier Features approximation.", "summary_of_the_review": "The theory is a compelling motivation for a proposed matrix approximation algorithm that seems to experimentally work well.\n\nThey should clean up their experiments a little, but this is overall encouraging as a pragmatic way to reduce the time and space complexity of real kernel algorithms by large constant factors.\n\nI recommend this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "JtEbDYflsZJ", "reviewer": "Reviewer_c4jW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well organized. I like the idea of the paper to exploit the theoretic result (in the high dimensional limit the spectrum of the kernel only depends on the first two generalized Gaussian moments of the activation function) by coming up with a sparse choice of the activation function and projection weight's distribution, that could make the random features computationally efficiently and easier to store.\n\nThe main concern is the importance of this finding (have a constant scale improvement in computation time and storage memory). I believe the proof technique of the main theorem is not original, so the contribution mainly come from the gains in computation and storage. I feel the authors should spend more space to argue that.\n\nSome minor issues:\n- In page 7 the authors argue that, the computation of the proposed random feature requires no multiplication and only $O(\\epsilon mnp)$ additions. Could there be more explanations around this claim? For example, (1) in the case $\\epsilon != 0$, why there is no multiplication needed, (2) in the case $\\epsilon = 0$, does the proposed random feature requires no multiplication and no additions? Or should the needed additions be $O((1-\\epsilon) mnp)$ instead since $1-\\epsilon$ proportion of the weights are non-zero?\n\n-------------- After revision ---------------\n\nThanks the authors' response. After reading the response and other reviewers' comments, I agree that the constant scale improvement in computation time and storage is a good contribution, and I raise my score to 6.", "summary_of_the_paper": "This paper studies random features method, which randomly projects the data onto a low-dimensional space, while at the mean time approximates the original kernel structure. \nSome contributions of this paper:\n- The authors show that, under the Gaussian mixture model, in the high-dimensional limit, in the spectrum sense, the random features-type kernel (defined in equation (1) of the paper) only depends on the first two generalized Gaussian moments of the activation function (with the assumption that the random projection weights are i.i.d. from some mean 0 and var 1 distribution).\n- Based on the above result, the authors propose a special choice of the random weights and the activation function, that could be efficiently computed and needs less memory to store.\n- The authors provide empirical evidence showing that the proposed method performs as well as other random features methods, and with advantage in computation and storage.", "summary_of_the_review": "My biggest concern is how important the main contribution is (have a constant scale improvement in computation time and storage memory). To be honest I'm not sure how to measure that, and thus will lower my confidence score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers overall were quite happy after the rebuttal phase, in which the authors considerably improved the presentation quality and addressed reviewer concerns, and recommended acceptance. The reviewers agreed that while the theory was short and relied on various possibly restrictive assumptions and maybe was largely an improvement in constant factors, it extended prior work (some of which was in ICLR) and was interesting and motivated the experiments which were notably faster than existing methods.
Decision: Accept (Poster)