Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
review_title: Solid submission but the authors overclaim their contribution

final_score: rating: 7: Good paper, accept
review_content: The paper proposes to learn a custom translation or rotation invariant kernel in the Fourier representation to maximize the margin of SVM. Instead of using Monte Carlo approximation as in the traditional random features literature, the main point of the paper is to learn these Fourier features in a min-max sense. This perspective leads to some interesting theoretical results and some new interpretation. Synthetic and some simple real-world experiments demonstrate the effectiveness of the algorithm compared to random features given the fix number of bases.

I like the idea of trying to formulate the feature learning problem as a two-player min-max game and its connection to boosting. As for the related work, it seems the authors have missed some very relevant pieces of work in learning these Fourier features through gradient descent [1, 2]. It would be interesting to compare these algorithms as well.

[1] Zichao Yang, Marcin Moczulski, Misha Denil, Nando de Freitas, Alex Smola, Le Song, Ziyu Wang. Deep Fried Convnets. ICCV 2015.
[2] Zichao Yang, Alexander J. Smola, Le Song, Andrew Gordon Wilson. A la Carte — Learning Fast Kernels. AISTATS 2015.
review_title: Interesting paper on kernel learning and random features

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
In this paper, the authors proposed an interesting algorithm for learning the l1-SVM and the Fourier represented kernel together. The model extends kernel alignment with random feature dual representation and incorporates it into l1-SVM optimization problem. They proposed algorithms based on online learning in which the Langevin dynamics is utilized to handle the nonconvexity. Under some conditions about the quality of the solution to the nonconvex optimization, they provide the convergence and the sample complexity. Empirically, they show the performances are better than random feature and the LKRF. 

I like the way they handle the nonconvexity component of the model. However, there are several issues need to be addressed. 

1, In Eq. (6), although due to the convex-concave either min-max or max-min are equivalent, such claim should be explained explicitly. 

2, In the paper, there is an assumption about the peak of random feature "it is a natural assumption on realistic data that the largest peaks are close to the origin". I was wondering where this assumption is used? Could you please provide more justification for such assumption?

3, Although the proof of the algorithm relies on the online learning regret bound, the algorithm itself requires visit all the data in each update, and thus, it is not suitable for online learning. Please clarify this in the paper explicitly. 

4, The experiment is weak. The algorithm is closely related to boosting and MKL, while there is no such comparison. Meanwhile, Since the proposed algorithm requires extra optimization w.r.t. random feature, it is more convincing to include the empirical runtime comparison. 

Suggestion: it will be better if the author discusses some other model besides l1-SVM with such kernel learning. 

review_title: interesting work but need more comparison

Meta-review: New effective kernel learning methods are very well aligned with ICLR's focus on Representation Learning. As a reviewer pointed out, not all aspects of the paper are algorithmically "clean". However, the proposed approach is natural and appears to give consistent improvements over a couple of expected baselines. The paper could be strengthened with more comparisons against other kernel learning methods, but acceptance at ICLR-2018 will increase the diversity of the conversation around advances in Representation Learning.
Decision: Accept (Poster)