Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposed a unified framework to train the online federated MKL model for clients efficiently. The model combined random feature approximation with federated learning and proposed a novel personalized online federated MKL algorithm (POF-MKL), which adds a new perspective for MKL models to achieve higher communication efficiency with a solid theoretical guarantee. Experiments are provided to validate the theoretical claims.
strengths_and_weaknesses: Pros:

1. The proposed method applied random feature approximation to select a subset of kernels, which added a novel perspective to achieve high communication efficiency and real-time approximation.

2. Compared with existing online federated MKL algorithms (eM-KOFL and vM-KOFL), this paper proposed a personalized federated MKL model based on a more scalable and adaptive pattern, where each client chose a subset of kernels and sent partial updates according to clients-server
communication bandwidth.

Cons/Questions:

1. The presentation in the experiments section is somewhat not well-structured. The writing could be improved by re-framing the description of results, giving the readers a more intuitive explanation, and reducing the citation of “Table 1”.

2. It would be interesting to see the performance of the real online learning tasks such as online regressions and time-series predictions.

3. It would be more convincing to provide the convergence time/speed of the proposed algorithm. 

4. It would be better to compare with more different online Federated MKL algorithms. For example, MK-OFL [1] also achieves the optimal sublinear regret bound and selects only one kernel for each client instead of a subset of kernels. What are the advantages when compared with MKOFL?

[1] Chae, J., & Hong, S. (2021). Multiple Kernel-Based Online Federated Learning. arXiv preprint
arXiv:2102.10861.

5. In line 276-277, there is no citation for each baseline, especially for OFSKL and OFMKL-Avg. Are they just two variations of the method Fed-OMD?
questions: It would be better to compare with more different online Federated MKL algorithms. For example, MK-OFL [1] also achieves the optimal sublinear regret bound and selects only one kernel for each client instead of a subset of kernels. What are the advantages when compared with MKOFL?

In line 276-277, there is no citation for each baseline, especially for OFSKL and OFMKL-Avg. Are they just two variations of the method Fed-OMD?
limitations: Limitation: see "Weakness".

negative societal impact: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers the problem multi-kernel learning in online and distributed settings. Given a set of preselected kernel, clients should decide a **personalized** allocation (denoted $\mathbf{w}$ in the paper) of the kernels in an online fashion with the goal of minimizing their cumulative regret.  The paper leverage random feature (RF) approximation to solve the problem if ``curse of dimensionality'' usually encountered in online kernel learning. The RF approximation parameters (denoted $\theta$ in the paper) are estimated **globally** across clients. In order to reduce the communication costs, at   time step $t$, each client selects randomly a subset  of kernels  according  to  a probability mass function that aims to give more importance to kernels with larger allocation factor $\mathbf{w}_{ik, t}$.  

The paper performs regret analysis, and proves that the each client achieves sub-linear regret with respect to the RF approximation of its best kernel in hindsight. Experimental results confirms the theoretical results and show the advantage of the proposed method in comparison to other online multi kernel federated learning methods.  


strengths_and_weaknesses: ## Strengths

The paper is overall well written and easy to follow. The proposed idea is relevant and the theoretical results are correct. 

## Weaknesses

### Originality and Related Work Discussion

**Reference [12] is not enough discussed.** &nbsp; The method proposed in [12] shares two similarities with POF-MKL. First, reference [12] uses RF approximation to handle  ``curse of dimensionality'' encountered in online kernel learning. Second, reference [12]  randomly  selects a subset of kernels to be communicated at every step in order to allow for a large  number  of  kernels to be  chosen  without  the  burden  of  communication  overhead. In this regard, this paper distinguishes itself from [12] by allowing clients to decide individually  the weights of each kernel, whereas, kernels' weights are global in [12]. Moreover the theoretical analysis is similar to the one performed in [12]. This discussion was not explicit in the paper and I think it will be useful if the similarities and differences with [12] were highlighted. 

**Related Work.** &nbsp; Personalized federated learning is a well studied field that is closely related to this paper. However, only four references ([3, 6, 18, 31]) on personalized FL are cited, and none of them is discussed. As mentioned above, the main contribution of the paper (in comparison with [12]) is that it allows for kernel weights to be personalized for each client; it is therefore to discuss in more details  personalized FL literature. Moreover, the idea of learning personalized weights of globally learnt base functions was previously proposed in (Marfoq el al., 2021).

### Technical soundness

**Notation.** &nbsp; The notation is sometime misleading and makes some parts of the paper hard to follow. For example:

* The notation $\hat{f}_{RF, it}$   hides the dependence  on $\Theta$ 

* $\Theta_{t}$ is used to denote two different quantities: in line108, it is used as $\Theta_{t}=[\alpha_{1,1}, \dots, \alpha_{K,1}, \dots, \alpha_{1, t}, \dots, \alpha_{K,t}] \in \mathbb{R}^{tK}$, while in line 156, it is used as $\Theta_{t}=[\theta_{1, t}, \dots, \theta_{N,t}] \in \mathbb{R}^{D \times N}$ 

