# Why are random Fourier features efficient?

I am trying to understand Random Features for Large-Scale Kernel Machines. In particular, I don't follow the following logic: kernel methods can be viewed as optimizing the coefficients in a weighted sum,

$$f(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{n=1}^{N} \alpha_n k(\mathbf{x}, \mathbf{x}_n) \tag{1}$$

Let $$\mathbf{x} \in \mathbb{R}^D$$ and let $$K < D$$. Rahimi and Recht propose a map $$\mathbf{z}: \mathbb{R}^D \mapsto \mathbb{R}^K$$ such that

\begin{align} \mathbf{w}_j &\sim \mathcal{N}(\mathbf{0}, \mathbf{I}) \\ \hat{k}(\mathbf{x}, \mathbf{y}) &= \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \mathbf{z}(\mathbf{y}; \mathbf{w}_j). \end{align}

Cool so far. Here's what I don't undertstand. Rahimi then claims here that if we plug in $$\hat{k}$$ into Equation $$1$$, we get an approximation,

$$\hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{j=1}^J \beta_j \mathbf{z}(\mathbf{x}; \mathbf{w}_j).$$

Question: I don't see how we get to eliminate the sum over $$N$$. I would have expected:

$$\hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{n=1}^{N} \alpha_n \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \mathbf{z}(\mathbf{x}_n; \mathbf{w}_j).$$

I could possibly rearrange the sums, but I still don't see how we can eliminate the sum over $$N$$,

$$\hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \underbrace{\sum_{n=1}^{N} \alpha_n \mathbf{z}(\mathbf{x}_n; \mathbf{w}_j)}_{\beta_j??}.$$

What am I missing?

So this kind of looks like a case of notational abuse to me.

### Quick Review of Dual Formulation of SVMs and Kernel Trick

For standard, basic vanilla support vector machines, we deal only with binary classification. As is typical, our two class labels will be encoded by the set $$\mathcal{Y} = \{+1, -1\}$$. I'll also use the notation $$[m] = \{1, 2, \dots, m\}$$. Our training data set is a sample of size $$m$$ of the form $$S = \{(\mathbf{x}_{i}, y_{i}) \ |\ i \in [m], \ \mathbf{x}_{i} \in \mathbb{R}^{D},\ y_{i} \in \mathcal{Y} \}$$.

After reformulating the problem in Lagrange dual form, enforcing the KKT conditions, and simplifying with some algebra, the optimization problem can be written succinctly as: $$\max_{\alpha} \sum_{i = 1}^{m}\alpha_{i} - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_{i}\alpha_{j}y_{i}y_{j}(\mathbf{x}_{i}\cdot\mathbf{x}_{j}) \tag{1}\\ \text{subject to}:\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\ \alpha_{i} \geq 0\ \ \forall i\in [m]\\ \sum_{i=1}^{m}\alpha_{i}y_{i}=0$$

The support vectors are the sample points $$\mathbf{x}_{i}\in\mathbb{R}^{D}$$ where $$\alpha_{i} \neq 0$$. All the other points not on the marginal hyperplanes have $$\alpha_{i} = 0$$.

The Kernel trick comes from replacing the standard Euclidean inner product in the objective function $$(1)$$ with a inner product in a projection space representable by a kernel function: $$k(\mathbf{x}, \mathbf{y}) = \phi(\mathbf{x}) \cdot \phi(\mathbf{y})\\ \text{where}\ \ \phi(\mathbf{x}) \in \mathbb{R}^{D_{1}}$$ This generalization let's us deal with nonlinearly separable situations since if we take $$D_{1} > D$$, we can find a linear separator in this higher-dimensional $$D_{1}$$ space corresponding to a nonlinear separator in our original $$D$$⁠-dimensional space.

### Correcting Notational Abuse

Let's look at these inner products a little more closely. The Euclidean inner product is the familiar sum: $$\mathbf{x}_{i}\cdot\mathbf{x}_{j} = \sum_{t=1}^{D}x_{i,t}x_{j,t}$$

So we see that the objective function $$(1)$$ really has this $$D$$ term sum nested inside the double sum. If I write $$\phi(\mathbf{x}) = \large{(} \normalsize{\phi_{1}(\mathbf{x}), \phi_{2}(\mathbf{x}), \dots, \phi_{D_{1}}(\mathbf{x})} \large{)}$$, then the kernel inner-product similarly looks like: $$\phi(\mathbf{x}_{i})\cdot\phi(\mathbf{x}_{j}) = \sum_{t=1}^{D_{1}}\phi_{t}(\mathbf{x}_{i})\phi_{t}(\mathbf{x}_{j}) \tag{2}$$

So from $$(2)$$ we are reminded that projecting into this higher-dimensional space means that there are more terms in the inner product. The 'trick' in the kernel trick is that appropriately chosen projections $$\phi$$ and spaces $$\mathbb{R}^{D_{1}}$$ let us sidestep this more computationally intensive inner product because we can just use the kernel function $$k$$ on the points in the original space $$\mathbb{R}^{D}$$ (for example, as long as the kernel satisfies Mercer's condition).

Ok, everything up to this point has pretty much been reviewing standard material. What Rahimi's random features method does is instead of using a kernel which is equivalent to projecting to a higher $$D_{1}$$⁠-⁠dimensional space, we project into a lower $$K$$-dimensional space using the fixed projection functions $$\mathbf{z}$$ with random weights $$\mathbf{w}_{j}$$. So rather than having a single projection $$\phi(\mathbf{x})$$ for each point $$\mathbf{x}$$, we instead have a randomized collection $$\mathbf{z}(\mathbf{x}, \mathbf{w_{j}})$$ for $$j \in [J]$$. In terms of the component notation, earlier we had: $$\phi(\mathbf{x}) = \large{(}\normalsize \phi_{1}(\mathbf{x}), \dots, \phi_{D_{1}}(\mathbf{x} ) \large{)} \tag{3},$$

whereas now we have: $$\mathbf{z}(\mathbf{x}, \mathbf{w}_{1}) = \large{(}\normalsize z_{1}(\mathbf{x}, \mathbf{w}_{1}), \dots, z_{K}(\mathbf{x}, \mathbf{w}_{1})\large{)} \\ \vdots \tag{4}\\ \mathbf{z}(\mathbf{x}, \mathbf{w}_{J}) = \large{(}\normalsize z_{1}(\mathbf{x}, \mathbf{w}_{J}), \dots, z_{K}(\mathbf{x}, \mathbf{w}_{J})\large{)}$$

As they allude to in one of the three papers Rahimi places in this trilogy, I forget which one, the components of projection functions of $$(4)$$ can now be viewed as $$J$$-dimensional vector valued instead of scalar valued in $$(3)$$. So now you're replacing your $$D_{1}$$-dimensional projection with $$J$$ individual $$K$$-dimensional projections, and substituted your $$D_{1}$$ term sum with a $$JK$$ term sum in each inner product.

So now your inner product is in fact a double sum, over both the $$J$$ components of each projection and the $$K$$ dimensions of the space: $$\hat{k}(\mathbf{x}, \mathbf{y}) = \sum_{t=1}^{K} \sum_{j=1}^{J} \beta_{j}z_{t}(\mathbf{x})z_{t}(\mathbf{y}) \tag{5}$$

Contrast this with the single sum representing the kernel equivalent inner product in $$(2)$$.

Hopefully tracking each index separately clarified things for you. As for why this is 'efficient,' since the $$K$$-dimensional projection is lower-dimensional, that's less computational overhead than figuring out the typical higher $$D_{1}$$ dimensional projection. Also, since you're randomly generating $$J$$ of these projections, assuming your random generation is computationally cheap, you get an effective ensemble of support vectors pretty easily.

• This is great, thanks. However, I am confused about $K$. What is $K$ and why isn't it just $J$? Each $z_{\omega_j}$ is really a $D$-vector, since it forms a dot product with a given $\mathbf{x} \in \mathbb{R}^D$. Then $\mathbf{z}_{\boldsymbol{\omega}}(\mathbf{x}) = [z_{\omega_1}^{\top} \mathbf{x}, \dots z_{\omega_J}^{\top} \mathbf{x}]$. – gwg Dec 20 '19 at 16:56
• My current understanding is that the efficiency of RFFs is that we can form a matrix $\mathbf{Z}$ that is $N \times J$, and provided $J \ll N$, then linear methods such as computing $\boldsymbol{\beta} = (\mathbf{Z}^{\top} \mathbf{Z})^{-1} \mathbf{Z}^{\top} \mathbf{y}$ is much faster if we did the same computation but with $\mathbf{X}$. For example, matrix inversion in $\mathcal{O}(NJ^2)$ rather than $\mathcal{O}(N^3)$. – gwg Dec 20 '19 at 16:59
• I can't edit my first comment, but clearly $\mathbf{z}_{\boldsymbol{\omega}}$ isn't just a vector of dot products but rather the full transformation as described in the paper. – gwg Dec 20 '19 at 17:04
• @gwg I was actually going to expand this answer a little later today, because I realized I was somewhat vague about the efficiency part. In order to really understand the efficiency part, you have to go into the Fourier theory. Given some assumptions on the kernel function you’re trying to approximate, the density of the Fourier basis functions in the function space you’re in implies that a randomly selected collection of basis functions will give you a low error approximation with high probability (a type of PAC learning statement). Will edit my answer to incorporate this aspect. – Don Walpola Dec 20 '19 at 17:06
• Rahimi suggests here (youtu.be/4Fz5syoDXXw?t=431) that a representer theorem implies that the decision function $f(x)$ that we want to learn is linear in the high-dimensional space associated with $\varphi(x)$. Therefore, if we have a good approximation of $k(x, y)$, which is equivalent to $\langle \varphi(x), \varphi(y) \rangle)$, then we can assume that our approximation is linear in $z$. – gwg Dec 22 '19 at 16:16