Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper derives generalization bounds for the sparse multi-kernel Support Vector Machine (SVM) problem. Recall that previous literature has focused on sparse multi-kernel problems, but only for the Ridge regression (square loss instead of hinge loss), or on multi-kernel SVM but without the sparsity inducing penalization. To do so, the authors introduce a new penalization, see Equation (5). Under some assumptions already used in previous works, excess risk bounds and estimation error bounds are derived (Theorem 1), further explicited in terms of the eigendecay of the kernel (Corollary 1). Bounds on the classification error are also provided (Theorem 2).
main_review: Although I do not question the technical quality of the present submission, I feel that authors fail at conveying a clear message that would benefit the Neurips audience. Among the main criticisms:

- the scope of the paper appears to be relatively restricted, as only the hinge loss is studied
- I might have missed something, but I cannot see why penalizing $||f_m||_n$ makes $\hat{f}$ sparse. As far as I understand, the proposed penalization is some kind of mixed norm (up to the regularization parameters $\lambda_m$ and $\gamma_m$), whose outer norm is $||\cdot||_1$ and inner norm is $\sqrt{||\cdot||_n^2 + ||\cdot||_K^2}$. By the $\ell_1$ outer norm, the solution to (5) contains many components $f_m$ with null inner norm, which means $||f_m||_n^2 + ||f_m||_K^2 = 0$, or again $f_m = 0$ as $||f_m||_K^2 = 0$. But I cannot see where is the impact of $||\cdot||_n$, as we can have $||f||_n = 0$ but $f \ne 0$. Am I missing something here?
- moreover, problem (5) is solved with penalization AND norm constraints (the optimization is carried out on $B_M$). Usually one of the two is chosen but not both at the same time. Is there a particular reason? Overall, I feel this penalization could have been better introduced and motivated, as it is far from natural from the current reading
- another point which is not discussed at all by the authors is the optimization of criterion (5). I think this aspect is very relevant for the Neurips community, and should not be omitted. A better theoretical objective which is impossible to minimize in practice would attract less interest. On the contrary, if the optimization of (5) is simpler than previous algorithms, this is definitely something that should be mentioned
- the bounds feature constants that are not explicited (e.g., $C_0, C_1$), making them harder to interpret. In addition, criterion (5) involves a lot of hyperparameters ($\lambda_m, \gamma_m$), to the extent that it is difficult to extract a clear and direct message from the Theorems, nor to determine how the new penalization was key. The comparison in Section 3.3 is however useful.
- the experiments are very basic and do not present any benchmark

Minor comments:
- l. 12: has bec*o*me
- l. 24/32: the acronyms DC and RKHS are never defined
- throughout the paper, authors keep referring at future equations, sections, which makes the reading incomfortable
- l. 43: not clear around citation [46]
- l. 100-101: RKHSs *are* known
- l. 156: we *knew*
- l. 200: increase*s*
- l. 254: *in this paper* twice
- l. 323: improve on previous

Overall, I think the present contribution is below the NeurIPS acceptance bar: better motivation/intuition/interpretation of the results seem needed, as well as a more in depth study of the algorithmic and empirical aspects.

**Post-rebuttal edit**

I thank the authors for their response, which addressed most of my concerns. Incorporating these comments into the submission (to the extent it is possible with the page limit) would be helpful I think. I won't oppose acceptance and have increased my score to 6 accordingly.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper consists of a theoretical analysis for bounds on the excess risk and estimation of SVMs in a sparse MKL setting.
Although the analysis is established for a larger class of combination of kernels with the Hinge loss, the derived bounds improve over existing ones, in terms of rates and dependency on the number of kernels, even in the more restrictive additive and linear cases and despite being adaptive to the unknown true sparsity.
It is worth noting that the analysis relies on the miniminization of the SVM problem with a specific penalty term that is slightly different from the ones used in previous work.
After deriving those theoretical results and comparing them to related work, the authors also provide some numerical experiments on simulated data whose generative process ensure that the true sparsity of the kernel combination is controlled.
The experimental results seem to closely verify the theoretical findings.
main_review: First of all, I want to acknowledge that I am not an expert reviewer for this submission.
Despite having contributed on MKL and in learning theory a long time ago, I have been mostly unaware of any development in the last decade or so.
Specifically, despite some efforts, I am not very confident about my ability to check the corectness of the proofs (although I could not spot any mistake).
Perhaps more importantly, I find myself to be struggling to carefully interpret or comment on the assumptions that are made to derive the analysis, despite efforts from the authors to relate them to assumptions that are made in related work.

