Published as a conference paper at ICLR 2018 NOT-SO-RANDOM FEATURES
We propose a principled method for kernel learning, which relies on a Fourieranalytic 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.
In this paper the authors consider learning directly Fourier representations of shift/translation invariant kernels for machine learning applications. They choose the alignment of the kernel to data as the objective function to optimize. They empirically verify that the features they learned lead to good quality SVM classifiers. My problem with that paper is that even though at first glance learning adaptive feature maps seems to be an attractive approach, authors' contribution is actually very little. Below I list some of the key problems. First of all the authors claim in the introduction that their algorithm is very fast and with provable theoretical guarantees. But in fact later they admit that the problem of optimizing the alignment is a non-convex problem and the authors end up with a couple of heuristics to deal with it. They do not really provide any substantial theoretical justification why these heuristics work in practice even though they observe it empirically. The assumptions that large Fourier peaks happen close to origin is probably well-justified from the empirical point of view, but it is a hack, not a well established well-grounded theoretical method (the authors claim that in their experiments they found it easy to find informative peaks, even in hundreds of dimensions, but these experiments are limited to the SVM setting, I have no idea how these empirical findings would translate to other kernelized algorithms using these adaptive features).  The Langevin dynamics algorithm used by the authors to find the peaks (where the gradient is available) gives only weak theoretical guarantees (as the authors actually admit) and this is a well known method, certainly not a novelty of that paper. Finally, the authors notice that "In the rotation-invariant case, where Ω is a discrete set, heuristics are available". That is really not very informative (the authors refer to the Appendix so I carefully read that part of the Appendix, but it is extremely vague, it is not clear at all how the Langevin dynamics can be "emulated" by a discrete Markov chain that mixes fast; the authors do not provide any justification of that approach, what is the mixing time ?; how the "good emulation property" is exactly measured ?).  In the conclusions the authors admit that: "Many theoretical questions remain, such as accelerating the search for Fourier peaks". I think that the problem of accelerating this approach is a critical point that this publication is missing. Without this, it is actually really hard to talk about general mechanism of learning adaptive Fourier features for kernel algorithms (which is how the authors present their contribution); instead we have a method heavily customized and well-tailored to the (not particularly exciting) SVM scenario (with optimization performed by the standard annealing method; it is not clear at all whether for other downstream kernel applications this approach for optimizing the alignment would provide good quality models) that uses lots of task specific hacks and heuristics to efficiently optimize the alignment. Another problem is that it is not clear at all to me how authors' approach can be extended to non shift-invariant kernels that do not benefit from Bochner's Theorem. Such kernels are very related to neural networks (for instance PNG kernels with linear rectifier nonlinearities correspond to random layers in NNs with ReLU) and in the NN context are much more interesting that radial basis function or in general shift-invariant kernels. A general kernel method should address this issue (the authors just claim in the conclusions that it would be interesting to explore the NN context in more detail).
To sum it up, it is a solid submission, but in my opinion without a substantial contribution and working only in a  very limited setting when it is heavily relying on many unproven hacks and heuristics.