Personalized Online Federated Learning with Multiple Kernels
Authors: Pouya M. Ghari
Yanning Shen
Venue: NeurIPS 2022 Accept (2022)

Abstract: Multi-kernel learning (MKL) exhibits well-documented performance in online non-linear function approximation. Federated learning enables a group of learners (called clients) to train an MKL model on the data distributed among clients to perform online non-linear function approximation. There are some challenges in online federated MKL that need to be addressed: i) Communication efficiency especially when a large number of kernels are considered ii) Heterogeneous data distribution among clients. The present paper develops an algorithmic framework to enable clients to communicate with the server to send their updates with affordable communication cost while clients employ a large dictionary of kernels. Utilizing random feature (RF) approximation, the present paper proposes scalable online federated MKL algorithm. We prove that using the proposed online federated MKL algorithm, each client enjoys sub-linear regret with respect to the RF approximation of its best kernel in hindsight, which indicates that the proposed algorithm can effectively deal with heterogeneity of the data distributed among clients. Experimental results on real datasets showcase the advantages of the proposed algorithm compared with other online federated kernel learning ones.

Personalized Online Federated Learning with Multiple Kernels
Pouya M. Ghari
Yanning Shen University of California Irvine yanningsQuci.
University of California Irvine pmollaebouci.co
Abstract
Multi-kernel learning (MKL) exhibits well-documented performance in online non-linear function approximation. Federated learning enables group of learners (called clients) to train an MKL model on the data distributed among clients perform online non-linear function approximation. There are some challenges in online federated MKL that need to be addressed: i) Communication efficiency especially when large number of kernels are considered ii) Heterogeneous data distribution among clients. The present paper develops an algorithmic framework to enable clients communicate with the server to send their updates with affordable communication cost while clients employ a large dictionary of kernels. Utilizing random feature (RF) approximation, the present paper proposes scalable online federated MKL algorithm. We prove that using the proposed online federated MKL. algorithm, each client enjoys sub-linear regret with respect the RF approximation its best kernel hindsight, which indicates that the proposed algorithm can effectively deal with heterogeneity of the data distributed among clients. Experi- mental results on real datasets showcase the advantages of the proposed algorithm compared with other online federated kernel learning ones.
Introduction
Kernel learning exhibits well-documented performance in function approximation tasks, while providing theoretical guarantees associated with different performance metrics, e.g. [48] 21 38)
In some cases, a group of learners aims at collaborating to perform function approximation without revealing their data. To this end, federated learning has been emerged as a crucial learning paradigm by enabling group of learners called clients to collaborate with each other by communicating with a Through this process, clients send model parameters and updates to the server without revealing their data. Upon receiving updates from clients, the server updates the model. Therefore, federated learning enables clients to perform kernel learning for function approximation. In this context, a server and clients collaborate with each other learn the optimal kernel. Furthermore, in some practical cases, clients may need to perform the function approximation in an online fashion while they are collaborating with the server to learn the kernel. For example, consider the case where clients may not have enough memory store data in batch. In addition, data samples may arrive in sequential manner such that clients are not able to perform the function approximation in batch form. There are major challenges in performing online kernel learning in federated fashion that need to be addressed:
central server to train centralized model 3 27 23
Communication Efficiency: Communication efficiency arises as a bottleneck in federated learning (see e.g. (25 37 19 16]). Specifically, limited clients-to-sers to-sevr communication bandwidth restricts
the number of parameters that can be sent from clients to the server.
Heterogeneous Data: The distribution of data observed by client might be different from others
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(see e.g. |44 29 6)). Thus, the optimal kernel that is aimed to be learned is different across clients. Computational Complexity: Clients should be able to perform function approximation fast enough in order to make a decision in real-time. Therefore, the computational complexity of kernel learning methods should be affordable for clients.
suffer from 'curse of dimensional- ity' 3 in the sense that the number of parameters that should be learned increases with the number of observed data. This can make employing conventional online kernel learning approaches infeasible to perform online federated kernel learning since clients may be required to send a large number of parameter updates to the server while the available clients-to-serye not enough for sending such information. Approximating kernels by Unite-dimensione representations (e.g. Nyström method 49) and random feature method of (361) makes online kernel learning approaches scalable in the sense that the learner can choose the number of parameters that should be learned, independent of the number of observed data samples (see e.g. 30 4 (22))
Conventional online kernel learning approaches (see c.g. 21 39)
communication bandwidth
feature
Employing finite-dimensional feature representations of kernels to perform online federated kernel learning, clients can choose the number of parameters that they should send to the server. Therefore, finite-dimensional kernel approximation can better cope with limited clients-to-server communication bandwidth compared to conventional kernel learning approaches. Random feature (RF) approxima- tion (36] has been exploited to perform online federated kernel learning when a single pre-selected kemee function is employed (6 17]. The choice of the kernel function greatly affects the performance of function approximation when it comes to exploiting only a single kernel function. Employing multiple kernels instead of single pre-selected one, can lead to obtaining more accurate function approximation since multi-kernel learning (MKL) can learn combination of kernels (24). Online federated MKL algorithms with theoretical guarantees called vM-KOFL. and eM-KOFL. have been proposed in [22]. However, eM-KOFL. and vM-KOFL do not provide personalized MKL models for clients since they learn the same combination of kernels for all clients.
The present paper proposes a novel personalized online federated MKL algorithm called POF-MKL that provides personalized MKL model for each client while it is ensured that the available clients- to-server communication bandwidth can afford communication cost of sending clients' updates to the server. In order to alleviate the communication cost of MKL, the propsoed POF-MKL employs RF approximation of kernels and at each time instant, each client chooses a subset of kernels to send their updates to the server instead of sending the updates of all kernels. The number of kernels in the chosen subset is selected such that the required bandwidth to send all clients' updates does not exceed communication bandwidth. Therefore, clients can send their updates
the available dlients-to-seree to the server independent of the number of kernels in the dictionary and as a result a comparatively large dictionary of kernels can be considered to perform function approximation. Contributions of the present paper can be summarized as follows:
el. Leveraging the proposed POF-MKL, clients can update a subset of kernels' parameters which alleviates computational complexity and communication cost of sending updates to the server; c2. Through theoretical analysis, is proved that using the proposed POF-MKL, each client achieves sub-linear regret with respect to RF approximation of the best kernel in hindsight associated with the corresponding client data samples (c.f. Theorem T.. Moreover, it is guaranteed that the server achieves sub-linear regret with respect to the best function approximator (c.f. Theorem [
c3. Experiments on real datasets showcase the effectiveness of the proposed POF-MKL compared to existing online federated kernel learning algorithms.
2 Problem Statement and Preliminaries
Let there be a set of K clients performing function approximation task in an online fashion. The k-th client's goal is to learn the function í using the stream of data samples (( Mk.)) such that Lk, E Idd is the data sample observed by the k-th client at time t and yke is the label associated with Ty.t. In the kernel learning context, the function ff is assumed to belong to a reproducing kernel Hilbert space (RKHS). The present paper studies the personalized federated supervised function approximation problem
T K
min FEw Km
(1)
2