I find the paper to be remarkably well-written (despite a few typos and mistakes I'll list later), and relatively easy to follow despite the technicality of the contributions.
Especially, the efforts made to write the proofs should be noted, especially as the proofs are "only" provided in the appendix.
I only have a few remarks or questions:
1) It is not clear to me how much the improvements over the existing results are specifically due to the choice of this peculiar penalty term. For instance, it would be nice to see whether the use of penalty terms that have been more classically used in the literature lead to slower convergence in the experimental setting used here.
2) Although it is mentioned that the chosen penalty term can "easily lead to a single adaptive group Lasso by the Cholesky decomposition", there is not any other comment about the algorithm, or computational complexity of solving problem (5). Can the authors comment? Or does it compare to formulations more commonly used?
3) Related to those last points, even if using that penalty term really improves the excess risk convergence in practive (beyond making this tighter analysis possible), can the authors comment on whether there is an interest for practioners to adopt (5)? More specifically, do you have any insight whether the (perhaps) faster empirical rate "compensate" for the higher computational cost induced by solving (5) rather than more computationally amenable formulations?

Here are some typos / mistakes I noticed in the paper:
- l.6: "and" was used twice
- l.174 "there existS"
- l.246 "multi-kernel cLAss", "From *a* model selection POV"
- l.254 "in this paper" was used twice
- l.259 "the popularity of sparse MK classification *is* mainly due"
- l.308 "from randomly choosING"
- l.323 "significantly improvE"

Last, I think recalling the theorems / propositions before exposing their proofs in the appendix would improve even further the ease of the reader.
limitations_and_societal_impact: Despite some comparison to related work, the limitations of this work have not been very deeply addressed. Addressing some of the remarkes I wrote in my main review would maybe improve that a bit.
There was no mention of potential negative societal impact but I am not sure that contribution in statistical learning theory have so much.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new sparse multi-kernel SVM which utilizes a mixed L-2 norm to enforce the sparsity and a RKHS-norm to enforce smoothness, and theoretically analyzes the estimation bound and excess risk. Finally, the numerical experiments are also performed in this paper.
main_review: Although the paper show that the proposed new formulation of the sparse MKL SVM enjoys better learning rate, it seems difficult to optimize due to the $\sqrt{}$ operator in regularization. Thus, to achieve the same generalization performance, few examples are needed, but maybe more computation time will be spent on optimization. On the whole, the new formulation does not bring too many benefits.

The experiments are performed on synthetic data, it seems better to show more results on real world data.

======================

Since the response has addressed my main concerns, I raise my score to 7.

limitations_and_societal_impact: No efficient optimization method will hinder the usage in practice.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper focus on the theoretical analysis of SVM with sparse multi-kernel approximation, where the total number of kernels may be larger than the sample size. More specifically, the refined bounds for the excess risk on multi-kernel SVM are provided, including high-dimensional linear or additive classification as special cases. The oracle rates of convergence of classifiers depend on the complexity of multi-kernels, the sparsity, the Bernstein condition and the sample size, which significantly improves the previous results even for the additive or linear cases.
main_review: In this paper,  a refined excess risk bound depends on the complexity of multi-kernels, the sparsity, the Bernstein condition and the sample size is provided, which significantly improves the previous results even for the additive or linear cases.  The oracle rate of the relative misclassification error is established, which consists of the same rate as the excess risk of the estimator plus some additional sparse approximation error. Many existing results can be incorporated as special cases of MKL for SVMs, so several existing results can be improved by the derived results. Moreover, the paper not only provides unified theoretical results for multi-kernel SVMs, but also enriches the literature on high-dimensional nonparametric classification. At last, the experiments on simulated data for SVM with sparse multi-kernel validate the theoretical findings.

In my opinion,  these results seem very interesting and important: the paper not only provides unified theoretical results for multi-kernel SVMs but also enriches the literature on high-dimensional nonparametric classification. Overall, I think this is a good theoretical and well-written paper, which is clearly of interest for the machine learning community.


limitations_and_societal_impact: Here are some concerns:
1. It would be better to briefly give the sketch of the proof in the main body, especially some important lemma. For example, in Theorem 1 (Line 204), the paper claims "A, C0 are positive constants specified in Lemma 1". However, Lemma 1 only appears in Appendix and is not provided in the main body.
2.  It would be better to give a table to clearly depict the advantage compared with the related results: such as single kernel learning, multiple kernel learning and high-dimensional learning.
3. Some notations should be explained after their first appearance.  For example, in the equation after Line 108, what does the operator $\wedge$ means? In Eq.(6), what does $\mu_{l}^{(m)}$ means?
4. The font size in Figure 1 is too small to be readable.
review_title: null

Meta-review: All reviewers have praised the quality of the paper (both substance and form) and acknowledged their appreciation of the responses made by the authors to their comments. This is a clear accept, with an expectation from the authors to do their best to incorporate as much as the insightful comments they provided in the feedback into the main text.


Decision: Accept (Spotlight)