* Problem (1) should be formulated without $\Theta$ and $\mathbf{w}$ as $\min_{f\in \mathcal{H}}  \sum_{t=1}^{T}\sum_{k=1}^{K} \mathcal{L}(f(x_{k,t}), y_{k,t}) + \lambda \Omega(\left\||f\right\||^{2})$

**Theorem 2.** &nbsp; Although Theorem 2 is correct, it has few problems and can be improved. First,  The second term of the RHS of Eq. (14) is inversely proportional to $p_{i^{\*}k, t}$, which can be made arbitrary small when kernel $i^{\*}$ is not optimal for client k but is optimal for all other clients. Second, the coefficient $(1+\epsilon)$ in the first term of the RHS of Eq. (14) is not needed. This coefficient appears in Eq. (41) as a result of using the bound $\sup_{x, x'}|z_{i}^{\intercal}(x)z_{i}(x')| \leq 1 + \epsilon$; however one can simply use  $\sup_{x, x'}|z_{i}(x)^{\intercal}z_{i}(x')| \leq 1$, as the functions $\sin$ and $\cos$ are bounded by $1$. Finally, in the context of this work, I think it would be better to report the bound of the local regret defined with respect to the optimal local predictor at each client. This can be obtained as a corollary of Theorem 1 and Theorem 2.

P.S.: *The assumption that each data sample is bounded (line 227) is not needed.*


## References 
Marfoq, O., Neglia, G., Bellet, A., Kameni, L., & Vidal, R. (2021). Federated multi-task learning under a mixture of distributions. Advances in Neural Information Processing Systems, 34, 15434-15447.



questions: * For Theorem 2 to make sense, it is crucial to have a lower bound on $p_{i^{\*}k, t}$, or  to show that this term can not get arbitrary close to zero. I will raise my score if this issue is solved.  

### Post rebuttal
The authors have partially addressed my concerns, I increase my score. 
limitations: No the authors did not discuss negative societal impact of their work, and I do not think such discussion is needed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed a novel personalized online federated MKL framework (named POF-MKL) based on RF approximate. In particular, each client updates a subset of kernel parameters to alleviate computational complexity and achieve communication efficiency. Theoretical analysis shows the proposed method achieves sub-linear regret.

The authors empirically evaluated the proposed method on several datasets and it seems that the proposed method exhibited impressive performance and outperformed the baseline methods.

The main contributions of the paper include:

- Proposing the personalized federated MKL method to tackle the heterogeneous in federated learning.
- Proving the convergence rate of the proposed algorithm.
- Saving communication cost compared to existing algorithms, both theoretically and experimentally.
strengths_and_weaknesses: Prons:

1. The paper is technically sound and, for the most part, well-written, with the authors' motivations and explanation of the method conceived quite straightforward. 
2. The method has a convergence guarantee.
3. The authors also clearly emphasise their contribution and their novelty.
4. The results are convincing and show quite some promise.

Cons:

1. It would be better if the authors can provide some complexity analysis of the proposed algorithm and compared methods.
2. It would be better if the authors can add high-level intuition to help readers better understand the method section. 
questions: 1. I am curious to know how to consider the case when only a subset of clients participated at every iteration in online federation learning. Would it have an impact on convergence ?
2. I would like to know how equation 7 is derived.
limitations: N.A.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Current federated multi-kernel learning algorithms face challenges from high communication efficiency and heterogeneous data. This paper proposes a personalized online federated multi-kernel learning to overcome these challenges. Random feature approximation is used to improve the communication efficiency and the kernel subset selection is applied to achieve personalization. The theoretical analysis gives the upper bound of the regret for both the individual clients and the server. Numerical simulations are provided to show the effectiveness of the proposed algorithm.
strengths_and_weaknesses: Strengths
- The paper applies the random feature approximation and the kernel subset selection to achieve a personalized online federated multi-kernel learning algorithm. And numerical simulations show the advantages over other federated multi-kernel learning algorithms.
- The theoretical analysis is solid and supports their proposed algorithm well.

Weaknesses
- Random feature approximation was used in the online federated multi-kernel learning algorithm. The core contribution is that the paper achieves personalization via kernel subset selection. One may think the contribution is not very large.
- The literature review and comparisons are not enough. Since the paper focuses on personalized federated learning, the authors should cite and compare their algorithm with other personalized federated learning papers in the absence of multi-kennel learning.
- Experiments for other datasets should be added. In federated learning, it’s usual to compare different algorithms in datasets like MNIST, FMNIST, CIFAR-100, and even IMAGENET. The current datasets have small features.	
questions: - Please explain how to choose the dictionary of kernels for different tasks.
- Does the regret have a lower bound? If so, can it show the optimal of the proposed method?
- What are the advantages and disadvantages of multiple-kernel learning compared with deep learning? Please explain why the paper uses multiple-kernel learning to achieve personalized online federated learning.

limitations: Yes
review_title: null

Meta-review: metareview: The authors carefully designed the algorithm and presented their results.
The reviewers commented on the analysis of running costs, discussion on related works, and experimental comparisons.
The authors, as far as I can see, have addressed these appropriately.
The reviewers did not respond to the updates, but the scores should be increased, and I have included them in my decision.
confidence: Less certain
Decision: Accept