In Ali Rahimi's and Ben Recht's paper "Random Features for Large-Scale Kernel Machines," there is a line near the bottom of the introduction which I can not reason about...
In addition to giving us access to extremely fast learning algorithms, these randomized feature maps also provide a way to quickly evaluate the machine. With the kernel trick, evaluating the machine at a test point x requires computing $$ f(x) = \sum_{i=1}^N c_i k(x_i, x) $$
which requires $O(N d)$ operations to compute and requires retaining much of the dataset unless the machine is very sparse. This is often unacceptable for large datasets. On the other hand, after learning a hyperplane w, a linear machine can be evaluated by simply computing $$f(x) = \mathbf{w}^\top \mathbf{z(x)}$$ which, with the randomized feature maps presented here, requires only $O(D + d)$ operations and storage.
Question
Why is it that in the kernel trick, we have to optimize over a column in the actual kernel with entries for $\mathbf{x}_i$ and $\mathbf{x}_j$, but in the random Fourier features, it is acceptable to just use the transformed features when optimizing the coefficients (which only contains the information from $\mathbf{x}_i$ since the actual kernel is supposed to be composed as
$$ k(\mathbf{x}, \mathbf{y}) = \langle \phi(\mathbf{x}), \phi(\mathbf{y}) \rangle \approx \mathbf{z(x)}^\top \mathbf{z(y)} $$
If I perform the inference $\mathbf{w}^\top \mathbf{z(x)}$, I am completely ignoring any kernel information that would have been supplied by $\mathbf{y}$, right? So how does this make sense?
