Title: Not-So-Random Features,
Abstract: We propose a principled method for kernel learning, which relies on a
Fourier-analytic characterization of translation-invariant or
rotation-invariant kernels. Our method produces a sequence of feature maps,
iteratively refining the SVM margin. We provide rigorous guarantees for
optimality and generalization, interpreting our algorithm as online
equilibrium-finding dynamics in a certain two-player min-max game. Evaluations
on synthetic and real-world datasets demonstrate scalability and consistent
improvements over related random features-based methods.