# random kitchen sinks as approximation to kernel machine

In the paper

Rahimi, Ali, and Benjamin Recht. "Random features for large-scale kernel machines." Advances in neural information processing systems. 2008.

the author introduces a way to approximate stationary kernel function by a way of random sampling in the feature space. The author did an experiment to solve the following ridge regression

$$\min_{w} ||Z'w - y||_2^2 + \lambda ||w||_2^2$$

where $$w$$ would be a vector of $$D$$ dimension.

The dimension of $$w$$ does not make sense to me. In order to approximate the kernel function with sufficient accuracy, we need to use a high number of $$D$$. It gives me a feeling of a high risk of overfitting the model and my model is appeared to be overfitting when I am trying to make use of it.

A kernel ridge regression can be described by the following equation:

$$f(x) = \sum_{i=1}^N \alpha_i k(x,x_i)$$

for $$\alpha_i$$ is computed by $$\alpha = (K + \sigma^2 I)^{-1} y$$.

In the paper, the author is trying to approximate $$k(x,y)$$ as

$$\begin{array} \\ k(x,y) & = k(x-y) \\ & \approx \operatorname{E}(z(x)'z(y)) \\ & = \displaystyle \frac{1}{D} \sum_{j=0}^{D} z_{\omega_j}(x)z_{\omega_j}(y) \\ & \mbox{ for }\omega_j\mbox{ draw from }p(\omega)\\ \end{array}$$

Isn't the true approximation to the kernel machine should be

1. For each data points $$x_i$$, $$x_j$$:
2. Compute $$K_{ij} = k(x_i,x_j) \approx \frac{1}{D} \sum_{k=0}^{D} z_{\omega_k}(x_i)'z_{\omega_k}(x_j)$$
3. Solve $$(K + \sigma^2I)^{-1} y$$

rather than sampling $$D$$ numbers of $$z_\omega(x)$$ and then fit a parametric model with $$D$$ parameters?

I think the author is trying to fit a linear model in the feature space (as $$z(x)$$ is the feature map) rather than the standard kernel trick which does not need to evaluate the feature map. But I don't understand why the author do not need to compute the sample average of $$K$$ (or do something similar to $$z$$)?

The implementation here is also fitting a model of $$D$$ parameter, no averaging step is done, which makes me quite confusing.

Let's say there are 1000 data points and the feature space is of infinite dimension and requires $$D=10000$$ to approximate $$K$$ with sufficient accuracy, am I going to fit 10000 parameters over 1000 data points?

What am I missing?