---

where IHI represents the RKHS the function f belongs to and [(,-) denotes the loss function which can be defined as
x))(=)))==(((())) + (
(2)
where -(:-)) is the cost function (c.g. least squares function for regression task), À denotes the regularization coefficient and (?(-) represents a regularizer function to prevent over-fitting and control the model complexity. Let θ be the global parameters of the function f which are learned through collaboration of clients with the server while ur be the personalized parameter of the function learned locally by the k-th client. Thus, the goal is that the cumulative difference between [ θ wx) and yk., over time minimized. At each time instant i, upon observing the data sample at,,, the k-th client make the prediction f( θ wa) and then observes the true label yk.t- Therefore, the function approximation problem that the server aims at solving can be expressed as min Σi= Σ (Z w,),, yk,,). Moreover, finding the local parameters wp by the k-th client can be expressed as the optimization problem min Σ ((f( O wx). Mss,e). In order to perform the function approximation task in an online fashion, the k-th client needs to perform the task with the values of @ and wy at time t denoted by O and uK.. respectively. Thus, the values of
function parameters @ and wy should be updated "on the fly'. Since the function f(;;,) belongs
reproducing kernel Hilbert space (RKHS), based on the representer theorem 48
given data
samples, the optimal solution for (I can be obtained as
K
) =
Σ
Σ aK,KK( xk.c)
(3)
where <(.,)) :) denotes symmetric positive definite kernel function such that k(xr, æ²) measures the similarity between and n'. And ore,t an unknown coefficient associated with k( ax,,)) which is required to be estimated. In this case, f()) in (3) belongs to the RKHS H. = (f())) =
Ee Ek=1 k=1 Ck,ck( xx, xb } such that RKHS norm is defined |l := E. Ex agay K (z,, (v). Therefore, the number of coefficients {0 Vk that should be estimated to obtain f(-) increases over time. This known as curse of dimensionality (48) since the computational complexity function approximation increases with time. This brings challenge for federated implementation of function approximation since dimension of updates that should be sent to the server by each client grows over time and when 7' is large, the available communication bandwidth may not be enough for clients to send their updates.
Furthermore, from (3) it can be inferred that O = [01,1, O..,I..... (e11--..,,,1,t:---.... x..,)..
In order to deal with the increasing number of unknown coefficients, one can employ random Fourier approximation [36). Assume that x(-) is shift-invariant kernel meaning that ((x,2²) = s(x x²). Let TT denotes the Fourier transform of k(.). If the kernel function k(-) is normalized such that x(0) = 1, then n (p) can be viewed as probability density function (PDF) (see e.g. (36)). Let Pi...., PD be a set of D independent and identically distributed (i.i.d) vectors drawn from T.)()).
Let the vector zax) be defined as
z (
isin (pT x)..... sin((ninnn x), [
(4)
Then, (x x') = x<x)² T 2<x') constitutes an unbiased estimator of x(a - x') and the random feature (RF) approximation of f(x) in (3) can be obtained as
[RF(#) ΣV Σ (( =(xx) = 0 z(x)
(5)
where in this case 0 = ΣT Σ (xx.) According to 4 (xxx,) is a 2D vector and as result it can be concluded that O is 2D vector well. Therefore, using RF approximation, the vector 0 should be estimated whose dimension does not grow over time.
The performance of kernel learning algorithm depends on the choice of the kemnl. Thus, per- forming the function approximation using a pre-selected kernel requires prior information which may not be available. To cope with this, employing dictionary of kernels in lieu of a pre-selected
single kernel has been proposed in the literature (see e.g. 45 24 31). Specifically, the ker- nel is learned a combination of kernels in the dictionary.
be set of Let Kg (...).....
3

---

N kernels where k.(-) denotes the i-th kernel. The function R(-) belongs to the convex hull K == {m(x)) Σi= (,,s(()) (x),, Pr 2 O, Vi, Ei= multi-kernel learning, the goal is to learn the convex combination of kernels in the dictionary to minimize the cumulative regret with respect to the best function approximator in hindsight. The cumulative regret is defined as the cumulative difference between loss of the online multi-kernel learning algorithm and that of the best function approximator in hindsight. Furthermore, for dataset {(r,, yt 3e)][== the best function approximator is f-) E arg (iE Ei= L(J (mt), ( ye) where (.) E arg org Ei= (x:e), M/4) such that Hi, is an RKHS induced by s:(+) and [N] := fl...... N). Enabled by random feature approximation, centralized and scalable online multi- kernel learning algorithms have been proposed in literature (see e.g. 40] 43 [5] ) The present paper proposes an algorithmic framework for personalized online federated MKL using RF approximation of kernels in the dictionary.
1} is kernel 41 Therefore, in online
(iE[N]
3 Personalized Online Federated Multi-Kernel Learning
The present section proposes an algorithmic framework for online federated multi-kernel learn- ing which can deal with heterogencous data among clients. To perform function approxi- mation, RF approximations of kernel functions are employed. For the i-th kernel Kg, vec- tors Pi.l.-..;PP.D are drawn i.i.d from Te, (.) to construct the random feature vector (x 1 a ...., sin(p .)) x)), c))(p) Then, at time instant the random VD
feature approximation associated with Ka(-) can be obtained as fRF,((()) = (, where 0z.e is the global function parameter associated the i-th kernel at time L.
3.1 Algorithm
At each time instant t, the server transmits global function parameters o.,,, Vi E [N] to all clients. The k-th client, assigns the weight Wik, to the i-th kernel which indicates the confidence of the k-th client at time & in the function approximation given by the i-th kernel. Upon receiving new data sample The the k-th client performs the function approximation combining kernels' RF approximations as
N f( Wk,) Σ
Wike 0T, (xx,,)
Wiket
(6)
WE.1
We,t
where θ, = ......... N.) Wx.t [wis.e.......................... [N and WK.s = E Wike. As it can be inferred from (6). each client constructs its own personalized combination of kernels. Upon observing the true label yk.e. the k-th client calculates the losses [[]fFra(EEx. 0,,c). yl,,)). Vi E [N]. Then, the k-th client leverages calculated losses to locally update both global and local parameters. Let 0u. and W 1 denote the k-th client's local updates of 0z, and Wik, respectively. Specifically, the k-th client utilizes multiplicative update rule to update Wiket as
W1R.1+1 Wsk,r exp (-nA-(JRE (Zp,1 (..)) Vi E [N]
(7)
where 7) is the learning rate of the k-th client. Note that the k-th client (Vk E [K]) does not send its updated local parameter WR,++1 to the server. Clients send their locally updated global parameters to
the server (i.e. 1)) Aggregating local updates, the server updates global parameters to ② If all clients send updates associated with all kernels (i.e. Osk,441. Vi E [N]), this requires sending 2N D parameters by each client at each time instant. When the number of both clients and kernels are large, the available client-to-serve sending 2N DK parameters per time instant even for small values of D. Note that reducing N and D degrade the performance of online federated MKL. Reducing N (the number of kernels), decreases the flexibility of clients to construct their ideal kernel using convex combination of kernels in the dictionary. Reducing D can degrade the accuracy of RF approximation.
communication bandwidth may not be enough to afford
The present paper proposes an algorithmic framework to enable clients to perform online function approximation with sufficiently large dictionary of kernels while the available clients-to-serve communication bandwidth can afford sending updates from clients the server when a desirable value for the number of random features D is chosen. To this end, at each time instant, each client

---

Algorithm 1 The k-th client kernel subset selection at time I.
Input:Weightss wis.t. Vi E [N]], parameter M and exploration rate 0 < EN I. Sort the kernels in descending order with respect weights {wiRa)i= i=11
Obtain the index sequence ..,...: &N such that Wayket S W,a if b > a, Va, b E [N].
Open bin B1 and initialize j=
for all i E [A]] the k-th client do if the bin Bj includes less than M kernels then
Adds the s,-th kernel to By.
else
Opens new bin Bj+1, adds the s,-th kernel to By+1 and updates j + j ++) 1.
end if
end for
Draw an index JR.. via PMF qk.t in 8
Output: SE,: indices set of kernels in the selected bin Big
randomly chooses a subset of M kernels among all N kernels in the dictionary. Then, each client updates and sends the global parameters of the chosen M kernels to the server instead of updating and sending global parameters of all kernels. To choose a subset of M kernels, each client splits kernels into some bins and draws randomly one of the bins at each time instant. Each bin contains at most M kernels and each client updates and sends global parameters associated with kernels in the chosen bin. In order to distribute kernels among bins, at first the k-th client sorts kernels in descending order according to kernels' weights { ? N Let B, represents the j-th bin of kernels. The k-th client adds kernels from sorted list one by one to B3 until either all kernels are assigned to bin or the number of kernels in B3 reaches M. When there are some kernels that are not assigned to any bins while there are M kernels in By. the k-th client opens the bin Bj+1 1 and adds kernels to this bin. This continues until all kernels are assigned to bin. As it can be inferred from the procedure of distributing kernels into bins, the number of bins at every client is can be concluded that B3 includes M kernels with the largest weights while the bin B,, includes N (m 1)M kernels with lowest weights. The k-th client assigns the weight uyk, at time to B, defined as Ujkk, = En,e,, Wik,r. The k-th client draws one of the bins according to the probability mass function (PMF) qu.t defined as
1 Furthermore, it
Gihtt = (1- Ex)
Uikkt UR.t
+ m
EN Vj [m]
(8)
where Uk,t= = -
Ujk,r and 0 <x S. is an exploration rate determined by the k-th client. Let Tr.e be the index of the chosen bin by the k-tth client at time The PMF in (8) constitutes trade-off between exploitation and exploration. According to the first term in the right hand side of (8). it is more probable that the k-th client draws bin which includes kernels with larger weights w.k. Hence, it is more probable that the k-th client collaborates in updating the global parameters of kernel with larger weight wik.r. Let Sy.t denotes the set which includes the indices of kernels in the chosen bin at time t. The Algorithm summarizes the procedure that the k-th client determines the set SR,t- According to Algorithm kernel subset selection personalized since each client chooses its own subset of kernels to update their parameters.
Let PaR.a denotes the probability that i SR, Then Past Qb.k. where b; is the index of the bin which includes the i-th kernel. The k-th client updates global parameters locally as follows
0 0ktt+1 0 V
Wh.)) 1iESE,
Pik,t
where Ligst, denotes an indicator function and is 1 when E Sk,t. The update rule in ( implies that when i & Sk.e, the k-th client does not update o.,, (i.e. 0u..+11 = O,.)) Therefore, the k-tth client sends 0 to the server only if i E Sx,t- Therefore, at each time instant, each client needs to send most 2D parameters to the server. Let Ct,, be set of client indices such that & C,,, if the k-th client sends Out,e1 to the server. Upon aggregating updates from clients, the server updates O,,, as
VL(O
1, z, (xK,)), yk.c)
0 0,1+1 0i.
Σ (0..- 0..,411 = 0z,t REC..
17
Lies (10)
K
K
Pik.t
5

---

Algorithm 2 Personalized Online Federated Multi-Kernel Learning (POF-MKL)
Input:Kemells Kig 1, .,, N, learning rate di and the number of random features D. Initialize: 0,, = 0, Wik.1 = 1, vi E [M] Ak E [K].
fort= port=1..... do
The server transmits the global parameters θ, 10 ON, all clients. for all k E [K], the kth client do
Receive datum k
Predicts f(x i ,, wx,e) via 6
Calculates losses L( [k f,,t), Uke.)) Vi [M].
Updates Wik,t+11 Vi E [N] via 77.
Selects subset of kernel indices Sg,t using Algorithm
Updates 02.,4I, Vi E Sk.t via (9) and sends O2 V E Sk., to the server.
end for
The server updates 01,411, Vi [N] via 10P.
end for
Algorithm 2 summarizes the proposed personalized online federated multi-kernel learning algorithm called PKF.MKL. It useful to note that using our proposed POF-MKL, the server cannot find the gradients V =
yh,x) from updates received from clients. Instead, the server can find VC se (wx,.), vw.x)/Pi.. where P is time-varying value determined locally by the k-th client. This can promote the privacy of the proposed POF-MKL since exchanging the gradients can be hazardous to the privacy of federated learning (see e.g. [3
Complexity. Each client needs to store d-dimensional D random feature vectors for each kernel. Therefore, the memory requirement of each client implement function approximation using POF- MKL is Dd. Using POF-MKL, at each time instant, each client needs to perform ((dN D) operations including inner products and summations. Furthermore, when & < 1, order choose subset of kernels, the k-th client needs to sort kernels which imposes worst case computational complexity of (N log N). However, when ÇA 1, according to PMF (8) the k-th client chooses one bin uniformly at random and as a result in this case the k-th client does not need to sort kernels. Therefore, setting εu < 1, the computational complexity for the k-th client is O D + N log N) while setting & 1, the computational complexity of the k-th client at each time instant is OdN D).
3.2 Regret Analysis
The present section analyzes the regret of the proposed POF-MKL. Specifically, two types of regret RR.T and RR,7 are considered for the k-th client and the server, respectively. The performance of the k-th client utilizing POF-MKL is analyzed terms of regret defined as
T
R&T =
Σ Cl C(f(ax,) O, wk.)). Vk.)) min
Σ L(fee,0 0..). 9k.))
(11)
NE
where R&. measures the cumulative difference between the loss of the k-th client and the loss of the RF approximation of the kernel with minimum loss among all kernels" RF approximations. Let ai Vt. [T], Yk [K] represents the optimal coefficients associated with the i-th kernel
such that (z) ΣT Σ ai (x,, Tk.t). Then the best function approximator is defined as f*(+) E arg min ,E[N] EK L(f. (x s).,). Furthermore, the regret of the server is defined the cumulative difference between the loss of POF-MKL and that of the best function approximator over all data samples distributed among clients which can be expressed as
T
K
T K
R₂ =
ΣΣ [=
C(((x, Or wk.).
ΣΣ 1=
(12)
In order to analyze the regret of POF-MKL, suppose that the following assumptions hold true: (as1) 2(0,,, v..)). vk [K] is convex with respect to O.,, at each time instant L. (as2) For 0 in bounded set satisfying |||| < C. the loss function and its gradient are bounded

---

as 0 I ( yk.e) I 1 and |V (x,,e) Mk.1 S L. Moreover, each data sample is bounded as | 1, vk [K]. E [T].
(as3) Kernels Ki (.), vi E [N] are shift-invariant with (0) = 1, vi [N].
The following theorem investigates the regret of the k-th client according the k-th client data. The proof of the following Theorem can be found in Appendix A
Theorem 1. Under (as3), the regret of the k-th client with respect to the best kernel satisfies
T
NN
Σ C(f(zx,1i Or (...).ua))
min iE[N]
C(frr O..)) Vk.e)
+
T.
(13)
2
1=1
the k-th client achieves sub-linear regret of ((VT). Furthermore, Theorem shows that POF-MKL can deal with heterogeneous data among clients since the regret of each client defined in (TT) is calculated with respect to the corresponding client data. The following theorem studies the regret of the server with respect to the best function approximator. The proof can be found in Appendix B
Theorem shows that by setting 7 O
VT
Theorem 2. Let i* == arg min EiT1
Ek= (2x,)) wk.e and as be the second Fourier moment of the i-th kernel. Under (asl (as3), the regret of the server with respect to the best function approximator satisfies
T
K
T
K
C(f(a O,, wk.e),
E( (D.,)).
R=1
KC²
7
T
K
K
In
T
+ ELKTC
(14)
2m
2
Pirk,t
2
t=1
k=1
k=1
with probability at least 1
28
exp
4(d
Dea
K where C' max E 2k=1 Ouee
As it can be inferred from 14, the regret of the server with respect to the best function approximator
depends on P'" From (8 and the fact that Pik.t Kb,k,r, it can be concluded that ki Ea. Thus,
setting Ex (1), then Pik,t 0 M). The regret bound in (14) shows that setting 7) O
M
NT
Vk E [K], the server obtains regret of O (V V/Nn TT)
and 6 = 1k = VT
with probability at least
1 28
51 exp
D22 This shows that increasing M tighten the regret bound and increasing 4(d++2
D increases the probability that the regret bound in (4] holds true. However, using POF-MKL, each client needs to transmit M parameters at each time instant. Since both M and D are determined by the algorithm POF-MKL, this shows that POF-MKL can provide flexibility to tighten regret bound while the available clients-to-server communication bandwidth can afford transmission of clients' updates to the server. bound of ka and as a result the optimal choice for & in terms of regret is & 1. However, choosing smaller values for & makes the value of Pik.t more dependent on weights {wak, ) fc.f. Therefore, choosing smaller values for Es makes Pik,t less predictable. This makes estimating [L(0,,=((r..)) w).t)) given VL(O,,,z Me.t) pact more difficult which leads to better protection of privacy.
useful to mention that choosing larger value for &a increases the lower
Comparison with personalized federated learning. In order to deal with heterogeneous data among clients, personalized federated learning has been studied extensively in the literature (see 20
44
8 12
10
29
28
42
6 32 50 46 3. Utilizing model-agnostic meta-learning [3]
5 personalized federated learning algorithms have been designed by learning heper-networks [8]. In [32,
personalized federated learning algorithms have been proposed in 12 In 42
personalized model is linear combination of set of shared component models such that each client constructs its personalized mixture of models. However, aforementioned personalized federated learning works, clients are assumed to store dataset to perform local updates with. Therefore, when clients are not able to store data in batch and they have to make decision upon receiving new data sample, aforementioned works in personalized federated learning cannot guarantee sub-linear
7

---

regret for clients. However, according to Theorems I and 2 POF-MKL provides sub-linear regret for clients when clients cannot store data in batch and make decision in an online fashion.
Comparison with online federated learning (34.. Fed-OMD algorithm has been proposed in [34] which enables clients to perform their learning task in an online and federated fashion while it proved that Fed-OMD enjoys sub-linear regret when the loss function is convex with respect to parameters required to be learnt each time instant. The proposed POF-MKL differs from Fed-OMD in the sense that Fed-OMD cannot guarantee sub-linear regret when it comes to performing the online learning
task with RF approximations of multiple kernels since the loss function <(E 1= Wi.0 , (x)) y) is not convex with respect to both f,. and we,c- However, according to Theorems) and 2 POF-MKL guarantees sub-linear regret.
the proposed
Comparison with [22]. Online federated MKL algorithms called vM-KOFL and eM-KOFL have been presented in [22]. Both POF-MKL and algorithms in [22] exploit random feature approximation to alleviate computational complexity of online kemnel learning. Furthermore, both POF-MKL and algorithms in [22] learn linear combination of kernels. The proposed POF-MKL has the following advantages and innovations compared to KM-KOFL and eM-KOFL: i) The proposed POF-MKL allows clients to learn their own personalized combination of kernels (c.f. ()). As it is proved in Theorem [ the proposed POF-MKI. can deal with heterogeneous data among clients in the sense that using POF-MKI. each client guarantees sub-linear regret with respect to the best kernel RF approximation according to the corresponding client data. However, both vM-KOFL and cMFL are not able to provide such guarantee. ii) Using VM-KOFL, each client needs to send (N + 1)D parameters to the server. However, using the proposed POF-MKL, each client needs to send M parameters to the server such that M S N is determined by POF-MKL and can be chosen to be much smaller than N. iii) In KOFL, the server chooses a kerne at each time instant and clients send their local updates associated with the chosen kemel by the server. The proposed POF-MKL provides more flexibility compared to eM-KOFLL in the sense that using POF-MKL each client can send local updates of M 2 kernels the server. And each client chooses its subset of kernels to send their updates to the server. Therefore, even though POF-MKL. sets M to 1, it is possible that time instant the server receives updates associated with all kernels in the dictionary. It is useful to mention that using eM-KOFL the cumulative regret of all clients is sub-linear with respect to the best kernel RF approximation with probability --d 8 where 0 S 1. However, utilizing the update rule in (2). using the proposed POF-MKL, each client obtains sub-linear regret with respect to RF approximation of its best kernel with probability 1.
4
Experiments
We tested the performance of the proposed POF-MKL for online regression task through set of experiments. The performance of POF-MKL is compared with the baselines PerFedAvg [2], OFSKL
34.. OFMKL-AVg 34, vM-KOFL 2 and eM-KOFL [2] PerFedAvg refers the personalized federated averaging algorithm in [12. In the experiments, PerFedAvg employs fully connected feedforward neural network model. More information about the implementation of PerFedAvg can OFSKL and OFMKL-Avg are two variations of Fed-OMD (3.. OFSKL 34 when a single radial basis function (RBF) with bandwidth of 10 is employed
be found in Appendix C
leverages Fed-OMD to perform the learning task. In OFMKL-Avg, kernels are learned independently from each other and the prediction the average of approximations given by kernels. Moreover, vM-KOFL and eM-KOFL are online federated MKL algorithms of (22) such that vM-KOFL requires transmission of all kernel updates at every time instant while <M-KOFL requires transmission of a kernel update at each time instant. In the experiments, each client observes 500 samples until the end of the learning task meaning that T 500. The performance of the proposed POF-MKL and other baselines are tested on the following real datasets downloaded from UCI machine learning repository [I: Naval 7. UJI [47), Air (51) and WEC [35]. More detailed information about datasets can be found in Appendix C Data samples of Naval and UJI datasets are distributed i..dd among clients. Data samples in Air and WEC datasets are distributed non-i.i.d among clients. More inforamtion about distributing data samples among clients can be found in Appendix C The number of clients for Naval, WI, Air and WEC datasets are 23, 42, 240 and 560, respectively. The dictionary of kernels consists of 51 RBFs with different bandwidth such that the bandwidth of the i-th kernel is a; 10 2:-22 We consider the case where the diients-tossever communication bandwidth is limited such that at each time instant, the maximum number of parameters that a client is allowed to transmit to the server
using Fed-OMD 34
8

---

is 1000. Furthermore, the memory and computational capability of clients are limited such that the maximum value can be picked for the number of random features D is 100. The experiments were carried for 20 different sets of random feature vectors. The performance of algorithms is measured using average of mean squared error (MSE) defined as
20
K
1
MSE-
(5gk,t yke,)
20
where U5,, denotes the prediction of the k-th client at time instant t corresponding to the j-th set of random feature vectors. Learning rates are set to 1) 7/2- v vk. Also, exploration rates are set to
& = 1, vk. The performance of POF-MKL with different &a is studied in Appendix C Codes are available at
/tte:://ggtttuuu. com http//ooummmhhar.c 1/POF-
Table presents the MSE and run time performance of online federated kernel learning algorithms on real datasets. Run time refers to average total run time of clients to perform online learning task on the entire data samples that they observe. In Table I M refers to the number of kernels whose updates are sent to the server after prediction at each time instant. And, is the number of random features. Comparing MSE of POF-MKL with that of OFMKL-AVg. it can be concluded that learning the weights to combine kernels provides higher accuracy than averaging kernels' predictions. Table shows that POF-MKL with M 1 provides lower MSE than eM- Using eM-KOFL, each time instant, the server receives updates belong to only one kernel. However, using POF-MKL with M 1, 1, each client sends an update belongs to a kernel which selected by the client. Therefore, the server receives updates associated with different kernels even though M = 1. Therefore, experimental results show the effecttivneess of the personalized kernel selection provided by POF-MKL. It can be observed that POF-MKL with M = 25 obtains lower MSE than those of PÓF-MKL with M = 51 and vM-KOFL. Since each client allowed to send most 1000 parameters per time instant, clients send updates of all kernels at every time instant as this is the case in vM-KOFL., cannot be chosen to be greater than 9. However, setting M = 25, POF-MKL can set D 20 which can improve the accuracy of online regression task compared to the case where D 9. Note that according to Theorem [2] increase in increases the probability that the server achieves sub-linear
regret with respect to the best function approximator. Furthermore, POF-MKL with M = 51 achieves lower MSE than vM-KOFL even data samples are distributed i.i.d among clients. This shows that the proposed POF-MKL can better cope with heterogeneous data among clients which is in agreement with theoretical results in Theorem [ In fact. the optimal combination of kernels can be different across clients. Using POF-MKL, each client constructs its own personalized combination of kernels which results in lower MSE compared to VM-LOFL. The proposed POF-MKL with M = 1 and .M 25 runs faster than eM-LOFL. In fact, using POF-MKL, clients only need to update parameters associated with M kernels while employing VM-KOFL and eM-KOFL, clients have to update parameters of all kernels. Moreover, POF-MKL obtains lower MSE than PerFedAvg. Note that since clients are not able to store data in batch, at each time instant clients update PerFedAvg's model using only the newly observed data sample. Therefore, convergence of PerFed is not guaranteed. Experimental results show that POF-MKL achieves higher accuracy than PerFedAvg in online regression task when it is not possible for clients store data in batch. Since OFSKL employs only a pre-selected single kernel, OFSKL runs faster than POF-MKL. However, utilizing multiple kernels enables POF-MKL to obtain lower MSE than that of OFSKL. In fact, using POF-MKL clients learn a linear combination of kernels which is proved to enjoy sub-linear regret with respect to the best kernel in hindsight while employing OFSKL clients have to make predictions using a pre-selected kernel. Furthermore, Figure [ Iillustrates the average regret of clients when clients employ vM- MOFOLL and the proposed POF-MKL with different M parameters. From Figure [ it can be observed that the proposed POF-MKL achieves sub-linear regret.
5 Conclusions
The present paper proposed a personalized online federated MKL algorithm called POF-MKL based on RF approximation. Employing the proposed POF-MKL, each client updates the parameters of a subset of kernels which alleviates the computational complexity of the client as well as communication cost of sending updated parameters of kernels. Theoretical analysis proved that using POF-MKI, each client achieves sub-linear regret with respect to the RF approximation of its best kernel in hindsight which indicates that POF-MKL can deal heterogeneous data among clients. While each

---

Table 1: MSE(X 10 10-3)-000000 3) and run time of online federated learning algorithms on real datasets.
MSE( x 10 10
Run time(s)
Algorithms
M
D
Naval
UJI
Air
WEC
Naval
UJI
Air
WEC
PerfedAvg
118.60
63.03
13.68
77.33
44.59
41.67
37.40
33.56
OFSKL
100
77.77
61.82
13.65
87.87
0.07
0.06
0.08
0.06
OFMKL-AVg
51
9
33.25
55.44
10.63
34.01
1.51
1.73
0.91
0.47
vM-KOFL
51
9
26.42
51.50
10.58
25.17
2.01
2.22
1.37
0.67
cM-KOFL
1
100
28.64
61.08
21.94
20.14
2.27
10.13
1.45
1.70
POF-MKL
100
16.16
33.02
9.27
11.44
1.22
9.02
1.25
1.10
POF-MKL
25
20
16.82
37.34
9.34
11.58
0.69
2.29
0.63
0.52
POF-MKL
51
9
16.65
41.00
9.38
11.97
0.82
1.07
0.81
0.65
4-1
29
10a
Tra
(a) Naval dataset.
(b) dataset.
(c) Air dataset.
(d) WEC dataset.
Figure I: Average regret of clients.
client updates a subset kernels, was proved that the server achieves sub-linear regret with respect to the best function approximator. Experiments on real datasets showcased the advantages of POF-MKL compared with other online federated kernel learning algorithms.
Acknowledgement
This work is supported by NSF ECCS 2207457. PI Yanning Shen also receives support from Microsoft Academic Grant Award for Research. Contact: Yanning Shen grannings@uci.. uuc..edu).
References
[1] Durmus Alp Emre Acar, Yue Zhao, Ruizhao Zhu, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Debiasing model updates for improving personalized federated training. Proceedings of International Conference on Machine Learning, volume 139, pages 21-31, Jul 2021.
[2] Idan Achituve, Aviv Shamsian, Aviv Navon, Gal Chechik, and Ethan Fetaya. Personalized federated learning with gaussian processes. In Proceedings of International Conference on Neural Information Processing Systems, volume 34, pages 8392 8406, Dec 2021.
[3] Yoshua Bengio, Olivier Delalleau, and Nicolas L. Roux. The curse of highly variable functions for local kernel machines. In Advances in Neural Information Processing Systems, pages 107-114, May 2006.
[4] Pantelis Bouboulis, Symeon Chouvardas, and Sergios Theodoridis. Online distributed learning over networks in rkh spaces using random fourier features. IEEE Transactions on Signal Processing, 66(7):1920 1992-1999,, Apr 2018.
[5] Hong- You Chen and Wei-Lun Chao. On bridging generic and personalized federated learning for image classification. In International Conference on Learning Representations, 2022.
[6] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared rep- resentations for personalized federated learning. In Proceedings of the International Conference on Machine Learning, volume 139, pages 2089-2099, Jul 2021.
10

---

[7] Andrea Coraddu, Luca Oneto, Aessandro Ghio, Stefano Savio, Davide Anguita, and Massimo Figari. Machine learning approaches for improving caddition-basee maintenance of naval propulsion plants. Proceedings of the Institution of Mechanical Engineers, Part M: Journal of Engineering for the Maritime Environment, 236(1):13-1153, 2016.
[8] Luca Corinzia, Ami Beuret, and Joachim M. Buhmann. Variational federated multi-task learning, 2019.
[9] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning, 2020.
[10] Canh T. Dinh, Nguyen H. Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In Proceedings of International Conference on Neural Information Processing Systems, page 21394-21405, Dec 2020.
[11] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[12] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta- leataleenning approach. Advances in Neural Information Processing Systems, volume 33, pages 3557-3568, Dec 2020.
[13] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostie meta-learning for fast adap- tation of deep networks. In Proceedings of International Conference on Machine Learning, volume 70, pages 11 122--1355, Aug 2017.
[14] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients how easy is it to break privacy in federated learning? In Advances in Neural Information Processing Systems, volume 33, pages 16937-16947, 2020.
[15] Pouya M Ghari and Yanning Shen. Online multi-kemel learning with graph-structured feedback. In Proceedings of the International Conference on Machine Learning, volume 119, pages 3474 3483, Jul 2020.
[16] Pouya M Ghari and Yanning Shen. Graph-assisted communication--fficieee. ensemble federated learning. arXiv preprint arXiv:2202.13447,,20 2022.
[17] Vinay Chakravarthi Gogineni, Stefan Werner, Yih-Fang Huang, and Anthony Kuh. Communication-effioe efficient online federated learning framework for nonlinear regression. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2222,, May 2022.
[18] David Ha, Andrew M. Dai, and Quoc V. Le. Hypernetworks. In International Conference on Learning Representations, 2017.
[19] Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh. FedBoost: A communication- efficient algorithm for federated learning. In Proceedings of International Conference on Machine Learning, volume 1 119, pages 3973-3983, Jul 2020.
[20] Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and opti- mal algorithms for personalized federated learning. In Proceedings of International Conference on Neural Information Processing Systems, page 2304-234 2315- Dec 2020.
[21] Steven C. H. Hoi, Rong Jin, Peilin Zhao, and Tianbao Yang. Online multiple kernel classification. Machine Learning, 90:289-316, 6, Feb 2013.
[22] Songnam Hong and Jeongmin Chae. Communication-effieee randomized algorithm for multi-kernel online federated learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, Nov 2021.
[23] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Har- chaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara
11

---

Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mchryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-200, 2021.
[24] Marius Kloft, Ulf Brefeld, Sören Sonnenburg, and Alexander Zien. Lp-norm multiple kernel learning. Journal of Machine Learning Research, 12:953-997, Jul 2011.
[25] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency, 2017.
[26] Anthony Kuh. Real time kernel learning for sensor networks using principles of federated learning. Asia-Pacciti Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), pages 2089-2093, Dec 2021.
[27] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
(28) Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In Proceedings of International Conference on Machine Learning, volume 139, pages 6357-6368, Jul 2021.
[29] Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. FedBN: Federated learning on non-llI) features via local batch normalization. In International Conference on Learning Representations, 2021.
[30] Jing Lu, Steven C.H. Hoi, Jialei Wang, Peilin Zhao, and Zhi- Liu. Large scale online kernel learning, Journal of Machine Learning Research, 17(47):1 2016.
[31] Shaogao Lv, Junhui Wang, Jiankun Liu, and Yong Liu. Improved learning rates of a functional lasso-type svm with sparse multi-kernel representation. In Advances in Neural Information Processing Systems, volume 34, pages 11467-21479, Dec 2021.
[32] Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Laetitia Kameni, and Richard Vidal. Federated multi-task learning under mixture of distributions. In Proceedings of International Conference on Neural Information Processing Systems, volume 34, pages 15434 15447, Dec 2021.
[33] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication Effficient Learning of Deep Networks from Decentralized Data. In Proceedings of International Conference on Artificial Intelligence and Statistics, volume 54, pages 1273- 1282, Apr 2017.
[34] Aritra Mitra, Hamed Hassani, and George J. Pappas. Online federated learning. In IEEE Conference on Decision and Control (CDC), pages 4083-4090, Dec 2021.
[35] Mehdi Neshat, Bradley Alexander, Markus Wagner, and Yuanzhong Xia. A detailed comparison of meta-heuristic methods for optimising wave energy converter placements. In Proceedings of the Genetic and Evolutionary Computation Conference, page 1318-1325, Jul 2018.
[36] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceed- ings of International Conference on Neural Information Processing Systems, pages 1177-1184, Dec 2007.
[37] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. FetchSGD: Communication-fficiee federated learning with sketching. In Proceedings of International Conference on Machine Learning, volume 119, pages $253-8265, Jul 2020.
12

---

[38] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Proceedings of International Conference on Neural Information Processing Systems, page 3218-3228, 2017.
[39] Doyen Sahoo, Steven C.H. Hoi, and Bin Li, Online multiple kernel regression. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 293-302, 2014.
[40] Doyen Sahoo, Steven C. H. Hoi, and Bin Li. Large scale online multiple kernel regression with application to time-series prediction. ACM Transactions on Knowledge Discovery from Data, 13(1), Jan 2019.
[41] Bernhard Scholkopf and Alexander J. Smola. Learning with Kemeess Support Vector Machines, Regularization, Oplimization, and Beyond. MIT Press, Cambridge, MA, USA, 2001.
[42] Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik. Personalized federated learning using hypernetworss. In Proceedings of International Conference on Machine Learning. volume 139, pages 9489-9509 Jul 2021.
[43] Yanning Shen, Tianyi Chen, and Georgios B. Giannakis. Random feature- based online multi- kernel learning in environments with unknown dynamics. Journal of Machine Learning Research, 20(1 (0(1):773-808 Jan 2019.
[44] Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Tallwalkar, Federated multi-task learning, In Advances in Neural Information Processing Systems, volume 30, pages 4424-4434, Dec 2017.
[45] Sören Sonnenburg, Gunnar Rätsch, Christin Schäfer, and Bernhard Schölkopf. Large scale multiple kernel learning. Journal of Machine Learning Research, 7:1531-1565, Dec 2006.
[46] Benyuan Sun, Hongxing Huo, YI YANG, and Bo Bai. Partialfed: Cross-domain personalized federated learning via partial initialization. In Proceedings of International Conference on Neural Information Processing Systems, volume 34, pages (3309-23320) Dec 2021.
[47] Joaquín Sospeda,, Raúl Montoliu, Adolfo Martínez- Joan P. Avariento, Tomás J. Arnau, Mauri Benedito-Bordonau, and Joaquín Huerta. Ujüindoorloc: A new multi-building and multi-floor database for wlan fingerprint- indoor localization problems. In International Conference Indoor Positioning and Indoor Navigation (IPIN), pages 261-270, Oct 2014.
[48] Grace Wahba. Spline Models for Observational Data. Society for Industrial and Applied Mathematics, 1990.
[49] Christopher K. I. Williams and Matthias Seeger. Using the nyström method speed up kernel machines. In Proceedings of the International Conference on Neural Information Processing Systems, page 661-667, Jan 2000.
[50] Jie Zhang, Song Guo, Xiaosong Ma, Haozhao Wang, Wenchao Xu, and Feijie Wu. Parameter- ized knowledge transfer for personalized federated learning. In Proceedings of International Conference Neural Information Processing Systems, volume 34, pages 10092-10104, Dec 2021.
[51] Shuyi Zhang, Bin Guo, Anlan Dong. Jing He, Ziping Xu, and Song Xi Chen. Cautionary tales on air-quality improvement in beijing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473(2205):20170457, 2017.
[52] Xiao Zhang and Shizhong Liao. Incremental randomized sketching for online kernel learning. In Proceedings of International Conference on Machine Learning, pages 7394-7403, Jun 2019,
[53] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, volume 32, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In section 4 we mention that
the proposed multi-kernl leanring algorithm POF-MKL runs slower than single kernel learning algorithm OFSKL.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not foresee any direct societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please see section 3.2 where we explicitly explain the assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs of theoretical results are presented in Appendices) A and B
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We provide code, data, and instructions to reproduce the main experimental results in the supplementary material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] In section and Appendix C detailed information about experimental setup is provided.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We did the experiments for 20 sets of random features. In Appendix C the standard deviation of MSE is reported.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] In Table we report run time of algorithms. Also, in Appendix C we explain that all experiments were carried out using Intel(R) Core(TM) i7- 105TOU CPU 1.80 GHz 2.30 GHz processor with 64-bit Windows operating system.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses cxisting assets, did you cite the creators? [Yes] In section 4 we cited all datasets used for experiments.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] In section 4 point out that datasets are downloaded from UCI
Machine Learning Repository.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xLTWwL4f4Vj", "reviewer": "Reviewer_wHGi", "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.\n\nThe authors empirically evaluated the proposed method on several datasets and it seems that the proposed method exhibited impressive performance and outperformed the baseline methods.\n\nThe main contributions of the paper include:\n\n- Proposing the personalized federated MKL method to tackle the heterogeneous in federated learning.\n- Proving the convergence rate of the proposed algorithm.\n- Saving communication cost compared to existing algorithms, both theoretically and experimentally.", "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 ?\n2. I would like to know how equation 7 is derived.", "limitations": "N.A.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Prons:\n\n1. The paper is technically sound and, for the most part, well-written, with the authors' motivations and explanation of the method conceived quite straightforward. \n2. The method has a convergence guarantee.\n3. The authors also clearly emphasise their contribution and their novelty.\n4. The results are convincing and show quite some promise.\n\nCons:\n\n1. It would be better if the authors can provide some complexity analysis of the proposed algorithm and compared methods.\n2. It would be better if the authors can add high-level intuition to help readers better understand the method section. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RIxCghhCVl", "reviewer": "Reviewer_KZ2t", "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.", "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?\n\nIn 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\".\n\nnegative societal impact: N/A", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. 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.\n\n2. 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\ncommunication bandwidth.\n\nCons/Questions:\n\n1. 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”.\n\n2. It would be interesting to see the performance of the real online learning tasks such as online regressions and time-series predictions.\n\n3. It would be more convincing to provide the convergence time/speed of the proposed algorithm. \n\n4. 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?\n\n[1] Chae, J., & Hong, S. (2021). Multiple Kernel-Based Online Federated Learning. arXiv preprint\narXiv:2102.10861.\n\n5. 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?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I8IAgreSIi", "reviewer": "Reviewer_dLL3", "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.", "questions": "- Please explain how to choose the dictionary of kernels for different tasks.\n- Does the regret have a lower bound? If so, can it show the optimal of the proposed method?\n- 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.\n", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- 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.\n- The theoretical analysis is solid and supports their proposed algorithm well.\n\nWeaknesses\n- 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.\n- 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.\n- 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.\t", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hp-dQH4HX9", "reviewer": "Reviewer_rNRS", "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}$.  \n\nThe 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.  \n\n", "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.  \n\n### Post rebuttal\nThe 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. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe paper is overall well written and easy to follow. The proposed idea is relevant and the theoretical results are correct. \n\n## Weaknesses\n\n### Originality and Related Work Discussion\n\n**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. \n\n**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).\n\n### Technical soundness\n\n**Notation.** &nbsp; The notation is sometime misleading and makes some parts of the paper hard to follow. For example:\n\n* The notation $\\hat{f}_{RF, it}$   hides the dependence  on $\\Theta$ \n\n* $\\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}$ \n\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})$\n\n**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.\n\nP.S.: *The assumption that each data sample is bounded (line 227) is not needed.*\n\n\n## References \nMarfoq, 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.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept